Основы математического программирования (стр. 25 )

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

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

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

1. Задачи планирования деятельности экономического объекта (предприятия, отрасли и т. п.) с учетом изменения потребности в продукции во времени.

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

Особенно эффективно применяется динамическое программирование, когда решение приходится принимать по этапам.

Пример.

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

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

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

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

На этом примере рассмотрим практические приемы динамического программирования, причем условия задачи будут упрощены.

Пусть самолет, находящийся на высоте Hs, и имеющий скорость Vs должен быть поднят на заданную высоту Hf, скорость его доведена до заданного значения Vf. Известен расход горючего, необходимый на подъем с любой высоты H на любую другую H’ > H при неизменной V. Известен также расход горючего, требуемый для увеличения скорости от любого значения скорости V до V’>V при неизменной высоте H.

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

Решение будем строить следующим образом.

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

Будем изображать состояние самолета точкой на плоскости, где абсцисса – скорость самолета V, а ордината – его высота H.

Очевидно, что существует множество траекторий, по которым можно перевести точку S из Ss в Sf.

Из этих траекторий нужно выбрать ту, на которой расход будет минимальным.

Будем решать задачу методом динамического программирования.

Разделим интервал скоростей Vf - Vs на n равных частей

DV = (Vf - Vs)/n

А интервал высот Hf – Hs на m равных частей

DH = (Hf – Hs )/m

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

Так как за каждый шаг меняется только высота или скорость, то общее число шагов k равно

k = n + m

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

Допустим, что n = 8, m = 6, k = 14.

Расход горючего задан в таблице

		Шаги по скорости
			1		2		3		4		5		6		7		8
			20		18		16		15		14		12		15		17	(14)
Шаги по высоте	6	12		12		13		13		14		15		15		16		14
			17		14		13		10		11		13		14		17	(13)
	5	9		8		8		10		11		12		13		13		13
			14		13		12		10	(8)	9	(9)	8	(10)	10	(11)	11	(12)
	4	7		6		8		7		8		10		11		11		12
			12		13		12		10	(7)	11		13		15		18
	3	8		7		8		9		9		10		11		8		10
			10		10	(4)	8	(5)	9	(6)	10		12		13		19
	2	10		8		9		11		10		11		12		13		13
			11	(2)	9	(3)	8		7		9		13		14		20
	1	11		9		10		12		13		14		14		15		15
		(0)	12	(1)	11		10		9		13		14		17		20

Любой траектории, переводящей S из So в S14, соответствует вполне определенный расход горючего, равный сумме чисел на отрезках