Контрольные вопросы и упражнения

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

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

Решить задачи линейного программирования методом искусственного базиса.

3.

4.

6 Двойственность в линейном программировании

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

Пара двойственных задач имеет вид:

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

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

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

Пример. Составить двойственную задачу к задаче из пункта 4, найти её решение. Дать экономико-математический анализ оптимального плана.

Решение: Исходная задача и её оптимальное решение имеют вид

Двойственная задача имеет вид

Проверим, как удовлетворяется система функциональных ограничений и целевая функция оптимальным планом

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

Значение целевой функции двойственной задачи

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

Экономико-математический анализ оптимальных решений базируется на свойствах двойственных оценок. В пределах устойчивости двойственных оценок имеют место следующие свойства.

1. Величина двойственной оценки того или иного ресурса показывает, на сколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на одну единицу (двойственные оценки измеряют эффективность малых приращений объемов ресурсов в конкретных условиях данной задачи). В рассматриваемом примере увеличение запасов сырья I вида не повлияет на оптимальный план выпуска продукции, а увеличение запасов сырья II вида на одну единицу привело бы к росту максимальной суммы прибыли на 2 ден.ед. (y₂=2).

2. Двойственные оценки отражают сравнительную дефицитность различных видов ресурсов в отношении принятого в задаче показателя эффективности. Оценки показывают, какие ресурсы являются более дефицитными (они будут иметь самые высокие оценки), какие менее дефицитны и какие совсем недефицитны (избыточны). В примере недефицитным ресурсом является сырье I, поскольку y₁=0. Самым дефицитным является сырье II.

3. Двойственные оценки позволяют определять своеобразные «нормы заменяемости ресурсов». В примере относительная заменяемость ресурсов определяется отношением 2:1.