Output Summary 2 страница

Глава 18. Имитационное моделирование

зователей такие "дружественные" интерфейсы могут значительно замедлить процесс создания имитационных моделей. Поэтому нет ничего удивительного в том, что мно­гие разработчики имитационных моделей предпочитают использовать в своей работе языки программирования "общего назначения", такие как С, Basic или FORTRAN.

УПРАЖНЕНИЯ 18.7⁷

1. Клиенты случайным образом прибывают на почтовое отделение, в котором работают три служащих. Время между их приходами является случайной величиной, распределенной по экспоненциальному закону с математическим ожиданием 5 мин. Время, затрачиваемое служащим на обслуживание кли­ента, имеет экспоненциальное распределение с математическим ожиданием 10 мин. Все прибывающие клиенты формируют единую очередь и ожидают первого освободившегося служащего. Используйте имитационную модель сис­темы для исследования ее работы на протяжении 480 мин., чтобы определить

a) среднее число клиентов, ожидающих в очереди;

b) среднюю занятость служащих.

2. Телевизионные блоки прибывают для проверки на ленточный конвейер с по­стоянной скоростью пять единиц в час. Время проверки блока является слу­чайной величиной, равномерно распределенной между 10 и 15 мин. Преды­дущий опыт показывает, что 20 % проверенных блоков должны быть отрегулированы и отправлены на повторную проверку. Время регулировки также является случайной величиной, равномерно распределенной между 6 и 8 мин. Используйте имитационную модель системы для исследования ее работы на протяжении 480 мин., чтобы вычислить

a) среднее время, необходимое для проверки одного блока;

b) среднее количество повторных проверок, которые должен пройти телеви­зионный блок перед выходом из системы.

3. Мышь находится в лабиринте и отчаянно пытается из него выбраться. Про­ведя в попытках выбраться от 1 до 3 мин. с равномерным распределением, в 30 % случаев она находит выход из лабиринта. В случае неудачи она бродит бесцельно от 2 до 3 мин. с равномерным распределением и, в конце концов, останавливается в месте, откуда она начинала, но лишь для того, чтобы по­пробовать еще раз. Мышь может пытаться выбраться на свободу столько раз, сколько она хочет, но всему есть предел. Истратив много энергии на много­численные попытки выбраться на свободу, мышь непременно умрет, если не ус­пеет выбраться за период времени, имеющий нормальное распределение с мате­матическим ожиданием 10 мин. и стандартным отклонением 2 мин. Постройте имитационную модель для оценки вероятности того, что мышь освободится. С этой целью предположите, что в модели будет использовано 100 мышей.

4. На финальной стадии сборки автомобиль движется по конвейеру между двумя параллельными рабочими местами, чтобы можно было выполнять работы как с левой, так и с правой стороны одновременно. Время выполнения работ с каждой стороны является равномерно распределенной случайной величиной с интервалом изменения от 15 до 20 мин. и от 18 до 22 мин. соответственно.

⁷ Решите эти упражнения, используя какой-либо язык имитационного моделирования по своему выбору или языки программирования Basic, FORTRAN или С.

Литература

Конвейер прибывает на рабочие места каждые 20 минут. Постройте имитаци­онную модель работы сборочного конвейера на протяжении 480 мин. для опре­деления времени использования рабочих мест слева и справа от машины.

5. Время между прибытием машин на пункт мойки с одним обслуживающим устройством является случайной величиной, распределенной по экспоненци­альному закону с математическим ожиданием 10 мин. Автомобили выстраи­ваются в одну очередь, которая может поместить максимум пять ожидаю­щих автомобилей. Если очередь заполнена, вновь прибывший автомобиль уезжает. Время мойки машины является случайной величиной, равномерно распределенной на интервале от 10 до 15 мин. Постройте имитационную мо­дель работы системы на протяжении 960 мин. и найдите время пребывания автомобиля на пункте мойки.

ЛИТЕРАТУРА

1. Box G. and Muller М. "A Note on the Generation of Random Normal Deviates", An­nals of Mathematical Statistics, Vol. 29, pp.610-611, 1958.

2. Law A. and Kelton W. Simulation Modeling & Analysis, 3rd ed., McGraw-Hill, New York, 2000.

3. Ross S. A Course of Simulation, Macmillan, New York, 1990.

4. Rubenstein R., Melamed B. and Shapiro A. Modern Simulation and Modeling, Wiley, New York, 1998.

5. Taha A. Simulation Modeling and SIMNET, Prentice Hall, Upper Saddle River, N. J., 1988.

Литература, добавленная при переводе

1. Ермаков С. М. Метод Монте-Карло и смежные вопросы. — М.: Наука, 1975.

2. Мур Дж., Уэдерфорд Л. Экономическое моделирование в Microsoft Excel. — М.: Издательский дом "Вильяме", 2004.

3. Нейлор Т. Машинные имитационные эксперименты с моделями экономиче­ских систем. — М.: Мир, 1978.

4. Соболь И. М. Численные методы Монте-Карло. — М.: Наука, 1973.

5. Шеннон Р. Имитационное моделирование систем — искусство и наука. — М.: Мир, 1978.

ГЛАВА 19

МАРКОВСКИЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ

В этой главе рассмотрено применение методов динамического программирова­ния для решения стохастических задач, где процесс принятия решений можно представить конечным числом состояний. Переходные вероятности между состоя­ниями описывают марковскую цепь¹. Структура вознаграждений в подобном про­цессе представима в виде матрицы, элементами которой являются величины дохо­да (или затраты), возникающие при переходе из одного состояния в другое. Матрица переходных вероятностей и матрица доходов зависят от альтернатив ре­шения, которыми располагает лицо, принимающее решение. Целью задачи явля­ется формирование оптимальной стратегии, максимизирующей ожидаемый доход от процесса, имеющего конечное или бесконечное число этапов.

19.1. МАРКОВСКАЯ ЗАДАЧА ПРИНЯТИЯ РЕШЕНИЙ

Мы используем простой пример, который будет служить нам на протяжении всей главы. Несмотря на простоту, парафраз этого примера находит применение во многих приложениях в области управления запасами, замены оборудования, кон­троля и регулирования денежных потоков и др.

Каждый год в начале сезона садовник проводит химический анализ состояния почвы в своем саду. В зависимости от результатов анализа продуктивность сада на новый сезон оценивается как 1) хорошая, 2) удовлетворительная или 3) плохая.

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

Состояние системы в следующем году

Состояние системы в текущем году

1 2 3

f0,2 0,5 0,3) 0 0,5 0,5 0 0 1

Р¹

¹ Обзор теории цепей Маркова приведен в разделе 19.5.

Глава 19. Марковские процессы принятия решений

Переходные вероятности в матрице Р' показывают, что продуктивность почвы в текущем году не лучше, чем в предыдущем. Например, если состояние почвы в текущем году удовлетворительное (состояние 2), то в следующем году оно может остаться удовлетворительным с вероятностью 0,5 или стать плохим (состояние 3) с той же вероятностью.

В результате различных агротехнических мероприятий садовник может изме­нить переходные вероятности Р¹. Обычно для повышения продуктивности почвы применяются удобрения. Эти мероприятия приводят к новой матрице переходных вероятностей Р².

1 2 ⁽ 0,3 0,6 0,1 0,6 ^0,05 0,4

0,1 ⁴ 0,3 0,55,

Чтобы рассмотреть задачу принятия решений в перспективе, садовник связыва­ет с переходом из одного состояния почвы в другое функцию дохода (или структуру вознаграждения), которая определяет прибыль или убыток за одногодичный пери­од в зависимости от состояний, между которыми осуществляется переход. Так как садовник может принять решение использовать или не использовать удобрения, его доход или убыток будет изменяться в зависимости от принятого решения. Мат­рицы R¹ и R² определяют функции дохода (в сотнях долл.) и соответствуют матри­цам переходных вероятностей Р¹ и Р².

3^

-1

'6

7 6

Элементы rfj матрицы R² учитывают затраты, связанные с применением удобрения.

Например, если система находится в состоянии 1 и остается в этом состоянии и в сле­дующем году, то доход составит г,² = 6, если же удобрения не используются, = 7.

Какая же задача принятия решений стоит перед садовником? Сначала необхо­димо установить, будет ли деятельность садовника продолжаться ограниченное число лет или бесконечно. В соответствии с этим рассматриваются задачи принятия решения с конечным и бесконечным числом этапов. В обоих случаях, имея результа­ты химического анализа почвы (состояние системы), садовник должен выбрать наи­лучшую стратегию поведения (удобрять или не удобрять почву). При этом оптималь­ность принятого решения основывается на максимизации ожидаемого дохода.

Садовника может также интересовать оценка ожидаемого дохода по заранее оп­ределенной стратегии поведения при том или ином состоянии системы. Например, он может принять решение всегда применять удобрения, если состояние почвы плохое (состояние 3). В таком случае говорят, что процесс принятия решений опи­сывается стационарной стратегией.

19.2. Модель динамического программирования с конечным числом этапов

Каждой стационарной стратегии соответствуют свои матрицы переходных веро­ятностей и доходов, которые можно построить на основе матриц Р¹, Р², R¹ и R². На­пример, для стационарной стратегии, требующей применения удобрения только тогда, когда состояние почвы плохое (состояние 3), результирующие матрицы пе­реходных вероятностей и доходов задаются следующими выражениями.

	'0,2	0,5	0,3 '		'1 6 Зч
р =		0,5	0,5	, R =	0 5 1
	,0,05	0,4	0,55,		ч6 3 -2,

Эти матрицы отличаются от Р¹ и R¹ только третьей строкой, включенной в них из матриц Р² и R². Причина этого в том, что Р² и R² — матрицы, соответствующие ситуации, когда удобрения применяются при любом состоянии почвы.

УПРАЖНЕНИЯ 19.1

1. В задаче садовника определите матрицы Р и R, соответствующие стационар­ной стратегии, требующей использования удобрений при удовлетворитель­ном и плохом состояниях почвы.

2. Определите все стационарные стратегии в примере с садовником.

19.2. МОДЕЛЬ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ С КОНЕЧНЫМ ЧИСЛОМ ЭТАПОВ

Предположим, что садовник планирует прекратить занятие садоводством через N лет. В этом случае необходимо определить стратегию поведения (удобрять или не удоб­рять почву) для каждого года планирования. Очевидно, что оптимальной стратегией будет такая, при которой садовник получит наибольший ожидаемый доход через N лет.

Пусть k = 1 или 2 обозначает две возможные (альтернативные) стратегии пове­дения садовника. Матрицы Р^к и R^k, представляющие переходные вероятности и функцию дохода для альтернативы k, определены в разделе 19.1; здесь они при­водятся для удобства.

	'0,2	0,5	0,3'		'1	6 зч
		0,5	0,5	• R'=NII=		5 1
	ч 0		1,		,0	0 -1,
	' 0,3	0,6	о,П		'6	5 -Г
*2=И1=	0,1	0,6	0,3	. R2=lk2ll=		4 0
	,0,05	0,4	0,55,		,6	3 -2,

Задачу садовника можно представить как задачу динамического программиро­вания (ДП) с конечным числом этапов следующим образом. Пусть число состояний для каждого этапа (года) равно т (3 в примере с садовником). Обозначим через f_n(i) оптимальный ожидаемый доход, полученный на этапах от п до N включительно при условии, что система находится в начале этапа п в состоянии L

Обратное рекуррентное уравнение, связывающее f_n и f_n+1, можно записать в виде

Л(0 = ™*{?>* [tf+/.♦. 0')]}.» = 1.2,...,АГ,

где f_N+l(J) = 0 для всех j.

Глава 19. Марковские процессы принятия решений

Приведенное уравнение основано на том, что накапливающийся доход ^rl + fn*iU) получается в результате перехода из состояния I на этапе п в состояние /

на этапе п + 1 с вероятностью /»*. Введя обозначение

рекуррентное уравнение ДП можно записать следующим образом:

A(/) = max{vf},

/„(/) = max|vf+Xp*/„_+l(y)J, «= 1,2,...,N-l.

Проиллюстрируем использование рекуррентного уравнения для вычисления ве­личин v* в задаче садовника для ситуации, когда удобрения не применяются (k = 1).

у,¹ =0,2x7 + 0,5x6 + 0,3x3 = 5,3,

v\ =0x0 + 0,5x5 + 0,5x1 = 3,

Ц=0х0 + 0х0 + 1х(-1) = -1.

Эти значения показывают, что если состояние почвы в начале года оказывается хо­рошим (состояние 1), то при одном переходе ожидаемый годовой доход составляет 5,3. Аналогично, если состояние почвы удовлетворительное, ожидаемый годовой доход составит 3, а в случае плохого будет равен -1.

Пример 19.2.1

В этом примере задача садовника решается при данных, заданных матрицами Р¹, Р², R¹ и R². Предполагается, что горизонт планирования включает 3 года (N= 3).

Так как значения v* многократно используются в вычислениях, для удобства они

сведены в таблицу. Напомним, что значение к = 1 соответствует решению "не удоб­рять", к = 2 — "удобрять".

/				2 V,
		5,3		4,7
				3,1
		-1		0,4
ЭтапЗ
				Оптимальное решение
/'	к= 1	к = 2	ад	к"
	5,3	4,7	5,3
		3,1	3,1
	-1	0,4	0,4

19.2. Модель динамического программирования с конечным числом этапов 741

Этап^

	Ч+л/з(1) + Л*/з(2) + л'/з(3)				Оптимальное решение
/	к = 1		к = 2		Hi) к
	5,3 + 0,2 х 5,3 + 0,5 х 3,1 + 0,3 х 0,4 =	= 8,03	4,7 + 0,3 х 5,3 + 0,6 х 3,1 + 0,1 х 0,4	= 8,19	8,19 2
	3 + 0 х 5,3 + 0,5 х 3,1 + 0,5 х 0,4 =	4,75	3,1 + 0,1 х 5,3 + 0,6 х 3,1 + 0,3 х 0,4	= 5,61	5,61 2
	-1 + 0 х 5,3 + 0 х 3,1 + 1 х 0,4 = -0,6	0,4 + 0,05 х 5,3 + 0,4 х 3,1 + 0,55 х 0,4	= 2,13	2,13 2
Этап 1
	*-+Р»Ш + Р-гШ + Р«Ш				Оптимальное решение
/	к= 1		к = 2		Щ *
	5,3 + 0,2 х 8,19 + 0,5 х 5,61 + 0,3 х 2,13 =	= 10,38 4,7 + 0,3 x 8,19 + 0,6 x 5,61 +0,1 х2,13 =	10,74	10,74 2
	3 + 0 х 8,19 + 0,5 х 5,61 + 0,5 х 2,13 =	6,87	3,1 + 0,1 х 8,19 + 0,6 х 5,61 + 0,3 х 2,13	= 7,92	7,92 2
	-1 + 0 х 8,19 + 0 х 5,61 + 1 х 2,13 =	1,13	0,4 + 0,05 х 8,19 + 0,4 х 5,61 + 0,55 х 2,13 = = 4,23	4,23 2

Оптимальное решение показывает, что в 1-й и 2-й годы садовник должен применять удобрения (к' = 2) независимо от состояния системы (состояния почвы по данным хи­мического анализа). На 3-й год садовнику следует применять удобрения только то­гда, когда система находится в состояниях 2 или 3 (т.е. при удовлетворительном или плохом состоянии почвы). Суммарный ожидаемый доход за три года составитyj(l) = 10,74 при хорошем состоянии системы в 1-й год,/,(2) = 7,92 — при удовлетворитель­ном состоянии системы в 1-й год и/ДЗ) = 4,23 — при плохом состоянии.

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

В первом случае значения доходов и переходные вероятности р* должны

быть функциями этапа п. Здесь рекуррентное уравнение динамического програм­мирования принимает вид

/_A.(.-) = max{vf-"},

/Л|>шах|^+£/»;••/„,(;)}. "=U,...,N-1

где

н

Второе обобщение заключается в следующем. Пусть а(< 1) — годовой коэффи­циент переоценки (дисконтирования), тогда D долларов будущего года равны aD долларам настоящего года. При введении коэффициента переоценки исходное ре­куррентное уравнение преобразуется в следующее:

Глава 19. Марковские процессы принятия решений

/„(/) = max {vf},

/„(,) = maxjvf + af>*/„_+l(y)J, «= 1,2,...,N-l.

УПРАЖНЕНИЯ 19.2

1. Фирма ежегодно оценивает положение со сбытом одного из видов своей ос­новной продукции и дает ему удовлетворительную (состояние 1) или не­удовлетворительную оценку (состояние 2). Необходимо принять решение о целесообразности рекламирования этой продукции в целях расширения ее сбыта. Приведенные ниже матрицы Р¹ и Р² определяют переходные ве­роятности при наличии рекламы и без нее в течение любого года. Соответ­ствующие доходы заданы матрицами R¹ и R². Найдите оптимальные реше­ния для последующих трех лет.

'0,9

Р' =

10,6

'0,7 0,2

0, 0,4

0,3 0,8

R' =

-1 -3

-1

Компания может провести рекламную акцию с помощью одного из трех средств массовой информации: радио, телевидения или газеты. Недельные затраты на рекламу с помощью этих средств оцениваются в 200, 900 и 300 долл. соответственно. Компания оценивает недельный объем сбыта своей продук­ции по трехбалльной шкале как удовлетворительный (1), хороший (2) и от­личный (3). Ниже указаны переходные вероятности, соответствующие каж­дому из трех средств массовой информации.

'0,4 0,1 1,0,1

Радио 2 3 0,5 0,0 0,7 0,2 0,2 0,7

Телевидение 1 2 3 0,2 0,6 0,7

'0,7 0,3,0,1

0,0 0,1 0,2

(0,2 0 0

Газета 2 3 0,5 0,7 0,2

0,3 0,3 0,8

Соответствующие недельные доходы (в тыс. долл.) равны следующему.

Радио '400 520 600"! 300 400 700 200 250 500,

Телевидение '1000 1300 1600^ 800 1000 1700 600 700 1100

Газета Г 400 530 710"! 350 450 800 250 400 650

Найдите оптимальную стратегию рекламы для последующих трех недель.

3. Задача управления запасами. Магазин электротоваров в целях быстрого удовлетворения спроса покупателей на холодильники может размещать за­казы в начале каждого месяца. Каждое размещение заказа приводит к по­стоянным затратам в 100 долл. Затраты на хранение одного холодильника в течение месяца равны 5 долл. Потери магазина при отсутствии холодиль­ников оцениваются в 150 долл. за каждый холодильник в месяц. Месячный спрос на холодильники задается следующим распределением вероятностей.

19.3. Модель с бесконечным числом этапов

Спрос х
рМ	0,2	0,5	0,3

Магазин реализует следующую стратегию: максимальный уровень запаса не должен превышать двух холодильников в течение любого месяца.

a) Определите переходные вероятности при различных альтернативах реше­ния этой задачи.

b) Определите ожидаемые месячные затраты на хранение запаса как функ­цию состояния системы и альтернативных решений.

c) Определите оптимальную стратегию размещения заказов на последующие 3 месяца.

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

		Месяц
Спрос, х
	0,1	0,3	0,2
	0,4	0,5	0,4
	0,5	0,2	0,4

19.3. МОДЕЛЬ С БЕСКОНЕЧНЫМ ЧИСЛОМ ЭТАПОВ

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

19.3.1. Метод полного перебора

Предположим, что в задаче принятия решений имеется S стационарных страте­гий. Пусть Р'иК' — матрицы переходных (одношаговых) вероятностей и доходов, соответствующие применяемой стратегии, 8 = 1,2, S. Метод перебора включает следующие действия.

Шаг 1. Вычисляем v,' — ожидаемый доход, получаемый за один этап при стратегии s для заданного состояния I, i = 1, 2.....т.

Шаг 2. Вычисляем п' — долгосрочные стационарные вероятности мат­рицы переходных вероятностей Р', соответствующие стратегии s. Эти вероятности (если они существуют) находятся из уравнений

Глава 19. Марковские процессы принятия решений

где я*=(я;,я'₂,...Х).

Шаг 3. Вычисляем по следующей формуле Е' ожидаемый доход за один шаг (этап) при выбранной стратегии s.

т

i-i

Шаг 4. Оптимальная стратегия s* определяется из условия, что

Е' =тах{Е'}.

Проиллюстрируем этот метод на примере задачи садовника при бесконечном го­ризонте планирования.

Пример 19.3.1

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

Стационарная стратегия, s	Действия
	Не применять удобрения вообще
	Применять удобрения независимо от состояния почвы
	Применять удобрения, если почва находится в состоянии 1
	Применять удобрения, если почва находится в состоянии 2
	Применять удобрения, если почва находится в состоянии 3
	Применять удобрения, если почве находится в состоянии 1 или 2
	Применять удобрения, если почва находится в состоянии 1 или 3
	Применять удобрения, если почва находится в состоянии 2 или 3

Матрицы Р⁵ и R¹ для стратегий от 3 до 8 получаются из аналогичных матриц для стратегий 1 и 2. Таким образом, имеем

	'0,2	0,5 0,3Ч			'1		У
р =		0,5 0,5		R =
	,о	0 1,			,o		-к
	'0,3	0,6 0,1 ^			'6		-Г
Р2 =	0,1	0,6 0,3	, R2
	,0,05	0,4 0,55,			,6	3 •	-2,
	'0,3	0,6 0,Г			'6		-Г
Р3 =		0,5 0,5		R3 =				»
	,о				,0		-lj
	'0,2	0,5 0,3N			'7		зч
Р4 =	0,1	0,6 0,3		R4 =
		0 1,					-к

19.3. Модель с бесконечным числом этапов

	'0,2	0,5	0,3 4		'1		3N
Р5 =		0,5	0,5	, R5 =
	0,05	0,4	0,55,		,6
	'0,3	0,6	0,Г			'6		-Г
Р6 =	0,1	0,6	0,3		R6 =
	,о							Ч
	'0,3	0,6	о,П		'6		-Г
Р7 =		0,5	0,5	, R7 =
	,0,05	0,4	0,55,		,6		-2,
	г 0,2	0,5	0,3'		'1		3'
Р8 =	0,1	0,6	0,3	, R8 =
	^0,05	0,4	0,55,		,6		"2,

Результаты вычислений значений v* приведены в следующей таблице.