Транспортная задача (задача Монжа — Канторовича)

Транспортная  задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной и входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).

Транспортная  задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум  времени на перевозку). Под названием  транспортная задача, определяется широкий  круг задач с единой математической моделью, эти задачи относятся к  задачам линейного программирования и могут быть решены оптимальным  методом. Однако, спец.метод решения транспортной задачи позволяет существенно упростить её решение, поскольку транспортная задача разрабатывалась для минимизации стоимости перевозок.

История поиска методов решения

Проблема была впервые  формализована французским математиком Гаспаром Монжем в 1781 году. Основное продвижение было сделано на полях во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем. Поэтому иногда эта проблема называется транспортной задачей Монжа — Канторовича.

 

 

 

Методы решения

Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей её можно решить проще (для задач малой размерности).

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

Итерационное  улучшение плана перевозок

Нахождение опорного плана

Требуется определить опорный план и путём последовательных операций найти оптимальное решение. Опорный план можно найти следующими методами: «северо-западного угла», «наименьшего элемента», двойного предпочтения и аппроксимации Фогеля.

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

Метод северо-западного  угла (диагональный)

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

 

 

 

Метод наименьшего  элемента

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

Алгоритм:

1. Из таблицы стоимостей выбирают наименьшую стоимость и в клетку, которая ей соответствует, вписывают большее из чисел.
2. Проверяются строки поставщиков на наличии строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются.
3. Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.

Итерации

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

• Метод падающего камня (нем.)
• Метод потенциалов.

Решение с помощью теории графов

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

К верхней доле искусственно присоединяется исток. Пропускная способность рёбер из истока в каждый пункт производства равна запасу продукта в этом пункте. Цена за единицу потока у этих рёбер равна 0.

Аналогично к нижней доле присоединяется сток. Пропускная способность рёбер из каждого пункта потребления в сток равна потребности в продукте в этом пункте. Цена за единицу потока у этих рёбер тоже равна 0.

Дальше решается задача нахождения максимального потока минимальной стоимости (mincost maxflow). Её решение аналогично нахождению максимального потока в алгоритме Форда — Фалкерсона. Только вместо кратчайшего дополняющего потока ищется самый дешёвый. Соответственно, в этой подзадаче используется не поиск в ширину, а алгоритм Беллмана — Форда. При возврате потока стоимость считается отрицательной.

Алгоритм «mincost maxflow» можно запускать и сразу — без нахождения опорного плана. Но в этом случае процесс решения будет несколько более долгим. Выполнение алгоритма «mincost maxflow» происходит не более чем за   операций. (  — количество рёбер,   — количество вершин.) При случайно подобраных данных обычно требуется гораздо меньше — порядка   операций.

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

 

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

В этом варианте пункты не делятся на пункты отправления и пункты потребления, все пункты равноправны, но производство задается положительным числом, а потребление - отрицательным. Перевозки осуществляются по заданной сети, в которой дуги могут соединять любые пункты (включая производитель -> производитель, потребитель -> потребитель). Задача решается слегка измененным методом потенциалов, практически тем же, что и классическая постановка.

Транспортная  задача с ограничениями пропускной способности

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

Многопродуктовая Транспортная задача

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Пример

Используя метод аппроксимации  Фогеля, найти опорный план транспортной задачи, исходные данные которой приведены  в таблице (опорный план этой задачи ранее был найден методом минимального элемента).

Пункты отправления	Пункты назначения				Запасы
	B1	B2	B3	B4
A1	7	8	1	2	160
A2	4	5	9	8	140
A3	9	2	3	6	170
Потребности	120	50	190	110	470

Решение

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

Пункты отправления	Пункты назначения				Запасы	Разности по строкам
	B1	B2	B3	B4
A1	7	8	1	2	160	1	6	-	-	-	-
A2	4	5	9	8	140	1	1	1	1	1	0
A3	9	2	3	6	170	1	1	1	7	-	-
Потребности	120	50	190	110	470
Разности по столбцам	3	3	2	4
	3	3	2	-
	5	3	6	-
	5	3	-	-
	0	0	-	-
	-	0	-	-

Так, в строке А2 минимальный тариф равен 4, а следующий за ним равен 5, разность между ними 5-4=1. Точно так же разность между минимальными элементами в столбце В4 равна 6-2=4. Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу В4. В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки А1 и столбца В4. Таким образом, эту клетку следует заполнить. Заполнив ее, тем самым мы удовлетворим потребности пункта В4. Поэтому исключим из рассмотрения столбец В4 и будем считать запасы пункта А1 равными 160—110=50 ед. После этого определим следующую клетку для заполнения. Снова найдем разности между оставшимися двумя минимальными тарифами в каждой из строк и столбцов и запишем их во втором дополнительном столбце и во второй дополнительной строке таблицы. Как видно из этой таблицы, наибольшая указанная разность соответствует строке А1. Минимальный тариф в этой строке записан в клетке, которая находится на пересечении ее с столбцом В3. Следовательно, заполняем эту клетку. Поместив в нее число 50, тем самым предполагаем, что запасы в пункте А1 полностью исчерпаны, а потребности в пункте В3 стали равными 190-50=140 ед. Исключим из рассмотрения строку А1 и определим новую клетку для заполнения. Продолжая итерационный процесс, последовательно заполняем клетки, находящиеся на пересечении строки A3 и столбца B3, строки A3 и столбца B2, строки A2 и столбца B1, строки А2 и столбца B2. В результате получим опорный план:

При этом плане общая стоимость  перевозок такова:

S = 1*50 + 2*110 + 4*120 + 5*20 + 2*30 + 3*140 = 1330.

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