Теория двойственности в задачах линейного программирования

 

Получение оптимального решения оптимизационной задачи вообще и задачи линейного программирования в частности - это не конец, а фактически только начало работы менеджера с количественной моделью. При формулировке модели, как уже отмечалось, величины, количественно характеризующие ту или иную систему или управленческую ситуацию, разбиваются на две группы. Первая группа – это величины, которые субъект, принимающий решение, должен менять в ходе поиска оптимума целевой функции. В нашем случае – это количество сливочного и шоколадного мороженого ( x₁, х₂ ).

Нахождение оптимальных значений x₁ и x₂ и составляет содержание процесса «принятия решений» в данном случае. Переменные второй группы величин в ходе поиска оптимума целевой функции должны считаться постоянными (количество молока и наполнителя, ограничения по спросу, отпускная цена, расход ресурсов на единицу продукции).

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

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

- какой ресурс наиболее сильно влияет на изменение прибыли (издержек)?

- как изменится решение и целевая функция при изменении количества того или иного ресурса?

- если какой-либо продукт не входит в оптимальный план, а по каким-то не формализуемым причинам желательно, чтобы он в него входил, то какой параметр, и в каком направление следует изменить? и т.д.

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

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

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

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

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

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

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

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

цена 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 ресурсов.

 

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться: