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

UptoLike

ВУЗ: 

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

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

Рубрика: 

186
Нулевая поставка должна быть записана в свободную клетку того столбца или
строки, в которых находится поставка x
ij
>0, не связанная лучем с другими поставками.
Пример вырожденного опорного плана, являющегося допустимым решением
задачи, приведен в табл. 5.1.
Табл. 5.1
Пункты и объемы
производства
Пункты и объемы потребления
В
1
В
2
В
3
В
4
100 160 190 150
А
1
140
140
А
2
210
160
50
А
3
150
0
50
100
А
4
100
100
После распределения поставок по методу минимального элемента получен план, в
котором шесть базисных клеток, тогда как ранг системы ограничительных уравнений
(4.2), (4.3) равен
r=т+п-1=4+4-1=7.
В этом плане поставка х
41
=100 в клетке A
4
B
1
не может быть связана лучами с
другими положительными поставками. В связи с этим нельзя построить циклы пересчета
ни для одной свободной клетки столбца В
1
и строки A
4
, а также вычислить для них
потенциалы u
4
и v
1
, пока не будет число базисных клеток доведено до r =7.
В данном примере поставку х
ij
=0 следует записать в одну из свободных клеток
столбца B
1
или строки A
4
—ту, в которой наименьшее значение показателя с
ij
, т. е. в клетку
A
3
B
1
или А
4
В
2
.
Дальнейший процесс решения задачи обычный. Следует вычислить потенциалы u
i
и v
j
, записать их в дополнительной графе и строке табл. 5.1 и по ним рассчитать
характеристики свободных клеток ∆
ij
, для проверки плана на оптимальность. Если план
окажется не оптимальным, надо обычным путем перейти к лучшему плану.
В нашем примере характеристики свободных клеток равны: ∆
11
=8; ∆
12
=2; ∆
14
=2;
∆
21
=3; ∆
23
=0, ∆
32
=0; ∆
42
= -2; ∆
43
= -2; ∆
44
=2.
Таким образом, опорный план табл. 5.1 оказался не оптимальным, поскольку
возможно снизить значение целевой функции F за счет перераспределения поставок.
Оценки свободных клеток A
4
B
2
и A
4
B
3
отрицательные и одинаковые по величине. Какую
из них занять в первую очередь? На рис.5.1 показаны циклы пересчета для этих клеток.
В данном случае при переходе к лучшему плану наибольшее снижение целевой
функции F может быть достигнуто при занятии свободной клетки A
4
B
2
, так как в нее
должна быть записана большая поставка (x
42
=100), чем в клетку A
4
B
3
.
6
2
3
3
4
4
5
4
2
5
6 5
1
2
3
6

Страницы