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

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

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

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

Будем называть «псевдостоимостью» перевозки единицы груза по некоторому маршруту величину, равную сумме внесенных платежей пунктом отправления и пунктом назначения:

.

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

Теорема о платежах транспортной задачи

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

.

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

Докажем это утверждение.

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

Теорема доказана.

Теорема об оптимальном плане транспортной задачи

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

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

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

Определим стоимость этого плана:

.

Теперь попробуем изменить оптимальный план перевозок , преобразовав его в план .

Стоимость нового плана будет равна следующей величине:

Очевидно, что ввиду условия , действующего в транспортной таблице относительно стоимостей и соответствующих их псевдостоимостей, имеем следующее неравенство:

Теорема доказана.

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

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

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

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

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

.

Таким образом, можно предположить следующий алгоритм решения классической транспортной задачи методом потенциалов:

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

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

.

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

3. Подсчитать псевдостоимости для всех свободных клеток. Если окажется, что выполняется условие (условие (а)), то рассматриваемый план перевозок является оптимальным.

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

5. Перейти к пункту 2.

 

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

Платежи пунктов отправления и пунктов назначения, а также псевдостоимости соответствующих маршрутов будем размещать в транспортной таблице, как показано ниже:

 

Сток Исток		…		Запасы:	Платежи:
			…	…
		…
…	…	…	…	…	…	…	…	…
…		…		…
			…	…
		…
Заявки:		…
Платежи:		…

 

Рассмотренным выше понятиям платежей за перевозку и псевдостоимостей можно дать следующую экономическую интерпретацию.

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

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

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

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

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

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

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

 

 

Сток Исток					Запасы:	Платежи:
Заявки:
Платежи:

 

Решение:

1. Методом «северо-западного» угла найдем опорный план перевозок (см. таблицу ниже).

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

r = n + m – 1 = 4 + 3 – 1 = 6

Посчитаем теперь стоимость найденного методом «северо-западного» угла опорного плана:

L = 22× 10 + 9× 7 + … = 796

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

 

Сток Исток					Запасы:	Платежи:
Заявки:
Платежи:

 

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

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

 

Сток Исток					Запасы:	Платежи:
										-1
Заявки:
Платежи:

 

3. Подсчитаем псевдостоимости для всех свободных клеток:

 

Сток Исток					Запасы:	Платежи:
										-1
Заявки:
Платежи:

 

Так как для некоторых свободных клеток – (2, 1), (2, 4), (3, 1), (3, 2) – не выполняется условие , то рассматриваемый план перевозок не является оптимальным.

4. В соответствии с алгоритмом улучшим найденный план путем переноски груза циклу любой свободной клетки транспортной таблицы, в которой не выполняется условие . В качестве такой клетки возьмем, например, свободную клетку (2, 1), так как именно в ней имеет место максимальная разница между стоимостью и пседостоимостью:

 

Сток Исток					Запасы:	Платежи:
										-1
Заявки:
Платежи:

 

В результате циклического переноса получим новый план перевозок (см. таблицу ниже).

 

Сток Исток					Запасы:	Платежи:
Заявки:
Платежи:

 

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

 

Сток Исток					Запасы:	Платежи:
										-1
Заявки:
Платежи:

 

Сток Исток					Запасы:	Платежи:
Заявки:
Платежи:

 

Сток Исток					Запасы:	Платежи:
										-1
Заявки:
Платежи:

 

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

L = 31× 7 + 22× 5 + 3× 6 + 3× 5 + × 20× 4 + 38× 6 = 668

Как и следовало ожидать, мы получили тот же самый ответ, что и при решении этой задачи распределительным методом.

Пример 4. Решение транспортной задачи с вырожденным планом перевозок методом потенциалов.

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

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

 

 

Сток Исток				Запасы:	Платежи:
Заявки:
Платежи:

 

Решение:

 

Сток Исток				Запасы:	Платежи:
Заявки:
Платежи:

 

Сток Исток				Запасы:	Платежи:
							40-e
				e
							20+e
				20-e
Заявки:
Платежи:

 

 

Сток Исток				Запасы:	Платежи:
							40-e
				e
							20+e
				20-e
Заявки:
Платежи:

 

Сток Исток				Запасы:	Платежи:
							40-e
				20+e
							20+e
				20-e
Заявки:
Платежи:

 

Сток Исток				Запасы:	Платежи:
							40-e
				20+e
							20+e
				20-e
Заявки:
Платежи:

 

 

Сток Исток				Запасы:	Платежи:
							40-e
		e
							20+e
		20-e
Заявки:
Платежи:

 

 

Сток Исток				Запасы:	Платежи:
							40-e
		e
							20+e	-2
		20-e
Заявки:
Платежи:

 

Сток Исток				Запасы:	Платежи:
							40-e
				40+e
		e		3-e
							20+e
		20-e
Заявки:
Платежи:

 

 

Сток Исток				Запасы:	Платежи:
							40-e
				40+e
		e		3-e
							20+e
		20-e
Заявки:
Платежи:

 

Полагая бесконечно малую величину e равной нулю, имеем:

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: