ГЛАВА 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ : Математические методы исследования операций в экономике - П. Конюховский : Книги по праву, правоведение

ГЛАВА 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

1 2 3 4 5 6 7 8 9 10 11 12 
РЕКЛАМА
<

 

5.1. ОБЩАЯ СХЕМА МЕТОДОВ

ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

 

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

* Динамическое программирование как научное направление возник­ло и сформировалось в 1951-1953 гг. благодаря работам Р. Беллмана и его сотрудников.

 

Обычно методами динамического программирования опти­мизируют работу некоторых управляемых систем, эффект ко­торой оценивается аддитивной, или мультипликативной, целевой функцией. Аддитивной называется такая функция не­скольких переменных f(х1, x2, ...,хn), значение которой вычис­ляется как сумма некоторых функций fj, зависящих только от одной переменной хj:

 

 

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

 

 

Поскольку логарифм функции типа (5.2) является аддитив­ной функцией, достаточно ограничиться рассмотрением функций вида (5.1).

Изложим сущность вычислительного метода динамическо­го программирования на примере задачи оптимизации

 

 

при ограниченияx

 

 

Отметим, что в отличие от задач, рассмотренных в преды­дущих главах, о линейности и дифференцируемости функций fj(xj) не делается никаких предположений, поэтому примене­ние классических методов оптимизации (например, метода Лагранжа) для решения задачи (5.3)-(5.4) либо проблематично, либо просто невозможно.

Содержательно задача (5.3)-(5.4) может быть интерпрети­рована как проблема оптимального вложения некоторых ресур­сов j, приводимых к единой размерности (например, денег) с помощью коэффициентов aj, в различные активы (инвестици­онные проекты, предприятия и т. п.), характеризующиеся фун­кциями прибыли fj, т. е. такого распределения ограниченного объема ресурса (b), которое максимизирует суммарную прибыль. Представим ситуацию, когда она решается последова­тельно для каждого актива. Если на первом шаге принято реше­ние о вложении в n-й актив xn единиц, то на остальных шагах мы сможем распределить b-anxn единиц ресурса. Абстрагируясь от соображений, на основе которых принималось решение на первом шаге (допустим, мы по каким-либо причинам не могли на него повлиять), будет вполне естественным поступить так, чтобы на оставшихся шагах распределение текущего объе­ма ресурса произошло оптимально, что равнозначно реше­нию задачи

 

 

при ограничениях

 

 

Очевидно, что максимальное значение (5.5) зависит от размера распределяемого остатка, и если оставшееся количество ресур­са обозначить через ξ, то величину (5.5) можно выразить как функцию от ξ:

 

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

 

 

Если бы имелась возможность влиять на xn , то мы для получе­ния максимальной прибыли должны были бы максимизировать Ωn по переменной xn , т. е. найти Λn(b) и фактически решить задачу:

 

 

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

 

 

т. е. значению целевой функции при одномоментном распреде­лении ресурса.

Если в выражении (5.9) заменить значения b на ξ, и п на k, то его можно рассматривать как рекуррентную формулу, позво­ляющую последовательно вычислять оптимальные значения це­левой функции при распределении объема ресурса ξ за k шагов:

 

 

Значение переменной xk , при котором достигается рассмат­риваемый максимум, обозначим k (ξ).

При k = 1 формула (5.11) принимает вид

 

 

т. е. допускает непосредственное вычисление функций Λ1(ξ) и 1(ξ).

Воспользовавшись (5.12) как базой рекурсии, можно с помо­щью (5.11) последовательно вычислить Λk(ξ) и k(ξ), k2:n. Положив на последнем шаге ξ = b, в силу (5.9), найдем глобаль­ный максимум функции (5.3), равный Λn(b), и компоненту опти­мального плана хn* = n(b). Полученная компонента позволяет вычислить нераспределенный остаток на следующем шаге при оптимальном планировании: ξ= b – аnх*n , и, в свою очередь, най­ти х*n-1 = n-1(ξn-1). В результате подобных вычислений последо­вательно будут найдены все компоненты оптимального плана.

Таким образом, динамическое программирование представ­ляет собой целенаправленный перебор вариантов, который при­водит к нахождению глобального максимума. Уравнение (5.11), выражающее оптимальное решение на k-м шаге через решения, принятые на предыдущих шагах, называется основным рекур­рентным соотношением динамического программирова­ния. В то же время следует заметить, что описанная схема решения при столь общей постановке задачи имеет чисто тео­ретическое значение, так как замыкает вычислительный про­цесс на построение функций Λk(ξ) (k1:n), т. е. сводит исход­ную задачу (5.3)—(5.4) к другой весьма сложной проблеме. Однако при определенных условиях применение рекуррентных соотношений может оказаться весьма плодотворным. В первую очередь это относится к задачам, которые допускают таблич­ное задание функций Λk(ξ).

5.1.2. Задачи динамического программирования, до­пускающие табличное задание рекуррентных соотноше­ний. Рассмотрим процесс решения модифицированного вариан­та задачи (5.3)-(5.4), в котором переменные хj и параметры aj , b могут принимать только целочисленные значения, а ограничение (5.4) имеет вид равенства. В рамках предложенной в п. 5.1.1 ин­терпретации о вложении средств в активы данные предпосылки вполне реалистичны и, более того, могут быть даже усилены тре­бованием о кратности значений хj , например, 1000 единицам. 

Чтобы не усложнять обозначения, условимся операции це­лочисленной арифметики записывать стандартным образом, по­лагая, что промежуточные результаты подвергаются правиль­ному округлению. Так, например, будем считать, что 12/5=2.

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

 

 

Поскольку ξ≤b, x1 принимает конечное число целых значений от 0 до b/a1. Это позволяет, например, путем перебора значе­ний f1(x1) найти функцию Λ1(ξ) и задать ее в форме таблицы следующей структуры (табл. 5.1).

Последняя колонка табл. 5.1 (1(ξ)) содержит значение x1 , на котором достигается оптимальное решение первого шага. Его необходимо запоминать для того, чтобы к последнему шагу иметь значения всех компонент оптимального плана.

На следующем (втором) шаге можно приступить к вычисле­нию функции Λ2(ξ), значения которой для каждого отдельно взятого ξ 0: b находятся как

 

 

где значения

 

 

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

 

 

На последующих шагах с номером k (k2:(n-l)) осущест­вляются аналогичные действия, результатом которых стано­вятся таблицы значений Λk(ξ), где ξ {0, 1,..., b} (см. табл. 5.2).

 

 

На последнем n-ом шаге нет необходимости табулиро­вать функцию Λn(ξ), так как достаточно определить лишь Λn(b) = f(n(b)). Одновременно определяется и оптимальное значение n-й компоненты оптимального плана x*n = n(b). Далее, используя таблицу, сформированную на предыдущем шаге, определяем оптимальные значения остальных перемен­ных:

 

 

и т. д. или, в общем виде,

 

 

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

Выигрыш, который дает применение рассмотренного алго­ритма, может также быть оценен с помощью следующего про­стого примера. Сравним приблизительно по числу операций (состоящих, в основном, из вычислений целевой функции) опи­санный метод с прямым перебором допустимых планов задачи (5.3)-(5.4) при а1 = a2 = ...аn = 1.

Количество допустимых планов такой задачи совпадает с ко­личеством целочисленных решений уравнения

 

 

т. е. равно числу сочетаний с повторениями из n элементов по b. Следовательно, при простом переборе число возможных вари­антов составит

 

 

В случае применения метода динамического программирова­ния для вычисления таблицы значений функции Λk(ξ) при фик­сированном ξ необходимо выполнить (ξ+1) операций. Поэто­му для заполнения одной таблицы необходимо проделать

 

 

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

 

 

операций, что при больших n  и b существенно меньше, чем в первом случае. Например, если п = 6 и b = 30, то непосредствен­ный перебор потребует выполнения 324 632 операций, а метод динамического программирования — только 2511.

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

Перечислим основные требования к задачам, выполнение ко­торых позволяет применить данный подход:

 

объектом исследования должна служить управляемая сис­тема (объект) с заданными допустимыми состояниями и допустимыми управлениями;

 

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

 

задача не должна зависеть от количества шагов и быть опре­деленной на каждом из них;

 

состояние системы на каждом шаге должно описываться оди­наковым (по составу) набором параметров;

 

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

 

Рассмотрим вопросы применения модели динамического про­граммирования в обобщенном виде. Пусть стоит задача управ­ления некоторым абстрактным объектом, который может пре­бывать в различных состояниях. Текущее состояние объекта отождествляется с некоторым набором параметров, обознача­емым в дальнейшем ξ и именуемый вектором состояния. Пред­полагается, что задано множество Ξ всех возможных состоя­ний. Для объекта определено также множество допустимых управлений (управляющих воздействий) X, которое, не умаляя общности, можно считать числовым множеством. Управляю­щие воздействия могут осуществляться в дискретные моменты времени k(k1:n), причем управленческое решение заключа­ется в выборе одного из управлений xkХ. Планом задачи или стратегией управления называется вектор х = (х1, х2, .., xn-1), компонентами которого служат управления, выбранные на каждом шаге процесса. Ввиду предполагаемого отсутствия последействия между каждыми двумя последователь­ными состояниями объекта ξk и ξk+1 существует известная функциональная зависимость, включающая также выбранное управление: ξk+1 = φk(xk , ξk), k1:п-1. Тем самым задание на­чального состояния объекта ξ1Ξ и выбор плана х однозначно определяют траекторию поведения объекта, как это показа­но на рис. 5.1.

Эффективность управления на каждом шаге k зависит от текущего состояния ξk , выбранного управления xk и количе­ственно оценивается с помощью функций fk(хk, ξk), являющих­ся слагаемыми аддитивной целевой функции, характеризую­щей общую эффективность управления объектом. (Отметим, что в определение функции fk(хk, ξk) включается область до­пустимых значений хk , и эта область, как правило, зависит от текущего состояния ξk .) Оптимальное управление, при задан­ном начальном состоянии ξ1 , сводится к выбору такого опти­мального плана х*, при котором достигается максимум суммы значений fk на соответствующей траектории.

Основной принцип динамического программирования заклю­чается в том, что на каждом шаге следует стремиться не к изолированной оптимизации функции fk(хk, ξk), а выбирать

 

 

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

Обозначим Λk(ξ) максимальное значение суммы функций fk на протяжении шагов от k до п (получаемое при оптимальном управлении на данном отрезке процесса), при условии, что объект в начале шага k находится в состоянии ξ . Тогда функции Λk(ξ) должны удовлетворять рекуррентному соотношению:

 

 

где ξk+1 = φk(xk, ξ)

 

Соотношение (5.14) называют основным рекуррентным со­отношением динамического программирования. Оно реализу­ет базовый принцип динамического программирования, извест­ный также как принцип оптимальности Беллмана:

 

F Оптимальная стратегия управления должна удовлетворять следующему условию: каково бы ни было

начальное состо­яние ξk на k-м шаге и выбранное на этом шаге управле­ние хk,, последующие управления (управленческие реше­ния) должны быть оптимальными по отношению к состоянию ξk+1 = φk(xk, ξk), получающемуся в результа­те решения, принятого на шаге k.

 

Основное соотношение (5.14) позволяет найти функции Λk(ξ) только в сочетании с начальным условием, каковым в нашем случае является равенство

 

 

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

 

 

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

В то же время, говоря о динамическом программировании как о методе решения оптимизационных задач, необходимо отметить и его слабые стороны. Так, в предложенной схеме решения зада­чи (5.3)-(5.4) существенным образом используется тот факт, что система ограничений содержит только одно неравенство, и, как следствие, ее состояние задается одним числом — нераспре­деленным ресурсом ξ . При наличии нескольких ограничений со­стояние управляемого объекта на каждом шаге характеризуется уже набором параметров ξ1, ξ2, ..., ξm , и табулировать значения функций Λk (ξ1, ξ2, ..., ξm) необходимо для многократно больше­го количества точек. Последнее обстоятельство делает приме­нение метода динамического программирования явно нерацио­нальным или даже просто невозможным. Данную проблему его основоположник Р. Беллман эффектно назвал «проклятием многомерности». В настоящее время разработаны определенные пути преодоления указанных трудностей. Подробную информа­цию о них можно найти в специальной литературе [4, 5].

 

5.2. ПРИМЕРЫ ЗАДАЧ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

 

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

Одним из важнейших классов задач, для которых примене­ние динамического программирования оказывается плодотвор­ным, являются задачи последовательного принятия решений. Их особенностью является то, что искомые переменные х1, x2, .., хk ,... должны определяться в строгой временной по­следовательности и не должны меняться местами. В качестве примера опишем так называемую задачу о найме работников (задачу об использовании рабочей силы).

В данной задаче рассматривается некоторый экономиче­ский объект (фирма, магазин, завод и т. п.), функционирую­щий в течение конечного числа периодов, обозначаемых но­мерами k (k l:n). Каждый период k характеризуется нормативной потребностью в определенном количестве одно­типных работников mk. Тот же объем работ может быть вы­полнен другим количеством сотрудников ξk, что, однако, влечет дополнительные затраты либо за счет нерационально­го использования рабочей силы, либо ввиду повышения опла­ты за интенсивный труд. Размеры этих дополнительных издер­жек описываются функциями gk (ξk - mk), где (ξk - mk) — отклонение фактической численности работающих ξk , от пла­ново необходимой mk , причем gk (0)=0. Управленческое ре­шение на шаге k заключается в выборе величины изменения числа сотрудников хkZ, что однозначно определяет количе­ство работающих в течение следующего периода: ξk+1 = ξk+хk. Затраты по изменению количества работников (найму и уволь­нению) при переходе от периода k к периоду (k+1) задаются функцией uk (хk) , где также uk (0)=0. Тогда суммарные издер­жки, вызванные принятым на шаге k решением, характеризу­ются значением функции

 

 

План задачи (стратегия управления) х = (x1, ..., хn-1, 0) за­ключается в выборе поэтапных изменений количества работни­ков, а его суммарная эффективность описывается аддитивной функцией

 

 

На основе сформулированной модели ставится задача мини­мизации целевой функции (издержек) (5.15). Добавим, что по­становка задачи не будет корректной, если не задать начальное условие на количество работников. Существуют две модифика­ции данной задачи, определяемые типом начального условия: в первом случае задается исходное значение на первом этапе m1, а во втором — требуемое количество в n-м периоде mn .

Рассмотрим первый случай. Поскольку фиксированным яв­ляется начальное количество работников и, напротив, ничего не известно о том, каким это количество должно быть на послед­нем этапе, то рассмотрение процесса принятия решений удоб­нее начать с конца. Оптимальное управление на последнем эта­пе п по условию равно х*n = n(ξ)=0, поэтому минимальные издержки полностью определяются количеством работников в последнем периоде:

 

 

Для остальных предшествующих шагов основное рекуррент­ное соотношение примет вид

 

 

где Λk(ξ) — минимальные затраты с k-го по п-й периоды, в пред­положении, что количество работников в k-й период равно ξ. Точки л(ξ), в которых достигаются минимумы (5.17), опреде­ляют условное оптимальное управление на каждом шаге.

Последовательно определяя л(ξ) и дойдя до этапа 1, мы смо­жем найти безусловное оптимальное управление x1*  из того условия, что на начало первого периода численность работни­ков должна составлять ξ1* = m1 , a именно

 

 

Остальные компоненты оптимального плана хk* и состояния ξk*, образующие оптимальную траекторию, последовательно находятся по рекуррентным формулам

 

 

после чего не составляет труда вычислить оптимальное значе­ние целевой функции (5.15).

Остановимся теперь на втором случае, когда задано фи­нальное состояние управляемого объекта, т. е. желаемое коли­чество работников на последнем периоде ξn*= mn . Очевидно, что в данной ситуации следует поступить с точностью «до наобо­рот» и рассмотреть процесс принятия решений от начала к кон­цу. Наилучшее условное управление на первом шаге 1(ξ) будет найдено в процессе вычисления функции

 

 

где состояние ξ ≥0 является возможным количеством работ­ников на начальном шаге. Соответственно, основное рекуррент­ное соотношение выразит минимальные издержки вплоть до k-го периода через таковые для предыдущих периодов (с перво­го по (k-1)-й) при условии, что численность работников в k-й период будет равна ξ:

 

 

Попутно будут найдены функции k(ξ), k2:n, определяю­щие условные оптимальные управления. На последнем перио­де, в силу начального условия, ξn*= mn. Отсюда путем последо­вательного решения рекуррентных уравнений могут быть найдены оптимальные численности работников ξ*k  и безуслов­ные оптимальные управления:

 

 

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

Обобщая изложенные схемы решения, можно прийти к вы­воду:

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

Продемонстрируем процесс решения задачи о найме работ­ников на конкретном примере:

Для функционирования некоторого предприятия в течение четырех месяцев (нумеруемых от 1 до 4) по нормам требуются следующие количества работников одинаковой квалификации:

 

 

причем перед началом первого месяца (в нулевом месяце) фак­тически имеется ξ0 = 2 сотрудников. Администрация планирует в конце каждого месяца k (кроме последнего) корректировать число работающих на величину xk , k0:4, х4 = 0. На прием одного сотрудника необходимо затратить 9 у. е., а на увольне­ние — 6 у. е. Предполагается, что расходы на содержание избы­точного работника составляют 8 у. е., а в случае нехватки персо­нала приходится нести затраты в размере 12 у. е. за каждое вакантное место.

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

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

 

 

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

 

 

Поскольку в поставленной задаче задано начальное условие ξ*0 = 2, ее решение начинается с конца, и, следовательно, будут применяться рекуррентные соотношения (5.17). С технической точки зрения будет удобно на каждом шаге составлять две табли­цы значений: функции издержек, получаемых начиная с текуще­го шага в зависимости от текущего состояния и управления,

 

 

и функции минимальных издержек в зависимости от текущего состояния

 

 

Для сокращения объема табулируемых значений можно вос­пользоваться свойством выпуклости функции Ωk (xk , ξ), выте­кающим из выпуклости f и g. Из выпуклости функции Ωk (xk , ξ) следует, что заполнять таблицу ее значений необходимо лишь до тех пор, пока они уменьшаются, т. е. можно остановиться, как только очередное значение оказывается больше предыду­щего. Отметим, что подобные приемы очень широко использу­ются в динамическом программировании. Разумеется, иллюст­рируемые методы не рассчитаны на ручной счет, поскольку связаны с очень большим объемом рутинных вычислений. Ради краткости ниже приведены только фрагменты таблиц, содержа­щие интересующие нас значения.

Итерация 1. Полагаем k=4. На данном этапе функция со­стояния Λ4(ξ) может быть найдена непосредственно, если учесть, что x4*=0 и u(0)=0:

 

 

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

 

 

Итерация 2. Полагаем k=3. Предварительно заполним таб­лицу значений функции Ω3 (x3, ξ) для достаточно большого множества аргументов согласно формуле:

 

 

Выбирая минимальные по х3 значения Ω3 (x3 , ξ) составим таблицу Λ3(ξ) и соответствующие значения условных опти­мальных управлений 3(ξ):

 

 

Итерация 3. Полагаем k=2. Так же, как на предыдущей итерации, заполним таблицу значений функции Ω2 (x2 , ξ) со­гласно формуле:

 

 

Выбирая минимальные по х2  значения Ω2 (x2 , ξ), составим таблицу Λ1(ξ) и соответствующие значения условных опти­мальных управлений 2(ξ):

 

 

Итерация 4. Полагаем k=1. Аналогично предыдущему, за­полним таблицу значений функции Ω1 (x1 , ξ) согласно формуле:

 

 

Выбирая минимальные по х1, значения Ω1 (x1 , ξ), составим таблицу Λ1(ξ) и соответствующие значения условных опти­мальных управлений 1(ξ):

 

 

Итерация 5. На последней итерации, в связи с наличием на­чального условия ξ*0 = 2, достаточно вычислить

 

 

и найти 0(2) как точку минимума Ω0 (x0 , 2) . Простые вычисле­ния показывают, что минимум

 

 

достигается при x0(2) = 1.

Следовательно, x*0 = 0(2)=1, после чего обратным ходом последовательно вычисляются оптимальные управления и оп­тимальные состояния (оптимальная траектория):

 

 

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

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

Пусть имеется некоторая система снабжения (склад, опто­вая база и т. п.), планирующая свою работу на п периодов. Ее деятельность сводится к обеспечению спроса конечных потре­бителей на некоторый продукт, для чего она осуществляет за­казы производителю данного продукта. Спрос клиентов (конеч­ных потребителей) в данной модели рассматривается как некоторая интегрированная величина, принимающая заданные значения для каждого из периодов, и он должен всегда удов­летворяться (т. е. не допускаются задолженности и отказы). Также предполагается, что заказ, посылаемый производителю, удовлетворяется им полностью, и временем между заказом и его выполнением можно пренебречь (т. е. рассматривается сис­тема с мгновенным выполнением заказа). Введем обозначения:

yk — остаток запаса после (k-1)-го периода;

dk — заранее известный суммарный спрос в k-м периоде;

хk — заказ (поставка от производителя) в k-м периоде;

сk (хk) —затраты на выполнение заказа объема xk в k-м пери­оде;

sk (ξk) — затраты на хранение запаса объема ξk в k-м пери­оде.

После получения поставки и удовлетворения спроса объем товара, подлежащего хранению в период k, составит ξk = yk + хk - dk . Учитывая смысл параметра yk , можно записать соот­ношение:

 

 

Расходы на получение и хранение товара в период k описыва­ются функцией

 

 

Планом задачи можно считать вектор х = (х1, х2, ..., хn), ком­понентами которого являются последовательные заказы в течение рассматриваемого промежутка времени. Соотношение между запасами (5.24) в сочетании с некоторым начальным условием связывает состояния системы с выбранным планом и позволяет выразить суммарные расходы за все п периодов функционирования управляемой системы снабжения в форме аддитивной целевой функции:

 

 

Естественной в рамках сформулированной модели представля­ется задача нахождения последовательности оптимальных управлений (заказов) x*k и связанных с ними оптимальных состояний (запасов) ξ*k , которые обращают в минимум (5.25). В качестве начального условия используем требование о со­хранении после завершения управления заданного количест­ва товара yn+1 , а именно

 

 

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

 

 

поскольку

 

Система рекуррентных соотношений (5.27)-(5.28) позво­ляет найти последовательность функций состояния Λ1(ξ), Λ2(ξ), …, Λn(ξ) и условных оптимальных управлений 1(ξ), 2(ξ), …, n(ξ). На n-м шаге с помощью начального условия (5.26) можно определить х*n = n (yn+1). Остальные значения оп­тимальных управлений x*k определяются по формуле:

 

 

Особый интерес представляет частный случай задачи (5.24)-(5.25), при котором предполагается, что функции за­трат на пополнение запаса сk(хk) являются вогнутыми по хk , а функции затрат на хранение sk(ξk) являются линейными отно­сительно объема хранимого запаса, т. е. sk(ξk) = skξk . Парал­лельно заметим, что обе предпосылки являются достаточно ре­алистичными.

Обозначим функцию затрат в течение k-ro периода через

 

 

или, что то же самое,

 

 

В силу сделанных предположений все функции затрат fk (xk , yk+1) являются вогнутыми (как суммы вогнутой и линей­ной функций). Данное свойство значительно упрощает процесс решения, так как для поиска минимума вогнутых функций fk (xk , yk+1) достаточно рассмотреть только две крайние точки множества, на котором отыскивается минимум. С учетом вве­денного обозначения задачу (5.24)-(5.25) можно записать в виде:

 

 

при условиях

 

 

Рассмотрим процедуру решения (5.32)-(5.33). Так как ищет­ся минимум суммы вогнутых функций fk(xk , yk+1), то решение будет достигаться на одной из крайних точек множества, опре­деляемого условиями (5.33). Общее число переменных xk  и yk в системе (5.33) равно 2п. Однако, учитывая то, что в ней толь­ко п уравнений, в оптимальном плане будет не более п ненуле­вых компонент, причем для каждого периода k значения xk и yk  не могут равняться нулю одновременно (в силу необходимости удовлетворения спроса либо за счет заказа, либо за счет запа­са). Формально это утверждение можно представить в виде ус­ловия дополняющей нежесткости:

 

 

где

 

 

С точки зрения содержательной интерпретации условия (5.34)-(5.35) означают, что при оптимальном управлении за­каз поставщику на новую партию не должен поступать, если в начале периода имеется ненулевой запас, или размер заказа должен равняться величине спроса за целое число периодов. Отсюда следует, что запас на конец последнего периода должен равняться нулю: у*n+1=0. Последнее позволяет решать задачу в прямом направлении, применяя рекуррентное соотношение

 

 

где ξ = уk+1= хk + уk  - dk .

Учитывая (5.34)-(5.35) и вогнутость fk (xk, ξ), заключаем, что минимум (5.36) достигается в одной из крайних точек xk =0 или xk = ξ + dk  поэтому

 

 

тогда для предыдущего периода функция состояния может быть выражена как

 

 

на oснове чего в общем виде получаем модифицированную фор­му для рекуррентного соотношения

 

 

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

 

КЛЮЧЕВЫЕ ПОНЯТИЯ

 

Аддитивная и мультипликативная функция.

Рекуррентное соотношения.

Принцип оптимальности Беллмана.

Отсутствие последействия.

Задача о найме работников.

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

 

КОНТРОЛЬНЫЕ ВОПРОСЫ

 

5.1. Для решения каких задач предназначен метод динамичес­кого программирования?

5.2. В чем заключена суть метода динамического программи­рования?

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

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

5.4. Какие трудности связаны с вычислительными алгоритма­ми динамического программирования?

5.5. Что определяет направление решения задачи в алгорит­мах динамического программирования?

5.6. Сформулируйте математическую модель для задачи о най­ме работников.

5.7. Выпишите основное рекуррентное соотношение, исполь­зуемое при решении задачи о найме

       работников.

5.8. С какими особенностями задач управления запасами свя­зано применение при их решении

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

5.9. Какой вид имеет целевая функция в динамической задаче управления запасами?

5.10. Выпишите основное рекуррентное соотношение, исполь­зуемое при решении динамической

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