Лабораторные работы по Методам Оптимизации

 

Введение.

   Динамическое  программирование – метод оптимизации, в котором процесс принятия решения и управления может быть разбит на отдельные этапы (шаги).

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

   К основным задачам динамического  программирования относятся:

         - оптимальная стратегия  замены оборудования;

         - оптимальное распределение ресурсов;

         - распределение   инвестиций   для   эффективного   использования потенциала предприятия;

         - минимизация затрат  на строительство и эксплуатацию  предприятий; нахождение рациональных  затрат при строительстве трубопроводов  и транспортных артерий и т.д.

Постановка  задачи.

    Совет директоров фирмы рассматривает  предложения по наращиванию производственных мощ –ностей для увеличения выпуска  однородной продукции на четырех  предприятиях, принадлежащих фирме. Для модернизации предприятий совет  директоров инвестирует средства в объеме 250 млн. рублей с дискретностью 50 млн. рублей. Прирост выпуска продукции зависит от выделенной суммы, его значения представлены в таблице. 

 

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

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

   В нашем распоряжении имеется какой-то запас средств (или ресурсов) К, который должен быть распределен между предприятиями P₁, P₂, ..., P_m. Каждое из предприятий P_i при вложении в него каких-то средств x приносит доход, зависящий от x, то есть представляющий собой какую-то функцию f_i(x). Все функции f_i(x), где i = 1, 2, ..., m, заданы (разумеется, эти функции – неубывающие). Нужно найти, как распределить средства К между предприятиями, чтобы в сумме они дали максимальный доход?

   Обозначим через x_k количество средств, выделенных k-му предприятию. Тогда суммарная прибыль равна

 
 

Переменные x удовлетворяют ограничениям

 
 x_k ≥ 0, k = 1, 2, 3, 4

   Процесс распределения средств рассматриваем как 4-шаговый, номер шага совпадает с номером предприятия. Уравнения состояний в данной задаче имеют вид:

   

= – , k = 1, 2, 3, 4

где s_k (параметр состояния) – количество средств, оставшихся после k-го предприятия, то есть средства, которые останется распределить между оставшимися 4-k предприятиями.

   Введем  в рассмотрение функцию ( ) – условную оптимальную прибыль, полученную от k-го, (k + 1)-го, …, 4-го предприятий, если между ними распределялись оптимальным образом средства

S_{k –1}(0 ≤ S_{k –1} ≤ 5)

   Допустимые  управления на k-м шаге удовлетворяют: 0 ≤ x_{k –1} ≤ 5 (либо k-му предприятию ничего не выделяем, x_k = 0, либо не больше того, что имеем к k-му щагу, x_k ≤ S_{k –1}).

   Уравнения Беллмана имеют вид:

                                                        k = 4, S₄ = 0         (s₃) =                        , 
 
                                                       (s₂) =                         (s₃)  

                                                   (s₁) =                         (s₂)  

                                                 (s₀ = 5) =                         (s₂)  

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

   Опишем  подробно процесс заполнения данной таблицы. Хотя наша задача в своей постановке она не содержит упоминания о времени, можно все же операцию распределения средств мысленно развернуть в какой-то последовательности, считая за первый шаг вложение средств в предприятие П₁, за второй – в П₂ и так далее.

   Управляемая система S в данном случае – средства или ресурсы, которые распределяются. Состояние системы S перед каждым шагом характеризуется одним числом S – наличным запасом еще не вложенных средств. В этой задаче шаговыми управлениями являются средства x₁, х₂, ..., х_m,  выделяемые предприятиям. Требуется найти оптимальное управление, то есть такую совокупность чисел x₁, х₂, ..., х_m, при которой суммарный доход максимален:

   Найдем  для каждого k-го шага условный оптимальный выигрыш (от этого шага и до конца), если мы подошли к данному шагу с запасом средств S. Обозначим условный оптимальный выигрыш (S), а со –ответствующее ему условное оптимальное управление – средства, вкладываемые в k-e предприятие, – (S). 
 

   Начнем  оптимизацию с последнего, m-го шага. Пусть мы подошли к этому шагу с остатком средств S. Что нам делать? Очевидно, вложить всю сумму S целиком в предприятие P_m. Поэтому условное опти –

мальное управление на m-м шаге: отдать последнему предприятию все имеющиеся средства S, то есть:

(S) = S

а условный оптимальный  выигрыш

(S) = (S)

   Задаваясь целой гаммой значений S (располагая их достаточно тесно), мы для каждого значения S будем знать х_m(S) и W_m(S). Последний шаг оптимизирован.

   Перейдем  к предпоследнему, (m – 1)-му шагу. Пусть мы подошли к нему с запасом средств S. Обозначим через W_{m – 1}(S) условный оптимальный выигрыш на двух последних шагах: (m – 1)-м и m-м (который уже оптимизирован). Если мы выделим на (m – 1)-м шаге (m – 1)-му предприятию средства х, то на последний шаг останется S – х. Наш выигрыш на двух последних шагах будет равен:

(х) + (S – х)

и нужно  найти такое х, при котором этот выигрыш максимален: 

                                       (S) =                   (x) + (S – x)

   Знак  max означает, что берется максимальное значение по всем х, какие только возможны (вложить больше, чем S, мы не можем), от выражения, стоящего в фигурных скобках. Этот максимум и есть услов –ный оптимальный выигрыш за два последних шага, а то значение х, при котором этот максимум достига –ется – условное оптимальное управление на (m – 1)-м шаге. Далее оптимизируем (m – 2)-й, (m – 3)-й и так далее. Вообще, для любого k-го шага будем находить условный оптимальный выигрыш за все шаги с этого и до конца по формуле