Решение методом динамического программирования - Метод динамического программирования

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

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

Для определения сущности динамического программирования рассмотрим задачу: Представим себе некоторую операцию О, состоящую из ряда последовательных "шагов" или этапов, например, деятельность отрасли промышленности в течение ряда хозяйственных лет. Пусть число шагов равно m. Выигрыш эффективность операции Z за всю операцию складывается из выигрышей на отдельных шагах: Если Z обладает таким свойством, то его называют аддитивным критерием.

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

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

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

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

Эти задачи должны удовлетворять таким требованиям: Задача оптимизации интерпретируется как n-шаговый процесс управления. Целевая функция равна сумме целевых функций каждого шага. Выбор управления на k-м шаге зависит только о состояния системы к этому шаге, не влияет на предшествующие шаги нет обратной связи. Состояние sk после k-го шага управления зависит только от предшествующего состояния sk-1и управления xk отсутствие последействия.

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

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

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

Имеется n объектов вложений, по каждому из которых известна ожидаемая прибыль fi xполучаемая от вложения определенной суммы средств. Необходимо распределить капитальные вложения между n объектами предприятиями, проектами таким образом, чтобы получить максимально возможную суммарную прибыль.

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

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

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

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

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

Метод динамического программирования — Студопедия

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

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

И к концу XIX. Важное место в развитии математической экономики занимают работы советских ученых. В первую очередь следует назвать Л. Канторовича, чья работа "Математические методы организации и планирования производства", опубликованная в г. Динамическое программирование возникло и сформировалось в — гг.

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

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

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

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

Автореферат выпускной работы магистра на тему: Понятие динамического программирования Общая постановка классической задачи распределения инвестиций Актуальность исследования Цель и задачи работы Обзор существующих исследований и разработок Предполагаемая научная новизна и практическая ценность Литература Введение.

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

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

Armstrong, Dynamic Programming Model for Wastewater Plant Investment, Journal of the Environmental Engineering Division, Vol. Siegmann, Continupus-time dynamic programming for ALM with risk averse loss functions, European Journal of Operational Research, 99, pp. Автореферат носит обзорный характер и не является полной версией магистерской диссертации, так как планируется продолжение работы над диссертацией в течение осеннего семестра г.

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

  2. Допустим, планируются капиталовложения на первый год. Замкнутая СМО с одним каналом и m источниками заявок. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи подзадачи , после чего объединить решения подзадач в одно общее решение.

Написать комментарий

:D:-):(:o8O:?8):lol::x:P:oops::cry::evil::twisted::roll::wink::!::?::idea::arrow: