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

Министерство образования Саратовской области

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

Доклад

Ученицы 10 «Б» класса

МОУ «Лицея № 15»

Мацак Юлии

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

Сергеева Надежда Викторовна

Учитель:

Копова Ольга Васильевна

Саратов  2011

Содержание.

Введение…………………………………………………………………………..3

1. Задача динамического программирования………………………………….4
2. Принцип поэтапного построения оптимального управления…………...…8
3. Общая постановка задачи динамического программирования…………...11
4. Общая формульная запись решения задачи оптимального управления      методом динамического программирования………………………………14
5. Задача о распределении вложений………………………………………….20

Заключение………………………………………………………………………23

Список литературы……………………………………………………………...24

Введение.

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

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

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

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

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

1. Вентцель Е.С. Элементы динамического программирования; изд-во Наука, 1964, 176с
2. Ховард Р. Динамическое программирование и марковские процессы. - М. : Сов. радио, 1964.
3. Беллман Р. Динамическое программирование. М.: Изд-во иностр. лит., 1960. 400 с.
4. Хедли Дж. Нелинейное и динамическое программирование, пер. с англ., М., 1967.

В этой литературе рассматривается метод динамического программирования.

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

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

Во 2 главе рассмотрен принцип поэтапного построения оптимального управления.

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

В 4 главе рассмотрена запись в общем виде не только постановки, но и решения задачи динамического программирования.

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

Самая общая задача оптимального (наилучшего) планирования ставится следующим образом.

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

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

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

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

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

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

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

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

Некоторые операции естественно распадаются на этапы; в других это членение приходится вводить искусственным путем.

Рассмотрим пример «естественно многоэтапной» операции. Пусть планируется деятельность некоторой системы промышленных предприятий

П1, П2, …, Пk

на некоторый период времени Т, состоящий из m хозяйственных лет (рис. 1.1).

Рис. 1.1

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

В начале каждого хозяйственного года (т. е. в моменты t1, t2, …, ti, …, tm) производится финансирование всей системы предприятий, причем на каждое из них выделяется какая-то доля средств, имеющихся к этому времени в распоряжении планирующего органа.

Обозначим xi(j)сумму, выделяемую в начале i-го года на долю предприятия Пj.

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

Сформулированная задача представляет собой типичную задачу многоэтапного планирования.

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

Предположим, что распределение средств на i-м шаге операции выполнено, т. е. мы выбрали определенное управление Ui:

Ui= (xi(1), xi(2), …, xi(k)).                              (1.1)

Формула (1.1) читается следующим образом: управление Ui, на i-м шаге состоит в том, что мы выделили предприятию П1 средства xi(1), предприятию П2 — средства xi(2), и т.д.

Рассмотрим всю совокупность управлений (выделенных средств)

U1, U2, …, Um                                           (1.2)

на m шагах операции. Критерий эффективности W многоэтапной операции, в качестве которого мы выбрали суммарный доход за m лет, зависит от всей совокупности управлений (1.2):

W=W(U1, U2, …, Um).                            (1.3)

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

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

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

xi(1), xi(2), …, xi(k)

совокупность которых

Ui=(xi(1), xi(2), …, xi(k))

образует управление на i-м этапе.

Как нужно выбрать совокупность управлений

U1, U2, …, Um

для того, чтобы некоторая величина W, зависящая от нее, обратилась в максимум:

W=W(U1, U2, …, Um)=max?

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

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

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

W=W(x1(1), x1(2), …, x1(k); x2(1), x2(2), …, x2(k); …; xm(1), xm(2), …, xm(k))     (1.4)

Эта функция многих аргументов может быть исследована на максимум, как таковая, без обязательного разделения элементов управления «по шагам». Для этого нужно найти такую совокупность значений аргументов xi(j) (i=1, 2, …, m; j=1, 2, ..., k), при которых функция (1.4) достигает максимума.

Казалось бы, чего проще?

Однако эта простота обманчива,

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

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

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

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

2. Принцип поэтапного построения оптимального управления

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

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

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

Проиллюстрируем принцип «дальновидного» планирования на примерах.

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

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

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

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

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

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

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

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

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

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

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

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

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

Продемонстрируем схему такой процедуры. Пусть планируется m-шаговая операция, и неизвестно, чем кончился (m-1)-й шаг. Сделаем об этом ряд «гипотез» или «предположений». Эти гипотезы мы обозначим:

                                 Sm-1(1), Sm-1(2), …, Sm-1(j), …                                    (2.1)

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

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

Предположим, что для каждого из предположений (2.1) условное оптимальное управление U*m на последнем шаге найдено:

  U*m (Sm-1(1));  U*m (Sm-1(2)); …; U*m (Sm-1(j)); …               (2.2)

Это означает, что последний шаг спланирован для любого исхода предпоследнего.

Перейдем к планированию следующего от конца, предпоследнего шага. Снова сделаем ряд гипотез о том, чем кончился предпредпоследний ((m-2)-й) шаг:

Sm-2(1), Sm-2(2), …, Sm-2(k), …                                                       (2.3)

Поставим вопрос: как нужно выбирать для каждой из этих гипотез условное оптимальное управление на (m-1)-м шаге?

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

Другими словами, для каждой из гипотез (2.3) нужно найти такое условное оптимальное управление на (m-1)-м шаге U*m-1(Sm-2), чтобы оно, в совокупности с уже найденным условным оптимальным управлением U*m (Sm-1), давало максимально возможный выигрыш на двух последних шагах.

Очевидно, к (m-1)-му шагу таким же точно способом может быть присоединен (m-2)-й и т. д. вплоть до самого последнего (от конца) 1-го шага, с которого процесс начинается.

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

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

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

Интерпретация управления в фазовом пространстве

Рассмотрим следующую общую задачу.

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

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

Обозначим наше управление (т. е. всю систему мероприятий, с помощью которой мы влияем на состояние системы S) одной буквой U. Критерий W зависит от этого управления; эту зависимость мы запишем в виде формулы:

W=W(U)                                                               (3.1)

Требуется найти такое управление U («оптимальное управление»), при котором критерий W достигает максимума:

W*=max{W(U)}                                                     (3.2)

                                                U

Запись max читается: «максимум по U», а формула (3.2) означает:

               U

W* есть максимальное из значений, которые принимает критерий W при всех возможных управлениях U.

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

С учетом начальных и конечных условий задача оптимального управления формулируется следующим образом: из множества возможных управлений U найти такое управление U*, которое переводит физическую систему S из начального состояния S0 в конечное Sкон так, чтобы некоторый критерий W(U) обращался в максимум.

Дадим процессу управления геометрическую интерпретацию. Для этого нам придется несколько расширить наши привычные геометрические представления и ввести понятие о так называемом «фазовом пространстве».

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

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

Пусть, например, состояние системы S характеризуется только одним параметром — координатой x. Тогда изменение этой координаты будет изображаться перемещением точки S по оси Ох (или по определенному ее участку, если на координату x наложены какие-то ограничения). В данном случае фазовое пространство будет одномерным и представляет собой ось абсцисс Ох или ее участок, а управление интерпретируется законом движения точки S из исходного состояния S0 в конечное Sкон. (рис. 6.1).

 Рис. 3.1

Если состояние системы S характеризуется двумя параметрами x1 и x2 (например, абсцисса материальной точки и ее скорость), то фазовым пространством будет плоскость x1Ox2 или какая-то ее часть (если параметры x1 и x2 наложены ограничения), а управляемый процесс будет изображаться перемещением точки S из S0 в Sкон по определенной траектории на плоскости x1Ox2 (рис. 3.2).

Если состояние системы характеризуется тремя параметрами x1, x2, x3  (например, две координаты и скорость), то фазовым пространством будет обыкновенное трехмерное пространство или его часть, а управляемый процесс изобразится перемещением точки S по пространственной кривой (рис. 3.3)

                    Рис. 3.2                                       Рис. 3.3

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

x1, x2, …, xn

мы будем изображать его как точку S в n-мерном фазовом пространстве, а управление интерпретировать, как перемещение точки S из какой-то начальной области S0 в конечную Sкон по некоторой «траектории», по определенному закону.

Итак, сформулируем общую задачу оптимального управления в терминах фазового пространства:

Найти такое управление U* (оптимальное управление), под влиянием которого точка S фазового пространства переместится из начальной области S0 в конечную область Sкон так, что при этом критерий W обратится в максимум.

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

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

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

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

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

Если  критерий W обладает таким  свойством:

                                                             (4.1)

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

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

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

Пусть имеется процесс управления физической системой S, расчлененный на m шагов (этапов). В нашем распоряжении на каждом (i-м) шаге имеется управление Ui посредством которого мы переводим систему из состояния Si-1, достигнутого в результате (i-1)-го шага, в новое состояние Si, которое зависит от Si-1, и выбранного нами управления Ui. Эту зависимость мы запишем так:

Si=Si(Si-1, Ui)                                                                     (4.2)

рассматривая  Si как функцию двух аргументов Si-1 и Ui.

Заметим, что для применения метода динамического программирования существенно, чтобы новое состояние Si зависело только от состояния Si-1 и управления на i-м шаге Ui и не зависело от того, каким образом система пришла в состояние Si-1. Если это оказывается не так, то следует «обогатить» понятие «состояния системы», введя в него те параметры из прошлого, от которых зависит будущее, т.е. увеличить число измерений фазового пространства.

Под влиянием управлений U1, U2, …, Um система переходит из начального состояния S0 в конечное Sкон. В результате всего процесса за m шагов получается «доход» или «выигрыш»

                                                           (4.3)

где wi(Si-1,Ui)– выигрыш на i-м шаге, зависящий, естественно, от предыдущего состояния системы Si-1 и выбранного управления Ui.

Задана область начальных состояний S0 и конечных состояний Sкон. Требуется выбрать начальное состояние S*0 и управления U*1, U*2, …, U*m на каждом шаге так, чтобы после m шагов система перешла в область Sкон и при этом выигрыш W обратился в максимум.

Опишем в общем виде процедуру применения метода динамического программирования к решению этой задачи.

Для этого нам понадобится ввести некоторые новые обозначения. Мы уже обозначили W – выигрыш за все время процесса; wi – выигрыш за i-й шаг. Поскольку процесс динамического программирования разворачивается с конца, нам придется внести специальное обозначение для выигрыша, приобретаемого за несколько последних шагов процесса.

Обозначим:

Wm – выигрыш за последний шаг,

Wm-1,m – выигрыш за два последних шага,

…

Wi,i+1, …, m – выигрыш за последние (m-i+1) шага, начиная с i-го и кончая m-м.

Очевидно,

Wm=wm,

Wm-1,m=wm-1+wm,

 …                                                                          (4.4)

Wi,i+1, …, m=wi+wi+1+…+wm

Как мы уже знаем, процесс оптимизации управления методом динамического программирования начинается с последнего (m-го) шага. Пусть после (m-1)-го шага система находится в состоянии Sm-1. Так как последний (m-й) шаг должен перевести систему в состояние Sm=Sкон, то в качестве Sm-1 можно брать не все в принципе возможные состояния системы, а только те, из которых за один шаг можно перейти в область Sкон.

Предположим, что состояние Sm-1 нам известно, и найдем при этом условии условное оптимальное управление на m-м шаге; обозначим его U*m(Sm-1). Это – то управление, которое, будучи примененным на m-м шаге, переводит систему в конечное состояние Sm, причем выигрыш на этом последнем шаге Wm достигает своего максимального значения:

W*m(Sm-1)=max{Wm(Sm-1, Um)}                                         (4.5)

Напомним смысл символической формулы Wm(Sm-1, Um) означает выигрыш вообще (не оптимальный) на последнем шаге; он зависит как от результата предыдущего шага Sm-1, так и от примененного на данном шаге управления Um. Из всех выигрышей Wm(Sm-1, Um) при разных управлениях Um выбирается тот выигрыш W*(Sm-1), который имеет максимальное значение; это и означает запись max. Заметим, что в качестве управлений Um мы должны брать только те, которые переводят систему из заданного состояния Sm-1 в состояние Sm, принадлежащее области Sкон.

Находя условное максимальное значение выигрыша W*m(Sm-1), мы тем самым находим и условное оптимальное управление U*m(Sm-1). Тот факт, что условный максимальный выигрыш W*m(Sm-1) достигается при условном оптимальном управлении U*m(Sm-1), мы запишем символически в виде

W*m(Sm-1)U*m(Sm-1)

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

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

Перейдем к оптимизации предпоследнего ((m-1)-го) шага. Сделаем снова предположение, что в результате (m-2)-го шага система пришла в состояние Sm-2. Пусть на (m-1)-м шаге мы применили управление Um-1. В результате этого управления мы на (m-1)-м шаге получим выигрыш, зависящий как от состояния системы, так и от примененного управления:

wm-1=wm-1(Sm-2; Um-1)                                                          (4.6)

а система перейдет в новое состояние Sm-1, тоже зависящее от предыдущего состояния и от управления:

Sm-1=Sm-1(Sm-2; Um-1)                                                           (4.7)

Но для любого результата (m-1)-го шага следующий, m-й шаг уже оптимизирован, и максимальный выигрыш на нем равен

W*m(Sm-1)=W*m(Sm-1(Sm-2, Um-1))                                          (4.8)

Введем в рассмотрение полный выигрыш на двух последних шагах при любом управлении на (m-1)-м шаге и оптимальном управлении на m-м шаге. Обозначим его W+m-1,m; знак «+» будет нам напоминать, что это выигрыш при неполностью оптимизированном управлении, в отличие от знака «*», которым мы обозначили выигрыш при полностью оптимизированном управлении. Выигрыш W+m-1,m, очевидно, зависит от предыдущего состояния системы Sm-2 и примененного на (m-1)-м шаге управления Um-1. Учитывая формулы (4.6) и (4.8), получим следующее выражение для W+m-1,m:

W+m-1,m (Sm-2, Um-1)=wm-1(Sm-2, Um-1)+ W*m(Sm-1(Sm-2, Um-1))              (4.9)

Нам нужно выбрать такое оптимальное условное управление на (m-1)-м шаге U*m-1(Sm-2), при котором величина (4.9) достигла бы максимума:

W*m-1,m (Sm-2)=max{ W+m-1,m(Sm-2, Um-1)}                                (4.10)

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

Таким образом, найден максимальный условный выигрыш на двух последних шагах и соответствующее ему оптимальное управление на (m-1)-м шаге:

W*m-1,m(Sm-2)U*m-1(Sm-2)

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

W*m-2,m-1,m(Sm-3)U*m-2(Sm-3)

W*m-3,m-2,m-1,m(Sm-4)U*m-3(Sm-4)

и т.д.

Если мы уже оптимизировали (i+1)-й шаг для любого исхода i-го, т.е. нашли

W*i+1, …, m(Si)U*i+1(Si),

то условная оптимизация i-го шага производится согласно общей формуле

W*i,i+1, …, m(Si-1)=max{W+ i,i+1, …, m(Si-1, Ui)}                                   (4.11)

где

W+i, i+1, …, m(Si-1, Ui)=wi(Si-1, Ui)+ W*i+1, …, m(Si(Si-1, Ui))       (4.12)

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

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

W*i, i+1, …, m(Si-1) U*i(Si-1)                                                  (4.13)

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

W*1, …, m(S0) U*1(S0),                                                       (4.14)

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

Остается выбрать оптимальным образом начальное состояние системы S*0. Если начальное состояние S0 в точности задано (т.е. вся область S0 сводится к одной точке S0), то выбора нет. Если же точка S0 может свободно выбираться в пределах области S0, то нужно оптимизировать выбор начального состояния, т.е. найти абсолютный (уже не условный) максимальный выигрыш за все шаги:

W*1, …, m=max{W*1, …, m(S0)},                                               (4.15)

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

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

W*=W*1,2, …, m S*0                                                           (4.16)

Но построено ли уже оптимальное управление? Нет еще: ведь мы нашли на каждом шаге только условное оптимальное управление.

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

В качестве начального состояния системы берется S*0 (или просто S0, если начальное состояние жестко фиксировано). На первом шаге применяется оптимальное управление U*1

U*1=U*1(S*0)                                                                     (4.17)

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

S*1=S1(S*0, U*1)                                                                   (4.18)

Теперь нужно выбрать оптимальное управление на втором шаге. Мы уже оптимизировали его для любого результата первого шага, т.е. знаем U*2(S1); подставляя в него S*1, получим

U*2=U*2(S*1)                                                                   (4.19)

И так далее, пока не дойдем до оптимального управления на последнем шаге

U*m=U*m(S*m-1)                                                                (4.20)

и конечного состояния системы

S*m=S*кон=S*m(S*m-1, U*m)                                                  (4.21)

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

U*=(U*1, U*2, …, U*m)                                                        (4.22)

Таким образом, в процессе динамического программирования последовательность этапов проходится дважды: первый раз — от конца к началу, в результате чего находится максимальное значение выигрыша W*, оптимальное начальное состояние процесса S*0 и условное оптимальное управление на каждом шаге; второй раз — от начала и концу, в результате чего находится оптимальное управление U*i на каждом шаге и конечное состояние системы при оптимальном управлении S*кон.

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

Эти трудности связаны, во-первых, с выбором группы параметров x1,x2,…, xn, характеризующих состояние физической системы S. Как уже было сказано, эти параметры нужно выбирать так, чтобы при заданном состоянии S(x1,x2, …, xn) системы S в любой момент ее следующее состояние S’(x1’,x2’, …, xn’), в которое она переходит под влиянием управления U, зависело только от прежнего состояния S и управления и не зависело от «предыстории» процесса, т. е. от того, когда, как и в результате каких управлений система пришла в состояние S. Если это оказывается не так, приходится те элементы прошлого, от которых зависит будущее, включать в совокупность параметров x1,x2, …, xn, характеризующих состояние системы в данный момент. А это приводит к увеличению числа измерений фазового пространства и, значит, к усложнению задачи.

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

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

5. Задача о распределении вложений

Постановка задачи:

Компания, занимающаяся производством пищевых продуктов, поставляет их для продажи в четыре города. Этим городам поставлены в соответствие торговые зоны 1, 2, 3, 4. В каждой из зон проведено изучение состояния рынка и найдены математические ожидания доходов, как функции полных капиталовложений (складские помещения, магазины, торговые уполномоченные, реклама и т.д.), которые приведены в табл. 5.1.

Таблица 5.1.

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

Решение:

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

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

fi (x) – доход, получаемый от вложения х млн. в i-ю зону, i=1,2,3,4;

F1,2(А) – максимальный доход, получаемый от вложения А млн. в зоны 1 и 2 вместе;

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

F1,2,3,4(А) – максимальный доход, получаемый от вложения А млн. в зоны 1, 2, 3 и 4 вместе.

Функцию F1,2 (А) определим равенством

                               F 1,2(А)=max [f1 (x)+f2(A-x)]                                          (5.1)

Таким образом, чтобы определить F 1,2(2), надо вычислить:

f1(0)+f2 (2)=0+ 0.41=0.41,

f1(1)+f2(1)=0.28+0.25=0.53,

f 1(2)+f 2(0)=0.45+0=0.45,

так что получаем F 1,2(2)=0.53. Значения величин F1,2 (A), вычисленные по формуле (2.1), при вложениях А = 0, 1, …, 10, приведены в табл. 5.2

Таблица 5.2

В табл. 5.2 приведены оптимальные стратегии, соответствующие максимальным доходам при данных капиталовложениях. Например, если в зоны 1 и 2 вместе вложить 4 млн., то в зону 1 надо вложить 3 млн., а во вторую зону – 1 млн., именно это обозначает вектор (3,1) в последнем столбце табл. 5.2; доход в этом случае равен 0.90 млн. Если в зоны 1 и 2 вкладывать 10 миллионов, следует выбрать стратегию (7,3); для такого распределения доход равен 1.68 млн.

Аналогично определим функции F 1,2,3(A) и  F 1,2,3,4(A)формулами

F 1,2,3(A)=max {F 1,2(x)+f 3(A-x)},                                   (5.2)

F 1,2,3,4(A)=max {F 1,2,3(x)+f 4(A-x)}                                (5.3)

Значения функций, вычисленные по формулам (5.2) и (5.3), приведены в табл. 5.3 и 5.4 соответственно. Оптимальные распределения вложений приведены в табл. 5.5

Таблица 5.3

Таблица 5.4

Таблица 5.5

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

Заключение

Итак, наряду с требуемым решением, получены такие оптимальные решения в случаях, когда капиталовложения составляют 1, 2, 3, …, 9 млн. рублей.

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

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

Список литературы.

1. Вентцель Е.С. Элементы динамического программирования; изд-во Наука, 1964, 176с
2. Ховард Р. Динамическое программирование и марковские процессы. - М. : Сов. радио, 1964.
3. Беллман Р. Динамическое программирование. М.: Изд-во иностр. лит., 1960. 400 с.
4. Хедли Дж. Нелинейное и динамическое программирование, пер. с англ., М., 1967.