Все шпаргалки / Теория вероятностей и матстатистика / 

Двойственная задача линейного программиро-вания. Основные теоремы двойственности. Эконо-мический смысл двойственных оценок. Первая теорема двойственности(Основная).

Если одна из двойственных задач имеет оптимальное решение, то и другая имеет его, причём экстремальные значения их целевых функций совпадают . -оптимальные реше-ния пары двойственных задач. Если же целевая одной из двойственных задач не ограничена, то двойственная задача решения не имеет, т.к. область допустимых решений пустая. Основная теорема двойственности даёт правило нахо-ждения оптимального решения двойственной задачи о оптимальному решению исходной задачи. Для нахож-дения оптимального решения двойственной задачи необходимо найти оптимальное решение исходной задачи симплекс-методом. Оптимальное значение двойственной переменной равно соответствующей оценке последней симплекс-таблицы плюс коэффици-ент целевой функции исходной задачи.Вторая теорема двойственности (О равновесии). Теорема верна для симметричных двойственных задач. Для остальных задач можно применять только для ограничений в виде неравенств и для неотрицательных переменных. Рассмотрим стандартную ЗЛП. Двойственная к ней имеет вид: Теорема. Для того, чтобы допустимые решения исходной и двойственной стандартных задач были оптимальными необходимо и достаточно, чтобы име-ли место следующие соотношения: Экономический смысл двойственных оценок. Рас-смотрим задачу. Предприятие имеет m-видов ресурсов в количестве единиц , из которых производятся n-видов продукции. -расход i-го ресурса на производство единицы j-ой продукции. Составить план выпуска продукции, обеспечивающий максимальную стоимость продукции. Обозначим за количество продукции j-го вида. Тогда модель задачи такова: Найти переменные , удовлетворяющие системе ограниче-ний при которых функция Оценим ресурсы, необходимые для изготовления про-дукции. Обозначим за - оценку единицы первого ресурса. Тогда оценка ресурсов, идущих на изготовле-ние единицы j-ой продукции равна . Она должна быть не меньше стоимости единицы продукции. Получаем систему ограничений двойственной задачи. Суммарная оценка всех ресурсов такова: Пусть найдены два оптимальных решения взаимно двойственных задач: и Из теоремы о равновесии следует, что если какая-либо переменная двойственной задачи равна «0», то соот-ветствующее ограничение исходной задачи выполня-ется как строгое неравенство. Допустим, что , тогда Это означает, что 1-й ресурс в оптимальном плане используется не полностью. Он имеется в избытке на предприятии, т.е. не является дефицитным. Из этой же теоремы следует, что если какая-либо переменная двойственной задачи не равна «0», то соответствующее ей ограничение исходной задачи выполняется как строгое равенство. Пусть , тогда , т.е. 2-й ре-сурс в оптимальном плане используется полностью, этот ресурс дефицитен для предприятия. Таким обра-зом, двойственные оценки показывают, какие ресурсы являются дефицитными для предприятия, а какие нет. Они выявляют за счёт увеличения каких ресурсов можно улучшить план. Рассмотрим целевую функцию двойственной задачи . Пусть 2-й ресурс является дефицитным, т.к. 2-й ресурс имеется в количестве , увеличим это количество на едини-цу. Получим: Т.е. целевая функция увеличивается на , тогда увеличивается на , т.о. ненулевые оценки показывают на сколько увеличится прибыль предпри-ятия, если объём дефицитного ресурса увеличить на единицу.