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

Происхождение термина

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

Алгоритм (метод) решения многоэтапных задач

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

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

Метод сверху и метод снизу

Несмотря то что при расчете на отдельном этапе решения задачи используются параметры процесса на текущий момент, результат оптимизации на предыдущем этапе влияет на расчеты последующих этапов для достижения наилучшего результата в целом. Динамическое программирование называет такой принцип решения методом оптимальности, который определяет, что оптимальная стратегия решения задачи вне зависимости от начальных решений и условий должна последующими решениями на всех этапах составить оптимальную стратегию относительно первоначального состояния. Как видим, процесс решения задачи представляет собой непрерывную оптимизацию результата на каждом отдельном этапе от первого до последнего. Такой метод называется методом программирования сверху. На рисунке схематически показан алгоритм решения сверху вниз. Но существует класс многошаговых задач, в которых максимальный эффект на последнем этапе уже известен, например, мы уже приехали из пункта А в пункт Б и теперь хотим узнать, правильно мы ехали на каждом предыдущем этапе или можно было что-то сделать более оптимально. Возникает рекурсивная последовательность этапов, т. е. мы идем как бы «от обратного». Этот метод решения получил название "метод программирования снизу".

Практическое применение

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

Поиск оптимального пути

С помощью динамической оптимизации возможно решение широкого класса задач по нахождению или оптимизации кратчайшего пути и других задач, в которых «классический» метод перебора возможных вариантов решения приводит к увеличению времени расчета, а иногда вообще неприемлем. Классическая задача динамического программирования - это задача о рюкзаке: дано некоторое количество предметов с определенной массой и стоимостью, и необходимо выбрать набор предметов с максимальной стоимостью и массой, не превосходящий объем рюкзака. Классический перебор всех вариантов в поисках оптимального решения займет значительное время, а с помощью динамических методов задача решается в приемлемые сроки. Задачи поиска кратчайшего пути для транспортной логистики являются основными, и динамические методы решения оптимально подходят для их решения. Наиболее простым примером такой задачи является построение кратчайшего маршрута автомобильным GPS-навигатором.

Производство

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

Научная сфера

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

К вопросу об экономике и управлении

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

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

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

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

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

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

Управление экономикой лежит в физическом плане существования и связано с взаимодействием объектов и личностное участие в этом взаимодействии в меру возможного и допустимого. Сочетание возможного и допустимого формирует некоторую последовательность (как «коридор») управления, в соответствие с текущим целеполагающим началом управляющего субъекта, находящегося в определенных отношениях и взаимосвязях, как с объектами управления, так и с субъектами активной деятельности по реализации общего алгоритма управления.
Возможности физического плана дополняются субъектными возможностями, обусловленными мотивационным началом в деятельности субъектов, реализующих управленческое решение.
Таким образом, преобразующее (управленческое, творческое) начало – как субъектно-социальное, принадлежит эмоциональному плану существования.
В таком случае, весь процесс управления опирается на знание, понимание и предвидение развития природных (главным образом, физических) процессов, обуславливающих суть происходящих изменений с объектами, и такое же понимание субъективной составляющей, используемых движущих сил, для их активного участия в объективных процессах с пользой для социума и личности в глобальной перспективе (которая и определяет критерии нахождения «границ коридора», на его соответствие выбранному, на основе целеполагания, вектору жизнедеятельности).
Динамика управления достигается использованием сослагательного подхода к анализу происходящего и его увязки с обозначенным коридором – и заключается в ответах на совокупность возможных (или невозможных) - а если?
(что, в частности, отражает и метод познания, в том числе исторический – «история, как данность не имеет сослагательного наклонения», но метод исторического анализа вполне может быть "сослагателен" – поиск алгоритма социально-личностного понимания общего, природно-социального, функционала задающего историческую данность).
Именно набор полученных ответов и позволяет вводить коррекцию на каждом шаге (цикле) последовательности управления (и познания), удерживая процесс в изначально обозначенном коридоре.
Динамичность управления отражает интеллектуальный план существования и используемые осознанные (в отличие от «метода тыка» - прерогативы эмоционального плана) методы познания происходящего.
«Заключительным аккордом» управления является предвидение – постановка вопроса - а вдруг?
Которое не базируется на текущей логике понимания разворачивающихся процессов, но отражает «пришедшую на ум» возможность в происходящем (обычно трактуемую, как случайную, но именно в силу личностного непонимания, а не как отражение объективно развивающегося природного процесса). Ответы на этот вопрос «лежат» в духовном плане, заключающем в себе общий функционал личностного (и социального) развития. При определенной личностной грамотности в его использовании, появляется возможность получать ответы из области априорного (интуитивного) «знания» того, что не только уже имеет место, но и грядущего на уровне субъективных возможностей (откуда и «судьба хранит», правда лишь тех, кому этот канал доступен в должной мере, чтобы быть значимым для конкретной личности).

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

Применение динамического программирования для моделирования процессов принятия решений

1.2 Метод динамического программирования и его основные этапы

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

Метод динамического программирования включает три основных этапа:

Предварительный этап.

Этап условной оптимизации.

Этап безусловной оптимизации.

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

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

Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

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

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

Таблица 1.1

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

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

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

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

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

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

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

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

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

Классификация экономико-математических методов и моделей

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

Планирование производства и управления инвестиционными ресурсами

Динамическое программирование - методы и модели оптимизации, когда процесс принятия оптимального решения может быть разбит на этапы (шаги)...

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

Применение динамического программирования для моделирования процессов принятия решений

Распределение инвестиций между предприятиями: "Малышок", "Ронда", "Товиус", "Сластёна", "Читек"

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

Распределение средств между предприятиями: ОАО "Весёлый молочник", ОАО "Нижнекамская пищевая компания", ООО "Сэлдом", ООО "СтойКом", ОАО "Счастье"

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

Трендовые и корреляционные модели

Делим динамический ряд 1 на количество частей, равное количеству неизвестных коэффициентов выравнивающей функции...

Экономические модели зависимости величины активов, подверженных кредитному риску, от пассивов, прибыли (убытков), ВВП

На первом этапе необходимо построить уравнение парной линейной регрессии. Эмпирическое уравнение парной линейной регрессии имеет следующий вид: (1) где Y - объясняемая переменная, X - объясняющая переменная, е - случайная величина (ошибка)...

Для развития трех торговых предприятий выделено 4 млн. руб. Известна эффективность капитальных вложений в каждое предприятие, заданное значением нелинейной функции? k (x k). Требуется составить оптимальный план распределения капитальных вложений между предприятиями. Предполагается, что распределение денежных средств проводится в целых числах x k , x k = 0, 1, 2, 3, 4.

Исходные данные.

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

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

1-ый шаг. k = 3.

2-ый шаг. k = 2.

3-ый шаг. k = 1.

Поясним построение таблиц и последовательность проведения расчетов.

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

В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.

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

Из таблицы 3-го шага имеем F* 3 (e 0 = 4) = 7.6. То есть максимальный доход всей системы при количестве средств e 0 = 4 равен 7.6 млн. руб.

Из этой же таблицы получаем, что первому торговому предприятию следует выделить u* 1 (e 0 = 4) = 1

Из таблицы 2-го шага имеем F* 2 (e 1 = 3) = 4.5. То есть максимальный доход всей системы при количестве средств e 1 = 3 равен 4.5 млн. руб.

Из этой же таблицы получаем, что второму торговому предприятию следует выделить u* 2 (e 1 = 3) = 2

При этом остаток средств составит:

Последнему торговому предприятию достается 1 млн. руб..

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

1-му торговому предприятию выделить 1;

2-му торговому предприятию выделить 2;

3-му торговому предприятию выделить 1;

Что обеспечит максимальный доход, равный 7.6 млн. руб.