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

14.05.2019

РЕФЕРАТ

«Методы динамического

программирования».

ВВЕДЕНИЕ

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

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

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

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

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

ОСНОВНЫЕ ПОНЯТИЯ И ОБОЗНАЧЕНИЯ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

Пусть планируется деятельность группы предприятий на N лет. Здесь шагом является один год. В начале 1-го года на развитие предприятий выделяются средства, которые должны быть как-то распределены между этими предприятиями. В процессе их функционирования выделенные средства частично расходуются. Каждое предприятие за год приносит некоторый доход, зависящий от вложенных средств. В начале года имеющиеся средства могут перераспределяться между предприятиями: каждому из них выделяется какая-то доля средств.

Ставится вопрос: как в начале каждого года распределять имеющиеся средства между предприятиями, чтобы суммарный доход от всех предприятий за N лет был максимальным?

Перед нами типичная задача динамического программирования, в которой рассматривается управляемый процесс – функционирование группы предприятий. Управление процессом состоит в распределении (и перераспределении) средств. Управляющим воздействием (УВ) является выделение каких-то средств каждому из предприятий в начале года.

УВ на каждом шаге должно выбираться с учетом всех его последствий в будущем. УВ должно быть дальновидным, с учетом перспективы. Нет смысла выбирать на рассматриваемом шаге наилучшее УВ, если в дальнейшем это помешает получить наилучшие результаты других шагов. УВ на каждом шаге надо выбирать “ c заглядыванием в будущее”, иначе возможны серьезные ошибки.

Действительно, предположим, что в рассмотренной группе предприятий одни заняты выпуском предметов потребления, а другие производят для этого машины. Причем целью является получение за N лет максимального объема выпуска предметов потребления. Пусть планируются капиталовложения на первый год. Исходя их узких интересов данного шага (года), мы должны были бы все средства вложить в производство предметов потребления, пустить имеющиеся машины на полную мощность и добиться к концу года максимального объема продукции. Но правильным ли будет такое решение в целом? Очевидно, нет. Имея в виду будущее, необходимо выделить какую-то долю средств и на производство машин. При этом объем продукции за первый год, естественно, снизится, зато будут созданы условия, позволяющие увеличивать ее производство в последующие годы.

В формализме решения задач методом динамического программирования будут использоваться следующие обозначения:

N – число шагов.

– вектор, описывающий состояние системы на k -м шаге.

– начальное состояние, т. е. c остояние на 1-м шаге.

– конечное состояние, т. е. cостояние на последнем шаге.

X k – область допустимых состояний на k -ом шаге.

– вектор УВ на k -ом шаге, обеспечивающий переход системы из состояния x k -1 в состояние x k .

U k – область допустимых УВ на k -ом шаге.

W k – величина выигрыша, полученного в результате реализации k -го шага.

S – общий выигрыш за N шагов.

– вектор оптимальной стратегии управления или ОУВ за N шагов.

S k +1 ( ) – максимальный выигрыш, получаемый при переходе из любого состояния в конечное состояние при оптимальной стратегии управления начиная с (k +1)-го шага.

S 1 ( ) – максимальный выигрыш, получаемый за N шагов при переходе системы из начального состояния в конечное при реализации оптимальной стратегии управления . Очевидно, что S = S 1 ( ), если –фиксировано.

Метод динамического программирования опирается на условие отсутствия последействия и условие аддитивности целевой функции.

Условие отсутствия последействия . Состояние , в которое перешла система за один k -й шаг, зависит от состояния и выбранного УВ и не зависит от того, каким образом система пришла в состояние , то есть

Аналогично, величина выигрыша W k зависит от состояния и выбранного УВ , то есть

Условие аддитивности целевой функции. Общий выигрыш за N шагов вычисляется по формуле

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

Условие отсутствия последействия позволяет сформулировать принцип оптимальности Белмана.

Принцип оптимальности.

Каково бы ни было допустимое состояние системы перед очередным i -м шагом, надо выбрать допустимое УВ на этом шаге так, чтобы выигрыш W i на i -м шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным.

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

Управление может быть хорошим или плохим, эффективным или неэффективным. Эффективность управления оценивается показателем S . Возникает вопрос: как выбрать шаговые управления , чтобы величина S обратилась в максимум?

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

Таким образом, перед нами стоит задача: определить оптимальное управление на каждом шаге (i=1,2,... N) и, значит, оптимальное управление всем процессом .

ИДЕИ МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Мы отметили, что планируя многошаговый процесс, необходимо выбирать УВ на каждом шаге с учетом его будущих последствий на еще предстоящих шагах. Однако, из этого правила есть исключение. Среди всех шагов существует один, который может планироваться без "заглядывания в будущее". Какой это шаг? Очевидно, последний - после него других шагов нет. Этот шаг, единственный из всех, можно планировать так, чтобы он как таковой принес наибольшую выгоду. Спланировав оптимально этот последний шаг, можно к нему пристраивать предпоследний, к предпоследнему - предпредпоследний и т.д.

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

N -й шаг. А как его спланировать, если мы не знаем, чем кончился предпоследний? Очевидно, нужно сделать все возможные предположения о том, чем кончился предпоследний, ( N - 1)-й шаг, и для каждого из них найти такое управление, при котором выигрыш (доход) на последнем шаге был бы максимален. Решив эту задачу, мы найдем условно оптимальное управление (УОУ) на N -м шаге, т.е. управление, которое надо применить, если (N - 1)-й шаг закончился определенным образом.

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

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

Теперь предположим, что УОУ на каждом шаге нам известно: мы знаем, что делать дальше, в каком бы состоянии ни был процесс к началу каждого шага. Тогда мы можем найти уже не "условное", а действительно оптимальное управление на каждом шаге. |

Действительно, пусть нам известно начальное состояние процесса. Теперь мы уже знаем, что делать на первом шаге: надо применить УОУ, найденное для первого шага и начального состояния. В результате этого управления после первого шага система перейдет в другое состояние; но для этого состояния мы знаем УОУ и т.д. Таким образом, мы найдем оптимальное управление процессом, приводящее к максимально возможному выигрышу.

Таким образом, в процессе оптимизации управления методом динамического программирования многошаговый процесс "проходится" дважды:

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

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

Можно сказать, что процедура построения оптимального управления

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

Предварительную;

Окончательную.

На предварительной стадии для каждого шага определяется УОУ, зависящее от состояния системы (достигнутого в результате предыдущих шагов), и условно оптимальный выигрыш на всех оставшихся шагах, начиная с данного, также зависящий от состояния. На окончательной стадии определяется (безусловное) оптимальное управление для каждого шага. Предварительная (условная) оптимизация производится по шагам в обратном порядке: от последнего шага к первому; окончательная (безусловная) оптимизация - также по шагам, но в естественном порядке: от первого шага к последнему. Из двух стадий оптимизации несравненно более важной и трудоемкой является первая. После окончания первой стадии выполнение второй трудности не представляет: остается только "прочесть" рекомендации, уже заготовленные на первой стадии.

Примеры задач динамического программирования

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

Именно на этой идее основан метод динамического программирования.

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

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

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

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

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

Сформулируем общий принцип, лежащий в основе решения всех задач динамического программирования («принцип оптимальности»):

«Каково бы ни было состояние системы S перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным».

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

При постановке задач динамического программирования следует руководствоваться следующими принципами:

Выбрать параметры (фазовые координаты), характеризующие состояние S управляемой системы перед каждым шагом.

Расчленить операцию на этапы (шаги).

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

Определить какой выигрыш приносит на i-ом шаге управление xi, если перед этим система была в состоянии S, т.е. записать «функцию выигрыша»:

Определить, как изменяется состояние S системы S под влиянием управление xi на i-ом шаге: оно переходит в новое состояние

. (1.1)

Записать основное рекуррентное уравнение динамического программирования, выражающее условный оптимальный выигрыш W i ( S ) (начиная с i -го шага и до конца) через уже известную функцию W i +1 ( S ):

. (1.2)

Этому выигрышу соответствует условное оптимальное управление на i -м шаге x i ( S ) (причем в уже известную функцию W i +1 ( S ) надо вместо S подставить измененное состояние

Заметим, что если состояние системы в начальный момент известно (а это обычно бывает так), то на первом шаге варьировать состояние системы не нужно - прямо находим оптимальный выигрыш для данного начального состояния S 0 . Это и есть оптимальный выигрыш за всю операцию

Данные этапы рассматривались для аддитивных задач, в которых выигрыш за всю операцию равен сумме выигрышей на отдельных шагах. Метод динамического программирования применим также и к задачам с так называемым «мультипликативным» критерием, имеющим вид произведения:

(если только выигрыши w i положительны). Эти задачи решаются точно так же, как задачи с аддитивным критерием, с той единственной разницей, что в основном уравнении (1.2) вместо знака «плюс» ставится знак «умножения»:

3.1. Задача планирования рабочей силы

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

Предположим, что проект будет выполняться в течение n недель и минимальная потребность в рабочей силе на протяжении i -й недели составит b i рабочих. При идеальных условиях хотелось бы на протяжении i -й недели иметь в точности b i рабочих. Однако в зависимости от стоимостных показателей может быть более выгодным отклонение численности рабочей силы как в одну, так и в другую сторону от минимальных потребностей.

Если x i i -й недели, то возможны затраты двух видов: 1) С 1 ( x i - b i )-затраты, связанные с необходимостью содержать избыток x i - b i рабочей силы и 2) С 2 ( x i - x i -1 )-затраты, связанные с необходимостью дополнительного найма (x i - x i -1 ) рабочих.

Элементы модели динамического программирования определяются следующим образом:

Этап і представляется порядковым номером недели і , і =1,2,… n .

Вариантами решения на і -ом этапе являются значения x i – количество работающих на протяжении і- й недели.

Состоянием на і-м этапе является x i -1 – количество работающих на протяжении (і- 1) –й недели (этапа).

Рекуррентное уравнение динамического программирования представляется в виде:

где

Вычисления начинаются с этапа n при x n = b n и заканчиваются на этапе 1.

3.2. Задача замены оборудования

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

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

Обозначим через r ( t ) и c ( t ) прибыль от эксплуатации t -летнего механизма на протяжении года и затраты на его обслуживание за этот же период. Далее пусть s ( t ) – стоимость продажи механизма, который эксплуатировался t лет. Стоимость приобретения нового механизма остается неизменной на протяжении всех лет и равна l .

Элементы модели динамического программирования таковы:

Этап і представляется порядковым номером года і, і=1,2,... n .

Вариантами решения на і -м этапе (т.е. для і -ого года) являются альтернативы: продолжить эксплуатацию или заменить механизм в начале і- ого года.

Состоянием на і -м этапе является срок эксплуатации t (возраст) механизма к началу і -ого года.

Пусть f i ( t )-максимальная прибыль, получаемая за годы от і до n при условии, что в начале і- ого года имеется механизм t -летнего возраста.

Рекуррентное уравнение имеет следующий вид:

(1)-если эксплуатировать механизм,

(2)-если заменить механизм.

3.3. Задача инвестирования

Предположим, что в начале каждого из следующих n лет необходимо сделать инвестиции P 1 , P 2 ,…, P n соответственно. Вы имеете возможность вложить капитал в два банка: первый банк выплачивает годовой сложный процент r 1 , а второй - r 2 . Для поощрения депозитов оба банка выплачивают новым инвесторам премии в виде процента от вложенной суммы.

Премиальные меняются от года к году, и для і -ого года равны q i 1 и q i 2 в первом и втором банках соответственно. Они выплачиваются к концу года, на протяжении которого сделан вклад, и могут быть инвестированы в один из двух банков на следующий год. Это значит, что лишь указанные проценты и новые деньги могут быть инвестированы в один из двух банков. Размещенный в банке вклад должен находиться там до конца рассматриваемого периода. -1) -го года.

Пусть f i (x i )- оптимальная сумма инвестиций для интервала от і-го до n -го года при условии, что в начале і-го года имеется денежная сумма x i n -й год являются частью накопленной денежной суммы от инвестиций, в выражения для s n добавлены q n 1 и q n 2 .

Итак, в данном случае рекуррентное уравнение для обратной прогонки в алгоритме динамического программирования имеет вид

где x i +1 выражается через x i в соответствии с приведенной выше формулой, а f n +1 (x n +1 )=0.

4. Общая структура динамического программирования

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

Для реализации такого метода необходимо выяснить все ситуации, в которых может происходить выбор последнего решения. Обычно условия, в которых принимается решение, называют «состоянием» системы. Состояние системы – это описание системы, позволяющее, учитывая будущие решения, предсказать ее поведение. Нет необходимости выяснять, как возникло то ил иное состояние или каковы были предшествующие решения. Это позволяет последовательно выбирать всего по одному решению в каждый момент времени. Независимо от того, отыскивают оптимальные решения с помощью табличного метода и последующего поиска или аналитическим путем, обычно быстрее и выгоднее производить выбор по одному решению в один момент времени, переходя затем к следующему моменту и т.д. К сожалению, таким методом можно исследовать не все процессы принятия решений. Необходимым условием применения метода динамического программирования является аддитивность цен всех решений, а также независимость будущих результатов от предыстории того или иного состояния.

Если число решений очень велико, то можно построить относительные оценки состояний так, чтобы оценки, отвечающие каждой паре последовательных решений, отличались друг от друга на постоянную величину, представляющую собой средний «доход» на решение. Также можно выполнять дисконтирование доходов от будущих решений. Необходимость в этом иногда появляется в том случае, когда решение принимаются редко, скажем раз в году. Тогда уже не нужно рассматривать последовательно 1,2,3…решения, чтобы достичь решения с большим номером. Вместо этого можно непосредственно оперировать функциональным уравнением, что, как правило, дает существенную выгоду с точки зрения сокращения объема вычислений.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

В течение 50-х годов XX века американский математик Р. Беллман и ряд его сотрудников развили новый общий метод решения вариационных задач, названный или динамическим программированием. Этот метод пригоден для оптимизации любых сложных систем, описываемых не только дифференциальными уравнениями с ограничениями на переменной, или без них, но и другим математическим аппаратом, включая различные статические системы, СМО и экономические системы.

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

В МДП принят иной путь нахождения оптимальной траекторий, который заключается в том, что оптимальная траектория и соответствующая ей уравнение ищутся на отдельных участках или ступенях. Иными словами, проще разбиваются на несколько ступеней, на каждой стоится множество траекторий и соответствующих им управлений. Теперь казалось бы достаточно перебрать все траектории, и выбрать оптимальную, но это нерациональный титанический труд. Создатели МДП пошли другим путем – на каждой стадии они выбирают оптимальную и отбрасывают неоптимальные, бесперспективные участки траекторий (на отдельной стадии для участка это сделать много легче, чем для траектории в целом). При этом оказывается, что отбрасывается не только не оптимальный кусочек траектории на этой стадии, но и вся траектория в целом, которые в своем составе имеют неперспективный кусочек на рассматриваемой стадии. Выбор оптимальной траектории при этом ставится намного легче и короче.

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

Пример .

Пусть между пунктами и следует проложить железную дорогу или шоссейную минимальной стоимости. Рельеф местности очень сложный и предварительные изыскания показали, что если дорогу проложить по прямой , её стоимость будет очень высокой. Геодезисты и экономисты рассмотрели отдельные сравнительно простые для строительства участки между и и определили стоимость строительства этих участков. Стоимость строительства дороги будет суммой стоимости строительства этих участках. Данную задачу можно решить перебором всех возможных траекторий между и и выбрать самую дешевую. Однако этот путь практически необозрим. По этому найдем по пути МДП. Разобьем весь район строительства на стадии, из которых до начальной или конечной точек можно попасть за одинаковое количество шагов. В МДП решение начинается с конца и хотя в нашем случае начало и конец неразличимы, по традиции МДП решение начинается с конца . Рассмотрим переход стадии к точке . Причем нас совершено не интересует предыстория движения, т.е. каким образом мы попали на стадию , но уже если попали в точку или , то попасть в точку мы можем за один шаг с затратами 8 из точки или 9 из точки . Эти затраты и ставим в соответствующие кружочки. Других траекторий из стадии в точку нет.

Сдвинемся еще на шаг назад на стадию и проанализируем траектории, по которым а точку можно попасть за два шага из точки до стадии можно попасть единственным образом , а в точку за два шага можно попасть по единственной траектории и стоимость это го участка 8 денежных единиц. А из точки до стадии можно попасть единственным образом и стоимость этого участка 25 д. ед. А из точки до стадии можно попасть двумя путями (стоимость 10 д.ед.) и (стоимость 11 д.ед.). И здесь на стадии (а не на всей траектории) очень легко выбрать оптимальный путь () и отвергнуть бесперспективный (). При этом отвергается не только бесперспективный путь , но и все траектории, исходящие из точки и включающие участок к . В кружочек поставим наименьшую стоимость пути д.ед.

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

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

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

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

Причем -вектор координат состояния

- вектор управления

Пусть и требуется минимизировать интеграл

В основе МДП лежит принцип оптимальности. Этот принцип сформулирован Р. Беллманом для широкого круга систем, будущее поведение которых полностью определяется их состоянием в настоящем. Поэтому оно не зависит от характера их «предыстории», т.е. поведение системы в прошлом, коль скоро система находится в данный момент в данном состоянии. Для иллюстрации рассмотрим оптимальную траекторию в мерном фазовом пространстве с начальным и конечным значением вектора , равным при и при .

Пусть начальное условие заданы, значение , вообще говоря, не известно.

Отметим какую-либо промежуточную точку , траектории, соответствующую ,где и назовем участок траектории от до первым, а от до - вторым.

Второму участку соответствует часть интеграла (1), равная

Второй участок траектории может рассматриваться и как самостоятельная траектория. Она будет оптимальной, если соответствующий ей интеграл минимален. Принцип оптимальности можно сформулировать так:

Это означает, что в том случае, когда начальное состояние системы есть , а начальный момент времени , то не зависимо от того, каким образом пришла система к этому состоянию. Ее оптимальным последующим движением будет траектория 2. Действительно допустим противное – тогда критерий (1), рассматриваемый для интервала времени от до , будет наименьшим не для траектории 2, а для какой-либо иной траектории , исходящей из точки и показанной пунктиром на рис.2. Но в этом случае можно было бы построить «лучшую» траекторию, чем траектория 1-2, и для первоначальной задачи, нужно лишь выбрать управление таким, чтобы описываемая траектория 1, а затем . Между тем мы исходим из того, что траектория 1-2 оптимальна. Противоречие доказывает невозможность существования траектории , обеспечивающее меньшее значение, чем траектория 2. И так траектория 2 оптимальна.

Сформулированный выше принцип оптимальности является весьма общим необходимым условием оптимального процесса, справедливым как для непрерывных, так и для дискретных систем.

Принцип оптимальности выглядит почти тривиальным и, на первый взгляд бедным по содержанию утверждением. Однако из него можно, как показывал Беллман, методически рассуждая вывести необходимое условие для оптимальной траектории, имеющее отнюдь не тривиальный характер. В сущности, принцип оптимальности не так уж тривиален, как может в начале показаться. Это видно хотя бы из того, что утверждение, кажущееся его обобщением: «Любой участок оптимальной траектории является оптимальной траекторией» - вообще говоря, не справедливо. Так, например, первый участок траектории на рис.2 может сам по себе не быть оптимальной траекторией, т.е. не давать минимум интегралу , если заданы только лишь начальные условия .

Поясним это утверждение элементарной иллюстрацией. Как распределяет свой силы хороший бегун при беге на длинную дистанцию? Действует ли он по принципу: Беги на каждом отрезке на столько быстро, на сколько сможешь? Конечно нет, ведь, бегун может «выдохнуться» за долго до подхода к цели. Разумно распределяя свои ресурсы в соответствии с конечной целью, бегун в начале экономит свои силы, чтобы не «выдохнуться» в конце дистанции. Аналогичным образом любое управлением не должно быть «близоруким», не должно руководствоваться лишь достижением наилучшего моментального, локального эффекта. Оно должно быть «дальновидным», оно должно быть подчинено конечной цели, т.е. минимизации функционала (1) на всем интервале от до . Только в том случае, когда задана конечная точка первого участка при , первый участок также сам по себе является оптимальной траекторией.

Можно дать и другую формулировку принципа оптимальности:

Эквивалентность этой и предыдущей формулировок очевидно, если понимать под «предысторией» системы ту траекторию 1, по которой изображающая точка пришла в положение (рис.2). Под состоянием системы в рассматриваемый момент времени понимается в данном случае именно то состояние, соответствующее точке при .

Поясним метод рассуждения Беллмана на простом принципе управляемого объекта с управлением

Где – единственная координата системы:

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

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

где для удобства за примем время равное нулю, т.е. ; значение будем для простоты считать фиксированным.

Прежде всего дискретизируем задачу, т.е. приближено значением непрерывную систему дискретно-непрерывной. Основания для этого следующее: во первых, дискретизация является неизбежным этапом подготовки задачи для ее решения на ЭВМ.

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

Разобьем интервал на равных участков малой длины и будем рассматривать лишь дискретные значения и в моменты времени . Тогда дифференциальное уравнение (27) объекта можно приближенно заменить уравнением в конечных разностях

Начальное условие остается прежним

Интервал (28) приближенно заменяется суммой

Задача теперь состоит в определении последовательности дискретных значений управляющего воздействия , т.е. величины , минимизирующих сумму (32) при условиях (4), (30) и (31), наложенных на систему таким образом, требуется найти минимум сложной функции многих переменных. Однако МДП дает возможность свести эту операцию к последовательности минимизаций значительно более простых функций одного переменного.

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

Рассмотрим последний участок траектории от до . Величина влияет лишь на те члены суммы (32), которые относятся к этому участку.

Обозначим сумму этих членов через .

из (30) получаем

Следовательно, так же зависит от . Найдем допустимое значение , удовлетворяющее (4) и минимизирующее величину . Обозначим найденное минимальное значение через . Эта величина очевидно зависит от состояния системы при т.е. от значения , входящее в (33) и (34). И так

Обратим внимание на то, что для определения нужно проводить минимизацию только по одному переменному простого выражения (33)(вместо минимизации по многим переменным ) сложного выражения (32), выполнив этот процесс, получим в виде функций от ; эту функцию следует запомнить, например, в каком либо запоминающем устройстве при вычислении на ЭВМ) при переходе к последующим стадиям решения.

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

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

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

Решением задачи динамического программирования является определение такого управления , которое переводит систему из состояния в состояние при наибольшем (наименьшем) значении .

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

Рассмотрим последний шаг . Состояние системы к началу шага , управление, а - целевая функция. Согласно принципу оптимальности управление нужно выбирать так, чтобы для любого состояния получался условный максимум целевой функции

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

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

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

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

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

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

При практической реализации метода динамического программирования на ЭВМ возникает ряд трудностей, связанных, в частности, со способами описания состояния объекта управления. Как правило, рассматривается конечное число состояний объекта управления на каждом шаге. Тем не менее, наибольший интерес представляет случай отыскания оптимального состояния объекта из бесконечного числа возможных состояний, например, методом математического программирования. В доступной литературе такие материалы отсутствуют, кроме того, не имеется сведений о программной реализации метода динамического программирования, хотя потребность в решении таких задач в достаточно велика. Из сказанного следует, что доведение методов динамического программирования до практического использования представляет собой актуальную и важную задачу исследования.

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

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

Итак, рассмотрим операцию Ơ , состоящую из Т Шагов (этапов). Пусть эффективность операции характеризуется каким-то показателем W , который мы для краткости будем в этой главе называть «выигрышем». Предположим, что выигрыш W за всю операцию складывается из выигрышей на отдельных шагах:

Где Wi - выигрыш на I -м шаге.

Если W обладает таким свойством, то его называют «аддитивным критерием».

Операция О, о которой идет речь, представляет собой управляемый процесс, т. е. мы можем выбирать какие-то параметры, влияющие на его ход и исход, причем на каждом шаге выбирается какое-то решение, от которого зависит выигрыш на данном шаге и выигрыш за операцию в целом. Будем называть это решение «шаговым управлением». Совокупность всех шаговых управлений представляет собой управление операцией в целом. Обозначим его буквой Х, а шаговые управления - буквами Х1, х2, …, Xm :

X = (X 1 , X 2 , …, Xm ). (12.2)

Следует иметь в виду, что Х1, х2, …., Xm в общем случае - не числа, а, может быть, векторы, функции и т. д.

Требуется найти такое управление Х, при котором выигрыш W обращается в максимум:

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

Х* = (). (12.4)

Тот максимальный выигрыш, который достигается при этом управлении, мы будем обозначать W* :

W* = {W (х) }. (12.5)

Формула (12.5) читается так: величина W * есть максимум из всех W { X } при разных управлениях Х (максимум берется по всем управлениям Х, возможным в данных условиях). Иногда это последнее оговаривается в формуле и пишут:

Рассмотрим несколько примеров многошаговых операций и для каждого из них поясним, что понимается под «управлением» и каков «выигрыш» (показатель эффективности) W.

1. Планируется деятельность группы промышленных предприятий П1, П2, …, ПK на период Т хозяйственных лет (M -летку). В начале периода на развитие группы выделены какие-то средства М, которые должны быть как-то распределены между предприятиями. В процессе работы предприятия, вложенные в него средства частично расходуются (амортизируются), а частично сохраняются и снова могут быть перераспределены. Каждое предприятие за год приносит доход, зависящий от того, сколько средств в него вложено. В начале каждого хозяйственного года имеющиеся в наличии средства перераспределяются между предприятиями. Ставится вопрос: какое количество средств в начале каждого года нужно выделять каждому предприятию, чтобы суммарный доход за Т лет был максимальным?

Выигрыш W (суммарный доход) представляет собой сумму доходов на отдельных шагах (годах):

И, значит, обладает свойством аддитивности.

Управление X I на I -м шаге состоит в том, что в начале I -го года предприятиям выделяются какие-то средства Х I 1 , х I 2 , …, х Ik (первый индекс - номер шага, второй - номер предприятия). Таким образом, шаговое управление есть вектор с K составляющими:

Xi = (Xi 1 , Xi 2 , …, Xik ). (12.7)

Разумеется, величины Wi в формуле (12.6) зависят от количества вложенных в предприятия средств.

Управление Х всей операцией состоит из совокупности всех шаговых управлений:

X = (X 1 , X 2 , …, Xm ). (12.8)

Требуется найти такое распределение средств по предприятиям и по годам (оптимальное управление X * ), при котором величина W обращается в максимум.

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

2. Космическая ракета состоит из Т ступеней, а процесс ее вывода на орбиту - из M этапов, в конце каждого из которых очередная ступень сбрасывается. На все ступени (без учета «полезного» веса кабины) выделен какой-то общий вес:

G = G 1 + G 2 + … + Gm ,

Где Gi - вес I -й ступени.

В результате I -го этапа (сгорания и сбрасывания 1-й ступени) ракета получает приращение скорости , зависящее от веса данной ступени и суммарного веса всех оставшихся плюс вес кабины. Спрашивается, как нужно распределить вес G между ступенями, чтобы скорость ракеты V при ее выводе на орбиту была максимальна?

В данном случае показатель эффективности (выигрыш) будет

V = (12.9)

Где - выигрыш (приращение скорости) на I -м шаге. Управление Х представляет собой совокупность весов всех ступеней Gi :

Х = (Gi , Gi , …, Gm ).

Оптимальным управлением Х* будет то распределение весов по ступеням, при котором скорость V максимальна. В этом примере шаговое управление - одно число, а именно, вес данной ступени.

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

1) продать машину и заменить ее новой;

2) ремонтировать ее и продолжать эксплуатацию;

3) продолжать эксплуатацию без ремонта.

Шаговое управление - выбор одного из этих трех решений. Непосредственно числами они не выражаются, но можно приписать первому численное значение 1, второму 2, третьему 3. Какие нужно принять решения по годам (т. е. как чередовать управления 1, 2, 3), чтобы суммарные расходы на эксплуатацию, ремонт и приобретение новых машин были минимальны?

Показатель эффективности (в данном случае это не «выигрыш», а «проигрыш», но это неважно) равен

W = (12.10)

Где Wi - расходы в I -м году. Величину W требуется обратить в минимум.

X = (3, 3, 2, 2, 2, 1, 3, …),

Что означает: первые два года эксплуатировать машину без ремонта, последующие три года ее ремонтировать, в начале шестого года продать, купить новую, затем снова эксплуатировать без ремонта и т. д. Любое управление представляет собой вектор (совокупность чисел):

Х = (J 1 , J 2 , …; Jm ), (12.11)

Где каждое из чисел J 1 , J 2 , …, Jm имеет одно из трех значений: 1, 2 или 3. Нужно выбрать совокупность чисел (12.11), при которой величина (12.10) минимальна.

4. Прокладывается участок железнодорожного пути между пунктами А и В (рис. 12.1). Местность пересеченная, включает лесистые зоны, холмы, болота, реку, через которую надо строить мост. Требуется так провести дорогу из А и В, чтобы суммарные затраты на сооружение участка были минимальны.

В этой задаче, в отлично от трех предыдущих, нет естественного членения на шаги: его приходится вводить искусственно, для чего, например, можно отрезок АВ разделить на Т частей, провести через точки деления прямые, перпендикулярные АВ, и считать за «шаг» переход с одной такой прямой на другую. Если провести их достаточно близко друг от друга, то можно считать на каждом шаге участок пути прямолинейным. Шаговое управление на г-м шаге представляет собой угол , который составляет участок пути с прямой АВ. Управление всей операцией состоит из совокупности шаговых управлений:

Х = ().

Требуется выбрать такое (оптимальное) управление Х *, при котором суммарные затраты па сооружение всех участков минимальны:

W = => Min. (12.12)

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

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

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

С первого взгляда идея может показаться довольно тривиальной. В самом деле, чего казалось бы, проще:

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

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

Пусть, например, планируется работа группы промышленных предприятий, из которых часть занята выпуском предметов потребления, а остальные производят для них машины. Задача операции - получить за Т лет максимальный объем выпуска предметов потребления. Допустим, планируются капиталовложения на первый год. Исходя из узких интересов этого шага (года), мы должны были бы все наличные средства вложить в производство предметов потребления. Но правильно ли будет такое решение с точки зрения эффективности операции в целом? Очевидно, нет. Это решение - расточительное, недальновидное. Имея в виду будущее, надо выделить какую-то долю средств и на производство машин. От этого объем продукции за первый год, конечно, снизится, зато будут созданы условия для его увеличения в последующие годы.

Еще пример. Допустим, что в задаче 4 (прокладка железнодорожного пути из А в В ) мы прельстимся идеей сразу же устремиться по самому легкому (дешевому) направлению. Что толку от экономии на первом шаге, если в дальнейшем он заведет нас (буквально или фигурально) в «болото»?

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

Однако из этого правила есть исключение. Среди всех шагов есть один, который может планироваться попросту, без оглядки на будущее. Какой это шаг? Очевидно, последний! Этот шаг, единственный из всех, можно планировать так, чтобы он сам, как таковой, принес наибольшую выгоду.

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

Вот тут-то и начинается самое главное. Планируя последний шаг, нужно сделать разные предположения о том, чем кончился предпоследний, (т — 1)-й шаг, и для каждого из этих предположений найти условное оптимальное управление на M -м шаге («условное» потому, что оно выбирается исходя из условия, что предпоследний шаг кончился так-то и так-то).

Предположим, что мы это сделали, и для каждого из возможных исходов предпоследнего шага знаем условное оптимальное управление и соответствующий ему условный оптимальный выигрыш на M -м шаге. Отлично! Теперь мы можем оптимизировать управление на предпоследнем, (т- 1)-м шаге. Снова сделаем все возможные предположения о том, чем кончился предыдущий, (M — 2)-й шаг, и для каждого из этих предположений найдем такое управление на (M — 1)-м шаге, при котором выигрыш за последние два шага (из которых M -й уже оптимизирован!) максимален. Так мы найдем для каждого исхода (M — 2)- шага условное оптимальное управление на (т — 1)-м шаге и условный оптимальный выигрыш на двух последних шагах. Далее, «пятясь назад», оптимизируем управление на (M — 2)-м шаге и т. д., пока не дойдем до первого.

Предположим, что все условные оптимальные управления и условные оптимальные выигрыши за весь «хвост» процесса (на всех шагах, начиная от данного и до конца) нам известны. Это значит: мы знаем, что надо делать, как управлять на данном шаге и что мы за это получим на «хвосте», в каком бы состоянии ни был процесс к началу шага. Теперь мы можем построить уже не условно оптимальное, а просто оптимальное управление Х* и найти не условно оптимальный, а просто оптимальный выигрыш W *.

В самом деле, пусть мы знаем, в каком состоянии S 0 была управляемая система (объект управления S ) в начале первого шага. Тогда мы можем выбрать оптимальное управление на первом шаге. Применив его, мы изменим, состояние системы на некоторое новое ; в этом состоянии мы подошли ко второму шагу. Тогда нам тоже известно условное оптимальное управление , которое к концу второго шага переводит систему в состояние , и т. д. Что касается оптимального выигрыша W* за всю операцию, то он нам уже известен: ведь именно на основе его максимальности мы выбирали управленце на первом шаге.

Таким образом, в процессе оптимизации управления методом динамического программирования многошаговый процесс «проходится» дважды: первый раз - от конца к началу, в результате чего находятся условные оптимальные управления и условные оптимальные выигрыши за оставшийся «хвост» процесса; второй раз - от начала к концу, когда нам остается только «прочитать» уже готовые рекомендации и найти безусловное оптимальное управление Х*, состоящее из оптимальных шаговых управлений

Первый этап - условной оптимизации - несравненно сложнее и длительнее второго. Второй этап почти не требует дополнительных вычислений.

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

Достаточно общая теория управления СССР Внутренний Предиктор

14. Метод динамического программирования как алгоритмическое выражение достаточно общей теории управления

В изложении существа метода динамического программирования мы опираемся на книгу “Курс теории автоматического управления” (автор Палю де Ла Барьер: французское издание 1966 г., русское издание - “Машиностроение”, 1973 г.), хотя и не повторяем его изложения. Отдельные положения взяты из курса “Исследование операций” Ю.П.Зайченко (Киев, “Вища школа”, 1979 г.).

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

1. Рассматриваемая задача может быть представлена как N -шаговый процесс, описываемый соотношением:

X = f(X U , n) , где n - номер одного из множества возможных состояний системы, в которое она переходит по завершении n -ного шага; X - вектор состояния системы, принадлежащий упомянутому n -ному множеству; U - управление, выработанное на шаге n (шаговое управление), переводящее систему из возможного её состояния в n -ном множестве в одно из состояний (n + 1 )-го множества. Чтобы это представить наглядно, следует обратиться к рис. 4, о котором речь пойдет далее.

2. Структура задачи не должна изменяться при изменении расчетного количества шагов N.

3. Размерность пространства параметров, которыми описывается состояние системы, не должна изменяться в зависимости от количества шагов N.

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

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

5. Критерий оптимального выбора последовательности шаговых управлений U и соответствующей траектории в пространстве формальных параметров имеет вид:

V = V (X , U) + V (X , U) + …+ V (X , U) + V (X).

Критерий V принято называть полным выигрышем, а входящие в него слагаемые - шаговыми выигрышами . В задаче требуется найти последовательность шаговых управлений U и траекторию, которым соответствует максимальный из возможных полных выигрышей . По своему существу полный “выигрыш” V - мера качества управления процессом в целом . Шаговые выигрыши, хотя и входят в меру качества управления процессом в целом, но в общем случае не являются мерами качества управления на соответствующих им шагах, поскольку метод предназначен для оптимизации управления процессом в целом, а эффектные шаговые управления с большим шаговым выигрышем, но лежащие вне оптимальной траектории, интереса не представляют. Структура метода не запрещает при необходимости на каждом шаге употреблять критерий определения шагового выигрыша V , отличный от критериев, принятых на других шагах.

С индексом n - указателем-определителем множеств возможных векторов состояния - в реальных задачах может быть связан некий изменяющийся параметр, например: время, пройденный путь, уровень мощности, мера расходования некоего ресурса и т.п. То есть метод применим не только для оптимизации управления процессами, длящимися во времени, но и к задачам оптимизации многовариантного одномоментного или нечувствительного ко времени решения, если такого рода “безвременные”, “непроцессные” задачи допускают их многошаговую интерпретацию.

Теперь обратимся к рис. 4 - рис. 6, повторяющим взаимно связанные рис. 40, 41, 42 из курса теории автоматического управления П. де Ла Барьера.

Рис. 4. К существу метода динамического программирования. Матрица возможностей.

На рис. 4 показаны начальное состояние системы - «0» и множества её возможных последующих состояний - «1», «2», «3», а также возможные переходы из каждого возможного состояния в другие возможные состояния. Всё это вместе похоже на карту настольной детской игры, по которой перемещаются фишки: каждому переходу-шагу соответствует свой шаговый выигрыш, а в завершающем процесс третьем множестве - каждому из состояний системы придана его оценка, помещенная в прямоугольнике. Принципиальное отличие от игры в том, что гадание о выборе пути, употребляемое в детской игре, на основе бросания костей или вращения волчка и т.п., в реальном управлении недопустимо, поскольку это - передача целесообразного управления тем силам, которые способны управлять выпадением костей, вращением волчка и т.п., т.е. тем, для кого избранный в игре «генератор случайностей» - достаточно (по отношению к их целям) управляемое устройство.

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

Рис. 5. К существу метода динамического программирования. Анализ переходов.

В соответствии с этим на рис. 5 анализируются возможные переходы в завершающее множество состояний «3» из каждого возможного состояния в ему предшествующем множестве состояний «2», будто бы весь предшествующий путь уже пройден и осталось последним выбором оптимального шагового управления завершить весь процесс. При этом для каждого из состояний во множестве «2» определяются все полные выигрыши как сумма = «оценка перехода» + «оценка завершающего состояния». Во множестве «2» из полученных для каждого из состояний, в нём возможных полных выигрышей, определяется и запоминается максимальный полный выигрыш и соответствующий ему переход (фрагмент траектории). Максимальный полный выигрыш для каждого из состояний во множестве «2» взят в прямоугольную рамку, а соответствующий ему переход отмечен стрелкой. Таких оптимальных переходов из одного состояния в другие, которым соответствует одно и то же значение полного выигрыша, в принципе может оказаться и несколько. В этом случае все они в методе неразличимы и эквивалентны один другому в смысле построенного критерия оптимальности выбора траектории в пространстве параметров, которыми описывается система.

После этого множество «2», предшествовавшее завершающему процесс множеству «3», можно рассматривать в качестве завершающего, поскольку известны оценки каждого из его возможных состояний (максимальные полные выигрыши) и дальнейшая оптимизация последовательности шаговых управлений и выбор оптимальной траектории могут быть проведены только на ещё не рассмотренных множествах, предшествующих множеству «2» в оптимизируемом процессе (т.е. на множествах «0» и «1»).

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

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

Рис. 6. К существу метода динамического программирования. Оптимальная траектория.

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

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

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

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

2. Если прогностика в согласии с иерархически высшим объемлющим управлением, а частное вложенное в объемлющее управление осуществляется квалифицировано, в силу чего процесс частного управления протекает в ладу с иерархически высшим объемлющим управлением, то НЕ СУЩЕСТВУЕТ УПРАВЛЕНЧЕСКИ ЗНАЧИМОЙ РАЗНИЦЫ МЕЖДУ .

Процесс целостен, по какой причине ещё не свершившееся, но уже нравственно избранное и объективно не запрещённое Свыше будущее, в свершившемся настоящем защищает тех, кто его творит на всех уровнях: начиная от защиты психики от наваждений до защиты от целенаправленной “физической” агрессии. То есть, если матрица возможных состояний (она же матрица возможных переходов) избрана в ладу с иерархически высшим объемлющим управлением, то она сама - защита и оружие, средство управления, на которое замкнуты все шесть приоритетов средств обобщённого оружия и управления.

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

Но для пользования методом динамического программирования и сопутствующими его освоению неформализованными в алгоритме жизненными проявлениями матриц перехода , необходимо СОБЛЮДЕНИЕ ГЛАВНОГО из условий:

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

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

«Каково бы ни было состояние системы перед очередным шагом, надо выбирать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным», - Е.С.Вентцель, “Исследование операций. Задачи, принципы, методология.” (М., “Наука”, 1988 г., стр. 109).

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

Это тем более справедливо для последовательных многовариантных шаговых переходов, если матрица возможных состояний вписывается в пословицу «Все дороги ведут в “Рим”», . Для такого рода процессов, если избрана устойчивая во времени цель и к ней ведут множество траекторий, то при устойчивом пошаговом управлении “расстояние” между оптимальными траекториями, идущими к одной и той же цели из различных исходных состояний, от шага к шагу сокращается, вплоть до полного совпадения оптимальных траекторий, начиная с некоторого шага. Это утверждение тем более справедливо, чем более определённо положение завершающего процесс вектора целей в пространстве параметров. По аналогии с математикой это можно назвать : асимптотичность множества траекторий выражается в том, что «все дороги ведут в “Рим”…»

И в более общем случае, рекомендации Нового Завета и Корана утверждают возможность обретения благодати, милости Вседержителя вне зависимости от начального состояния (греховности человека) в тот момент, когда он очнулся и увидел свои дела такими, каковы они есть.

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

То есть метод динамического программирования, необходимостью как определённости в выборе конечного состояния-процесса, так и выявления истинного начального состояния, сам собой защищён от применения его для наукообразной имитации оптимизации управления при отсутствии такового. Это отличает метод динамического программирования, в частности от аппарата линейного программирования , в который можно сгрузить экспромтные оценки “экспертами” весовых коэффициентов в критериях оптимизации Min (Z) либо Max (Z) .

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

Примерами тому “Математическая экономика на персональном компьютере” под ред. М.Кубонива , в которой глава об управлении в экономике содержит исключительно макроэкономические интерпретации аппарата линейного программирования (прямо так и названа “Управление в экономике. Линейное программирование и его применение”), но ничего не говорит о векторе целей управления и средствах управления; в ранее цитированном учебнике Ю.П.Зайченко описание метода динамического программирования также построено на задачах иного характера.

Однако при мотивации отказа от макроэкономических интерпретаций метода динамического программирования авторы обычно ссылаются на так называемое в вычислительной математике «проклятие размерности», которое выражается в том, что рост размерности пространства параметров задачи N вызывает рост объема вычислений, пропорциональный N , где показатель степени k» 1. Такой нелинейный сверхпропорциональный рост объема вычислений действительно делает многие вычислительные работоспособные процедуры никчемными в решении практических задач как из-за больших затрат машинного времени компьютеров, так и из-за накопления ошибок в приближённых вычислениях. Но это «проклятие размерности» относится не только к методу динамического программирования, но и к другим методам, которые, однако, встречаются и в их макроэкономических интерпретациях.

Из книги Прозрение автора Ефимов Виктор Алексеевич

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

Из книги Об искоренении глобальной угрозы «международного терроризма» автора СССР Внутренний Предиктор

Отступление от темы 5: Кибернетика и история теории управления На протяжении всей второй половины ХХ века кибернетику представляют обществу в качестве науки об управлении вообще, хотя она - в том виде, в котором её представил публике Н.Винер, - в действительности не

автора СССР Внутренний Предиктор

1. Достаточно общая теория управления: зачем это надо? Всякий разум - индивидуальный или соборный - в иерархии взаимной вложенности структур Мироздания решает прежде всего задачи управления по отношению к иерархически низшим системам и задачи самоуправления в

Из книги 12 тем. Маркетинг 21 века автора Грант Дж

2. Категории достаточно общей теории управления В теории управления возможна постановка всего двух задач.· Первая задача: мы хотим управлять объектом в процессе его функционирования сами непосредственно. Это.· Вторая задача: мы не хотим управлять объектом в процессе

Из книги «О текущем моменте» № 7(79), 2008 г. автора СССР Внутренний Предиктор

Из книги Геннадий Шичко и его метод автора Дроздов Иван

Часть 1. Полная функция управления в толпо-“элитаризме” и в реальном народовластии 1.1. Полная функция управления и первобытная практика её реализации в жизни общества В достаточно общей теории управления (ДОТУ) есть понятие «полная функция управления». Полная функция

Из книги Что нас ждет, когда закончится нефть, изменится климат, и разразятся другие катастрофы автора Кунстлер Джеймс Говард

Из книги Новая опричнина, или Модернизация по-русски автора Калашников Максим

Из книги Что нас ждет, когда закончится нефть, изменится климат и разразятся другие катастрофы XXI века автора Кунстлер Джеймс Говард

Сжатие инновационных циклов – вопрос национального выживания: меморандум Института динамического консерватизма 10 июня 2009 года в Институте динамического консерватизма состоялась экспертная встреча практиков-инноваторов и ученых на тему: «Реальные инновации и их

Из книги Антисемитизм: концептуальная ненависть автора Альтман Илья

Из книги Достаточно общая теория управления автора СССР Внутренний Предиктор

Выражение признательности МАРК ВЕЙЦМАНЭта книга готовилась в честь Симона Визенталя. Поскольку обычно такого рода сборники издаются в честь выдающихся ученых, идея посвятить книгу Симону была чрезвычайно уместна. Не занимая должности научного сотрудника или

Из книги Неужели я гений? автора Венгар Вин

1. Достаточно общая теория управления: зачем это надо? Всякий разум – индивидуальный или соборный – в иерархии взаимной вложенности структур Мироздания решает прежде всего задачи управления по отношению к иерархически низшим системам и задачи самоуправления в

Из книги Куда Кейнс зовет Россию? автора Дзарасов Солтан

Из книги автора

14. Метод динамического программирования как алгоритмическое выражение достаточно общей теории управления В изложении существа метода динамического программирования мы опираемся на книгу “Курс теории автоматического управления” (автор Палю де Ла Барьер: французское

Из книги автора

Выражение признательности Программа ускоренного обучения «Проект возрождения» главная тема этой книги - начала реализовываться 25 лет назад благодаря усилиям огромного количества людей, пионеров в области изучения человеческого сознания, тех, кто принимал участие в

Из книги автора

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