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

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




Скачати 359.48 Kb.
Назва6. Динамическое программирование
Дата06.09.2012
Розмір359.48 Kb.
ТипДокументи

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


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

Характерным для динамичного программирования является поэтапный (много-шаговый) процесс решения оптимизационной задачи.

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

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


^ 6.1. Математическая модель задачи и суть метода динамического программирования

Пусть некоторая операция состоит из m этапов (шагов), и эффективность операции характеризуется показанием (критерием) L, который для краткости будем называть “доходом”.

Предположим, что доход L за всю операцию складывается из доходов на отдельных шагах:

, (6.1.)

где - доход на i-м шаге.

Если L обладает таким свойством, его называют “аддитивным показателем”.

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

Обозначим управление операцией в целом, через вектор x=||x1, x2, ..., xm||, где хi - управление на i-м шаге, которое, в общем случае, может быть тоже вектором или функцией, а не только числом.

Требуется найти такое управление х, при котором доход L обращается в максимум:

.

То управление х*, при котором этот максимум достигается называется оптимальным управлением. Оно состоит из совокупности оптимальных шаговых управлений: .

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

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

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

3) продолжать эксплуатацию.

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

Показатель эффективности (в данном случае это расходы) равен:

,

где - расход на машину в i-м году, необходимо обратить в минимум.

Управление операцией в целом представляет собой какую-либо комбинацию чисел 1, 2, 3, например:

x=(3, 3, 2, 2, 2, 2, 3, 1, 3 ...),

что означает первые два года эксплуатировать машину без ремонта, последующие четыре года ее ремонтировать, седьмой год - не ремонтировать, а в начале восьмого - продать, купить новую, затем снова эксплуатировать без ремонта и т.д. Нужно выбрать совокупность чисел 1, 2, 3, при которой величина (6.1) минимальна.

Пример 2. Планируются инвестиции в группу фирм Ф1, Ф2, ..., Фk на период m лет. В начале на все инвестиции выделено M гривен. В процессе деятельности фирм часть получаемого от инвестиций дохода вновь инвестируется в эти фирмы. Ставится вопрос: какое количество средств в начале каждого года инвестировать в каждое предприятие, чтобы суммарный доход за m лет был максимальным.

Суммарный доход представляет собой сумму доходы на отдельных шагах (годах):

,

и значит обладает свойством аддитивности. Управление хi на i-м шаге состоит в том, что вначале i-го года в фирмы инвестируются какие-то средства хi=||x11, x12, ..., x1k||, где xij - средства инвестируемые на первом году в j-ю фирму. Таким образом, шаговое управление в данном случае, есть векторное, а в предыдущем примере оно выражалось просто числом.

Требуется найти такое распределение средств по годам:



при котором величина L обращается в максимум?

Пример 3. Прокладывается участок дороги между пунктами А и В (рис.6.1). Пересеченная местность, включает горы, леса, болота, реку. Требуется так провести дорогу из А в В, чтобы суммарные затраты на сооружение дороги были минимальными.

A

B

Рис. 6.1.


В этой задаче, в отличие от трех предыдущих, нет естественного разделения на шаги (года); его приходится вводить искусственно, для чего, например, можно отрезок АВ разделить на m частей, провести через точки деления прямые перпендикулярные АВ, и считать, за шаг переход с одной прямой на другую. Шаговое управление на i-м шаге представляет собой угол i, которой составляет участок пути с прямой АВ.

Требуется выбрать такое управление x=||1, 2, .. m||, при котором суммарные затраты на сооружение всех участков дороги минимальны.

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

Управление на i-м шаге выбирается не так, чтобы выигрыш именно на данном шаге был максимален, а так, чтобы была максимальна сумма выигрышей на всех оставшихся до конца шагах плюс данный.

Однако из этого правила есть исключение. Среди всех шагов есть один, который можно планировать без оглядки на будущее. Это - последний шаг, который можно планировать так, чтобы он сам, как таковой, принес наибольшую выгоду.

Поэтому в динамическом программировании широко используется алгоритм обратной прогонки, который предписывает начинать вычисления с последнего этапа, а затем “двигаться” назад до этапа 1. Но планируя последний шаг, нужно сделать разные предположения о том, чем закончится предпоследний (m-1)-й шаг, и для каждого из этих предположений найти условное оптимальное управление на m-м шаге (“условное” потому, что оно выбирается исходя из условия, что предыдущий шаг кончится так-то и так-то). Далее делаются возможные предположения о том, чем кончится (m-2)-й шаг и определяются условное оптимальное управление на (m-1)-м шаге и условный оптимальный доход на двух последних шагах.

Когда все условные оптимальные управления и условные оптимальные доходы за весь процесс станут известны, то сразу получаем оптимальное управление х* и оптимальный доход L*, “проходя” уже процесс управления от первого шага к последнему по уже полученным условно оптимальным управлениям. Проиллюстрируем суть метода динамического программирования на примерах решения конкретных задач.


^ 6.2. Примеры решения задач динамического программирования.

1. Прокладка наивыгоднейшего пути между двумя пунктами.

Требуется соорудить путь соединяющий два пункта А и В. Для простоты допустим, что при прокладке пути можно двигаться либо строго на восток, либо строго на север. Затраты на сооружение каждого из отрезков известны (стоимость в условных единицах поставлено на каждом отрезке на рис. 6.2).




Север


6 3 3 2 1 11 7 В

9 5 2 9 3 9 1 2

4 5 2 4 5 7 7

4 1 4 6 6 8 2 7

3 1 5 7 4 4 8

8 2 3 3 8 4 3 6

5 8 5 1 2 3 4

6 7 2 9 3 5 4 5

1 4 4 5 6 2 3

3 5 1 2 5 2 5 1

А 8 2 4 2 7 1 2 х, Восток

Рис.6.2.

Требуется проложить такой путь из А в В, при котором суммарные затраты минимальны.

Целенаправленный организованный поиск оптимального решения, обеспечиваемый динамическим программированием, имеет большие преимущества перед пассивным “слепым” перебором всех возможных вариантов.

Будем использовать алгоритм обратной прогонки. В точку ^ В можно попасть только из точек В1 и В2. Запишем стоимости прокладки отрезков из этих точек в точку В в кружках в этих точках (рис.6.3). Оптимальное управление из этих точек покажем строчками.

с1 В1

1 18 11 7 7 В


9 1 2




5 15 7 8 7 2 В2

с2

8 2 7




14 4 10 8 9




с3

Рис. 6.3.


Очевидно, что из точки В1 у нас вынужденное движение только на восток, а из точки В2 - только на север. Таким образом условная оптимизация последнего шага сделана, и условная оптимальная стоимость для каждой из точек В1 и В2 записана в соответствующем кружке. Предпоследний шаг мог бы сделан из точек С1, С2 и С3. Найдем для каждой из них условное оптимальное управление (покажем его стрелкой из соответствующей точки) и условную оптимальную стоимость (цифра будет поставлена внутри соответствующего кружка). Для точки с1 управление вынужденное: идти на восток; стоимость из этой точки до конечной точки В составит 18 единиц. Это число записывает в кружке при точке С1. Для точки С2 управление уже не вынужденное: можно идти или на север, или на восток. В первом случае затраты составят одну единицу и от В, еще 7 единиц, всего 8 единиц. Если пойдем на восток затратим 7+2=9 единиц. Значит условно оптимальное управление в точке С2 - идти на север (отмечаем это стрелкой, а число 8 записываем в кружке точки С2).

Для точки ^ С3 управление снова вынужденное (ставим стрелку строго на север и записываем число 7+2=9 единиц в кружке при С3).

Аналогично, “пятясь” от предпоследнего шага назад, найдем для каждой точки условно оптимальное управление, которое обозначается стрелкой, и условные оптимальные расходы, записанные в кружке. Вычисляются они так: расход на данном шаге складывается с уже оптимизированным расходом, записанным в кружке, куда ведет стрелка. Таким образом, на каждом шаге мы оптимизируем только этот шаг, а следующие за ним - уже оптимизированы. Конечный результат процедуры оптимизации показан на рис. 6.4.

В кружке при точке А записаны оптимальные расходы на все сооружения пути из А в В: L*=34.



Рис. 6.4.

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

х*=||C, B B, C, B, B, B, B, C, C, C, B||

где С - шаг на север; В - шаг на восток.

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

Если бы мы пытались решить задачу “наивным” способом: выбирать на каждом шаге, начиная с первого, самое выгодное только для этого шага направление, то получили бы:

х=||C, B B, C, C, C, B, B, C, B, B, B||

Расходы для такого решения будут равны

L=2+1+4+2+3+4+2+4+3+1+11+7=45,

что больше, чем L*=34. В данном случае разница не очень велика, но в других случаях она может быть существенной.

Заметим, что в данной задаче точки А и В (начало и конец) в принципе ничем друг от друга не отличаются, поэтому можно было бы использовать и алгоритм прямой прогонки (строить условно оптимальные управления не с конца к началу, а с начала к концу, а безусловные - в обратном направлении).


2. Задача распределения ресурсов

В распоряжение имеются запас средств (ресурс) К=10 (условных единиц), который может быть распределен между m=5 фирмами П1, П2, ..., П5. Каждая из фирм при вложении в нее х единиц ресурса дает доход i(х), i=1,5, представленный в таблице 6.1.

Таблица 6.1.

х

f(х)

f2(х)

f3(х)

f4(х)

f5(х)

1

0.5

0.1

0.6

0.3

1.0

2

1

0.5

1.1

0.6

1.2

3

1.4

1.2

1.2

1.3

1.3

4

2

1.8

1.4

1.4

1.3

5

2.5

2.5

1.6

1.5

1.3

6

2.8

2.9

1.7

1.5

1.3

7

3.0

3.5

1.8

1.5

1.3

8

3.0

3.5

1.8

1.5

1.3

9

3.0

3.5

1.8

1.5

1.3

10

3.0

3.5

1.8

1.5

1.3


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

Проведем условную оптимизацию начиная с последнего 5-го шага.

Требуется так распределить средства К между фирмами, чтобы в сумме это дало максимальный доход. Хотя в своей постановке задача не содержит упоминания о времени, она легко решается методом динамического программирования, если считать за первый шаг вложение средств в фирму П1, за второй - в П2 и т.д.

В такой задаче “шаговыми управлениями” являются средства х1, х2, ..., х5, инвестируемые фирмам.

Требуется найти такой вектор х=||х1, х2, ..., х5||, при котором суммарный доход:

был бы максимален.

Начнем оптимизацию с последнего 5-го шага. Пусть мы подошли к этому шагу с остатком средств S. Очевидно, что эту сумму можно вложить в фирму 5, т.е. х5(S)=S и условной оптимальный выигрыш .

Задаваясь всеми возможными значениями s мы уже для каждого s будем знать . Таким образом последний шаг будет оптимизирован. Далее переходим к предпоследнему, 4-му шагу. Пусть мы подошли к нему с запасом средств S. Обозначим - условный оптимальный выигрыш на двух последних шагах. Если мы выделим на 4-м шаге 4-ой фирме средства х, то на последний 5-й шаг останется S-x. Выигрыш на двух последних шагах будет равен



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



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

Далее оптимизируется 3-й шаг. В таблице 6.2 дали результаты условной оптимизации по всем шагам. Таблица построена так: в первом столбце даются значения запаса ресурса S, с которым мы подходим к данному шагу. Далее для каждого шага приводится значение условного оптимального управления и условного оптимального выигрыша.

Таблица 6.2.




i=5

i=4

i=3

i=2

i=1

S

x5(S)



x4(S)



x3(S)



x2(S)



x1(S)



1

[1]

[1.0]

[0]

[1.0]

0

1.0

0

1.0







2

2

1.2

1

1.3

1

1.6

0

1.6







3

3

1.3

2

1.6

[2]

[2.1]

0

2.1







4

4

1.3

3

2.3

2

2.4

0

2.4







5

5

1.3

3

2.5

1

2.9

0

2.9







6

6

1.3

4

2.6

2

3.4

5

3.5







7

7

1.3

5

2.7

2

3.6

5

4.1







8

8

1.3

5

2.8

4

3.7

[5]

[4.6]







9

9

1.3

6

2.8

5

3.9

7

5.1







10

10

1.3

7

2.8

5

4.1

7

5.6








Чтобы было более понятно, как заполнялась таблица 6.2, проиллюстрируем получение условно оптимального решения на 3-м шаге, если мы подошли к нему с запасом средств S=7 (предположим, что 4-й и 5-й шаги уже оптимизированы).

Составим вспомогательную таблицу 6.3. В первом ее столбце перечислим все возможные значения х на 3-м шаге, не превосходящие S=7. В третьем столбце - выигрыш на третьем шаге от вложения средств х на фирму 3 (заполняется по столбцу 3(х) таблицы 6.1).

В четвертом - условно оптимальный выигрыш во всех остальных шагах (4-м и 5-м) при условии, что мы подошли к четвертому шагу с оставшимися средствами (заполняется по столбцу i=4 таблицы 6.2). В пятом столбце - сумма двух выигрышей: шагового и оптимизированного дальнейшего при данном вложении х в третий шаг. Из всех выигрышей последнего столбца выбирается максимальный (в таблице 6.3 он равен =3,6, а соответствующие управление х3(7)=2.

Таблица 6.3

x

7-x

3(x)





7

0

1.8

0

1.8

6

1

1.7

1.0

2.7

5

2

1.6

1.3

2.9

4

3

1.4

1.6

3.0

3

4

1.2

2.3

3.5

[2]

5

1.1

2.5

[3.6]

1

6

0.6

2.6

3.2

0

7

0

2.7

2.7


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

И так, в результате последовательной оптимизации 5-го, 4-го, 3-го, 2-го и 1-го шагов мы получим полный список всех рекомендаций по оптимальному управлению и безусловный выигрыш L за всю операцию - в данном случае они равны 5.6. На 1-м шаге заполнена только одна строка, так как состояние системы перед началом первого шага в точности известно: S0=K=10. Оптимальные управления на всех шагах выделены рамкой. Таким образом, мы получили оптимальное решение: надо выделить первой фирме две единицы из десяти; второй - 5 единиц; третьей - две; четвертой - ни одной; пятой - одну единицу. При таком распределении доход будет максимален и равен 5.6.


3. Задача о загрузке машины.

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

В качестве примера рассмотрим следующую задачу: имеется набор предметов П1, ...Пп (каждый в единственном экземпляре); известны их веса q1, ..., qn и стоимости C1, ..., Cn. Грузоподъемность машины равна . Необходимо определить, какие из предметов нужно взять в машину, чтобы их суммарная стоимость была максимальна.

Конкретный численный пример приведен в таблице 6.4.


Таблица 6.4.

Предмет Пі

П1

П2

П3

П4

П5

П6

Вес qі

4

7

11

12

16

20

Стоимость С

7

10

15

20

27

34


Процесс загрузки машины можно представить себе как по-шаговый, при котором на каждом шаге ищется ответ на вопрос: брать данный предмет (i=1,6) в машину или не брать?

Управление хi на i-м шаге равно единице, если i-й предмет берется в машину, и нулю - если не берется.

Состояние системы ^ S перед очередным шагом характеризуется весом, который остался до полной загрузки машины. Как и ранее, будем придавать S только целые значения. Условная оптимизация решения показана в таблице 6.5.

Ее заполнение аналогично заполнению в предыдущей задаче, с той разницей, что возможные управления только 0 или 1.


Таблица 6.5.




i=6

i=5

i=4

i=3

i=2

i=1

S

x6

6

x5

5

x4

4

x3

3

x2

2

x1

i

0

[0]

0

0

0

0

0

0

0

0

0







1

0

0

0

0

0

0

0

0

0

0







2

0

0

0

0

0

0

0

0

0

0







3

0

0

0

0

0

0

0

0

0

0







4

0

0

0

0

0

0

0

0

0

0







5

0

0

0

0

0

0

0

0

0

0







6

0

0

0

0

0

0

0

0

1

0







7

0

0

0

0

0

0

0

0

1

10







8

0

0

0

0

0

0

0

0

1

10







9

0

0

0

0

0

0

0

0

1

10







10

0

0

0

0

0

0

1

0

0

10







11

0

0

0

0

0

0

0

15

0

15







12

0

0

0

0

1

20

0

20

0

20







13

0

0

0

0

1

20

0

20

0

20







14

0

0

0

0

1

20

0

20

0

20







15

0

0

0

0

1

20

0

20

0

20







16

0

0

[1]

27

0

27

0

27

0

27







17

0

0

1

27

0

27

0

27

0

27







18

0

0

1

27

0

27

0

27

0

27







19

0

0

1

27

0

27

0

27

1

30







20

1

34

0

34

0

34

0

34

0

34







21

1

34

0

34

0

34

0

34

0

34







22

1

34

0

34

0

34

0

34

0

34







23

1

34

0

34

0

34

0

34

1

37







24

1

34

0

34

0

34

0

34

1

37







25

1

34

0

34

0

34

0

34

1

37







26

1

34

0

34

0

34

0

34

1

37







27

1

34

0

34

0

34

0

34

1

44







28

1

34

0

34

[1]

47

0

47

0

47







29

1

34

0

34

1

47

0

47

0

47







30

1

34

0

34

1

47

0

47

0

47







31

1

34

0

34

1

47

1

49

0

49







32

1

34

0

34

1

54

1

54

0

54







33

1

34

0

34

1

54

0

54

0

54







34

1

34

0

34

1

54

0

54

0

54







35

1

34

0

34

1

54

0

54

[1]

57

[0]

57


В таблице 6.5. выделен оптимальный выигрыш L*=57 и оптимальные шаговые управления, при которых этот выигрыш достигается: х*1=0; х*2=1; х*3=0; х*4=1; х*5=0





Схожі:

6. Динамическое программирование icon6. Динамическое программирование
Динамическое программирование представляет собой математический аппарат, разработанный с целью повышения эффективности при решении...
6. Динамическое программирование icon6. Динамическое программирование
Динамическое программирование представляет собой математический аппарат, разработанный с целью повышения эффективности при решении...
6. Динамическое программирование icon6. Динамическое программирование
Динамическое программирование представляет собой математический аппарат, разработанный с целью повышения эффективности при решении...
6. Динамическое программирование icon6. Динамическое программирование
Динамическое программирование представляет собой математический аппарат, разработанный с целью повышения эффективности при решении...
6. Динамическое программирование icon6. Динамическое программирование
Динамическое программирование представляет собой математический аппарат, разработанный с целью повышения эффективности при решении...
6. Динамическое программирование icon6 Задача динамического программирования. Общий случай
Но в отличии от линейного программирования динамическое программирование не сводится к какой-либо стандартной вычислительной процедуре;...
6. Динамическое программирование iconЗадача динамического программирования. Общий случай
Но в отличии от линейного программирования динамическое программирование не сводится к какой-либо стандартной вычислительной процедуре;...
6. Динамическое программирование iconЗадача динамического программирования. Общий случай
Но в отличии от линейного программирования динамическое программирование не сводится к какой-либо стандартной вычислительной процедуре;...
6. Динамическое программирование icon6 Задача динамического программирования. Общий случай
Но в отличии от линейного программирования динамическое программирование не сводится к какой-либо стандартной вычислительной процедуре;...
6. Динамическое программирование icon5. Целочисленное программирование
Целочисленные программирование ориентировано на решение задач математического программирования, в которых все или некоторые переменные...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи