Дз 9 (Решения задач)

Выполнили студенты 321 группы:Аграновский МихаилБрызгалов АнтонМирошник ВладиславСмирнов АлександрЗадача 9.1Расшифровать теорему Каруша-Куна-Такера для ОзЛП.ОзЛП: max( , ) = min( , ).Теорема Каруша-Куна-Такера (далее ТККТ)Пусть в задаче математического программирования с регулярным множеством :функции , выпуклы на, ∈ ( );≠ ∅;регулярно ∀ ∈ ;Тогда — точка минимумамножеством ⇔ ∃ ≥ 0.;в задаче математического программирования с регулярнымРешение1 шаг= max( , ) = − min(− , ) = − min ( ),∈∈∈где( ) = (− , ) = −=∈:( ) ≤ 0 ∀ = 1,( )=где,−=( , )−,,— это -ая строка.2 шагПусть— решение= max( , ) = − min ( ).

Тогда согласно ТККТ это равносильно:∈∈∃ ∈≥0((3 шагРаспишем последние соотношения подробнее:, )=0)=0Выполнили студенты 321 группы:Аграновский МихаилБрызгалов АнтонМирошник ВладиславСмирнов Александр( , ) = −( , ) +( ) = −( , ) +((, )−) = −( , ) +( , )−= −( , ) +− ( , ) = −( , ) +−( , )= −( , ) +− ( , ) = −( , ) +−( , )(= −( , ) +) − ( , ) = −( , ) + (, )−( , ) =(− , )−( , )Тогда:(, )=, (Итак,(− , )−( , ) =) = −( , ) + (− =0⟹)=0⟹(,— точка max( , ) тогда и только тогда, когда ∃ ∈,≥ 0:=)=( , )= и(,∈Задача 9.2Показать, что — решение двойственной задачи ЛП.РешениеШаг 1∗Запишем ТККТ для двойственной задачи к ОзЛП:= min ( , ).∈,=⟺ −≥0− ≤0+ ≤0− ≤0Пусть( )=( , )( )=( )=( )=−где∗, = 1,,− , = 1,,+ , = 1, ,— это -ый столбец матрицы .— точка min ( , ) ⟺ ∃ ∈∈,, ≥ 0:( ∗, ) = 0 и, ( ∗ ) = 0.) = ( , ).Выполнили студенты 321 группы:Аграновский МихаилБрызгалов АнтонМирошник ВладиславСмирнов Александр( , )=( , )+( )=( , )−+,−+−,−= (∗)Переобозначим:=( ,),,∈,,∈Тогда(∗) = ( , ) − ( , ) + (=( , −, )−( ,)+( −( ∗, ) =, ( ∗) = ( ,∗Итак,) + (−−− (− (−),−)−(− (∗), )+( ,− ), ))=0−=0⟺( ,∈− (0: −)=0и( ,−∃, ̅∈∈−)=(+ (, ̅ ≥ 0: −,−∗ ),),−)=(−является точкой min ( , ) тогда и только тогда, когда ∃,)∈,,∈,∗)),−,,≥или, переобозначая:, ̅ =̅=0и+ (̅,+∗Шаг 2Покажем, что если:то ∃∃ ∈∃ ∈∗,:≤, ≥ 0:, ̅∈∈Переобозначим:= ,(, ̅ ≥ 0: − +,≡)=( , ),+∗∗:≤Из ∃ ∈=0⟹:=≤ получаем, что ∃ ̅ ∈̅+ .и∃∈,Из этого следует, что, переобозначая∗∈+̅,∗∗Имеем: ∃Итак, получим: ∃, ̅ =̅=0и,∗≥0и∃≥ 0:∗∗(, ̅== ̅: ∃∈,=)=( ,,∗̅−:∈,∗≥ 0, ∃ ̅ ∈∗)≤0⟹∃≥ 0::∈,, ̅ =( ,=̅+∗и≥ 0:̅− +)., ̅ =( ,∗).Таким образом, доказано, что если задача ЛП разрешима, то разрешима и двойственная к ней, и вслучае разрешимости значения этих задач совпадают:max( , ) = ( ,∈)=( ,∗)= min ( , ),∈,что и требовалось доказать (в силу того, что двойственная к двойственной задаче ЛП совпадает спрямой задачей ЛП)..