Решение задач методом динамического программирования

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

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

Реализация  названных принципов дает гарантию того, что, во-первых, решение, принимаемое  на очередном шаге, окажется наилучшим  с точки зрения всего процесса (а не "узких интересов" отдельного этапа) и, во-вторых, последовательность решений одношаговой, двухшаговой и т. п. задач приведет к решению исходной N-шаговой задачи.

Замечание.

В общем случае необходимо учитывать некоторые условия, накладываемые на начальное и конечное состояния системы:  
 
Здесь     -область начальных состояний,   -область конечных состояний. Если состояние системы характеризуется двумя фазовыми переменными     и     то процесс управления представляет собой перемещения точки из     в      
 
 
Рассмотрим несколько примеров многошаговых операций и для каждого из них поясним, что понимается под "управлением" и каков "выигрыш" (показатель эффективности) Z.

Пример 1.

Владелец автомашины эксплуатирует ее в течение m лет. В начале каждого года он может принять одно из трех решений:

Продать машину и заменить ее новой;

Ремонтировать ее и продолжать эксплуатацию;

Продолжать  эксплуатацию без ремонта.

Шаговое управление-выбор одного из этих трех решений. 
Непосредственно числами они не выражаются, но можно приписать первому численное значение 1, второму 2, третьему 3. Какие нужно принять решения по годам (т. е. как чередовать управления 1, 2,3), чтобы суммарные расходы па эксплуатацию, ремонт и приобретение новых машин были минимальны? 
Показатель эффективности (в данном случае это не "выигрыш", а "проигрыш", но это неважно) равен                                               . 
 
где   - расходы в i-м году.

Величину Z требуется обратить в минимум. Управление операцией в целом представляет собой какую-то комбинацию чисел 1, 2, 3, например:     Это означает, что первые два года следует эксплуатировать машину без ремонта, последующие три года ее ремонтировать, в начале шестого года продать, купить новую, затем снова эксплуатировать без ремонта и т. д.  
Управление представляет собой вектор:  
   где каждое из чисел     имеет одно из трех значений: 1, 2 или 3 . Нужно выбрать совокупность чисел так, чтобы величина Z ,была минимальна.

Пример 2.

Метод динамического программирования позволяет с успехом решать экономические задачи. Рассмотрим одну из простейших таких задач:  
В нашем распоряжении имеется какой-то запас средств (ресурсов) К, который должен быть распределен между m предприятиями        Каждое из предприятий     при вложении в него каких-то средств х приносит доход, зависящий от х, т. е. представляющий собой какую-то функцию        Все функции    известны. Спрашивается, как нужно распределить средства К между предприятиями, чтобы в сумме они дали максимальный доход?

Эта задача легко решается методом динамического  программирования. Хотя в своей постановке она не содержит упоминания о времени, можно все же операцию распределения  средств мысленно развернуть в какой-то последовательности, считая за первый шаг вложение средств в предприятие  , за второй-в     и т. д. Управляемая система S в данном случае-средства или ресурсы, которые распределяются. Состояние системы S перед каждым шагом характеризуется одним числом Q - наличным запасом еще не вложенных средств. В этой задаче "шаговыми управлениями" являются средства     , выделяемые предприятиям. Требуется найти оптимальное управление, т. е. такую совокупность чисел     , при которой суммарный доход максимален.

 

 

 

 

2.2 Решение задачи динамического  программирования.

 

Процедура построения оптимального управления методом динамического программирования распадается на две стадии: предварительную и окончательную. 
На предварительной стадии для каждого шага определяется условное оптимальное управление, зависящее от состояния -Q системы (достигнутого в результате предыдущих шагов), и условный оптимальный выигрыш на всех оставшихся шагах, начиная с данного, также зависящий от состояния Q.

На окончательной  стадии для каждого шага определяется окончательное (безусловное) оптимальное  управление. 
Предварительная (условная) оптимизация проводится по шагам, в обратном порядке: от последнего шага к первому; 
Окончательная (безусловная) оптимизация-также по шагам, но в естественном порядке: от первого шага к последнему.

Введем  следующие обозначения:  -условный оптимальный выигрыш, получаемый на всех последующих шагах, начиная с i-го и до конца; 
он достигается при оптимальном управлении на всех этих шагах и равен максимальному выигрышу, который можно получить на всех этих шагах вместе, если перед их началом система находится в состоянии  . 
 -условное оптимальное управление на i-ом шаге, которое, совместно с оптимальным управлением на всех последующих шагах, обращает выигрыш на всех шагах, начиная с данного, в максимум. 
Поставим задачу - построить алгоритм определения функций условного оптимального выигрыша     и условного оптимального управления     для всех шагов     Рассмотрим i-ыи шаг процесса управления. Пусть в результате i-1 предыдущих шагов система пришла в состояние     , и мы выбираем какое-то управление     на i-ом шаге. Если мы его применим, то, во-первых, получим на данном i-ом шаге какой-то выигрыш     Он зависит от состояния системы Q так и от управления : 
       (1) 
Кроме того, мы получим какой-то выигрыш на всех оставшихся шагах. На основании принципа оптимальности, будем считать, что он максимален. Чтобы найти этот выигрыш, мы должны знать состояние системы перед следующим, (i+1)-м шагом. Под влиянием управления        на i-ом шаге система из состояния Q   (в котором она была перед этим шагом) перейдет в какое-то новое состояние     Это новое состояние будет зависеть, опять-таки, от прежнего состояния Q и примененного управления  
    (2) 
Запишем выигрыш, который мы получим на всех шагах, начиная с i-го, если на i-ом шаге будет применено любое (возможно, не оптимальное) управление   а на всех последующих (i+1)-го до N-го оптимальное управление. 
Этот выигрыш будет равен выигрышу zi на данном i-ом шаге, плюс условный оптимальный выигрыш на всех последующих шагах, начиная с (i+1)-го, определяемый для нового состояния системы  ; 
  (3) 
обозначим такой "полуоптимальный" выигрыш через     тогда учитывая (2) и (3),                                                            . 
  (4) 
Теперь, в соответствии с принципом оптимальности, мы должны выбрать такое управление   при котором величина (4) максимальна и достигает значения: 
  (5) 
То управление     при котором этот максимум в (5) достигается, и есть условное оптимальное управление на i-ом шаге, а сама величина (5)-условный оптимальный выигрыш (на всех шагах, начиная с i-го и до конца). В уравнении (5) функции     и     известны. Неизвестными остаются функции:

   и     ; из них первая выражается через вторую. Формула (5) представляет собой так называемое основное функциональное уравнение динамического программирования илиуравнение Беллмана. Оно позволяет определить функцию Zi(Q) , если известна следующая за ней по порядку   
Что касается функции   (условный оптимальный выигрыш на последнем шаге), то она может быть определена очень просто. 
Действительно, за последним шагом нет следующего, и нужно обратить в максимум выигрыш на этом шаге:  
  (6)  
Максимум в формуле (6) берется не по всем возможным управлениям XN на N-ом шаге, а только по тем, которые приводят в систему в заданную область  т.е. по тем, для которых    Это всегда нужно иметь в виду при использовании формулы (6). То управление     при котором достигается максимум выигрыша, и есть условное оптимальное управление на последнем шаге.

Теперь  построим всю цепочку условных оптимальных  управлений. Зная   можно по общей формуле (5), полагая в ней i+1=n , найти функцию   и соответствующее оптимальное управление  ; затем   и   и так далее , вплоть до последнего шага от конца т.е. первого шага, для которого будут найдены функции Z1(Q) и X1(Q) . Функция Z1(Q) есть условный оптимальный выигрыш за всю операцию, т.е. на всех шагах начина с первого и до последнего (если первый шаг начинается с определенного состояния Q1). 
Таким образом предварительная оптимизация закончена-найдены условный оптимальный выигрыш и условное оптимальное управление для каждого шага.

Рассмотрим  вторую стадию оптимизации-нахождение безусловного или окончательного оптимального управления    

  Начнем с первого шага.

Предположим, что исходное состояние Q1 нам полностью  известно. Подставим это состояние Q1 в формулу для условного оптимального выигрыша Z1(Q). Получим: 
  (7) 
Одновременно найдем оптимальное управление на первом шаге     Далее, зная исходное состояние Q1 и управление X1 , можем найти состояние   системы после первого шага:    Зная это состояние   можно найти оптимальное управление на втором шаге     затем     и т. д. Таким образом, идя по цепочке 
  (8) 
мы определили одно за другим, все шаговые оптимальные управления операций в целом     а также конечное состояние системы     Это условие будет выполняться, т.к. мы выбираем управление на последнем шаге так, чтобы     Рассмотрим теперь случай, когда исходное состояние системы ограничено условием  .   В этом случае нужно найти такое начальное состояние   при котором условный минимальный выигрыш за все шаги максимален. 
  (9) 
То начальное состояние   для которого этот максимум достигается и нужно взять в качестве исходного. Далее оптимальное управление строится в соответствии с выражением (8), заменяя Q1 на    
  (8a) 
При изложении материала мы использовали систему символических формул, которая непригодна для непосредственного вычисления. Однако с их помощью можно организовать процедуру динамического программирования в следующей последовательности:

Выбрать способ описания процесса, т.е. параметры  характеризующие состояние системы, фазовое пространство и способ деления  операции на шаги.

Записать  выигрыш на i-ом шаге в зависимости от состояния системы Q перед этим шагом и управления Xi    

Записать  для i-го шага функцию, выражающую изменение  состояния системы от Q к Q` под  действием управления Q` 
  

Записать  основное функциональное уравнение 
  (5)

Найти условный оптимальный выигрыш последнего N-го шага     при этом должно выполняться условие     Одновременно определить условное оптимальное управление Xn(Q) на последнем шаге.

Зная  Zn(Q) по уравнению (5) для конкретного вида функций Zi(Q,Xi) и найти   последовательно Wn-1(Q),Wn-2(Q),:,W1(Q) и соответствующие им условные оптимальные уравнения 

Если  начальное состояние системы Q1 задано, найти оптимальный выигрыш Zmax=Z1(Q1) и безусловные оптимальные управления в последовательности, указанной  выражением (8).

Если  начальное состояние Q1 задано условием     то для определения Zmax нужно использовать выражение (9). Определение безусловных оптимальных управлений провести по схеме (8а).

 

Отметим преимущества и недостатки метода динамического программирования. К числу положительных качеств можно отнести:

МДП дает возможность решать задачи, которые  раньше не исследовались из-за отсутствия соответствующего математического  аппарата.

МДП в  ряде случаев сокращает объем  при поиске оптимальных решений.

К недостаткам  относятся:

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

Трудности при решении задач большой  размерности.

 

 

 

 

 

 

 

 

 

 

 

 

ПРАКТИЧЕСКАЯ  ЧАСТЬ.

Задача о распределении инвестиций.

 

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

 

Инвестиции, млн.руб.	Прирост выпуска продукции, млн.руб.
	Предприятие 1	Предприятие 2	Предприятие 3	Предприятие 4
50	15	12	17	13
100	32	30	33	31
150	39	38	40	37
200	46	45	47	44
250	52	54	60	63