Задача динамического программирования. Общий случай icon

Задача динамического программирования. Общий случай




Скачати 123.48 Kb.
НазваЗадача динамического программирования. Общий случай
Дата06.09.2012
Розмір123.48 Kb.
ТипЗадача

Задача динамического программирования. Общий случай


Общая идея динамического программирования: пошаговая оптимизация, проходимая в одном направлении, “условно”, в другом - ”безусловно”. Но в отличии от линейного программирования динамическое программирование не сводится к какой-либо стандартной вычислительной процедуре; оно может быть передано на решение ЭВМ лишь после того, как записаны соответствующие формулы, а это часто бывает не так-то легко.

Первый вопрос, на который нужно ответить: какими параметрами характеризуется состояние S управляемой системы перед каждым шагом? От правильного выбора этих параметров часто зависит возможность успешно решить задачу оптимизации. В трех конкретных примерах, которые решались выше, состояние системы характеризовалось очень небольшим числом параметров: двумя координатами - в первом примере, одним числом - во втором и третьем. Но такие простые задачи редко встречаются на практике. Если состояние системы описывается многими параметрами (так называемыми “фазовыми координатами”), то становится трудно перед каждым шагом перебрать все их варианты и для каждого найти оптимальное условное управление.

Последнее еще больше затрудняется, когда число возможных вариантов велико. В этом случае возникает по выражению Р.Беллмана “проклятие многомерности”. Обычно задачи динамического программирования решаются не вручную, а на ЭВМ.

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

Поскольку при увеличении числа шагов m возрастет объем расчетов, то число шагов надо выбирать рационально: 1) шаг должен быть достаточно малым для того чтобы процедура шагового управления была достаточна проста, и 2) шаг должен быть не слишком малым, чтобы не усложнять процедуру поиска оптимального решения. На практике нас интересует не строго оптимальное, а “приемлемое” решение, не слишком отличающееся от оптимального по значению выигрыша L*.

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

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

Выигрыш на і-м шаге при управлении хі, если система была в состоянии S

(6.1.)

Под влиянием уравнения хі на і-м шаге система переходит в новое состояние

(6.2.)

Функции и должны быть записаны. Заметим, что в общем случае аргументы функций и - вектора.

Основное рекурентное уравнение динамического программирования, выражающее условный оптимальный выигрыш Li(S) (начиная с і-го шага и до конца), для метода “обратной прогонки” выражается через уже известную функцию Li+1(S):

(6.3.)

Этому выигрышу соответствует условное оптимальное уравнение на і-м шаге хi(S).

Условную оптимизацию последнего m-го шага производят задаваясь всеми возможными состояниями системы S, из которых можно за один шаг дойти до конечного состояния, вычисляя для каждого из них условных оптимальный выигрыш по формуле

(6.4.)

Таким образом, находится условное оптимальное управление хm(S), для которого этот максимум достигается.

Производя условную оптимизацию (m-1)-го, (m-2)-го и т.д. шагов по формуле (6.3.), полагая в ней i=(m-1), (m-2), ..., определяем для каждого из шагов условное оптимальное управление хi(S), при котором максимум достигается.

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

(6.5.)

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

В заключение отметим, что метод динамического программирования применим также и к задачам с мультипликационной целевой функцией, имеющей вид произведения:

,

где .

Эти задачи решаются точно также, как и с аддитивной целевой функции, с той разницей, что в основном уравнении (6.3.) вместо знака “плюс”, ставится знак “умножение”.

(6.6.)

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

Пример. Для увеличения количества продукции трем предприятиям выделено 700 тыс. грн. Использование каждым предприятием хі тыс.грн. обеспечит рост производимой продукции (х) (таб. 6.5.) Определить оптимальное распределение средств.


Таблица 6.5

x

fi(x)




предприятие 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


Решение

1. Состояние S системы характеризуется количеством средств, с которым мы подходим к каждому шагу.

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

2. В данной задаче количество шагов определяется числом предприятий (m=3). Считаем за первый шаг вложение средств в предприятие 1, за второй - в предприятие 2, за третий - в предприятие 3.

3. Условную оптимизацию начинаем с последнего шага в соответствии с выражением (6.4.). Получаем таблицу 6.6.


Таблица 6.6

S

x3(S)

L3(S)

0

0

0

100

100

40

200

200

50

300

300

110

400

400

120

500

500

180

600

600

220

700

700

240


4. Условную оптимизацию предпоследнего шага осуществляем в соответствии с выражением (6.3.):

S=0; x=0; ; x2=0

S=100; x=||0, 100||; ; x2=100

S=200; x=||0, 100, 200||; ; x2=100

S=300; x=||0, 100, 200, 300||; ; x2=200

S=400; x=||0, 100, 200, 300, 400||; ; x2=100

S=500; x=||0, 100, 200, 300, 400, 500||; ;

S=600; x=||0, 100, 200, 300, 400, 500, 600||; ; x2=100

S=700; x=||0, 100, 200, 300, 400, 500, 600, 700||; ; x2=100

Результат условной оптимизации на 2-м шаге записаны в таблицу 6.7.

Таблица 6.7.

S

x2

L2

0

0

0

100

100

50

200

100

90

300

200

120

400

100

160

500

300

400

500

190

600

100

230

700

100

270


5. Условную оптимизацию первого шага также осуществляем в соответствии с выражением (6.6.)

S=So=700; x=||0, 100, 200, 300, 400, 500, 600, 700||; ; x1=0

6. Безусловная оптимизация дает такое оптимальное управление

x*=||0, 100, 600||, а

максимальный прирост производства соответствует 270 тыс. грн.


ТЕСТЫ

(Верно (В) или неверно (Н) ?)


1. В моделях ДП число шагов равно количеству подзадач.

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

3. При проведении характерных для ДП расчетов объем вычислений на каждом этапе находится в прямой зависимости от размеров области допустимых значений переменной состояния.

4. При решении задач ДП обычно труднее определить этапы, чем состояния.

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

6. Принцип оптимальности обеспечивает независимость последующих решений от решений принятых ранее.

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

8. Задачи динамического программирования могут допускать как аддитивную, так и мультипликативную декомпозицию.

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

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


ЗАДАЧИ

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

І. Прокладка наивыгоднейшего пути между двумя пунктами. Определить наиболее дешевый путь из А в В. Двигаться можно из каждой точки либо на восток, либо на север. Стоимость каждого участка указана на ветвях, где і - номер студента.




II. Задача о распределении материальных ресурсов. Имеется запас ресурсов 10 (условных единиц). Требуется распределить эти средства между четырьмя фирмами (m=4). Для простоты предполагается, что распределяется только целые количества средств. Функции доходов fi(x) заданы в следующей таблице:

х

f1(x)

f2(x)

f3(x)

f4(x)

1

0.1

0.5+0.i

0.3+0.i

0.4+0.i

2

0.1+0.i

0.7+0.i

0.4+0.i

0.6+0.i

3

0.2+0.i

0.8+0.i

0.5+0.i

0.7+0.i

4

0.3+0.i

0.9+0.i

0.6+0.i

0.8+0.i

5

0.5+0.i

1.2+0.i

0.7+0.i

0.9+0.i

6

0.8+0.i

1.5+0.i

0.8+0.i

0.9+0.i

7

0.9+0.i

1.5+0.i

0.9+0.i

0.9+0.i

8

1.2+0.i

1.5+0.i

1.0+0.i

0.9+0.i

9

1.4+0.i

1.5+0.i

1.1+0.i

0.9+0.i

10

2+0.i

1.5+0.i

1.1+0.i

0.9+0.i

где i - номер студента


ІІІ. Задача о распределении людских ресурсов. Для выполнения работ направляется 6 человек. Оценка эффективности на работы на различных участках определяется функциями fi(x), i=1, 2, 3, представленной в следующей таблице:


х

f1(x)

f2(x)

f3(x)

0

0

0

0

1

50+i

30+i

200+i

2

100+i

60+i

350+i

3

150+i

120+2i

450+i

4

250+i

180+i

550+i

5

350+i

300+i

600+i

6

500+i

550+i

650+i


где i - номер студента

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

Схожі:

Задача динамического программирования. Общий случай icon6 Задача динамического программирования. Общий случай
Но в отличии от линейного программирования динамическое программирование не сводится к какой-либо стандартной вычислительной процедуре;...
Задача динамического программирования. Общий случай iconЗадача динамического программирования. Общий случай
Но в отличии от линейного программирования динамическое программирование не сводится к какой-либо стандартной вычислительной процедуре;...
Задача динамического программирования. Общий случай icon6 Задача динамического программирования. Общий случай
Но в отличии от линейного программирования динамическое программирование не сводится к какой-либо стандартной вычислительной процедуре;...
Задача динамического программирования. Общий случай icon1. Модели и критерии эффективности
Тема Задачи динамического программирования и методы сетевого планирования и управления
Задача динамического программирования. Общий случай icon2 Двойственная задача линейного программирования Двойственная задача
Между прямой и двойственной задачами существуют тесная взаимосвязь. Фактически оптимальное решение одной из задач непосредственно...
Задача динамического программирования. Общий случай icon2 Двойственная задача линейного программирования Двойственная задача
Между прямой и двойственной задачами существует тесная взаимосвязь. Фактически оптимальное решение одной из задач непосредственно...
Задача динамического программирования. Общий случай iconЗадача прогноз задача ефект ставка -1 задача ефект ставка -2 задача опт портфель графіки
По акціях корпорацій виплачується дивіденд 5 г о на одну акцію. Продажна ціна акцій на фондовій біржі становила 100 г о
Задача динамического программирования. Общий случай iconУдк 621. 382. Контроль зарядового состояния системы диэлектрик полупроводник методом динамического конденсатора
Контроль зарядового состояния системы диэлектрик полупроводник методом динамического конденсатора
Задача динамического программирования. Общий случай iconУдк 621. 314 Замкнутые системы формирования требуемых нагрузочных режимов в системах динамического нагружения
Замкнутые системы формирования требуемых нагрузочных режимов в системах динамического нагружения
Задача динамического программирования. Общий случай iconПлоская задача теории упругости
Плоская задача включает в себя плоскую деформацию и обобщенное плоское напряженное состояние
Додайте кнопку на своєму сайті:
Документи


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