XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 55
Текст из файла (страница 55)
В практике компьютерного имитационного моделирования для уменьшения выборочной дисперсии широко используют леееуеод дополнения. Основная идея этого метода заключается в следующем. Если 1 сли (уь) — последовательность псевдослучайных чисел (см., например, табл. 9.5), то (1 — уь) — также последовательность псевдослучайных чисел. Значит, возможна реализация двух прогонов модели с использованием двух наборов пеев о- дослучайных чисел ув и 1 — дь, й = 1, и. Если ял н гь — соответствующие результаты этих прогонов, то: а) оба рассматриваемых набора псевдослучайных чисел имеют одинаковые числовые характеристики; б) так как уй+ (1 — уь) = 1, 1с = 1, и, то между множествами псевдослучайных чисел уь и 1 — уь существует отрицательная корреляция [ХЪ'П]; в) если иь = (яь+дь)/2, й= 1, и, то оценку 1 1 й= — ~ив = — — ~(хь+ гл) «=1 ь — 1 параметра И можно рассматривать как оценку, полученную по данным случайной выборки объема 2п [ХуП) г) если со4х(ео)'з(ол)) ( 0 и и(м) = (~) + ~(~) 2 391 Вопросы и ввдвчи 390 а ВВеДение В имитАЦиОннОе мОДелиРОВАние то дисперсии случайных величин х(ы), х(и), и(ы) связаны неравенством [ХН] Р [и(ь )] = 0,25 (Р [х(ь )]+ Р[я(ы)]) + 0,5 соч[х(ы) су(м)] < < 0,25(Р[х(ы)] + Р[у(ы)]), т.е.
оценка й параметра д обладает дисперсиен, меньшей, чем дисперсия аналогичной оценки, полученной по данным случайной выборки объема 2п. Вопросы и задачи 9.1. В чем заключается основная цель имитационного моделирования и что является его основой. "? 9.2, Сформулируйте основную задачу имитационного моделирования. Чем она отличается от задач исследования операций? 9.3. Почему компьютерное имитационное моделирование можно рассматривать как статистический эксперимент и что представляют собой результаты этого моделирования.
? 9.4. Назовите основные области применения компьютерного имитационного моделирования. 9.8. Какие цели преследуют при использовании компьютерного имитационного моделирования применительно к задачам организационного управления? 9.8. Назовите основные этапы построения и практического использования имитационной модели, 9.7.
Сформулируйте основную идею метода Монте-Карло. Что общего между компьютерным имитационным моделированием и методом Монте-Карло? 9.8. Для чего нужны псевдослучайные числа в компьютерном имитационном моделировании и в чем заключается основная идея их использования? 9.9. Изложите общую идею метода мультнпликативных конгруэнций получения псевдослучайных чисел. 9.10.
Сформулируйте основные идеи, используемые при компьютерном моделировании случайных величин с заданными законами распределения. 9.11. Как можно смоделировать с помощью компьютера: а) случайный вектор; б) случайное событие? 9.12. Пусть С С К" — ограниченная область, в которой определена скалярная функция ~р(Х) векторного аргумента Х Е С. Сформулируйте основную идею использования метода Монте-Карло для вычисления интеграла р(х) их. 9.13.
Каким образом случайные события используют при построении и эксплуатации компьютерных имитационных моделей? 9.14. Каковы основные идеи методов повторения, подынтервалов и циклов получения наблюдений в компьютерном имитационном моделировании? Назовите их достоинства и недостатки. 9.15. Какие методы уменьшения выборочной дисперсии при компьютерном имитационном моделировании Вы знаете? В чем заключаются основные идеи этих методов? 9.18.
Используя иэ табл. 9.5 первые 10 псевдослучайных чисел, запишите результаты первых 10 исходов в игре с бросанием игральной кости (см. пример 9Л). О т в е т: 4, 4, 4, 3, 3, 4, 3, 6, 3, 1. 9.17. В примере 9.4 игрок решил воспользоваться таблицей псевдослучайных чисел. Как он может это сделать? От вет: если псевдослучайное число уь попадает в промежуток [О, 0,5), то при бросании двух монет выпадают герб 393 Вопросы и задачи 0 5 20 2Ь 30 Зо 10 10 Рис. 9.5 о В В 1. 1- ...~ 1,08 1,1! 1,21 1 О 0,8! 1,51 2,11 2,28 2,27 0,55 0,78 0,85 0,81 Рис. 9.4 392 9. ВВЕДЕНИЕ В ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ и решка; если 95 Е [0,5, 0,75), то выпадают два герба; если уь Е [0,75, Ц, то выпадают две решки. 9.18.
Пусть время обслуживания заявки в некоторой системе массового обслуживания представляет собой случайную величину, распределенную по зкспоненцизльному закону с параметром 12 = 10 (заявок в минуту). Построив модель системы с помощью псевдослучайных чисел из табл. 9.5, определите время обслуживания первых пяти заявок. О т в е т: 0,09 мин; 0,07 мин; 0,11 мин; 0,04 мин; 0,04 мин. У к а з а н и е: см.
пример 9.6. 9.19, В примере 9.11 продолжите процесс имитационного моделирования, полагая Т = 2,36 ч. Определите тип и время реализации основных событий на отрезке времени [О,Т). Вычислите среднюю длину очереди и среднее время ожидания обслуживания на [О, Т). Ответ: тип и время реализации основных событий изображены на рис. 9.4; средняя длина очереди — 0,7 заявки, а среднее время ожидания обслуживания — 0,6 ч. 9.20, На рис. 9,5 отражено изменение числа заявок г, находящихся в одноканальной системе массового обслуживания.
Время моделирования Т = 36, количество циклов 4. С доверительной вероятностью 0,95 определите интервальные оценки: а) для доли времени простоя системы; б) для числа заявок, находящихся в системе. От в ет: а) 0,364~0,096; б) 1,004 ~0,511. 9.21. Пусть время обслуживания в одноканальной системе массового обслуживания является случайной величиной, распределенной по зкспоненциальному закону с параметром 12 = 0,5. Определите среднее время обслуживания одной заявки и исправленную выборочную дисперсию втой оценки: а) по десяти н~юдениям с использованием псевдослучайных чисел уь, к = 21, 30, из табл. 9.5; б) по десяти наблюдениям с использованием псевдослучайных чисел 1 — уы к = 21, 30, из табл.
9.5; в) по первым пяти наблюдениям, взятым из а) и б), с использованием метода дополнения. Ответ: а) х=2,45, 52=3,64; б) 2=1,89, 52=4,77; в) и= = 2,31, У = 5,48. 395 Приложение 1. ВЕНГЕРСКИЙ МЕТОД РЕШЕНИЯ ЗАДА'ЧИ О НАЗНА'4ЕНИЯХ При обсуждении постановки задачи о назначениях (см, 5.3) было отмечено, что эта задача является частным случаем классической щракспоргпкой задачи и, как следствие, является задачей гпранспортного типа.
Применительно к задаче о назначениях симплекскый метод не эффективен, так как любое ее допустимое базисное решение является вырожденным. Специфические особенности задачи о назначениях позволили разработать эффективный метод ее решения, известный как венгерский метпод". Прежде чем приступать к изучению этого метода, напомним основной результат, полученный в 5.3 при анализе задачи о назначениях. Пусть С = (с;,) б М„(К) — матрица стоимости задачи о назначениях (5.11) и С' = (с,'") Е М„(К) — зявивалекяпкая ей матприца сгпоимостпи, т.е. с,',=сз+4+1,, 1=1,п, 1=1,п, где д;, 1= 1, п, и 1, 1 = 1, и, — некоторые постоянные.
Тогда при замене в задаче (5.11) параметров с;, входящих в матрицу стоимости С, параметрами с,', 1,1 = 1, и, из эквивалентной матрицы стоимости С' опгпимальное решение исходной задачи останется неизменным. Основная идея венгерского метода заключается в переходе от исходной матрицы стоимости С к эквивалентной ей матрице стоимости С" с неотрицательными элементами и системой и независимых нулей, т.е.
с совокупностью нулевых элементов 'Смэ Рискин Л.Г. матрицы, из которых никакие два не принадлежат одной и той же строке или одному и тому же столбцу. Понятно, что квадратная матрица порядка и не может иметь систему более чем из и независимых нулей. Согласно (5.11), можно утверждать, что для любого допусгпимого решения задачи о назначениях матрица перемекных Х = (х; ) б М„(К) содержит п(п — 1) нулей и п единиц, из которых никакие две не принадлежат одной и той же строке или одному и тому же столбцу. Таким образом, если зти п единиц в матрице Х расставить в соответствии с расположением элементов системы п независимых нулей эквивалентной матрицы стоимости С', то получим допустимое решение рассматриваемой задачи о назначениях.
Более того, найденное допустимое решение является оптимальным решением, так как ему соответствует нулевое значение целевой у«уккции, определяемой матрицей С', которое не может быть уменьшено в силу неотрицательности элементов эквивалентной матрицы стоимости С*. Алгоритм венгерского метода решения задачи о наэцачениях состоит из подготовительного этапа и не более чем и — 2 последовательно повторяющихся итераций. На подготовительном этапе получают матрицу стоимости Со, эквивалентную матрице стоимости рассматриваемой задачи о назначениях и содержащую первоначальную систему независимых нулей. На каждой итерации число независимых нулей в преобразованной эквивалентной матрице стоимости увеличивается не менее чем на единицу.
Через конечное число итераций система независимых нулей в преобразованной эквивалентной матрице стоимости С' будет состоять из и элементов, что означает завершение процесса решения рассматриваемой задачи. Подготовительный этап заключается в последовательном выполнении следующих трех шагов. Шаг 1. Для каждого столбца матрицы стоимости С задачи о назначениях находят минимальный элемент 1 = ш'1п с;, 1' = 1, и, «=ц«« 397 У с;,=с;,-1, >О, 1,1=1,п. 5 6 7 1 10 4 6 7 8 5 3 5 12 5 9 8 1=1,п, 411 = ш1п ссу, 1=!,п 0 2 4 0 5 0 3 6 3 1 0 4 7 1 6 7 4 0 3 6 0 4 5 6 0 2 5 0 3 1 6 0 0" 2 4 0 0' 2 4 0 0" 3 6 1 0' 4 0 5 6 5 0 3 6 3 1 0* 4 6 0" 5 6 5 С = 3 6 Со —— 396 ПРИЛОЖЕНИЕ 1.
ВЕНГЕРСКИЙ МЕТОД и формируют эквивалентную матрицу стоимости С' = (с'; ), в которой В результате выполнения первого шага подготовительного этапа получают эквивалентную матрицу стоимости С', в каждом столбце которой имеется по крайней мере один нулевой элемент. Шаг 2. Для каждой строки матрицы стоимости С' находят минимальный элемент и формируют эквивалентную матрицу стоимости Со = (со ), в которой В результате выполнения второго шага подготовительного этапа получают эквивалентную матрицу стоимости Со с неотрицательными элементами, в каждой строке и каждом столбце которой имеется по крайней мере один нулевой элемент. Шаг 3. В первом столбце матрицы Со выбирают любой нулевой элемент и обозначают его как 0'. Затем переходят ко второму столбцу матрицы Со, и если в нем есть нулевые элементы, не лежащие в одной строке с нулевым элементом 0" первого столбца, то выбирают любой из них и обозначают как 0*. Далее процедуру повторяют для всех последующих столбцов матрицы стоимости Со и получают для нее первоначальную систему независимых нулей, состоящую из нулевых элементов, обозначенных как 0'.
Можно доказать, что первоначальная система независимых нулей не может содержать менее двух элементов, Пример П1,1. Нроиллюстрируем подготовительный этап алгоритма венгерского метода для следующей матрицы стоимости: Шаг 1. В первом столбце минимальным является элемент 11 = сы — — 5, во втоРом — 11 —— сзз = 4, в тРетьем — !з = сзз —— = 3, в четвертом — 14 = сгя = 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
