Принцип оптимальности беллмана реферат

Обновлено: 02.07.2024

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

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

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

Даже для n = 50 число вариантов становится очень большим!

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

В частном случае методы динамического программирования позволяют решать подобные задачи при числе агрегатов порядка 20-30.

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

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

Задан график оплаченной электроэнергии, избыточно произведенная электроэнергия не оплачивается.

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

Интересны задачи о распределении инвестиций и ресурсов.

Задача о распределении инвестиций: имеется несколько предприятий, между которыми требуется распределить данную сумму инвестиций. Известна эффективность вложения данной суммы средств в каждое предприятие.

Задача о распределении ресурса: имеется N предприятий, каждое из которых приносит доход, зависящий от доли выделенного ресурса. Требуется наилучшим способом распределить между ними ограниченный ресурс a на доли x1, . , xN (x1 ≥ 0, . , xN ≥ 0, x1 +. + xN ≤ a).

Задача о наилучшей загрузке транспорта: транспорт, имеющее грузоподъемность a , загружается грузами N типов. Каждый тип груза имеет стоимость yi и вес zi .

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

Задача о замене автомобиля: автотранспортное предприятие планирует приобрести автомобиль и эксплуатировать его в течение N лет.

Можно либо купить новый автомобиль возраста x0 = 0 лет и стоимости p, либо бывший в эксплуатации возраста x0 > 0 лет по стоимости, зависящей от времени эксплуатации.

Показатели эксплуатации автомобиля включают: f (t) – стоимость произведенных за год изделий на оборудовании возраста t лет; r(t) – затраты на эксплуатацию в течение года автомобиля возраста t.

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

Все эти и многие другие задачи могут быть решены с помощью принципа оптимальности Беллмана.

Опишем формально принцип Беллмана и объясним его смысл.

Ключевым является понятие управляемого объекта, к которому применяется принцип Беллмана.

Пусть имеется изменяющийся во времени объект, на который осуществляется внешнее воздействие u(t) или управление, а x(t) – описание этого объекта в момент времени t.

Если при известном управлении до момента t1, зная описание x(t) в момент времени t , можно однозначно определить его значение x(t) для любого t > t1 , то такое описание называют полным.

Полное описание называют состоянием, множество возможных состояний – пространством состояний.

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

Будем рассматривать только дискретные моменты времени и в эти моменты управлять системой.

Каждому переходу из состояния xk в следующее состояние ставится в соответствие функция затрат, зависящая от состояния xk , момента времени и применяемого управления.

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

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

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

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

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

Общий принцип формулируется так: вне зависимости от того, каким образом управляемый процесс на шаге k попал в состояние xk , далее надо применять управление, оптимальное для этого состояния в завершающем (N − k)-шаговом процессе с учетом оптимального продолжения.

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

Пусть Yk – множество состояний, из которых (при использовании допустимых управлений) можно ровно за k шагов попасть в одно из состояний финального множества X N.

Можно считать, что Y0 = X N.

Возьмем произвольное xN −k ∈Yk и обозначим через Sk (xN −k ) функцию, описывающую зависимость оптимальных затрат от состояния xN −k за k последних шагов, переводящих систему из xN −k в X N.

Такие функции называют функциями Беллмана.

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

Второе ограничение необходимо для того, чтобы гарантировать достижение заданного финального множества X N.

Значение uN , при котором достигается минимум в этом соотношении, обозначим через u*N( xN-1).

Несложно понять (сделайте это!), что функция оптимальных затрат Sk +1(xN −k −1) каждой следующей задачи рекуррентно выражается через предыдущую Sk (xN −k )

u*N −k (xN −k – 1) – управление, при котором достигается минимум затрат в (2).

Выражение u*k (xk-1) − определяет для каждого момента времени оптимальные правила управления в виде функций от текущего состояния динамического процесса, задают закон оптимального управления в форме оптимального регулятора по состоянию.

Оптимальное начальное состояние x*0 можно получить из решения следующей задачи:

Систему (1)-(3) называют рекуррентными уравнениями Беллмана.

Значения оптимального управления в явном виде можно последовательно определить следующим образом:

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

Рубрика	Программирование, компьютеры и кибернетика
Вид	реферат
Язык	русский
Дата добавления	13.05.2015
Размер файла	335,3 K

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

Системы поддержки принятия решений

Тема :Динамическое программирование. Уравнение Беллмана

Содержание

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

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

3. Уравнение Беллмана

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

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

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

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

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

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

Математически это можно записать следующим образом:

где Fk(uk) - значение искомой целевой функции на k-м этапе; Fk+1(uk+1) - значение целевой функции на k+1 этапе; Z(xk ,uk ) - оценочная функция данного k-го этапа; x, u - выбранные параметры функции.

Выражение (29) представляет собой математическую запись принципа оптимальности. Его называют основным функциональным уравнением динамического программирования или функциональным уравнением Беллмана.

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

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

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

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

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

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

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

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

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

Во-первых, это - модели календарно-сетевого планирования и управления (КСПУ), с появления которых и зародилось управление проектами.

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

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

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

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

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

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

Требуется выбрать подмножество работ M так, чтобы их суммарная полезность

была максимальной при ограничении на общее время выполнения T:

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

Способ построения сети рассмотрим на примере из пяти работ, данные о полезности и времени которых приведены в таблице 1.

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

Содержание работы

Введение
1. Задача динамического программирования
2.Общая структура динамического программирования
3. Принцип оптимальности. Функциональные уравнения Беллмана
4.Применение динамического программирования
Заключение
Список использованной литературы

Содержимое работы - 1 файл

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

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

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

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

3. Принцип оптимальности. Функциональные уравнения Беллмана

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

Список использованной литературы

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

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

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

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

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

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

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

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

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

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

Произвести условную оптимизацию последнего (m-го) шага, задаваясь гаммой состояний S, из которых можно за один шаг дойти до конечного состояния, вычисляя для каждого из них условный оптимальный выигрыш по формуле
Произвести условную оптимизацию (m-1)-го, (m-2)-го и т.д. шагов по формуле (1.2), полагая в ней i=(m-1),(m-2),…, и для каждого из шагов указать условное оптимальное управление x_i(S), при котором максимум достигается.

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

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

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

ПРИНЦИП ОПТИМАЛЬНОСТИ. ФУНКЦИОНАЛЬНЫЕ УРАВНЕНИЯ БЕЛЛМАНА

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

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

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

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

Понятие динамического программирования………………………..……. ……3
Принцип оптимальности Беллмана………………………………………….……5
Практическое применение динамического программирования……………..…6
Заключение…………………………………………………………………….…..11
Список литературы………………………………………………………………..12

Файлы: 1 файл

методы и модели в экономике.doc

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

ЮЖНО-УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ЭКОНОМИКИ И ПРЕДПРИНИМАТЕЛЬСТВА

Работу выполнил: студент гр. ЭиП-213

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача о выборе наиболее экономного маршрута доставки груза.

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

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

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

х_n(s) – решение, позволяющее достичь f_n(s).

Т.е. х_n(s) соответствует пути минимальной длины от состояния s до конечного состояния, которое достигается за n шагов.