Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Двойственность в задачах линейного программирования. Теорема двойственности.






Рассмотрим задачу линейного программирования в нормальной форме:

или, в матричной записи:

Задачей, двойственной к задаче выше(двойственной задачей)- называется задача линейного программирования от m переменных вида:

или, в матричной записи:

, где

Теорема о двойственности: пусть х – допустимый план задачи линейного прог-я, у – допустимый план двойственной задачи:

1.

2. Если , то задача линейного прог-я не имеет допустимых планов, следовательно z=+бесконечность, следовательно двойственная задача не имеет допустимых планов.

3. Если х – допустимый план задачи линейного прог-я, у- допустимый план двойственной задачи и , то х – решение задачи линейного прог-я, у- решение двойственной задачи.

Док-во:

1) Т.к. х – допустимый план, то . Оценим

2) – противоречие => Z не имеет допустимых планов.

3) − допустимый планы. . Пусть – решение задачи линейного прог-я.

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

решение задачи => y - решение двойственной задачи. Док-но.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.