Основные понятии и постановка задачи.
В ЗЛП процесс является статическим(незав от времени) и поэтому оптимальные решения находились только на первом этапе планирования. Такие задачи назывались одношаговыми.
В ЗДП процесс зависит от времени, от нескольких этапов. Поэтому находится целый ряд оптимальных решений, последовательно для каждого этапа, обеспечивающих оптимальное развитие всего процесса в целом. Эти задачи называются многоэтапными, а раздел математики представляет собой математический аппарат, позволяющий осуществить оптимальное планирование многошаговых процессов, зависящих от времени.
Экономический процесс называется управляемым, если можно влиять на ход его развития, а управлением будет называться совокупность решений, принимаемых на каждом этапе для влияния на ход процесса. В экономическом процессе управление заключается в распределении и перераспределении ресурсов на каждом этапе.
Например:
Выпуск продукции предприятием – это управление процессом, т.к. он определяет изменение состава оборудования, объема поставок сырья, фиксирование и т.д.
Совокупность решений, принимаемых в начале каждого года планируемого периода по обеспечению предприятия сырьём, заменой оборудования, фиксирование является управлением. выпуск продукции надо спланировать так, чтобы избежать нежелательных эффектов, необходимо рассмотреть мероприятия по обеспечению оборудования по мере износа. Таким образом, экономический процесс выпуска продукции можно считать состоящим из нескольких этапов на каждом из которых осуществляется влияние на его развитие.
Началом этапа управления процесса считается момент принятия первого решения о величине капиталовложения и т.д.
Под временным этапом обычно понимают год. Планируя процесс исходят из интересов всего производства в целом и на каждом этапе иметь в виду конечную цель.
Пример:
Пусть планируется деятельность системы промышленных предприятий на некотором периоде времени T, состоящем из k хозяйственных лет , причём
В начале периода T на развитие производства выделяются средства D. В начале хозяйственного года происходит финансирование предприятий. Известно начальное состояние системы , характеризующееся количеством средств уже вложенных и конечное состояние , характеризующееся всей суммой дополнительных вложений D.
Как следует распределить по предприятиям, по годам основные средства D, чтобы к концу периода T суммарный доход W от всей системы был максимальным?
Общая схема решения:
- сумма, выделяемая в начале i-го года j-му предприятию (i =1…k, j = 1…n)
Предположим, что средства на i-ом этапе распределены, т.е. выбрано управление , которое состоит в том, что в начале i-го года предприятию выделены средства , выделены , …, выделены
Тогда определяет распределение средств на i-ом этапе, совокупность выделенных средств, т.е. управлений, на k-шагах выразится системой векторов.
Суммарный доход за k лет зависит от совокупности управлений
На каждом этапе необходимо выбрать такое управление, чтобы суммарный доход от всей системы был max.
Примечание:
Начальное состояние чаще всего являются некоторым элементом (множество начальных значений) тоже самое можно сказать и о конечном значении, т.е.
При большом количестве этапов задача будет громоздкой. При нахождении экстремума по известным методикам решения будут внутри области. Если дискретны, то математический аппарат будет неподходящим.
Динамическое программирование позволяет учитывать появляющиеся изменения. В отличии от ЛП, в котором симплекс-метод является универсальным, в ДП такого метода нет. Каждая задача имеет свои трудности и требует учёта этих особенностей при решении. Метод ДП чувствителен к размерности пространства.
Общая постановка задачи ДП:
Пусть имеется управляемая система , находящаяся в первоначальном состоянии с течением времени её состояние меняется и переходит в . С процессом изменения
51 продолжение (страница 3)
Процесс отображается в таблице. Числа на вертикальных линиях изображают расход горючего на наборе высоты; а на горизонтальных линиях при наборе скорости при const высоте.
Оптимизацию начнём с последнего шага. Рассмотрим угол сетки с точкой . В неё можно прийти из точки и . В каждом случае управление единственно и если на предпоследнем шаге самолёт перешёл в состояние он использует 8 единиц горючего, если в точку , то придётся набирать высоту, используя 11 единиц горючего. Эти расходы для данных состояний будут минимальными. Т.о. последний шаг спланирован.
Планируем предыдущий. Рассмотрим возможные состояния, из которых можно попасть в и .(найдём min управление расходом топлива).
Из и - 17 единиц.
Для - 18 единиц или 24 единицы 18 единиц.
Для - 22 единицы и т.д. Получили:
Процесс перехода из в был упрощен, т.к. не рассмотрели случай одновременного изменения V и H.
Принцип, в котором оптимальное продолжение процесса отыскивается относительно состояния, достигнутого в данный момент, называется принципом оптимальности Беллмана.
Основная рекуррентная формула ДП:
Во многих примерах, использующих метод ДП, каждый очередной итог состоит в рассмотрении всех состояний, в которых система может находиться в данное время. В этом случае основная формула может быть записана в следующем виде:
(I) [стоимость шага t +(новое состояние перед шагом t +1)], где min в (I) берется по всем возможным решениям в ситуации, когда система на шаге t находится в состоянии i. В соотношении (I) величина есть min стоимости завершения задачи из состояния i, (I) отражает тот факт, что min стоимостей затрат необходимых, чтобы от шага t дойти до конца задачи может быть получен минимизацией суммы затрат самого шага t и min затрат необходимых для того, чтобы от шага t +1дойти до конца задачи.
состояния системы связан некоторый численный критерий w. Необходимо так организовать процесс, чтобы критерий достиг оптимального значения. Обозначим U - множество возможных управлений. Тогда задача состоит в том, чтобы из U найти такое U*, которое позволяет перевести систему S из состояния в состояние , чтобы критерий W(U) принял оптимальное значение W*.
Состояние некоторой системы S можно описать параметрами, которые можно считать координатами системы. Тогда начальное состояние можно считать некоторой точкой . Управление изобразится некоторой линией на плоскости, по которой точка S перемещается от к . Нужно из всех траекторий, принадлежащих области возможных состояний системы и соединяющей области и , выбрать такую, на которой критерий принимал бы оптимальное значение.
Принцип поэтапного построения оптимального управления:
ДП представляет собой поэтапное планирование многошагового процесса при котором на каждом этапе учитывается развитие всего процесса. Но оптимизируют только первый шаг, т.е. нацеливают его на следующий шаг, чтобы получить результат, т.е. на каждом шаге учитывается будущее. Однако в каждом процессе имеется последний k-ый шаг, принятие решения на котором уже не зависит от будущего, поэтому выбирают управление, позволяющее получить наибольший эффект. Спланировав этот шаг к нему присоединяем k-1 шаг и избрать более сильное решение, затем k-2 шаг и т.д. в конечном итоге приходят в начальное состояние системы , т.е. процесс ДП разворачивается от конца к началу.
Пример: Игра со спичками.
Два игрока, 30 спичек. Каждый игрок может взять 1, 2 или 3. Проиграл тот, кто взял последнюю. Может ли первый игрок всегда добиваться выигрыша?
Начинаем с конца:
Последний этап: последняя спичка перед проигравшим. 1 спичка – поиграл. 5 спичек – поиграл тот, кто делает ход сейчас.
Рассуждая аналогично, можно прийти к выводу, что игрок перед которым осталось 5,9,13,17,21,25 и 29 спичек проигрывает при правильной игре противника первый игрок может выиграть взяв 1 спичку на первом ходу.
Чтобы спланировать k-ый шаг нужно знать состояние на k-1 шаге. Если состояние системы на k-1 шаге неизвестно, то делают предположение о его возможных состояниях и затем для каждого предположения выбирают оптимальное управление на последнем шаге и так двигаясь от конца к началу, где на нулевом шаге приходят к определению первого шага. В этом состоит рекурсивность.
*Рассмотрим задачу о минимизации расхода горючего самолетом при наборе высоты и скорости:
Пусть самолёт находится на высоте , скорость . Должен подняться на высоту и набрать скорость . Известен расход горючего при подъёме самолёта с любой высоты на любую высоту , с const V. А так же расход горючего при изменении скорости с до , при const высоте.Найти оптимальное управление высоты и скорости, при котором расход горючего будет минимальным.
Из условия задачи видно, что состояние физической системы S (самолёт) характеризуется V и H. Поэтому решение будем искать на плоскости VOH, при этом ОДЗ будет ограничена прямоугольником. Начальное состояние системы обозначим (,). Конечное состояние ().
Разобьем - на частей
- на частей
Траекторий очень много и они будут ступенчатого вида, W – расход горючего.
, k= - Это свойство аддитивности критерия.
Задачу можно решить перебором, но при больших и это потребует много времени. Поэтому используем динамическое программирование.
