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

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

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

    ТЕОРЕМА 1. Если одна из двойственных задач имеет  оптимальное решение, то другая также  имеет оптимальное решение, причем для любых оптимальных решений X и Y выполняется равенство

    L(x)max = S(y)min.

    Если  одна из двойственных задач неразрешима  ввиду того, что 

    L(x)max → ∞ (или S(y)min →  - ∞), то другая задача не имеет допустимых решений.

    ТЕОРЕМА 2. Для оптимальности допустимых решений X и Y пары двойственных задач необходимо и достаточно, чтобы они удовлетворяли системе уравнений

    Xопт j ( ∑aijyопт i - cj ) = 0,

    yопт i ( ∑aijxопт j - bi ) = 0.

    Теоремы позволяют определить оптимальное  решение одной из пары задач по решению другой. 

    3. Решение двойственных задач

    Решение симметричных задач

    Рассмотрим  решение задач с использованием теорем двойственности.

    Исходная  задача                      Двойственная задача

    L (x) = x1  - x2   → max              S(y) = 2y1  + 2y2 + 5y3  → min

    при ограничениях:                        при ограничениях:

    -2x1 + x2 ≤ 2 │ y1  -2y1 + y2 + y3 ≥ 1 │x1

    x1 - 2x2 ≤ 2 │ y2                                  y1 – 2y2 + y3 ≥ -1 │x2

    x1 + x2 ≤ 5   │ y3                                     yi ≥0,  I = 1,3.

    x1 ≥0 , x2 ≥0.

    Решим исходную задачу графическим методом, получим Хопт = (4,1), при этом L(x)max = 3.

    На  основании 1-й теоремы двойственности

    L(x)max = S(y)min = 3.

    Так как x1, x2 > 0, то по 2-й теореме двойственности систему ограничений можно записать в виде равенств:

    -2y1 + y2 + y3 = 1,

    y1 – 2y2 + y3 = -1.

    Подставим Хопт в систему ограничений исходной задачи:

    -2*4 + 1 ≤ 2,           9 < 2 ═> у1 = 0,

    4 – 2*1 ≤ 2,           2 = 2 ═> у2 > 0,

    4 + 1 ≤ 5,                5 = 5 ═> у3 > 0.

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

    y2 + y3 = 1,

    – 2y2 + y3 = -1.

    Откуда  Yопт = (0, 2/3, 1/3), при этом S(y)min = 3.

    Пусть дано решение двойственной задачи Yопт = (0, 2/3, 1/3), S(y)min = 3, найдем решение исходной.

    По 1-й теореме двойственности L(x)max = S(y)min = 3. Так как y2 , y3 > 0, то по 2-й теореме двойственности второе и третье неравенства исходной задачи обращаются в равенства:

    x1 - 2x2 = 2 ,

    x1 + x2 = 5.

    Откуда  Хопт = (4,1), при этом     L(x)max = 3.

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

    S(y) = 2y1  + 2y2 +  5y3  → mах

    При ограничениях:

    -2y1 + y2 + y3 – у4 = 1,

    y1 – 2y2 + y3 – у5 = 1,  

 

    yj ≥ 0, i = 1,5.

    Из  таблицы следует, что Yопт = (0, 2/3, 1/3), S(y)min = 3.

    На  основании 1-й теоремы двойственности получаем

    L(x)max = S(y)min = 3.

    Решение другой задачи найдем по соответствию между переменными:

 

    Значение  хj определяем по последней симплексной таблице в строке  ∆i  в соответствующем столбце, причем значения хj берем по модулю:

    Х1 → У4,    Х1 = │∆4│= │-4│=4,

    Х2 → У5,    Х2 = │∆5│= │-1│=1.

    Таким образом, решение исходной задачи:

    Хопт = (4,1), при этом     L(x)max = 3.

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

    Уопт = С*А ,

    где С – матрица-строка коэффициентов при базисных переменных целевой функции в оптимальном решении исходной задачи; А  - обратная матрица для матрицы А, являющейся матрицей коэффициентов базисных переменных системы ограничений исходной задачи в оптимальности решении.

    Решим симплексным методом исходную задачу вида

    L (x) = x1  - x2   → max

    при ограничениях:                       

    -2x1 + x2 + x3 = 2,

    x1 - 2x2 + x4 =2,

    x1 + x2 + x5 = 5,

    x1 ≥0 , j = 1,5.

    Из  таблицы (см. ниже) следует, что Хопт = (4,1), L(x)max = 3. матрицы записываются в виде

    С = (1  -1  0)1×3 ,                         -2  1    1

                                              А  =   1  -2   0           ,

                                                        1   1    0   3×3

    тогда

                               0   1/3     2/3

                      А =   0  -1/3   1/3        ,

                                1     1       1 

                                                          0   1/3     2/3