Математическое программирование (линейное программирование). Киселева Э.В - 54 стр.

    Мы доказали теорему для пары двойственных задач, задан-                   Согласно условию 1, если в оптимальной системе оценок ка-
ных в стандартной форме.                                                  кой-то ресурс i получит отличную от нуля оценку уi* > 0 , то в со-
    Теорема остается справедливой для любой пары двойствен-
                                                                          ответствии с оптимальным планом производства прямой задачи
ных задач. Запишем условия дополняющей нежесткости в коор-
                                                                          этот ресурс, являясь дефицитным, будет израсходован полно-
динатной форме:
            n
                                                                          стью:
       yi* (∑ aij x*j − bi ) = 0    (i = 1,m) ,                                                            n

           j =1
                                                                 (7.12)
                                                                                                           ∑a x
                                                                                                           j =1
                                                                                                                   ij
                                                                                                                         *
                                                                                                                         j   = bi .
            m
       x*j (∑ aij y*i − c j ) = 0   ( j = 1,n).                  (7.13)
                                                                              Если какой-то i-й ресурс расходуется не полностью (избыто-
           i =1
                                                                          чен), т.е.
                                                                                                           n
    Из этих условий следует:
    1. Если какое-либо (i-е) ограничение прямой задачи в ее оп-                                            ∑a x
                                                                                                           j =1
                                                                                                                   ij
                                                                                                                         *
                                                                                                                         j   < bi ,
тимальном плане Х* обращается в строгое неравенство, то соот-
ветствующая (i-я) компонента уi* оптимального плана Y* двойст-            то его оценка равна нулю, уi* = 0.
венной задачи должна равняться нулю.                                           Отсюда следует, что оценки оптимального плана – это
    2. Если же какая-либо (j-я) компонента xj*оптимального пла-           мера дефицитности ресурсов.
    *
на Х прямой задачи положительна, то соответствующее (j-е) ог-                  Согласно условию 2, если некоторый продукт j входит в оп-
раничение в двойственной задаче ее оптимальным планом долж-               тимальный план производства (xj*>0), то при оптимальной систе-
но обратиться в равенство.                                                ме оценок двойственной задачи затраты ресурсов на его изготов-
    То есть:                                                              ление совпадают со стоимостью этого продукта, т.е.
                           n                                                                         m
                  если ∑ aij x*j < bi , то        y*i = 0;                                                 *
                                                                                                    ∑ aij y j = c j .
                          j =1                                                                      i =1
                                              m                               Если затраты ресурсов на выпуск какого-либо продукта j
                  если x*j > 0 ,          то ∑ aij yi* = c j .            превышают его стоимость,
                                              i =1
    Аналогично:                                                                                          ∑a       ij   y*j > c j ,
                           m
                   если ∑ aij y*j > c j , то x*j = 0;                     то этот продукт не производится, т.е. xj*=0.
                          i =1                                                 Отсюда вывод:
                                                  n
                                                                               Дефицитный ресурс (полностью использованный в произ-
                   если y*j > 0,          то ∑ aij x*j = bi .             водстве) имеет положительную оценку, а ресурс недефицитный
                                              j =1
                                                                          (избыточный) имеет нулевую оценку.
    Дадим экономическую интерпретацию условиям дополняю-                       Для иллюстрации применения второй теоремы двойственно-
щей нежесткости.                                                          сти при рассмотрении пары двойственных задач рассмотрим сле-
                                                                          дующие примеры.

                                    109                                                                                      110