Составители:
Рубрика:
144
-12/11+9/11-8/11=-1<1,
которому соответствует в решении (3.68) х
2
= 0. Таким образом, выполняется условие
второй теоремы двойственности и допустимые решения (3.68) и (3.72) действительно
являются оптимальными решениями. В этом можно еще дополнительно убедиться
проверкой равенства F
min
= G
max
. Действительно, подставляя значения (3.72) в выражение
(3.69), имеем
G
max
=2⋅12/11+6⋅9/11-7⋅8/11=2
И из (3.66), (3.68) F
min
=2.
В оптимальном решении двойственной задачи (3.69), (3.70) переменная y
3
= -8/11 приняла
отрицательное значение. Этим не следует смущаться, так как в задаче двойственной к
канонической задаче переменные не ограничиваются по знаку.
3.4. Понятие о вырожденности
Вычислительные правила симплексного метода выводятся в предположении, что в
каждой программе все т базисных переменных имеют положительные значения. Такие
программы называются невырожденными. Программа, в которой хотя бы одна из
базисных переменных принимает нулевое значение, является вырожденной, а задача
линейного программирования, имеющая хотя бы одну вырожденную программу,—
вырожденной задачей.
Условие невырожденности используется только при обосновании правил перехода
(см. 3.1) от одной программы (опорного решения) к «лучшей» программе, т. е. к такому
решению, при котором происходит увеличение значения целевой функции. Там же
установлена связь между двумя смежными значениями целевой функции F и F' в виде
формулы
,
'
k
FF ∆−=
β
где
.0min >
=
ik
i
a
b
β
В невырожденном случае всегда
β
>0, в вырожденном же случае, когда не все b
i
>0,
минимум отношения
ik
i
a
b
может оказаться равным нулю, т. е.
β
= 0, и никакого
«улучшения» при переходе к новому опорному решению не получится. Не исключена
возможность неограниченного количества итераций без какого-либо увеличения значения
целевой функции. Это случится, если последовательные замещения базисных переменных
образуют так называемый цикл, т. е. если будет происходить повторение нескольких
программ при невыполнении признака оптимальности по знакам чисел ∆
j
оценочной
строки.
Хотя вырожденные задачи линейного программирования встречаются
относительно часто, «зацикливание» при решении их симплексным методом появляется
лишь в исключительных случаях. Это объясняется тем, что зацикливание обусловлено не
только вырождением, но и другими условиями, которые встречаются весьма редко.
Установлено, что зацикливание невозможно, если каждая программа содержит не менее
чем т—1 положительных значений переменных.
Существуют различные способы устранения возникновения зацикливания. Однако
в практических вычислениях они почти никогда не применяются. Обычно при решении
реальных вырожденных задач линейного программирования придерживаются обычной
схемы симплексного метода. В любом случае делают некоторое замещение базисного
Страницы
- « первая
- ‹ предыдущая
- …
- 142
- 143
- 144
- 145
- 146
- …
- следующая ›
- последняя »
