Транспортная задача открытого типа

В общем виде транспортная задача формулируется в следующем виде.

Заданы m пунктов отправления с запасами грузов, n пунктов потребления подали заявки на груз в количестве, известна стоимость перевозки единицы груза из i-го пункта отправления в j-й пункт назначения. Вводятся переменные, определяющие количество отправляемых грузов из i-го склада в j-й пункт потребления, — x_ij.

Ставится задача минимизировать стоимость перевозок, поэтому целевая функция будет.

. (1).

Количество груза, отправляемого с каждого склада, не должно превышать имеющихся запасов:

. (2).

Условие выполнения заявок каждого пункта потребления запишется в виде.

. (3).

При равенстве количества запасов и заявок пунктов потребления, т. е.

(4).

задача называется сбалансированной. В случае если заявок больше или меньше запасов, транспортная задача называется открытой (несбалансированной). Решение таких задач возможно путем введения дополнительных условий. Рассматриваются два случая.

1. Если запасы больше потребностей:, то для сведения этой задачи к сбалансированной задаче вводится фиктивный пункт назначения с потребностями.

(5).

и допущением, что стоимость перевозки единицы груза между любым пунктом i и фиктивным пунктом равна нулю, т. е. c_{i (n+1)} = 0, i=.

Очевидно, что оптимальное решение такой задачи будет оптимальным и для исходной.

2. Когда запасы меньше потребностей удовлетворение всех пунктов в этом случае невозможно, поэтому необходимо управлять транспортировкой таким образом, чтобы наиболее важные пункты удовлетворялись полнее и чтобы стоимость перевозок была бы минимальной.

Обозначим: r_j — величина ущерба на одну единицу груза в результате невыполнения запроса j-го пункта. Тогда для приведения этой задачи к основной вводится фиктивный пункт отправления А_m+1 с запасами.

(6).

и предполагается, что стоимость перевозки единицы груза между этим пунктом и любым пунктом назначения равна нулю, т. е. c_(m+1)j = 0 для всех j=.

Далее минимизируем затраты.

(7).

где y_j — количество груза, «недовезенного» в пункт j при тех же ограничениях и дополнительном условии.

. (8).