Тема. Математическая постановка транспортной задачи

Пусть имеется m пунктов отправления A₁, A₂, …, A_m, в которых сосредоточен однородный груз в количестве соответственно a₁, a₂, …,a_m условных единиц. Этот груз необходимо доставить в n назначения B₁, B₂, …, B_n. Потребность пунктов назначения в грузе соответственно b₁, b₂, …, b_n условных единиц. Известны тарифы с_ij перевозок единицы груза от пункта отправления с номером i в пункт назначения с номером j. Требуется так составить план перевозок, чтобы максимально удовлетворить потребителей и чтобы общие затраты на перевозку были минимальными.

Обозначим через x_ij - количество единиц груза, перевозимого из пункта отправления с номером i в пункт назначения с номером j. Сумма запасов , сумма потребностей .

Определение. Если , то модель транспортной задачи называется закрытой, иначе модель ТЗ называется открытой.

Определение. План X=(x^*_ij), i =1,2,…, m, j =1,2,…, n, при котором функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записываются в таблицу:

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

Любое решение транспортной задачи (х₁₁,х₁₂,…,х_mn) называется распределением поставок.

Число переменных x_ij в транспортной задаче с m пунктами отправления и n пунктами назначения равно mn, а число уравнений в системе ограничений равно (m+n).