Semenalidery.com

IT Новости из мира ПК
2 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Модели динамического программирования

Динамическое программирование — это вычислительный метод для решения задач определенной структуры. Возникло и сформировалось в 1950-1953 гг. благодаря работам Р. Беллмана над динамическими задачами управления запасами. В упрощенной формулировке динамическое программирование представляет собой направленный последовательный перебор вариантов, который обязательно приводит к глобальному максимуму.

Основные необходимые свойства задач, к которым возможно применить этот принцип:

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

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

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

Постановку задачи динамического программирования рассмотрим на примере инвестирования, связанного с распределением средств между предприятиями. В результате управления инвестициями система последовательно переводится из начального состояния S В конечное S n . Предположим, что управление можно разбить на n шагов и решение принимается последовательно на каждом шаге, а управление представляет собой совокупность n пошаговых управлений. На каждом шаге необходимо определить два типа переменных — переменную состояния системы S k переменную управления x k . Переменная S k определяет, в каких состояниях может оказаться система на рассматриваемом k-м шаге. В зависимости от состояния S на этом шаге можно применить некоторые управления, которые характеризуются переменной xk которые удовлетворяют определенным ограничениям и называются допустимыми. Допустим. = (x 1 , x 2 , . x k , . x n ) — управление, переводящее систему на состояния S в состояние S n , a S k — есть состояние системы на k-м шаге управления. Тогда последовательность состояний системы можно представить в виде графа, представленного на рис. 2.11.

Применение управляющего воздействия x k на каждом шаге переводит систему в новое состояние S 1 (S, x k ) и приносит некоторый результат W k (S, x k ). Для каждого возможного состояния на каждом шаге среди всех возможных управлений выбирается оптимальное управление x* k , такое, чтобы результат, который достигается за шаги с k-го по последний n-й, оказался бы оптимальным. Числовая характеристика этого результата называется функцией Беллмана F k (S) и зависит от номера шага k и состояния системы S. Задача динамического программирования формулируется следующим образом: требуется определить такое управление , переводящее систему из начального состояния S в конечное состояние S n , при котором целевая функция принимает наибольшее (наименьшее) значение F(S ,) => extr.

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

  1. задача оптимизации формулируется как конечный многошаговый процесс управления;
  2. целевая функция (выигрыш) является аддитивной и равна сумме целевых функций каждого шага:

Принцип оптимальности и математическое описание динамического процесса управления.
В основе метода ДП лежит принцип оптимальности, впервые сформулированный в 1953 г. американским математиком Р.Э.Беллманом: каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая выигрыш на данном шаге. При решении задачи на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. Если считать все шаги независимыми, тогда оптимальным управлением будет то управление, которое обеспечит максимальный выигрыш именно на данном шаге. Однако, например, при покупке новой техники взамен устаревшей на ее приобретение затрачиваются определенные средства, поэтому доход от ее эксплуатации в начале может быть небольшой, а в следующие годы новая техника будет приносить больший доход. И наоборот, если принято решение оставить старую технику для получения дохода в текущем году, то в дальнейшем это приведет к значительным убыткам. Этот пример демонстрирует следующий факт: в многошаговых процессах управление на каждом конкретном шаге надо выбирать с учетом его будущих воздействий на весь процесс. Кроме того, при выборе управления на данном шаге следует учитывать возможные варианты состояния предыдущего шага. Например, при определении количества средств, вкладываемых в предприятие в i-м году, необходимо знать, сколько средств осталось в наличия к атому году и какой доход получен в предыдущем (i — 1)-м году. Таким образом, при выборе шагового управления необходимо учитывать следующие требования:

  1. возможные исходы предыдущего шага S k-1;
  2. влияние управления x k на все оставшиеся до конца процесса шаги (n-k).

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

Условная оптимизация

На первом этапе решения задачи, называемом условной оптимизацией, определяются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем, n-м шаге оптимальное управление — х* n определяется функцией Беллмана: F(S) = max n (S, x n )>, в соответствии с которой максимум выбирается из всех возможных значений x n , причем x n € X.
Дальнейшие вычисления производятся согласно рекуррентному соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге. В общем виде это уравнение имеет вид F n (S) = max n (S, x n ) + F k+1 (S n (S, x k )> x k € X.
Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

Безусловная оптимизация

После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый, осуществляется второй этап решения задачи, называемый безусловной оптимизацией. Пользуясь тем, что на первом шаге (k = 1) состояние системы известно — это ее начальное состояние S , можно найти оптимальный результат за все n шагов и оптимальное управление на первом шаге x 1 , которое этот результат доставляет. После применения этого управления система перейдет в другое состояниеS 1 (S, x* 1 ), зная которое, можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге x* 2 , и так далее до последнего n-го шага. Вычислительную схему динамического программирования можно строить на сетевых моделях, а также по алгоритмам прямой прогонки (от начала) и обратной прогонки (от конца к началу). Рассмотрим примеры решения различных по своей природе задач, содержание которых требует выбора переменных состояния и управления.

Модели динамического программирования

1. Какие основные принципы заложены в методе?

2. Как он применяется при решении задач?

… Математик может считать свою проблему

решенной тогда, только когда поймет суть

оптимального подхода к решению

(Р. Беллман)

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

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

8.1 Суть метода динамического программирования и его особенности

Суть метода динамического программирования (ДП) заключается в следующем.

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

Каждая подзадача решается отдельно один раз. Оптимальные значения решений всех подзадач запоминаются.

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

Таким образом, основные отличия данной техники от техники «разделяй и властвуй «заключаются в следующем:

Таблица 8.1 — Отличительные особенности методов «разделяй и властвуй» и ДП.

Разделяй и властвуй

Не зависимые подзадачи

Решение всех подзадач не запоминается

Решение всех подзадач запоминается

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

Показатель эффективности задачи в целом обозначим через W, а показатели эффективности на отдельных шагах—через φi, i=1..m. Если W обладает свойством аддитивности, т.е.

Переменная xi, от которой зависят выигрыши на i-м шаге и, следовательно, выигрыш в целом, называется шаговым управлением, i=1..m.

Управлением процесса в целом (x) называется последовательность шаговых управлений (вектор управлений) x = (x1, x2,…, xi,…, xm).

Оптимальное управление x* — это значение управления x, при котором значение W(x*) является максимальным (или минимальным, если требуется уменьшить проигрыш).

где X—область допустимых управлений.

Оптимальное управление x* определяется последовательностью оптимальных шаговых управлений x*=(x1*, x2*,…, xi*,…, xm*).

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

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

  1. Разбиение задачи на шаги (этапы). Шаг не должен быть слишком мелким, чтобы не проводить лишних расчетов и не должен быть слишком большим, усложняющим процесс шаговой оптимизации.
  2. Выбор переменных, характеризующих состояние s моделируемого процесса перед каждым шагом, и выявление налагаемых на них ограничений. В качестве таких переменных следует брать факторы, представляющие интерес для исследователя, например годовую прибыль при планировании деятельности предприятия.
  3. Определение множества шаговых управлений xi, i=1..m и налагаемых на них ограничений, т.е. области допустимых управлений X.
  4. Определение выигрыша φ(s, xi), который принесет на i-м шаге управление xi, если система перед этим находилась в состоянии s.
  5. Определение состояния s’, в которое переходит система из состояния s под влиянием управления xi : s’=fi(s, xi), где fi—функция перехода на i-м шаге из состояния s в состояние s’.
  6. Составление уравнения, определяющего условный оптимальный выигрыш на последнем шаге, для состояния s моделируемого процесса
  • (8.3) [TEX]rm Wm(S)=max[/TEX]

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

В уравнении (8.4) в уже известную функцию Wi+1(s), характеризующую условный оптимальный выигрыш с (i+1)-го шага до конца процесса, вместо состояния s подставлено новое состояние s’=fi(s, xi), в которое система переходит на i-м шаге под влиянием управления xi.

После того как выполнены пункты 1-7, и математическая модель составлена, приступают к ее расчету. Укажем основные этапы решения задачи динамического программирования.

  1. Определение множества возможных состояний Sm для последнего шага.
  2. Проведение условной оптимизации для каждого состояния s, принадлежащей Sm на последнем m-м шаге по формуле (8.3) и определение условного оптимального управления x(s), s принадлежит Sm.
  3. Определение множества возможных состояний Si для i-го шага, i=2, 3,…m-1.
  4. Проведение условной оптимизации для i-го шага, i=2, 3,…m-1 для каждого состояния s, принадлежащей Si,, по формуле (8.4) и определение условного оптимального управления xi(s), s принадлежит Si, i=2, 3,…m-1.
  5. Определение начального состояния системы s1, оптимального выигрыша W1(S1) и оптимального управления x1(S1) по формуле (8.4) при i=1. Это есть оптимальный выигрыш для всей задачи W*=W1(x1*).
  6. Проведение безусловной оптимизации управления. Для проведения безусловной оптимизации необходимо найденное на первом шаге оптимальное управление x1*=x1(s1) подставить в формулу (8.2) и определить следующее состояние системы s2=f2(s1, x1). Для измененного состояния найти оптимальное управление x2*=x2(s2), подставить в формулу и т.д. Для i-го состояния si найти si+1=fi+1(si,xi*) и x*i+1(si+1) и т.д.
  7. Динамическое программирование дает достаточно эффективный метод последовательного принятия решений об оптимизации работы системы с помощью решения серии связанных между собой одношаговых задач Это позволяет говорить о многошаговом процессе принятия решения . Таким способом могут быть оптимизированы динамические системы , для которых фактор времени играет существенную роль . Однако специфичный способ решения задач динамического программирования , который оперирует рекуррентными соотношениями , позволяет оптимизировать не только реальные динамические системы .

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

Перечислим основные требования к задачам, выполнение которых позволяет применить данный подход:

а) объектом исследования должна cлужить управляемая систем а(объект) с заданными допустимыми состояниями и допустимыми управлениями;

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

в) задача не должна зависеть от количества шагов и быть определенной на каждом из них ;

г) состояние системы на каждом шаге должно описываться одинаковым ( по составу ) набором параметров;

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

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

8.2 Применение метода в конкретных задачах

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

Задача 8.1 Задача о возврате сдачи. Необходимо вернуть сдачу покупателю 10 грн. Сколько способов существует для возврата сдачи, если у продавца имеется неограниченные количества разменных монет достоинством 1, 2 и 5 грн. ? При этом способы различаются и порядком следования монет, т.е. сдача набором монет <1, 2, 2, 5>и сдача — <5, 2, 2, 1>– это разные способы.

Решение. Введем обозначения F(n) – количество способов, которыми можно вернуть сдачу достоинством n. Тогда в задаче требуется найти F(10).

Перейдем к задачам меньшей размерности. Рассмотрим случаи, когда n=1, n=2, n=3, n=4 и даже n=0. Эти задачи меньшей размерности решим методом перебора, результат приведем в таблице 8.2.

Таблица 8.2 Решение подзадач к задаче 8.1 для n

Модели динамического программирования

Их применение связано в первую очередь с анализом так называемых многошаговых процессов принятия решений. Процесс является одношаговым, если, например, разработана схема оптимального пути из пункта А в пункт В. Если же вначале известно, как проехать из А в первый промежуточный пункт, а там станет известно, как добраться до 2-го промежуточного пункта и т.д., то весь путь будет известен только по достижении пункта В и процесс принятия решений по поводу оптимального пути из А в В станет уже многошаговым. Таким образом, динамическое программирование — это метод оптимизации, приспособленный к операциям в которых процесс принятия решений может быть разбит на отдельные этапы (шаги). Как раздел математического программирования динамическое программирование начало развиваться в 50-х годах XX века благодаря работам Р.Белмана и его сотрудников. Впервые этим методом решались задачи оптимального управления запасами, затем класс задач значительно расширился (многошаговые детерминированные модели задач оптимального распределения ресурсов; расчет развития на перспективу производственной базы стройиндустрии; установление оптимальных режимов замены изношенного оборудования, производства и хранения продукции во времени, при меняющемся спросе на нее, рациональная загрузка транспортных средств, оптимальное распределение капиталовложений и др.).

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

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

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

Сущность метода динамического программирования описывается так называемым динамическим рекурентным соотношением

(6.20)

где fn(s) — стоимость, отвечающая стратегии минимальных затрат для пути из состояния s до конечного состояния системы, если остаток пути состоит из n шагов;

csj — стоимость перевода исследуемой системы из состояния s в состояние j.

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

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

В рассматриваемом примере ответ имеет вид: 1 → 4 → 6 → 7, при этом время дооборудования этого маршрута составит 12 дней.

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

Применение моделей динамического программирования для решения управленческих задач

Автор работы: Пользователь скрыл имя, 11 Декабря 2012 в 19:17, курсовая работа

Описание

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

Работа состоит из 1 файл

Federalnoe_gosudarstvennoe_byudzhetnoe_obrazova.doc

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

РОССИЙСКАЯ АКАДЕМИЯ НАРОДНОГО ХОЗЯЙСТВА И ГОСУДАРСТВЕННОЙ СЛУЖБЫ

ПРИ ПРЕЗИДЕНТЕ РОССИЙСКОЙ ФЕДЕРАЦИИ

НИЖЕГОРОДСКИЙ ИНСТИТУТ УПРАВЛЕНИЯ

Факультет заочного обучения

Кафедра математики и системного анализа

ПО ДИСЦИПЛИНЕ «Разработка управленческого решения»

«Применение моделей динамического программирования для решения управленческих задач»

Выполнила: студентка 4 курса, группы ГК-641

Макаров Сергей Александрович

Введение.

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

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

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

— разъяснить принцип Беллмана, лежащий в основе метода;

— построить алгоритм решения задач методом динамического программирования;

— выявить преимущества и недостатки данного метода.

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

Динамическое программирование.

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

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

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

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

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

Выделим особенности модели ДП:

  1. Задача оптимизации интерпретируется как n-шаговый процесс управления.
  2. Критерий должен обладать свойством аддитивности, т.е. его величина есть сумма частных величин, достигаемых на отдельных этапах. Целевая функция равна сумме целевых функций каждого шага.
  3. Рассматриваемый процесс должен быть марковским, т.е. в нем предыстория не должна иметь значения для определения будущих действий. Выбор управления на k-м шаге зависит только от состояния системы к этому шагу, не влияет на предшествующие шаги (нет обратной связи).
  4. Состояние Sk после k-го шага управления зависит только от предшествующего состояния Sk-1 и управления Xk (отсутствие последействия).
  5. На каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние Sk — от конечного числа параметров.

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

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

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

На первом этапе решения задачи, называемом условной оптимизацией, определяются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем, n-м шаге, оптимальное управление х * n определяется функцией Беллмана: V(S)=maxn(S,xn)>, в соответствии с которой максимум выбирается из всех возможных значений хn, причем хn∈Х.

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

Vn * — условный максимум целевой функции показателя эффективности n-го шага при условии, что к началу последнего шага система S была в произвольном состоянии Sn-1, а на последнем шаге управление было оптимальным.

Sn-1 — состояние системы к началу n-го шага,

Хn — управление на n-м шаге,

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

После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый, осуществляется второй этап решения задачи, называемый безусловной оптимизацией. Пользуясь тем, что на первом шаге (k = 1) состояние системы известно – это ее начальное состояние S, можно найти оптимальный результат за все n шагов.

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

Алгоритм решения задач методом динамического программировани я.

Рассмотрим в общем виде алгоритм решения задач методом динамического программирования.

Будем считать, что состояние Sk рассматриваемой системы S на k-м шаге (k = 1, 2, . n) определяется совокупностью чисел Sk= (S1, S2 … Sm), которые получены в результате реализации управления Xk, обеспечивающего переход системы S из состояния Sk-1 в состояние Sk.

Пусть также выполняются два условия:

1. Условие отсутствия последействия. Состояние Sk, в которое перешла система S, зависит от исходного состояния Sk-1 и выбранного управления Xk и не зависит от того, каким образом система S перешла в состояние Sk-1.

2. Условие аддитивности. Если в результате реализации k-го шага обеспечен определенный выигрыш, также зависящий от исходного состояния системы и выбранного управления, то общий выигрыш fk(Sk-1,xk)за k шагов составит

Задача состоит в нахождении оптимальной стратегии управления, т. е. такой совокупности управлений x=(x1, x2…xn), в результате реализации которых система S за k шагов переходит из начального состояния в конечное, и при этом функция дохода F(x) принимает наибольшее значение.

Из принципа оптимальности следует, что оптимальную стратегию управления можно получить, если сначала найти оптимальную стратегию управления на n-м шаге, затем на двух последних шагах, затем на трех последних шагах и т. д., вплоть до первого шага. Таким образом, решение рассматриваемой задачи динамического программирования целесообразно начинать с определения оптимального решения на последнем, n-м шаге. Для того чтобы найти это решение, очевидно, нужно сделать различные предположения о том, как мог окончиться предпоследний шаг, и с учетом этого выбрать управление xn 0 , обеспечивающее максимальное значение функции дохода fn(Sn-1,xn). Такое управление, выбранное при определенных предположениях о том, как окончился предыдущий шаг, называется условно оптимальным. Следовательно, принцип оптимальности требует находить на каждом шаге условно оптимальное управление для любого из возможных исходов предшествующего шага.

Чтобы решить задачу необходимо воспользоваться основным функциональным уравнением Беллмана.

Полагая k = n — 1 в уравнении Беллмана, получаем следующее функциональное уравнение:

Используя теперь это уравнение и рассматривая всевозможные допустимые состояния системы S на (n — 1)-м шаге находим условные оптимальные решения и соответствующие значения функции.

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

Перейдем теперь к рассмотрению функционального уравнения при

Решая это функциональное уравнение при различных состояниях на (n — 2)-м шаге, получим условно оптимальные управления x 0 n-2(Si (n-2) ), i=1,2… . Каждое из этих управлений совместно с уже выбранным управлением на последнем шаге обеспечивает максимальное значение дохода на двух последних шагах.

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

Динамическое программирование для начинающих

    Статьи, 7 июня 2016 в 15:04

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

О чём вообще речь? Что такое динамическое программирование?

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

Хорошо, как это использовать?

Решение задачи динамическим программированием должно содержать следующее:

  • Зависимость элементов динамики друг от друга. Такая зависимость может быть прямо дана в условии (так часто бывает, если это задача на числовые последовательности). В противном случае вы можете попытаться узнать какой-то известный числовой ряд (вроде тех же чисел Фибоначчи), вычислив первые несколько значений вручную. Если вам совсем не повезло – придётся думать
  • Значение начальных состояний. В результате долгого разбиения на подзадачи вам необходимо свести функцию либо к уже известным значениям (как в случае с Фибоначчи — заранее определены первые два члена), либо к задаче, решаемой элементарно.

И что, мне для решения рекурсивный метод писать надо? Я слышал, они медленные.

Конечно, не надо, есть и другие подходы к реализации динамики. Разберём их на примере следующей задачи:

Идея решения

Здесь нам даны и начальные состояния (a = a1 = 1), и зависимости. Единственная сложность, которая может возникнуть — понимание того, что 2n — условие чётности числа, а 2n+1 — нечётности. Иными словами, нам нужно проверять, чётно ли число, и считать его в зависимости от этого по разным формулам.

Рекурсивное решение

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

И она отлично работает, но есть нюансы. Если мы захотим вычислить f(12) , то метод будет вычислять сумму f(6)+f(5) . В то же время, f(6)=f(3)+f(2) и f(5)=f(2)-f(1) , т.е. значение f(2) мы будем вычислять дважды. Спасение от этого есть — мемоизация (кеширование значений).

Рекурсивное решение с кэшированием значений

Идея мемоизации очень проста — единожды вычисляя значение, мы заносим его в какую-то структуру данных. Перед каждым вычислением мы проверяем, есть ли вычисляемое значение в этой структуре, и если есть, используем его. В качестве структуры данных можно использовать массив, заполненный флаговыми значениями. Если значение элемента по индексу N равно значению флага, значит, мы его ещё не вычисляли. Это создаёт определённые трудности, т.к. значение флага не должно принадлежать множеству значений функции, которое не всегда очевидно. Лично я предпочитаю использовать хэш-таблицу — все действия в ней выполняются за O(1), что очень удобно. Однако, при большом количестве значений два числа могут иметь одинаковый хэш, что, естественно, порождает проблемы. В таком случае стоит использовать, например, красно-чёрное дерево.

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

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

Последовательное вычисление

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

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

LATOKEN, Москва, от 200 000 до 360 000 ₽

Суть метода в следующем: мы создаём массив на N элементов и последовательно заполняем его значениями. Вы, наверное, уже догадались, что таким образом мы можем вычислять в том числе те значения, которые для ответа не нужны. В значительной части задач на динамику этот факт можно опустить, так как для ответа часто бывают нужны как раз все значения. Например, при поиске наименьшего пути мы не можем не вычислять путь до какой-то точки, нам нужно пересмотреть все варианты. Но в нашей задаче нам нужно вычислять приблизительно log2(N) значений (на практике больше), для 922337203685477580-го элемента (MaxLong/10) нам потребуется 172 вычисления.

Ещё одним минусом такого подхода является сравнительно большой расход памяти.

Создание стека индексов

Сейчас нам предстоит, по сути, написать свою собственную рекурсию. Идея состоит в следующем — сначала мы проходим «вниз» от N до начальных состояний, запоминая аргументы, функцию от которых нам нужно будет вычислять. Затем возвращаемся «вверх», последовательно вычисляя значения от этих аргументов, в том порядке, который мы записали.

Зависимости вычисляются следующим образом:

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

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

Все необходимые значения вычислены, осталось только написать

Конечно, такое решение гораздо более трудоёмкое, однако это того стоит.

Хорошо, математика — это красиво. А что с задачами, в которых не всё дано?

Для больше ясности разберём следующую задачу на одномерную динамику:

На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных «маршрутов» мячика с вершины на землю.

Идея решения

На первую ступеньку можно попасть только одним образом — сделав прыжок с длиной равной единице. На вторую ступеньку можно попасть сделав прыжок длиной 2, или с первой ступеньки — всего 2 варианта. На третью ступеньку можно попасть сделав прыжок длиной три, с первой или со втрой ступенек. Т.е. всего 4 варианта (0->3; 0->1->3; 0->2->3; 0->1->2->3). Теперь рассмотрим четвёртую ступеньку. На неё можно попасть с первой ступеньки — по одному маршруту на каждый маршрут до неё, со второй или с третьей — аналогично. Иными словами, количество путей до 4-й ступеньки есть сумма маршрутов до 1-й, 2-й и 3-й ступенек. Математически выражаясь, F(N) = F(N-1)+F(N-2)+F(N-3). Первые три ступеньки будем считать начальными состояниями.

Реализация через рекурсию

Здесь ничего хитрого нет.

Реализация через массив значений

Исходя из того, что, по большому счёту, простое решение на массиве из N элементов очевидно, я продемонстрирую тут решение на массиве всего из трёх.

Так как каждое следующее значение зависит только от трёх предыдущих, ни одно значение под индексом меньше i-3 нам бы не пригодилось. В приведённом выше коде мы записываем новое значение на место самого старого, не нужного больше. Цикличность остатка от деления на 3 помогает нам избежать кучи условных операторов. Просто, компактно, элегантно.

Там вверху ещё было написано про какую-то двумерную динамику.

С двумерной динамикой не связано никаких особенностей, однако я, на всякий случай, рассмотрю здесь одну задачу и на неё.

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

Идея решения

Логика решения полностью идентична таковой в задаче про мячик и лестницу — только теперь в клетку (x,y) можно попасть из клеток (x-1,y) или (x, y-1). Итого F(x,y) = F(x-1, y)+F(x,y-1). Дополнительно можно понять, что все клетки вида (1,y) и (x,1) имеют только один маршрут — по прямой вниз или по прямой вправо.

Реализация через рекурсию

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

Реализация через массив значений

Классическое решение динамикой, ничего необычного — проверяем, является ли клетка краем, и задаём её значение на основе соседних клеток.

Отлично, я всё понял. На чём мне проверить свои навыки?

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

Взрывоопасность

При переработке радиоактивных материалов образуются отходы двух видов — особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров N определить количество возможных типов безопасных стопок.

Решение

Ответом является (N+1)-е число Фибоначчи. Догадаться можно было, просто вычислив 2-3 первых значения. Строго доказать можно было, построив дерево возможных построений.

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

Реализация

Подъём по лестнице

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

Решение

Очевидно, что сумма, которую мальчик отдаст на N-ой ступеньке, есть сумма, которую он отдал до этого плюс стоимость самой ступеньки. «Сумма, которую он отдал до этого» зависит от того, с какой ступеньки мальчик шагает на N-ую — с (N-1)-й или с (N-2)-й. Выбирать нужно наименьшую.

Реализация

Калькулятор

Имеется калькулятор, который выполняет три операции:

  • Прибавить к числу X единицу;
  • Умножить число X на 2;
  • Умножить число X на 3.

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

Решение

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

Правильное решение заключается в нахождении для каждого числа от 2 до N минимального количества действий на основе предыдущих элементов, иначе говоря: F(N) = min(F(N-1), F(N/2), F(N/3)) + 1. Следует помнить, что все индексы должны быть целыми.

Для воссоздания списка действий необходимо идти в обратном направлении и искать такой индекс i, что F(i)=F(N), где N — номер рассматриваемого элемента. Если i=N-1, записываем в начало строки 1, если i=N/2 — двойку, иначе — тройку.

Реализация

Самый дешёвый путь

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

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

Решение

В любую клетку таблицы мы можем попасть либо из клетки, находящейся непосредственно над ней, либо из клетки, находящейся непосредственно слева. Таким образом, F(x,y) = min(F(x-1,y), F(x,y-1)). Чтобы не обрабатывать граничные случаи, можно добавить первую строку и столбец, заполненные некоторой константой — каким-то числом, заведомо большим содержимого любой из клеток.

Читать еще:  Восстановление айфон 5s ошибка 4013
Ссылка на основную публикацию
Adblock
detector