Решение задач транспортного типа методом потенциалов

| Категория реферата: Рефераты по статистике
| Теги реферата: реферат мировой, оформление титульный реферата
| Добавил(а) на сайт: Kojtasbaev.

Процедура построения потенциального (оптимального) плана состоит в следующем.

В качестве первого приближения к оптимальному плану берётся любой допустимый план (например, построенный способом минимальной стоимости по строке). В этом плане 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 ) исходя из условия, чтобы в любой базисной клетке псевдостоимости были равны стоимостям. Один из платежей можно назначить произвольно, например, положить равным нулю.