Выполнили студенты 321 группы:

Аграновский Михаил

Брызгалов Антон

Мирошник Владислав

Смирнов Александр

Задача 9.1

Расшифровать теорему Каруша-Куна-Такера для ОзЛП.

ОзЛП: .

Теорема Каруша-Куна-Такера (далее ТККТ)

Пусть в задаче математического программирования с регулярным множеством :

• функции , выпуклы на ;

• ;

• ;

• регулярно ;

Тогда — точка минимума в задаче математического программирования с регулярным множеством .

Решение

1 шаг

где

где — это -ая строка.

2 шаг

Пусть — решение . Тогда согласно ТККТ это равносильно:

3 шаг

Распишем последние соотношения подробнее:

Тогда:

Итак, — точка тогда и только тогда, когда .

Задача 9.2

Показать, что — решение двойственной задачи ЛП.

Решение

Шаг 1

Запишем ТККТ для двойственной задачи к ОзЛП: .

Пусть

где — это -ый столбец матрицы .

— точка .

Переобозначим:

Тогда

Итак, является точкой тогда и только тогда, когда , или, переобозначая:

Шаг 2

Покажем, что если:

то

Переобозначим:

Имеем:

Из получаем, что .

Из этого следует, что, переобозначая : .

Итак, получим: .

Таким образом, доказано, что если задача ЛП разрешима, то разрешима и двойственная к ней, и в случае разрешимости значения этих задач совпадают:

что и требовалось доказать (в силу того, что двойственная к двойственной задаче ЛП совпадает с прямой задачей ЛП).