Тема 2.9. Метод потенциалов

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

Л.В. Канторовичем. Рассмотрим применение этого метода при следующих данных:

а ₁=250, а ₂ = 200, а ₃ = 50, b ₁ = 50, b ₂ = 100, b ₃ = 150, b ₄=120, b ₅ = 80,

С =

где С – матрица тарифов.

Данные задачи группируем в таблицу 2.6:

Таблица 2.6

b j ai

Находим первое базисное решение (первый план перевозок) методом северо-западного угла. Для этого максимально «загружаем» клетку (1,1), помещая туда 50 т. При этом спрос первого потребителя полностью удовлетворяется, первый столбец «закрываем». Заметим, что если бы на первом складе было бы меньше груза, чем требуется первому потребителю, то освободился бы полностью первый склад и мы бы «закрыли» первую строку, а недостающий груз первому потребителю был бы поставлен со второго склада, а при необходимости последовательно еще и с других складов. Теперь максимально «загружаем» клетку (1,2), помещая туда 100 т. Так как при этом спрос второго потребителя удовлетворяется полностью, то второй столбец «закрываем». Максимально загружаем клетку (1,3), помещая туда оставшиеся на первом складе 100 т. После этого первая строка «закрыта». Теперь распределяем груз из второго склада. Максимально загружаем клетку (2,3), помещая туда 50 тонн. Так как после этого спрос третьего потребителя полностью удовлетворяется, то «закрываем» третий столбец.

Максимально загружаем клетку (2, 4), помещая туда 120 тонн. Тогда четвертый столбец будет «закрыт». Максимально загружаем клетку (2, 5), помещая туда оставшиеся на втором складе 30 тонн. Теперь остается весь груз из третьего склада отдать пятому потребителю и его спрос будет удовлетворен, т.е. в клетку (3,5) помещаем 50 тонн. В результате получаем первый план перевозок, содержащийся в таблице 2.7.

Таблица 2.7

bi ai
			100-l		l
			50+l		30 -l

Количество базисных переменных равно: m + n -1=3+5-1=7.

В данном случае базисными переменными являются величины х ₁₁, х ₁₂, х ₁₃, х ₂₃, х ₂₄,_, х _25, х ₃₅, соответствующие «загруженным» клеткам.

Транспортные расходы выражаются формулой:

f =

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

f = f ₀ + ,

где х_pq – свободные переменные, f ₀ – транспортные расходы по начальному плану перевозок.

Если хотя бы один из коэффициентов g_pq <0, то транспортные расходы можно уменьшить, в противном случае - план перевозок будет оптимальным.

Каждой загруженной клетке(i, j) поставим в соответствие величины U_i, V_j, которые вычисляются из уравнений:

U_i + V_j = с_ij.

В рассматриваемом случае число уравнений равно

m + n–1= 7, а число неизвестных U_i, V_j равно m + n = 8. Так как число неизвестных больше числа уравнений на единицу, то одной из неизвестных можно дать произвольное значение, например, 0.

Обозначим через с¢_pq (косвенный тариф) сумму U_P+ V где (p, q) – пустая клетка. Можно доказать, что знак g_pq = с_pq – с¢_pq.

Величины U_i, V_j называют потенциалами и в силу этого метод решения транспортной задачи носит название метода потенциалов.

Составляем систему уравнений и находим потенциалы.

U ₁ + V ₁ = 10, U ₁ = 0, V ₁=10,

U ₁ + V ₂ = 12, U ₂ = -11, V ₂ = 12,

U ₁ + V ₃ = 15, U ₃ = -17. V ₃ = 15,

U ₂ + V ₃ = 4, V ₄ = 25,

U ₂ + V ₄ = 14, V ₅ = 41.

U ₂ + V ₅ = 30,

U ₃ + V ₅ =24.

Находим величины с¢_pq,

Так как некоторые из величин g_pq отрицательные, то план можно улучшить. «Загружаем» клетку (1;5), ибо g ₁₅ – наибольший по модулю отрицательный коэффициент, помещая туда l тонн, и перераспределяем поставки груза. Перераспределение груза осуществляется по выбранному контуру с таким расчетом, чтобы транспортные затраты уменьшились.

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

5 l - 15 l +4 l- 30 l /= /-36l/ =36l =36× 30 =1080.

Таким образом, такое перераспределение поставок груза целесообразно и мы получаем второй, более лучший план поставок (таблица 2.8).

Таблица 2.8

bi ai

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

Теперь мы не будем так подробно составлять и решать очередную систему уравнений. Для этого добавим к предыдущей таблице стоку и столбец потенциалов. Получим таблицу 2.9.

Таблица 2.9

bi ai
			70 -		5 30+	= 0
	-1		80 +	120-	-6
					24 50-	= 19
				= 25

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

24 - 5 = 19, = 4 - 15 = - 11, =14 – (-11) = 25.

Находим косвенные тарифы с¢_pq.

Найденные косвенные тарифы размещаем в не загруженных клетках соответствующей таблицы напротив фактических тарифов.

Находим величины g_pq.

Так как g₃₄ – наибольший по модулю отрицательный коэффициент, то «загружаем» клетку (3;4), помещая туда l тонн, и перераспределяем поставки груза. Выбираем контур, соединяющий клетки (3;4), (3;5),(1;5), (1;3), (2;3),(2;4) в таблице 9.

Перераспределение поставок по этому контуру дает уменьшение транспортных расходов на 26 l, где l = 50. В результате получаем третий план перевозок (таблица 2.10).

Таблица 2.10

bj ai
			20- l	l
	-1	-1	130 + l	70 - l	-6×	-11
					-2	-7

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

Загружаем клетку (1;4) так как только g ₁₄< 0.

Выбираем контур и осуществляем перераспределение поставок груза (таблица 2.10). Транспортные расходы при этом уменьшаются на величину 5 l, где l = 20. Получаем четвертый план перевозок груза.

Таблица 2.11

bj ai
					-1	--6
						--2

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

Так как g_pq > 0, т.е. косвенные тарифы для каждой пустой клетки не превышают соответствующих фактических тарифов, то четвертый план является оптимальным. Наименьшие транспортные расходы составляют:

50×10 + 100×12 + 20×20 + 80×5 + 150×4 + 50×14 + 50×18 = 4700.

Часто оптимальный план достигается быстрее, если первоначальный план перевозок находят не методом северо-западного угла, а методом наименьшего расстояния (методом наименьшего тарифа). Суть его состоит в том, что максимально «загружают» клетку, соответствующую наименьшему расстоянию, в результате «закрывается» либо строка, либо столбец, на пересечении которых она находится. Из оставшихся клеток заполняют ту, которая соответствует наименьшему расстоянию и т.д. Для подтверждения сказанного решим рассмотренную нами задачу снова.

Составляем первый план перевозок по методу наименьшего тарифа. Первой «загружается» клетка (2;3) и третий столбец закрывается. Затем «загружается» клетка (1;5)) и пятый столбец закрывается. Далее «загружается» клетка (2;1) и закрывается первый столбец и вторая строка. Потом «загружается» клетка (1;2) и закрывается второй столбец. Затем «загружаются» клетки (3;4) и (1;4). В результате получаем первый план перевозок груза, которому соответствуют транспортные расходы 4800.

Таблица 2.12

bj ai
	l			70- l
	50- l			l
						-2

Находим потенциалы U_i, V_j и косвенные тарифы.

«Загружаем» клетку (2;4), ибо g ₂₄ – наибольший по модулю отрицательный коэффициент.

Выбираем контур перераспределения груза и при l = 50 приходим к полученному нами ранее оптимальному плану перевозок

Дата добавления: 2014-10-31