Методы оптимазации в задачах планирования производства

  • МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ИНСТИТУТ  ЭКОНОМИКИ, УПРАВЛЕНИЯ И ПРАВА (г. КАЗАНЬ)

Кафедра высшей математики

КУРСОВОЙ  ПРОЕКТ

ПО ВЫСШЕЙ МАТЕМАТИКЕ

НА ТЕМУ:

МЕТОДЫ  ОПТИМИЗАЦИИ

В ЗАДАЧАХ ПЛАНИРОВАНИЯ ПРОИЗВОДСТВА

 
 
 
 
 

                       Выполнил:

                                           студент группы № 581

                                     дневного отделения

                                                   экономического факультета

                                                                        специальность менеджмент организации

                                                            Хайрутдинова Регина Нафисовна

 

                            Руководитель:

                                                   Кабирова Раиса Гашимовна

 
 
 

Бугульма  – 2009 г.

ПОСТАНОВКА  ЗАДАЧИ

 

          Условия задачи представлены в таблице:

    D T R T VT D Ж R Ж V Ж B D BR BV S T S Ж P0 P1 P2
    13 7 1 3 3 1 0 720 180 21 9 30 0,02 200
 

          Дополнительная  возможность 1: получение ссуды. 

          То  есть задача формулируется следующим образом:

          Строительная  фирма имеет возможность постройки  двух видов зданий: торговый комплекс или жилой дом. Каждый вид сооружается  в течение года. Для сооружения тысячи «торговых» квадратных метров требуется вложить 13 миллионов рублей, задействовать 7 рабочих и затратить 1 тысячу кубометров стройматериалов. Для сооружения тысячи квадратных метров «жилой» площади требуется вложить 3 миллиона рублей, задействовать 3 рабочих и затратить 1 тысячу кубометров стройматериалов. За каждую тысячу квадратных метров торговых площадей фирма получает доход 21 млн. рублей, а за каждую тысячу кв. жилой площади – 9 млн. рублей. На складах фирмы имеется 180 тысяч кубометров стройматериалов, в штате фирмы 720 рабочих, а собственный капитал фирмы составляет 0 рублей. Кроме того, фирма может взять кредит в банке в размере y млн. руб., при этом в конце года фирма платит за кредит

    P(y) = (30– 0,02∙y + 0,000∙1y2) процентов годовых, если сумма кредита                    превышает 50 млн. руб. и (30 – 0,02∙50 + 0,0001∙502) = процентов годовых, если сумма кредита меньше. 

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

          РЕШЕНИЕ

          Составим  экономико-математическую модель задачи. Для этого обозначим х1 – количество тысяч квадратных метров торговых площадей, а х2 – количество тысяч квадратных метров жилой площади построенных фирмой. Кредит у (в млн. руб.), полученный фирмой в банке может быть любым неотрицательным числом.

          Эта задача является задачей оптимального использования ресурсов. Система  ограничений, получаемая из ограниченности ресурсов, имеет вид:

          7х1 + 1х2 ≤  у,

3х1 + 1х2 ≤ 720,                                                                                                         (1)

         1х1 + 3 х2 ≤ 180,

    где справа стоит  количество каждого вида ресурса, которое  не может быть                      превышено в процессе деятельности фирмы. Эти ограничения являются нетривиальными.

            Далее, х1  и х2  являются неотрицательными (нельзя построить отрицательное число квадратных метров зданий), что дает нам тривиальное ограничение задачи: 

          х1 ≥ 0,   х2 ≥ 0                                                                                                   (2)

          Наконец, функция цели (или целевая функция) представляет собой общую стоимость произведенной продукции, и эта функция в поставленных ограничениях оптимизируется на максимум:

           F = 9х1 + 9 х2 – f (y)              max                                                                   (3)

    где функция  f (y)  отражает выплаты банку. Она связана с процентной ставкой Р и суммой кредита у следующим соотношением:

            f (y) = (1 +P (y)  ∕ 100) ∙ y

           Согласно условию задачи, получаем:

                            

                                    (1 + 0,01 ∙ (0,15 – 0,02 ∙ y + 0,001y2)) ∙ y, при y > 50

                                                                                           ,                                                                  , при у < 50                   (4)                                                                                                              

          Из- за нелинейной функции (4) к данной задаче нельзя применить методы линейного программирования непосредственно. Задача же нелинейного программирования (1)-(4) достаточно сложна.

          Однако  данную проблему можно разбить на два этапа. На первом определяем оптимальный  план следующей задачи линейного  программирования:

            Z = 9х1 + 9 х2 - f (y)                 max                                                             (5)                                                               

           13х1 + 3х2 ≤  у,

                     7х1 + 3х2 ≤ 720,                                                                                            (6)                                                                                                  

          1х1 + 1 х2 ≤ 180,

          х1 ≥ 0,   х2 ≥ 0,                                                                                                (7)                                                                                          

    рассматривая  у как параметр (известную величину). В результате решения задачи (5) - (7) получаем оптимальный план, в котором х1*, х2* и Z* зависит от у.

          На  втором этапе решаем задачу нелинейного  программирования. Ищем у* из задачи

    F (y) = Z* (y) - f (y)              max,                                                                           (8)                

    y ≥ 0.                                                                                                                        (9)

          Задача (8), (9), (4) – одномерная задача, и ее можно легко решить графически с  последующим аналитическим уточнением. 

          ЭТАП 1.

            Для решения задачи симплекс  – методом приведем систему  (5)-(7) к каноническому виду, введя дополнительные балансовые переменные х3, х4, х5, которые означают неиспользованное количество денег, рабочих и стройматериалов соответственно. При этом неравенство (6) преобразуется в уравнения:

            13х1 + 3х2 + х3                 =  у

     7х1 + 3х2       + х4          = 720                                                                    (10)                                                                                                                

          1х1 + 1х2           + х5 = 180

          По  смыслу балансовые переменные здесь  также неотрицательны, поэтому тривиальная  система неравенств   принимает вид:

    x j  ≥ 0   для всех  j = 1,5.                                                                                   (11)

          Введем  балансовые переменные и в целевую  функцию с коэффициентами равными  нулю:

           Z = 21х1 +9х2 + 0х3 +0х4 + 0х5                max                                         (12)

           Задача в  форме (12), (10), (11) имеет канонический вид. Соответствующая ей векторная  форма записи будет такова:

          с (21;9;0;0;0);

                  13                  3                 1                0               0                у

              Р1     7      ;     Р2   3     ;    Р3    0   ;     Р4   1  ;    Р5    0     ;   Р0   720     .           

                     1                    1                  0              0               1               180

          Здесь векторы  Р3, Р4 и Р5 имеют базисный вид, т.е. являются единичными в одном из компонентов и нулевым во всех остальных компонентах. Их и возьмем в качестве первоначальных базисных векторов. Данная задача является классической задачей оптимального использования ресурсов, и потому в ней всегда имеется возможность выделить первоначальные базисные вектора.

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

    Таблица 1.

    Базисные  переменные Свободные члены х1 х2 х3 х4 х5 Оценочные отношения
    х3 y 13 3 1 0 0 y/13
    х4 720 7 3 0 1 0 720/7
    х5 180 1 -9 0 0 1 180/1=180

    F

    0 -21 -9 0 0 0 max
 

      Ведущим столбцом будет первый столбец, так  как ему в индексной строке соответствует самое отрицательное  число. При определении ведущей  строки  оценочных отношений, полученных в последнем столбце, нужно выбрать  наименьшее. Очевидно, что α31> α21, при любых значениях у. Соотношение между α11 и α12 зависит от у.

    1. Рассмотрим случай y/13≥720/7 . Тогда y≥ 180 и ведущей строкой будет вторая строка:
    Базисные  переменные Свободные члены х1 х2 х3 х4 х5 Оценочные отношения
    х3 y 13 3 1 0 0 y/13
    х4 720 7 3 0 1 0 720/7
    х5 180 1 1 0 0 1 180

    F

    0 -21 -9 0 0 0 max
 

Таким образом, в базис входит х1 , а покидает ее х4. 

      Пересчитаем таблицу по всем правилам пересчета  симплексных таблиц. Получаем новую  симплексную таблицу:

    Базисные  переменные Свободные члены х1 х2 х3 х4 х5 Оценочные отношения
    х3 у – 9360/7 0 -18/7 1 13/7 0  
    х1 720/7 1 3/7 0 1/7 0  
    х5       540/7 0 4/7 0 3/7 1  

    F

    2160 0 0 0 3 0 max
 

      Так как в индексной строке все  элементы неотрицательны, то полученный план является оптимальным. Таким образом, при y≥180 оптимален план х1*=720, х2*=0, х3*=( у – 180), х4*=0, х5*=720, а значение целевой функции равно Z=2160. 

    1. Теперь  рассмотрим случай y<180. Тогда в табл. 1 ведущей строкой будет первая строка:
    Базисные  переменные Свободные члены х1 х2 х3 х4 х5 Оценочные отношения
    х3 y 13 3 1 0 0 y/13
    х4 720 7 3 0 1 0 720/7
    х5 180 11 1 0 0 1 180

    F

    0 -21 9 0 0 0 max

В базис входит х1, а покидает его х3. Пересчитывая, получаем новую симплексную таблицу:

Таблица 2. 

    Базисные  переменные Свободные члены х1 х2 х3 х4 х5 Оценочные отношения
    х1   y/13 1 3/13 1/13 0 0 y
    х4 720 - 7y/13 0 18/13 -7/13 1 0 720 - 7y/13
    х5 180 - y/13 0 10/13 -1/13 0 1 180-у/10

    F

    21y/13 0 -180/13 21/13 0 0 max
 

        Ведущим столбцом будет второй, так как ему в индексной  строке соответствует единственное отрицательное число. При определении ведущей среди оценочных отношений, полученных в последнем столбце, нужно выбрать наименьшее. Все они зависят от у. Определим, в каких интервалах изменения у минимально каждое из чисел αip. Для этого рассмотрим три неравенства:

      720 -7 y/18 ≥ 180-у/10 → у  ≤ 97200/52;

      720 -7 y/18 ≥ y              → у  ≤12960/25;

      180 – y/10 ≥ y                → у ≤1800/11.

      Проанализировав результат, приходим к следующим  выводам:

         α12 = y меньше остальных симплексных отношений при у≤1800;

         α22 = 720 - 7y/18 меньше остальных отношений при у≥9720/52;

         α32 = 180 – y/10 меньше остальных отношений при 1800/11≤ у≤9720/520.

      Рассмотрим  все три случая с учетом условий у<9360/7 и у≥0.0<y<1800/11

  • Тогда в табл. 2 ведущей строкой будет первая строка:
    • Базисные  переменные Свободные члены х1 х2 х3 х4 х5 Оценочные отношения
      х1   y/13 1 3/13 1/13 0 0 Y
      х4 720 - 7y/13 0 18/13 -7/13 1 0 720 - 7y/18
      х5 180 - y/13 0 10/13 -1/13 0 1 180-y/10

      F

      21y/13 0 -180/13 21/13 0 0 Max
     

      В базис входит х2, а покидает его х1. пересчитывая получаем новую симплексную таблицу:

      Базисные  переменные Свободные члены х1 х2 х3 х4 х5 Оценочные отношения
      х2   y/3 13/3 1 1/3 0 0  
      х4 714 - 7y/3 -6 0 -1 1 0  
      х5 18 - 61y/13 10/3 0 199/897 0 1  

      F

      99y/13 60 0 81/13 0 0 max
     

      Так как  в индексной строке все элементы неотрицательны, то полученный план является оптимальным. Таким образом, при 0≤ у≤1800 оптимальный план: х1*=0, х2*= y/13, х3*=0, х4*=(720 - 7y/13), х5*=(180 + 13), а значение целевой функции равно Z*=21у/13. 

  • 97200≤ у<9360. тогда в табл. Ведущей строкой будет вторая:

      Базисные  переменные Свободные члены х1 х2 х3 х4 х5 Оценочные отношения
      х1   y/13 1 3/13 1/13 0 0 y/3
      х4 720 - 7y/13 0 18/13 -7/13 1 0 720 - 7y/18
      х5 180 - y/13 0 10/13 -1/13 0 1 180 – y/10

      F

      21y/13 0 -180/3 21/13 0 0 Max
     

             В базис входит  х2, а покидает его х4. Пересчитывая, получаем новую симплексную таблицу:  

      Базисные  переменные Свободные члены х1 х2 х3 х4 х5 Оценочные отношения
      х1 720+13y/1170 1 0 15/9 1/13 0  
      х2 720 - 7y/18 0 1 -7/9 13/18 0  
      х5 720 - 8y/9 0 0 -7/69 101/13 1  

      F

      28у/9 0 0 1 0 0 max

                 

          Так в индексной строке все элементы неотрицательны, то полученный план является оптимальным. Таким образом, при 720-8у/9≤ у<180 оптимальный план: х1*=(720+13у/1170), х2*=(720-7у/18) , х3*=0, х4*=0, х5*=(720-8у/9), а значение целевой функции равно Z*=(28у/9). 

  • 97200/52<y<1800/11. Тогда в табл. 2 ведущей строкой будет третья строка:
    • Базисные  переменные Свободные члены х1 х2 х3 х4 х5 Оценочные отношения
      х1   y/13 1 3/13 1/13 0 0 Y
      Х2 720 - 7y/13 0 18/13 -7/13 1 0 720 - 7y/18
      х5 180 - y/13 0 10/13 -1/13 0 1 180 – y/10

      F

      21y/13 0 -180/3 21/13 0 0 Max
     

      В базис входит х2, а покидает его х5. Пересчитывая, получаем новую симплексную таблицу: 
       

      Базисные  переменные Свободные члены х1 х2 х3 х4 х5 Оценочные отношения
      х1 3у/5-10 1 0 13/18 0 3/13  
      х4 у/39 0 0 7/69 1 -1/13  
      х2 180-у/10 0 1 -1/10 0 13/10  

      F

      18у/39 0 0 18/10 0 21/13 Max
     

          Так как в индексной строке все  элементы неотрицательны, то полученный план является оптимальным. Таким образом, при 97200/52<y<1800/11 оптимальный план: х1*=(3у/5-10), х2*=(180-у/10) , х3*=0, х4*=(у/39), х5*=0, а значение целевой функции равно Z*=(18у/39).

    Методы оптимазации в задачах планирования производства