 |
 |
 |
 |
|
 |
 |
96
Обобщая изложенные схемы решения, можно прийти к выводу:
При использовании алгоритмов динамического программирования, если задано начальное состояние
управляемой системы, то задача решается в обратном направлении, а если конечное, тo
—
в
прямом.
Наконец, если заданы как начальное, так и конечное состояния, то задача существенно
усложняется. (В качестве компромисса в этом случае можно отказаться от оптимизации на первом или
последнем этапе.)
Продемонстрируем процесс решения задачи о найме работников на конкретном примере:
Для функционирования некоторого предприятия в течение четырех месяцев (нумеруемых от 1 до 4)
по нормам требуются следующие количества работников одинаковой квалификации:
причем перед началом первого месяца (в нулевом месяце) фактически имеется
?
0
=
2 сотрудников.
Администрация планирует в конце каждого месяца
k (кроме последнего) корректировать число
работающих на величину x
k
, k?0:4, х
4
=
0. На прием одного сотрудника необходимо затратить 9 у. е., а
на увольнение — 6 у. е. Предполагается, что расходы на содержание избыточного работника
составляют 8 у. е., а в случае нехватки персонала приходится нести затраты в размере 12 у. е. за каждое
вакантное место.
Требуется найти оптимальные значения приращений численности работающих в конце каждого из
первых трех месяцев, при которых суммарные издержки за весь рассматриваемый период будут
минимальными.
В начале решения запишем в аналитической форме функции издержек на прием-увольнение
сотрудников (и), а также на содержание ненормативного штата (g). С этой целью введем функции
Оценки эффективности управления на каждом шаге имеют вид:
Поскольку в поставленной задаче задано начальное условие
?
*
0
= 2, ее решение начинается с конца,
и, следовательно, будут применяться рекуррентные соотношения (5.17). С технической точки зрения
будет удобно на каждом шаге составлять две таблицы значений: функции издержек, получаемых
начиная с текущего шага в зависимости от текущего состояния и управления,
и функции минимальных издержек в зависимости от текущего состояния
Для сокращения объема табулируемых значений можно воспользоваться свойством выпуклости
функции
?
k
(x
k
, ?),
выте
кающим из выпуклости f и g. Из выпуклости функции
?
k
(x
k
, ?)
следует, что
заполнять таблицу ее значений необходимо лишь до тех пор, пока они уменьшаются, т. е. можно
остановиться, как только очередное значение оказывается больше предыдущего. Отметим, что
подобные приемы очень широко используются в динамическом программировании. Разумеется,
иллюстрируемые методы не рассчитаны на ручной счет, поскольку связаны с очень большим объемом