Полная версия

Главная arrow Математика, химия, физика arrow Дискретная оптимизация. Модели, методы, алгоритмы решения прикладных задач

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Область применения динамического программирования

Общее условие применимости метода Р.Веллмана выражается в требовании отсутствия влияния предыстории. Именно поэтому формулировка принципа оптимальности, приведенная в нами разделе 3.2, начинается со слова «если» в отличие от целого ряда других источников [6,12 ].

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

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

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

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

Сравнивая варианты (например, варианты достижения узла на двумерной сетке) после первых двух этапов и отдавая предпочтение варианту с меньшим произведением затрат zzi, мы никак не учитываем, что важно не только это произведение, но и конкретно zi, так как от zi зависит следующее слагаемое. Другими словами, важно не только значение целевой функции, но и как оно получено. Может оказаться, что выгоднее оставить вариант с большим значением Z1Z2, но с меньшим значением Z2. Такой пример приведён на рис. 3.8. Если сравнивать варианты АЕС и ANC, то останется вариант АЕС, что даёт решение AECDB со значением целевой функции 11(1 *5+5* 1+1*1). Оптимальным же является вариант ANCDB со значением целевой функции 9 (3*2+2* 1+1*1).

Отметим, что во многих задачах влияние предыстории можно преодолеть за счёт усложнения формализации понятия «состояние». Так, если в задаче поиска оптимального пути на двумерной сетке считать состоянием не узел, а два последних пройденных узла, то есть отрезок их соединяющий, то сравнимыми становятся варианты, у которых общим является не один последний узел, а два, то есть варианты, имеющие общий последний отрезок (переход) рис. 3.9.

Ошибочность сравнения вариантов ЛЕС и ANC

Рис. 3.8. Ошибочность сравнения вариантов ЛЕС и ANC

Сравнение вариантов не «в точку», а «в отрезок»

Рис. 3.9. Сравнение вариантов не «в точку», а «в отрезок»

Варианты, сходящиеся в точке D (AED и AND), теперь сравнивать нельзя, так как они соответствуют разным состояниям. Нужно сравнивать AEDM и ANDM и оставить лучший из них.

Это сравнение корректно и при новой целевой функции (3.3). Но при наличии ограничений на число поворотов это сравнение некорректно, так как число поворотов у сравниваемых вариантов разное.

Лучший из оставшихся вариант нельзя сравнивать с вариантом АЕСМ. К нему нужно добавить общий отрезок, например, MG и сравнивать с AECMG по целевой функции (3.3). Но при наличии ограничений на число поворотов эти варианты не сравнимы, так как AECMG имеет один поворот, а все остальные, содержащие переход MG, - больше. Нужно ввести ещё одну «координату» - число поворотов и усложнить тем самым формализацию понятия «состояние». Чем больше чисел (координат) нужно для задания конкретного состояния, тем больше объём вычислений и требуемой памяти, так как сравниваются варианты достижения одного и того же промежуточного состояния и число таких вариантов резко возрастает с ростом числа координат.

На конкретных примерах мы убедились в том, что применению принципа оптимальности Р.Беллмана может помешать не только наличие целевой функции более сложной, чем сумма по-шаговых затрат, но и наличие ограничений. В этой связи трудно согласиться с утверждением о том, что ограничения «не страшны» для этого метода. Так, в книге Е.С. Вентцель «Исследование операций. Задачи, принципы, методология» (см. [6] с. 107) утверждается: «Метод динамического программирования является очень мощным и плодотворным методом оптимизации управления; ему не страшны ни целочисленность решения, ни нелинейность целевой функции, ни вид ограничений, накладываемых на решение.» Это утверждение безусловно верно, если ограничения накладываются на каждую или некоторые переменные отдельно (в задачах оптимального управления часто бывает именно так). Такие ограничения могут даже упростить поиск решения. Но если ограничения даже очень простого вида (например, линейные) связывают несколько переменных, то каждое новое ограничение увеличивает число координат, задающих состояние системы (их называют ещё параметры состояния). А при числе параметров состояния больше трёх и большом числе возможных вариантов перехода из каждого промежуточного состояния вычислительные трудности при реализации метода динамического программирования могут оказаться не преодолимыми даже для сверхмощных современных компьютеров. Вот почему вид ограничений, накладываемых на искомое решение, крайне важен и приведенное выше утверждение [6, с. 107] в общем случае неверно.

Что касается целевой функции, то и здесь важна её структура. Мы видели, что даже сравнительно простая функция в виде суммы произведений затрат на двух последних шагах (3.3) требует увеличения числа параметров состояния. Существенным является не то, что целевая функция нелинейна, а возможность её вычисления по отдельным шагам. Если этой возможности нет и целевая функция может быть вычислена только после того как сформирована вся траектория, т.е. последовательность состояний, то метод динамического программирования применить не удаётся. Конечно, для линейной функции такая возможность по-шаговых вычислений очевидна. И для суммы нелинейных функций, в которой каждое слагаемое зависит только от одной переменной, дополнительных сложностей не возникает, так как нет связи между переменными. Но если в целевую функцию включить слагаемое, зависящее нелинейным образом от двух переменных (например, произведение первой и последней), то всё осложняется. Такая нелинейность целевой функции весьма существенна для применимости метода динамического программирования. Следовательно, цитированное выше утверждение о том, что «не страшно» для метода динамического программирования требует существенного уточнения и в части влияния нелинейности и в части влияния вида ограничений.

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

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

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

  • 1. Должна быть возможность интерпретации задачи как многошагового процесса принятия решений, в котором решение, принимаемое на каждом шаге, состоит в выборе одного или нескольких чисел (управляющих переменных, определяющих однозначно переход в следующее состояние). В сложных случаях управляющие переменные могут быть векторами или функциями. На каждом шаге для каждого состояния должна быть возможность количественной оценки принятого решения (управления), а не только выяснения состояния, в которое перейдёт система. Речь идёт о возможности вычисления целевой функции по отдельным шагам, но правила вычисления этой функции на отдельных шагах (расчётные формулы) могут и различаться.
  • 2. При рассмотрении задачи, состоящей из нескольких шагов (этапов), должен быть задан некоторый набор параметров, описывающих состояние системы (параметры состояния). Это же множество параметров должно описывать состояние системы на всех шагах независимо от количества шагов.
  • 3. Возможность выбора управления (перехода) на каждом из шагов и состояний не должна зависеть от того, как система попала в это состояние, то есть не должна влиять предыстория. Практически речь идёт о системах, при управлении которыми на каждом этапе в каждом из состояний при принятии решений можно забыть о том, какие решения принимались ранее (на предыдущих этапах), важно только то, к чему они привели, и можно «начать с чистого листа, имея то, что имеем.»
 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>