Транспортная задача

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

 

Таблица 7.

 

Заказы   Запасы
						60
				30
			40	50

 

Найдем суммарную стоимость перевозок по этому плану:

 

Сравнивая это значение со стоимостью плана, полученного по методу северо-западного угла, видим, что 1, то есть мы получили более выгодный план перевозок.

7. Метод  потенциалов как метод определения оптимального плана

 

Этот первый точный метод решения транспортной задачи предложен в 1949 году Кантаровичем А. В. И Гавуриным М. К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Однако в начале он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данциом, который исходил из общей идеи линейного программирования. В американской литературе принято называть модифицированным распределительным методом. Метод потенциалов позволяет определить отправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций) 8.

Определение 11.

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

a) Вычисление потенциалов

Сопоставим каждому поставщику и каждому потребителю величины соответственно так, чтобы для всех базисных клеток плана были выполнены соотношения

 

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

b) Проверка оптимальности плана

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

План является оптимальным, если все разности 0. В противном случае план можно улучшить следующим способом.

c) Перераспределение поставок

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

Груз будет перераспределен по клеткам цикла на величину следующим образом. В клетках со знаком «плюс» значение перевозки нужно увеличить на величину , а в клетках со знаком «минус» – уменьшить на величину . Так как после пересчета у нас добавилась лишняя базисная клетка, то их количество необходимо сократить, убрав нуль в одной из клеток цикла. Если таких клеток получилось несколько, то свободной делаем ту из них, в которой тариф перевозок максимален.

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

Пример 4.

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

 

 

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

 

 

при ограничениях

 

 

Задача имеет закрытый тип, т.к. запасы груза т равны суммарным потребностям магазинов т.

 Составим опорный план по правилу минимального элемента.

 

Склад	Магазин										Запасы
		20		23		20		15		24	320
	0		0		0		0		0
		29		15		16		19		29	280
	0		0		0		0		0
		6		11		10		9		8	250
	0		0		0		0		0
Потребности	150		140		110		230		220

 

Введем некоторые обозначения: - излишек нераспределенного груза от поставщика - недостача в поставке груза потребителю

которые вычисляются по формулам ,  .

Находим незанятую клетку с минимальным тарифом: . Помещаем туда меньшее из чисел .  Исключаем из рассмотрения столбец .

Находим незанятую клетку с минимальным тарифом: . Помещаем туда меньшее из чисел . Исключаем из рассмотрения строку

Находим незанятую клетку с минимальным тарифом: . Помещаем туда меньшее из чисел . Исключаем из рассмотрения столбец

Находим незанятую клетку с минимальным тарифом: . Помещаем туда меньшее из чисел . Исключаем из рассмотрения столбец .

Находим незанятую клетку с минимальным тарифом: . Помещаем туда меньшее из чисел . Исключаем из рассмотрения столбец .

Находим незанятую клетку с минимальным тарифом: Помещаем туда меньшее из чисел . Исключаем из рассмотрения строку .

Находим незанятую клетку с минимальным тарифом: Помещаем туда меньшее из чисел

Пришли к таблице:

 

Склад	Магазин										Запасы
		20		23		20		15		24	320
							230		90
		29		15		16		19		29	280
			140		110				30
		6		11		10		9		8	250
	150								100
Потребности	150		140		110		230		220

 

Транспортные расходы составят:

 

Решим задачу методом потенциалов. Т.к. и имеем 7 загруженных клеток, план ацикличный. Пусть - потенциалы -го склада и-го магазина соответственно.

 

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

 

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

 

 

 

 

 

 

 

 

 

Имеем две клетки с отрицательными оценками – и ). Выбираем клетку с наименьшей оценкой и строим для нее цикл.

 

Склад	Магазин										Запасы
	⊕	20		23		20		15		24	320
							230		90
		29		15		16		19		29	280
			140		110				30
		6		11		10		9	⊕	8	250
	150								100
Потребности	150		140		110		230		220

 

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