Eng | Rus | Ukr
Исследование операций
27.01.2005

<< prev | ^up^ | next >>

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

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

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

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

при условиях

                                                         (2.7.2)

xj³0.

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

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

Пусть ограничение bi получают некоторые вариации Dbi, что приводит к вариациям плана x0, x0= x0(b+Db) и функции Lmax (x0(b0+Db)). Предположим, эти вариации Db таковы, что план x0(b+Db)  остается допустимым ( т.е. удовлетворяет условию неотрицательности). Найдем отношения приращения

DLmax(b)= Lmax (x0(b0+Db))- Lmax (x0(b)) к Db.

Имеем

                                                            (2.7.3)

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

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

                                   ,                    (2.7.4)

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

                                       .                       (2.7.5)

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

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

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

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

xопт= A-1x b.

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

xн = А-1хbн = А-1х(b+Db).

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

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

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

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

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

                              для j=r ;                  (2.7.6)

       2) rÎ Jб,

          jÎJнеб                   (2.7.7)

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

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

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

Решая совместно систему неравенств вида (c1, c2,.,cr)³0,jÎJнебы находим условия для вариаций , при которых прежний оптимальный базис сохраняется.

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

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

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

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

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

при условиях

                                                 ,                                     (2.7.9)

xj³0.

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

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

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

при условиях 

                                     ,                            (2.7.11)

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

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

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

 .

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

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

 Пример 2.10.

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

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

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

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

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

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

max (2 x1+3 x2)

при условиях 

3 x1+2 x2 £ 32;

1 x1+2 x2 £ 24;

x1³0,    x2³0.

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

Получим=4; =10; max (2 x1+3 x2)=38.

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

                                                                                                                            Таблица2.27

cj

   

2

3

0

0

 

Bx

A0

A1

A2

A4

A5

2

х1

4

1

0

    

3

х2

10

0

1

    

 

D

38

0

0

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

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

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

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

x1-x6=6R-x1+x6=-6. Допишем эту строку в симплекс-таблице 2.27, и одновременно  справа от нее столбец A6. Получим главную часть табл.2.28.

   Таблица 2.28.

ci

   

2

3

     
 

Bx

A0

A1

A2

A4

A5

A6

2

x1

4

1

0

      

      -

0

3

x2

10

0

1

    

       

0

 

x6

-6

-1

0

         0

         0

1

-2

0

0

      

    

1

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

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

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

Таблица 2.29.

ci

   

2

3

     
 

Bx

A0

A1

A2

A4

A5

A6

2

x1

6

1

0

0

0

-1

3

x2

7

0

1

     

0

 

x4

4

0

0

       -1

1

-2

 

D

33

0

0

      

0

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

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

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

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

Таблица 2.30.

ci

   

2

3

   

4

 

Bx

A0

A1

A2

A4

A5

A3

2

x1

4

1

0

        

    

      

3

x2

10

0

1

     

 

D

38

0

0

        

    

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

Таблица 2.31.

ci

   

2

3

   

4

 

Bx

A0

A1

A2

A4

A5

A3

4

x3

8

2

0

1

-1

1

3

x2

4

    

1

-1

0

 

D

44

0

1

0

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

<< prev | ^up^ | next >>

 
     
  Copyright © 2002-2004