Динамическое программирование - rita.netnado.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Динамическое программирование - страница №1/1

Глава 10 ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

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

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

В общем случае задача динамического программирова­ния формулируется следующим образом. Пусть данная физи­ческая система S находится в некотором начальном состоя­нии So и является управляемой. Благодаря осуществлению
некоторого управления uU указанная система переходит из
начального состояния Б„ в конечное состояние S. При этом, качество каждого из реализуемых управлений uU характе­ризуется соответствующим значением функции W(u). Задача состоит в том, чтобы из множества возможных управлений uU найти такое u*U, при котором функция W(u) принима­ет экстремальное значение W(u*).

Экономическую интерпретацию общей задачи динамичес­кого программирования рассмотрим на следующих примерах.



Задача 1. Для осуществления своей эффективной деятель­ности производственные объединения и предприятия долж­ны периодически проводить замену используемого ими оборудования. При этой замене учитываются производительность используемого оборудования, затраты, связанные с содер­жанием и ремонтом, стоимость приобретаемого и заменяемого оборудования. Предположим, что к началу текущей пяти­летки на предприятии установлено новое оборудование. За­висимость производительности этого оборудования от време­ни его использования предприятием, а также зависимость затрат на содержание и ремонт оборудования при различном времени его использования приведены в табл. 10.1.

Таблица 10.1




Время t, в течение которого используется оборудование, лет

0

1

2

3

4

5

Годовой выпуск продукции R(t) в стоимостном выражении, тыс. руб.

80

75

65

60

60

55

Ежегодные затраты Z(t), связанные с содержанием и ремонтом оборудования, тыс. руб.

20

25

30

35

45

55

Зная, что затраты, связанные с приобретением и уста­новкой нового оборудования, идентичного с установленным, составляют 40 тыс. руб., а заменяемое оборудование списы­вается, составить такой план замены оборудования в течение пятилетки, при котором общая прибыль за данный период времени максимальна.

Эту задачу можно рассматривать как задачу динамичес­кого программирования, в которой в качестве системы S выступает оборудование. Состояния этой системы определяются фактическим временем использования оборудования (его возрастом) т, т.е. описываются единственным параметром . В качестве управлений выступают решения о замене и сохранении оборудования, применяемые в начале каждого года. Обозначим через С решение о сохранении оборудования, а через 3 — решение о замене оборудования. Тогда задача состоит в нахождении такой стратегии управления, опреде- ляемой решениями, применяемыми к началу каждого года, при которой общая прибыль предприятия за пятилетку является максимальной.

Общая прибыль предприятия за пятилетку составляется из ежегодной прибыли предприятия за каждой год пятилет­ки, т.е. если u1v u2, ..., u5 — управления, применяемые в начале каждого года, W(τi;ui) — прибыль предприятия за i-й год пятилетки, то

W(u)=

где u = (u1, u2, u3, u4, u5), τi — возраст оборудования в начале i-го года пятилетки,

[ R(τ,)-Z<t,) при ui = С,

I R(0) - Z(0) - 40 при ui = 3.

Например, если u = (С, 3, С, С, С), то

W(u) = W1 (C,0) + W2(3,0) + W3(C, 1) +W4(C, 2) + + W5(C, 3) =(R(0) - Z(0))+(R(0) - Z(0) - 40)+(R(l) -- Z(1))+(R(2) - Z(2))+(R(3) - Z(3))= 60 + 20 + 50 + 35 + + 25 = 190 тыс. руб.

Задача 2. Для увеличения объемов выпуска пользующейся повышенным спросом продукции, изготовляемой предприя­тиями, выделены капиталовложения в объеме А тыс. руб. Использование i-ым предприятием (i = l,n) xi тыс. руб. из указанных средств обеспечивает прирост выпуска продук­ции, определяемой значением функции fi(xi). Требуется най­ти распределение капиталовложений между предприятия­ми, обеспечивающее максимальное увеличение выпуска продукции.

Эту задачу можно рассматривать как многоэтапную, если исследовать эффективность вложения средств на одном пред­приятии, на двух предприятиях и т.д., наконец, на n предприятиях. Таким образом, получим n этапов, на каждом из которых состояние системы {в качестве которой выступают предприятия) описывается объемом средств, подлежащих освоению к предприятиями (к =1,п). Решения об объемах ка­питаловложений хk, выделяемых k-му предприятию, и явля­ются управлениями. Задача состоит в выборе таких управле­ний, при которых функция



принимает наибольшее значение.



10.2. Алгоритм решения задач методом динамического программирования

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

Будем считать, что. состояние рассматриваемой системы S на k-ом шаге (k = 1,п) определяется совокупностью чисел x(k) = (х1(k),…хm(k)), которые получены в результате реали­зации управления uk, обеспечивающего переход системы S из состояния x(k-1) в состояние х(k).

Будем предполагать, что состояние х(k), в которое пере­шла система S, зависит от данного состояния х(k-1) и выбран­ного управления Uk и не зависит от того, каким образом си­стема S перешла в состояние x(k-1).

Далее, будем считать, что если в результате реализа­ции k-го шага обеспечен определенный доход, также завися­щий от исходного состояния системы х(k-1) и выбранного уп­равления Uk, равный Wk (x(k-1); uk), то общий доход за n шагов составляет

,

где u = (u1, u2, ..., un).

Таким образом, сформированы два условия, которым должна удовлетворять рассматриваемая задача динамичес­кого программирования. Первое условие обычно называют условием отсутствия последействия, а второе — условием аддитивности целевой функции задачи.

Задача состоит в нахождении оптимальной стратегии уп­равления, т.е. такой совокупности управлений u* = (u1* , ..., un*), в результате реализации которых система S за n шагов переходит из начального состояния х(о) в конечное x(n) и при этом функция дохода W(u) принимает наибольшее значение.



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

Из принципа оптимальности следует, что оптимальную стратегию управления можно получить, если сначала найти оптимальную стратегию управления на n-м шаге, затем на двух последних шагах, затем на трех последних шагах и т.д., вплоть до первого шага. Таким образом, решение рассматри­ваемой задачи динамического программирования целесообраз­но начинать с определения оптимального решения на после­днем, n-м шаге. Для того чтобы найти это решение, очевид­но, нужно сделать различные предположения о том, как мог окончиться предпоследний шаг, и с учетом этого выбрать управление un° , обеспечивающее максимальное значение функции дохода Wn(x(n-1);un),. Такое управление, выбранное при определенных предположениях о том, как окончился предыдущий шаг, называется условно оптимальным управ­лением. Следовательно, принцип оптимальности требует на­ходить на каждом шаге условно оптимальное управление для любого из возможных исходов предшествующего шага.

Чтобы построить алгоритм решения задач, дадим мате­матическую формулировку принципа оптимальности, Для этого введем некоторые дополнительные обозначения. Обозначим через Fo(x(o)) максимальный доход, получаемый за n шагов при переходе системы S из начального состояния х(о) в ко­нечное состояние х(n) при реализации оптимальной стратегии управления u* = (u1* , ..., un*), а через Fk(x(k)) — максималь­ный доход, получаемый при переходе из любого состояния х(к) в конечное состояние х(n) при оптимальной стратегии уп­равления на оставшихся (n-k) шагах. Тогда

Fo(x(n-1)) = [W1(x(0),u1)+ ... + Wn(x(n), un], (10.1)

Fk(x(k)) = [Wk+1(x(k+1),uk+1)+ Fk+1 (x(k+1))] (10.2)

при k = o,n-l.

Выражение (10.2) представляет собой математическую запись принципа оптимальности Беллмана и носит название основного функционального уравнения Беллмана. Используя уравнение (10.2) находится решение рассматриваемой зада­чи динамического программирования. Рассмотрим этот про­цесс более подробно.

Полагая k=n-1 в уравнения Беллмана (10.2), получим следующее функциональное уравнение:

Fn-1 (x (n-1)) = [Wn(x (n-1) ,un)+ Fn(x(n))]. (10.3)

В уравнении (10.3) Fn (x(n)) можно считать известным. Ис­пользуя теперь уравнение (10.3) и рассматривая всевозмож­ные допустимые состояния системы S на (n-1)-ом шаге x1(n-1), х2 (n-1),…,xn (n-1) ,… находим условные оптимальные решения

uno (x1(n-1)), uno2 (n-1)),…, uno (xn (n-1) ) и соответствующие значения функции (10.3)

Fn-1o (x1(n-1)), Fn-1o2 (n-1)),…, Fn-1o (xn (n-1) )

Таким образом, на n-ом шаге находим условно оптималь­ное управление при любом допустимом состоянии системы S после (n-l)-гo шага, т.е. в каком бы состоянии система не оказалась после (n-l)-гo шага, нам уже известно, какое сле­дует принять решение на n-м шаге.

Перейдем теперь к рассмотрению функционального урав­нения при k=n-2:

Fn-2(x (n-2)) = max[Wn-1(x(n-2), un-1)+ Fn-1 (x(n-1))]. (10.4)
Решая функциональное уравнение (10.4) при различных состояниях на (n-2)-ом шаге, получим условно оптимальные управления un-1o(xi(n-2), i=1,2,.... Каждое из этих управлений совместно с уже выбранным управлением на последнем шаге обеспечивает максимальное значение дохода на двух после­дних шагах.

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

Чтобы найти оптимальную стратегию управления, т.е. определить искомое решение задачи, нужно теперь пройти всю последовательность шагов, только на этот раз от начала к концу. А именно: на первом шаге в качестве оптимального управления

u1* возьмем найденное условно оптимальное уп­равление u1° . На втором шаге найдем состояние x1*, в кото­рое переводит систему управление u1*. Это состояние опре­деляет найденное условно оптимальное управление u2o, ко­торое теперь будем считать оптимальным. Зная u2*, находим х2* а значит, определяем u3* и т.д. В результате этого нахо­дим решение задачи, т.е. максимально возможный доход и оптимальную стратегию управления, включающую оптималь­ные управления на отдельных шагах.

Из изложенного видно, что этот процесс является до­вольно громоздким. Однако использование ЭВМ позволяет находить на основе метода динамического программирования решение и более сложных практических задач.

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



10.3. Решение задач

Решение задачи 1.

Состояние системы к началу k-го года определяется фак­тическим временем использования оборудования (его возрас­том) τ(k). В качестве управлений, как уже говорилось в 10.1, выступают решения о замене (uk = 3) и сохранении (uk = С) оборудования. Отметим также, что задача обладает свойствами аддитивности и отсутствия последействия. Решая задачу ме­тодом динамического программирования, на первом этапе при движении от начала 5-го года пятилетки к началу 1-го года для каждого допустимого состояния оборудования найдем условное оптимальное управление, а на втором этапе при движении от начала 1-го года пятилетки к началу 5-го года из условных оптимальных решений для каждого года соста­вим оптимальный план замены оборудования на пятилетку.

Так как (см. 10.1) прибыль предприятия за k-ый год пяти­летки (k=1,...,5) составит

,

то уравнение Беллмана имеет вид


(10.5)

Используя уравнение Беллмана, определим условно оп­тимальные решения для последнего (5-го) года пятилетки, в связи с чем находим множество допустимых состояний обо­рудования к началу данного года. Так как к началу пятилетки имеется новое оборудование (τ(1) = 0), то возраст оборудова­ния к началу 5-го года может составлять 1, 2, 3 и 4 года. Поэтому допустимые состояния системы на данный период времени таковы τ1(5) = 1, τ2(5) = 2, τ3(5) = 3, τ4(5) = 4 .

Для каждого из этих состояний найдем условно опти­мальное решение и соответствующее значение функции F5(5)).

Из (10.5) и соотношения F6(τ (6)) = 0 (так как рассматри­вается последний год расчетного периода) следует



Подставляя в полученную формулу вместо τ(5)его зна­чения и учитывая данные таблицы 10.1, находим









Полученные результаты вычислений сведем в табл. 10.2.



Таблица 10.2

Возраст оборудования,

τ(5) лет



Значения функции дохода F5, тыс, руб.

Условно оптимальное решение

1

50

С

2

35

С

3

25

С

4

20

3

Рассмотрим теперь возможные состояния оборудования к началу 4-го года пятилетки. Очевидно, допустимыми состо­яниями являются τ(4) = 1, τ(4)= 2, τ(4)= 3. Для каждого из них определяем условно оптимальное решение и соответству­ющее значение функции F4(τ(4)). Для этого используем урав­нение (10.5) и данные табл. 10.1 и табл. 10.2. Имеем:





Полученные результаты вычислений сведем в табл. 10.3.



Таблица 10.3

Возраст оборудования,

τ(5)



Значения функции дохода F4, тыс. руб.

Условно оптимальное

решение


1

85

С

2

70

С

3

70

3

Определим теперь условно оптимальное решение каждого из допустимых состояний оборудования к началу 3-го года пятилетки. Очевидно, такими состояниями явля­ются τ1(3) = 1 и τ2(3) = 2. В соответствии с уравнением (10.5)

имеем:




Полученные результаты вычислений сведем в табл. 10.4.



Таблица 10 .4

Возраст оборудования,

τ (3) лет



Значения функции дохода F3,тыc. руб.

Условно оптимальное решение

1

120

С

2

105

3

Наконец, к началу 2-го года пятилетки возраст оборудо­вания может быть равен только лишь одному году. Поэтому

Так как к началу пятилетки установлено новое оборудо­вание (τ1(1) =0), то

F1(0) - R(0) - Z(0) + F2(l) = 80-20+155 = 215. Просматривая полученные результаты в обратном по­рядке» получим: для 1-го года пятилетки решение единствен­но — следует сохранить оборудование. Значит, возраст обо­рудования к началу 2-го года пятилетки равен одному году. Тогда оптимальным решением для 2-го года пятилетки яв­ляется решение о сохранении оборудования. Реализация та­кого решения приводит к тому, что возраст оборудования к началу 3-го года пятилетки становится равным двум годам. При таком возрасте (см. табл. 10.4) оборудование следует заменить. После замены оборудования его возраст к началу 4-го года пятилетки составит один год. Как видно из табл. 10.3, при таком возрасте оборудования его менять не следует. По­этому возраст оборудования к началу 5-го года пятилетки со­ставит два года, а значит, согласно табл. 10.2, оборудование менять нецелесообразно.

Итак, получается следующий оптимальный план замены оборудования (табл. 10.5).



Таблица 10 .5




Годы пятилетки




1

2

3

4

5

Олтимальное решение

Сохранить

оборудо­вание



Сохранить

оборудо­вание



Произвести замену обо­рудования

Сохранить

оборудо­вание



Сохранить

оборудо­вание


Максимальная прибыль предприятия равна 215 тыс.руб.

Общая схема возможных состояний системы и управле­ний за пятилетку с указанием дохода за каждый год пятилет­ки приведена на рис. 10.1.

Решение задачи 2. Решим задачу при А = 700 тыс. руб., n = 3 (число предприятий). Значения функций fi приведены в табл. 10.6.

Таблица 10.6

Объем

капиталовложений

Xi, тыс.руб.


Прирост выпуска продукции fi (Xi) в зависимости от объема капиталовложений, тыс.руб.

Предприятие 1

Предприятие 2

Предприятие 3

0

0

0

0

100

30

50

40

200

50

80

50

300

90

90

110

400

110

150

120

500

170

190

180

600

180

210

220

700

210

220

240

Задача состоит в определении таких капиталовложений x1*, x2*, x3*, которые максимизируют прирост выпуска продукции, т.е. функции и удовлетворяют условию .

Для решения задачи составим уравнения Беллмана:

F3(X (3)) = f3(x3), x3 = Х (3),

где Х(3) — допустимое состояние на 3-м шаге, т.е. остаточ­ный объем капиталовложений на 3-м предприятии;

F2(X'2)) = max (f2(x2) + F3(X (3))),

0≤x2≤X(2)

где Х(2) -допустимое состояние на 2-ом шаге, т.е. остаточный объем капиталовложений на 2-ом предприятии, Х(3) = Х(2) - х2;

F 1(X(1)) = max (f (x1) + F2(X (2))),

0≤x1≤X(1)

где X(1) — допустимое состояние на 1-м шаге, т.е. остаточ­ный объем капиталовложений на 1-м предприятии, Х(2) = X(1) – x1, X (1) = А.

Таким образом, значения функции F3 находятся из табл. 10.6 по значениям функции f3.

Допустимые состояния на 2-ом шаге могут быть:

x0(2)=0; х1(2)=100; x2 (2)=200; xз(2)=300; x4(2) =400; x5(2) =500; x6 (2)=600; х7(2)=700.

Тогда
F2(0)=f2(0)+F3(0);












Допустимое состояние на 1-ом шаге может быть только x(1)=700.

Тогда

Таким образом, max W = 270 и оптимальное распределе­ние капиталовложений следующее: x1* = 0; x2* = 100; х3* = 600.