Дз 9 (1125212)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Выполнили студенты 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 ( , ),∈,что и требовалось доказать (в силу того, что двойственная к двойственной задаче ЛП совпадает спрямой задачей ЛП)..

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов курсовой работы