Примеры задач динамического программирования
⇐ ПредыдущаяСтр 4 из 4 Задача о найме работников. Рассмотрим вопросы применения методов динамического программирования в конкретных экономико-математических моделях. Отдельно отметим, что данные вычислительные схемы, вообще говоря, достаточно часто используются для решения конкретных задач: задача о ранце, задача о кратчайшем пути, задачи транспортного типа. Одним из важнейших классов задач, для которых применение динамического программирования оказывается плодотворным, являются задачи последовательного принятия решений. Их особенностью является то, что искомые переменные В данной задаче рассматривается некоторый экономический объект (фирма, магазин, завод и т. п.), функционирующий в течение конечного числа периодов, обозначаемых номерами k
План задачи (стратегия управления)
На основе сформулированной модели ставится задача минимизации целевой функции (издержек) (15). Причём постановка задачи не будет корректной, если не задать начальное условие на количество работников. Существуют две модификации данной задачи, определяемые типом начального условия: в первом случае задается исходное значение на первом этапе Рассмотрим первый случай. Поскольку фиксированным является начальное количество работников и, напротив, ничего не известно о том, каким это количество должно быть на последнем этапе, то рассмотрение процесса принятия решений удобнее начать с конца. Оптимальное управление на последнем этапе п по условию равно
Для остальных предшествующих шагов основное рекуррентное соотношение примет вид
где Последовательно определяя Остальные компоненты оптимального плана
после чего не составляет труда вычислить оптимальное значение целевой функции (15).
Остановимся теперь на втором случае, когда задано финальное состояние управляемого объекта, т. е. желаемое количество работников на последнем периоде
где состояние
Одновременно будут найдены функции
В заключение, как и в первом случае, подсчитывается минимальная величина издержек. Обобщая изложенные схемы решения, приходим к выводу: При использовании алгоритмов динамического программирования, если задано начальное состояние управляемой системы, то задача решается в обратном направлении, а если конечное, то - в прямом. Наконец, если заданы как начальное, так и конечное состояния, то задача существенно усложняется. (В качестве компромисса в этом случае можно отказаться от оптимизации на первом или последнем этапе.) Продемонстрируем процесс решения задачи о найме работников на конкретном примере: Для функционирования некоторого предприятия в течение четырех месяцев (нумеруемых от 1 до 4) по нормам требуются следующие количества работников одинаковой квалификации: причем перед началом первого месяца (в нулевом месяце) фактически имеется
Требуется найти оптимальные значения приращений численности работающих в конце каждого из первых трех месяцев, при которых суммарные издержки за весь рассматриваемый период будут минимальными. В начале решения запишем в аналитической форме функции издержек на прием-увольнение сотрудников (и), а также на содержание ненормативного штата (g). С этой целью введем функции
Оценки эффективности управления на каждом шаге имеют вид:
Поскольку в поставленной задаче задано начальное условие
и функции минимальных издержек в зависимости от текущего состояния
Для сокращения объема табулируемых значений можно воспользоваться свойством выпуклости функции Итерация 1. Полагаем Таблица значений данной функции и условные оптимальные управления имеют вид
Итерация 2. Полагаем
Выбирая минимальные по
Итерация 3. Полагаем
Выбирая минимальные по
Итерация 4. Полагаем
Выбирая минимальные по
Итерация 5. На последней итерации, в связи с наличием начального условия и найти достигается при
Таким образом, результаты расчета свидетельствуют, что при заданной системе расценок в третьем месяце выгоднее не брать 5-го работника, а компенсировать его отсутствие дополнительными выплатами за сверхурочную работу имеющимся сотрудникам.
Динамические задачи управления запасами. Одной из наиболее известных сфер приложения методов динамического программирования является такая область математической экономики, как теория управления запасами. Ее предметом является разработка и исследование математических моделей систем, занимающих промежуточное положение между источниками (производителями) тех или иных ресурсов и их потребителями. При математической формализации процессов управления запасами очень часто приходится использовать скачкообразные, недифференцируемые и кусочно-непрерывные функции. Как правило, это обусловливается необходимостью учета эффектов концентрации, фиксированных затрат и платы за заказ. В связи с этим получаемые задачи с трудом поддаются аналитическому решению классическими методами, однако могут быть успешно решены с помощью аппарата динамического программирования. Рассмотрим достаточно типичную задачу, возникающую в процессе планирования деятельности системы снабжения, - так называемую динамическую задачу управления запасами.
Пусть имеется некоторая система снабжения (склад, оптовая база и т. п.), планирующая свою работу на п периодов. Ее деятельность сводится к обеспечению спроса конечных потребителей на некоторый продукт, для чего она осуществляет заказы производителю данного продукта. Спрос клиентов (конечных потребителей) в данной модели рассматривается как некоторая интегрированная величина, принимающая заданные значения для каждого из периодов, и он должен всегда удовлетворяться (т. е. не допускаются задолженности и отказы). Также предполагается, что заказ, посылаемый производителю, удовлетворяется им полностью, и временем между заказом и его выполнением можно пренебречь (т. е. рассматривается система с мгновенным выполнением заказа). Введем обозначения:
После получения поставки и удовлетворения спроса объем товара, подлежащего хранению в период k, составит
Расходы на получение и хранение товара в период k описываются функцией
Планом задачи можно считать вектор
Естественной в рамках сформулированной модели представляется задача нахождения последовательности оптимальных управлений (заказов)
При решении поставленной задачи методом динамического программирования в качестве функции состояния управляемой системы
так как
Система рекуррентных соотношений (27)-(28) позволяет найти последовательность функций состояния
Особый интерес представляет частный случай задачи (24)- (25), при котором предполагается, что функции затрат на пополнение запаса
или, что то же самое,
В силу сделанных предположений все функции затрат
при условиях
Рассмотрим процедуру решения (32)-(33). Так как ищется минимум суммы вогнутых функций
где
С точки зрения содержательной интерпретации условия (34)-(35) означают, что при оптимальном управлении заказ поставщику на новую партию не должен поступать, если в начале периода имеется ненулевой запас, или размер заказа должен равняться величине спроса за целое число периодов. Отсюда следует, что запас на конец последнего периода должен равняться нулю:
где Учитывая (34)-(35) и вогнутость
тогда для предыдущего периода функция состояния может быть выражена в виде
Следовательно, в общем виде получаем модифицированную форму для рекуррентного соотношения
При дальнейших конкретизирующих предположениях о виде функций
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|