Ограничениям (2.49) и (2.50).

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

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

Если х_ij — количество товара, перевезенного от i-гo поставщика к j-ому потребителю, то математическая формулировка выглядит так:

(2.60)

(i=1,2,…,m), (2.61)

(j=1,2,…,n), (2.62)

(i=1,2,…,m; j=1,2,…,n). (2.63)

Задача (2.60) — (2.63) является задачей ЛП, в которой m*n переменных и m + n ограничений, записанных в виде равенств.

Если общее количество товара у всех поставщиков равно общему количеству товара, требуемого потребителями, т. е.

(2.64)

то такая модель транспортной задачи называется закрытой. В противном случае, модель называется открытой. Если модель является открытой, то соответствующие ограничения принимают форму неравенств. Отметим, что задача (2 61) — (2 63), относится к закрытой модели.

Транспортную задачу обычно представляют в виде таблицы.

Таблица 2.7.1

Потребители

П

о

с

т

а

в

щ

и

к

и

В каждую клетку в верхний левый угол записывают соответствующее значение С_ij.

Сделаем одно замечание. Мы видели, что число уравнений, составляющих ограничения транспортной задачи, равно m + n. Однако, на самом деле одно из уравнений этой системы (причем любое) является линейной комбинацией остальныхуравнений, что можно проверить непосредственно.

Тот факт, что в транспортной задаче одно из уравнений является лишним, следует из равенства запасов и потребностей. Таким образом, число линейно-независимых уравнений, составляющих ограничения в транспортной задаче, равно m + n — 1. Этим важным фактом воспользуемся в дальнейшем. В соответствии с теоремой II. 1 это означает, что в оптимальном плане не может быть больше, чем m + n — 1 ненулевых перевозок.

Конечно, можно найти решение транспортной задачи с помощью известных методов решения задач ЛП (например, симплекс-метода). Но при этом нужно учитывать то, что в транспортных задачах число переменных достаточно велико. Поэтому в дальнейшем мы рассмотрим специфичные способы решения.

Построение первоначального опорного плана транспортной задачи

Идейно методы решения транспортных задач это те же алгоритмы симплекс-метода, представленные для транспортной задачи в удобной форме. Сначала находится первоначальный опорный план, затем осуществляется процесс улучшения решения до тех пор, пока найденный опорный план не станет оптимальным. Рассмотрим два способа получения первоначального опорного плана.