ВУЗ:
Составители:
93
4. Для «вырожденного» случая характерно, когда один (или более)
свободный член в уравнениях-ограничениях получается равным нулю.
Это означает, что в данном опорном решении обращаются в нуль не
только свободные переменные, но и некоторые из базисных.
При наличии «вырождения» может оказаться, что замена одной из
свободных переменных на базисную и обратно
приводит только к пере-
становке переменных, без уменьшения целевой функции. В очень ред-
ких случаях может оказаться, что последовательное применение прави-
ла выбора разрешающего элемента приводит к тому, что после несколь-
ких замен х
j
↔ у
i
мы вновь возвращаемся к тому же набору базисных и
свободных переменных, с которого начали. Это называется «зациклива-
нием». Для избежания этого достаточно бывает при повторении взять
разрешающий элемент не так, как он был взят первый раз (например, в
другом столбце).
П р и м е р I. Найти решение задачи линейного программирова-
ния с уравнениями
),2(2
),(5
),(1
),2(2
21
4
31
3
321
2
321
1
хх
у
хх
у
ххх
у
ххх
у
−−=
+−=
+−−=
−+−=
(5.23)
обращающее в минимум линейную функцию
min L = 0 – (-x
1
+2x
2
+x
3
). (5.24)
Р е ш е н и е. Все свободные члены (5.23) неотрицательны, значит
опорное решение налицо:
x
1
= x
2
= х
3
= 0; у
1
= 2; у
2
= 1; у
3
= 5; у
4
= 2.
Является ли оно оптимальным? Нет, т.к. коэффициенты при x
2
и х
3
в (5.24) положительны, значит, увеличивая эти переменные, мы умень-
шаем L. Запишем (5.23), (5.24) в виде стандартной таблицы (см. табл.
5.10).
Страницы
- « первая
- ‹ предыдущая
- …
- 91
- 92
- 93
- 94
- 95
- …
- следующая ›
- последняя »
