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

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