Модели управления запасами

Важной областью применения методов динамического программирования являются задачи управления запасами. В главах 11 и 16 рассмотрены некоторые задачи этого класса, при этом в главе 11 рассматриваются детерминированные модели, а в главе 16 — стохастические.

4.5. Проблема размерности

Во всех рассмотренных выше задачах динамического программирования состояние системы на любом этапе описывалось единственной переменной. Например, в задаче о загрузке (раздел 10.4.1) вес предмета является единственным ограничением, которое учитывается при его погрузке. Вместе с этим объем судна также может быть ограничительной величиной. В этом случае говорят, что состояние системы является двухмерным, так как формируется двумя переменными: весом и объемом.

Увеличение числа переменных состояния системы влечет за собой увеличение объема вычислений на каждом этапе. Особенно это заметно в моделях динамического программирования при вычислениях с использованием таблиц, так как количество строк каждой таблицы должно соответствовать всем возможным комбинациям значений переменных состояния. Эти вычислительные трудности настолько значительны в динамическом программировании, что в литературе на них ссылаются как на проклятие размерности.

Следующий пример приводится для иллюстрации проклятия размерности. Он также демонстрирует возможность решения задачи линейного программирования методами динамического программирования.

Пример 4.5-1

Предприятие обрабатывающей промышленности выпускает два вида продукции. Производственный процесс составляет 430 минут в день. Для производства единицы продукции первого вида требуется 2 минуты, а второго — 1 минута. На дневной объем производства продукции первого вида ограничений нет (кроме возможностей производственного процесса), максимальный ежедневный спрос на второй вид продукции равен 230 единиц. Реализация единицы продукции первого вида приносит прибыль в 2 доллара, а второго — 5 долларов. Необходимо найти оптимальное решение задачи максимизации прибыли методами динамического программирования.

Данная задача является следующей задачей линейного программирования.

Максимизировать z = 2х₁ + 5х₂

при ограничениях

Элементы модели динамического программирования таковы.

1. Этап i соответствует продукции i,i - 1,2.

2. Альтернативой х_i на i-м этапе является объем производства продукции i,i=l,2.

3. Состояние представляет количество ресурсов, необходимое для производства продукции вида 1 и 2 (производственное время и ограничение на спрос) и используемое на этапах 1 и 2.

4. Состояние (v₂, w₂) представляет количество ресурсов, необходимое для производства продукции вида 1 и 2 (производственное время и ограничение на спрос) и используемое на этапе 2.

Этап 2.

Пусть f₂(v₂, w₂) представляет максимальную прибыль для этапа 2 (прибыль от выпуска продукции вида 2) при заданном состоянии (v₂, w₂). Тогда

Следовательно, имеет место при . Имеем следующее решение для второго этапа.

Состояние	Оптимальное решение

Этап 1.

Оптимизация па первом этапе требует решение минимаксной задачи, что в общем случае является достаточно сложным делом. Для рассматриваемой задачи имеем и , что дает . Так как представляет собой нижнюю огибающую двух пересекающихся прямых (проверьте!), отсюда следует, что

Графически можно легко проверить, что функция достигает максимального значения при . Итак получаем следующее:

Состояние	Оптимальное решение
(430,230)

Для определения оптимального значения х₂ заметим, что

Следовательно

.

Итак, оптимальное решение имеет вид:

единиц, единиц, .

Упражнения 4.5,а

1. Решите следующие задачи линейного программирования методами динамического программирования.

а) Максимизировать z = 4x₁ + 14х₂

при ограничениях

b) Максимизировать z = 8x₁ + 7х₂

при ограничениях

c) Максимизировать z = 7x₁² +6x₁ +5х₂²

при ограничениях

2. Пусть в задаче из примера 4.4-1 о загрузке предметов п наименований ограничения самолета по весу и объему представлены величинами W и V соответственно. Величины w_i, v_i и r_i представляют соответственно вес, объем и прибыль, отнесенные к одному предмету наименования. Необходимо записать рекуррентное уравнение обратной прогонки для алгоритма динамического программирования решения сформулированной задачи.

4.6. Заключение

В этой главе рассмотрены некоторые примеры детерминированных моделей динамического программирования. Принцип оптимальности является основой поэтапного решения задачи динамического программирования. Хотя этот принцип не содержит информации о способах решения подзадач на каждом этапе, его применение существенно облегчает решение многих сложных задач, которые нельзя решить другими методами.

Литература

Bertsekas D. Dynamic Programming: Deterministic and Stochastic Models, Prentice Hall, Upper Saddle River, N. J., 1987.

Denardo E. Dynamic Programming Theory and Application, Prentice Hall, Upper Saddle River, N. J., 1982.

Dreyfus S., Law A. The Art and Theory of Dynamic Programming, Academic Press, N. Y., 1977.

Sniedovich M. Dynsmic Programming, Marcel Dekker, N. Y., 1991.

Комплексная задача

• 4-1. Компания проверяет состояние оборудования в конце каждого года и на основании этого принимает следующее решение: либо использовать его еще один год, либо заменить. Однако оборудование, которое находилось в эксплуатации три года, подлежит замене в обязательном порядке. Компания планирует разработать стратегию замены имеющегося оборудования на следующие 10 лет. Соответствующая информация содержится в приведенной ниже таблице. Считается, что в начале первого года все оборудование новое.

Год покупки	Стоимость покупки ($)	Стоимость содержания ($) для данного возраста (лет)	Стоимость продажи ($) для данного возраста (лет)

Глава V

Вероятностное динамическое программирование

5.1. Введение

Вероятностное динамическое программирование (ДП) отличается от детерминированного динамического программирования, описанного в главе 10, тем, что состояния и прибыли на каждом этапе являются случайными. Модели вероятностного ДП возникают, в частности, при рассмотрении стохастических моделей управления запасами и в теории марковских процессов принятия решений. Этим двум темам посвящены главы 16 и 19, поэтому в настоящей главе они не рассматриваются. В этой главе описываются некоторые примеры достаточно общего содержания, призванные показать стохастическую природу ДП.

5.2. Азартная игра

Одна из разновидностей игры в русскую рулетку состоит во вращении колеса, на котором по его периметру нанесены п последовательных чисел от 1 до п. Вероятность того, что колесо в результате одного вращения остановится на цифре i, равна р_i,. Игрок платит х долларов за возможность осуществить т вращений колеса. Сам же игрок получает сумму, равную удвоенному числу, которое выпало при последнем вращении колеса. Поскольку игра повторяется достаточно много раз (каждая до т вращений колеса), требуется разработать оптимальную стратегию для игрока.

Мы сформулируем задачу в виде модели ДП, используя следующие определения.

1. Этап i соответствует i-му вращению колеса, i = 1, 2, ..., m.

2. Альтернативы на каждом этапе состоят в следующем — либо покрутить колесо еще раз, либо прекратить игру.

3. Состояние системы j на каждом этапе i представляется одним из чисел от 1 до п, которое выпало в результате последнего вращения колеса.

Пусть f_i(j) — максимум ожидаемой прибыли при условии, что игра находится на этапe (вращении) i и исходом последнего вращения есть число j Имеем следующее.

Рекуррентное уравнение для f_i(j) можно записать следующим образом.

Обоснование рекуррентного уравнения сводится к следующему. При первом вращении колеса (i = 1) состоянием системы является j = 0, ибо игра только началась. Следовательно, f₁(0) = p₁f₂(l) + + ... + p_nf₂(n). После выполнения последнего вращения колеса (i = т) имеется лишь один выбор — закончить игру независимо от исхода j m – говращения. Следовательно f_m+1(j) = 2j.

Рекуррентные вычисления начинаются с f_m+1, заканчиваются при f₁(0) и сводятся таким образом к т + 1 вычислительному этапу. Так как f₁(0) представляет собой ожидаемую прибыль от всех т вращений колеса, а игра обходится игроку в х долларов, имеем следующее.

Ожидаемая прибыль = f₁(0) – x.

Пример 5.2-1

Предположим, что по периметру колеса русской рулетки расставлены числа от 1 до 5. Вероятности р_i остановки колеса на числе i соответственно равны следующему: p₁= 0.3,
р₂=0.25, p₃ = 0.2, p₄ = 0.15, р₅ = 0.1. Игрок платит 5 долларов за возможность сделать не более четырех вращений колеса. Определим оптимальную стратегию игрока для каждого из четырех вращений и найдем соответствующий ожидаемый выигрыш.

Этап 5.

Исход 4-го вращения	Оптимальное решение
j	f5(j)	Решение
		Закончить
		Закончить
		Закончить
		Закончить
		Закончить

Этап 4.

Исход 3-го вращения	Ожидаемая прибыль	Оптимальное решение
j	Закончить	Вращать	f4(j)	Решение
				Вращать
				Вращать
				Закончить
				Закончить
				Закончить

Этап 3.

Исход 2-го вращения	Ожидаемая прибыль	Оптимальное решение
j	Закончить	Вращать	f3(j)	Решение
		6.15	6.15	Вращать
		6.15	6.15	Вращать
		6.15	6.15	Вращать
		6.15	8.00	Закончить
		6.15	10.00	Закончить

Этап 2.

Исход 1-го вращения	Ожидаемая прибыль	Оптимальное решение
j	Закончить	Вращать	f3(j)	Решение
		6.81	6.81	Вращать
		6.81	6.81	Вращать
		6.81	6.81	Вращать
		6.81	8.00	Закончить
		6.81	10.00	Закончить

Этап.1.

В начале игры единственным выбором является вращение колеса.

Из предыдущих таблиц следует, что оптимальным решением будет следующая последовательность действий.

Номер вращения	Оптимальная стратегия
	Начало игры; вращать
	Продолжить игру, если исходом первого вращения есть 1, 2 или 3; иначе закончить игру
	Продолжить игру, если исходом первого вращения есть 1, 2 или 3; иначе закончить игру
	Продолжить игру, если исходом первого вращения есть 1 или 2; иначе закончить игру

Ожидаемая прибыль от игры составляет 7.31 – 5 = 2.31 доллара.

Упражнение 5.2, а

1. Пусть в задаче из примера 5.2-1 по периметру колеса расставлены числа от 1 до 8 и вероятности остановки колеса на каждом из этих чисел одинаковы. Предполагая, что каждая игра состоит не более чем из пяти вращений колеса, определите оптимальную стратегию игры.

2. Я хочу продать свой подержанный автомобиль тому, кто предложит наивысшую цену. Изучая автомобильный рынок, я пришел к выводу, что с равными вероятностями мне за автомобиль могут предложить очень низкую цена (около 1050 долларов), просто низкую цену (около 1900 долларов), среднюю цену (около 2500 долларов) либо высокую цену (примерно 3000 долларов). Я решил помещать объявление о продаже автомобиля на протяжении не более трех дней подряд. В конце каждого дня мне следует решить, принять ли наилучшее предложение, поступившее в течение этого дня. Какой должна быть моя оптимальная стратегия относительно принятия предложенной цены за автомобиль?

5.3. Задача инвестирования

Некто планирует инвестировать С тысяч долларов через фондовую биржу в течение последующих п лет. Инвестиционный план состоит в покупке акций в начале года и продаже их в конце этого же года. Накопленные деньги затем могут быть снова инвестированы (все или их часть) в начале следующего года. Степень риска инвестиции представлена тем, что прибыль имеет вероятностный характер. Изучение рынка свидетельствует о том, что прибыль от инвестиции зависит от т условий рынка (благоприятных или неблагоприятных). При этом условие i приводит к прибыли r_i с вероятностью p_i, i = 1, 2, ..., т. Как следует инвестировать С тысяч долларов для наибольшего накопления к концу п лет?

Обозначим

x_i – сумма денежных средств, доступных для инвестирования в начале i-го года (х₁=С),

y_i – сумма реальной инвестиции в начале i-го года (у_i ≤ х_i).

Элементы модели ДП можно описать следующим образом.

1. Этап i представляет i-й год инвестирования.

2. Альтернативами на этапе i являются величины y_i.

3. Состояние системы на этапе i описывается величиной х_i.

Пусть f_i(x_i) — максимальная ожидаемая сумма поступления денежных средств за года от i до п при условии, что в начале i-го года имеется сумма x_i. Для k-го условия рынка имеем следующее.

Так как вероятность k-го условия рынка равна p_k, рекуррентное уравнение динамического программирования имеет следующий вид.

где , так как после n-го года инвестиций нет. Отсюда следует, что

,

поскольку функция в фигурных скобках является линейной по у_n и, следовательно, достигает своего максимума при у_n = х_n.

Пример 5.3-1

Пусть в предыдущей модели инвестирования объем инвестиции составляет С =10 000 долларов на 4-летний период. Существует 40%-ная вероятность того, что вы удвоите деньги, 20%-ная — останетесь при своих деньгах и 40% — потеряете весь объем инвестиции. Необходимо разработать оптимальную стратегию инвестирования.

Используя принятые в модели обозначения, имеем следующее.

Этап 4.

.

Отсюда порлучаем

Состояние	Оптимальное решение
f4(x4)
x4	1.4x4	x4

Этап 3.

Поэтому имеем

Состояние	Оптимальное решение
f3(x3)
x3	1.96x3	x3

Этап 2.

Отсюда следует

Состояние	Оптимальное решение
f2(x2)
x2	2.744x2	x2

Этап 1.

Имеем

Состояние	Оптимальное решение
f1(x1)
x1	2.744x1	x1

Оптимальную инвестиционную политику можно сформулировать следующим образом. Так как для i = 1, 2, 3, 4, то оптимальным решением является инвестирование всех наличных денежных средств в начале каждого года. Накопленные денежные средства к концу четырех лет составят 3.8416x₁ = 3.8416 3 10000 = 38416 долларов.

Упражнения 5.3,а

1. Определите оптимальную инвестиционную политику в примере 5.3-1 в предположении, что вероятности р_k и прибыли r_k для следующих 4 лет принимают такие значения.

Год
			0.5	0.1	0.4	0.5
			– 1	0.4	0.4	0.2
		– 1	– 1	0.2	0.4	0.4
	0.8	0.4	0.2	0.6	0.2	0.2

2. Камера объемом 10 кубических метров предназначена для хранения изделий трех наименований. Одно изделие наименований 1, 2, 3 занимает соответственно 2, 1 и 3 кубических метра. Вероятности спроса на эти изделия приведены в следующей таблице.

Количество едициц	Вероятность спроса
Наименование 1	Наименование 2	Наименование 3
	0.5	0.3	0.3
	0.5	0.4	0.2
	0.0	0.2	0.5
	0.0	0.1	0.0

Стоимость хранения единицы изделия наименований 1, 2, 3 равна 8, 10 и 15 дол­ларов соответственно. Сколько единиц изделий каждого наименования следует хранить в камере?

3. Фирма с высокотехнологичным производством начала выпуск самых современных суперкомпьютеров в расчете на трехлетний период. Годовой спрос D на новый суперкомпьютер описывается распределением

Производственная мощность завода составляет три суперкомпьютера в год стоимостью 5 миллионов долларов каждый. Количество произведенных за год суперкомпьютеров может не совпадать в точности с объемом спроса. На нереализованный к концу года суперкомпьютер требуются затраты в 1 миллион долларов, связанные с его хранением и содержанием в исправности. Фирма терпит убытки в 2 миллиона долларов, если поставка суперкомпьютера откладывается на один год. Фирма не будет принимать новых заказов позже четвертого года, но будет продолжать выпуск суперкомпьютеров на протяжении пятого года, чтобы выполнить все заказы, оказавшиеся невыполненными к концу четвертого года. Определите оптимальные годичные объемы производства суперкомпьютеров.

4. Компания владеет тремя спортивными центрами в деловой части города. На Пасху популярны велосипедные прогулки на открытом воздухе. В компании имеется восемь велосипедов, которые она может распределить между тремя центрами для их проката в целях максимизации доходов. Спрос на велосипеды и часовая стоимость их аренды зависят от месторасположения центра и характеризуются следующими данными.

Количество велосипедов	Вероятность спроса
Центр 1	Центр 2	Центр 3
	0.10	0.02
	0.20	0.03	0.15
	0.30	0.10	0.25
	0.20	0.25	0.30
	0.10	0.30	0.15
	0.10	0.15	0.10
		0.05	0.025
		0.05	0.025
		0.05
Арендная плата ($/час)

Как компании распределить восемь велосипедов между тремя спортивными центрами?

5.4. Максимизация вероятности достижения цели

В разделе 5.3 рассматривалась задача, связанная с максимизацией ожидаемой прибыли. Иным полезным критерием для рассмотренной задачи является максимизация вероятности достижения определенного уровня дохода. Продемонстрируем этот подход на примере модели инвестирования, которая описана в разделе 5.3.

Используя обозначения из раздела 5.3, оставим без изменения определение этапа i, альтернативы у_i и состояния х_i. Эти модели отличаются только определением критерия; здесь нашей целью является максимизация вероятности достижения некоторой накопленной денежной суммы S по истечении п лет. С этой точки зрения определим функцию f_i(x_i) – вероятность накопления суммы S, если в начале i-го года имеются денежные средства в сумме х_i и для последующих лет i, i + 1,..., п используется оптимальное инвестирование.

Рекуррентное уравнение динамического программирования имеет вид

Рекуррентная формула основана на формуле условной вероятности

В нашем случае f_i+1 (x_i + r_k y_i) играет роль вероятности Р{А | B_j}.

Пример 5.4-1

Некий индивидуум планирует инвестировать 2 000 долларов. Имеющиеся варианты позволяют удвоить эту сумму с вероятностью 0.3 или потерять ее с вероятностью 0.7. Акции продаются в конце года, а в начале следующего года все деньги или их часть снова инвестируются. Этот процесс повторяется на протяжении трех лет. Целью является максимизация вероятности достижения суммы в 4 000 долларов в конце третьего года.

В соответствии с обозначениями данной модели, имеем r₁ = 1 с вероятностью 0.3
и r₂ = –1 с вероятностью 0.7.

Этап 3.

На этом этапе состояние х₃может изменяться от 0 до 8 000 долларов. Минимальное значение возможно, когда вся инвестиция потеряна, а максимальное – когда инвестиция удваивается в конце каждого из двух первых лет. Следовательно, рекуррентное уравнение для этапа 3 записывается в следующем виде:

,

где, x₃ = 0, 1,..., 8.

Приведенная ниже таблица содержит детали вычислений для данного этапа. Все заштрихованные ячейки таблицы являются неподходящими, так как не удовлетворяют условию у₃ ≤ x₃. Кроме того, при выполнении вычислений можно заметить, что

.

В противном случае эти вероятности равны 1.

Хотя приведенная таблица и свидетельствует о том, что существуют альтерна­тивные оптимумы для х₃ = 1, 3, 4, 5, 6, 7 и 8, оптимальный (последний) столбец содержит лишь наименьшие оптимальные значения у₃. Это объясняется тем, что инвестор не собирается инвестировать больше того, что необходимо для достиже­ния поставленной цели.

Этап 2.

.

Этап 1.

.

x1		Оптимум
y1 = 0	y1 = 1	y1 = 2	f1	y1
	0.330.3+0.730.3 = 0.3	0.330.51+0.730.09 = 0.216	0.331+0.730 = 0.3	0.3

Оптимальная стратегия определяется следующим образом. При заданной начальной сумме х₁ = 2000 долларов вычисления для первого этапа дают у₁ = 0. Это означает, что в первый год не следует делать инвестиций. Данное решение оставляет инвестора с 2000 долларов к началу второго года. Из таблицы, соответствующей второму этапу, при x₂ = 2 получаем у₂ = 0; это снова означает, что на протяжении второго года также не следует делать инвестиций. Далее использование значения х₃ = 2 на третьем этапе приводит к у₃ = 2, а это означает, что на третий год следует инвестировать всю имеющуюся в распоряжении сумму. Соответствующая максимальная вероятность достижения цели S = 4 равна f₁(2) = 0.3.

Упражнения 5.4,а

1. В примере 5.4–1 этап 1 решения задачи показывает, что существует два альтернативных оптимума: y₁ = 0 и у₁ = 2. Покажите, что применение стратегии у₁ = 2 (т.е. инвестировать все деньги в начале первого года) не изменяет результата инвестиционной политики на протяжении трех лет, а именно, соответствующая максимальная вероятность достижения цели сохраняется равной 0.3.

2. Решите задачу из примера 5.4-1, если целью инвестора является максимизация вероятности достижения, по меньшей мере, суммы в 6 000 долларов к концу третьего года. Инвестор имеет в своем распоряжении 1000 долларов, и вероятность удвоения суммы на протяжении каждого года равна 0.6.

3. Вы и ваш друг хотите сыграть в казино в следующую игру. Вы делаете определенную ставку, и каждый из вас независимо подбрасывает симметричную монету. За каждый доллар суммы ставки казино заплатит три доллара, (что дает чистую прибыль в 2 доллара), если в результате подбрасывания выпадут две решки. Иначе вы теряете сумму ставки. Если вы с другом имеете в сумме один доллар, определите стратегию игры, считая, что целью является максимизация вероятности окончания трех игр с суммой в 4 доллара.

Литература

Bertsekas D. Dynamic Programming: Deterministic and Stochastic Models, Prentice Hall, Upper Saddle River, N. J., 1987.

Cooper L. and Cooper M. Introduction to Dynamic Programming, Pergamon Press, N. Y., 1981.

Smith D. Dynamic Programming: A Practical Introduction, Ellis Horwood, London, 1991.

Комплексные задачи

5-1. Компания использует грузовые автомобили для доставки заказов покупателям и планирует заменить свои автомобили на протяжении последующих пяти лет. Годовые затраты, связанные с использованием нового грузовика, являются нормально распределенной случайной величиной с математическим ожиданием 300 долларов и среднеквадратическим отклонением 50 долларов. Математическое ожидание и среднеквадратическое отклонение годовых эксплуатационных затрат через год возрастают на 10%. Стоимость нового грузового автомобиля в настоящее время равна 20 000 долларов и через год возрастет, как ожидается, на 12%. Грузовые автомобили используются чрезвычайно интенсивно, поэтому существует вероятность того, что каждый из них может сломаться в любое время, после чего ремонту не подлежит. Имеется возможность сдать старый автомобиль при покупке нового. При этом стоимость старого автомобиля зависит от того, находится ли он в рабочем состоянии. В начале шестого года автомобиль подлежит продаже по цене, которая также зависит от его состояния (аварийное или рабочее). Приведенная ниже таблица содержит данные, описывающие ситуацию в зависимости от возраста автомобиля.

Возраст автомобиля (года)
Вероятность поломки	0.01	0.05	0.10	0.16	0.25	0.40	0.60

Если автомобиль использовался 1 год и находится в рабочем состоянии, то его стоимость равна 70% от начальной и за год уменьшается на 15%. Если же он находится в аварийном состоянии, то соответствующие показатели уменьшаются в два раза. Стоимость автомобиля в виде испорченного имущества в начале шестого года составляет 200 долларов, если он находится в рабочем состоянии, и 50 долларов, если он аварийный. Разработайте оптимальную политику замены автомобилей.