58. Геометрическая интерпретация двойственной задачи.

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

59. Нахождение решения двойственной задачи.

. Рассмотрим пару двойственных задач – основную задачу линейного программирования (1) и двойственную к ней задачу (2)

Предположим, что с помощью симплексного метода найден оптимальный план X^* задачи (1) и этот план определяется базисом, образованным векторами .

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

Таким образом, если найти симплексным методом оптимальный план задачи (1), то, используя последнюю симплекс–таблицу, можно определить ии с помощью соотношениянайти оптимальный план двойственной задачи (2).

В том случае, когда среди векторов , составленных из коэффициентов при неизвестных в системе уравнений (1), имеетсят единичных, указанную матрицу образуют числа первыхт строк последней симплекс–таблицы, стоящие в столбцах данных векторов. Тогда нет необходимости определять оптимальный план двойственной задачи умножением на, поскольку компоненты этого плана совпадают с соответствующими элементами(m+1)–й строки столбцов единичных векторов, если данный коэффициент , и равны сумме соответствующего элемента этой строки иесли

Сказанное выше имеет место и для симметричной пары двойственных задач. При этом так как система ограничений исходной задачи содержит неравенства вида “”, то компоненты оптимального плана двойственной задачи совпадают с соответствующими числами (m+1)–й строки последней симплекс–таблицы решения исходной задачи. Указанные числа стоят в столбцах векторов, соответствующих дополнительным переменным

60. Экономическая интерпретация двойственных задач.

Для любых допустимых планов ипрямой и двойственной ЗЛП справедливо неравенство,т.е.– основное неравенство теории двойственности.Теорема (критерий оптимальности Канторовича). Если для некоторых допустимых планов ипары двойственных задач выполняется неравенство, тоиявляются оптимальными планами соответствующих задач.Теорема (малая теорема двойственности). Для существования оптимального плана любой из пары двойств-ых задач необходимо и достаточно существование допустимого плана для каждой из них. Теорема. Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремальные значения целевых функций равны: . Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива. Экономическое содержание первой теоремы двойственности состоит в следующем: если задача определения оптимального плана, максимизирующего выпуск продукции, разрешима, то разрешима и задача определения оценок ресурсов. Причем цена продукции, полученной при реализации оптимального плана, совпадает с суммарной оценкой ресурсов. Совпадение значений целевых функций для соответствующих планов пары двойственных задач достаточно для того, чтобы эти планы были оптимальными. Это значит, что план производства и вектор оценок ресурсов являются оптимальными тогда и только тогда, когда цена произведенной продукции и суммарная оценка ресурсов совпадают.

Теорема (о дополняющей нежесткости). Для того, чтобы планы ипары двойственных задач были оптимальны, необходимо и достаточно выполнение условий:(1)(2)      Условия (1), (2) называются условиями дополняющей нежесткости. Из них следует: если какое-либо ограничение одной из задач ее оптимальным планом обращается в строгое неравенство, то соответствующая компонента оптимального плана двойственной задачи должна равняться нулю; если же какая-либо компонента оптимального плана одной из задач положительна, то соответствующее ограничение в двойственной задаче ее оптимальным планом должно обращаться в строгое равенство.Экономически это означает, что если по некоторому оптимальному плану производства расходi-го ресурса строго меньше его запаса , то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок егоi-я компонента строго больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс (полностью используемый по оптимальному плану производства) имеет положительную оценку, а ресурс избыточный (используемый не полностью) имеет нулевую оценку.      Теорема (об оценках). Двойственные оценки показывают приращение функции цели, вызванное малым изменением свободного члена соответствующего ограничения задачи математического программирования.