1) Экономическая интерпретация ЗЛП: задача об оптимальном использовании ограниченных ресурсов, двойственная задача и ее экономическое содержание 2) Экономический смысл задачи, двойственной к задаче оптимального использования ресурсов. 3) Правило построения двойственной задачи, математическая запись. Теоремы двойственности и их использование для анализа оптимальных решений. 4) Двойственные оценки в ЗЛП, интервалы устойчивости двойственных оценок. Свойства двойственных оценок и их использование для анализа оптимальных решений. 5) Двойственные оценки как мера влияния ограничений на целевую функцию.

Понятие двойственности ЗЛП Прямая ЗЛП – исходная задача. Двойственная задача – задача, формулируемая из прямой с помощью определенных правил. Любой прямой ЗЛП можно поставить в соответствие двойственную задачу. Запишем ЭММ прямой и двойственной к ней задачи.

Прямая задача Целевая функция Ограничения Двойственная задача Целевая функция Ограничения

1) если целевая функция исходной задачи формулируется на максимум, то целевая функция двойственной задачи – на минимум (и, наоборот), при этом в двойственной задаче на максимум все неравенства в функциональных ограничениях имеют вид ( ), в задаче на минимум вид ( ); 2) матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи и аналогичная матрица А T в двойственной задаче получаются друг из друга транспонированием; 3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи числу переменных в исходной; 4) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи коэффициенты при неизвестных в целевой функции исходной; 5) каждому ограничению одной задачи соответствует переменная другой задачи, номер переменной совпадает с номером ограничения. При этом ограничению, записанному в виде неравенства, соответствует переменная, связанная условием неотрицательности. Если функциональное ограничение исходной задачи является равенством, то соответствующая переменная двойственной; задачи может принимать как положительные, так и отрицательные значения.

х 1 – число женских костюмов x 2 – число мужских костюмов Максимизировать целевую функцию f ( x ) = 10 х х 2 Ограничения задачи имеют вид: х 1 + 3, 5 х 2 350, 2 х 1 + 0, 5 х х 1 + х 2 150, х 2 60, х 1 0. y 1 – двойственная оценка ресурса шерсть y 2 - двойственная оценка ресурса лавсан y 3 - двойственная оценка ресурса труд y 4 - двойственная оценка мужских костюмов Минимизировать целевую функцию Ограничения задачи имеют вид:,

Теорема 1. (Основная). Если одна из двойственных задач имеет opt решение, то и другая имеет opt, причем экстремальные значения целевых функций совпадают при opt решении. max f ( x ) = min g ( y ), или f ( x 0 ) = g ( y 0 ). Если одна из двойственных задач неразрешима, то неразрешима и другая.

Пусть вектор Х=(x 1, x 2,..., x n ) – допустимое решение прямой задачи, а вектор Y = (y 1, y 2,..., y m ) – допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соответственно прямой и двойственной задач, необходимо и достаточно, чтобы выполнялись следующие соотношения:

Значения переменных y i o в opt решении двойственной задачи представляет собой оценки влияния свободных членов b i системы ограничений неравенств прямой задачи на величину целевой функции Δ f(x o ) = y i o Δ b i. Переменные y i в двойственных задачах называют двойственными оценками, они отражают ценность единицы ресурса.

Теорема 1. Предприятию безразлично, производить ли продукцию по opt плану X o =(x 1 o, x 2 o,… x n o ) и получить max прибыль, либо продать ресурсы по opt ценам Y o =(y 1 o, y 2 o,… y n o ) и возместить от продажи равные ей минимальные затраты на ресурсы. Теорема 3. а) Величина двойственных оценок показывает на сколько возросло бы max значение целевой функции, если бы объем данного ресурса на одну единицу.

б) Двойственные оценки отражают сравнительную дефицитность различных видов ресурсов. Чем выше объективно обусловленные оценки y i, тем более дефицитен ресурс; в) двойственные оценки служат инструментом определения выгодности выпуска новых изделий: Затраты Стоимость Если Δ i 0, то изделие выпускать невыгодно, и если Δ i 0, то выпуск изделия выгоден. Теорема 3. Двойственные оценки показывают, на сколько ед. изменится макс. прибыль при изменении запаса i -го ресурса на одну единицу.