Примеры задач динамического программирования

 

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

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

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

 

 

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

 

 

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

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

 

 

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

 

 

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

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

 

 

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

 

 

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

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

 

 

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

 

 

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

 

 

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

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

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

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

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

 

 

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

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

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

 

 

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

 

 

 

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

 

 

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

 

 

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

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

 

 

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

 

 

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

 

 

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

 

 

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

 

 

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

 

 

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

 

 

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

 

 

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

 

 

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

 

 

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

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

 

 

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

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

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

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

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

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

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

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

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

 

 

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

 

 

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

 

 

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

 

 

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

 

 

поскольку

 

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

 

 

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

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

 

 

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

 

 

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

 

 

при условиях

 

 

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

 

 

где

 

 

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

 

где ξ = у_{k +1} = х_k + у_k - d_k .

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

 

 

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

 

 

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

 

 

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

 

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

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

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

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

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

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

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

 

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

 

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

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

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

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

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

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

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

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

работников.

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

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

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

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

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