r = 5

Стоимость найденного плана перевозок равна:

L = 20×5 + 20×4 + 20×6 + 3×5 + 20×6 = 435

Попытаемся еще улучшить найденный опорный план перевозок. Для этого перейдем к пункту 2 алгоритма:

1. Вычислим цену цикла для каждой свободной переменной.

1. Максимальное количество груза, которое можно перенести по циклу свободной переменной х₃₂ = 20.

2. g₃₂×max x₃₂ = - 80.

Сток Исток							Запасы:
		10		5		4	40-e
			20		20+e
		6		4		5	23
	20				3
		7		3		6	20+e
					20-e
Заявки:	20		20		43		83

1. Перенесем 20 единиц груза по циклу переменной x₃₂, , уменьшив значение целевой функции на 80 единиц.

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

Сток Исток							Запасы:
		10		5		4	40-e
					40+e
		6		4		5	23
	20				3
		7		3		6	20+e
			20		e
Заявки:	20		20		43		83

Полученный на этом этапе новый план перевозок имеет пять базисных клеток в соответствующей ему транспортной таблице (см. таблицу выше).

r = 5

Стоимость найденного плана перевозок равна:

L = 40×4 + 20×6 + 3×5 + 20×3 = 355

Еще раз попытаемся улучшить найденный опорный план перевозок. Для этого перейдем к пункту 2 алгоритма:

1. Вычислим цену цикла для каждой свободной переменной.

1. Максимальное количество груза, которое можно перенести по циклу единственной свободной переменной х₂₂, имеющей отрицательную цену цикла, равно бесконечно малой величине e. Полагая e = 0, получим окончательный оптимальный план перевозок:

Сток Исток							Запасы:
		10		5		4	40
					40
		6		4		5	23
	20				3
		7		3		6	20
			20
Заявки:	20		20		43		83

стоимость которого равна:

L = 40×4 + 20×6+ 3×5 +20×3 =355

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

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

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

Лабораторная работа № 4 (4 часа)

Решение транспортной задачи методом потенциалов

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

Пусть имеется транспортная задача:

Будем условно считать, что каждый из пунктов отправления вносит за перевозку единицы груза платеж ; в свою очередь каждый пункт назначения также вносит за перевозку единицы груза сумму .

Будем называть «псевдостоимостью» перевозки единицы груза .

Обозначим всю совокупность платежей через . Докажем общее положение о платежах.

Теорема о платежах ТЗ

Для заданной совокупности платежей суммарная псевдостоимость перевозок:

.

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

Докажем это предложение.

Теорема об оптимальном плане ТЗ.

Если для всех базисных клеток плана , а для всех свободных клеток , то план является оптимальным.

Доказательство.

Обозначим - план с соответствующей ему системой платежей , обладающий свойством оптимальности. Определим стоимость этого плана:

.

Теперь попробуем изменить план .

Стоимость нового плана:

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

Таким образом доказано, что признаком оптимальности плана является выполнение двух условий:

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

Для любой системы платежей , удовлетворяющей условию (а), каждая свободная клетка имеет цену цикла, равную разности стоимости и псевдостоимости в этой клетке:

.

Итак, можно предположить следующий алгоритм решения ТЗ методом потенциалов.

1. Взять любой опорный план перевозок, в котором отмечены базисных клеток.

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

.

Один из платежей можно назначить произвольно, например, положить равным 0, т.к. уравнений всего , а число неизвестных .

1. Подсчитать псевдостоимости для всех свободных клеток. Если окажется, что , то план оптимален.

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

3. Перейдем к пункту 2.

Понятиям платежей и псевдостоимостей можно дать следующую интерпретацию: пусть поставщики и потребители действуют как единая экономическая система, а платежи - реальные платежи, которые пункты и платят за перевозку единицы груза «перевозчику». Перевозки единицы груза из пункт в пункт объективно стоит , а стороны А и В вместе платят за эту перевозку .

Оптимальным будет такой план перевозок, при котором пункты и не переплачивают «перевозчику» ничего сверху объективной стоимости перевозок, т.е. .

Пример 5. Решить методом потенциалов ТЗ.

C

И
					31	0
					48	-1
					38	0
	22	34	41	20	117
	10	7	6	7

Псевдостоимости будем записывать в левом верхнем углу. Один из платежей, например , выбираем произвольно .