Тема 3 Двойственные задачи линейного программирования
Две задачи ЛП, обладающие следующими свойствами называются двойственными. 1. В одной задачи ищется максимум, в другой минимум линейной функции. 2. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений другой задачи. 3. Каждая задача записана в стандартной форме, причем в задаче на минимум все неравенства вида « 4. Матрицы коэффициентов при переменных в системах ограничений обоих задач являются транспонированными друг к другу: 5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных другой задачи. 6. Условия неотрицательности переменных имеются в обеих задачах. Рассмотрим двойственные задачи ЛП:
Первая (основная) теорема двойственности: если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая задача, причем оптимальные значения их целевых функций равны:
Замечание. Обратное утверждение не верно. Именно: если условия одной задачи противоречивы, это вообще говоря не означает, что другая задача неограниченна. Вторая теорема двойственности. Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных целевой функции, выраженной через не основные переменные, ее оптимального решения Третья теорема двойственности. Компоненты оптимального решения двойственной задачи равны значениям частных производных функции Метод, при котором сначала симплекс-методом решается двойственная задача, а затем оптимум и оптимальное решение исходной задачи находится с помощью теорем двойственности, называется двойственным симплекс методом. Он применяется в случаях, когда первое базисное решение недопустимо или при Компоненты оптимального решения двойственной задачи называются оптимальными (двойственными или объективно обусловленными) оценками исходной задачи. Двойственные оценки служат инструментом анализа и принятия правильных решений в условиях постоянно меняющегося производства. Пример. В результате решения задачи был получен оптимальный план Решение. Имеем Сопоставим дополнительные затраты на ресурсы в расчете на единицу продукции Полученный результат больше, чем цена продукции Объективно обусловленные оценки ресурсов позволяют судить об эффекте не любых, а лишь сравнительно маленьких изменениях ресурсов. При крупных изменениях меняются сами оценки, что делает невозможным использование оценок для анализа производства.
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|