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

Введение

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

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

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

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

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

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

  

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

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

 

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

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

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

Размеры этих дополнительных издержек описываются функциями  gk (ξk - mk), где (ξk - mk) — отклонение фактической численности работающих ξk , от планово необходимой mk , причем gk (0)=0. Управленческое решение на шаге k заключается в выборе величины изменения числа сотрудников хk∊Z, что однозначно определяет количество работающих в течение следующего периода: ξ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(ξ), k∊2:n, определяющие условные оптимальные управления. На последнем периоде, в силу начального условия, ξn*= mn. Отсюда путем последовательного решения рекуррентных уравнений могут быть найдены оптимальные численности работников ξ*k и безусловные оптимальные управления:

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

Обобщая изложенные схемы решения

 

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

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

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

причем перед началом  первого месяца (в нулевом месяце) фактически имеется ξ0 = 2 сотрудников. Администрация планирует в конце  каждого месяца k (кроме последнего) корректировать число работающих на величину xk , k∊0: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-го работника, а  компенсировать его отсутствие дополнительными  выплатами за сверхурочную работу имеющимся  сотрудникам.