6. Демонстрационные примеры

В этой главе рассмотрены два, иллюстрирующие различные классы СДС и процессов принятия решений в таких системах, примера моделирования: экзамен и игра "Крестики-нолики". Первый из них представляет собой модель экзамена, и протекающие в ней процессы связаны со временем: с длительностью подготовки к экзамену и его сдачи, со временем прихода. Поэтому для моделирования используется объект операций. В качестве второго примера рассматривается игра, в которой все действия лица, принимающего решения, зависят не от времени, а только лишь от очередности ходов и выбранных клеток игрового поля. Поэтому вместо объекта операций используется объект точек принятия решений.

6.1. Моделирование экзамена

Одним из инструментов моделирования дискретных процессов являются сети Петри и их модификации. Сети Петри широко используют для решения различных задач, и данный аппарат продолжает активно развиваться (см., например, статьи в журналах «Программирование» и «Известия РАН. Теория и системы управления»). Он позволяет описывать параллельные, асинхронные, иерархические процессы достаточно простыми средствами. Математическая модель описываемого сетью Петри процесса достаточно наглядна и легко алгоритмизируема для моделирования на ЭВМ.

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

Такая модификация сетей Петри, как временные сети, позволяет в явном виде ввести в процесс имитации время протекания действий, например, интервал прихода студентов, время подготовке к ответу и т.д.

Другое добавление к сети Петри  специальные вершины, служащие для оперативного управления объектом. Их маркировку можно изменять нажатием соответствующих клавиш.

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

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

Функционирование системы описывается последовательной сменой ее состояний, т.е. последовательной сменой маркировок. Изменение маркировки в позициях сети может произойти только при выполнении некоторого перехода, т.е. при выполнении некоторого действия на экзамене или при изменении пользователем маркировки управляющих вершин.

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

Начальная маркировка сети по умолчанию равна (0, 0, 0, 0, 0, 40, 8, 1, 0, 0, 0, 0, 0, 2, 1) при просмотре слева направо и сверху вниз по схеме. Процесс имитации продолжается до тех пор, пока все студенты не будут опрошены, что соответствует маркировке ( 0, 0, 0, 0, 40, 0, …)

Таблица 6.1

Имя	Название	Описание
	Места и начальная	маркировка
p1	Студенты в коридоре (Очередь 1) = 0	Количество студентов, пришедших на экзамен и стоящих за дверью, так как нет вакантных мест или аудитория закрыта
p2	Студенты готовятся = 0	Количество студентов, вошедших в аудиторию и начавших готовиться
p3	Студенты, готовые отвечать (Очередь 2) = 0	Количество студентов, готовых к ответу и ждущих, когда освободится один из преподавателей
p4	Отвечающие студенты = 0	Количество отвечающих студентов и занятых преподавателей
p5	Ответившие студенты = 0	Количество студентов, уже сдавших экзамен. Экзамен заканчивается, когда экзамен сдали все студенты группы
p6	Студентов в группе (еще не пришли) <= 100	Количество студентов, которые должны прийти на экзамен. В начале моделирования равняется количеству студентов в группе, в конце 0
p7	Вакантных мест = 10  p14 <= 10	В начале моделирования количество одноместных парт в аудитории, которые могут одновременно быть заняты. В процессечисло вакантных мест. Регулируется управляющими местамиp10 иp11
p8	Свободных преподавателей = 2 p15 <= 2	В начале число преподаваелей на экзамене. В процессеколичество преподавателей, находящихся в аудитории и не занятых опросом студентов
p9	Открыть/Закрыть аудиторию (Действие 1) = 0 <= 1	Управляющая позиция для ограничения прохода в аудиторию студентов. При нажатии на клавишу пробела "SPACE"закрывает либо открывает дверь
p10	Уменьшить (Действие 2) = 0 <= 1	Управляющая позиция для регулирования длины очереди готовых к ответу студентов. При нажатии на клавишу управления курсором "DOWN" маркируется единицей
p11	Увеличить (Действие 3) = 0 <= 1	Управляющая позиция для регулирования очереди к преподавателю готовых к ответу студентов. При нажатии на клавишу управления курсором "UP" маркируется единицей
p12	Уменьшить (Действие 4) = 0 <= 1	Управляющая позиция для регулирования количества экзаменаторов в аудитории. При нажатии на клавиши "CTRL" + "DOWN" маркируется единицей
p13	Увеличить (Действие 5) = 0 <= 1	Управляющая позиция для регулирования количества экзаменаторов в аудитории. При нажатии на клавиши "CTRL" + "UP" маркируется единицей
p14	Запасные места = 10  p7 <= 10	Количество парт в аудитории, которые должны оставаться свободными
p15	Отдыхающие преподаватели = 2p8 <= 2	Количество преподавателей вне аудитории, которых можно позвать принимать экзамен
		Продолжение табл. 6.1
Имя	Название	Описание
	Переходы
t1	Приход студента	Выполняется, если есть еще не пришедшие студенты, и переход не занят. Интервал прихода студентов вычисляется следующим образом. Первые три приходят с интервалами 0.01, 0.02 и 0.01 часа, вторые четыре с интервалами от 0.02 до 0.10 часа, третьи три с интервалами 0.03, 0.04 и 0.08, а остальные с интервалами, получаемыми с помощью генератора случайных чисел по экспоненциальному закону со средним 0.2 на интервале от 0.0 до 0.5 часа
t2	Вход в аудиторию	Выполняется, если дверь в аудиторию открыта и есть вакантные места. Длительность = 0.0
t3	Подготовка к ответу	Выполняется по приходу студента в аудиторию в течение интервала времени, получаемому с помощью генератора псевдослучайных чисел по нормальному закону со математическим ожиданием = 0.4 часа (24 мин) и дисперсией = 0.1 (6 мин) в диапазоне от 0.1 (6 мин) до 0.6 часа (36 мин)
t4	Студент идет отвечать	Выполняется при наличии свободного преподавателя и готового отвечать студента. При этом освобождается вакантное место. Длительность = 0.0
t5	Студент отвечает	Выполняется при наличии отвечающего студента. Длительность ответа вычисляется с помощью генератора псевдослучайных чисел по равномерному закону распределения на интервале от 0.1 (6 мин) до 0.3 часа (18 мин)
t6	Уменьшение вакантных мест в аудитории	Выполняется при наличии вакантных мест и маркированном управляющем месте уменьшения вакантных мест. Длительность = 0.0
t7	Увеличение вакантных мест в аудитории	Выполняется при наличии запасных мест и маркированном управляющем месте увеличения вакантных мест. Длительность = 0.0
t8	Уменьшение количества преподавателей в аудитории	Выполняется при наличии свободных преподавателей в аудитории и маркированном управляющем месте уменьшения количества экзаменаторов. Длительность = 0.0
t9	Увеличение количества преподавателей в аудитории	Выполняется при наличии отдыхающих преподавателей и маркированном управляющем месте увеличения количества экзаменаторов. Длительность = 0.0

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

В модели экзамена имеется четыре типа ресурсов (табл. 6.2), более подробно описанных в комментариях к их параметрам.

Таблица 6.2

Тип ресурса	Описание
Экзамены	Постоянный ресурс, отражающий общее состояние экзамена
Преподаватели	Постоянный ресурс, отражающий состояние преподавателя
Парты	Постоянный ресурс, отражающий состояние мест в аудитории (для анимации)
Студенты	Временный ресурс, отражающий состояние пришедшего на экзамен студента до конца его нахождения на экзамене

Файл типов ресурсов Examen.trp имеет вид:

$Resource_type Экзамены : permanent

$Parameters

Состояние : (Подготовка, Управление, Проходит) = Подготовка

{Подготовка - установка начальных значений параметров;}

{Управление - изменение параметров, открытие двери;}

{Проходит - после начала экзамена}

{Вершины сети Петри:}

Вершина1 : integer [0..1] = 0 {Открыть/Закрыть аудитории}

Студентов : integer [0..100] = 40 {Cтудентов в группе}

Очередь1 : such_as Экзамены.Студентов = 0

{Число студентов в коридоре}

Очередь2 : such_as Экзамены.Студентов = 0 {Студенты,

готовые отвечать}

Отвечающие : such_as Экзамены.Студентов = 0 {Отвечающие

студенты | занятые преподаватели}

Ответившие : such_as Экзамены.Студентов = 0 {Ответившие

студенты}

{Ограничение количества студентов в аудитории }

Свободные_места : integer [0..10] = 10

Уменьшить_мест : such_as Экзамены.Свободные_места = 0

Увеличить_мест : such_as Экзамены.Свободные_места = 0

Запасные_места : such_as Экзамены.Свободные_места = 0

{Регулирование количества преподавателей}

Свободные_препод : integer [0..2] = 2

Уменьшить_препод : such_as Экзамены.Свободные_препод = 0

Увеличить_препод : such_as Экзамены.Свободные_препод = 0

Отдыхающие_препод : such_as Экзамены.Свободные_препод = 0

Идет : integer [0..1] {Очередной студент идет на экзамен}

$End

$Resource_type Преподаватели : permanent

$Parameters

Номер : such_as Экзамены.Свободные_препод

Состояние : (Занят, Принимает, Свободен, Отдыхает)

Номер_студента : such_as Экзамены.Студентов = 0

$End

$Resource_type Парты : permanent

$Parameters

Состояние : (Свободна, Занята)

Номер : integer [1..10]

Номер_студента : such_as Экзамены.Студентов = 0

$End

$Resource_type Студенты : temporary

$Parameters

Номер : such_as Экзамены.Студентов

Состояние : (Пришел, Готовится, Готов, Отвечает, Ответил)

Время_прихода : real = 0.0

Время_входа : real = 0.0

Время_конца_подготовки : real = 0.0

Время_начала_ответа : real = 0.0

Время_ухода : real = 0.0

$End

Операции и правила модели описывают, по большей части, функционирование сети Петри.

Файл описания операций Еxamen.opr имеет вид:

$Operations

{Задание начальных установок по константам}

Начальные_установки : Образец_Начальные_установки

{Управление}

{Команда открыть аудиторию}

Начать_экзамен : Образец_Начать_экзамен 'SPACE'

{Команда уменьшить max количество студентов в ауд.}

Уменьшить_места : Образец_Уменьшить_места 'DOWN'

{Уменьшение max количества студентов в ауд.}

Уменьшение_мест : Образец_Уменьшение_вакантных_мест

{Команда увеличить max количество студентов в ауд.}

Увеличить_места : Образец_Увеличить_места 'UP'

{Увеличение max количества студентов в ауд.}

Увеличение_мест : Образец_Увеличение_вакантных_мест

{Команда уменьшить количество преподавателей в ауд.}

Выйти_преподавателю :

Образец_Уменьшить_количество_препод 'CONTROL' + 'DOWN'

{Уменьшение количества преподавателей в ауд.}

Уход_преподавателя : Образец_Уменьшение_количества_препод

{Команда увеличить количество преподавателей в ауд.}

Прийти_преподавателю :

Образец_Увеличить_количество_препод 'CONTROL' + 'UP'

{Увеличение количества преподавателей в ауд.}

Приход_преподавателя : Образец_Увеличение_количества_препод

{Приход студента по экспоненциальному закону}

Приход_студента : Образец_Приход_студента

{Подготовка студента с нормальным распределением времени}

Вход_и_подготовка : Образец_Вход_и_подготовка

{Следующий студент идет отвечать}

Идти_отвечать : Образец_Идет_отвечать

{Студент отвечает с равномерным распределением времени ответа}

Отвечает : Образец_Студент_отвечает

{Сдавший экзамен студент покидает аудиторию}

Сдал : Образец_Уход_студента

$End

Интерактивные операции по управлению прохождения экзамена связаны не только с клавишами клавиатуры, но и имеют соответствующие активные области на каждом из двух графических кадров, изображенных на рис. 6.1 и 6.2. На первом кадре этими областями являются соответствующие позиции сети Петри, а на втором  изображение двери (открытой или закрытой) и треугольные кнопки увеличения и уменьшения количеств преподавателей и вакантных мест. Кадры можно сменять через список кадров.

После построения модели был проведен ряд экспериментов для выяснения оптимального количества вакантных мест в аудитории при приеме экзамена двумя и одним преподавателем. Оптимальным количеством мест будем считать такое их количество, при котором очередь к преподавателю составляет не более 2 человек.

Рис.6.1. Первый кадр анимации

Рис.6.2. Второй кадр анимации

В результате экспериментов (табл. 6.3 и 6.4) установлено, что при приеме экзамена двумя преподавателями экзамен длится около 4,5 часов, и должно быть занято 78 парт; а при приеме одним экзаменатором экзамен длится почти 9 часов, и необходимо 34 парты.

Таблица 6.3

Параметры \ Эксперименты	1	2	3	4	5	6
{Базы генераторов случ. Чисел:} Вторые_четыре.Seed = Экспоненц_интервал.Seed = Нормальное_распределение.Seed = Равномерное_распределение.Seed = { Диапазоны } Группа = { 1 ..100} Мест = { 0 ..10 } Преподавателей = { 0 .. 2 } {доля часа 0,1 = 6 минут} Приход_среднее = {0,0 .. 0,5 } Подгот_среднее = {0,1 .. 0,6 } Подгот_дисперсия = Ответ_min = Ответ_max =	123123 123123 123123 123123 40 9 2 0,2 0,4 0,1 0,1 0,3	998877 998877 998877 998877 40 9 2 0,2 0,4 0,1 0,1 0,3	123123 123123 123123 123123 40 8 2 0,2 0,4 0,1 0,1 0,3	998877 998877 998877 998877 40 8 2 0,2 0,4 0,1 0,1 0,3	123123 123123 123123 123123 40 7 2 0,2 0,4 0,1 0,1 0,3	998877 998877 998877 998877 40 7 2 0,2 0,4 0,1 0,1 0,3
Очередь_ к_преподавателю = Время_ожидания_преподавателя = {tзанят/tне_отдыхает :} Нагрузка_на_преподавателя_1 = Нагрузка_на_преподавателя_2 =	4,1769 0,4815 0,9008 0,8998	4,2341 0,4854 0,9241 0,8585	3,404 0,3914 0,9008 0,8998	3,4858 0,4007 0,9238 0,8651	2,6330 0,3051 0,9008 0,8998	2,6840 0,3111 0,9238 0,8651

Таблица 6.4

Параметры \ Эксперименты	1	2	3	4	5	6
Вторые_четыре.Seed = Экспоненц_интервал.Seed = Нормальное_распределение.Seed = Равномерное_распределение.Seed = Группа = { 1 ..100} Мест = { 0 ..10 } Преподавателей = { 0 .. 2 } {доля часа 0.1 = 6 минут} Приход_среднее = {0,0 .. 0,5 } Подгот_среднее = {0,1 .. 0,6 } Подгот_дисперсия = Ответ_min = Ответ_max =	123123 123123 123123 123123 40 5 1 0,2 0,4 0,1 0,1 0,3	998877 998877 998877 998877 40 5 1 0,2 0,4 0,1 0,1 0,3	123123 123123 123123 123123 40 4 1 0,2 0,4 0,1 0,1 0,3	998877 998877 998877 998877 40 4 1 0,2 0,4 0,1 0,1 0,3	123123 123123 123123 123123 40 3 1 0,2 0,4 0,1 0,1 0,3	998877 998877 998877 998877 40 3 1 0,2 0,4 0,1 0,1 0,3
Очередь_ к_преподавателю = Время_ожидания_преподавателя = {tзанят/tне_отдыхает :} Нагрузка_на_преподавателя_1 = Нагрузка_на_преподавателя_2 =	2,7600 0,6034 0,9473 0	2,8019 0,6005 0,9591 0	1,8867 0,4113 0,9473 0	1,9137 0,4121 0,9591 0	0,9917 0,2165 0,9403 0	1,0114 0,2269 0,9254 0