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

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

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

     Связь исходной и двойственной задач состоит в том, что коэффициенты Cj функции цели исходной задачи являются свободными членами системы ограничений двойственной задачи, свободные члены Bi системы ограничений исходной задачи служат коэффициентами функции цели двойственной задачи, а матрица коэффициентов системы ограничений двойственной задачи является транспонированной матрицей коэффициентов системы ограничений исходной задачи. Решение двойственной задачи может быть получено из решения исходной и наоборот.

     В качестве примера рассмотрим задачу использования ресурсов. Предприятие имеет т видов ресурсов в количестве bi (i = 1, 2, ., m) единиц, из которых производится n видов продукций. Для производства 1 ед. i-й продукции расходуется aij ед. t-гo ресурса, а ее стоимость составляет Cj ед. Составить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Обозначим через xj(j =1,2, ., n) количество ед. j-й продукций, Тогда исходную задачу сформулируем так.

Найти вектор Х =(x1, x2, …, xn), который удовлетворяет  ограничениям

a11x1 + a12x2 + … + a1nxn £ b1,

a21x1 + a22x2 + … + a2nxn £ b2, xj ³ 0 (j =1,2, ., n)

…………………………………

am1x1 + am2x2 + … + amnxn £ bm,

и доставляет максимальное значение линейной функции 

Z = C1x1 + C2x2 + … + Cnxn,

     Оценим  ресурсы, необходимые для изготовления продукции. За единицу стоимости ресурсов примем единицу стоимости выпускаемой продукции. Обозначим через уi (j =1,2, ., m) стоимость единицы i-го ресурса. Тогда стоимость всех затраченных ресурсов, идущих на изготовление единицы j-й продукции, равна . Стоимость затраченных ресурсов не может быть меньше стоимости окончательного продукта, поэтому должно выполняться неравенство ³ Cj, j =1,2, ., n. Стоимость всех имеющихся ресурсов выразится величиной . Итак, двойственную задачу можно сформулировать следующим образом.

Найти вектор Y =(y1, y2, …, yn), который удовлетворяет  ограничениям

a11y1 + a12y2 + … + am1ym £ C1,

a12y1 + a22y2 + … + am2ym £ C2, yj ³ 0 (i =1,2, ., m)

…………………………………

a1ny1 + a2ny2 + … + amnym £ Cm,

и доставляет минимальное значение линейной функции

f = b1y1 + b2y2 + … + bmym.

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

     Исходная  задача. Сколько и  какой продукции xj (j =1,2, ., n) необходимо произвести, чтобы при заданных стоимостях Cj (j =1,2, ., n) единицы продукции и размерах имеющихся ресурсов bi (i =1,2, ., n) максимизировать выпуск продукции в стоимостном выражении.

     Двойственная  задача. Какова должна быть цена единицы каждого из ресурсов, чтобы при заданных количествах ресурсов bi и величинах стоимости единицы продукции Ci минимизироватьобщую стоимость затрат?

     Переменные  уi называются оценками или учетными, неявными ценами.

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

2. Несимметричные двойственные  задачи. Теоремы двойственности.

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

     Исходная  задача. Найти матрицу-столбец X = (x1, x2, …, xn), которая удовлетворяет ограничениям

(1.1) AX = A0, Х ³ 0

и минимизирует линейную функцию Z = СХ.

     Двойственная  задача. Найти матрицу-строку Y = (y1, y2, …, ym), которая удовлетворяет ограничениям

(1.2) YA £  С 

и максимизирует  линейную функцию f = YA0

     В обеих задачах C = (c1, c2, …, cn) - матрица-строка, A0 = (b1, b2, …, bm) — матрица-столбец, А = (aij) — матрица коэффициентов системы ограничений. Связь между оптимальными планами пары двойственных задач устанавливает следующая теорема.

     Теорема двойственности. Если из пары двойственных задач одна обладает оптимальным планом, то и другая имеет решение, причем для экстремальных значений линейных функций выполняется соотношение min Z = max f. Если линейная функция одной из задач не ограничена, то другая не имеет решения.

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

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

(1)

(2)

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

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

 
 
 
 
 
 
 
 
 
 

3. Симметричные двойственные  задачи

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

     Исходная  задача. Найти матрицу-столбец Х = (x1, x2, …, xn), которая удовлетворяет  системе ограничений  АХ>А0, Х>0

и минимизирует линейную функцию Z = СХ.

     Двойственная  задача. Найти матрицу-строку Y = (y1, y2, …, yn), которая удовлетворяет системе  ограничений YA £ C, Y ³ 0 и максимизирует линейную функцию f = YA0.

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

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

     Исходная  задача. Найти минимальное значение линейной функции Z = x1 + 2x2 + 3x3 при ограничениях

2x1 + 2x2 - x3 ³ 2,

x1 - x2 - 4x3 £ -3, xi ³ 0 (i=1,2,3)

x1 + x2 - 2x3 ³ 6,

2x1 + x2 - 2x3 ³ 3,  

     Для того чтобы записать двойственную задачу -  второе неравенство следует умножить на -1.

Двойственная  задача. Найти максимум линейной функции f = 2y1+ 3y2 + 6y3 + 3y4 при ограничениях

2y1 - y2 + y3 + 2y4 £ 1,

2y1 + y2 + y3 + y4 ³ 2,

-y1+ 4y2 - 2y3 - 2y4 ³ 3,

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

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

Оптимальный план двойственной задачи Y* = (0; 1/2; 3/2; 0), fmax = 21/2.

     Оптимальный план исходной задачи находим, используя  оценки (m + 1)-й строки последней итерации, стоящие в столбцах A5, A6, A7 : x1 = 3/2 + 0 = 3/2; x2 = 9/2 + 0 = 9/2; x3 = 0 + 0 = 0. При оптимальном плане исходной задачи X* = (3/2; 9/2; 0) линейная функция достигает наименьшего значения: Zmin =21/2.  
 
 
 
 
 
 
 
 
 

4. Виды математических  моделей двойственных  задач. 

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

Несимметричные  задачи .

(1) Исходная  задача. Двойственная задача .

Zmin = CX; fmax = YA0;

AX = A0; YA £ С.

X ³ 0.

(2) Исходная  задача. Двойственная задача .

Zmax = CX; fmin = YA0;

AX = A0; YA ³ С.

X ³ 0.

Симметричные  задачи .

(3) Исходная  задача Двойственная задача.

Zmin = CX; fmax = YA0;

AX ³ A0; YA £ С.

X ³ 0. Y ³ 0.

(4) Исходная  задача. Двойственная задача.

Zmax = CX; fmin = YA0;

AX £ A0; YA ³ С.

X ³ 0. Y ³ 0.

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

Найти минимальное значение линейной функции  Z = 2x1 + x2 + 5x3 при ограничениях

x1 – x2 – x3 £ 4,

x1 – 5x2 + x3 ³ 5, xj ³ 0 (j = 1, 2, 3).

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