Математические методы исследования операций в экономике (стр. 31 из 37)

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

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 , ξ)следует, что заполнять таблицу ее значений необходимо лишь до тех пор, пока они уменьшаются, т. е. можно остановиться, как только очередное значение оказывается больше предыдущего. Отметим, что подобные приемы очень широко используются в динамическом программировании. Разумеется, иллюстрируемые методы не рассчитаны на ручной счет, поскольку связаны с очень большим объемом рутинных вычислений. Радикраткости ниже приведены только фрагменты таблиц, содержащие интересующие нас значения.