Раздел 3. Динамическое программирование

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

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

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

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

-распределение дефицитных капитальных вложений между возможными новыми направлениями их использования;

-разработка правил замены выбывающих из эксплуатации основных фондов;

-разработка оптимального плана строительства и оснащения предприятия;

-систематизация методов поиска ценного ресурса;

- и другие задачи.

1.Модель задачи оптимального распределения инвестиций.

Пусть фирма состоит из n предприятий Р1,Р2, ... , Рn. Часть полученной прибыли в размере Q решено инвестировать в расширение производства на продприятиях. Целью вложений является дополнительное получение прибыли f. Эта дополнительная прибыль будет складываться из дополнительных прибылей fk, полученных на предприятиях Pk, k=1, ... ,n, в результате сделанных в эти предприятия вложений Vk. Суммарная дополнительная прибыль равна

f(v) =å fk (Vk), V= (V1, ... ,Vn).

Предполагается, что все значения fk(Vk) известны.

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

2.Модель задачи о замене оборудования.

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

Обозначим моменты начала каждого этапа через Т0, Т1, ... , Тn-1; момент завершения периода - через Тn. Тогда на каждом этапе выбираем одно из двух возможных управлений:

u1 - сохранить уже установленное оборудование и продолжать на нем выпуск;

u2 - заменить оборудование, приобретя и установив новый комплект.

Состояние процесса на каждом из этапов Тк характеризуется возрастом обору-дования Ski оборудования, эксплуатируемого к началу данного этапа: Ski=t, если перед моментом Tk оборудование имело возраст равный t=i. Прибыль fk получаемая на k-ом этапе, зависит от состояния оборудования Ski и сделанного выбора uk:

c(t)-r(t), если uk=u1

fk =fk(Ski; uk)

c(0) - r(0) - z, если uk=u2.

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

n-1

f = å fk (Ski; uk).

k=0

3. Модель задачи о строительстве и оснащении

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

В начальный момент Т0 строительство не начато и оборудование не установлено. В итоге требуется установить m комплексов оборудования и построить n зданий. Часть оборудования можно размещать в старых, ранее построенных помещениях, что, возможно, обойдется дороже размещения в новых корпусах.

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

Данная задача допускает интерпритацию как задача динамического программирования, если ввести следующие обозначения. Пусть Ski - состояние процесса, означающее, что число установленных комплектов оборудования в момент, когда в эксплуатацию введено k зданий, равно i (0<= i<=m); uk -управление на к-ом этапе (k=0, ... , n-1). Для того чтобы процесс был переведен на очередной этап, управление может быть одним из следующих:

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

установка нескольких очередных комплектов оборудования и ввод очередного здания;

Если процесс находится в состоянии Skm, то есть все m комплектов оборудования уже установлены, имеется только одно возможное управление: вводитьв эксплуатацию очередное здание.

Точки через которые проходят горизонтальные, вертикальные и наклонные линии, изображают состояния, в которых процесс может находиться при попадании на этап Тk или при в ходе выполнения данного этапа. Точка в пересечении вертикали kи горизонтали i означает состояние Ski . Исходным является состояние S*0=S 00, конечным состоянием S*n = Snm. Каждый вертикальный отрезок между двумя соседними состояниями соответствует установке комплекта оборудования ( в пределах этапа), горизонтальный - вводу в эксплуатацию здания (без установки оборудования), наклонный - вводу здания и установке оборудования одновременно.

Переход от состояния к состоянию возможен только в направлении вправо(r) , вверх (t) и по диагонали вправо вверх(d). Назовем эти переходы локальными управлениями. Два таких перехода (r и d) соответствуют управлениям: они переводят процесс на следующий этап. Переход t оставляет процесс на том же этапе, т.е. еще одним видом управления служат один или несколько последовательных переходов t, за которыми следует переход r и d. На этапе k=n-1 к управлению добавляются еще несколько переходов t, переводящих процесс в верхнее положение на последней вертикали Tn.

Предположим, что для каждого возможного перехода r,t и d из состояния Ski известна стоимость осуществеления такого перехода, т.е. стоимость осуществления соответственно ввода в эксплуатацию очередного здания, установки очередного комплекта оборудования или одновременного того и другого. Это означает , что каждому отрезку на рис , соединяющему два соседних состояния Ski, сопоставлено некоторое положительное число.

Геометрический выбор оптимального управления означет, что на чертеже требуется выбрать такой путь из вершины А в вершину Z , составленный из отрезков, пройденных в направлениях r,t или d, что сумма чисел, соответствующая пройденным отрезкам (суммарная стоимость осуществления процесса ) оказывается наименьшей из возможных. Если через fk обозначить сумму чисел на всех выбранных на этапе Tk переходах в направлении t и одного в направлении r или d, которые вместе определяют управление uk на k-ом этапе, то общая стоиммость f(u) составляет величину:

n-1

f(u) =  fk (uk)

k=0

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