Студопедия

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

КАТЕГОРИИ:

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






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




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

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

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

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

, где

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

1.

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

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

Док-во:

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

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

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

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

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


mylektsii.ru - Мои Лекции - 2015-2018 год. (0.005 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал