Реферат: Метод Зойтендейка

Рис 3.

Кроме того, множество активных ограниче ний в точке х₂ равно l={2}, так ч то направление движения получается из решения следующей зад ачи:

минимизировать

при условии

Читатель может проверить на рис. 3, что оптимальным реше­нием этой задачи линейного программирования является точка, а соответствующее значение целевой функции равно .

Линейный поиск. При начальной точке х ₂ любая точка в на­правлении d₂ может быть представлена в виде Соответств ующее ей значение целевой функ­ции равно

Макси мальное значение l для которого точка Х₂ +ld₂ остается допустимой, определяется в соответствия с (1) следующим образом:

Таким образом, в качестве ^ берется оптимальное решение сле­дующе й задачи:

минимизировать

при условии

Оптимальным решением этой задачи является ,т ак что

Рис 4.

Итерация 3

Поиск направ ления. Вточке х₃ = имеем Кроме того, множество активных ограни­чений в точке х_з равно l = { 2}, так что направление движения получается из решения следующей задачи:

Можно легко проверить по рис. 4. что действительно является решением этой задачи ли­нейного программирования. Соответствующее значение целевой функции равно нулю, и процедура заканчивается. Более того, точка является точкой Куна—Такке ра.

В этой конкретной задаче функция f выпукла, и по теореме 4.3.7 точка х является оптимальным решением.

Таблица 1

?????????? ????????и ? ?? ?????? Зойтендейка ??? ?????? ???????? ???????????

Рис. 5. Пои ск решения методом Зойтендейка (случай линейных ограничений).

В табл. 1 приведены результаты вычислений для рассмо­тренной задачи. На рис. 10.5 изображен процесс поиска решения в соответствии с описанным алгоритмом.

Задачи с нелинейными ограничениями-неравенствами

Теперь рассмотрим задачу, в которой допустимая область за­дается системой ограничений-неравенств не обязательно ли­нейных:

минимизировать f(х)

при условиях g _i (х) £0,i=1, ...,m.

В теореме формулируются достаточн ые условия, при которых вектор d является возможным направлением спуска.

???????. ?????????? ?????? ??????????? f(х ) ??? ???????? g_i (?)£0,i=1, ...,m.. ????? ???????????? ?????, ? I?????????? ???????? ???????? ? ???? ????? ????????????, ?. е. . ???????????, ????? ????, ??? ??????? f ? g_i ??? ??????????????? ? ?, ? ??????? g_i ??? ?????????? ? ???? ?????. ???? ??? , ?? ?????? d ???????? ????????? ?????????н ??? ??????.

Ри с. 6. Совокупность возможных н аправлений спуска в задаче с нелиней­ными ограничен иями. 1— 1- е ограни чение; 2—3-е ограничение; 3—4-е ограни­чение; 4— 2-е ограничение; 5— возможные направления спуска; 6— линии уровня целевой функции.

Доказательство. Пусть вектор и удовлетворяет неравенствам и при . Для выполняютсянеравенства , и так как g_i непрерывн ы в точке х, то для достаточно малых . В силу дифференцируемости функций g_i при имеем

где при . Так как , то при достаточно малых . Следовательно, при i = 1, . . ., m, т.е. точка допустимая для достаточно малых положи тельных значений . Аналогично из следует, что для достаточно малых > 0 имеем . Следов ательно, вектор и является возможным направлением спуска.

На рис. 6 показана совокупность возможных направлений спуска в точке х. Вектор d , удовлетворяющий равенству , является касательн ым к множеству в точке х. Поскольку функции g_i нелинейны, движение вдоль такого вектора d может привести в недопустимую точку, что вы­нуждает нас тре бовать выполнения строгого неравенства .

????? ????? ?????? d, ?????е ????????? ???????????? ??? , ??????????? ???и ??????????? ???????? ?? и ??? . ????????? ???? ????и ??? ????? z. ????? ??????????? ?????????и ? Для ??????? j, ??????? ????????? ?????? ??? ?????????? ???????????.

Пусть (z, d)—оптимальное решение этой задачи линейного про­граммирования. Если z <0, то очевидно, что d—возможное направление спуска. Если же z= 0, то, как показано ниже, те­кущая точка является точкой Ф. Джона.

???????.. ?????????? ?????? ??????????? f (?) ??? ???????? g_i (х) £0, i = 1,..., m. ????? х— ?????????? ?????, ? . ?????????? ????????? ?????? ??????????? ???????????: