3.5 Опорный план транспортной задачи
Метод решения транспортной задачи представляет собой развитие идеи симплекс-метода [3] и тоже основан на переборе опорных планов этой задачи. Опорный план должен включать столько базисных переменных, сколько в задаче линейного программирования независимых уравнений.
Если бы система ограничений закрытой транспортной задачи была линейно независимой, то базисных переменных было бы m+n. Но из задач (6) и (7) видно, что такая система линейных уравнений является линейно зависимой (например, если сложить все ограничения из первой и все из второй группы, а затем вычесть из одной суммы другую, в левой части получится ноль). Можно доказать, что если удалить из системы одно ограничение, то она станет независимой (одно ограничение является лишним, оно следует из остальных). Следовательно, базисных переменных должно быть m+n-1.
Для построения опорного плана транспортной задачи разработано несколько способов, наиболее распространенным является метод северо-западного угла.
3.5.1 Метод северо-западного угла построения опорного плана транспортной задачи
Этот метод принято сокращенно обозначать МСЗУ.
Представим опорный план транспортной задачи в виде таблицы, строки которой будут соответствовать поставщикам (с их запасами ai), столбцы – потребителям (с их потребностями bj), а ячейки – компонентам опорного плана (например, в первой строке первого столбца будет стоять значение переменной x11). Будем заполнять лишь те ячейки, которые будут соответствовать базисным компонентам, переменные в незаполненных ячейках равны нулю.
Применение метода начинают с того, что рассматривают левый верхний («северо-западный») угол таблицы, который соответствует переменной x11, т.е. перевозкам от первого поставщика к первому потребителю. Сравнивают их запас и потребность — a1 и b1.
1). Если a1 < b1, то x11 = a1, т.е. всю продукцию первого поставщика отправляют к первому потребителю.
После этого первую строку исключают из рассмотрения (все остальные x1j = 0). В самом деле, ведь запасы первого поставщика уже закончились. Следовательно, больше никому ничего везти от него нельзя.
Первому столбцу вместо b1 ставят в соответствие b1`= b1 — a1, поскольку потребность первого потребителя снизилась (она уже частично удовлетворена).
Затем снова рассматривают левый верхний угол оставшейся части таблицы (без первой строки), т.е. х21.
2). Если a1 > b1 , то x11 = b1., т.е. первого потребителя полностью удовлетворяют за счет запасов первого поставщика, после чего этого потребителя (первый столбец) исключают. Запасы первого поставщика уменьшаются a1`= a1 — b 1.
Затем рассматривают левый верхний угол оставшейся части таблицы (без первого столбца), т.е. х12.
3). Если a1 = b1, то можно исключить либо столбец, либо строку.
Далее действуют аналогично, т.е. либо принимают х21 = min 1`;a2>, либо принимают х12 = min 2; a1`>. Процесс продолжается до тех пор, пока не будут исключены из рассмотрения все ячейки. При этом окажется заполненной m+n-1 клетка таблицы.
Рассмотрим применение данного метода к задаче о холодильных установках. Для этого необходимо построить таблицу из трех строк и столбцов, соответствующих шести центрам производства и сбыта (включая дополнительный). Чтобы построить опорный план, необходимо заполнить 3 + 3 – 1 = 5 клеток этой таблицы.
Ее левый верхний угол будет соответствовать поставкам холодильных установок из Стокгольма в Лейпциг (переменной x11). Так как в Стокгольме производится меньше установок, чем необходимо поставить в Лейпциг (a1 < b1, 120 < 150), то направим все эти 120 установок в Лейпциг (x11 = 120). После этого Стокгольм (первую строку таблицы) можно исключить из рассмотрения, так как холодильных установок в этом центре сбыта больше не осталось. В Лейпциг же необходимо поставить еще 150 – 120 = 30 установок, поэтому Лейпцигу (первый столбец) ставится в соответствие новое значение потребностей – 30:
дополнительный центр сбыта
Глава2 ТРАНСПОРТНАЯ ЗАДАЧА
Под транспортной задачей в дальнейшем понимается задача линейного программирования, в которой требуется найти оптимальный (по стоимости) план перевозок некоторого однородного груза от конечного числа поставщиков A 1 , A 2 , , A m с заданными запасами a 1 , , a m к конечному числу потребителей B 1 , B 2 , , B n с потребностями b 1 , , b n . Стоимость c ij перевозки единицы груза от поставщика A i к потребителю B j предполагается известной. Отметим, что данная постановка задачи может быть значительно расширена или изменена. Например, в приложениях часто рассматриваются задачи перевозки неоднородного груза. Также в качестве критерия оптимальности можно рассматривать время перевозок (транспортная задача по критерию времени). Подобного рода задачи решаются сведением к однородной транспортной задаче, или для них разработаны другие методы, изложение которых остается за рамками данной книги.
§ 2.1. Постановка задачи
Итак, пусть X = ( x ij ) – m × n матрица, где x ij – объем перевозок от i -го поставщика к j -му потребителю. Тогда общие затраты на пе-
| m | n | |
| ревозку груза определяются функцией | z ( X ) = ∑∑ c ij x ij . Математиче- | |
| i = 1 | j = 1 | |
ская постановка транспортной задачи определяется следующей задачей линейного программирования m n z ( X ) = ∑∑ c ij x ij → min i = 1 j = 1 при условиях
| ∑ x ij = b j , | j = 1, , n , | |
| m | ||
| i = 1 | ||
| n | i = 1, , m , | (2.1) |
| ∑ x ij = a i , | ||
| j = 1 | ||
| x | ≥ 0. | |
| ij | ||
Первая часть нетривиальных ограничений означает, что все потребности удовлетворены, вторая часть – то, что весь груз вывезен от поставщиков. Замечание 2.1. Если запасы и потребности задаются целыми числами, то транспортная задача имеет целочисленное оптимальное решение, поэтому транспортную задачу относят формально к задачам целочисленного линейного программирования. Можно показать, что число базисных переменных в системе ограничений (2.1) равно m + n − 1 .
| Поставщики | Потребители | Запасы | |||||
| B 1 | B 2 | … | B j | … | B n | ||
| A 1 | c 11 | c 12 | … | c 1 j | … | c 1 n | a 1 |
| x 11 | x 12 | x 1 j | x 1 n | ||||
| A | c | с | … | с | … | c | a |
| 2 | 21 | 22 | 2 j | 2 n | 2 | ||
| x 21 | x 22 | x 2 j | x 2 n | ||||
| … | … | … | … | … | … | … | … |
| A i | c i 1 | c i 2 | … | c ij | … | c in | a i |
| x i 1 | x i 2 | x ij | x in | ||||
| … | … | … | … | … | … | … | … |
| A m | c m 1 | c m 2 | … | c mj | … | c mn | a m |
| x m 1 | x m 2 | x mj | x mn | ||||
| Потребности | b 1 | b 2 | … | b j | … | b n | |
| Таблица 2.1 | |||||||
Определение 2.1. Решение X = ( x ij ) (оптимальное решение X * = ( x ij * ) ) транспортной задачи, удовлетворяющее условиям (2.1) и имеющее не более m + n − 1 занятой клетки (ненулевой перевозки), бу- дем называть опорным планом (оптимальным опорным планом) транспортной задачи. Исходные данные задачи представляют в виде таблицы 2.1. m Общие запасы определяются суммой ∑ a i , а общая потребность – i = 1
n ∑ b j . Транспортная задача называется задачей с правильным балан- j = 1
| m | n | |
| сом , а ее модель закрытой , если ∑ a i | = ∑ b j , то есть суммарные запа- | |
| i = 1 | j = 1 | |
| сы | поставщиков равны суммарным | запросам потребителей. Если |
| m | n | |
| ∑ a i ≠ ∑ b j , то такая задача называется задачей с неправильным ба- | ||
| i = 1 | j = 1 | |
лансом , а ее модель – открытой .
§ 2.2. Построение начального опорного плана транспортной задачи
Алгоритм решения транспортной задачи с правильным балансом излагается в курсе «Линейная алгебра». В этом параграфе мы напомним основные методы построения начального опорного плана и метод потенциалов решения транспортной задачи. Первым этапом решения является построение начального опорного плана, т.е. плана перевозок, удовлетворяющего всем ограничениям конкретной транспортной задачи. Сущность методов состоит в том, что начальный опорный план находят за не более чем m + n − 1 шагов (по числу базисных переменных), на каждом из которых в транспортной таблице заполняют одну клетку, которую называют занятой. Заполнение одной из клеток обеспечивает полностью либо удовлетворение потребности в грузе одного из пунктов назначения (того, в столбце которого находится заполненная клетка), либо вывоз груза из одного из пунктов
| B 1 | B 2 | B 3 | B 4 | a i | |
| A 1 | 1 | 11 | 3 | 13 | 140 |
| A 2 | 12 | 4 | 8 | 2 | 160 |
| A 3 | 3 | 5 | 14 | 6 | 100 |
| b j | 80 | 40 | 150 | 130 | 400 |
| Таблица 2.2 | |||||
оптимального.
отправления (из того, в строке которого находится заполняемая клетка). Различаются эти планы по принципам выбора заполняемых клеток и, в зависимости от этого, могут давать планы, более или менее отличные от
Пример 2.1. Рассмотрим транспортную задачу, заданную таблицей 2.2. В правом нижнем углу стоит сумма запасов (и, одновременно, сумма потребностей, так как модель закрытая) 140+160+100=80+40+ +150+ 130=400.
| Напомним | сначала | метод северо-западного | угла. Заполнение | |||||||
| таблицы начинаем с левого | ||||||||||
| B 1 | B 2 | B 3 | B 4 | a i | верхнего (северо-западного) | |||||
| A 1 | 1 | 40 | 11 | 3 | 13 | 140 | угла таблицы. Так как по- | |||
| 80 | 20 | |||||||||
| требности первого потреби- | ||||||||||
| A 2 | 12 | 4 | 8 | 2 | 160 | |||||
| теля В 1 равны 80, а запасы | ||||||||||
| 130 | 30 | |||||||||
| A 3 | 3 | 5 | 14 | 6 | 100 | первого поставщика A 1 | рав- | |||
| 100 | ны 140, то в клетку | A 1 B 1 | ||||||||
| b j | 80 | 40 | 150 | 130 | 400 | |||||
| вписываем | максимально | |||||||||
| Таблица 2.3 | возможную перевозку | 80. | ||||||||
| Потребности В 1 | полностью удовлетворены, поэтому первый столбец | |||||||||
исключаем из рассмотрения, а оставшиеся запасы первого поставщика, т.е. 60, переносим следующим потребителям. Мы можем 40 записать потребителю В 2 (столбец В 2 исключается), а оставшиеся 20 – В 3 и исключить первую строку из дальнейшего рассмотрения . Далее, так как потребности В 3 равны 150, а 20 единиц груза ему уже доставлены, то оставшиеся 130 единиц доставляются от второго поставщика A 2 (заполняем клетку A 2 B 3 ) . С толбец В 3 исключаем из рассмотрения, а оставшиеся запасы второго поставщика (30 единиц) записываем потребителю В 4 . Окончательно потребности последнего удовлетворяются за счет поставщика A 3 : вписываем в клетку A 3 B 4 пе- ревозку 100. Заметим, что, так как исходная задача — с правильным балансом, то потребности последнего потребителя B 4 равны запасам по- ставщика A 3 , т.е. 100. Получаем таблицу 2.3 с начальным опорным планом
| 80 | 40 | 20 | 0 |
| 0 | 0 | 130 | 30 |
| X = | . | ||
| 0 | 0 | 0 | 100 |
Суммарная стоимость перевозок равна z ( X ) = 1 80 + 11 40 + 3 20 + 8 130 + 2 30 + 6 100 = 2280. Из решения видно, что метод северо-западного угла, с одной стороны, достаточно прост с точки зрения построения, а с другой стороны, не учитывает стоимость перевозок. Поэтому опорный план, построенный методом северо-западного угла, как правило, далек от оптимального.
Построим теперь для этой же задачи начальный опорный план методом минимального тарифа. Суть этого метода состоит в том, что в клетки с наименьшими тарифами помещают максимально возможные перевозки. Итак, в таблице исходной задачи выбираем клетку с минимальным тарифом, т.е. клетку A 1 B 1 с тарифом 1 . Запасы постав- щика A 1 равны 140, а потребности В 1 – 80, поэтому в клетку A 1 B 1 вписываем максимально возможную перевозку 80, и потребителя В 1 ис- ключаем из рассмотрения. В оставшейся части таблицы выбираем минимальный тариф, т.е.
| B 1 | B 2 | B 3 | B 4 | a i | клетку A B с тарифом 2. За- | ||||
| 1 | 11 | 3 | 13 | ||||||
| A 1 | 140 | 2 | 4 | ||||||
| 80 | 60 | пасы поставщика A 2 | равны | ||||||
| A | 12 | 4 | 8 | 2 | 160 | 140, а потребности В 4 | — 130, | ||
| 2 | 30 | 130 | поэтому в клетку A 2 B 4 | запи- | |||||
| A 3 | 3 | 5 | 14 | 6 | 100 | ||||
| 10 | 90 | сываем перевозку 130 и по- | |||||||
| b j | 80 | 40 | 150 | 130 | 400 | требителя | В | исключаем из | |
| 4 | |||||||||
| Таблица 2.4 | рассмотрения. | У оставшихся | |||||||
потребителей В 2 , В 3 выбираем клетку с минимальным тарифом. Это A 1 B 3 с тарифом 3. Запасы (оставшиеся) поставщика A 1 равны 60, а по-
| требности В 3 – 150, поэтому в клетку | A 1 B 3 | записываем максимально | |||||
| возможную перевозку 60 и исключаем поставщика A 1 из дальнейшего | |||||||
| рассмотрения. Далее, аналогично в клетку | A 2 B 2 записываем 30 и ис- | ||||||
| ключаем второго поставщика. | |||||||
| В оставшиеся две клетки A 3 B 2 | и A 3 B 3 | последовательно вписыва- | |||||
| ем перевозку 10 в A 3 B 2 | и 90 в A 3 B 3 . Получаем таблицу 2.4 с начальным | ||||||
| 80 | 0 | 60 | 0 | ||||
| опорным планом X = | 0 | 30 | 0 | 130 | |||
| . Суммарная стоимость пере- | |||||||
| 0 | 10 | 90 | 0 | ||||
возок равна z ( X ) = 1 80 + 3 60 + 4 30 + 2 130 + 5 10 + 14 90 = 1950 < 2280. Таким образом, опорный план, построенный методом минимального тарифа, лучше, чем план, полученный методом северо-западного угла. Применим, наконец, к исходной задаче метод аппроксимации Фогеля. Для этого найдем разность между двумя минимальными тарифами для каждой строки и столбца таблицы и запишем их в дополнительно образованные строки и столбцы (см. таблицу 2.5). В строке A 1 минимальный тариф равен 1, а следующий за ним 3, поэтому раз- ность между ними 4-2=2; в строке A 2 минимальный тариф равен 2, а следующий за ним 4, поэтому разность между равна 2; аналогично, для строки A 3 разность между минимальным тарифом 3 и следующим за ним 5 равна 2. Итак, три двойки записываем в первый дополнительный столбец. Аналогично для столбцов разности 3-1=2, 5-4=1, 8-3=5 и 6-2=4 записываем в первую дополнительную строку. Теперь из всех разностей выбираем максимальную , т.е. 5 в столбце B 3 , и в клетку A 1 B 3 с минимальным тарифом в этом столбце записываем максимально возможную перевозку 140. При этом поставщика A 1 исключаем из рас- смотрения. Теперь аналогично вычисляем разности между оставшимися минимальными тарифами и заполняем вторые дополнительные столбец и строку, не учитывая тарифы в строке A 1 . Видим, что теперь максимальная разность получается в столбце B 1 и перевозку 80 записываем в клетку A 3 B 1 с минимальным тарифом 3 в этом столбце (первую строку мы исключили из рассмотрения). Столбец B 1 аналогично исключаем из рассмотрения. Как видно из таблицы, на следующем
| B 1 | B 2 | B 3 | B 4 | a i | Разности по строкам | ||||||
| A 1 | 1 | 11 | 3 | 13 | 140 | 2 | – | – | – | – | – |
| 140 | |||||||||||
| A 2 | 12 | 4 | 8 | 2 | 160 | 2 | 2 | 2 | 2 | 0 | – |
| 20 | 10 | 130 | |||||||||
| A 3 | 3 | 5 | 14 | 6 | 100 | 2 | 2 | 1 | 1 | 0 | 0 |
| 80 | 20 | ||||||||||
| b j | 80 | 40 | 150 | 130 | 400 | ||||||
| 2 | 1 | 5 | 4 | ||||||||
| 9 | 1 | 6 | 4 | ||||||||
| Разности | |||||||||||
| – | 1 | 6 | 4 | ||||||||
| по | |||||||||||
| – | 1 | – | 4 | ||||||||
| столбцам | |||||||||||
| – | 1 | – | – | ||||||||
| – | 0 | – | – | ||||||||
Таблица 2.5 шаге вписываем перевозку 10 в клетку A 2 B 3 и исключаем столбец B 3 , затем – максимально возможную перевозку 40 в клетку A 2 B 4 и исключаем из рассмотрения столбец B 4 . Теперь для вычисления дальнейших разностей остается единственный столбец B 2 , поэтому в качестве разностей по строкам записываем нули. Далее, в клетку A 2 B 2 записываем 20, а на последнем шаге записываем перевозку 20 в клетку A 3 B 2 . По-