2. Лекции Практические и лабораторные занятия
жүктеу/скачать 0,77 Mb.
|
УМКД метод матер МО и Исл опер
- Бұл бет үшін навигация:
- Рекомендуемая литература
- Лекция 15. Динамическое программирование. Содержание лекционного занятия
| Вопросы для самоконтроля:
1.Необходимые и достаточные условия первого и второго порядков оптимальности в задаче с ограничениями-равенствами. 2.Необходимые и достаточные условия первого и второго порядков оптимальности в задаче со смешанными ограничениями
1.Ашманов С.А. Линейное программирование. —М.: Наука, 1981. 2.Айсагалиев А.С., Айсагалиева С.С. Лекции по методам оптмизации.-Алматы:Гылым,1996
Постановка задачи динамического программирования Многоэтапные процессы принятия решений Принцип оптимальности Р. Беллмана Динамическое программирование — это особый метод, наиболее эффективный при решении задач, распадающихся на ряд последовательных этапов (шагов), таких как планирование производства и инвестиций на ряд временных интервалов (лет, кварталов, месяцев), последовательность тестовых испытаний при контроле аппаратуры, поиск оптимальной траектории движения и др. В любом случае речь идет о процессах, в которых окончательное решение (план, проект, последовательность управляющих воздействий, обеспечивающая нужную траекторию и т.д.) вырабатывается последовательно (по шагам), причем на каждом шаге приходится решать однотипные задачи, которые существенно проще, чем решение исходной задачи в целом. В этом и состоит основная идея метода: свести решение одной сложной задачи к решению множества однотипных, иногда совсем простых задач, например выборка чисел из массива, суммирование и сравнение результатов. Возникновение динамического программирования связано с исследованием многошаговых процессов, возникающих в теории создания запасов. Основная идея, которая привела к созданию вычислительного метода, была сформулирована в начале 50-х гг. прошлого века Р. Беллманом (R. Bellman), сделавшим самый большой вклад в развитие метода, который он назвал «динамическое программирование», но который чаще называют просто метод Беллмана. Метод не является универсальным в отличие, например, от симплекс-метода Данцига для решения задач линейного программирования. Его реализация для каждого конкретного многошагового процесса принятия решений, как правило, требует разработки нового алгоритма. Многие практические задачи, которые можно решать с помощью этого метода, были рассмотрены его автором совместно с Дрейфусом (S. Dreyfus). Первоначально метод предлагался для решения сравнительно узкого класса задач, возникающих в процессах, которые развиваются во времени. Отсюда и название: Динамическое программирование, причем слово программирование скорее означало планирование, чем разработку компьютерных программ. Фактически этот метод, как и симплекс-метод Данцига, был разработан на заре «компьютерной эры», т.е. до массового применения вычислительной техники. Тогда слово «programming» на русский язык переводилось как планирование, и метод Р. Беллмана первоначально назывался динамическое планирование. После появления первых работ Р. Беллмана выяснилось, что для многих задач, которые не являются многоэтапными в явном виде, эту многоэтапность можно организовать искусственно и применить метод Беллмана. Рассмотрим сначала простую задачу поиска оптимального пути на двумерной прямоугольной сетке, в которой разрешены переходы из одного узла в другой только по горизонтали (вправо) или по вертикали (вверх). Рис. 12 Задача поиска оптимального пути. Заданы затраты на каждый из возможных переходов и требуется найти путь с минимальными суммарными затратами из левого нижнего угла сетки (рис. 12, точка А) в правый верхний угол (точка В). Такой путь называется оптимальным. Узлы сетки пронумерованы так, как показано на рис. 12, где тип задают соответственно вертикальный и горизонтальный размеры сетки. Затраты на переход в узел i, j по горизонтали (из узла i, j - 1) составляют gij, а по вертикали (из узла i - 1, j) – vij. В точке А соответствующие величины равны нулю. Таким образом, исходными данными в этой задаче являются: m, n и все шаговые затраты gij и vij (i = 0, 1, 2,..., m; j = 0, 1, 2, ..., п). Всего n (m + 1) чисел gij и m (n + 1) чисел vij, т.е. всего 2mn + m + n переходов и соответствующих им затрат. Следующая идея состоит в том, чтобы из точки А идти в том направлении, которое требует минимальных затрат на первом шаге (первый ход), не думая о затратах на последующих шагах, и так в каждой точке. Т.е. рассматривать только затраты на данном шаге и выбирать тот переход, для которого на данном шаге затраты минимальны. Легко убедиться в ошибочности этой идеи даже при m = n = 1 Поиск оптимального пути можно рассматривать как многошаговый процесс. На первом шаге находимся в точке А и имеем две возможности: пойти вверх или направо. Сделать выбор нельзя, так как нужно учитывать последствия этого выбора. При любом выборе, попадем мы в точку (0,1) или (1,0), встанет та же задача выбора из двух возможностей и опять выбор сделать нельзя и т.д. Однако существуют точки, находясь в которых мы не имеем выбора. Эти точки С и D находятся в одном шаге от последней точки В и имеют координаты (m, n-1) и (m-1,n) (рис. 13). Рис. 13. Выбор на последних шагах Для каждой из этих точек запомним затраты на оставшийся путь и рассмотрим предпоследний шаг. В двух шагах от финиша мы можем быть в точках Е, F или G. В точках Е и G выбора нет, и мы просто запомним для каждой из них суммарные затраты на весь оставшийся путь. На рис. 13 это 10 для точки Е и 8 для точки G. А что делать, если мы в двух шагах от финиша окажемся в точке F? Ответ кажется простым: надо идти в точку С, а не в точку D, так как, несмотря на то что на предпоследнем шаге затраты больше (2 против 1), с учетом затрат на оставшийся путь (4 против 7) суммарные затраты на путь До точки В окажутся меньше (6 против 8). Конечно, из точки F надо идти в точку С, но при одном непременном Условии: ничто не может помешать нам это сделать, нет никакой связи с тем, как мы попали в данную точку или, как говорят, нет «предыстории». В нашей задаче такой связи нет, но в более сложных задачах она вполне возможна. Например, могло быть задано дополнительное условие: суммарное количество изменений направления (поворотов) не больше заданного числа. Тогда мы, во-первых, должны знать, сколько было сделано поворотов до попадания в точку F и каким образом (по горизонтали или по вертикали), мы попали в эту точку, т.е. должны знать предысторию. Может оказаться, что мы попали в точку F по горизонтали и уже исчерпали заданный «лимит» поворотов, тогда переход из точки F в точку С просто невозможен, так как это уже лишний поворот. Получается, что сделать оптимальный выбор в точке F нам может помешать предыстория. Продолжим поиск оптимального пути в нашей задаче, в которой таких осложнений нет, и предыстория не имеет значения. В точке F мы запомним затраты на весь оставшийся путь при условии, что выбран оптимальный вариант: переход в точку С. Сделав еще шаг назад, т.е. оказавшись за три шага до финиша, мы увидим, что ситуация полностью аналогична предыдущей. Выбора или нет (точки на крайней верхней или крайней правой стороне сетки), или есть две возможности, но для каждой из них уже известны последствия выбора. Так, оказавшись в точке М, мы выберем не точку F, для которой затраты до конца пути равны 6, а казавшуюся бесперспективной точку Е. Для нее эти затраты равны 10, но суммарные затраты на весь оставшийся путь меньше (13 против 14). При этом выборе мы решаем совсем простую задачу: суммируем затраты на каждый из возможных переходов на данном шаге (в точку Е или в точку F) с уже известными затратами на дальнейший путь по оптимальному для выбранной точки варианту. Поступая аналогичным образом, мы рано или поздно в своем обратном движении придем в начальную точку А (рис. 14). Но при этом уже будут известны последствия для каждого из вариантов выбора (пойти по вертикали в точку К или по горизонтали в точку L), так как для каждой из них уже вычислены и записаны затраты на весь оставшийся путь до точки В. Рис. 14. Выбор на первом шаге Теперь ничто не мешает нам сделать выбор, куда идти из точки А. Просуммируем затраты из А в К с тем, что записано для точки К на весь оставшийся путь от К до В. Затем просуммируем затраты из А в L с тем, что записано для L на путь из L в В, выберем наименьшую из сумм, которая и будет равна суммарным затратам по оптимальному пути. В примере на рис. 14 получаем для точки К 99, а для точки L 100, и, следовательно, теперь ясно, что идти надо в точку К. Но нам нужны не только эти минимальные из всех возможных затраты, но и сам оптимальный путь. Пока мы знаем, куда идти из точки А на первом шаге. А дальше? Дальше знаем только затраты на весь оставшийся путь. Чтобы не оказаться в такой ситуации неопределенности, при записи затрат на оставшийся путь в каждой из промежуточных точек (С, D, E, F, G, М, и т.д. рис. 13) нужно записывать и сделанный выбор: куда идти из этих точек. Когда из точки А выберем точку К или L, в любой из них уже будет записано, куда идти (по вертикали или по горизонтали, т.е. 1 или 0) и т. д. Обратным разворотом мы дойдем до точки В и восстановим оптимальный путь. Заметим, что если при сравнении вариантов на любом из этапов попадутся два варианта с равными затратами, то можно выбрать любой из них. Это означает, что оптимальный путь может быть не единственным. В реальных задачах многоэтапные процессы могут иметь не один исход (точку финиша) или начало (точку старта), а несколько. Однако это не мешает применить метод Р. Беллмана. Во-первых, для упрощения алгоритма всегда можно ввести еще один фиктивный этап с нулевыми затратами на нем. Например, ввести единственную фиктивную точку финиша, которая достигается из реальных точек финиша без дополнительных затрат. Во-вторых, можно просто сравнить варианты финиша в каждой из точек, если их несколько. Аналогично можно поступить и при наличии нескольких точек старта, но в этом случае необходимо либо добавить фиктивную точку старта, из которой затраты на первый шаг равны нулю, либо сразу «тащить» много вариантов. Принцип оптимальности Р. Беллмана сформулирован для широкого круга задач управления, распределения ресурсов, проектирования и др. и вообще задач принятия решений в многошаговых (многоэтапных) процессах. Если задано начальное (точка А) и конечное (точка В) состояния некоторой системы и переход из начального в конечное состояние осуществляется в несколько промежуточных этапов, на каждом из которых система может находиться в одном из различных состояний, и каждому переходу на каждом этапе можно сопоставить некоторые затраты, то задача состоит в том, чтобы выбрать такой путь (т.е. все промежуточные состояния), при котором некоторая количественная оценка этого пути достигает минимума. Общее условие применимости принципа оптимальности выражается в требовании отсутствия влияния «предыстории». Именно поэтому формулировка этого принципа, приведенная в разделе 2, начинается со слова «если». Установить возможность применения принципа Р. Беллмана — значит доказать отсутствие влияния «предыстории». Это влияние может возникать при наличии более сложных целевых функций, чем сумма затрат. Может оказаться, что даже если удается разбить задачу на ряд последовательных этапов, значение целевой функции можно вычислить только при полностью известной траектории (полной последовательности переходов системы от начального состояния к конечному). жүктеу/скачать 0,77 Mb. Достарыңызбен бөлісу:
|