Классификация математических моделей, используемых в экономике и менеджменте
Если же некоторая часть дохода участвует в дальнейшем распределении в каком-нибудь году, то к правой части равенства (4.2) прибавляется соответствующая величина.
Требуется
определить
ns
неотрицательных
переменных
,
удовлетворяющих
условиям (4.2) и
максимизирующих
функцию (4.1).
Вычислительная
процедура ДП
начинается
с введения
функции
,
обозначающей
доход, полученный
за п—k+1
лет,
начиная с k-го
года
до конца рассматриваемого
периода, при
оптимальном
распределении
средств между
s
предприятиями,
если в k-м
году
распределялось
средств.
Функции
для k=1,
2,
...n-1
удовлетворяют
функциональным
уравнениям
(2.2), которые запишутся
в виде:
(4.3)
При k=n согласно (2.2) получаем
(4.4)
Далее
необходимо
последовательно
решить уравнения
(4.4) и (4.3) для всех
возможных
(k
= n—1,
п—2,
1). Каждое из этих
уравнений
представляет
собой задачу
на оптимизацию
функции, зависящей
от s
переменных.
Таким образом,
задача с ns
переменными
сведена к
последовательности
п
задач,
каждая из которых
содержит s
переменных.
В этой общей
постановке
задача по-прежнему
сложна (из-за
многомерности)
и упростить
ее, рассматривая
как ns-шаговую
задачу, в данном
случае нельзя.
В самом деле,
попробуем это
сделать. Пронумеруем
шаги по номерам
предприятий
сначала в 1-м
году, затем во
2-м и т. д.:

и
будем пользоваться
одним параметром
для характристики
остатка средств.
В
течение k-го
года
состояние
'
к началу любого
шага s(k-1)_+i
(i=1,2,…,s)
определится
по предыдущему
состоянию
с
помощью простого
уравнения
![]()
.
Однако
по истечении
года, т.е. к началу
следующего
года, к наличным
средствам
необходимо
будет добавить
средств
и, следовательно,
состояние
в начале (ks+1)-гo
шага
будет зависеть
не только от
предшествующего
ks-гo
состояния,
но и от всех s
состояний и
управлений
за прошлый год.
В результате
мы получим
процесс с
последействием.
Чтобы исключить
последействие,
приходится
вводить несколько
параметров
состояний;
задача на каждом
шаге остается
по-прежнему
сложной из-за
многомерности.
Задача
2.
Планируется
деятельность
двух предприятий
(s=2)
в течение п
лет.
Начальные
средства составляют
.
Средства х,
вложенные
в предприятие
I, приносят к
концу года
доход f1(x)
и
возвращаются
в размере
аналогично,
средства х,
вложенные
в предприятие
II, дают доход
f2(x)
и
возвращаются
в размере
.
По истечении
года все оставшиеся
средства заново
перераспределяются
между предприятиями
I и II, новых средств
не поступает
и доход в производство
не вкладывается.
Требуется найти оптимальный способ распределения имеющихся средств.
Будем
рассматривать
процесс распределения
средств как
n-шаговый,
в котором номер
шага соответствует
номеру года.
Управляемая
система — два
предприятия
с вложенными
в них средствами.
Система характеризуется
одним параметром
состояния
—количеством
средств, которые
следует перераспределить
в начале k-гo
года.
Переменных
управления
на каждом шаге
две:
—
количество
средств, выделенных
соответственно
предприятию
I и II. Так как средства
ежегодно
перераспределяются
полностью, то
).
Для
каждого шага
задача становится
одномерной.
Обозначим
через
,
тогда
![]()
Показатель
эффективности
k-гo
шага
равен
.
Это
— доход, полученный
от двух предприятий
в течение k-гo
года.
Показатель эффективности задачи — доход, полученный от двух предприятий в течение п лет — составляет
(4.5)
Уравнение
состояния
выражает остаток
средств
после
k-гo
шага
и имеет вид
(4.6)
Пусть
—условный
оптимальный
доход, полученный
от распределения
средств
между
двумя предприятиями
за n—k+1
лет,
начиная с k-гo
года
до конца рассматриваемого
периода. Запишем
рекуррентные
соотношения
для этих функций:
(4.7)
![]()
где
- определяется
из уравнения
состояния
(4.6).
При
дискретном
вложении ресурсов
может возникнуть
вопрос о выборе
шага Δх
в изменении
переменных
управления.
Этот шаг может
быть задан или
определяется
исходя из требуемой
точности вычислений
и точности
исходных данных.
В общем случае
эта задача
сложна, требует
интерполирования
по таблицам
на
предыдущих
шагах вычисления.
Иногда предварительный
анализ уравнения
состояния
позволяет
выбрать подходящий
шаг Δх,
а также установить
предельные
значения
,
для которых
на каждом шаге
нужно выполнить
табулирование.
Рассмотрим двумерную задачу, аналогичную предыдущей, в которой строится дискретная модель ДП процесса распределения ресурсов.
Задача 3. Составить оптимальный план ежегодного распределения средств между двумя предприятиями в течение трехлетнего планового периода при следующихусловиях:
1) начальная сумма составляет 400;
2) вложенные средства в размере х приносят на предприятии I доход f1(x) и возвращаются в размере 60% от х, а на предприятии II — соответственно f2(x) и 20%;
3) ежегодно распределяются все наличные средства, получаемые из возвращенных средств:
4) функции f1(x) и f2(x)заданы в табл. 1:

Модель динамического программирования данной задачи аналогична модели, составленной в задаче 1.
Процесс
управления
является трехшаговым.
Параметр
—
средства, подлежащие
распределению
в k-м
году
(k=l,
2, 3).
Переменная
управления
—
средства, вложенные
в предприятие
I в k-м
году.
Средства, вложенные
в предприятие
II в k-м
году,
составляют
Следовательно,
процесс управления
на k-м
шаге
зависит от
одного параметра
(модель
одномерная).
Уравнение
состояния
запишется в
виде
(4.8)
А функциональные уравнения в виде
(4.9)
(4.10)
Попытаемся
определить
максимально
возможные
значения, для
которых необходимо
проводить
табулирование
на k-м
шаге
(k=l,
2,
3). При
=400
из уравнения
(4.8) определяем
максимально
возможное
значение
имеем
=
0,6*400=2400 (все средства
вкладываются
в предприятие
I). Аналогично,
для
получаем предельное
значение 0,6*240 =
144. Пусть интервал
изменения
совпадает с
табличным, т.
е. Δх
=50. Составим таблицу
суммарной
прибыли на
данном шаге:
![]()
Это
облегчит дальнейшие
расчеты. Так
как
то клетки,
расположенные
по диагонали
таблицы, отвечают
одному и тому
же значению
,
указанному
в 1-й строке (в
1-м столбце) табл.
2. Во 2-й строке
таблицы записаны
значения f1(x),
а
во 2-м столбце
— значения
f2(у)взятые
из табл. 1.Значения
в остальных
клетках таблицы
получены сложением
чисел f1(x)
и
f2(у),стоящих
во 2-й строке и
во 2-м столбце
и соответствующих
столбцу и строке,
на пересечении
которых находится
данная клетка.
Например, для
=150
получаем ряд
чисел: 20 —для
х
= 0,
у=150;
18 —для х=50, у=100; 18—
для х—100,
у=50;
15 — для х= 150, у=0.
Проведем условную оптимизацию по обычной схеме. 3-й шаг. Основное уравнение (4.9)
![]()
Как
указывалось
выше,
.
Просмотрим
числа на диагоналях,
соответствующих
=0;
50; 100; 150 и на каждой
диагонали
выберем наибольшее.
Это и есть
В 1-й строке находим
соответствующее
условное оптимальное
управление.
Данные оптимизации
на 3-м шаге поместим
в основную
таблицу (табл.
4). В ней введен
столбец Δх,
который
в дальнейшем
используется
при интерполяции.
Оптимизация 2-го шага проведена в табл. 5 согласно уравнению вида (4.10):
![]()
При этом может быть получен максимальный доход, равный Zmax=99,l. Прямой подсчет дохода по табл. 2 для найденного оптимального управления дает 97,2. Расхождение в результатах на 1,9 (около 2%) объясняется ошибкой линейной интерполяции.
Мы рассмотрели несколько вариантов задачи оптимального распределения ресурсов. Существуют другие варианты этой задачи, особенности которых учитываются соответствующей динамической моделью.
2.2.5 Оптимальное управление запасами
Класс задач, в которых рассматривается оптимальное управление Запасами, является наиболее характерным для динамического программирования. Это обусловлено тем, что в задачах управления запасами процесс естественно разворачивается во времени, причем управление как раз и заключается в том, что решение на данном промежутке времени принимается с учетом того состояния, к которому пришла система за предшествующие периоды времени. Кроме того, эти задачи связаны, как правило, с дискретным характером переменных и, следовательно, решаются довольно сложно другими методами. Наконец, весьма важным обстоятельством является то, что форма зависимостей задачи для каждого периода времени является довольно простой (часто — линейной), что облегчает решение частной задачи оптимизации на каждом шаге, в то время как единовременное решение общей задачи с большим числом переменных (для многих промежутков времени и кусочно-линейной или нелинейной целевой функцией для всего процесса) является достаточно сложным.
Проблема управления запасами является одной из важнейших областей практического приложения экономико-математических методов, в том числе методов математического программирования. Мы ограничимся анализом некоторых простейших задач с целью иллюстрации их решения методами динамического программирования.
При формулировке задач управления запасами используют такие понятия.
Запасы — это любые денежные или материальные ценности, которые периодически пополняются (производятся, доставляются и т. д.) и некоторое время сохраняются с целью расходования их в последующие промежутки времени. Уровень запасов в любой момент времени определяется начальным уровнем запасов плюс пополнение и минус расход за промежуток времени от начального момента до данного.
Управление запасами в общем случае состоит в воздействии на соотношение между двумя основными факторами— пополнением и расходом. Цель управления — оптимизация некоторого критерия, зависящего от расходов на хранение запасов, стоимости поставок, затрат, связанных с пополнением, штрафов и т. д.
В такой общей постановке подобные задачи могут иметь самое разнообразное практическое применение. Например, под запасами можно понимать продукцию предприятия, которая производится непрерывно (пополнение) и отгружается потребителям определенными дискретными партиями (расход). При этом спрос на продукцию предполагается наперед заданным (детерминированный спрос) или подверженным случайным колебаниям (стохастическая задача). Управление запасами состоит в определении, размеров необходимого выпуска продукции для удовлетворения заданного спроса. Цель — минимизация суммарных затрат на хранение и пополнение запасов. Под запасами можно понимать запасы сырья или других материалов, поставляемых дискретными партиями (пополнение) и должных обеспечить непрерывное потребление в процессе производства (расход). Критерием оптимальности могут служить суммарные затраты на хранение запасов, замораживание оборотных средств и поставки запасов.
Запасами могут быть товары, поставляемые в магазин определенными партиями и предназначенные для удовлетворения непрерывного, но подверженного случайным колебаниям покупательского спроса. Критерий оптимальности — суммарные затраты на поставки, хранение запасов и изменение производственного ритма в связи с вариациями спроса.
Запасами могут быть и сезонные товары, сохраняющиеся на складе ограниченной емкости. Товары можно покупать и продавать в различных количествах по ценам, меняющимся во времени. Задача состоит в определении политики покупок и продаж, обеспечивающих максимум суммарной прибыли, и является примером задачи складирования.
Число таких примеров можно было бы умножить. Однако в настоящем параграфе мы рассмотрим лишь некоторые простейшие динамические модели задач управления запасами.
Если в задаче исходные данные определены однозначно, то задачи называются детерминированными; если же хотя бы часть данных носит случайный характер и заданы распределения вероятностей, то соответствующие задачи называются стохастическими. В этой главе мы ограничимся примерами детерминированных задач управления запасами.
Рассмотрим модель задачи управления запасами при заданном расходе. Управление в этих задачах будет сводиться к пополнению.
Задача 1. Планируемый период разделен на n промежутков времени (дни, месяцы, кварталы и т. д.), в которых задан расход dk (k=l, 2, ..., п), производимый в конце каждого из промежутков. Известны начальный уровень запасов и зависимость суммарных затрат на хранение и пополнение запасов в данном периоде от среднего уровня хранимых запасов и их пополнения.
Требуется определить размеры пополнения запасов в каждом промежутке времени для удовлетворения заданного расхода из условия минимизации суммарных затрат за весь планируемый период времени.
Составим
математическую
модель задачи.
Обозначим
размер пополнения
запасов в k-м
промежутке
времени через
xk,
а
уровень запасов
в начале этого
промежутка
(после произведенного
расхода) — через
-Согласно
условию, суммарные
затраты в k-м
промежутке
зависят от xk
и
— среднего
уровня запасов
в k-м
промежутке,
равного
(5.1)
Следовательно,
затраты в k-м
промежутке
можно рассматривать
как функцию
![]()
Целевая функция задачи — суммарные затраты — запишется в виде
(5.2)
Требуется
определить
переменные
xk,
которые
связаны с переменными
балансовыми
уравнениями
(5.3)
выражающими
уровень запаса
в начале (k+1)-гo
промежутка
через сумму
уровня запасов
в начале k-гo
промежутка
и
пополнения
запасов в этом
промежутке
xk
минус
расход dk.
Ставится задача — найти совокупность п переменных xk, удовлетворяющих ограничениям (5.3) — (5.5) и минимизирующих функцию (5.2).
Подобные
задачи при
большом числе
переменных
и нелинейности
функций
другими
методами
математического
программирования
решаются сложно.
Особенно сложным
становится
решение, когда
на переменные
xk
налагаются
условия целочисленности
(или в общем
случае — дискретности),
как это часто
бывает.
Дадим
описание динамической
модели задачи.
Будем рассматривать
n-шаговый
процесс оптимизации
с параметрами
состояния
и
переменными
управлениями
xk.
Тогда
равенство (5.3)
представляет
собой уравнение
состояния.
Здесь удобнее
использовать
прямую схему
расчета, так
как задано
конечное состояние.
В задачах управления запасами чаще всего возникает именно такая ситуация, поэтому продемонстрируем построение прямой схемы вычислений.
Обозначим
через
)
условные оптимальные
затраты за
промежутки,
начиная с 1-го
до k-гo
включительно,
если в конце
k-гo
промежутка
уровень запасов
равен
.
Начинаем с условной оптимизации 1-го шага в предположении, что к концу этого шага система окажется в состоянии
(5.6)
На k-м шаге получим соответственно
(5.7)
В соответствии с формой рекуррентных соотношений удобно и уравнение состояния (5.3) записать в виде
(5.8)
При
решении локальных
задач в соответствии
с уравнениями
(5.6) и (5.7) будем считать,
что состояние
в
конце шага
известно. Поэтому
и неравенство
(5.4) удобно записать
для
т.
е. в виде
,
откуда
следуют ограничения
на xh: