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

UptoLike

ВУЗ: 

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

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

Рубрика: 

204
.
5
17
8
5
1
14;
5
2
8
5
1
02
;
4
13
15
20
1
13;120
4
1
04
;
5
2
8
5
1
02;
2
1
20
5
1
2
3
2
;08
4
1
02;
2
5
20
5
1
2
3
5
;
2
9
10
20
1
05;
2
3
20
20
1
2
3
2
4223
4122
3414
3213
3111
=
⋅+−−=∆=
⋅+−=∆
=
⋅+−−=∆−=
⋅+−=∆
=
⋅+−=∆−=
⋅+−−=∆
=
⋅+−=∆=
⋅+−−=∆
=
⋅+−=∆=
⋅+−−=∆
Из этих расчетов видно, что опорный план табл. 5.9 не оптимальный, поскольку
характеристики свободных клеток
A
1
B
4
и
A
2
B
2
оказались отрицательными, что указывает
на возможность снижения значения целевой функции, т.к.
.
'
1 ijijss
xFF ∆+=
−
Таким образом, следующий,
третий шаг
в решении задачи
заключается в
переходе от не оптимального
плана
к лучшему плану.
Переход к лучшему опорному плану
, так же как и в транспортной задаче,
осуществляется посредством перераспределения заданий по циклу пересчета (цепям),
поскольку запись новой переменной в одну из свободных клеток нарушает
ограничительные условия (5.29, 5.30). Однако здесь это не настолько просто, как это было
в транспортной задаче.
Поскольку в уравнение (5.30) входят ламбды, путем простого перераспределения
по циклу пересчета общего баланса (т. е. удовлетворения условий (5.29), (5.30) добиться
не удается. Поэтому в ламбда-задаче на каждой итерации, помимо перераспределения
заданий по специфическим циклам пересчета, производится балансировка за счет записи
заданий в столбец резерва времени, величина которого является переменной.
В связи с этим циклы (цепи) в ламбда-задаче строятся таким образом, чтобы они
обязательно
имели выход на одну или две базисные клетки столбца B
n+1
.
Соединение
цикла пересчета с базисной клеткой столбца
B
n+1
называют
шлейфом.
Возвратимся к нашему примеру и для клетки
A
2
B
2
, в которой наибольшая по
абсолютной величине отрицательная оценка, построим цикл пересчета. Если бы это была
транспортная задача, цикл пересчета имел бы форму четырехугольника с вершинами в
клетках
A
2
B
2
,
A
2
B
4
,
A
4
B
4
и
A
4
B
2
.
В ламбда-задаче этот цикл надо соединить шлейфом еще с
базисной клеткой
A
2
B
n+1
.
Таким образом, в этом цикле (рис. 5.6) появилась новая, пятая,
вершина, в отличие от других клеток (не принадлежащих столбцу (
B
n+1
),
имеющая
одностороннюю связь.
Прежде чем сформулировать свойства циклов пересчета ламода-задачи, построим
циклы для всех остальных свободных клеток. Это нами делается не из требований
решения данного примера задачи (на этой итерации достаточно цикла клетки
A
2
B
2
,
которую следует занять
х
22
для перехода к лучшему плану), а для демонстрации
различных вариаций в построении циклов для того, чтобы читатель мог разобраться в
этом новом, сначала не легком деле. Вершины циклов (рис. 5.6 и 5.7), соответствующие
клеткам для которых они построены, отмечены квадратами, остальные вершины—
кружками. В них указаны «координаты» соответствующих вершин.

Страницы