Метод последовательного улучшения плана перевозок и состоит в том, что в таблице отыскиваются циклы с отрицательной ценой, по ним перемещаются перевозки, и план улучшается до тех пор, пока циклов с отрицательной ценой уже не останется. При улучшении плана циклическими переносами, как правило, пользуются приёмом, заимствованным из симплекс-метода: при каждом шаге (цикле) заменяют одну свободную переменную на базисную, то есть заполняют одну свободную клетку и взамен того освобождают одну из базисных клеток. При этом общее число базисных клеток остаётся неизменным и равнымm + n - 1. Этот метод удобен тем, что для него легче находить подходящие циклы.
Можно доказать, что для любой свободной клетке транспортной таблице всегда существует цикл и притом единственный, одна из вершин которого лежит в этой свободной клетке, а все остальные в базисных клетках. Если цена такого цикла, с плюсом в свободной клетке, отрицательна, то план можно улучшить перемещением перевозок по данному циклу. Количество единиц грузаk, которое можно переместить, определяется минимальным значением перевозок, стоящих в отрицательных вершинах цикла (если переместить большее число единиц груза, возникнут отрицательные перевозки).
Применённый выше метод отыскания оптимального решения транспортной задачи называется распределённым; он состоит в непосредственном отыскании свободных клеток с отрицательной ценой цикла и в перемещении перевозок по этому циклу.
Распределительный метод решения транспортной задачи, с которым мы познакомились, обладает одним недостатком: нужно отыскивать циклы для всех свободных клеток и находить их цены. От этой трудоёмкой работы нас избавляет специальный метод решения транспортной задачи, который называется методом потенциалов.
5. Решение транспортной задачи методом потенциалов.
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены.
Пусть имеется транспортная задача с балансовыми условиями
Стоимость перевозки единицы груза изAiвBjравнаCij; таблица стоимостей задана. Требуется найти план перевозокxij, который удовлетворял бы балансовым условиям и при этом стоимость всех перевозок бала минимальна.
Идея метода потенциалов для решения транспортной задачи сводиться к следующему. Представим себе что каждый из пунктов отправленияAiвносит за перевозку единицы груза (всё равно куда) какую-то суммуai; в свою очередь каждый из пунктов назначенияBjтакже вносит за перевозку груза (куда угодно) суммуbj. Эти платежи передаются некоторому третьему лицу (“перевозчику“). Обозначимai+bj=cij( i=1..m ;j=1..n)и будем называть величинуcij“псевдостоимостью” перевозки единицы груза изAiвBj. Заметим, что платежиaiиbjне обязательно должны быть положительными; не исключено, что “перевозчик” сам платит тому или другому пункту какую-то премию за перевозку. Также надо отметить, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах (aiиbj) одна и та же и от плана к плану не меняется.
До сих пор мы никак не связывали платежи (aiиbj) и псевдостоимостиcijс истинными стоимостями перевозокCij. Теперь мы установим между ними связь. Предположим, что планxijневырожденный (число базисных клеток в таблице перевозок ровно m + n -1). Для всех этих клетокxij>0. Определим платежи (aiиbj) так, чтобы во всех базисных клетках псевдостоимости были ровны стоимостям:
cij=ai+bj=сij,приxij>0.
Что касается свободных клеток (гдеxij= 0), то в них соотношение между псевдостоимостями и стоимостями может быть, какое угодно.
Оказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является ли план оптимальным или же он может быть улучшен. Существует специальная теорема: Если для всех базисных клеток планаxij> 0,
ai+bj=cij=сij,
а для всех свободных клетокxij=0,
ai+bj=cijсij,
то план являетсяоптимальными никакими способами улучшен быть не может. Нетрудно показать, что это теорема справедлива также для вырожденного плана, и некоторые из базисных переменных равны нулю. План обладающий свойством :
cij=сij(для всех базисных клеток ) (1)
cijсij( для всех свободных клеток ) (2)
называетсяпотенциальнымпланом, а соответствующие ему платежи (aiиbj) — потенциалами пунктовAiиBj(i=1,...,m ; j=1,...,n). Пользуясь этой терминологией вышеупомянутую теорему можно сформулировать так:
Всякий потенциальный план является оптимальным.
Итак, для решения транспортной задачи нам нужно одно - построить потенциальный план. Оказывается его можно построить методом последовательных приближений, задаваясь сначала какой-то произвольной системой платежей, удовлетворяющей условию (1). При этом в каждой базисной клетке получиться сумма платежей, равная стоимости перевозок в данной клетке; затем, улучшая план следует одновременно менять систему платежей. Так, что они приближаются к потенциалам. При улучшении плана нам помогает следующее свойство платежей и псевдостоимостей: какова бы ни была система платежей (aiиbj) удовлетворяющая условию (1), для каждой свободной клетки цена цикла пересчёта равна разности между стоимостью и псевдостоимостью в данной клетке :gi,j=сi,j-ci,j.
Таким образом, при пользовании методом потенциалов для решения транспортной задачи отпадает наиболее трудоёмкий элемент распределительного метода: поиски циклов с отрицательной ценой.
Процедура построения потенциального (оптимального) плана состоит в следующем.
В качестве первого приближения к оптимальному плану берётся любой допустимый план (например, построенный способом минимальной стоимости по строке). В этом плане m + n - 1 базисных клеток, где m - число строк, n - число столбцов транспортной таблицы. Для этого плана можно определить платежи (aiиbj), так, чтобы в каждой базисной клетке выполнялось условие :
ai+bj=сij(3)
Уравнений (3) всегоm + n - 1, а число неизвестных равноm + n.Следовательно, одну из этих неизвестных можно задать произвольно (например, равной нулю). После этого изm + n - 1уравнений (3) можно найти остальные платежиai,bj, а по ним вычислить псевдостоимости,ci,j=ai+bjдля каждой свободной клетки.
Таблица №5
 | | | | | | |
|
ПН
ПО
|
В1 |
В2 |
В3 |
В4 |
В5 |
ai |
А1
|
10
c= 7
|
8
c= 6
|
5
42
|
6
6 |
9
c= 6
|
a1 = 0
|
А2
|
6
4 |
7
c= 5
|
8
c= 4
|
6
c= 5
|
5
26
|
a2= -1 |
А3
|
8
c= 8
|
7
27
|
10
c= 6
|
8
c= 7
|
7
0
|
a3= 1 |
А4
|
7
14 |
5
c= 6
|
4
c= 5
|
6
6
|
8
c= 6
|
a4= 0
|
bj
|
b1= 7 |
b2= 6 |
b3= 5 |
b4= 6 |
b5= 6 |
|
a4 = 0, ®
b4 = 6, так как a4 + b4 = С44 = 6, ®
a1 = 0, так как a1 + b4 = С14 = 6, ®
b3 = 5, так как a1 + b3 = С13 = 5, ®
b1 = 7, так как a4 + b1 = С41 = 7, ®
a2 = -1, так как a2 + b1 = С21 = 6, ®
b5 = 6, так как a2 + b5 = С25 = 5, ®
a3 = 1, так как a3 + b5 = С35 = 7, ®
b2 = 6, так как a3 + b2 = С25 = 7.
Если оказалось, что все эти псевдостоимости не превосходят стоимостей
cijЈсij,Ј і
то план потенциален и, значит, оптимален. Если же хотя бы в одной свободной клетке псевдостоимость больше стоимости (как в нашем примере), то план не является оптимальным и может быть улучшен переносом перевозок по циклу, соответствующему данной свободной клетке. Цена этого цикла ровна разности между стоимостью и псевдостоимостью в этой свободной клетке.
В таблице № 5 мы получили в двух клеткахcijісij, теперь можно построить цикл в любой из этих двух клеток. Выгоднее всего строить цикл в той клетке, в которой разностьcij-сijмаксимальна. В нашем случае в обоих клетках разность одинакова (равна 1), поэтому, для построения цикла выберем, например, клетку (4,2):
Таблица №6
Теперь будем перемещать по циклу число 14, так как оно является минимальным из чисел, стоящих в клетках, помеченных знаком - . При перемещении мы будем вычитать 14 из клеток со знаком - и прибавлять к клеткам со знаком + .
После этого необходимо подсчитать потенциалыaiиbjи цикл расчетов повторяется.
Итак, мы приходим к следующему алгоритму решения транспортной задачи методом потенциалов.
1. Взять любой опорный план перевозок, в котором отмечены m + n - 1базисных клеток (остальные клетки свободные).
2. Определить для этого плана платежи (aiиbj) исходя из условия, чтобы в любой базисной клетке псевдостоимости были равны стоимостям. Один из платежей можно назначить произвольно, например, положить равным нулю.
3. Подсчитать псевдостоимостиci,j=ai+bjдля всех свободных клеток. Если окажется, что все они не превышают стоимостей, то план оптимален.
4. Если хотя бы в одной свободной клетке псевдостоимость превышает стоимость, следует приступить к улучшению плана путём переброски перевозок по циклу, соответствующему любой свободной клетке с отрицательной ценой (для которой псевдостоимость больше стоимости).
5. После этого заново подсчитываются платежи и псевдостоимости, и, если план ещё не оптимален, процедура улучшения продолжается до тех пор, пока не будет найден оптимальный план.
Так в нашем примере после 2 циклов расчетов получим оптимальный план. При этом стоимость всей перевозки изменялась следующим образом: F0= 723, F1= 709, F2= Fmin= 703.
Следует отметить так же, что оптимальный план может иметь и другой вид, но его стоимость останется такой же Fmin= 703.
Сп исок использованной литературы
1. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования М.; Наука, 1976г.
2. Карманов В.Г. Математическое программирование. – М.; Наука, 1986г.
3. Моисеев Н.Н., Иванов Ю.П., Столярова Е.М. Методы оптимизации. – М.; Наука, 1978г.
4. Иванов Ю.П., Лотов А.В. Математические модели в экономике. – М.; Наука, 1979г.
5. Бронштейн И.Н., Семендяев К.А. Справочник по математике. – М.; Наука, 1986г
1
2
