Hi-Tech  ->  Программы  | Автор: | Добавлено: 2015-03-23

Применение динамического программирования для решения экстремальных задач

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

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

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

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

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

Многошаговый процесс распределения ресурсов

Допустим, что мы имеем некоторое физическое количество x, которое разделим на две неотрицательные части y, и x-y, получая от первой доли y доход g(y), а от второй - доход h(x-y). Желание выполнить это разделение так, чтобы максимизировать общий доход, приводит нас к аналитической задаче определения максимума функции

R1(x, y) =g(y) +h(x-y) по всем y є [0, x]. Мы будем предполагать, что функции g и h непрерывны при всех конечных x>=0, так что интересующий нас максимум всегда будет существовать.

Рассмотрим теперь двухшаговый процесс. Предположим, что за счет издержек, требующихся для получения дохода g(y), первоначальное количество y уменьшается до ay, где a - некоторая постоянная, заключенная между 0 и 1. Пусть аналогично x-y уменьшается до b(x-y) за счет издержек для получения h(x-y). Затем мы повторяем процесс с суммарным остатком ay+b(x-y), полагая ay+b(x-y)=x1=y1+(x1-y1), где 0<=y1<=x1. В результате этого нового распределения мы на втором шаге получили доход g(y1)+h(x1-y1). Полный доход от описанного двухшагового процесса будет

R2(x, y, y1) =g(y) +h(x-y) +g (y1) +h(x1-y1).

Максимальный суммарный доход получается при максимизации этой функции относительно y и y1 в двумерной области, определенной неравенствами

1. 0<=y<=x

2. 0<=y1<=x1.

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

RN(x, y, y1,. ,yN-1)=g(y)+h(x-y)+g(y1)+h(x1-y1)+. +g(yN-1)+h(xN-1-yN-1), где величины, подлежащие дальнейшему разделению после (N-1)-го шагов, определяются соотношением xN-1=ayN-2+b(xN-2-yN-2), 0<=yN-2<=xN-2, 0<=yN-1<=xN-1. 1)

Максимальный окончательный доход будет получаться в результате максимизации функции RN по N-мерной области в пространстве переменных y, y1,. , yN-1, в которой значения этих переменных удовлетворяют соотношениям 1).

Метод функциональных уравнений

Поставив своей целью сохранение одномерности задачи, будем действовать следующим образом. Прежде всего, заметим, что максимум полного дохода от N-шагового процесса зависит только от N и от начальной величины x. В связи с этим определим функцию fN(x) как максимум дохода, полученного от N-шагового процесса, который начинается с величины x, для N=1, 2,. и x>=0.

Мы имеем fN(x) =max{y,yi}RN(x, y, y1. yN-1), N=2, 3.

и f1(x) =max0<=y<=x[gy+hx-y].

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

Если только y1 выбрано оптимальным, то в результате начального распределения y мы получим от второго шага нашего двухшагового процесса полный доход f1(ay+b(x-y)). Следовательно, для окончательного дохода от двухшагового процесса при начальном распределяемом количестве y получается выражение

R2x, y, y1=gy+hx-y+f1ay+bx-y.

Так как y выбиралось таким образом, чтобы максимизировать это выражение, то можно легко установить рекуррентное соотношение f2x=max0<=y<=x[gy+hx-y+f1(ay+bx-y)], связывающие функции f1(x) и f2(x). Используя точно такую же аргументацию для N-шагового процесса, мы получим основное функциональное уравнение fNx=max0<=y<=xgy+hx-y+fN-1ay+bx-y 2) для N>=2.

Отправляясь от функции f1(x) мы используем формулу 2) для вычисления f2(x), которое, если процесс повторить, даст нам f3(x) и т. д. При этом на каждом шаге вычисления мы получаем не только fk(x), но также и yk(x), так как распределение исходной величины x в начале k-шагового процесса было оптимальным.

Отсюда видно, что процесс решения нашей задачи состоит в табулировании последовательностей функции {yk(x)} и {fk(x)} для x>=0, k=1, 2,.

Если дана последовательность функций {yk(x)}, то решение конкретной задачи с заданным числом шагов N и величиной x имеет вид y=yNx, y1=yN-1(ay+b(x-y)), yN-1=y1(ayN-2+b(xN-2-yN-2)), где (y, y1,. ,yN-1) - система распределений, максимизирующих полный доход от N-шагового процесса.

Бесконечношаговая аппроксимация

Обратимся вновь к процессу распределения. Если число N велико, то естественно рассмотреть в качестве аппроксимации N-шагового процесса бесконечношаговый процесс, отличающийся от конечношагового процесса только тем, что он продолжается сколь угодно долго. Одно несомненное и немедленно сказывающееся преимущество такой аппроксимации заключается в том, что вместо последовательности уравнений можно рассматривать единственное уравнение fx=max0<=y<=x[gy+hx-y+fay+bx-y], которому должна удовлетворять функция f(x) и которое определяет полный доход от процесса вместе с единственной распределяющей функцией y=y(x).

Процессы, зависящие от времени

Рассмотрим теперь процессы, которые зависят ещё и от времени начала процесса. Допустим, что в результате разделения x на y и x-y на k-м шаге мы получаем доход gk(x, y) и для распределения остается величина ak(x, y). Необходимо определить поведение, которое максимизирует полный доход от N-шагового процесса.

Предположим, что функции gk(x, y) и ak(x, y) непрерывны как функции от x и y для x>=0 и 0<=y<=x, причем ak(x, y) в этой области удовлетворяет неравенству 0<=ak(x, y)<=ax, a<1, для k=1,2,. Определим fk(x) - полный доход, который получится от процесса, начинающегося с величины x на k-ом шаге и кончающийся на N-м шаге при k=1,2,. ,N, если придерживаться оптимального поведения.

Тогда fN(x)=max0<=y<=xgNx,y, fk(x)=max0<=y<=xgkx,y+fk+1akx,y, k=1,2,. ,N-1.

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

Случай неограниченно продолжающегося процесса, т. е. тот случай, когда N=infinity, приводит к системе функциональных уравнений fk(x)=max0<=y<=xgkx,y+fk+1akx,y.

Функциональные уравнения

Ранее нами предполагалось, что в результате разделения количества x на y и x-y получается доход g(y)+h(x-y), после чего для распределения остается количество ресурса x1=ay+b(x-y). Допустим теперь, что в результате разделения с вероятностью p1, будет получен доход g1(y)+h1(x-y) и для распределения останется количество a1y+b1(x-y), а с вероятностью p2=1-p1 будет получен доход g2(y)+h2(x-y) и останется количество a2y+b2(x-y).

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

В этом случае, как и раньше, мы получим уравнения f1x=max0<=y<=xp1g1y+h1x-y+p2g2y+h2x-y, fN+1x=max0<=y<=xp1g1y+h1x-y+fNa1y+b1x-y+p2g2y+h2x-y+fNa2y+b2x-y для N>=1.

Простая задача

Предположим, что мы имеем стаю норок и располагаем возможностью отправлять в конце года некоторую часть стаи (y) на рынок, сохраняя часть (z) для разведения. Допустим, что стоимость норок, посылаемых на рынок, выражается функцией g(y) , а оставшаяся часть стаи за год увеличивается до az, a>1.

Вывести рекуррентное соотношение, максимизирующее полный доход звероводческой фермы за N-летний период.

Решение.

fN(x) - полный доход за N шагов.

На первом шаге полный доход будет равен максимальному доходу от продажи части стаи (y).

f1x=max0<=y<=xg(y),

Тогда на N-ом шаге полный доход будет равен: fNx=max0<=y<=x[gy+fN-1(ax-y)].

Задача на планирование трудовых ресурсов

Предпринимателю необходимо составить план регулирования численности рабочих на последующие пять недель. Он оценивает минимальные потребности в рабочей силе bi на каждую из пяти недель следующим образом: 5, 7, 8, 4 и 6 рабочих для i=1, 2, 3, 4 и 5 соответственно. Предприниматель имеет возможность регулировать количество имеющихся в наличии рабочих путем найма и увольнения.

Пусть yi - количество рабочих, имеющихся в наличии на j-й неделе. Определим C1(yj-bj) как величину убытков, связанных с тем, что превышает заданное значение bj a C2(yj-yj-1) - как величину накладных расходов по найму новых рабочих (yj-yj-1). Необходимо составить оптимальный план регулирования численности рабочих для 5-недельного периода планирования при условии, что исходное количество y0 рабочих, имеющихся в наличии к началу первой недели, составляет пять человек. Опишем задачу в виде модели динамического программирования.

Этап j ставится в соответствие j-й неделе. Состояние yj-1 на этапе j выражает количество рабочих, имеющихся к концу этапа j-1. Варианты решения yj описываются количеством рабочих, имеющихся на этапе j. Обозначим через минимальную величину расходов, осуществленных в течение периодов времени (недель) j,j+1,. 5 , при заданном yj-1. Рекуррентное соотношение записывается в следующем виде:

Заключение

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

Комментарии


Войти или Зарегистрироваться (чтобы оставлять отзывы)