Постановка задачи. 
Экономические задачи, сводящиеся к транспортной модели

Некоторый однородный продукт, сосредоточенный у m поставщиков А_i в количестве а_i (i = 1,., m) единиц соответственно, необходимо доставить n потребителям В_j в количестве b_j (j = 1,., n) единиц. Известна стоимость с_ij перевозки единицы груза от i-го поставщика к j-му потребителю.

Необходимо составить план перевозок, позволяющий вывести все грузы, полностью удовлетворить потребности и имеющий минимальную стоимость. Обозначим через х_ij количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю. Так как от i-го поставщика к j-му потребителю запланировано к перевозке х_ij единиц груза, то стоимость перевозки составит с_ijx_ij. Стоимость всего плана выразится двойной суммой:

Систему ограничений получаем из следующих условий задачи:

а) все грузы должны быть перевезены, т. е.

б) все потребности должны быть удовлетворены, т. е.

Таким образом, математическая модель транспортной задачи имеет следующий вид: найти минимальное значение линейной функции.

при ограничениях.

В рассмотренной модели предполагается, что суммарные запасы равны суммарным потребностям, т. е.

Транспортная задача, в которой суммарные запасы и потребности совпадают, т. е. выполняется данное условие, называется закрытой моделью; в противном случае — открытой. Для открытой модели может быть два случая:

а) суммарные запасы превышают суммарные потребности.

б) суммарные потребности превышают суммарные запасы.

Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений. Найти минимальное значение линейной функции:

При ограничениях.

Открытая модель решается приведением к закрытой модели. В случае «а», когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель В_{n + 1}, потребность которого:

В случае «б», когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик А_{m + 1}, запасы которого:

Как стоимость перевозки единицы груза до фиктивного потребителя, так и стоимость перевозки груза от фиктивного поставщика полагаются равными нулю, поскольку груз в обоих случаях не перевозится.

Транспортная задача имеет n + m уравнений с mn неизвестными.

Матрицу Х = (х_ij) _{m, n}, удовлетворяющую условиям (3) — (5), называют планом перевозок транспортной задачи (х_ij-перевозками).

План Х*, при котором целевая функция (2) обращается в минимум, называется оптимальным.

Теорема 1.

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

План транспортной задачи называется опорным, если положительным перевозкам соответствует система линейно независимых векторов P_ij (i = 1. m, j = 1… n), где P_ij — векторы при переменных х_ij (i = 1… m, j = 1… n) в матрице системы ограничений (3) — (5).

Теорема 2.

Существует план, содержащий не более m + n — 1 положительных перевозок, при этом система векторов P_ij, соответствующая таким перевозкам (х_ij > 0), линейно независима.

Таким образом, опорный план транспортной задачи содержит m + n — 1 положительных перевозок. Если менее (m + n — 1) компонент опорного плана положительный, то он называется вырожденным. Дадим другое определение опорного плана.

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