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

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

Реклама

Пусть процесс управления некоторой системой Х состоит из m шагов (этапов); на i-м шаге управление yi переводит систему из состояния xi-1, в котором она находилась после (i — 1)-го шага, в новое состояние xi. При этом задана функция fi(х, у), и новое состояние определяется по этой функции значениями  xi-1,  yi  так, что xi = fi (xi-1, yi),  i = 1, 2,…, m. Таким образом, управления у1, у2, …, уm переводят систему из начального состояния х0 ∈ Х0 в конечное состояние хm ∈ Хm, где Х0 и Хm — совокупности допустимых начальных и конечных состояний системы Х.

Одна из возможных постановок задач динамического программирования состоит в следующем. При заданном начальном состоянии х0 требуется выбрать управления у1, у2, …, уm таким образом, чтобы система Х перешла в допустимое конечное состояние и при этом заданная целевая функция F(х0, у1, х1,…, уm, хm) достигла максимального значения F*, т. е.

где максимум берётся по всем управлениям у1, …,  уm,  для  которых  хm  ∈ Хm.

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

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

В основе динамического программирования лежит принцип оптимальности, сформулированный Р. Беллманом. Пусть выбраны некоторые управления  у1, у2, …, yk и тем самым траектория х0, х1 , …,xk состояний и требуется  завершить  процесс, т. е. выбрать у k+1, …,  уm ( а   значит,  и   xk+1, …, хm).

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

то и весь процесс не будет оптимальным. Пользуясь принципом оптимальности Беллмана, можно получить основное функциональное соотношение динамического программирования, которое состоит  в следующем. Пусть  ωm(х) = 0,

k = 1, 2, …, m, где максимум берётся по всем управлениям у, допустимым на шаге k. Соотношение, определяющее зависимость ωk-1 от ωk, называется уравнением Беллмана. Смысл этих функций достаточно ясен: если система на шаге k-1 оказалась в состоянии х, то ωk-1(х) есть максимально возможное значение функции Fk. Одновременно с построением функций ωk-1(х) находятся условные оптимальные управления yk(х) на каждом шаге, т. е. значения оптимального управления при всевозможных предположениях о состоянии х системы на шаге k-1. Окончательно оптимальные управления находятся последовательным вычислением величин ω00) = F*, у1, х1, у2, …, уm, xm.

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

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

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

Лит.: Беллман Р. Динамическое программирование. М., 1960; Математическая теория оптимальных процессов. М., 1961; Ховард Р. А.

Динамическое программирование и марковские процессы. М., 1964; Хедли Дж. Нелинейное и динамическое программирование. М., 1967; Хедли Дж., Уайтин Т. Анализ систем управления запасами. М., 1969.

Тоичкина О.В.
Автореферат выпускной работы магистра на тему:

«Динамическое программирование в решении производственных задач»


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

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

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

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

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

где zi- выигрыш на i-м шаге.

Если Z обладает таким свойством, то его называют аддитивным критерием.

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

Совокупность всех шаговых управлений является управлением операцией в целом.

Обозначим его буквой х, а шаговые управления- буквами х1, х2, … , хm: х=х(х1, х2, … , хm). Требуется найти такое управление х, при котором выигрыш Z обращается в максимум:

То управление х*, при котором этот максимум достигается, называется оптимальным управлением. Оно состоит из совокупности оптимальных шаговых управлений: х*=х*(х1*, х2*, … , хm*).

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

где Х- множество допустимых (возможных) управлений.

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

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

Метод динамического програмирования может применяться только для определенного класса задач. Эти задачи должны удовлетворять таким требованиям:

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

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

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

Этот принцип впервые был сформулирован Р.

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

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

Наверх

Общая постановка классической задачи распределения инвестиций

Рассмотрим общую постановку динамической задачи распределения инвестиций.

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

Для составления математической модели исходим из предположений:

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

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

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

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

Наверх

Актуальность исследования

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

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

Наверх

Цель и задачи работы

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

Объектом исследования выступают инвестиционные проекты, основные фонды, производственные и материальные запасы на предприятиях.

Цель работы – исследование методов математической оптимизации инвестиционной деятельности предприятия методом динамического программирования.

Данная цель достигается путем следующих задач работы:

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

Наверх

Обзор существующих исследований и разработок

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

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

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

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

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

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

Разработан ряд методов и моделей, предназначенных для предприятий и различного характера.

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

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

Наверх

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

Научная новизна работы определяется усовершенствованием модели принятия решения инвестиционного планирования благодаря таким факторам:

  • учет приоритетности проектов;
  • учет уровня риска;
  • оперативное распределение ресурсов с учетом их возможной ограниченности в текущий момент времени.

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

Литература

  1. Мищенко А.В., Попов А.А.

    Некоторые подходы к оптимизации инвестиционного портфеля , «Менеджмент в России и за рубежом», №2 / 2002.

  2. John M. Armstrong, Dynamic Programming Model for Wastewater Plant Investment, Journal of the Environmental Engineering Division, Vol. 102, No. 5, September/October 1976, pp. 985-1003
  3. Arjen H. Siegmann, Continupus-time dynamic programming for ALM with risk averse loss functions, European Journal of Operational Research, 99, pp. 123-135, 1997.
  4. Мищенко А.В., Джамай Е.В. Динамическая задача определения оптимальной производственной программы, Менеджмент в России и за рубежом №2 / 2002
  5. R.A.A.Wijnen. Runway Capacity Planning Supported by Dynamic Programming, Aerospace science and technology, 7/2003.

Наверх

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

#include <string>

#include <cstdio>

#include <iostream>

intlast_was_less=-1;

boolisGood(inta,intb){

if(a>b&&last_was_less==1){

last_was_less=0;

returntrue;

}

if(a<b&&last_was_less==0){

last_was_less=1;

returntrue;

}

if(last_was_less==-1){

if(a<b)last_was_less=1;

elselast_was_less=0;

returntrue;

}

returnfalse;

}

intmain(){

freopen("INPUT.TXT","r",stdin);

freopen("OUTPUT.TXT","w",stdout);

intn;

std::cin>>n;

intseq[n];

for(inti=0;i<n;i++){

std::cin>>seq[i];

}

intlongest=0;

for(inti=0;i<n-1;i++){

intcount=1;

for(intj=i;j<n-1;j++){

if(isGood(seq[j],seq[j+1])){

count++;

}else{

last_was_less=-1;

break;

}

}

if(count>longest)

longest=count;

}

std::cout<<longest<<std::endl;

return0;

}

Поиск Лекций


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

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

 

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

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

Рассмотрим основные понятия и обозначения, используемые при построении модели.

S – состояние системы. Описывается набором параметров (х1, х2,… , хm). Для краткости будем отождествлять набор параметров, описывающих состояние системы, с этим состоянием.

Si – состояние системы к началу i-го шага.

Система меняет своё состояние по шагам под действием управления U=(u1, u2,… ,un), где каждая компонента представляет собой одно из возможных управленческих решений (принимаемое на соответствующем шаге).

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

Система рассматривается на протяжении n шагов.

W(U) – целевая функция. Оценивает качество управления. Обычно при описании этой функции используют понятие «доход» и говорят о максимизации дохода (выгоды) или минимизации затрат.

Wi(ui, Si) – доход на i-м шаге, получаемый при нахождении системы в состоянии Si при реализации управления ui.

Fi(Si) – максимальный доход, получаемый начиная с i-го и до n-ного шага, если (i–1)-ый шаг система завершила в состоянии Si.

 

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

Пусть состояние системы можно описать набором параметров (х1, х2,… , хm). Система рассматривается на протяжении n шагов. На каждом из шагов реализуются управленческие решения, составляющие в совокупности управление U=(u1, u2,… ,un). Качество управления оценивается целевой функцией W(U).

Цель: для данного начального состояния системы определить оптимальное управление U*, максимизирующее целевую функцию.

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

 

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

Для применения этого алгоритма должны выполняться два условия:

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

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

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

  1. Начинаем применять алгоритм с последнего шага (k=n), при этом считаем, что .
  2. Находим оптимальное управленческое решение на данном шаге, учитывая оптимальный план для последующих шагов:

.

  1. Переходим к предшествующему шагу (уменьшаем k на 1).
  2. Алгоритм завершается при достижении первого шага. Выбранный набор управленческих решений составит оптимальное управление:

.

 

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

 

Виды решаемых задач

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

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

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

 

©2015-2018 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Нарушение авторских прав и Нарушение персональных данных

Добавить комментарий

Закрыть меню