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

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

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

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

. (7.1)

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

. (7.2)

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

. (7.3)

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

, (7.4)

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

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

(7.5)

и допущением, что стоимость перевозки единицы груза между любым пунктом i и фиктивным пунктом равна нулю, т.е. c_i₍_n₊₁₎ = 0, i= .

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

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

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

(7.6)

и предполагается, что стоимость перевозки единицы груза между этим пунктом и любым пунктом назначения равна нулю, т.е. c₍_m₊₁₎_j = 0 для всех j= .

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

, (7.7)

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

. (7.8)