Динамическое программирование

  

  Стоимость сырья 

  Расходы , связанные с использованием единицы оборудования j-го типа на i-ой операции

  Производительности, соответственно, по выходу и входу и для  j-готипа оборудования, претендующего на i-ую операцию. 

  Решение:

  Для того, чтобы решить данную задачу методом  динамического программирования введем следующие обозначения:

  N = 3 – число шагов.

    - Технологическая линия.

   =  (0,0,0)

   = (                   )

    – выбор оборудования для  i-ой операции.

  U_i – область допустимых УВ на i-м шаге.

   т.е.

  W_i – оценка минимальной себестоимости, полученная в результате реализации i-го шага.

  S – функция общего выигрыша  т. е. минимальная себестоимость .

    

  

                            - вектор – функция, описывающая переход системы из состояния               в состояние   под действием УВ.

            

   - вектор УВ на i-ом шаге, обеспечивающий переход системы из состояния x_i-1 в состояние x_{i ,} т.е. оптимальный выбор оборудования за N  шагов.

  S_i+1( ) – максимальный выигрыш ( в нашем случае минимальная себестоимость), получаемый при переходе из любого состояния в конечное состояние при оптимальной стратегии управления начиная с (k+1)-го шага.

  S₁( ) – максимальный выигрыш, получаемый за N шагов при переходе системы из начального состояния в конечное при реализации оптимальной стратегии управления . Очевидно, что S = S₁( ), если = 0. 

  Запишем вектора допустимых значений

    
 
 

  Запишем вектора допустимых управляющих воздействий

    
 
 

   Запишем вектор – функцию, описывающую переход системы из состояния                  в состояние   под действием УВ.

    

  

    
 
 

   Запишем основное функциональное уравнение 

    
 

  1) Обратный проход

   Для  i=3 
 
 
 

  Учитывая  то, что этот шаг у нас последний и следующей операции

   уже не будет, а также то, что мы на обратном проходе, вместо функции

            возьмем стоимость сырья                    

  

  при                                                                              =         
 

  

  при                                                                              =                                                    

  

  т. е.                                                           

  Для   i=2

    
 
 

                                                                                

  

  при                                                                                           =                                         

  

  

  при                                                                                           =   

  

  при                                                                                             = 

  

  при                                                                                            =

  

  т. е.                           

   Для i=1 
 
 

  

  

  при                                                                                         =     

  

  при                                                                                       = 
 
 
 

   при                                                                                         =

  

  

  при                                                                                         ==

  

  

  при                                                                                               =

  

  

  при                                                                                                 =

  

  

  при                                                                                                =

  

  

  при                                                                                                   =

  

  т. е.                                  

2. Прямой проход

Учитывая то, что                                  и   = (0,0,0)  имеем

  i=1 

  
 
 

i=2 

 
 

i=3 

 
 

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

На  1-ую операцию назначим оборудование 2-го вида

На  2-ую операцию назначим оборудование 1-го вида

На  3-ью операцию назначим оборудование 2-го вида

Оценка минимальной  себестоимости составит 105,5.