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

       7.5. Анализ устойчивости двойственных оценок                 дут к суммарному изменению прибыли ΔZ max , которое может
    Продолжим рассмотрение пары двойственных ЗЛП.                   быть вычислено по формуле:
    Предположим, что исходная задача имеет невырожденные                                                m
опорные планы и хотя бы один из них является оптимальным.                                   ΔZ max ≈ ∑ y i* ⋅ Δbi .                  (7.15)
Очевидно, изменение правых частей ограничений исходной зада-                                           i =1
чи приводит, вообще говоря, к изменению максимального значе-            Эта формула имеет место лишь тогда, когда при изменении
ния целевой функции Zmax, т.е. Zmax можно рассматривать как
                                                                    величин bi значения переменных y i* в оптимальном плане соот-
функцию свободных членов системы линейных уравнений:
                       Z max (b1 , b2 , K , bm ).                   ветствующей двойственной задачи остаются неизменными, по-
                                                                    этому представляет интерес определить такие интервалы измене-
    Теорема (об оценках). В оптимальном плане двойст-               ния каждого из свободных членов bi, в которых оптимальный
венной задачи значение переменной y i* численно равно ча-           план двойственной задачи не меняется. Такие интервалы назы-
стной производной функции Z max (b1 , b2 , K , bm ) по соот-        вают интервалами устойчивости двойственных оценок.
ветствующему аргументу bi , т.е.                                        Нижнюю и верхнюю границы интервала (bi − Δbiн , bi + Δbiв )
                        дZ max                                      устойчивости двойственных оценок определяют по формулам:
                               = y*i   (i = 1,m).          (7.14)
                         дbi                                                            ⎧ − ∞ , если ∀d ji ≤ 0,
    Из теоремы об оценках вытекает, что при малом изменении                             ⎪      ⎧⎪ x*j ⎫⎪
                                                                                 Δbiн = ⎨                                            (7.16)
                                                                                        ⎪ j ⎨⎪ d ⎬⎪, для d ji > 0 ,
правой части i-го ограничения в системе ограничений ЗЛП мак-                              min
симальное значение целевой функции изменяется на величину                               ⎩       ⎩ ji ⎭
                             i
                          ΔZ max ≈ yi* ⋅ Δbi .                                                 ⎧         ⎧⎪ x*j ⎫⎪
                                      i
                                          ≈ y i* .                                             ⎪ max               , для d ji < 0,
    В частности, при Δbi = 1 имеем ΔZ max                                              Δbiв = ⎨ j ⎨⎪⎩ d ji ⎬⎪⎭                       (7.17)
    Применительно к задаче оптимального использования ресур-                                   ⎪ + ∞,
                                                                                               ⎩               если ∀d ji ≥ 0
сов можно сказать, что двойственная оценка y i* i-го ресурса
                                                                        Здесь d ij – элементы матрицы D=B–1, обратной к матрице В
приближенно равна приращению оптимальной прибыли,
                                                                    базиса оптимального плана, а j принимает значения индексов
возникающему за счет увеличения объема i-го ресурса на
                                                                    базисных переменных x *j оптимального плана.
единицу.
                                                                         Пример 7.9. Для задачи оптимального использования ресур-
    Из теоремы также вытекает, что если изменится объем каж-        сов (см. пример 7.1), математическая модель которой имеет вид:
дого ресурса на величину Δbi (i = 1, m) , то эти изменения приве-



                                 117                                                                           118