Реферат: Решение задач транспортного типа методом потенциалов
b 5 = 6, так как a 2 + b 5 = С25 = 5, ®
a 3 = 1, так как a 3 + b 5 = С35 = 7, ®
b 2 = 6, так как a 3 + b 2 = С25 = 7.
Если оказалось, что все эти псевдостоимости не превосходят стоимостей
č ij £ с ij , £ ³
то план потенциален и, значит, оптимален. Если же хотя бы в одной свободной клетке псевдостоимость больше стоимости (как в нашем примере), то план не является оптимальным и может быть улучшен переносом перевозок по циклу, соответствующему данной свободной клетке. Цена этого цикла ровна разности между стоимостью и псевдостоимостью в этой свободной клетке.
В таблице № 5 мы получили в двух клетках č ij ³ с ij , теперь можно построить цикл в любой из этих двух клеток. Выгоднее всего строить цикл в той клетке, в которой разность č ij - с ij максимальна. В нашем случае в обоих клетках разность одинакова (равна 1), поэтому, для построения цикла выберем, например, клетку (4,2):
Таблица №6
| ПН ПО |
В1 |
В2 |
В3 |
В4 |
В5 |
a i |
| А1
| 10 | 8 | 5 42 | 6 6 | 9 | 0 |
| А2
| 6 + 4 | 7 | 8 | 6 | 5 - 26 | -1 |
| А3
| 8 | 7 - 27 | 10 | 8 | 7 + 0 | 1 |
| А4
| 7 - 14 | 5 + - | 4 | 6 6 | 8 | 0 |
| b j
| 7 | 6 | 5 | 6 | 6 |
Теперь будем перемещать по циклу число 14, так как оно является минимальным из чисел, стоящих в клетках, помеченных знаком - . При перемещении мы будем вычитать 14 из клеток со знаком - и прибавлять к клеткам со знаком + .
После этого необходимо подсчитать потенциалы a i и b j и цикл расчетов повторяется.
Итак, мы приходим к следующему алгоритму решения транспортной задачи методом потенциалов.
1. Взять любой опорный план перевозок, в котором отмечены m + n - 1 базисных клеток (остальные клетки свободные).
2. Определить для этого плана платежи (a i и b j ) исходя из условия, чтобы в любой базисной клетке псевдостоимости были равны стоимостям. Один из платежей можно назначить произвольно, например, положить равным нулю.
3. Подсчитать псевдостоимости č i , j = a i + b j для всех свободных клеток. Если окажется, что все они не превышают стоимостей, то план оптимален.
4. Если хотя бы в одной свободной клетке псевдостоимость превышает стоимость, следует приступить к улучшению плана путём переброски перевозок по циклу, соответствующему любой свободной клетке с отрицательной ценой (для которой псевдостоимость больше стоимости).
5. После этого заново подсчитываются платежи и псевдостоимости, и, если план ещё не оптимален, процедура улучшения продолжается до тех пор, пока не будет найден оптимальный план.
Так в нашем примере после 2 циклов расчетов получим оптимальный план. При этом стоимость всей перевозки изменялась следующим образом: F0 = 723, F1 = 709, F2 = Fmin = 703.
Следует отметить так же, что оптимальный план может иметь и другой вид, но его стоимость останется такой же Fmin = 703.