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.

Если оказалось, что все эти псевдостоимости не превосходят стоимостей

čij £ сij , £ ³

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

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

Таблица №6

Теперь будем перемещать по циклу число 14, так как оно является минимальным из чисел, стоящих в клетках, помеченных знаком - . При перемещении мы будем вычитать 14 из клеток со знаком - и прибавлять к клеткам со знаком + .

После этого необходимо подсчитать потенциалы ai и bj и цикл расчетов повторяется.

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

1. Взять любой опорный план перевозок, в котором отмечены m + n - 1 базисных клеток (остальные клетки свободные).

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

3. Подсчитать псевдостоимости či,j = ai + bj для всех свободных клеток. Если окажется, что все они не превышают стоимостей, то план оптимален.

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

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

Так в нашем примере после 2 циклов расчетов получим оптимальный план. При этом стоимость всей перевозки изменялась следующим образом: F0 = 723, F1 = 709, F2 = Fmin = 703.

Следует отметить так же, что оптимальный план может иметь и другой вид, но его стоимость останется такой же Fmin = 703.

Список использованной литературы

1. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования М.; Наука, 1976г.

2. Карманов В.Г. Математическое программирование. – М.; Наука, 1986г.

3. Моисеев Н.Н., Иванов Ю.П., Столярова Е.М. Методы оптимизации. – М.; Наука, 1978г.

4. Иванов Ю.П., Лотов А.В. Математические модели в экономике. – М.; Наука, 1979г.

5. Бронштейн И.Н., Семендяев К.А. Справочник