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

      На этой основе можно записать уравнение, которое позволяет рекуррентно вычислить функции Беллмана, опираясь на результаты предыдущего шага. Для каждого варианта управления доход определяется как сумма двух слагаемых: непосредственного результата управления и его последствий.

      Если  в начале каждого года сохраняется  оборудование, возраст которого t лет, то доход за этот год составит r(t). К началу (k+1)-го года возраст оборудования достигнет (t+1) и максимально возможный доход за оставшиеся годы (с (k+1)-го по n-й) составит F_k+1(t+1). Если в начале k-го года принято решение о замене оборудования, то продается старое оборудование возраста     t лет по цене S(t), приобретается новое за P единиц, а эксплуатация его в течение k-го года нового оборудования принесет прибыль r(0). К началу следующего года возраст оборудования составит 1 год и за все оставшиеся годы с (k+1)-го по n-й максимально возможный доход будет F_k+1(1). Из двух возможных вариантов управления выбирается тот, который приносит максимальный доход.

      Функция F_k(t) вычисляется на каждом шаге управления для всех                1 ≤ t ≤ t₀ + k – 1. Управление при котором достигается максимум дохода, является оптимальным.

      Значения  функции F_n(t), определяемые F_n-1(t), F_n-2(t) вплоть до F₁(t). F₁(t₀) представляют собой возможные доходы за все годы. Максимум дохода достигается при некотором управлении, применяя которое на первом году, мы определяем возраст оборудования к началу второго года. Для данного возраста оборудования выбирается управление, при котором достигается максимум дохода за годы со второго по n-й и так далее. В результате на этапе безусловной оптимизации определяются годы, в начале которых следует произвести замену оборудования.

        

      2   РАСЧЕТНАЯ ЧАСТЬ

      Построение  оптимальной последовательности операций в коммерческой деятельности

      Пример

      Пусть на оптовую базу «Ларес» прибыло 10 машин с товаром для разгрузки и   8 машин для загрузки товаров, направляемых в магазины. Материально-ответственное лицо оптовой базы осуществляет оформление документов по операциям разгрузки или загрузки для одной машины, а затем переходит к обслуживанию другой машины. Известны затраты по выполнению каждой операции, которые показаны на ребрах графа (рис. 2). Издержки от операций обусловлены простоем транспорта, типом операции (прием или отправка товара) и не зависят от конкретной машины. Необходимо спланировать последовательность операций обоих видов таким образом, чтобы суммарные издержки по приему и отправке товаров для всех машин были минимальными.

      Решение:

      Из  условия следует, что состояние экономической системы характеризуется двумя параметрами: количеством принятых и оформленных машин по разгрузке товара и количеством машин, отправленных с товаром в магазины. Поэтому решение будем искать на плоскости X0Y, на ограниченном прямыми прямоугольнике, который является областью допустимых состояний системы. Если по оси X отложить число (10) разгруженных машин, а по оси Y – число (8) загруженных товаром машин, то можно построить на плоскости граф состояний процесса, в котором каждая вершина характеризует состояние операции приема и отгрузки товара на оптовой базе. Ребра этого графа означают выполнение работы по приему или отправке товара на очередной машине. Каждому ребру можно сопоставить издержки, связанные с выполнением операции по разгрузке или загрузке машины.

      Точка S₀ определяет начало процесса, a S₁ – конечное состояние, соответствующее приему и отправке всех машин. Оптимизацию процесса будем производить с конечного состояния S₁. Весь процесс разобьем на шаги, их количество k = n + m = 10 + 8 = 18. Каждый шаг представляет собой сечение графа состояний, проходящее через вершины (на рис. 2 сечения показаны косыми линиями).

      

      

    К=18     К=17    К=16      К=15    К=14    К=13     К=12       К=11      К=10     К=9

Рисунок 2 – Графическая схема связи операций 

      I этап. Условная оптимизация.

       1-й шаг.  k = 1. На первом шаге, с задаваемым сечением А₁В₁, из состояний      А₁ и B₁ возможен только один вариант перехода в конечное состояние S₁. Поэтому в вершинах А₁ и B₁ записываем соответственно издержки 13 и 10. Ребра A₁S₁ и B₁S_l обозначаем стрелкой, направленной в вершину S₁, как показано на рис. 3.

                                                                                       

                                                                                   
 

      Рисунок 3 – Сетевая модель операции, шаг 1 

      2-й  шаг. k = 2. Второй шаг оптимизации задается сечением по вершинам            А₂, В₂, C₁. Из состояний А₂ и C₁ возможен единственный переход в вершины  А₁ и B₁ соответственно, поэтому в вершинах А₂ и C₁ записываем суммарные издержки 29 и 28 на первых двух шагах перехода в конечное состояние S₁.

      Из  вершины В₂ возможны два варианта перехода: в вершину А₁ или вершину B₁. При переходе В₂ → А₁ сумма издержек составляет 11 + 13 = 24, на переходе В₂ → В₁ сумма составляет 15 + 10 = 25. Из двух вариантов суммарных издержек выбираем наименьшую (24) и обозначаем стрелкой условно оптимальный переход В₂ → А₁, как показано на рис. 4.

        

        

        

      Рисунок 4 – Сетевая модель операции, шаг 2 

      3-й  шаг. k = 3. На третьем шаге сечение  проходит через вершины А₃, В₃, С₂, D₁. Из вершин А₃ и D₁ возможен единственный переход в вершины А₂ и С₁ соответственно. Суммарные издержки для состояния D₁ равны 28 + 19 = 47; для состояния А₃: 29 + 20 = 49. Из вершины В₃ возможны два варианта перехода:    в вершину А₂ издержки равны 29 + 9 = 38; в вершину В₂ – 13 + 24 = 37.

      Для вершины С₂ возможен переход в вершину В₂ (21 + 24 = 45) и в вершину   С₁ (18 + 28 = 46). Выбираем для вершин В₃ и С₂ наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход, как показано на рис. 5.

        

        

        

        
 

      Рисунок 5 – Сетевая модель операции, шаг 3 

      4-й  шаг. k = 4. Четвертый шаг оптимизации задается сечением по вершинам А₄, В₄, C₃, D₂, Е₁. Из состояний А₄ и Е₁ возможен единственный переход в вершины А₃ и D₁ соответственно, поэтому в вершинах А₄ и Е₁ записываем суммарные издержки:

      А₄А₃: 18 + 49 = 67

      Е₁D₁: 18 + 47 = 65.

      Вершина В₄: В₄А₃: 10 + 49 =59

                            В₄В₃: 13 + 37 = 50.

      Вершина С₃: С₃В₃: 20 + 37 =57

                            С₃С₂: 21 + 45 = 66.

      Вершина D₂: D₂С₂: 19 + 45 =64

                            D₂D₁: 11 + 47 = 58. 
 
 

      

        

        

        

        
 

      Рисунок 6 – Сетевая модель операции, шаг 4 

      5-й шаг. k = 5. На пятом шаге сечение проходит через вершины А₅, В₅, С₄, D₃, Е₂, F₁. Из вершин А₅ и F₁ возможен единственный переход в вершины         А₄ и Е₁ соответственно:

      А₅А₄: 15 + 67 = 82

      F₁Е₁: 16 + 65 = 81.

      Вершина В₅: В₅А₄: 13 + 67 =80

                            В₅В₄: 12 + 50 = 62.

      Вершина С₄: С₄В₄: 18 + 50 = 68

                            С₄С₃: 12 + 57 = 69.

      Вершина D₃: D₃С₃: 18 + 57 = 75

                            D₃D₂: 11 + 58 = 69.

      Вершина Е₂: Е₂D₂: 16 + 58 = 74

                            Е₂Е₁: 15 + 65 = 80. 
 
 
 
 

      

        
 

        

        

        

        

      Рисунок 7 – Сетевая модель операции, шаг 5 

      6-й  шаг. k = 6. Шестой шаг оптимизации задается сечением по вершинам А₆, В₆, C₅, D₄, Е₃, F₂, G₁. Из состояний А₆ и G₁ возможен единственный переход в вершины А₅ и F₁ соответственно, поэтому в вершинах А₆ и G₁ записываем суммарные издержки:

      А₆А₅: 13 + 82 = 95

      G₁F₁: 10 + 81 = 91.

      Вершина В₆: В₆А₅: 14 + 82 =96

                            В₆В₅: 15 + 62 = 77.

      Вершина С₅: С₅В₅: 10 + 62 = 72

                            С₅С₄: 12 + 68 = 80.

      Вершина D₄: D₄С₄: 16 + 68 = 84

                            D₄D₃: 12 + 69 = 81.

      Вершина Е₃: Е₃D₃: 15 + 69 = 84

                            Е₃Е₂: 14 + 74 = 88.

      Вершина F₂: F₂Е₂: 15 + 74 = 89

                            F₂F₁: 12 + 81 = 93.