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

Ермакова Елизавета Вячеславовна

__________________

(подпись)

Научный руководитель

Д.э.н., профессор Павленков.М.Н.

__________________

(подпись)

Дзержинск

2013г.

Введение :

1.Введение

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

3. Основные идеи вычислительного метода динами­ческого программирования

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

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

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

7. Заключение

8. Список использованных источников

Введение

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

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

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

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

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

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

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

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

3. Основные идеи вычислительного метода динами­ческого программирования

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

* Динамическое программирование как научное направление возник­ло и сформировалось в 1951-1953 гг. благодаря работам Р. Беллмана и его сотрудников.

Обычно методами динамического программирования опти­мизируют работу некоторых управляемых систем, эффект ко­торой оцениваетсяаддитивной, или мультипликативной, целевой функцией. Аддитивной называется такая функция не­скольких переменных f(х₁, x₂, ...,х_n), значение которой вычис­ляется как сумма некоторых функций f_j, зависящих только от одной переменной х_j:

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

Поскольку логарифм функции типа (5.2) является аддитив­ной функцией, достаточно ограничиться рассмотрением функций вида (5.1).

Изложим сущность вычислительного метода динамическо­го программирования на примере задачи оптимизации

при ограничениях

Отметим, что в отличие от задач, рассмотренных в преды­дущих главах, о линейности и дифференцируемости функций f_j(x_j) не делается никаких предположений, поэтому примене­ние классических методов оптимизации (например, метода Лагранжа) для решения задачи (5.3)-(5.4) либо проблематично, либо просто невозможно.

Содержательно задача (5.3)-(5.4) может быть интерпрети­рована как проблема оптимального вложения некоторых ресур­сов j, приводимых к единой размерности (например, денег) с помощью коэффициентов a_j, в различные активы (инвестици­онные проекты, предприятия и т. п.), характеризующиеся фун­кциями прибыли f_j, т. е. такого распределения ограниченного объема ресурса (b), которое максимизирует суммарную прибыль. Представим ситуацию, когда она решается последова­тельно для каждого актива. Если на первом шаге принято реше­ние о вложении вn-й актив x_n единиц, то на остальных шагах мы сможем распределить b-a_nx_n единиц ресурса. Абстрагируясь от соображений, на основе которых принималось решение на первом шаге (допустим, мы по каким-либо причинам не могли на него повлиять), будет вполне естественным поступить так, чтобы на оставшихся шагах распределение текущего объе­ма ресурса произошло оптимально, что равнозначно реше­нию задачи

при ограничениях,

Очевидно, что максимальное значение (5.5) зависит от размера распределяемого остатка, и если оставшееся количество ресур­са обозначить через ξ, то величину (5.5) можно выразить как функцию от ξ:

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

Если бы имелась возможность влиять на x_n , то мы для получе­ния максимальной прибыли должны были бы максимизировать Ω_n по переменной x_n , т. е. найти Λ_n(b) и фактически решить задачу:

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

т. е. значению целевой функции при одномоментном распреде­лении ресурса.

Если в выражении (5.9) заменить значения b на ξ, и п на k, то его можно рассматривать как рекуррентную формулу, позво­ляющую последовательно вычислять оптимальные значения це­левой функции при распределении объема ресурса ξ за k шагов:

Значение переменной x_k , при котором достигается рассмат­риваемый максимум, обозначим _k (ξ).

При k = 1 формула (5.11) принимает вид

т. е. допускает непосредственное вычисление функций Λ₁(ξ) и ₁(ξ).

Воспользовавшись (5.12) как базой рекурсии, можно с помо­щью (5.11) последовательно вычислить Λ_k(ξ) и _k(ξ), k∊2:n. Положив на последнем шаге ξ = b, в силу (5.9), найдем глобаль­ный максимум функции (5.3), равный Λ_n(b), и компоненту опти­мального плана х_n* = _n(b). Полученная компонента позволяет вычислить нераспределенный остаток на следующем шаге при оптимальном планировании: ξ= b – а_nх*_n , и, в свою очередь, най­ти х*_n-1= _n-1(ξ_n-1). В результате подобных вычислений последо­вательно будут найдены все компоненты оптимального плана.

Таким образом, динамическое программирование представ­ляет собой целенаправленный перебор вариантов, который при­водит к нахождению глобального максимума. Уравнение (5.11), выражающее оптимальное решение на k-м шаге через решения, принятые на предыдущих шагах, называется основным рекур­рентным соотношением динамического программирова­ния. В то же время следует заметить, что описанная схема решения при столь общей постановке задачи имеет чисто тео­ретическое значение, так как замыкает вычислительный про­цесс на построение функций Λ_k(ξ) (k∊1:n), т. е. сводит исход­ную задачу (5.3)—(5.4) к другой весьма сложной проблеме. Однако при определенных условиях применение рекуррентных соотношений может оказаться весьма плодотворным. В первую очередь это относится к задачам, которые допускают таблич­ное задание функций Λ_k(ξ).

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

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

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

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

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

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

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

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

Рассмотрим вопросы применения модели динамического про­граммирования в обобщенном виде. Пусть стоит задача управ­ления некоторым абстрактным объектом, который может пре­бывать в различных состояниях. Текущее состояние объекта отождествляется с некоторым набором параметров, обознача­емым в дальнейшем ξ и именуемый вектором состояния. Пред­полагается, что задано множество Ξ всех возможных состоя­ний. Для объекта определено также множество допустимых управлений (управляющих воздействий) X, которое, не умаляя общности, можно считать числовым множеством. Управляю­щие воздействия могут осуществляться в дискретные моменты времени k(k∊1:n), причем управленческое решение заключа­ется в выборе одного из управлений x_k∊Х. Планом задачи или стратегией управления называется вектор х = (х₁, х₂, .., x_n-1), компонентами которого служат управления, выбранные на каждом шаге процесса. Ввиду предполагаемого отсутствия последействия между каждыми двумя последователь­ными состояниями объекта ξ_k и ξ_k+1 существует известная функциональная зависимость, включающая также выбранное управление: ξ_k+1 = φ_k(x_k , ξ_k), k∊1:п-1. Тем самым задание на­чального состояния объекта ξ₁∊Ξ и выбор плана ходнозначно определяют траекторию поведения объекта, как это показа­но на рис. 5.1.

Эффективность управления на каждом шаге k зависит от текущего состояния ξ_k , выбранного управления x_k и количе­ственно оценивается с помощью функций f_k(х_k, ξ_k), являющих­ся слагаемыми аддитивной целевой функции, характеризую­щей общую эффективность управления объектом. (Отметим, что в определение функции f_k(х_k, ξ_k) включается область до­пустимых значений х_k , и эта область, как правило, зависит от текущего состояния ξ_k .) Оптимальное управление, при задан­ном начальном состоянии ξ₁ , сводится к выбору такого опти­мального плана х*, при котором достигается максимум суммы значений f_k на соответствующей траектории.

Основной принцип динамического программирования заклю­чается в том, что на каждом шаге следует стремиться не к изолированной оптимизации функции f_k(х_k, ξ_k), а выбирать

оптимальное управление х_k* в предположении об оптимально­сти всех последующих шагов. Формально указанный принцип реализуется путем отыскания на каждом шаге k условных оптимальных управлений _k(ξ), ξ∊Ξ, обеспечивающих наи­большую суммарную эффективность начиная с этого шага, в предположении, что текущим является состояние ξ.

Обозначим Λ_k(ξ) максимальное значение суммы функций f_k на протяжении шагов от k до п (получаемое при оптимальном управлении на данном отрезке процесса), при условии, что объект в начале шага k находится в состоянии ξ . Тогда функции Λ_k(ξ) должны удовлетворять рекуррентному соотношению:

где ξ_k+1 = φ_k(x_k, ξ)

Соотношение (5.14) называют основным рекуррентным со­отношением динамического программирования. Оно реализу­ет базовый принцип динамического программирования, извест­ный также как принцип оптимальности Беллмана:

F Оптимальная стратегия управления должна удовлетворять следующему условию: каково бы ни было

начальное состо­яние ξ_k на k-м шаге и выбранное на этом шаге управле­ние х_k,, последующие управления (управленческие реше­ния) должны быть оптимальными по отношению к состоянию ξ_k+1 = φ_k(x_k, ξ_k), получающемуся в результа­те решения, принятого на шаге k.

Основное соотношение (5.14) позволяет найти функции Λ_k(ξ) только в сочетании с начальным условием, каковым в нашем случае является равенство

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

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

В то же время, говоря о динамическом программировании как о методе решения оптимизационных задач, необходимо отметить и его слабые стороны. Так, в предложенной схеме решения зада­чи (5.3)-(5.4) существенным образом используется тот факт, что система ограничений содержит только одно неравенство, и, как следствие, ее состояние задается одним числом — нераспре­деленным ресурсом ξ . При наличии нескольких ограничений со­стояние управляемого объекта на каждом шаге характеризуется уже набором параметров ξ₁, ξ₂, ..., ξ_m , и табулировать значения функций Λ_k (ξ₁, ξ₂, ..., ξ_m) необходимо для многократно больше­го количества точек. Последнее обстоятельство делает приме­нение метода динамического программирования явно нерацио­нальным или даже просто невозможным. Данную проблему его основоположник Р. Беллман эффектно назвал «проклятием многомерности». В настоящее время разработаны определенные пути преодоления указанных трудностей. Подробную информа­цию о них можно найти в специальной литературе [4, 5].

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

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

Одним из важнейших классов задач, для которых примене­ние динамического программирования оказывается плодотвор­ным, являются задачи последовательного принятия решений. Их особенностью является то, что искомые переменные х₁, x₂, .., х_k ,... должны определяться в строгой временной по­следовательности и не должны меняться местами. В качестве примера опишем так называемую задачу о найме работников (задачу об использовании рабочей силы).

В данной задаче рассматривается некоторый экономиче­ский объект (фирма, магазин, завод и т. п.), функционирую­щий в течение конечного числа периодов, обозначаемых но­мерами k (k ∊ l:n). Каждый период k характеризуется нормативной потребностью в определенном количестве одно­типных работников m_k. Тот же объем работ может быть вы­полнен другим количеством сотрудников ξ_k, что, однако, влечет дополнительные затраты либо за счет нерационально­го использования рабочей силы, либо ввиду повышения опла­ты за интенсивный труд. Размеры этих дополнительных издер­жек описываются функциями g_k (ξ_k - m_k), где (ξ_k - m_k) — отклонение фактической численности работающих ξ_k , от пла­ново необходимой m_k , причем g_k (0)=0. Управленческое ре­шение на шаге k заключается в выборе величины изменения числа сотрудников х_k∊Z, что однозначно определяет количе­ство работающих в течение следующего периода: ξ_k+1 = ξ_k+х_k. Затраты по изменению количества работников (найму и уволь­нению) при переходе от периода k к периоду (k+1) задаются функцией u_k (х_k) , где также u_k (0)=0. Тогда суммарные издер­жки, вызванные принятым на шаге k решением, характеризу­ются значением функции

План задачи (стратегия управления) х = (x₁, ..., х_n-1, 0) за­ключается в выборе поэтапных изменений количества работни­ков, а его суммарная эффективность описывается аддитивной функцией

На основе сформулированной модели ставится задача мини­мизации целевой функции (издержек) (5.15). Добавим, что по­становка задачи не будет корректной, если не задать начальное условие на количество работников. Существуют две модифика­ции данной задачи, определяемые типом начального условия: в первом случае задается исходное значение на первом этапе m₁, а во втором — требуемое количество в n-м периодеm_n .

Рассмотрим первый случай. Поскольку фиксированным яв­ляется начальное количество работников и, напротив, ничего не известно о том, каким это количество должно быть на послед­нем этапе, то рассмотрение процесса принятия решений удоб­нее начать с конца. Оптимальное управление на последнем эта­пе п по условию равно х*_n = _n(ξ)=0, поэтому минимальные издержки полностью определяются количеством работников в последнем периоде:

Для остальных предшествующих шагов основное рекуррент­ное соотношение примет вид

где Λ_k(ξ) — минимальные затраты с k-го по п-й периоды, в пред­положении, что количество работников в k-й период равно ξ. Точки _л(ξ), в которых достигаются минимумы (5.17), опреде­ляют условное оптимальное управление на каждом шаге.

Последовательно определяя _л(ξ) и дойдя до этапа 1, мы смо­жем найти безусловное оптимальное управление x₁*из того условия, что на начало первого периода численность работни­ков должна составлять ξ₁* = m₁ , a именно

Остальные компоненты оптимального плана х_k* и состояния ξ_k*, образующие оптимальную траекторию, последовательно находятся по рекуррентным формулам

после чего не составляет труда вычислить оптимальное значе­ние целевой функции (5.15).

Остановимся теперь на втором случае, когда задано фи­нальное состояние управляемого объекта, т. е. желаемое коли­чество работников на последнем периоде ξ_n*= m_n . Очевидно, что в данной ситуации следует поступить с точностью «до наобо­рот» и рассмотреть процесс принятия решений от начала к кон­цу. Наилучшее условное управление на первом шаге ₁(ξ) будет найдено в процессе вычисления функции

где состояние ξ ≥0 является возможным количеством работ­ников на начальном шаге. Соответственно, основное рекуррент­ное соотношение выразит минимальные издержки вплоть до k-го периода через таковые для предыдущих периодов (с перво­го по (k-1)-й) при условии, что численность работников в k-й период будет равна ξ:

Попутно будут найдены функции _k(ξ), k∊2:n, определяю­щие условные оптимальные управления. На последнем перио­де, в силу начального условия, ξ_n*= m_n. Отсюда путем последо­вательного решения рекуррентных уравнений могут быть найдены оптимальные численности работников ξ*_k и безуслов­ные оптимальные управления:

В заключение, как и в первом случае, подсчитывается мини­мальная величина издержек.

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

^ При использовании алгоритмов динамического програм­мирования, если задано начальное состояние управляемой системы, то задача решается вобратном направлении, а если конечное, тo — в прямом. Наконец, если заданы как начальное, так и конечное состояния, то задача суще­ственно усложняется. (В качестве компромисса в этом слу­чае можно отказаться от оптимизации на первом или последнем этапе.)

Продемонстрируем процесс решения задачи о найме работ­ников на конкретном примере:

Для функционирования некоторого предприятия в течение четырех месяцев (нумеруемых от 1 до 4) по нормам требуются следующие количества работников одинаковой квалификации:

причем перед началом первого месяца (в нулевом месяце) фак­тически имеется ξ₀ = 2 сотрудников. Администрация планирует в конце каждого месяца k (кроме последнего) корректировать число работающих на величину x_k , k∊0:4, х₄ = 0. На прием одного сотрудника необходимо затратить 9 у. е., а на увольне­ние — 6 у. е. Предполагается, что расходы на содержание избы­точного работника составляют 8 у. е., а в случае нехватки персо­нала приходится нести затраты в размере 12 у. е. за каждое вакантное место.

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

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

Оценки эффективности управления на каждом шаге имеют вид:

Поскольку в поставленной задаче задано начальное условие ξ*₀ = 2, ее решение начинается с конца, и, следовательно, будут применяться рекуррентные соотношения (5.17). С технической точки зрения будет удобно на каждом шаге составлять две табли­цы значений: функции издержек, получаемых начиная с текуще­го шага в зависимости от текущего состояния и управления,

и функции минимальных издержек в зависимости от текущего состояния

Для сокращения объема табулируемых значений можно вос­пользоваться свойством выпуклости функции Ω_k (x_k , ξ), выте­кающим из выпуклостиf и g. Из выпуклости функции Ω_k (x_k , ξ) следует, что заполнять таблицу ее значений необходимо лишь до тех пор, пока они уменьшаются, т. е. можно остановиться, как только очередное значение оказывается больше предыду­щего. Отметим, что подобные приемы очень широко использу­ются в динамическом программировании. Разумеется, иллюст­рируемые методы не рассчитаны на ручной счет, поскольку связаны с очень большим объемом рутинных вычислений. Ради краткости ниже приведены только фрагменты таблиц, содержа­щие интересующие нас значения.

Итерация 1. Полагаем k=4. На данном этапе функция со­стояния Λ₄(ξ) может быть найдена непосредственно, если учесть, что x₄*=0 и u(0)=0:

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

Итерация 2. Полагаем k=3. Предварительно заполним таб­лицу значений функции Ω₃(x₃, ξ) для достаточно большого множества аргументов согласно формуле:

Выбирая минимальные по х₃ значения Ω₃(x₃, ξ) составим таблицу Λ₃(ξ) и соответствующие значения условных опти­мальных управлений ₃(ξ):

Итерация 3. Полагаем k=2. Так же, как на предыдущей итерации, заполним таблицу значений функции Ω₂(x₂, ξ) со­гласно формуле:

Выбирая минимальные по х₂значения Ω₂(x₂ , ξ), составим таблицу Λ₁(ξ) и соответствующие значения условных опти­мальных управлений ₂(ξ):

Итерация 4. Полагаем k=1. Аналогично предыдущему, за­полним таблицу значений функции Ω₁(x₁, ξ) согласно формуле:

Выбирая минимальные по х₁, значения Ω₁(x₁, ξ), составим таблицу Λ₁(ξ) и соответствующие значения условных опти­мальных управлений ₁(ξ):

Итерация 5. На последней итерации, в связи с наличием на­чального условия ξ*₀ = 2, достаточно вычислить

и найти ₀(2) как точку минимума Ω₀(x₀, 2) . Простые вычисле­ния показывают, что минимум

достигается при x₀(2) = 1.

Следовательно, x*₀ = ₀(2)=1, после чего обратным ходом последовательно вычисляются оптимальные управления и оп­тимальные состояния (оптимальная траектория):

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

Заключение

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

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

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

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: