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