Математические методы в коммерческой деятельности. Буравлева О.Ю. - 27 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

В качестве первого приближения к оптимальному плану берется любой допустимый план (напри-
мер, построенный способом минимальной стоимости по строке). В этом плане m + n – 1 базисных кле-
ток, где m – число строк, n – число столбцов транспортной таблицы. Для этого плана можно определить
платежи (α
i
в β
j
), так, чтобы в каждой базисной клетке выполнялось условие
α
i
+ β
j
= с
i,j
. (5.3)
Уравнений (5.3) всего m + n – 1, а число неизвестных равно m + n. Следовательно, одну из этих не-
известных можно задать произвольно (например, равной нулю). После этого из m + n – 1 уравнений
(5.3) можно найти остальные платежи α
i
и β
j
, а по ним вычислить псевдостоимости С
i,j
= α
i
+ β
j
для каж-
дой свободной клетки.
Если оказалось, что все эти псевдостоимости не превосходят стоимостей С
i,j
≤ с
i,j
, то план по-
тенциален и, значит, оптимален. Если же хотя бы в одной свободной клетке псевдостоимотсь
больше стоимости (как в нашем примере), то план не является оптимальным и может быть
улучшен переносом перевозок по циклу, соответствующему данной свободной клетке. Цена
этого цикла равна разности между стоимостью и псевдостоимостью в этой свободной клетке.
Таблица 5.12
ПН
ПО
В
1
В
2
В
3
В
4
В
5
α
i
А
1
10
c = 7
8
c = 6
5
42
6
6
9
c = 6
0
А
2
6
4
7
c = 5
8
c = 4
6
c = 5
5
26
–1
А
3
8
c = 8
7
27
10
c = 6
8
c = 7
7
0
1
А
4
7
14
5
c = 6
4
c = 5
6
6
8
c = 6
0
β
j
7
6
5
6
6
Таблица 5.13
ПН
ПО
В
1
В
2
В
3
В
4
В
5
α
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
+
x
4 6
6
8
0
β
j
7
6
5
6
6
В таблице 5.12 мы получили в двух клетках С
i,j
≤ с
i,j
, теперь можно построить цикл в любой из этих
двух клеток. Выгоднее всего строить цикл в той клетке, в которой разность С
i,j
– с
i,j
максимальна. В на-
шем случае в обоих клетках разность одинакова (равна 1), поэтому, для построения цикла выберем, на-
пример, клетку (4, 2).
Теперь будем перемещать по циклу число 14, так как оно является минимальным из чисел, стоящих
в клетках, помеченных знаком "–". При перемещении мы будем вычитать 12 из клеток со знаком "–" и
прибавлять к клеткам со знаком "+".
После этого необходимо подсчитать потенциалы α
i
и β
j
и цикл расчетов повторяется.

Страницы