Математические свойства пары взаимно двойственных задач

Исходная (прямая) задача.

Исходная в матричном виде.

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

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

Лемма 1: двойственная задача к двойственной является исходной задачей.

Лемма 2 (основное неравенство теории двойственности): для любого допусти…

Пример:

Предприятие может работать по двум технологиям. При этом используются два типа ресурсов. Запасы ресурсов составляют 12 тонн и 4 литра соответственно. За 1 час работы по первой технологии расходуется 2 тонны первого ресурса и 1 литр второго, а за 1 час работы по второй технологии — 1 тонна первого ресурса. 1 час работы по первой технологии приносит доход 8 тыс. руб., а по второй — 3 тыс. руб. Суммарное время работы по технологиям должно составлять 6-часовую смену. Определить время работы по каждой технологии так, чтобы суммарный доход был наибольшим.

· Математическая модель.

[час] - время работы по каждой технологии.

• · Построим двойственную задачу.
• ·
• · Проверим, является ли оптимальным решение .

Для этого запишем соотношения дополняющей не жесткости. Подставим в эти соотношения компоненты решения

Решая данную систему уравнений, получим. Подставим в ограничения двойственной задачи. Первое ограничение не выполняется:

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

· Предположим, что нам известно оптимальное решение прямой задачи, тогда найдем :

Таким образом, мы получили оптимальное решение двойственной задачи .