Конечные бескоалиционные игры и равновесия. Матвеев В.А. - 71 стр.

§9. Двойственная задача линейного
программирования
     Вместе с задачей линейного программирования изучается
тесно с ней связанная двойственная или сопряжённая задача.
Исходную задачу часто называют прямой задачей линейного
программирования. Использование теории двойственности
позволяет удвоить полезные свойства задач математического
программирования. Особенно важна эта теория для матричных
игр. Матричная игра в определённом смысле эквивалентна паре
из стандартной и двойственной ей задачи линейного
программирования.
     Пусть рассматривается стандартная прямая задача
линейного программирования (8.1) – (8.3).
             f ( x) = c1 x1 + c 2 x 2 + ... + c m x m → max;
            ai1 x1 + ai 2 x 2 + ... + aim x m ≤ bi , i = 1,...n,
                         x j ≥ 0, j = 1,..., m.
Двойственной ей является задача
           f d ( y ) = b1 y1 + b2 y 2 + ... + bn y n → min;        (9.1)
          a1i y1 + a 2 i y 2 + ... + a ni y n ≥ ci , i = 1,...m,   (9.2)
                          y j ≥ 0, j = 1,..., n.                   (9.3)
     Особенно удобно запоминать прямую и двойственную
задачи линейного программирования, записанные в матричной
форме. Задачу (8.1) – (8.3) можно представить
                         C mT ⋅ X m → max,
                          Am×n ⋅ X m ≤ Bn ,
                              X m ≥ 0 m.                           (9.4)
    Аналогично для задачи (9.1) – (9.3) верна запись


                                                                           71