Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Информационные технологии и моделирование бизнес-процессов

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

Задачи динамического программирования

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

o функция цели должна быть аддитивной, то есть состоять из суммы функций, каждая из которых зависит только от соответствующей переменной;

o задача должна допускать интерпретацию как многошаговый процесс принятия решений;

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

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

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

1. В состав производственного объединения входит m предприятий. Предположим, что для развития этих предприятий в течение п лет выделены средства в размере k у.е. Эти средства в начале каждого года распределяются между предприятиями. Одновременно с тем между предприятиями распределяется полученный ими прибыль за прошлый год, который зависит от вложенных средств. Задача состоит в следующем: необходимо определить такое распределение средств на начало каждого года предприятию, чтобы суммарная прибыль всех предприятий за n лет был максимальным.

2. Пусть самолет, находится на высоте ho и имеет скорость v0, должен подняться на высоту hk и достичь скорости vk. Известны расход топлива для подъема с любой высоты h до высоты H при постоянной скорости v и расход топлива для увеличения скорости от v к V при постоянной высоте h. Необходимо определить такую траекторию полета (набор высоты и скорости), при которой общие расходы топлива будут минимальными.

3. Для осуществления эффективной деятельности фирма должна периодически проводить замену оборудования, которое им используется. При этой замене учитываются: производительность оборудования, используемого; расходы, связанные с содержанием и ремонтом оборудования; стоимость оборудования, которое предполагается приобрести, и стоимость оборудования, подлежащего замене.

Предположим, что на начало планового периода фирма приобрела новое оборудование, причем известно, что в k-м году, используя приобретенное оборудование, компания может выпустить продукции на s1 у.е., а ежедневные расходы, связанные с содержанием и ремонтом оборудования, составляют s2 у.е. В k -ом году оборудование может быть продано за s3 у.е., а новое приобретенное за s4 у.е. С учетом всех этих факторов найти оптимальный план замены оборудования в течение N лет.

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

Состояние системы управления

Рис.8.1. Состояние системы управления

Сформулированы требования лежат в основе принципа оптимальности Беллмана, который определяется следующим образом:

Свойство оптимального управления - для произвольного начального состояния и начального управления u1 управления на k-м (k = 2,3, .., n) шаге должно быть оптимальным только о текущем состоянии системы и не зависеть от предыдущих состояний

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

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

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

Предположим, что для каждого возможного предпоследнего состояния системы мы нашли условное оптимальное управление на последнем шаге и соответствующий ему оптимальный выигрыш на этом этапе. Тогда можем перейти к оптимизации управления на предпоследнем (n - 1) -м шаге.

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

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

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

Пусть So - начальное состояние системы. Тогда мы можем выбрать оптимальное управление u1, которое на первом этапе переведет систему из состояния So в некоторое состояние S1. На втором шаге нам известно условно оптимальное управление u2 *, которое переведет систему из состояния S1 в некоторое состояние S2, и т. Д. Следовательно, мы найдем оптимальное управление U * = (u1 * u2 *, ..., un *) , которое переведет систему с начального состояния в некоторое конечное состояние Бп. Это оптимальное управление и обеспечит максимальный выигрыш от управления процессом в целом.

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

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

 
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Предметы
Агропромышленность
Банковское дело
БЖД
Бухучет и аудит
География
Документоведение
Естествознание
Журналистика
Инвестирование
Информатика
История
Культурология
Литература
Логика
Логистика
Маркетинг
Математика, химия, физика
Медицина
Менеджмент
Недвижимость
Педагогика
Политология
Политэкономия
Право
Психология
Региональная экономика
Религиоведение
Риторика
Социология
Статистика
Страховое дело
Техника
Товароведение
Туризм
Философия
Финансы
Экология
Экономика
Этика и эстетика
Прочее