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

       ТЕОРЕМА 3. Значения переменных уi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов системы ограничений исходной задачи на оптимальное значение ее целевой функции, т.е. уi = ðLi / ðbi/

       Примем  ðLi  ≈ ∆ Li, ðbi  ≈ ∆bi, тогда ∆ Li  ≈ уi * ∆bi.

       Для задачи оптимального использования  сырья это уравнение показывает, что при изменении i – ресурса оптимальный доход является линейной функцией его приращения, причем коэффициентом служит уi – i –я компонента оптимального решения двойственной задачи.

       Если  уi  мало, то значительному увеличению i –го ресурса будет соответствовать небольшое увеличение оптимального дохода и ценность ресурса невелика.

       Если  уi = 0, то при увеличении i –го ресурса оптимальный доход остается неизменным и ценность этого ресурса равна нулю. В самом деле, сырье, запасы которого превышают потребности в нем, не представляют ценности для производства и его оценку можно принять за нуль.

       Если  уi велико, то незначительному увеличению  i –го ресурса будет соответствовать существенное увеличение оптимального дохода и ценность ресурса высока. Уменьшение ресурса ведет к существенному сокращению выпуска продукции.

       Переменную  уi считают некоторой характеристикой ценности i –го ресурса. В частности, при увеличении i –го ресурса на единицу оптимальный доход возрастает на уi, что позволяет рассматривать уi как «условную цену», оценку единицы i –го ресурса , объективно обусловленную оценку.

       Так как уi представляет частную производную от оптимального дохода по i – му  ресурсу, то уi характеризует скорость изменения оптимального дохода при изменении i –го ресурса.

       С помощью уi можно определить степень влияния ограничений на значение целевой функции. Предельные значения (нижняя и верхняя границы) ограничений ресурсов, для которых остаются неизменными, определяются по формулам:

       bi = min (xj / dij )  ,    bi = max (xj / dij )  ,

       где xj – значение переменной в оптимальном решении; dij – элементы матрицы ( dij )  = А , обратной к матрице базиса оптимального решения, для которой А = ( аij )m×n . 
 

5. Стратегическое планирование  выпуска изделий  с учетом имеющихся  ресурсов

      Фирма выпускает три вида изделий, располагая при этом сырьем 4 типов : А, Б, В, Г  соответственно в количествах 18, 16, 8 и 6 т. Нормы затрат каждого типа сырья на единицу изделия первого вида составляют соответственно 1, 2, 1, 0, второго вида – 2, 1, 1, 1 и третьего вида  1, 1, 0, 1. Прибыль от реализации единицы изделия первого вида = 3 усл. ед., второго =4 усл. ед., третьего = 2 усл. ед.

      Требуется:

      1) составить план производства  трех видов, максимизирующих прибыль;

      2) определить дефицитность сырья;

      3) установить размеры максимальной прибыли при изменении сырья А на 6 т, Б – на 3 т, В – на 2 т, Г – на 2 т. Оценить раздельное влияние этих изменений и суммарное их влияние на прибыль;

      4) оценить целесообразность введения  в план производства фирмы  нового вида изделий (четвертого), нормы затрат на единицу которого соответственно равны 1, 2, 2, 0, а прибыль составляет 15 усл. ед.

      Решение. 1. Обозначим через Х = ( х1, х2, х3) план производства изделий трех видов, тогда математическая модель задачи примет вид

      L (x) = 3x1  + 4x2  + 2x3    → max    

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

    x1 + 2x2  + x3 ≤ 18,

    2x1 + x2 + x3 ≤ 16 ,

                                                     x1 + x2 ≤ 8,

                                                      x2 + x3 ≤ 6,

    xj ≥0 , j = 1,3.

    Решаем  задачу симплексным методом, при этом последняя таблица будет иметь вид

 

    Из  таблицы следует

    Хопт = (5,3,3,4,0,0,0), при этом L(x)max = 33 усл. ед.

    Согласно  теоремам двойственности

    Уопт = (0,1/2,2,3/2,0,0,0), при этом S(y)min = 33 усл. ед.

    2. Наиболее дефицитным является  сырье типа В, для которого  двойственная оценка у3 = 2. Менее дефицитным является сырье вида Б, для которого у2 = ½. Совсем не дефицитным является сырье А (у1 =0).

    Для определения интервала устойчивости оценок найдем обратную матрицу для  матрицы коэффициентов при базисных переменных в оптимальном решении  системы ограничений. Базисными переменными в оптимальном решении являются х1, х2, х3, х4. Матрица коэффициентов при этих переменных в системе ограничений примет вид

                        1  2  1  1

    А = (аij)   =      2  1  1  0   .

                        1  1  0  0

                        0  1  1  0 

    Тогда обратная матрица для матрицы А следующая:

           0  1/2  0   -1/2

    А =  0  -1/2  1  1/2   .

        0   1/2  -1   1/2

       1    0    -1    -1

    Найдем  интервал устойчивости  оценок по видам  сырья:

    ∆b1 = min (xоптj / d1j ) = 3 / (1/2) = 6,

    ∆b1 = min (xоптj / d1j ) = 4 / (-1/2) = 8.

    Интервал  устойчивости оценок по отношению к  первому ограничению:

    (b1 - b1 ; b1 + b1) = (18 – 6; 18 + 8) = (12; 26).

    Аналогично  определим интервалы устойчивости оценок по отношению к ограничениям остальных видов сырья:

    ∆b2 = min ( 3/1; 4/(1/2) ) = 3,                    ∆b2 = │3/ (-1/2) │=6,

    ∆b3 = min ( 3/(1/2); 4/(1/2) ) = 6,                ∆b3 = │3/ (-1) │=3,

    ∆b4 =5/1 = 5,                                               ∆b4 = max│3/ (-1); 4/(-1) │=3.

    Интервалы устойчивости оценок по отношению ко второму ограничению:

    (16 – 3; 16 + 6) = (13;22),

    к третьему ограничению:

    (8 – 6; 8 + 3) = (2;11),

    к четвертому ограничению:

    (6 – 5; 6 + 3) = (1;9).

    3. Изменения сырья согласно условиям  задачи на +6, -3, +2, +2 т приводят к ограничению запаса сырья до 24, 13, 10, 8 т соответственно. Поскольку эти изменения находятся в пределах устойчивости оценок, на что указывают интервалы, то раздельное их влияние на прибыль определяется по формуле

    Li = yоптi * bi,

    тогда

    L1 max = yопт1 * b1 = 0*6 = 0,

    L2 max = yопт2 * b2 = 1/2*(-3) = -3/2,

    L 3max = yопт3 * b3 = 2*2 = 4 ,

    L 4max = yопт4 * b4 = 3/2*2 = 3.