 |
 |
 |
 |
|
 |
 |
54
Представляется полезным обратить внимание читателя и на то, что применяемый для решения задач
линейного программирования симплекс-метод может быть рассмотрен как частный случай метода
допустимых направлений. В частности, этап выбора столбца, вводимого в очередной базис, соответ-
ствует определению допустимого прогрессивного направления. Более подробно о такой концепции
симплекс-метода можно прочесть в [1].
2.1.6. Пример решения ЗНП методом допустимых направлений. Рассмотрим процесс применения
метода допустимых направлений на конкретном примере. Пусть дана ЗНП:
Итерация 1. В качестве начального приближения возьмем точку х
(1)
= (0,0). Нетрудно заметить, что
она удовлетворяет
системе неравенств (2.27), т. е. х
(1)
?
D. Для х
(1)
все неравенства выполняются как
строгие, т. е. множество индексов активных ограничений I(х
(1)
)
=
?. Следовательно, в х
(1)
любое
направление является допустимым, и нам остается определить, с каким шагом
?
1
можно двигаться
вдоль градиента целевой функции s
(1)
=
?f(x
(1)
)=(1, 1). Система неравенств типа (2.18), из решения
которых определяется интервал допустимых значений для
?,
для данной задачи примет вид:
Тогда
достигается при
?
1
= 3 . Отсюда получаем следующую точку
Итерация 2. Путем подстановки координат точки x
(2)
в (2.27) определим множество активных
ограничений в точке x
(2)
: I(x
(2)
)={2}. Соответственно, задача (2.24) - (2.25), которую требуется решить
для определения допустимого прогрессивного направления
s
(2)
с учетом того, что ?f(x
(2)
)=(1, 1) и
?g2(x
(2)
)= (0, 1) примет вид:
В данном случае оптимальный план ЗЛП находится довольно просто и равен (
?,
s1,
s2)* =(-1,
1, 0).
Отбросив дополнительную переменную
?,
получаем вектор
s
(2)
= (1,0), т. е. очередная точка будет
определяться как