Исходная (прямая) задача.
Исходная в матричном виде.
Двойственная задача.
Двойственная задача в матричном виде.
Лемма 1: двойственная задача к двойственной является исходной задачей.
Лемма 2 (основное неравенство теории двойственности): для любого допусти…
Пример:
Предприятие может работать по двум технологиям. При этом используются два типа ресурсов. Запасы ресурсов составляют 12 тонн и 4 литра соответственно. За 1 час работы по первой технологии расходуется 2 тонны первого ресурса и 1 литр второго, а за 1 час работы по второй технологии — 1 тонна первого ресурса. 1 час работы по первой технологии приносит доход 8 тыс. руб., а по второй — 3 тыс. руб. Суммарное время работы по технологиям должно составлять 6-часовую смену. Определить время работы по каждой технологии так, чтобы суммарный доход был наибольшим.
· Математическая модель.
[час] - время работы по каждой технологии.
- · Построим двойственную задачу.
- ·
- · Проверим, является ли оптимальным решение .
Для этого запишем соотношения дополняющей не жесткости. Подставим в эти соотношения компоненты решения
Решая данную систему уравнений, получим. Подставим в ограничения двойственной задачи. Первое ограничение не выполняется:
Мы получили, что найденное нами решение не является допустимым для двойственной задачи. Поэтому можно сделать вывод, что решение не является оптимальным решением исходной задачи.
· Предположим, что нам известно оптимальное решение прямой задачи, тогда найдем :
Таким образом, мы получили оптимальное решение двойственной задачи .