Выпуклый анализ. Теория двойственности в линейном программировании. Лекция 29 презентация

11. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ (ПРОДОЛЖЕНИЕ) 11.5. Теоремы двойственности и равновесия.

Слайд 1ВЫПУКЛЫЙ АНАЛИЗ
ЛЕКЦИЯ 14

11. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ
ПРОГРАММИРОВАНИИ


Слайд 2



11. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ
ПРОГРАММИРОВАНИИ (ПРОДОЛЖЕНИЕ)
11.5. Теоремы двойственности и равновесия.



Слайд 3






11.5. Теоремы двойственности и равновесия.
Справедлива следующая теорема,
которую обычно называют

теоремой двойственности.

Теорема 1.

либо они обе имеют решение и

не имеют решения,




Доказательство.

Выпишем функцию Лагранжа для задачи 3.



Слайд 4







Выпишем функцию Лагранжа для задачи 3д(а).
где


Слайд 5






Сравним функцию Лагранжа для двойственной задачи
Приходим к равенству
где


Слайд 6






Пусть
Тогда
Таким образом,
Пусть одна из взаимно двойственных задач имеет решение.
Тогда по теореме

9.3 существует седловая точка

функции Лагранжа для этой задачи.

При этом


Слайд 7






Выше установлено, что
Тогда по теореме 9.2
В силу (1)
справедливо равенство
Аналогично устанавливается, что
следует

существование решения основной задачи.

Теорема доказана.

Установим условия разрешимости взаимно двойственных задач.

Для существования решения взаимодвойственных задач достаточно,

чтобы обе взаимодвойственные задачи были допустимыми.

Теорема 2.

из существования решения двойственной задачи

что если одна из взаимно двойственных задач не имеет решения,

Доказательство.

Тогда


Слайд 8Из (2) выводим
то целевая функция


Слайд 9






Наоборот, если
Теорема доказана.
Теорема 3 (равновесия).
Доказательство.
Из неравенства (2)


Слайд 10






следует
В силу теоремы 1 справедливо равенство
все знаки неравенства в (6)
Имеем


Слайд 11






Из (7) выводим


Слайд 12












Аналогично из (7)
следует
Теорема доказана.


Слайд 13




Пример 1.
Рассмотрим задачу линейного программирования





Слайд 14






Построим двойственную к ней задачу:


является допустимой для прямой задачи,
так

как выполняются соотношения

Слайд 15












,

,

является допустимой для двойственной задачи,

,

,


,
так как выполняются соотношения


Слайд 16






По теореме 2 обе взаимодвойственные задачи имеют решение.
Решение прямой задачи:



Решение двойственной задачи:


В соответствии с теоремой 1 здесь выполнено равенство



Действительно,


,

Выпишем эти решения.

В силу теоремы 3


Слайд 17






Вычислим второе ограничение основной задачи,
Имеем


Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика