Постановка задачи линейного программирования Основы теории двойственности Экономическое содержание теории двойственности

или, в матричной записи,

где — матрица коэффициентов. Вектор называется вектором коэффициентов линейной формы, — вектором ограничений.
Стандартная задача важна ввиду наличия большого числа прикладных моделей, сводящихся наиболее естественным образом к этому классу задач ЛП.
Каноническая задача ЛП.

или, в матричной записи,

Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи.
Общая задача ЛП.
В этой задачи часть ограничений носит характер неравенств, а часть является уравнениями. Кроме того, не на все переменные наложено условие неотрицательности:

Здесь. Ясно, что стандартная задача получается как частный случай общей при ; каноническая — при .
Все три перечисленные задачи эквивалентны в том смысле, что каждую из них можно простыми преобразованиями привести к любой из двух остальных.
При изучении задач ЛП сложилась определенная терминалогия. Линейная форма , подлежащая максимизации (или минимизации) , называется целевой функцией. Вектор , удовлетворяющий всем ограничениям задачи ЛП, называется допустимым вектором, или планом. Задача ЛП, для которой существуют допустимые векторы, называется допустимой задачей. Допустимый вектор , доставляющий наибольшее значение целевой функции по сравнению с любым другим допустимым вектором , т.е. , называется решением задачи, или оптимальным планом. Максимальное значение целевой функции называется значением задачи.
Двойственная задача линейного программирования.
Рассмотрим задачу ЛП
(1)
или, в матричной записи,
(2)
Задачей, двойственной к (1) (двойственной задачей), называется задача ЛП от переменных вида
(3)
или, в матричной записи,
(4)
где .
Правила построения задачи (3) по форме записи задачи (1) таковы: в задаче (3) переменных столько же, сколько строк в матрице задачи (1). Матрица ограничений в (3) — транспортированная матрица . Вектор правой части ограничений в (3) служит вектором коэффициентов максимизируемой линейной форме в (1), при этом знаки неравенств меняются на равенство. Наоборот, в качестве целевой функции в (3) выступает линейная форма, коэффициентами которой задаются вектором правой части ограничений задачи (1), при этом максимизация меняется на минимизацию. На двойственные переменные накладывается условие неотрицательности. Задача (1), в отличии от двойственной задачи (3) называется прямой.
Теорема (первая теорема двойственности). Если одна из пары сопряженных задач имеет оптимальный план, то и вторая задача также имеет решение, причем для оптимальных решений значения целевых функций обеих задач совпадают, т.е.
.
Если целевая функция одной из задач неограниченная, то сопряженная задача также не имеет решения.
Первая теорема двойственности дает возможность в процессе решения одной задачи вместе с тем находить план второй.
Экономическое содержание первой теоремы двойственности. Максимальную прибыль (Fmax) предприятие получает при условии производства продукции согласно оптимальному плану , однако такую самую сумму денег
( ) оно может иметь, реализовав ресурсы по оптимальным ценам . При условиях использования других планов на основании основной неравенства теории двойственности можно утверждать, что прибыли от реализации продукции всегда меньшие, чем затраты на ее производство.
Теорема (вторая теорема двойственности для симметричных задач). Для того, чтобы планы X* и Y* соответствующих сопряженных задач были оптимальными, необходимо и достаточно, чтобы выполнялись условия дополняющей нежесткости:
(3.11)
. (3.12)
Очевиднее взаимосвязь между оптимальными планами прямой и двойственной задач устанавливает следствие второй теоремы двойственности.
Следствие. Если в результате подстановки оптимального плана одной из задач (прямой или двойственной) в систему ограничений этой задачи i-тое ограничение выполняется как строгая неравенство, то соответствующая i-тая компонента оптимального плана сопряженной задачи равняется нулю.
Если i-тая компонента оптимального плана одной из задач положительна, то соответствующее i-тое ограничение сопряженной задачи выполняется для оптимального плана как уравнение.
Экономическое содержание второй теоремы двойственности относительно оптимального плана Х* прямой задачи. Если для изготовления всей продукции в объеме, который определяется оптимальным планом Х*, затраты одного i-того ресурса строго меньши его общего объем , то соответствующая оценка такого ресурса (компонента оптимального плана двойственной задачи) будет равнять нулю, т.е. такой ресурс при данных условиях для производства не является «ценным».
Если же затраты ресурса равняются его имеющемуся объему , т.е. его использовано полностью, то он есть «ценным» для производства, и его оценка будет строго больше нуля.
Экономическое толкование второй теоремы двойственности относительно оптимального плана Y* двойственной задачи: в случае, если некоторое j-тое ограничение выполняется как неравенство, т.е. все затраты на производство единицы j-го вида продукции превышают его цену сj, производство такого вида продукции есть нецелесообразным, и в оптимальном плане прямой задачи объем такой продукции равняется нулю.
Если затраты на производство j-го вида продукции равняются цене единицы продукции , то ее необходимо изготовлять в объеме, который определяется оптимальным планом прямой задачи .
Существование двойственных переменных делает возможным сопоставление затрат на производство и цен на продукцию, на основании чего обосновывается вывод о целесообразности или нецелесообразности производства каждого вида продукции. Кроме этого, значение двойственной оценки характеризует изменение значения целевой функции, которая обусловлена малыми изменениями свободного члена соответствующего ограничения. Данное утверждение формулируется в виде такой теоремы.
Теорема (третья теорема двойственности). Компоненты оптимального плана двойственной задачи равняются значениям частичных производных от целевой функции по соответствующим аргументами , или
(3.13)
Экономическое содержание третьей теоремы двойственности. Двойственные оценки являются уникальным инструментом, который дает возможность сопоставлять несравнимые вещи. Очевидно, что невозможным есть простое сопоставление величин, которые имеют разные единицы измерения. Если взять в качестве примера производственную задачу, то интересными есть вопросы: как будет изменяться значение целевой функции (может измеряться в денежных единицах) за изменения объемов разных ресурсов (могут измеряться в тоннах, м2, люд./ч, га и т.п.).
Используя третью теорему двойственности, можно легко определить влияние на смену значения целевой функции увеличения или уменьшение объемов отдельных ресурсов: числовые значения двойственных оценок показывают, на какую величину изменяется целевая функция при изменении объема соответствующего данной оценке ресурса ….