Использование табличного симплекс-метода для решения задач линейного программирования для оптимизации экономических задач 2.doc

       значения переменных  x1  и  x2 , максимизирующих целевую  функцию F  =

         2x1  + 3x2 .

    3. Формирование системы  ограничений.

      При определении   плана  производства  продукции   должны  быть  учтены

       ограничения на  время, которое администрация предприятия сможет пре -

 

 

                                   - 12 -

 

       доставить на  изготовления всех изделий.  Это   приводит  к  следующим

       трём ограничениям :

      x1  + 5x2    (    10 ;       3x1  + 2x2   (  12 ;      2x1 + 4x2  (

                                     10 .

        Так  как   объёмы  производства   продукции   не   могут   принимать

       отрицательные  значения, то появляются ограничения  неотрицательности :

                      x1  ( 0 ;                x2 ( 0 .

       Таким  образом, математическая модель  задачи представлена  в  виде  :

       определить  план  x1 ,  x2   ,  обеспечивающий  максимальное  значение

       функции  :

                         max F = max ( 2x1  + 3x2  )

       при наличии  ограничений :

                            x1  + 5x2    (    10 ;

                            3x1  + 2x2   (  12 ;

                             2x1  + 4x2  (  10 .

                             x1  ( 0 ;  x2 ( 0 .

 

                         3.2 Решение задачи вручную

 

    Табличный  метод   ещё  называется  метод  последовательного   улучшения

оценки. Решение задачи осуществляется поэтапно.

    1. Приведение задачи  к форме :

                           x1  + 5x2    (    10 ;

                            3x1  + 2x2   (  12 ;

                             2x1  + 4x2  (  10 .

                             x1  ( 0 ;  x2 ( 0 .

    2. Канонизируем систему  ограничений :

 

 

                                   - 13 -

 

      x1  + 5x2   + x3                         =  10 ;

    3x1  + 2x2          + x4         = 12 ;

    2x1  + 4x2                  + x5 = 10 .

    x1  ( 0 ;  x2 ( 0 .

    A1         A2     A3    A4    A5    A0

    3. Заполняется  исходная  симплекс-таблица  и   рассчитываются  симплекс-

       разности  по формулам :

    (0 = [pic]  - текущее значение целевой функции

    (i = [pic]   - расчёт симплекс-разностей,  где j = 1..6  .

|         |         |C        |2        |3        |0        |0        |0       |

|Б        |Cб       |A0       |A1       |A2       |A3       |A4       |A5      |

|A3       |0        |10       |1        |5        |1        |0        |0       |

|A4       |0        |12       |3        |2        |0        |1        |0       |

|A5       |0        |10       |2        |4        |0        |0        |1       |

|         |(        |0        |-2       |-3       |0        |0        |0       |

 

    Так  как  при   решении  задачи  на   max   не   все   симплекс-разности

положительные, то оптимальное  решение  можно улучшить.

    4.  Определяем  направляющий  столбец  j*.  Для задачи   на   max   он

определяется минимальной отрицательной  симплекс-разностью. В  данном  случае

это вектор А2

    5.  Вектор  i*,  который   нужно  вывести  из  базиса,  определяется  по

отношению :

                          min  [pic]  при аi j > 0

 

 

                                   - 14 -

 

    В данном случае сначала  это А3 .

    5. Заполняется новая  симплекс-таблица по исключеню  Жордана - Гаусса :

       а). направляющую  строку  i*  делим на направляющий  элемент :

                  a i j  = a i j / a i j    , где j = 1..6

       б). преобразование всей оставшейся части матрицы :

             a ij = aij - a i j ( aij    , где i ( i*  ,  j ( j*

    В результате преобразований получаем новую симплекс-таблицу :

 

|         |         |C        |2        |3        |0        |0        |0       |

|Б        |Cб       |A0       |A1       |A2       |A3       |A4       |A5      |

|A2       |3        |2        |1/5      |1        |1/5      |0        |0       |

|A4       |0        |8        |13/5     |0        |-2/5     |1        |0       |

|A5       |0        |2        |6/5      |0        |-4/5     |0        |1       |

|         |(        |6        |-7/5     |0        |3/5      |0        |0       |

 

    Повторяя пункты 3 - 5, получим  следующие таблицы :

 

|         |         |C        |2        |3        |0        |0        |0       |

|Б        |Cб       |A0       |A1       |A2       |A3       |A4       |A5      |

|A2       |3        |5/3      |0        |1        |1/3      |0        |-1/6    |

|A4       |0        |11/3     |0        |0        |4/3      |1        |-13/6   |

|A1       |2        |5/3      |1        |0        |-2/3     |0        |5/6     |

|         |(        |8  1/3   |0        |0        |-1/3     |0        |7/6     |

 

|         |         |C        |2        |3        |0        |0        |0       |

|Б        |Cб       |A0       |A1       |A2       |A3       |A4       |A5      |

|A2       |3        |3/4      |0        |1        |0        |-1/4     |3/8     |

|A3       |0        |11/4     |0        |0        |1        |3/4      |-13/8   |

|A1       |2        |7/2      |1        |0        |0        |1/2      |-1/4    |

|         |(        |9  1/4   |0        |0        |0        |1/4      |5/8     |

 

 

                                   - 15 -

 

    Так как все   симплекс-разности  положительны,  то  оптимальное  решение

найдено :

    X = ( 7/2 ,   3/4 ,   11/4 ,   0 ,   0  )   ( единиц )

    max F = 9  1/4  ( рублей )

 

 

 

                                   - 16 -

 

                    4. АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ

 

             4.1 Построение двойственной задачи и её численное решение

 

    Проведение   анализа   на   чувствительность    связано    с    теорией

двойственности, поэтому в курсовой работе необходимо построить  двойственную

задачу и найти её численное  решение.

    Для рассматриваемой  модели двойственная задача имеет вид :

           min  T( y ) = min ( 10y1 + 12y2 + 10y3 )   при условиях

                                                        y1 + 3y2 + 2y3  ( 2

               А1

 

    5y1 + 2y2 + 4y3 ( 3                А2

                                                   y1 ( 0 ,   y2 (0 ,    y3

( 0.          А3,  А4,  А5

    Оптимальное решение  двойственной задачи получается  при решении  прямой

задачи из последней  симплекс-таблицы.  В  результате  получаем  оптимальное

решение двойственной задачи :

    Yопт = ( 0, 1/4, 5/8, 0, 0 ), для которого Т(yопт) = 9  1/4.

    Оптимальное значение  целевой функции в двойственной  задачи совпадает  с

оптимумом целевой функции  прямой задачи, в чём не трудно убедиться.

 

                          4.2 Определение статуса ресурсов

 

    Ресурсы относятся к  дефицитным, если оптимальный   план  предусматривает

их  полное  использование,  при  частичном   использовании   ресурсов,   они

считаются  не  дефицитными.  Статус  ресурсов  для  любой  модели  линейного

программирования можно установить непосредственно из  оптимальной  симплекс-

таблицы  исходной  по  значению  дополнительных  переменных.   Положительное

значение до -

 

 

 

                                   - 17 -

 

    полнительной   переменной   указывает   на    неполное    использование

соответствующего ресурса,  т.е.  на  его  недефицитность,  нулевое  значение

дополнительной переменной указывает  на дефицитность ресурса.

    Для данного примера   дополнительные переменные х4  и   х5  равны  нулю,

следовательно,   оборудование   второго   и    третьего    типов    являются

“дефицитными”, а первого типа - “недефицитным” (  х3  =  2,75  ).  Такой  же

вывод можно сделать из решения  двойственной задачи.

 

                        4.3 Определение значимости ресурсов

 

    Значимость ресурса   характеризуется  величиной   улучшения  оптимального

значения  целевой  функции  F,  приходящейся  на  единицу  прироста  данного

ресурса.  Значимость  ресурсов   всегда   можно   определить   по   значению

двойственных переменных в оптимальном решении двойственной задачи.

    В данном случае Yопт  = ( 0, 1/4, 5/8, 0, 0 ). Таким  образом,  из  двух

“дефицитных” ресурсов оборудование второго типа имеет большую  значимость  и

увеличении интервала  работы на  этом  оборудовании  более  выгодно  с  точки

зрения влияния на значение целевой функции.

 

          4.4 Определение допустимого интервала  изменения запаса ресурсов

 

     Изменение отведённого  администрацией предприятия времени ( т.е. правых

частей ограничений )  может  привести  к  недопустимости  текущего  решения.

Поэтому важно определить диапазон изменений компонент  вектора  ограничений,

в котором допустимость решений  не нарушается.

    Оборудование  второго  типа,  которое  используется  для   изготовления

изделий,  является  “дефицитным  и  имеет  большую   значимость.   Определим

диапазон  допустимых  изменений  интервала  работы  на  этом   оборудовании.

Оптимальная

 

 

                                   - 18 -

 

    симплекс-таблица задачи имеет вид :

|         |         |C        |2        |3        |0        |0        |0       |

|Б        |Cб       |A0       |A1       |A2       |A3       |A4       |A5      |

|A2       |3        |3/4      |0        |1        |0        |-1/4     |3/8     |

|A3       |0        |11/4     |0        |0        |1        |3/4      |-13/8   |

|A1       |2        |7/2      |1        |0        |0        |1/2      |-1/4    |

|         |(        |9  1/4   |0        |0        |0        |1/4      |5/8     |

 

    Так  как   начальными  базисными  переменными   являлись  x1,  x2,  x3  в

оптимальной  симплексной  таблице  в  соответствующих  столбцах  расположена

матрица А-1 Изменим время  работы на оборудование второго  типа  на  величину

(2, тогда время работы будет 12 + (2 .

    Найдём базисное  решение, соответствующее изменённому  времени работы  на

оборудовании второго  типа :

 

    [pic]

     0.75 - (2 / 4 ( 0 ,   (2 = 3;

    2.75 + 3(2 / 4 ( 0 ,   (2 = -3.66;

    3.5 + (2 / 2 ( 0 ,   (2 = -7.

    Отсюда видно, что    -3.66 ( (2 ( 3 ,  т.е. 8.34 ( b2 ( 15 .

    Таким образом  первоначальный интервал работы  на  оборудовании  второго

типа можетбыть увеличен до 15 часов или уменьшен до 8.34 часа без  нарушения

допустимого решения. Уменьшение времени влечёт за  собой  уменьшение  единиц

вырабатываемой продукции, поэтому является не целесообразным.

 

 

 

                                   - 19 -

 

               4.5 Исследование зависимости оптимального  решения от

                               изменений запасов ресурсов

 

    Изменение свободного  члена ограничения исходной задачи  на  величину  (2

вызывает изменение целевой  функции на (F = ( i  (  y  j    .Если  приращение

времени  работы  бертся  из   интервала   допустимых   изменений,   значений

двойственных оценок остаются неизменными. Таким образом,  изменение  целевой

функции будет линейно  зависеть от изменения времени работы.

    В данном примере  (F = ( i  ( 12 = 12  (  (  i    .  Ищется  зависимость

значений  целевой  функции  от  изменения  времени  работы  на  оборудовании

второго типа. Для этого  изменяется время работы начиная  от 0 часов  с  шагом

h = 0.5  до 3 часов.Результаты  измерений приведены в таблице  1.

                                                              Таблица      1

|(2, часов|0        |0.5      |1        |1.5      |2        |2.5      |3       |

|b2, часов|12       |12.5     |13       |13.5     |14       |14.5     |15      |

|(F, руб. |0        |6.25     |13       |20.25    |28       |36.25    |45      |

|F, руб.  |9.25     |(        |(        |(        |(        |(        |        |

 

 

    Т.к. зависимость  F( b2 ) - линейная, то достаточно подсчитать  значение

функции в двух крайних  точках  интервала.

    Cледовательно, с  увеличением времени  работы  на  оборудовании  второго

типа на 2 часа  увеличивается  и  объём   изделий  на  общей  стоимостью  28

рублей.

 

 

 

                                   - 20 -

 

                   5. ГРАФИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ ПОЛУЧЕННЫХ

                                   РЕЗУЛЬТАТОВ

 

    Графический метод  применим только для двух и менее  переменных  х,  что

подходит к данному  заданию.Линии, соответствующие ограничения,  строятся  на

осях Ох. Заштрихованная область - область допустимых стратегий.

                           x1  + 5x2    (    10 ;

                            3x1  + 2x2   (  12 ;

                             2x1  + 4x2  (  10 .

                             x1  ( 0 ;  x2 ( 0 .

    1). x1  + 5x2    (    10 ;

        x1 = 0,   x2  = 2   ;

        x1 = 10,  x2  = 0  .

    2). 3x1  + 2x2   (  12 ;

         x1 = 0,   x2  = 6   ;

         x1 = 4,  x2  = 0  .

    3). 2x1  + 4x2  (  10 ;

         x1 = 0,   x2  = 2.5   ;

         x1 = 5,  x2  = 0  .

    4). Найдём экстремум  функции :

          F = 2x1 + 3x2 ,

    [pic]

      Графически  область допустимых решений показана на рисунке 1.

 

 

 

                                   - 21 -

 

 

 

           Рисунок 1 - Область допустимых  решений данной системы.

 

 

                                   - 22 -

 

                  6. ВЫВОДЫ И РЕКОМЕНДАЦИИ ПО  ПРАКТИЧЕСКОМУ

                                  ИСПОЛЬЗОВАНИЮ

 

    Составление математической  модели и решение систем линейных  неравенств