Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Двойственность в линейном программировании, свойства двойственных оценок и их использование в анализе оптимального плана

Рассмотрим основные понятия и выводы специального раздела линейного программирования — теории двойственности.

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

Связь исходной и двойственной задач заключается, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой.

Хорошо разработанный математический аппарат линейного программирования позволяет не только получать с помощью эффективных вычислительных процедур оптимальный план, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, двойственной к исходной ЗЛП.

Каждая из задач двойственной пары фактически является самостоятельной задачей линейного программирования и может быть решена независимо от другой задачи. Однако при определении симплексным методом оптимального плана одной из задач находится решение и другой задачи.

Правило построения двойственной задачи по отношению к исходной задаче определяется системой соотношений:

Исходная задача Двойственная задача

Двойственная задача составляется согласно следующим правилам:

1) целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи — на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид «£», а в задаче на минимум — «³».

2) матрица, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица в двойственной задаче получаются друг из друга транспонированием;

3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи; число ограничений двойственной задачи равно числу переменных в исходной задаче;

4) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи — коэффициенты при неизвестных в целевой функции исходной задачи;

5) каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записанному в виде неравенства «£», соответствует переменная, связанная условием неотрицательности.

Основные утверждения о двойственных задачах содержатся в двух следующих теоремах

Теорема 1(основная теорема двойственности). Если одна из двойственных задач разрешима, то разрешима и другая, причем экстремальные значения целевых функций задач равны: . Если одна из двойственных задач неразрешима, то неразрешима и другая.



Теорема 2 (о дополняющей нежесткости). Если при подстановке компонент оптимального плана в систему ограничений исходной задачи iограничение обращается в неравенство, то iкомпонента оптимального плана двойственной задачи равна нулю. Если iкомпонента оптимального плана двойственной задачи положительна, то iограничение исходной задачи удовлетворяется ее оптимальным решением как строгое равенство.

То есть для оптимальных планов двойственных задач имеют место соотношения:

,

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

<== предыдущая лекция | следующая лекция ==>
| Двойственность в линейном программировании, свойства двойственных оценок и их использование в анализе оптимального плана

Дата добавления: 2014-01-07; Просмотров: 278; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ‚аш ip: 54.196.107.247
Генерация страницы за: 0.123 сек.