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

Каждой задаче линейного программирования соответствует задача, называемая двойственной или сопряженной по отношению к исходной задаче.

Экономическая интерпретация двойственной задачи Рассмотрим задачу об использовании ресурсов Предположим, что некоторая организация решила закупить ресурсы S 1, S 2 и S 3 предприятия и необходимо установить оптимальные цены на эти ресурсы: y 1,y 2 и y 3

Экономическая интерпретация двойственной задачи Рассмотрим задачу об использовании ресурсов Предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не менее той суммы, которую предприятие могло получить при переработке ресурсов в готовую продукцию. Z(y)= b 1 y 1 + b 2 y 2 + b 3 y 3 min.

Экономическая интерпретация двойственной задачи Цены ресурсов y 1, y 2, y 3 называются учетными, неявными, теневыми, их часто называют оценками ресурсов. Формулировка двойственной задачи Найти такой набор оценок ресурсов, при которых общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее выручки от реализации этой продукции.

Свойства взаимно двойственных задач В одной задаче ищут максимум целевой функции, а в другой минимум. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений в другой. Каждая из задач задана в стандартной форме, причем в задаче на максимум все неравенства вида, а в задаче на минимум – все неравенства вида. Матрицы коэффициентов при переменных в системах ограничений являются транспонированными друг к другу. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче. Условия неотрицательности переменных имеются в обеих задачах.

Пример f(x)= –х 1 + 2х 2 max

Пример

Запись решения двойственной задачи 1) min z(y)=max f(x). Если одна из задач имеет решение, то имеет решение и другая. 2) Установим соответствие между переменными: переменной x i из исходной задачи ставится в соответствие дополнительная переменная из двойственной задачи, введенная в i-е ограничение (x 1 ~ y 5, x 2 ~ y 6 ). Аналогично, первоначальным переменным двойственной задачи соответствуют дополнительные переменные исходной задачи. 3) Компоненты оптимального решения двойственной задачи равны по абсолютной величине коэффициентам при соответствующих переменных в последней записи целевой функции исходной задачи. 4) Если в одной из двойственных задач нарушается единственность оптимального решения, то оптимальное решение двойственной задачи вырожденное.

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

Пример Последняя запись целевой функции исходной задачи с двумя переменными имела вид: Ее решение Поставим в соответствие переменные: Решение взаимно двойственной задачи:

Экономический смысл переменных взаимно-двойственных задач Компоненты оптимального решения исходной задачи Число единиц продукции Остатки ресурсов (число единиц) Р1Р2S1S2S3S4 x1x2x3x4x5x6 y5y6y1y2y3y4 Превышение затрат на ресурсы над ценой их реализации Объективно обусловленные оценки ресурсов (условные цены) Компоненты оптимального решения двойственной задачи

Экономический смысл объективно обусловленных оценок ресурсов Оценки ресурсов показывают, на сколько денежных единиц изменится максимальная прибыль (выручка) от реализации продукции при изменении запаса соответствующего ресурса на одну единицу. 2) Двойственные оценки могут служить инструментом анализа и принятия правильных решений в условиях постоянно меняющегося производства. С помощью этих оценок возможно сопоставление оптимальных условных затрат и результатов производства.

Экономический смысл объективно обусловленных оценок ресурсов Но: Оценки ресурсов позволяют судить об эффекте не любых, а лишь сравнительно небольших изменений ресурсов. При резких изменениях сами оценки могут стать другими, тогда их невозможно использовать для анализа эффективности производства. 3) По соотношениям объективно обусловленных оценок могут быть определены расчетные нормы заменяемости ресурсов, при соблюдении которых проводимые замены в пределах устойчивости двойственных оценок не влияют на эффективность оптимального плана.

Пример Дана задача линейного программирования, ее решение и последняя запись целевой функции. Записать для нее двойственную задачу и ее решение. Последняя запись целевой функции: Ответ:

СПАСИБО ЗА ВНИМАНИЕ! к.т.н., доц. Калашникова Т.В.