Математические методы исследования операций в экономике (стр. 19 из 37)
Тогда
достигается при λ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), т. е. очередная точка будет определяться как
Действуя по аналогии с предыдущей итерацией, для определения промежутка допустимых значений шагового множителя λ составляем систему неравенств (2.18):
Окончательно имеем λ∈ [0; 1].
Тогда
достигается при λ2=1. Отсюда получаем следующую точку x(3) = (3,4).
Итерация 3. В точке x(3) множество активных ограничений будет иметь вид I(x(3))={1,2}. Найдем значения градиентов: ∇f(x(3)) = (1, 1), ∇g1(x(3)) = (2x1(3), 2x2(3)) =(8, 6) и ∇g2(x(2)) = (0,1).
Задача определения допустимого прогрессивного направления (2.24)-(2.25) будет иметь вид:
Значение τ из практических соображении следует брать достаточно малым, например τ =0,001. Опуская решение данной задачи, приведем интересующие нас компоненты ее оптимального плана:s(3) = (0,0). Итак, не существует прогрессивного направления, исходящего из точки х(3) Таким образом, оптимальный план рассматриваемой задачи (2.26)-(2.27) х* = (4,3), а максимальное значение целевой функции f* = х1(3) + х2(3) =7.
Графическая иллюстрация проведенного процесса решения представлена графически на рис. 2.6.
2.2. ДВОЙСТВЕННОСТЬ В НЕЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
2.2.1. Понятие седловой точки. В настоящем параграфе мы кратко остановимся на некоторых фундаментальных моментах теории нелинейного программирования. Отправной точкой для них является распространение метода Лагранжа для решения ЗНП с ограничениями в форме неравенств:
где X — некоторая область в пространствеRn.
По аналогии с п. 2.1.2 определим для задачи (2.28) функцию Лагранжа:
-Пара векторов (х, u) называетсяседловой точкойфункции Ф(х,и) в некоторой области X x U, еслидля любых x ∈ X и u ∈ U
Неравенства (2.30) также называют неравенствами седловой точки.
В качестве примера седловой точки может быть приведена точка (0, 0) для функции Ф(х,и) = -х2 + и2, определенной на множестве R х R. В самом деле, Ф(0,0)=0, Ф(х,0)=-х2, Ф(0, и) = и2, а для любых x∊R иu∊R выполняются неравенства –х2≤0 и 0 ≤и2.
На рис. 2.7 изображен график функции Ф(х,и) (гиперболический параболоид), и, как видно, в окрестности точки (0,0) он действительно по форме напоминает седло, чем и объясняется происхождение соответствующего термина.
2.2.2. Теорема Куна—Таккера. Центральное место в теории нелинейного программирования занимает теорема Куна— Таккера, которая связывает решение ЗНП с наличием седловой точки у соответствующей функции Лагранжа.
  Теорема 2.3. (Достаточное условие экстремума).Если (х, и) — седловая точка функции Лагранжа, в области x∊X⊇D,и≥0,то х являетсяоптимальным планом задачи (2.28), причем справедливо так называемоеправило дополняющей нежесткости: |
Доказательство.
По определению седловой точки
при всех x∊X,и≥0. Из второго неравенства в (2.32) следует, что
Однако (2.33) может иметь место только тогда, когда gi(x)≤0 при всех i∊1:m. Действительно, если существует такоеk, чтоgk(x)>0, то, положив иi=0 для всехi ≠ k и выбрав достаточно большое иk > 0, можно добиться того, что значение
окажется больше постоянного выражения
Из того, что для всех i∊1:m выполняются неравенстваgi(x)≤0, следует, что х является допустимым планом задачи (2.28).Если в левую часть неравенства (2.33) подставить значения ui = 0,i∊1:m, то получим, что
Вместе с тем из того что,gi(x)≤0 и ui ≥0, следует оценка 
Совместное рассмотрение последних двух неравенств приводит к правилу дополняющей нежесткости в точке х: 
Тогда на основании левой части неравенства седловой точки (2.32) имеем, что для всех х∊Х (в том числе и для х∊D)
Но условию ЗНП для любыхх∊Dверны неравенства gi(x)≤0, что, в сочетании с условием ui≥0, позволяет записать 
Значит,
Окончательно получаем, что для любыхх∊Dсправедливо соотношениеf(x)≥f(x), т. е. х — оптимальный план задачи (2.28). -Утверждение, обратное теореме (2.3), т. е. необходимое условие экстремума в ЗНП, оказывается верным только при выполнении дополнительных условий, которым должна удовлетворять задача (2.28). Важнейшим из них является так называемое условие регулярности Слейтера:
-Говорят, что функция gi (х), задающая ограничение в задаче (2.28), удовлетворяет условию регулярности Слейтера, если существует такая точка 
, принадлежащая области допустимых планов D, что