2.7. ИССЛЕДОВАНИЕ МОДЕЛЕЙ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ  НА ЧУВСТВИТЕЛЬНОСТЬ

Теория двойственности позволяет анализировать модели ЛП на чувствительность.

Рассмотрим обычную задачу ЛП в виде

                           максимизировать                      (2.7.1)

при условиях

                                                         (2.7.2)

x_j³0.

Напомним ее экономическую интерпретацию. Целевая функция L(x) -это доход от реализации плана производства x; a_ij  -интенсивность расходования i-го ресурса при j-м способе производства; bi- имеющийся уровень i-го ресурса.

1. Варьирование ограниченных ресурсов. Предположим, что величины ресурсов b=|| b_i || варьируются. Тогда возникают вопросы: при каких вариациях правых частей ограничений найденный оптимальный план x₀ не изменяется; как эти вариации влияют на функцию максимального дохода L_max? Ответ на эти вопросы дает анализ соответствующей задачи ЛП на чувствительность.

Пусть ограничение b_i получают некоторые вариации Db_i, что приводит к вариациям плана x_0, x₀₌ x₀(b+Db) и функции L_max (x₀(b₀+Db)). Предположим, эти вариации Db таковы, что план x₀(b+Db)  остается допустимым ( т.е. удовлетворяет условию неотрицательности). Найдем отношения приращения

DL_max(b)= L_max (x₀(b₀+Db))- L_max (x₀(b)) к Db.

Имеем

                                                            (2.7.3)

где b рассматривается как варьируемый параметр.

Вспомним, что в соответствии с основной теоремой двойственности

                                   ,                    (2.7.4)

и, подставляя (2.7.4) в (2.7.3), получим

                                       .                       (2.7.5)

Таким образом, оптимальные значения двойственных переменных  определяют вклад каждого ресурса в доход L_max при оптимальном решении x₀. Эта величина численно равна дополнительному доходу при увеличении i-го ресурса b_i на единицу при условии, что ресурсы используются оптимальным образом.

Итак, величины  служат показателями важности соответствующих ресурсов для системы. Чем большее значение  при некотором i, тем существеннее вклад i-го ресурса в функцию максимального дохода L_max и тем выгоднеее его увеличение. Если для некоторого =0, то i-й ресурс не является существенным ограничением для системы.

Заметим, что этот вывод хорошо согласуется с результатами теоремы 2.6 двойственности, которая связывает величины с ограничениями прямой задачи.

Обозначим через A_x матрицу оптимального базиса задачи ЛП при векторе ресурсов b. Очевидно соответствующее оптимальное решение

x_опт= A^-1_x b.

Предположим, что мы изменили вектор ресурсов b=|| b_i ||  на  b_н=b+ Db  и хотим узнать, как это повлияет на оптимальное решение. Для этого найдем новое соответствующее базисное решение

x_н = А^-1_хb_н = А^-1_х(b+Db).

Если все компоненты x_iн ³ 0, то это решение x_н = [x_iн] оптимально (т.е. оптимальный базис не изменился). В противном случае нужно произвести поиск нового решения, для этого можно применить двойственный симплекс-метод, начиная с текущего базисного решения x_н.

2. Варьирование целевой функции. Теперь рассмотрим случай, когда варьируются коэффициенты {c_j}, j= 1,2,…,n... Попытаемся выяснить условия, при которых найденный ранее оптимальный план останется оптимальным при таких вариациях.

Пусть вариациям  подвергнется коэффициент . Обозначим через J_б,  J_неб  множество  индексов базисных и небазисных векторов в оптимальном плане x₀ соответственно.

Найдем значения оценок  после вариации c_r для двух случаев:

1) rÎ J_неб , тогда  для всех j¹r ;

                              для j=r ;                  (2.7.6)

       2) rÎ J_б,

          jÎJ_неб                   (2.7.7)

Очевидно, что для сохранения оптимальности прежнего плана при вариациях коэффициента c_r необходимо и достаточно  сохранение знаков оценок  для всех небазисных переменных. Поэтому из условий ³0 в соответствии с формулами (2.7.6) и (2.7.7) можно определить допустимые вариации коэффициента , при которых сохраняется прежнее оптимальное решение.

До сих пор мы рассматривали вариации лишь одного коэффициента целевой функции. Этот же подход можно применить, когда варьируются одновременно несколько коэффициентов c_i.

В таком случае получим соотношения, аналогичные (2.7.7), в которых оценки будут функциями уже нескольких параметров (d₁, d₂,…,d_r)...

Решая совместно систему неравенств вида (c₁, c₂,…,c_r)³0,jÎJ_небы находим условия для вариаций , при которых прежний оптимальный базис сохраняется.

Эта задача  относится к классу задач параметрического программирования [12].

3.  Варьирование элементов матрицы ограничений A. Рассмотрим лишь случай вариации компонентов небазисных векторов A_j=[a_ij],  i=1,2,...,m, поскольку исследование вариаций компонент базисных векторов A_i довольно сложное, легче  заново решить задачу с новыми условиями.

Итак, пусть небазисный вектор A_j=[a_mj] изменился. Нужно выяснить, останется ли оптимальным текущий базис. Для этого полезно применить теорию двойственности. Пусть оптимальный базис прямой задачи A_x, а соответствующие оптимальные значения двойственных переменных . Как известно, условие оптимальности  ³0, " jÎ J_неб Вместе с тем в соответствии с (2.6.11), . Значит если ,то прежний оптимальный базис сохраняется.

4.  Добавление еще одного способа производства. Предположим, что первоначально задача имеет вид

                                      максимизировать                               (2.7.8)

при условиях

                                                 ,                                     (2.7.9)

x_j³0.

Предположим, что найден оптимальный базис {A_i}, iÎ J_б и соответствующие оптимальные решения прямой  и двойственной  задач.

Пусть прибавляется еще один (n+1)-й способ производства, которому отвечает вектор технологических затрат A_n+1=[a_{i n+1}] и коэффициент целевой функции c_n+1. Тогда будем иметь следующую задачу:

                           максимизировать                        (2.7.10)

при условиях 

                                     ,                            (2.7.11)

                                            x_j³0,  j=1, 2,…, n+1.                            (2.7.12)         

Нужно определить, изменится ли при этом прежнее оптимальное решение и при каком значении коэффициента c_n+1 выпуск (n+1)-го продукта будет рентабельным (то есть ). 

Чтобы оптимальное решение после ввода вектора A_n+1 не изменилось , необходимо, чтобы вектор A_n+1 и переменная x_n+1  оставались небазисными, т.е., чтобы D_n+1³0. На основании теории двойственности получим 

 .

Если  , то прежний оптимальный план не изменится после включения выпуска (n+1)-го вида продукции.

Если же , то выпуск (n+1)-го вида продукции становится рентабельным, и прежний оптимальный план изменяется.

 Пример 2.10.

 Предприятие выпускает изделия двух видов, для изготовления которых используются ресурсы двух типов. Пусть прибыль от продажи изделий составляет соответственно c₁=2 и c₂=3, объем ресурсов равняются b₁=32, b₂=24 соответственно. Нормы затрат ресурсов на единицу выпуска задаются такой матрицей: 

1. Нужно найти оптимальный план выпуска, который максимизирует суммарный доход и исследовать чувствительность целевой функции к вариации ограниченных ресурсов, т.е. как изменится суммарный доход при увеличении на единицу любого из видов ресурсов.

2. Пусть первый  ресурс b₁ увеличился до 35, а второй уменьшился до 20. Как изменится при этом оптимальное решение, останется ли оптимальным прежний базис? 

3. Пусть вводится дополнительное ограничение на выпуск первого продукта x₁³ 6. Определить новый оптимальный план. 

4. Пусть предприятие может дополнительно выпускать третий вид продукции, для которого c₃=4, а нормы затрат ресурсов составляют a₁₃=3; a₂₃=2. Найти оптимальный план с учетом этого условия и определить, при каком значении c₃ производство третьего вида изделий будет рентабельным. 

Решение. Математическая модель задачи: 

max (2 x₁+3 x₂)

при условиях 

3 x₁+2 x₂ £ 32;

1 x₁+2 x₂ £ 24;

x₁³0,    x₂³0.

Решим эту задачу симплекс-методом и через две итерации найдем оптимальный план (табл.2.27). 

Получим=4; =10; max (2 x₁+3 x₂)=38.

Матрица  образована небазисными векторами A₄, A₅ в табл.2.27. 

                                                                                                                            Таблица2.27

Оптимальные значения двойственных переменных находим в индексной строке табл.2.27: ; .  Анализируя значения , , видим, что при увеличении на единицу первого ресурса мы получим приращение ц.ф.   а при увеличении на единицу второго ресурса . Итак, второй ресурс оказывается более важным для системы и его повышение выгоднее.

Пусть первый ресурс увеличен до 35 единиц, а второй уменьшен до 20 единиц, тогда новый вектор =[ 35; 20 ]^T. Найдем новое базисное решение для этого вектора:

Поскольку, то это решение будет оптимально (так как не изменились оценки D₄ и D₅  для небазисных векторов). 

Пусть введено дополнительное ограничение x₁³6. Приведем его к стандартному виду:

x₁–x₆=6®-x₁+x₆=-6. Допишем эту строку в симплекс-таблице 2.27, и одновременно  справа от нее столбец A₆. Получим главную часть табл.2.28.

   Таблица 2.28.

 Анализируя ее видим, что базисный столбец A₁ не является единичным, и нужно исключить переменную x₁ в строке  x₆. Для этого прибавим к строке x₆ строку x₁, в результате получим новую строку  , которую дописываем в табл.2.28 внизу, а строку x₆ можно вычеркнуть.

Так как компонента = -2<0, то базисное решение { x₁ , x_{6 ,}  x'₆} -это псевдоплан: и дальше для продолжения итераций применим двойственный симплекс-метод. 

Направляющая строка , направляющий столбец A₄. Выполнив одну итерацию двойственного симплекс-метода, получим симплекс-таблицу 2.29.

Таблица 2.29.

Так как=6>0, =7>0, то это новое решение оптимально. При этом L_max==33. 

Проверим целесообразность введения третьего способа производства. Для этого рассмотрим столбец   

В соответствии с теорией двойственности  . Так как D₃<0 , то столбец A₃ целесообразно ввести в базис. В соответствии с методом обратной матрицы вычисляем его вид , в котором его можно дописать в таблицу 2.27:

Дописав столбец A₃ в симплекс-таблиу оптимального решения исходной задачи (табл.2.27), получим табл. 2.30. При этом  .

Таблица 2.30.

 Выполнив одну итерацию симплекс-метода, получим симплекс-таблицу 2.31.

Таблица 2.31.

 Поскольку все элементы ее индексной строки D_j  ³ 0, то это решение оптимально: =8; =4. При этом значение ц.ф. увеличилось до 44 единиц.