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

          Уопт = С*А = (1   -1  0) ×       0  -1/3   1/3        = (0  2/3  1/3).

                                                           1     1       1

 

    Таким образом, решение двойственной задачи следующее:

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

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

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

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

    L (x) = 3x1  + x2   + 3x3  + x4   → min              S(y) = 9y1  + 6y2   → mах

    x1 - 2x2 + 3x3  - x4   = 9 │ y1                                   2y1 + y2 ≤ 3 │x1

    x1 + x2 - 6x3  - x4   = 6   │ y2                                                           -2 y1 + y2 ≤ 1  │x2                                                                                                           

    xj ≥0 , j = 1,4.                                                     3y1 - 6y2  ≤ 3 │x3

                                                                               -2y1 - y2  ≤ 1 │x4

                                                                                     y1,  y2  - произвольные по знаку.

    Решив двойственную задачу графическим методом, получим

    Yопт = (1/2, 2), при этом S(y)max = 33/2.

    По 1-й теореме двойственности L(x)min = S(y)mах = 33/2.

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

    2*1/2 +2 ≤ 3,  3 = 3,

    -2 *1/2 + 2 ≤ 1, 1 = 1,

    3*1/2 – 6*2 ≤ 3, -21/2 < 3 → х3 = 0,

    -2*1/2 – 2 ≤ 1,-3 < 1 → х4 = 0.

    Так как х3 = х4 = 0 , то система ограничений исходной задачи примет вид

    2x1 - 2x2   = 9,

    x1 +x2 =6.

    Решая данную систему, получим

Хопт = (21/4, 3/4, 0,0), при этом     L(x)min = 33/2.

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

     Пусть решение исходной задачи

                       Xопт = (21/4,3/4,0,0), при этом L(x)min = 33/2.

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

    Уопт = С*А ,

    где

    С = (3,1),        А =  2   -2   ,                 А = 1/4   1/2  ,

                                    1    1                           -1/4   1/2 

    Yопт = (3  1) * 1/4   1/2   = (1/2  2).

                           -1/4  1/2

Таким образом, Yопт = (1/2, 2), при этом S(y)mах = 33/2. 

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

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

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

    L (x) = x1  - 6x2   - x3     → mах                     S(y) = 3y1  + 4y2   → min

    x1 + 3x2 + 3x3     = 3 │ y1                                 y1 + 2y2 ≥ 1   │x1

    2x1 + 3x3 ≤4         │ y2                                                         3y1 ≥ -6            │x2                                                                                                           

    xj ≥0 , j = 1,3.                                              3y1 + 3y2 ≥ -1 │x3

                                                                                                                           y1 – произвольная по знаку, y2 ≥0.

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

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

По 1-й  теореме двойственности

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

Так как  х1 > 0,  х3   > 0, то по 2-й теореме двойственности первое и третье ограничения двойственной задачи выполняются в виде равенств:

          y1 + 2y2  = 1,

    3y1 + 3y2 = -1,  

    Откуда  y1 = -5/3,  y2  = 4/3, т.е. Yопт = (-5/3, 4/3). 

    4. Экономический анализ  задач с использованием  теории двойственности

    Рассмотрим  задачу оптимального использования  ресурсов, запишем ее математическую модель

    L(x) = ∑ сjxj → mах

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

    ∑  aijxj ≤ bi │y,

    xj ≥0, i = 1,m,    j = 1,n.

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

    S(y) = ∑ biyi → min

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

    ∑  aijуj ≥ cj , уi ≥ 0, i = 1,m.