Двойственность в линейном программировании кратко

Обновлено: 02.07.2024

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

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

Рассмотрим прямую задачу линейного программирования и двойственную задачу.

Прямая задача.
Максимизировать функцию

Двойственная задача.
Минимизировать функцию

Эти задачи обладают следующими свойствами:

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

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

Мы обусловимся называть их просто взаимно-двойственными задачами.

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

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

Приводят все неравенства системы ограничений исходной задачи к неравенствам одного смысла(то есть с одним и тем же знаком): если в исходной задаче ищется максимум функции цели (линейной формы) - они записываются со знаком "меньше или равно", если же минимум - со знаком "больше или равно". Для этого неравенства, в которых это требование не выполняется, умножают на минус единицу.
Выписывают матрицу A коэффициентов при переменных исходной задачи, полученых после преобразований, описанных в предыдущем пункте, и составляют матрицу A', транспонированную относительно матрицы A.
Составляют систему ограничений двойственной задачи, взяв в качестве коэффициентов при переменных элементы матрицы A', а в качестве свободных членов - коэффициенты при переменных в функци цели исходной задачи и записывают неравенства противоположного смысла (то есть меняют знак) по сравнению с неравенствами, полученными в пункте 1.
Составляют функцию цели (линейную форму) двойственной задачи, приняв за коэффициенты при переменных свободные члены системы ограничений исходной задачи, полученные в пункте 1.
Указывают, что необходимо найти при решении двойственной задачи, а именно: минимум функции цели, если в исходной задаче ищется максимум, и максимум, если в исходной задаче ищется минимум.
Записывают условие неотрицательности переменных двойственной задачи.

Пример 1. Составить задачу, двойственную следующей: найти максимум функции при ограничениях

Решение. Третье неравенство системы исходной задачи не удовлетворяет пункту 1 правил составления двойственной задачи. Поэтому умножим его на минус единицу:

Для облегчения составления двойственной задачи лучше пользоваться расширенной матрицей B, в которую наряду с коэффициентами при переменных системы ограничений исходной задачи запишем свободные члены и коэффициенты при переменных в функции цели, выделив для этой цели дополнительные столбец (отделён чертой) и строку (выделена красным цветом). Матрицу B транспонируем и, используя транспонированную матрицу B', составляем задачу, двойственную исходной. Матрицы B и B' имеют вид

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

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

Свободные члены в прямой задаче - коэффициенты функции цели в двойственной задаче.
Коэффициенты функции цели в прямой задаче - свободные члены в двойственной задаче.
Расширенная матрица в прямой задаче - транспонированная расширенная матрица в двойственной задаче.
j-й неизвестный в прямой задаче неотрицательный - j-е неравенство в двойственной задаче со знаком "больше или равно".
j-й неизвестный в прямой задаче без ограничения знака - j-е ограничение в двойственной задаче в виде уравнения.
j-й неизвестный в прямой задаче неположительный - j-е неравенство в двойственной задаче со знаком "меньше или равно".
i-е неравенство в прямой задаче со знаком "меньше или равно" - i-е неизвестный в двойственной задаче неотрицательный.
i-е ограничение в прямой задаче в виде уравнения - i-й неизвестный в двойственной задаче без ограничения знака.
i-е неравенство в прямой задаче со знаком "больше или равно" - i-й неизвестный в двойственной задаче неположительный.

Пример 2. Составить задачу, двойственную следующей: найти минимум функции при ограничениях

Решение. Как видим, прямая задача записана в общей форме. Это будем учитывать при расстановке знаков в условиях двойственной задачи. А пока, как и в предыдущем примере, произведём универсальное действие - составим матрицу B прямой задачи и транспонированную матрицу B' двойственной задачи:

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

Основные теоремы двойственности

Теория двойственности в линейном программировании строится на двух основных теоремах.

Теорема 1. Для прямой и двойственной задач в силе одно и только одно из следующих утверждений. 1. Если одна из задач линейного программирования имеет конечный оптимум, то и двойственная к ней задача также имеет конечный оптимум, причём оптимальные значения линейных форм обеих задач совпадают, т. е. F max = Z min или F min = Z max . 2. Если линейная форма одной из двойственных задач не ограничена, то условия другой задачи противоречивы. 3. Обе задачи не имеют решения, так как системы ограничений противоречивы.

Прежде чем сформулировать следующую теорему, установим соответствия между переменными в исходной и двойственной задачах. Приготовьтесь: последует игра формул, которую с первого раза не каждый поймёт, но после ознакомления с примером 2 должны понять все.

При решении симплекс-методом исходной задачи для сведения системы неравенств к эквивалентной ей системе уравнений нужно ввести m добавочных неотрицательных переменных (по числу неравенств в системе ограничений) x n+1 , x n+2 , . x n+i , . x n+m , где i = 1, 2, . m означает номер неравенства, в которое была введена добавочная переменная x n+i .

Система ограничений двойственной задачи состоит из n неравенств, содержащих m переменных. Если решать эту задачу симплекс-методом, то следует ввести n добавочных неотрицательных переменных y m+1 , y m+2 , . y m+j , . y m+n , где j = 1, 2, . n означает номер неравенства системы ограничений двойственной задачи, в которое была введена добавочная переменная y m+j .

Всё вышесказанное было приведено для того, чтобы установить следующее соответствие между переменными в исходной и двойственной задачах линейного программирования:

То есть, основные переменные исходной задачи, в порядке их следования, соответствуют добавочным переменным двойственной задачи, тоже в порядке их следования. В свою очередь добавочные переменные исходной задачи, в порядке их следования, соответствуют основным переменным двойственной задачи, также в порядке их следования.

Иными словами, каждой первоначальной переменной исходной задачи x j ( j = 1, 2, . n ) ставится в соответствие добавочная переменная y m+j , введённая в j-е неравенство двойственной задачи, а каждой добавочной переменной x n+i исходной задачи ( i = 1, 2, . m ), введённой в i-е неравенство исходной задачи, - первоначальная переменная y i двойственной задачи.

Всё вышесказанное, как уже было отмечено, станет более понятным из примера 2, который будет вскоре после Теоремы 2.

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

Из теорем 1 и 2 следует, что если решить одну из взаимно двойственных задач линейного программирования, то есть найти её оптимальное решение и оптимум функции цели, то можно записать оптимальное решение и оптимум функции цели другой задачи. Теперь пример, который поможет разложить всё вышеизложенное по полочкам.

Пример 3. На основании решений прямой и двойственной задач линейного программирования из примера 1 убедиться в справедливости теорем 1 и 2.

В примере 1 была дана исходная задача: найти максимум функции при ограничениях

Мы составили двойственную ей задачу: найти минимум функции при ограничениях

Для решения прямой задачи симплекс-методом система ограничений-неравенств сводится к системе уравнений путём введения добавочных неотрицательных переменных x 3 , x 4 , x 5 , x 6 :

Читатель может проверить, решив задачу симплекс-методом, что она имеет следующие решения:

а максимум целевой функции F max = 13 ,

при этом сама целевая функция выражается как

Система ограничений двойственной задачи сводится к системе уравнений путём введения добавочных переменных y 5 , y 6 :

Решение двойственной задачи симплекс-методом даёт следующий ответ:

а минимум целевой функции Z min = 13 ,

при этом сама целевая функция выражается как

Решив двойственную задачу, убеждаемся в справедливости первой части теоремы 1: двойственная задача тоже имеет конечный оптимум, причём Z min = F max = 13 .

Убедимся, что справедливо также и утверждение теоремы 2. Для этого запишем переменные прямой и двойственной задачи, соблюдая их соответствие:

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

Функцию цели, полученную на последнем шаге решения двойственной задачи, выразим через все переменные этой задачи:

Рассматривая коэффициенты при переменных y j в этой функции цели и учитывая их соответствие коэффициентам при переменных x i , получим решение (4; 1; 0; 5; 4; 0) , совпадающее с решением прямой задачи.

Замечание. Решив прямую задачу, можно сразу получить решение двойственной задачи линейного программирования. Если выразить функцию цели, полученную при решении прямой задачи, через все переменные задачи, то получим

На основании теоремы 2, учитывая соответствие между переменными в прямой и двойственной задачах и взяв абсолютную величину коэффициентов при переменных, найдём оптимальное решение двойственной задачи (2/3; 0; 0; 7/3; 0; 0) . При этом Z min = F max = 13 .

Пример 4. Убедиться в том, что системы ограничений прямой задачи

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

Решение. Вычтем из второго уравнения системы ограничений прямой задачи первое уравнение той же системы. Получим . Это уравнение не имеет решения, так как . Таким образом, система ограничений прямой задачи несовместна.

Сложим первые два неравенства системы ограничений двойственной задачи. Получим , что невозможно. Таким образом, системы ограничений и прямой, и двойственной задачи несовместны. Согласно части 3 теоремы 1 двойственности, обе задачи не имеют решений.

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

Посмотрим ещё раз на прямую задачу линейного программирования и двойственную задачу рядом.

Прямая задача.
Максимизировать функцию

Двойственная задача.
Минимизировать функцию

В этих задачах a - расходы сырья определённого вида на производство одного вида продукции, b запасы сырья определённого вида, c - прибыль от реализации единицы продукции определённого вида. В прямой задаче x - количество единиц выпускаемой продукции определённого вида. А в двойственной задаче b - цены сырья соответствующего вида. А целевая функция Z - общие затраты на приобретение сырья, которые требуется минимизировать.

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

Максимальную прибыль определяет решение прямой задачи. Путём же решения двойственной задачи линейного программирования находятся цены y, точнее говоря, объективно обусловленные оценки. Они являются компонентами оптимального решения двойственной задачи линейного программирования.

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

Рассмотрим задачу о планируемом выпуске продукции.

Содержательная постановка прямой задачи: составить такой план выпуска продукции X = (х₁,х₂ . х_n), при котором прибыль (выручка) от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов.

Общие правила составления двойственной задачи:

Прямая	Двойственная
Целевая функция (max)	Правая часть ограничений
Правая часть ограничений	Целевая функция (min)
A - матрица ограничений	A T – матрица ограничений
i -ое ограничение: ≤ 0, (≥ 0)	Переменная y_i ≥ 0, (≤ 0)
i -ое ограничение: = 0	Переменная y_i≠ 0
Переменная x_j ≥ 0 (≤ 0)	j -ое ограничение: ≤ 0 (≥ 0)
Переменная x_j ≠ 0	j -ое ограничение: = 0

max → min

Прямая	Двойственная
Целевая функция (min)	Правая часть ограничений
Правая часть ограничений	Целевая функция (max)
A - матрица ограничений	A T – матрица ограничений
i -ое ограничение: ≥ 0, (≤ 0)	Переменная y_i ≥ 0, (≤ 0)
i -ое ограничение: = 0	Переменная y_i≠ 0
Переменная x_j ≥ 0 (≤ 0)	j -ое ограничение: ≤ 0 (≥ 0)
Переменная x_j ≠ 0	j -ое ограничение: = 0

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

Заметим, что строки матрицы задачи I являются столбцами матрицы задачи II. Поэтому коэффициенты при переменных y_i в задаче II - это, соответственно, коэффициенты i -го неравенства в задаче I.
Полученная модель и есть экономико-математическая модель задачи, двойственной к прямой задаче.

Теоремы двойственности

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

Первая теорема двойственности .

Если одна из пары двойственных задач I и II разрешима, то разрешима и другая, причем значения целевых функций на оптимальных планах совпадают, F(x*) = G(y*), где х *, у * - оптимальные решения задач I и II

Вторая теорема двойственности .

Планы х * и у * оптимальны в задачах I и II тогда и только тогда, когда при подстановке их в систему ограничений задач I и II соответственно хотя бы одно из любой пары сопряженных неравенств обращается в равенство.
Это основная теорема двойственности. Другими словами, если х * и у * - допустимые решения прямой и двойственной задач и если c T x*=b T y*, то х * и у * – оптимальные решения пары двойственных задач.

Третья теорема двойственности . Значения переменных y_i в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов b_i системы ограничений - неравенств прямой задачи на величину целевой функции этой задачи:
Δf(x) = b_iy_i

Решая ЗЛП симплексным методом, мы одновременно решаем двойственную ЗЛП. Значения переменных двойственной задачи y_i, в оптимальном плане называют объективно обусловленными, или двойственными оценками. В прикладных задачах двойственные оценки y_i часто называются скрытыми, теневыми ценами или маргинальными оценками ресурсов.

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

Итак, имеем исходную задачу I и ее оптимальное решение х * = (0, 40, 0, 100) и F(х*) = 700.

Применяя теорему двойственности, получим решение двойственной задачи по известному решению исходной задачи.
Найдем решение двойственной задачи II у* = (у₁, у₂, у₃), не прибегая к симплекс-методу, а воспользовавшись второй теоремой двойственности и известным оптимальным планом х *.

Рассмотрим выполнение неравенств задачи I при подстановке х* в систему ограничений.

5x₁+0,4x₂+2x₃+0,5x₄≤400	50+0,440+20 + 0,5100 = 66 0	Второе ограничение в двойственной задаче будет равенством 0,4y₁ + 5y₂ = 5
x₃ ≥ 0	x₃ = 0	Третье ограничение в двойственной задаче будет неравенством 2y₁ + y₂ + y₃ ≥ 4
x₄ ≥ 0	x₄ = 100 > 0	Четвертое ограничение в двойственной задаче будет равенством 0,5y₁ + y₂ + y₃ = 5

Поскольку 1, 5, 7 неравенства строгие (имеют знак " "), то соответствующие им неравенства в задаче II из пары сопряженных обязаны обратиться в равенства. имеем:
y₁=0
0.4y₁+5y₂=5
0.5y₁+y₂+y₃=5 или
y₁=0, y₂=1, y₃=4
т.е. у* = (0, 1, 4) - оптимальное решение.

Заметим, что действительно G(y*) = 400y₁+ 300y₂+ 100y₃= 400 · 0 + 300 · 1 + 100 · 4 = 700 = F(x*).

Итак, в силу второй теоремы двойственности мы очень быстро нашли оптимальное решение задачи II, пользуясь условием обращения в равенство хотя бы одного из пары сопряженных неравенств в системах ограничений двойственных задач.
Между переменными исходной задачи и переменными двойственной существует глубокая связь. А именно: после приведения обеих задач I и II к каноническому виду основные и дополнительные переменные задач соответствуют друг другу следующим образом:

Установив такую связь, можно заметить, что, решив задачу I симплекс-методом и получив последнюю симплекс-таблицу (табл.), мы фактически решим и задачу II.
Запишем таблицу, учитывая соответствие между переменными х _i и y_j .

у₄	у₂	у₆	у₃
базисные	-х₁	-х₆	-х₃	-х₇	свободные
у₁	х₅	334
у₅	х₂	40
у₇	х₄	100
-F	1	1	1	4	700

В силу соответствия и II теоремы двойственности переменные у₁, у₅, у₇ обязаны равняться 0, т.к. х₅, х₂, х₄>0 строго. А переменные у ₄, у ₂, у ₆, у ₃ принимают значения из индексной строки 1, 1, 1, 4 соответственно, т.к. им соответствующие переменные х₁, х₆, х₃, х₇ = 0, как свободные. Итак, из последней таблицы задачи II, не проводя даже никаких вычислений и пользуясь лишь соответствием переменных:

Мы научились по решению исходной задачи находить решение двойственной. Это оказалось возможно благодаря глубокой связи между переменными х_i и y_j. Осталось разобраться, каково экономическое содержание этих взаимосвязей.

Теорема равновесия

Задача 2
Составить двойственную задачу к задаче 1. Найти ее решение по теореме равновесия.
3x₁+x₂≥12
x₁+2x₂≥14
4x₁+11x₂≥68

Теорема равновесия. Пусть X*=(x₁*. x_n*) и Y*=(y₁*. y_n*) - допустимые планы пары двойственных задач в симметричной форме. Эти планы являются оптимальными тогда и только тогда, когда выполняются следующие условия дополняющей нежесткости:

Теорема 4 позволяет определить оптимальное решение одной из пары двойственных задач по решению другой. Если ограничение одной задачи при подстановке оптимального решения обращается в строгое неравенство, то соответствующая двойственная переменная в оптимальном решении двойственной задачи равна 0. Если в оптимальном плане одной задачи какая-нибудь переменная положительна, то соответствующее ей ограничение двойственной задачи является уравнением.
Дадим экономическую интерпретацию условиям дополняющей нежесткости. Если в оптимальном решении какое-нибудь сырье имеет отличную от 0 оценку, то оно будет израсходовано полностью (ресурс является дефицитным). Если сырье расходуется не полностью (находится в избытке), то его оценка равна 0. Таким образом, получаем, что двойственные оценки – это мера дефицитности сырья. Оценка показывает, на сколько возрастет значение целевой функции при увеличении запаса соответствующего сырья на 1 ед. Если некоторый вид продукции входит в план производства, то затраты на его производство совпадают со стоимостью произведенной продукции. Если затраты на производство какого-нибудь вида продукции больше стоимости продукции, то продукция не производится.
В случае если одна из пары двойственных задач содержит две переменных, ее можно решить графически, а, затем, найти решение двойственной задачи, используя Теоремы 3 и 4. При этом могут возникнуть 3 случая: обе задачи имеют допустимые решения, допустимые решения имеет только одна задача, обе задачи не имеют допустимых решений.

Пример 2
Составить двойственную задачу и найти ее решение по теореме равновесия
x₂-2x₃+2x₄-2x₅≤4
-2x₁-2x₂+2x₃+2x₄+x₅≥2
x_i≥0, i= 1,5
Z=10x₁-9x₂-19x₃-13x₄-11x₅ → max, если известно решение исходной задачи: Zmax=(3;4;0;0;0).
Построим двойственную задачу. Согласуем знаки неравенств с целью исходной задачи.

Пример 3
Составить двойственную задачу к задаче из примера раздела 1.5 и найти ее решение по теореме равновесия
x₁+3x₂≥12
5x₁+4x₂≥31
2x₁+3x₂≥18
x₁, x₂≥0
Z(x₁,x₂)=12000x₁+16000x₂→min
В разделе 1.5 было найдено решение исходной задачи средствами MS Excel: Zmin(3;4)=100000
Составим двойственную задачу. Знаки неравенств уже согласованы с целью задачи.

Каждой ЗЛП можно сопоставить точно одну двойственную ей ЗЛП. Связь между ними задается следующим образом.

При этом векторы переменных X и U и соответственно векторы правых частей и коэффициентов целевой функции разложены на два вектора, а матрица коэффициентов состоит из четырех подматриц.

В частности, в первой задаче по знаку ограничено ровно столько переменных, сколько есть неравен ств ср еди условий по второй задаче. Если рассмотреть задачу, двойственную к двойственной задаче, то снова придем к исходной задаче.

Рассмотрим двойственную задачу на примере.

D > Пример 6.6. Исходная задача. Изготовление продукции двух видов требует использования четырех видов сырья . Запас сырья каждого вида ограничен (табл. 6.4).

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

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

Сформулируем задачу. Пусть . — число единиц продукции соответственно видов, Среди решений системы

ограничений

необходимо выбрать такое соотношение объемов выпуска продукции при котором целевая функция будет иметь максимальное значение.

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

Сравнение двух построенных математических моделей позволяет сделать следующие выводы: 1) исходная задача имеет 2 переменные и 4 ограничения (ограничения не считаются), и в ней требуется отыскать максимальное значение целевой функции; двойственная задача имеет 4 переменные и 2 ограничения, и в ней требуется отыскать минимальное значение целевой функции.

Рассмотрим вопрос, представляющий основной практический интерес к проблеме двойственности: как связаны между собой оптимальные решения двойственной пары задач?

Проследим за этой связью на нашем примере.

Решим графически исходную задачу. Из рис. 6.2 видно, что целевая функция достигает максимального значения в точке С с координатами откуда

Двойственную задачу будем решать симплексным методом. Введем дополнительные переменные (базисные) и приведем математическую модель двойственной задачи к виду общей задачи линейного программирования:

Составимсимплексные таблицы (табл. 6.5).

Оптимальное базисное решение:

Итак, мы видим, что в рассмотренном случае минимальное значение целевой функции в точности равно максимальному значению Э то верно и в общем случае. Отсюда в теории

линейного программирования доказываются теоремы.

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

Теорема 2. (теорема равновесия). Если в оптимальном плане исходной задачи значение какой-либо переменной строго больше нуля, то соответствующее ограничение двойственной задачи при подстановке в него оптимального плана становится равенством.

Поясним содержание теоремы равновесия на примере 6.6.

В оптимальном плане мы получили переменные Переменной соответствует ограничение двойственной задачи, а переменной — ограничение П одставим в эти ограничения вместо соответствующие значения оптимального плана двойственной задачи:

В результате этой подстановки получим, что ограничения двойственной задачи, соответствующие ненулевым значениям выполняются как равенства.

Сформулированные теоремы двойственности находят широкое применение в экономической практике. Они позволяют, например, решение ЗЛП, которое по той или иной причине вызывает затруднение при реализации, свести к решению двойственной задачи.

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

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

Пусть в качестве исходной дана задача:

Задача линейного программирования, двойственная задаче (2.4), будет иметь вид:

Можно сформулировать правила получения двойственной задачи из задачи исходной.

1. Если в исходной задаче ищется максимум целевой функции, то в двойственной ей - минимум.

2. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений другой задачи.

3. В исходной ЗЛП все функциональные ограничения - неравенства вида “≤”, а в задаче, двойственной ей, - неравенства вида “≥”.

4. Коэффициенты при переменных в системах ограничений взаимно двойственных задач описываются матрицами, транспонированными относительно друг друга.

5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой.

6. Условие неотрицательности переменных сохраняется в обеих задачах.

Связь между оптимальными планами взаимно двойственных задач устанавливают теоремы двойственности.

Теорема 1. Если одна из двойственных задач имеет конечный оптимум, то другая также имеет конечный оптимум, причем экстремальные значения целевых функций совпадают:

Если целевая функция одной из двойственных задач не ограничена, то условия другой задачи противоречивы.

Теорема 2 (о дополняющей нежесткости). Для того чтобы план и план являлись оптимальными решениями, соответственно, задач (2.5) и (2.6) необходимо и достаточно, чтобы выполнялись следующие соотношения:

Таким образом, если компонент оптимального плана больше нуля, то при подстановке в соответствующее ограничение двойственной задачи оптимального плана это ограничение обращается в верное равенство, и наоборот.

Теорема об оценках. Значения переменных в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов b_i в системе ограничений прямой задачи на величину целевой функции :

На свойствах двойственных оценок базируется экономико-математический анализ распределения ресурсов. В пределах устойчивости двойственных оценок имеют место свойства, рассмотренные ниже.

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

Формулировка прямой (исходной) задачи:

Получим двойственную задачу.

В результате решения получим следующие оптимальные планы:

Легко убедиться, что при подстановке оптимальных планов в целевые функции задач оба получаемых значения равны 64.

Перейдем к рассмотрению свойств двойственных оценок.

Свойство 1. Оценки как мера дефицитности ресурсов. Двойственные оценки отражают сравнительную дефицитность факторов производства. Чем выше величина оценки , тем выше дефицитность i-го ресурса. Факторы, получившие нулевые оценки, не являются дефицитными и не ограничивают производство.

В нашем примере нулевую оценку получил третий ресурс ( = 0), поэтому он не является дефицитным, т.е., с точки зрения задачи, фонд рабочего времени на участке С не ограничивает производство. Напротив, первый (участок А) и второй (участок В) ресурсы являются дефицитными, причем ограничивают производство в одинаковой степени ( = = 1/3).

Последнее утверждение легко подтвердить, подставив и в ограничения исходной задачи:

Вернемся к нашему примеру. Пусть предприятие планирует к выпуску новый вид изделий: бейсбольные биты. Для производства одной биты необходимо затратить 3 часа работы на участке А, 4 часа работы на участке В и 1 час работы на участке С. Прибыль, получаемая от продажи одной биты, составляет $3. Выгодно ли предприятию выпускать новую продукцию?

Для ответа на вопрос рассчитаем Δ_j по формуле (2.9):

Δ_j = 3ּ + 4ּ + 1ּ - 3 = 3ּ1/3 + 4ּ1/3 + 1ּ0 - 3 = -2/3,

Δ_j 0 и > 0, только второе и четвертое ограничения двойственной задачи обращаются в верное равенство при подстановке в них оптимального плана (такой вывод следует из соотношений (2.7)). Учитывая, что = 0, можем записать систему из двух уравнений с двумя неизвестными:

2y₂ = 2, y₂ + y₃ = 4.

Решая систему, получим: = 1, = 3.

Полностью решение двойственной задачи запишется так:

Пусть в качестве исходной дана задача:

Задача линейного программирования, двойственная задаче (2.4), будет иметь вид:

Можно сформулировать правила получения двойственной задачи из задачи исходной.

1. Если в исходной задаче ищется максимум целевой функции, то в двойственной ей - минимум.

5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой.

6. Условие неотрицательности переменных сохраняется в обеих задачах.

Связь между оптимальными планами взаимно двойственных задач устанавливают теоремы двойственности.

Если целевая функция одной из двойственных задач не ограничена, то условия другой задачи противоречивы.

Формулировка прямой (исходной) задачи:

Получим двойственную задачу.

В результате решения получим следующие оптимальные планы:

Перейдем к рассмотрению свойств двойственных оценок.

Последнее утверждение легко подтвердить, подставив и в ограничения исходной задачи:

Для ответа на вопрос рассчитаем Δ_j по формуле (2.9):

Δ_j = 3ּ + 4ּ + 1ּ - 3 = 3ּ1/3 + 4ּ1/3 + 1ּ0 - 3 = -2/3,

16. Некоторые замечания к общей схеме формирования двойственности

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

(см. (14.2)). На формирование двойственности в силу отображения можно смотреть как на универсальную схему, распространяющуюся на оптимизационные задачи и из других разделов математики (математическая экономика, оптимальное управление, приближение функций и др.). Схема работает, естественно, и для задач ЛП. Проиллюстрируем это на задаче . Запишем для нее функцию Лагранжа , . С помощью элементарных преобразований ее можно переписать в виде . Тогда двойственная к L задача L * по схеме (16.2) запишется так:

что эквивалентно задаче

что и требовалось.

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

Запишем для ее функцию Лагранжа

и ее градиент . Двойственная к задача запишется по правилу (16.2) в форме:

или путем замены :

Итак, в качестве двойственной к мы получим задачу (16.5), обозначенную . Последняя является ничем иным как задачей, реализующей метод квадратичных штрафных функций, примененным к задаче (16.3) со штрафной константой . Обозначим задачу (16.5) символом . Нами показано

На самом деле реализуется схема:

В нижней части этой схемы переход соответствует проверенному соотношению (16.6). Верен и обратный переход , однако его обоснование требует специального подхода, базирующегося на искусственном преобразовании задачи (16.5). Это преобразование состоит в замене c - A T u = w и перезаписи задачи в форме

Функцией Лагранжа для этой задачи (с учетом в ней ограничения ) будет

где x - вектор множителей Лагранжа, соответствующий векторному уравнению w = A T u - c ; - аналогичный вектор для . Двойственной к (16.5) (следовательно, и к (16.7)) будет задача

С учетом (16.9) преобразуем функцию Лагранжа:

Таким образом, применяя к (16.5) схему формирования двойственной задачи, мы получим задачу

а это - задача . Следовательно, мы проверили соотношение

Наравне со схемой 6 можно выписать ей симметричную схему:

в соответствии с которой справедливо соотношение

Задачи и связаны между собой классической теоремой двойственности (вытекает из обоснования схемы 6 и теоремы 13.1).

П р и м е ч а н и е. Естественно, это утверждение верно и для пары задач , .

Выпишем тройку задач:

Отметим связи между ними (при разрешимости L ): 1) (теорема двойственности); 2) , ; 3) при достаточно малом 0$ --> оптимальный вектор задачи является минимальным по норме оптимальным вектором задачи L * .

Следствие. Пусть L разрешима. Тогда при достаточно малом 0:\ \ \mathrm\, L_<<\,\mathrm>> - \mathrm\, L = \mbox\, \mbox<$\parallel$>\bar u \mbox<$\parallel$>$ --> .

Заметим, что для задачи L в качестве чаще записывают задачу: , где l j ( x ) - левые части системы , R j > 0, . В этом случае оценка 2) и соотношение из следствия принимают вид:

- при достаточно большом .

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

Читайте также: