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

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

                      Министерство образования Украины

 

                 Севастопольский Государственный  Технический

                                 Университет

 

                                      –

 

 

            Департамент ИС

 

 

 

        ИСПОЛЬЗОВАНИЕ  табличного симплекс - метода для  РЕШЕНИЯ ЗАДАЧ

                          ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

                                     ДЛЯ

                       ОПТИМИЗАЦИИ ЭКОНОМИЧЕСКИХ задач

 

 

 

                   Пояснительная записка к курсовой  работе

                по дисциплине “Методы исследования  операций”

 

                            Гибкий магнитный диск

                                  59 листов

 

 

 

                                                                  Выполнил:

 ст. гр. И-22 д

 

          Крыльцова  Т.В.

                                                                     Принял:

  Старобинская Л.П.

 

 

                                 Севастополь

                                    1997

 

 

                                    - 3 -

 

                                 СОДЕРЖАНИЕ

 

 

 

    ВВЕДЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .  .

. . . . . . . . . . . . . .    5

1. КРАТКИЙ ОБЗОР АЛГОРИТМОВ  РЕШЕНИЯ ЗАДАЧ

     ДАННОГО ТИПА . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .

. . . . . . . . .      6

       1.1 Математическое  программирование . . . . . . . . . . . . . .  .  .

. . .      6

       1.2 Табличный симплекс - метод . . . . . . . . . . . . . . . . . .  .

. . . . . . .     7

       1.3 Метод  искусственного базиса . . . . . . . . . . . . . . . .  .  .

. . . . . . .      8

       1.4 Модифицированный  симплекс - метод . . . . . . . . . . . . .  .  .

. .       8

2. СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ . . . . . . . . . . . .    10

3. РАЗРАБОТКА И ОПИСАНИЕ АЛГОРИТМА  РЕШЕНИЯ

    ЗАДАЧИ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .  .

. . . . . . . . . . . . . . . .   11

      3.1 Построение математической модели задачи . . . . . . . . . .  .  .

    . .   11

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

    . . . . . . . . .   12

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

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

             решение . . . . . . . . . . . . . . . . . . . . . . . . .  .  .

. . . . . . . . . . . . . . . . .     16

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

. . . . . . .     16

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

. . . . . .    17

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

            ресурсов . . . . . . . . . . . . . . . . . . . . . . . . .  .  .

. . . . . . . . . . . . . . . . .      17

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

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

. . . . . . . . .      19

 

 

 

                                    - 4 -

 

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

    РЕЗУЛЬТАТОВ . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .

. . . . . . . . . . . .     20

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

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

. . . . . . . .     22

    ПРИЛОЖЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .  .

. . . . . . . . . . . .    23

    ЛИТЕРАТУРА  . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .

. . . . . . . . . . . .      11

                                    - 5 -

 

 

                                  ВВЕДЕНИЕ

 

 

        Цель  данного  курсового  проекта  -  составить  план  производства

требуемых изделий, обеспечивающий максимальную  прибыль  от  их  реализации,

свести  данную  задачу  к  задаче  линейного  программирования,  решить   её

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

методом  на ЭВМ.

                                       - 6 -

 

                 1.  КРАТКИЙ ОБЗОР АЛГОРИТМОВ  РЕШЕНИЯ ЗАДАЧ

                                   ДАННОГО ТИПА

 

                     1.1 Математическое программирование

 

    Математическое  программирование занимается изучение  экстремальных задач

и  поиском  методов  их  решения.  Задачи  математического  программирования

формулируются следующим образом :  найти экстремум некоторой функции  многих

переменных f ( x1, x2, ... , xn ) при ограничениях                gi  (  x1,

x2, ... , xn ) ( bi ,  где gi -  функция,  описывающая  ограничения,   (   -

один из следующих знаков ( ,  ( ,  ( ,  а bi - действительное число, i =  1,

...  ,  m.                       f   называется   функцией  цели  (  целевая

функция ).

    Линейное    программирование    -    это     раздел     математического

программирования, в котором  рассматриваются  методы  решения  экстремальных

задач с линейным функционалом  и  линейными  ограничениями,  которым  должны

удовлетворять искомые переменные.

   Задачу линейного программирования  можно сформулировать так .  Найти max

                                    [pic]

    при условии :          a11 x1 + a12 x2  + . . . + a1n xn  ( b1 ;

                                                       a21 x1 + a22 x2  + .

. . + a2n xn  ( b2 ;

                                                        .  .  .  .  .  .  .

.  .  .  . .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .

                                      am1 x1 + am2 x2  + . . . + amn xn   (

bm ;

                                     x1 ( 0,   x2 ( 0,  . . . ,  xn ( 0 .

    Эти  ограничения  называются  условиями  неотрицательности.  Если   все

ограничения заданы в виде  строгих  равенств,  то  данная  форма  называется

канонической.

                                    - 7 -

 

    В  матричной   форме   задачу   линейного   программировани   записывают

следующим образом. Найти    max cT x

    при условии

                                 A x  (  b ;

                                  x  (  0 ,

    где А - матрица  ограничений размером ( m(n), b(m(1)   -  вектор-столбец

свободных членов, x(n ( 1)  - вектор переменных,  сТ = [c1, c2, ... ,  cn  ]

- вектор-строка коэффициентов  целевой функции.

    Решение х0 называется  оптимальным, если для  него  выполняется  условие

    сТ х0  ( сТ  х ,  для всех х ( R(x).

    Поскольку  min f(x)  эквивалентен  max [ - f(x) ] , то задачу  линейного

программирования всегда можно свести к эквивалентной  задаче максимизации.

    Для решения  задач данного типа применяются  методы:

    1) графический;

    2) табличный ( прямой, простой ) симплекс - метод;

    3) метод искусственного  базиса;

    4) модифицированный симплекс - метод;

    5) двойственный  симплекс - метод.

 

                           1.2 Табличный симплекс - метод

 

    Для его применения  необходимо, чтобы знаки  в   ограничениях  были  вида

  “ меньше либо равно  ”, а компоненты вектора b - положительны.

    Алгоритм решения  сводится к следующему :

    1.  Приведение  системы ограничений к каноническому  виду  путём  введения

       дополнительных  переменных для приведения неравенств  к равенствам.

    2.  Если в  исходной системе ограничений  присутствовали знаки “ равно ”

                                    - 8 -

 

    или    “  больше либо равно ”, то  в указанные ограничения добавляются

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

       со знаками,  определяемыми типом оптимума.

    3.  Формируется  симплекс-таблица.

    4.  Рассчитываются  симплекс-разности.

    5.  Принимается  решение об окончании либо  продолжении счёта.

    6.  При необходимости  выполняются итерации.

    7.  На каждой  итерации определяется вектор, вводимый в базис, и  вектор,

       выводимый  из базиса. Таблица пересчитывается  по методу Жордана-Гаусса

       или каким-нибудь  другим способом.

 

                       1.3 Метод искусственного базиса

 

    Данный метод  решения  применяется  при   наличии  в  ограничении  знаков

 “ равно ”, “  больше либо  равно  ”,  “   меньше  либо  равно  ”   и  является

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

искусственных переменных со знаком, зависящим от  типа  оптимума,  т.е.  для

исключения из базиса этих переменных последние вводятся в целевую функцию  с

большими отрицательными коэффициентами ( ,   а  в  задачи  минимизации  -  с

положительными ( . Таким образом  из исходной получается новая ( - задача.

    Если в оптимальном  решении ( - задачи нет искусственных переменных, это

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

решении ( - задачи хоть одна из искусственных переменных  будет  отлична  от

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

неразрешима.

                       1.4 Модифицированный симплекс - метод

    В основу данной  разновидности симплекс-метода положены  такие особен -

 

                                    - 9 -

 

    ности линейной  алгебры  ,  которые  позволяют  в  ходе  решения  задачи

работать  с  частью  матрицы  ограничений.  Иногда  метод  называют  методом

обратной матрицы.

    В процессе работы  алгоритма  происходит  спонтанное  обращение  матрицы

ограничений по частям, соответствующим  текущим базисным векторам.  Указанная

способность делает весьма  привлекательной  машинную  реализацию  вычислений

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

сокращения времени счёта. Хорош  для  ситуаций,  когда  число  переменных  n

значительно превышает число ограничений m.

    В целом, метод отражает  традиционные черты  общего  подхода  к  решению

задач линейного программирования, включающего  в  себя  канонизацию  условий

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

решений о коррекции базиса и  исключение Жордана-Гаусса.

    Особенности  заключаются   в  наличии   двух   таблиц   -   основной   и

вспомагательной, порядке их заполнения и некоторой  специфичности  расчётных

формул.

                                   - 10 -

 

                     2. СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ

 

     Для производства  двух видов  изделий  А   и  В  используется  три   типа

технологического  оборудования.  На  производство  единицы  изделия  А  идёт

времени, часов :  оборудованием 1-го типа - а1 ,   оборудованием  2-го  типа

- а2 ,  оборудованием 3-го  типа - а3 . На  производство  единицы   изделия  В

идёт времени, часов :  оборудованием 1-го типа - b1  ,   оборудованием  2-го

типа - b2 ,, оборудованием 3-го типа - b3 .

    На  изготовление   всех   изделий   администрация   предприятия   может

предоставить оборудование 1-го типа не более, чем на  t1 ,  оборудование  2-

го типа не более, чем на  t2 ,  оборудование 3-го типа не более, чем на   t3

 часов.

    Прибыль от реализации  единицы готового изделия А составляет ( рублей, а

изделия В -  ( рублей.

    Составить план производства  изделий А и В, обеспечивающий  максимальную

прибыль от их  реализации.  Решить  задачу  простым  симплекс-методом.  Дать

геометрическое истолкование задачи, используя для этого  её  формулировку  с

ограничениями-неравенствами.

    а1 = 1          b1 = 5          t1 = 10          (  = 2

    а2 = 3          b2 = 2          t2 = 12          ( = 3

    а3 = 2          b3 = 4          t3 = 10

 

 

 

                                   - 11 -

 

              3. РАЗРАБОТКА И ОПИСАНИЕ АЛГОРИТМА  РЕШЕНИЯ ЗАДАЧИ

 

                 3.1 Построение математической модели  задачи

 

|                   |На произв-во       |На  произв-во       |Предпр-е          |

|                   |изделия А, часов   |изделия B, часов   |предоставит, часов|

|Оборуд-е 1го типа  |1                  |5                  |10                |

|Оборуд-е 2го типа  |3                  |2                  |12                |

|Оборуд-е 3го типа  |2                  |4                  |10                |

|Прибыль от         |2                  |3                  |                  |

|реализации, за ед. |                   |                   |                  |

|изд-я              |                   |                   |                  |

 

 

    Построение математической  модели осуществляется в три  этапа :

    1.   Определение   переменных,   для   которых    будет    составляться

       математическая  модель.

       Так как требуется  определить план производства изделий  А  и  В,  то

       переменными модели  будут:

        x1  - объём  производства изделия А, в единицах;

          x2  - объём производства изделия В,  в единицах.

    2. Формирование целевой  функции.

        Так как  прибыль  от  реализации  единицы  готовых  изделий  А  и  В

       известна, то общий  доход от их реализации составляет  2x1  +  3x2   (

       рублей ).  Обозначив   общий  доход  через  F,  можно  дать  следующую

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