Содержательная постановка двойственной задачи

Для любой задачи линейного программирования можно сформулировать задачу-двойник, или иначе, двойственную задачу. Эта задача-двойник является своеобразным«зеркальным отражением» исходной задачи, поскольку ее формулировка использует те же параметры, что и исходная задача, а ее решение может быть получено одновременно с решением исходной задачи. Фактически при решении исходной задачи симплекс – методом одновременно решается и двойственная задача, и наоборот. Следует также заметить, что исходная и двойственная задачи совершенно симметричны. Если двойственную задачу рассматривать как исходную, то исходная будет для нее двойственной.

Одной из важнейших “зеркальных” связей между исходной и двойственной задачами является связь между искомыми неизвестными (х₁, х₂) и эффективностью (предельной эффективностью, «теневой ценой»). Для того чтобы уловить эту связь, сформулируем содержательно двойственную задачу к знакомой нам задачи об оптимальном плане выпуска мороженого.

Пусть имеется покупатель на все виды ресурсов, используемые для выпуска продукции (см.табл.исходных данных).

Какие цены на эти ресурсы нужно назначить, чтобы продать их было выгоднее, чем производить продукцию? Какую минимальную сумму можно выручить от продажи ресурсов при этом условии?

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

цена 1кг молока - u₁

цена 1 кг наполнителя - u₂

цена 1 кг изменения спроса на сливочное мороженое - u₃

цена 1 кг изменение спроса на шоколадное мороженое - u₄

Сразу заметим, что эти цены называются теневыми. Они, разумеется, не могут иметь никакого отношения к рыночным ценам на данные ресурсы, поскольку, как будет видно из решения, никаких рыночных (или внерыночных) механизмов формирования цен на данные в решение не рассматривается. Теневые цены характеризуют ценность ресурсов для производителя.

Целевая функция - это, очевидно, доход, который получит производитель-продавец ресурсов, если продаст по этим ценам все имеющиеся ресурсы. Таким образом, целевая функция, записанная в таблице элементов модели (см.табл.) - это сумма произведений искомых цен на запасы имеющихся ресурсов, приведенных в соответствующем столбце таблицы параметров задачи. Разумеется, интерес продавца ресурсов состоит в том, чтобы продать их подороже. Однако интерес покупателя в том, чтобы купить подешевле.

Решение данной задачи позволит продавцу определить нижние границы цен на ресурсы, которые он может назначить, чтобы доход от их продажи была не ниже, чем доход тот производства товаров на основе этих ресурсов. Целевую функцию данной задачи можно также рассматривать как издержки покупателя ресурсов, которые необходимо минимизировать, приняв во внимание интересы производителя-продавца ресурсов.

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

Соответственно при записи ограничений в таблице элементов модели (см.табл.) использован тот же принцип. Если производитель (продавец ресурсов) хочет продать 0,8 кг молока, 0,4 кг наполнителя и 1кг спроса на сливочное мороженое, то он должен получить не меньше, чем отпускная цена 1 кг сливочного мороженого (на которое, согласно данным табл.4.1, и идут все эти ресурсы). Аналогично если он хочет продать 0,5 кг молока, 0,8 кг наполнителя и по 1 кг изменения спроса на сливочное и шоколадное мороженое, то он должен получить не меньше, чем отпускная цена 1 кг шоколадного мороженого.

 

Элементы модели

Искомые неизвестные	Целевая функция
u₁, u₂, u₃, u₄	Z(u)=400u₁+365u₂+100u₃+350u₄
Ограничения
0,8u₁+0,4u₂+u₃+0u ≥16 0,5u₁+0,8u₂-u₃+u₄≥14 u₁, u₂, u₃, u₄≥0

 

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

Целевая функция исходной задачи формируется как сумма произведений строки переменных (количество продуктов разного типа x₁,x₂) на строку дохода от производства единицы каждого продукта; целевая функция двойственной задачи - как сумма произведений столбца переменных (теневых цен ресурсов u₁-u₄) на столбец запасов этих ресурсов.

Аналогично ограничение на расход каждого из используемых ресурсов в исходной задаче формируется как сумма произведений строки переменных (x₁,x₂) на расход данного ресурса при производстве единицы каждого продукта. Ограничение на выручку от продажи ресурсов, идущих на производство данного продукта в двойственной задаче, формируется как сумма произведений столбца теневых цен (u₁-u₄) на столбец расходов каждого из используемых ресурсов на производство единицы данного продукта.

Эта симметрия проявляется и при сопоставлении более общих формулировок исходной и двойственной задач, когда n продуктов может быть произведено из m ресурсов.