Задачи динамического программирования.


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

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

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

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

Предположим, что интересующий нас процесс можно разбить на N шагов, а действия, совершаемые на i-ом шаге, характеризуются совокупностью показателей . Состояние процесса к началу этого шага имеет характеристику в виде набора параметров . Обычно предпринимаемые действия не являются полностью произвольными, а зависят от состояния , которое возникло перед i-ым шагом, т.е. . Очевидно, результирующее значение критерия Z, получаемое в конце процесса, будет определяться теми , которые были приняты, т.е. . Возникает вопрос: Как выбрать , чтобы величина Z приняла экстремальное значение? Ответ можно получить, рассматривая Z как функцию переменных и находя экстремум z одним из известных способов, однако этот путь не всегда прост (особенно при большом числе переменных).
Появляется идея провести оптимизацию поэтапно, анализируя последовательно каждый шаг процесса в поисках наилучших вариантов его продолжения.

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

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

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

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

Замечание.

В общем случае необходимо учитывать некоторые условия, накладываемые на начальное и конечное состояния системы:

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


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

Пример 1.

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

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

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

Пример 2.

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

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

Hosted by uCoz