Пусть имеется m пунктов отправления A1, A2, …, Am, в которых сосредоточен однородный груз в количестве соответственно a1, a2, …,am условных единиц. Этот груз необходимо доставить в n назначения B1, B2, …, Bn. Потребность пунктов назначения в грузе соответственно b1, b2, …, bn условных единиц. Известны тарифы сij перевозок единицы груза от пункта отправления с номером i в пункт назначения с номером j. Требуется так составить план перевозок, чтобы максимально удовлетворить потребителей и чтобы общие затраты на перевозку были минимальными.
Обозначим через xij - количество единиц груза, перевозимого из пункта отправления с номером i в пункт назначения с номером j. Сумма запасов , сумма потребностей .
Определение. Если , то модель транспортной задачи называется закрытой, иначе модель ТЗ называется открытой.
Определение. План X=(x*ij), i =1,2,…, m, j =1,2,…, n, при котором функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи.
Обычно исходные данные транспортной задачи записываются в таблицу:
|
|
Пункты отправления | Пункты назначения | Запасы | ||||
... | ... | |||||
... | ... | |||||
... | ... | ... | .... | ... | ... | ... |
... | ... | |||||
... | ... | ... | ... | ... | ... | ... |
... | ... | |||||
Потребности |
Любое решение транспортной задачи (х11,х12,…,хmn) называется распределением поставок.
Число переменных xij в транспортной задаче с m пунктами отправления и n пунктами назначения равно mn, а число уравнений в системе ограничений равно (m+n).