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

7

Контрольная работа

по дисциплине  «Математические методы в экономике»

на тему

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

Москва – 2010

Содержание:

1. Уравнение Беллмана.

2. Задача управления запасами.

1.  Уравнение Беллмана

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

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

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

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

Оптимизация управления n-шагового процесса состоит в том, чтобы найти такую последовательность управлений ui, при которой критерий качества Jn(u) принимает минимальное значение. Это минимальное значение критерия качества управления n-шагового процесса будет зависеть только от начального состояния x0 и его можно обозначать fn(x0). По определению имеем:

fn(x0)=min min … min [Q(x0,u0)+ Q(x1,u1)+…+ Q(xn-1,un-1)].

Заметим, что первое слагаемое этого выражения Q(x0,u0) зависит только от управления u0, тогда как остальные слагаемые зависят как от u0, так и от управлений на других шагах. Так, Q(x1,u1) зависит от u1, но оно зависит и от u0, так как x1 =T(x0,u0). Аналогично обстоит дело и с остальными слагаемыми. Поэтому выражение можно записать в виде

fn(x0)=min {Q(x0,u0)+ min … min [Q(x1,u1)+…+ Q(xn-1,un-1)]}.

Заметим далее, что выражение min … min [Q(x1,u1)+…+ Q(xn-1,un-1)] представляет собой минимальное значение критерия качествa управления   (n-1)-шагового процесса, имеющего начальное состояние х1. В соответствии с определением эту величину можем обозначить через fn-1(x1). Таким образом, получаем: fn(x0)=min {Q(x0,u0)+ fn-1(x1)}.

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

fn-1(x1)=min {Q(x1,u1)+ fn-2(x2)}.

Продолжая эти рассуждения, получаем аналогичное выражение для    (n -k) -шагового процесса, начинающегося с состояния xk:

fn-k(xk)=min {Q(xk,uk)+ fn-(k+1)(xk+1)}.

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

Рекуррентная формула — формула вида выражающая каждый член последовательности an () через предыдущих членов.

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

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

                                            2.1

где wi — выигрыш на i-м шаге. Если W обладает таким свойством, то его называют аддитивным критерием.

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

Шаговые управления в общем случае не числа, а, как правило, векторы, функции и т.п.

В модели динамического программирования процесс на каждом шаге находится в одном из состояний s множества состояний S. Считается, что всякому состоянию сопоставлены некоторые шаговые управления. Эти управления таковы, что управление, выбранное в данном состоянии при любой предыстории процесса, определяет полностью следующее состояние процесса. Обычно выделены два особых состояния: s0 — начальное и sw — конечное.

Итак, пусть каждому состоянию поставлено множество допустимых шаговых управлений и каждому шаговому управлению соответствует — состояние, в которое процесс попадает из si в результате использования шагового управления u. Пусть процесс находится в начальном состоянии s0. Выбор переводит процесс в состояние s1 = σ(s0,u1), выбор — в состояние s2 = σ(s1,u2) и т.д. В результате получается траектория процесса, которая состоит из последовательности пар

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

  2.2

   2.3

конечны и Us для различных s не пересекаются.

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

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

              2.4

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

Wmax = maxU{W(u)}.             (2.5)

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

Загрузку рюкзака можно представить себе как процесс, состоящий из n шагов. На каждом шаге требуется ответить на вопрос: взять данный предмет в рюкзак, или нет? Таким образом, шаг процесса — присваивание переменной xi значения 1 или 0.

Теперь определим состояния. Очевидно, что текущее состояние процесса характеризует остаточная грузоподъёмность рюкзака — вес, который остался в нашем распоряжении до конца (до полной укладки рюкзака).

Следовательно, под состоянием перед i-м шагом понимается величина

        2.6

при этом s0 является начальным состоянием, которому соответствует величина b — исходная грузоподъемность рюкзака.

Управление на i-м шаге означает присваивание двоичной переменной xi значения 0 или 1. Значит, на каждом шаге имеем всего два управления. Причем допустимость управления ui, устанавливающего xi = 1, определяется условием

             (2.7)

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

Тогда формулы (2.6), (2.7) примут следующий вид:

                           (2.8)

         (2.9)

Шаговый выигрыш можно определить как Поэтому

             (2.10)

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

Уравнение Беллмана для задачи о рюкзаке:

Пусть к началу -шага остаточная грузоподъемность равна s. Оптимальное управление определяется следующим образом:

- если то последний предмет можно положить в рюкзак, что соответствует оптимальному управлению ;

-  иначе 

Ясно, что оптимальный условный выигрыш на -ом шаге составит

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

Нужно найти такое при котором этот выигрыш максимален

где максимум берется по всем допустимым управлениям — управлениям, для которых верно ограничение (2.9). Напомним, что может принимать лишь два значения: 0 или 1.

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

   (2.11)

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

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

                 сравнительную простоту расчетов, удобство их алгоритмизации;

                 независимость от вида исходных данных (целевая функция и функции ограничений могут быть линейными и нелинейными, целочисленными и нецелочисленными, заданными аналитически и таблично).

Недостатки метода

                 большой объём промежуточной информации;

                 большой объём вычислительной работы.

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

1.                 Задача управления запасами

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

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

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

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

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

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

1) длительность одного этапа планового периода;

2) выпуск продукции в течение этапа;

3) спрос на продукцию в конце этапа;

4) уровень запасов изделий на конец этапа;

5) максимально возможный выпуск изделий на одном этапе;