В общем виде транспортная задача формулируется в следующем виде.
Заданы m пунктов отправления с запасами грузов , n пунктов потребления подали заявки на груз в количестве , известна стоимость перевозки единицы груза из i -го пункта отправления в j -й пункт назначения. Вводятся переменные, определяющие количество отправляемых грузов из i -го склада в j -й пункт потребления, – xij.
Ставится задача минимизировать стоимость перевозок, поэтому целевая функция будет
. (7.1)
Количество груза, отправляемого с каждого склада, не должно превышать имеющихся запасов:
. (7.2)
Условие выполнения заявок каждого пункта потребления запишется в виде
. (7.3)
При равенстве количества запасов и заявок пунктов потребления, т.е.
, (7.4)
задача называется сбалансированной. В случае если заявок больше или меньше запасов, транспортная задача называется открытой (несбалансированной). Решение таких задач возможно путем введения дополнительных условий. Рассматриваются два случая.
1. Если запасы больше потребностей: , то для сведения этой задачи к сбалансированной задаче вводится фиктивный пункт назначения с потребностями
|
|
(7.5)
и допущением, что стоимость перевозки единицы груза между любым пунктом i и фиктивным пунктом равна нулю, т.е. ci(n+1) = 0, i= .
Очевидно, что оптимальное решение такой задачи будет оптимальным и для исходной.
2. Когда запасы меньше потребностей удовлетворение всех пунктов в этом случае невозможно, поэтому необходимо управлять транспортировкой таким образом, чтобы наиболее важные пункты удовлетворялись полнее и чтобы стоимость перевозок была бы минимальной.
Обозначим: rj – величина ущерба на одну единицу груза в результате невыполнения запроса j -го пункта. Тогда для приведения этой задачи к основной вводится фиктивный пункт отправления Аm+1 с запасами
(7.6)
и предполагается, что стоимость перевозки единицы груза между этим пунктом и любым пунктом назначения равна нулю, т.е. c(m+1)j = 0 для всех j = .
Далее минимизируем затраты
, (7.7)
где yj – количество груза, «недовезенного» в пункт j при тех же ограничениях и дополнительном условии
. (7.8)