Глава2 ТРАНСПОРТНАЯ ЗАДАЧА

Под транспортной задачей в дальнейшем понимается задача линейного программирования, в которой требуется найти оптимальный (по стоимости) план перевозок некоторого однородного груза от конечного числа поставщиков A1, A2 , , Am с заданными запасами

a1, ,am к конечному числу потребителей B1, B2 , , Bn с потребностями b1, ,bn . Стоимость cij перевозки единицы груза от поставщика Ai к потребителю Bj предполагается известной.

Отметим, что данная постановка задачи может быть значительно расширена или изменена. Например, в приложениях часто рассматриваются задачи перевозки неоднородного груза. Также в качестве критерия оптимальности можно рассматривать время перевозок (транспортная задача по критерию времени). Подобного рода задачи решаются сведением к однородной транспортной задаче, или для них разработаны другие методы, изложение которых остается за рамками данной книги.

§ 2.1. Постановка задачи

Итак, пусть X =(xij ) – m ×n матрица, где xij – объем перевозок от i -го поставщика к j -му потребителю. Тогда общие затраты на пе-

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

m n

z(X ) = ∑∑cij xij → min

i=1 j=1

при условиях

23

Первая часть нетривиальных ограничений означает, что все потребности удовлетворены, вторая часть – то, что весь груз вывезен от поставщиков.

Замечание 2.1. Если запасы и потребности задаются целыми числами, то транспортная задача имеет целочисленное оптимальное решение, поэтому транспортную задачу относят формально к задачам целочисленного линейного программирования.

Можно показать, что число базисных переменных в системе ограничений (2.1) равно m + n −1.

Определение 2.1. Решение X =(xij ) (оптимальное решение X * =(xij* )) транспортной задачи, удовлетворяющее условиям (2.1) и

имеющее не более m + n −1 занятой клетки (ненулевой перевозки), бу-

дем называть опорным планом (оптимальным опорным планом)

транспортной задачи.

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

m

Общие запасы определяются суммой ∑ai , а общая потребность –

i=1

24

n

∑bj . Транспортная задача называется задачей с правильным балан-

j=1

лансом, а ее модель – открытой.

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

Алгоритм решения транспортной задачи с правильным балансом излагается в курсе «Линейная алгебра». В этом параграфе мы напомним основные методы построения начального опорного плана и метод потенциалов решения транспортной задачи.

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

груза из одного из пунктов

Пример 2.1. Рассмотрим транспортную задачу, заданную таблицей 2.2. В правом нижнем углу стоит сумма запасов (и, одновременно, сумма потребностей, так как модель закрытая)

140+160+100=80+40+ +150+ 130=400.

25

исключаем из рассмотрения, а оставшиеся запасы первого поставщика, т.е. 60, переносим следующим потребителям. Мы можем 40 записать потребителю В2 (столбец В2 исключается), а оставшиеся 20 – В3

и исключить первую строку из дальнейшего рассмотрения.

Далее, так как потребности В3 равны 150, а 20 единиц груза ему

уже доставлены, то оставшиеся 130 единиц доставляются от второго поставщика A2 (заполняем клетку A2B3 ) . С толбец В3 исключаем из

рассмотрения, а оставшиеся запасы второго поставщика (30 единиц) записываем потребителю В4 . Окончательно потребности последнего

удовлетворяются за счет поставщика A3 : вписываем в клетку A3B4 пе-

ревозку 100. Заметим, что, так как исходная задача - с правильным балансом, то потребности последнего потребителя B4 равны запасам по-

ставщика A3 , т.е. 100. Получаем таблицу 2.3 с начальным опорным планом

Суммарная стоимость перевозок равна

z(X ) =1 80 +11 40 +3 20 +8 130 + 2 30 +6 100 = 2280.

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

26

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

щика A1 равны 140, а потребности В1 – 80, поэтому в клетку A1B1 вписываем максимально возможную перевозку 80, и потребителя В1 ис-

ключаем из рассмотрения. В оставшейся части таблицы выбираем минимальный тариф, т.е.

потребителей В2 , В3 выбираем клетку с минимальным тарифом. Это A1B3 с тарифом 3. Запасы (оставшиеся) поставщика A1 равны 60, а по-

возок равна

z(X ) =1 80 +3 60 + 4 30 + 2 130 +5 10 +14 90 =1950 < 2280.

Таким образом, опорный план, построенный методом минимального тарифа, лучше, чем план, полученный методом северо-западного угла.

Применим, наконец, к исходной задаче метод аппроксимации Фогеля. Для этого найдем разность между двумя минимальными тарифами для каждой строки и столбца таблицы и запишем их в дополнительно образованные строки и столбцы (см. таблицу 2.5). В строке A1 минимальный тариф равен 1, а следующий за ним 3, поэтому раз-

ность между ними 4-2=2; в строке A2 минимальный тариф равен 2, а следующий за ним 4, поэтому разность между равна 2; аналогично,

27

для строки A3 разность между минимальным тарифом 3 и следующим

за ним 5 равна 2. Итак, три двойки записываем в первый дополнительный столбец.

Аналогично для столбцов разности 3-1=2, 5-4=1, 8-3=5 и 6-2=4 записываем в первую дополнительную строку. Теперь из всех разностей выбираем максимальную, т.е. 5 в столбце B3 , и в клетку A1B3 с

минимальным тарифом в этом столбце записываем максимально возможную перевозку 140. При этом поставщика A1 исключаем из рас-

смотрения. Теперь аналогично вычисляем разности между оставшимися минимальными тарифами и заполняем вторые дополнительные столбец и строку, не учитывая тарифы в строке A1 . Видим, что теперь

максимальная разность получается в столбце B1 и перевозку 80 записываем в клетку A3B1 с минимальным тарифом 3 в этом столбце (первую строку мы исключили из рассмотрения). Столбец B1 аналогично исключаем из рассмотрения. Как видно из таблицы, на следующем

Таблица 2.5

шаге вписываем перевозку 10 в клетку A2B3 и исключаем столбец B3 , затем – максимально возможную перевозку 40 в клетку A2B4 и исключаем из рассмотрения столбец B4 . Теперь для вычисления дальнейших разностей остается единственный столбец B2 , поэтому в качестве разностей по строкам записываем нули. Далее, в клетку A2B2 записываем 20, а на последнем шаге записываем перевозку 20 в клетку A3B2 . По-

28