Доказательство
Рассмотрим в
. Покажем:
. Пусть
, что
. Если
. Если
, что
.
- выпуклы!
- т.к. оно пересечение конечного числа полупространств. Покажем для
. Пусть
, что
Из выпуклости
И выпукло.
Из (Т.1, п.2.4) - гиперплоскость,
отделяющая
. Обозначим
(2) Покажем:
Действительно, пусть
(очевидно)
Тогда
(2) перепишется: (3)Из (3) выведем:
, где
удовлетворяет условиям (Т.4.1.1) и является Седловой точкой.
Пусть положим
. Из левой части (3) для
получаем
Из правой части (3)
Значит
(4)
В рассмотрим
Подставляя
в правую часть (3), получим:
Покажем, что
Пусть
точка, фигурирующая в условиях Слейтера, тогда
Для
из левой части (3) находим
(5)
Предположим, Тогда, т.к.
из условий Слейтера следует
. Это противоречит (5), т.е. значит
Поделив
на
можно считать
Осталось показать, что
(6)
Пусть Для
выполняется
С учетом
из левой части (3) для этой точки получим
и в силу (4) получаем условие (6).
Замечание. При задача ВП является частным случаем задачи 1 (П.3.1). Предположим, что в задаче ВП
. Тогда условие 1 в (Т.1., п.4.2) принимает вид
и из теоремы Куна-Таккера вытекает теорема Кароша-Джона, в которой
Обратно, если в задаче ВП некоторая точка
удовлетворяет условиям (Т.1, п.1.3) при
то по Т.,п.4.2 пара
является седловой точкой функции Лагранжа этой задачи и по Т.2, п.4.2 точка
доставляет решение задаче ВП.
12. Связь между основной и двойственной задачами.
Пусть - функция Лагранжа для задачи ВП. Введем в рассмотрение функцию
,
Тогда и при
неравенство переходит в равенство. Если
то либо
, что
либо
, что
. В любом случае
выбором
можно сделать сколь угодно большой, поэтому
и
.
Поэтому исходная задача может быть записана в виде:
Задача 1. .
Поступим аналогичным образом, поменяв роль переменных и операций максимизации и минимизации, т.е. введем наряду с функцией функцию
, определенную формулой
и рассмотрим задачу.
Задача 2. .
Опр. 1.Задача 2 называется двойственной к задаче 1, которая называется основной. Переменные называются основными, а
двойственными. В качестве примера рассмотрим следующую задачу:
, (1) где А – матрица размерности
. Она называется задачей линейного программирования в канонической форме. Для этой задачи
,а функция Лагранжа
имеет вид:
.
Функция выписывается в явном виде
Отсюда ясно, что точку , на которой может достигаться верхняя грань функции
, достаточно искать во множестве
. Двойственная задача к задаче (1) формулируется следующим образом:
(2). Таким образом, двойственная задача к задаче (1) тоже является задачей линейного программирования. Можно показать, что двойственная задача к задаче (2) будет исходной задачей (1).
Замечание.В общем случае задача двойственная к двойственной не всегда совпадает с исходной.
Задачи 1 и 2 из предыдущего пункта тесно связаны между собой. Обозначим .
Теорема 1.Имеет место неравенство .