Курсовая работа: Транспортная задача

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 базисных клеток (остальные клетки свободные).

Страницы: 1, 2, 3, 4, 5, 6, 7, 8