Математическое программирование и моделирование экономических процессов. Коробов П.Н. - 170 стр.

UptoLike

ВУЗ: 

СПбГЛТУ | Санкт-Петербург

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

Рубрика: 

170
этот опорный план является невырожденным, так как число базисных клеток,
заполненных поставками x
ij
>0, равно рангу r=т+п-1 системы ограничительных уравнений
(4.14), (4.15).
Следующий этап решения задачи методом потенциалов заключается в проверке
исходного опорного плана на оптимальность. С этой целью прежде всего необходимо
вычислить предварительные потенциалы. Для этого потенциал поставщика А
2
принимаем
равным нулю, т. е. u
2
=0. Остальные потенциалы вычисляются по формулам (4.20) и (4.21),
они будут равны
v
1
=c
21
-u
2
=4-0=4, u
1
=c
13
-v
3
=3-4= -1;
v
2
=c
22
-u
2
=7-0=7, u
3
=c
31
-v
1
=3-4= -1;
v
3
=c
23
-u
2
=4-0=4, u
4
=c
42
-v
2
=3-7= -4;
v
4
=c
14
-u
1
=2-(-1)=3.
Полученные значения предварительных потенциалов записываются, в
дополнительную строку (v
j
) и дополнительную графу (u
i
) табл. 4.9.
Далее по формуле (4.23) вычисляются значения характеристик свободных клеток:
∆
11
=c
11
-(u
1
+v
1
)=5-(-1+4)=2,
∆
12
=c
12
-(u
1
+v
2
)=4-(-1+7)= -2,
∆
24
=c
24
-(u
2
+v
4
)=4-(0+3)=1,
∆
32
=c
32
-(u
3
+v
2
)=5-(-1+7)=-1,
∆
33
=c
33
-(u
3
+v
3
)=6-(-1+4)=3,
∆
34
=c
34
-(u
3
+v
4
)=8-(-1+3)=6,
∆
41
=c
41`
-(u
4
+v
1
)=4-(-4+4)=4,
∆
43
=c
43
-(u
4
+v
3
)=7-(-4+4)=7,
∆
44
=c
44
-(u
4
+v
4
)=5-(-4+3)=6,
Из этих данных видно, что условие (4.24), а следовательно, и (4.22) не
выполняются. Таким образом, исходный опорный план (табл. 4.9) не оптимальный.
Для улучшения плана следует занять положительной поставкой клетку A
l
B
2
,
имеющую минимальную отрицательную характеристику.
Переход к лучшему опорному плану в методе потенциалов осуществляется так же,
как и в распределительном методе.
Т а б л. 4.10
Пункты и объемы
производства
Пункты и объемы потребления
Потенциалы
поставщиков
u
i
В
1
В
2
В
3
В
4
180 200 150 120
A
1
190
70
120
-3
A
2
200 20
30
150
0
A
3
160 160
-1
A
4
100
100
-4
Потенциалы
потребителей v
j
4 7 4 5
На рис. 4.8 представлен цикл перераспределения поставок относительно
свободной клетки A
1
B
2
. В эту клетку следует записать поставку, равную 70 (наименьшую
из отмеченных знаком минус по вершинам цикла), далее в положительных вершинах
следует прибавить эту поставку, в отрицательных — вычесть.
5
4 3 2
4
7
4
4
3 5 6 8
4 3
7
5

Страницы