Материалы сайта
Это интересно
Динамическое программирование
Курсовая работа по теории оптимального управления экономическими системами. Тема : Задача динамического программирования. I.Основные понятия и обозначения. Динамическое программирование – это математический метод поиска оптимального управления, специально приспособленный к многошаговым процессам. Рассмотрим пример такого процесса. Пусть планируется деятельность группы предприятий на N лет. Здесь шагом является один год. В начале 1-го года на развитие предприятий выделяются средства, которые должны быть как-то распределены между этими предприятиями. В процессе их функционирования выделенные средства частично расходуются. Каждое предприятие за год приносит некоторый доход, зависящий от вложенных средств. В начале года имеющиеся средства могут перераспределяться между предприятиями : каждому из них выделяется какая-то доля средств. Ставится вопрос : как в начале каждого года распределять имеющиеся средства между предприятиями, чтобы суммарный доход от всех предприятий за N лет был максимальным? Перед нами типичная задача динамического программирования, в которой рассматривается управляемый процесс – функционирование группы предприятий. Управление процессом состоит в распределении (и перераспределении) средств. Управляющим воздействием (УВ) является выделене каких-то средств каждому из предприятий в начале года. УВ на каждом шаге должно выбираться с учетом всех его последствий в будущем. УВ должно быть дальновидным, с учетом перспективы. Нет смысла выбирать на рассматриваемом шаге наилучшее УВ, если в дальнейшем это помешает получить наилучшие результаты других шагов. УВ на каждом шаге надо выбирать “c заглядыванием в будущее”, иначе возможны серьезные ошибки. Действительно, предположим, что в рассмотренной группе предприятий одни заняты выпуском предметов потребления, а другие производят для этого машины. Причем целью является получение за N лет максимального объема выпуска предметов потребления. Пусть планируются капиталовложения на первый год. Исходя их узких интересов данного шага (года), мы должны были бы все средства вложить в производство предметов потребления, пустить имеющиеся машины на полную мощность и добиться к концу года максимального объема продукции. Но правильным ли будет такое решение в целом? Очевидно, нет. Имея в виду будущее, необходимо выделить какую-то долю средств и на производство машин. При этом объем продукции за первый год, естественно, снизится, зато будут созданы условия, позволяющие увеличивать ее производство в последующие годы. В формализме решения задач методом динамического программирования будут использоваться следующие обозначения: N – число шагов. [pic]– вектор,описывающий состояние системы на k-м шаге. [pic]– начальное состояние, т. е. cостояние на 1-м шаге. [pic]– конечное состояние, т. е. cостояние на последнем шаге. Xk – область допустимых состояний на k-ом шаге. [pic]– вектор УВ на k-ом шаге, обеспечивающий переход системы из состояния xk-1 в состояние xk. Uk – область допустимых УВ на k-ом шаге. Wk – величина выигрыша, полученного в результате реализации k-го шага. S – общий выигрыш за N шагов. [pic]– вектор оптимальной стратегии управления или ОУВ за N шагов. Sk+1([pic]) – максимальный выигрыш, получаемый при переходе из любого состояния [pic][pic]в конечное состояние [pic] при оптимальной стратегии управления начиная с (k+1)-го шага. S1([pic]) – максимальный выигрыш, получаемый за N шагов при переходе системы из начального состояния [pic] в конечное [pic] при реализации оптимальной стратегии управления [pic]. Очевидно, что S = S1([pic]), если [pic] –фиксировано. Метод динамического программирования опирается на условие отсутствия последействия и условие аддитивности целевой функции. Условие отсутствия последействия. Состояние [pic], в которое перешла система за один k-й шаг, зависит от состояния [pic] и выбранного УВ [pic] и не зависит от того, каким образом система пришла в состояние [pic], то есть [pic] Аналогично, величина выигрыша Wk зависит от состояния [pic] и выбранного УВ [pic], то есть [pic] Условие аддитивности целевой функции. Общий выигрыш за N шагов вычисляется по формуле [pic] Определение. Оптимальной стратегией управления [pic] называется совокупность УВ [pic], то есть [pic], в результате реализации которых система за N шагов переходит из начального состояния [pic] в конечное [pic] и при этом общий выигрыш S принимает наибольшее значение. Условие отсутствия последействия позволяет сформулировать принцип оптимальности Белмана. Принцип оптимальности. Каково бы ни было допустимое состояние системы[pic][pic] перед очередным i-м шагом, надо выбрать допустимое УВ [pic] на этом шаге так, чтобы выигрыш Wi на i-м шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным. В качестве примера постановки задачи оптимального управления продолжим рассмотрение задачи управления финансированием группы предприятий. Пусть в начале i-го года группе предприятий [pic] выделяются соответственно средства: [pic][pic]совокупность этих значений можно считать управлением на i-м шаге, то есть [pic]. Управление [pic] процессом в целом представляет собой совокупность всех шаговых управлений, то есть [pic]. Управление может быть хорошим или плохим, эффективным или неэффективным. Эффективность управления [pic] оценивается показателем S. Возникает вопрос: как выбрать шаговые управления [pic], чтобы величина S обратилась в максимум ? Поставленная задача является задачей оптимального управления, а управление, при котором показатель S достигает максимума, называется оптимальным. Оптимальное управление [pic] многошаговым процессом состоит из совокупности оптимальных шаговых управлений: [pic] Таким образом, перед нами стоит задача: определить оптимальное управление на каждом шаге [pic](i=1,2,...N) и, значит, оптимальное управление всем процессом [pic]. II. Идеи метода динамического программирования Мы отметили, что планируя многошаговый процесс, необходимо выбирать УВ на каждом шаге с учетом его будущих последствий на еще предстоящих шагах. Однако, из этого правила есть исключение. Среди всех шагов существует один, который может планироваться без "заглядыва-ния в будущее". Какой это шаг? Очевидно, последний — после него других шагов нет. Этот шаг, единственный из всех, можно планировать так, чтобы он как таковой принес наибольшую выгоду. Спланировав оптимально этот последний шаг, можно к нему пристраивать предпоследний, к предпоследнему — предпредпоследний и т.д. Поэтому процесс динамического программирования на 1-м этапе разворачивается от конца к началу, то есть раньше всех планируется последний, N-й шаг. А как его спланировать, если мы не знаем, чем кончился предпоследний? Очевидно, нужно сделать все возможные предположения о том, чем кончился предпоследний, (N — 1)-й шаг, и для каждого из них найти такое управление, при котором выигрыш (доход) на последнем шаге был бы максимален. Решив эту задачу, мы найдем условно оптимальное управление (УОУ) на N-м шаге, т.е. управление, которое надо применить, если (N — 1)-й шаг закончился определенным образом. Предположим, что эта процедура выполнена, то есть для каждого исхода (N — 1)-го шага мы знаем УОУ на N-м шаге и соответствующий ему условно оптимальный выигрыш (УОВ). Теперь мы можем оптимизировать управление на предпоследнем, (N — 1)-м шаге. Сделаем все возможные предположения о том, чем кончился предпредпоследпий, то есть (N — 2)-й шаг, и для каждого из этих предположений найдем такое управление на (N — 1)-м шаге, чтобы выигрыш за последние два шага (из которых последний уже оптимизирован) был максимален. Далее оптимизируется управ чение на (N — 2)-м шаге, и т.д. Одним словом, на каждом шаге ищется такое управление, которое обеспечивает оптимальное продолжение процесса относительно достигнутого в данный момент состояния. Этот принцип выбора управления , называется принципом оптимальности. Само управление, обеспечивающее оптимальное продолжение процесса относительно заданного состояния, называется УОУ на данном шаге. Теперь предположим, что УОУ на каждом шаге нам известно: мы знаем, что делать дальше, в каком бы состоянии ни был процесс к началу каждого шага. Тогда мы можем найти уже не "условное", а дейсгвительно оптимальное управление на каждом шаге. | Действительно, пусть нам известно начальное состояние процесса. Теперь мы уже знаем, что делать на первом шаге: надо применить УОУ, найденное для первого шага и начального сосюяния. В результате этого управления после первого шага система перейдет в другое состояние; но для этого состояния мы знаем УОУ и г д. Таким образом, мы найдем оптимальное управление процессом, приводящее к максимально возможному выигрышу. Таким образом, в процессе оптимизации управления методом динамического программирования многошаговый процесс "проходится" дважды: — первый раз — от конца к началу, в результате чего находятся УОУ| на каждом шаге и оптимальный выигрыш (тоже условный) на всех шагах, начиная с данного и до конца процесса; . второй раз — от начала к концу, в результате чего находятся оптимальные управления на всех шагах процесса. Можно сказать, что процедура построения оптимального управления методом динамического программирования распадается на две стадии: предварительную и окончательную. На предварительной стадии для каждого шага определяется УОУ, зависящее от состояния системы (достигнутого в результате предыдущих шагов), и условно оптимальный выигрыш на всех оставшихся шагах, начиная с данного, также зависящий от состояния. На окончательной стадии определяется (безусловное) оптимальное управление для каждого шага. Предварительная (условная) оптимизация производится по шагам в обратном порядке: от последнего шага к первому; окончательная (безусловная) оптимизация — также по шагам, но в естественном порядке: от первого шага к последнему. Из двух стадий оптимизации несравненно более важной и трудоемкой является первая. После окончания первой стадии выполнение второй трудности не представляет: остается только "прочесть" рекомендации, уже заготовленные на первой стадии. III. Пример задачи динамического программирования Выбор состава оборудования технологической линии. Есть технологическая линия , то есть цепочка, последовательность операций. На каждую операцию можно назначить оборудование только каго-то одного вида, а оборудования, способного работать на данной операции, - несколько видов. Исходные данные для примера |i |1 |2 |3 | |j |1 |2 |1 |2 |1 |2 | | |10 |8 |4 |5 |8 |9 | |[pic] |12 |8 |4 |6 |9 |9 | | |20 |18 |6 |8 |10 |12 | Стоимость сырья Расходы , связанные с использованием единицы оборудования j-го типа на i- ой операции[pic] Производительности, соответственно, по выходу и входу [pic] и [pic] для j-готипа оборудования, претендующего на i-ую операцию. Решение: Для того, чтобы решить данную задачу методом динамического программирования введем следующие обозначения: N = 3 – число шагов. [pic] - Технологическая линия. [pic]= (0,0,0) [pic]= ( ) [pic] – выбор оборудования для i-ой операции. Ui – область допустимых УВ на i-м шаге. [pic]т.е.[pic] Wi – оценка минимальной себестоимости, полученная в результате реализации i-го шага. S – функция общего выигрыша т. е. минимальная себестоимость . - вектор – функция, описывающая переход системы из состояния в состояние [pic] под действием УВ. [pic] - вектор УВ на i-ом шаге, обеспечивающий переход системы из состояния xi-1 в состояние xi , т.е. оптимальный выбор оборудования за N шагов. Si+1([pic]) – максимальный выигрыш ( в нашем случае минимальная себестоимость), получаемый при переходе из любого состояния [pic][pic]в конечное состояние [pic] при оптимальной стратегии управления начиная с (k+1)-го шага. S1([pic]) – максимальный выигрыш, получаемый за N шагов при переходе системы из начального состояния [pic] в конечное [pic] при реализации оптимальной стратегии управления [pic]. Очевидно, что S = S1([pic]), если [pic]= 0. Запишем вектора допустимых значений Запишем вектора допустимых управляющих воздействий Запишем вектор – функцию, описывающую переход системы из состояния в состояние [pic] под действием УВ. Запишем основное функциональное уравнение 1) Обратный проход Для i=3 Учитывая то, что этот шаг у нас последний и следующей операции уже не будет, а также то, что мы на обратном проходе, вместо функции возьмем стоимость сырья при [pic] = при [pic] = т. е. Для i=2 при [pic] = при [pic] = при [pic] = при [pic] = т. е. Для i=1 при [pic] = при [pic] = при [pic] = при [pic] == при [pic] = при [pic] = при [pic] = при [pic] = т. е. 2) Прямой проход Учитывая то, что и [pic]= (0,0,0) имеем i=1 i=2 i=3 Таким образом оптимальный выбор составаоборудования технологической линии предполагает следующее: На 1-ую операцию назначим оборудование 2-го вида На 2-ую операцию назначим оборудование 1-го вида На 3-ью операцию назначим оборудование 2-го вида Оценка минимальной себестоимости составит 105,5. ----------------------- [pic] [pic] [pic] [pic][pic][pic] [pic][pic] [pic] [pic] [pic][pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic]125,3 [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic]115,2 [pic] [pic] [pic]138,04 [pic] [pic] [pic]102,8 [pic] [pic] [pic]123,1 [pic] [pic] [pic] [pic] [pic] [pic]140,2 [pic] [pic] [pic]125,3 [pic] [pic] [pic]125,3 [pic] [pic] [pic]125,3 [pic] [pic] [pic]125,3 [pic] [pic] [pic]125,3 [pic] [pic] [pic]125,3 [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic]