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

Итерация 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 периода через