1. Нагрузить граф задания 1.1. согласно матрице длин дуг и нарисовать.
2. По алгоритму окрашивания найти кратчайший путь между вершинами V1 и V6.
3. Построить покрывающее дерево с корнем в вершине V1.
Х1
Х2
Х3
Х4
Х5
Х6
V1
4
6
3
V2
4
3
2
V3
6
3
2
V4
3
2
3
V5
3
2
V6
2
0
Решение:
Окрасила вершину V1. d(V1) = 0, d(x) =
для любого x
V1 и x = V1.
1. d (V2) = 4
d (V3) = 6
d (V4) = 3 – наименьшее; закрашиваю вершину V4 и дугу (V1, V4) или (V4, V2)
y = V4
2. d (V2) = 4 – наименьшее; закрашиваю вершину V2 и дугу (V1, V2)
d (V3) = 6
d (V5) = min (6; 3+3) = 6
d (V6) =
y = V2
3. d (V3) = 6 – наименьшее; закрашиваю вершину V3 и дугу (V2, V3)
d (V5) = 6
d (V6) =
y = V3
4. d (V5) = 6 – наименьшее; закрашиваю вершину V5 и дугу (V4, V5)
d (V6) = min (8; 6+2) = 8
y = V5
5. d (V6) = 8 – закрашиваю вершину V6 и дугу (V5, V6)
Кратчайший путь
V1
V3
V6.
Покрывающее дерево:
2. Сетевое планирование
Задание 2.1
1. Для задачи планирования поставки товаров оптовым покупателям построить сетевой график, привязанный к оси времени, согласно структурно-временной таблицы. Задание конкретного варианта расположено в одной из пяти правых колонок таблицы.
Содержание работ
Работа
Длитель-ность, ti
Коэффициент, сi
Обозначение, аi
Опорная, аj
отбор товара
0,1
a1
-
2
подготовка к отправке
0,2
a2
a1
3
выписка накладных
0,3
a3
a2
1
определение объема отгрузки
0,4
a4
a3
1
проверка цен
0,5
a5
a3
1
оформления счета
0,6
a6
a5
1
заказ автомашин для перевозки товара
0,7
a7
a4
а6
3
отправка счета покупателю
0,8
a8
a4
а6
1
проверка товара по счету
0,9
a9
a7
2
оплата счета
1
a10
a8
12
погрузка товара и проверка кол-ва
1,1
a11
a9
а10
2
перевозка товара
1,2
a12
a11
4
выгрузка и сверка с документами
1,3
a13
a12
4
2. Вычислить временные параметры сетевой модели.
3. Построить критический путь, вычислить критическое время, нанести критический путь на сетевой график.
Решение:
tij
– время выполнения работ;
Tp
– ранний срок наступления события;
K – номер вершины, при движении из которой было получено значение Tp;
Tп
– поздний срок наступления события;
Rij
– полный резерв времени;
rij
– свободный резерв времени.
- критический путь.
Резервы нашла по формуле:
Rij
=
- Ti
- tij
rij
=
-
- tij
На критическом пути резервов времени нет.
3. Система массового обслуживания (СМО)
Задание 3.1
Решить задачу для СМО с отказами:
В вычислительный центр с m ЭВМ поступают заказы на вычислительные работы. Если работают все m ЭВМ, то вновь поступающий заказ не принимается. Пусть среднее время работы с одним заказом составляет часов. Интенсивность потока заявок равна λ (1/ч). Найти вероятность отказа Ротк
и m3 – среднее число занятых ЭВМ.
Вероятность отказа (когда заняты три ЭВМ), таким образом, Ротк
= р3
= 0,033.
Относительная пропускная способность центра: Q = 1 - Ротк
; Q = 1 – 0,033 = 0,967, т. е. в среднем из каждых 100 заявок вычислительный центр обслуживает 96,7 заявок.
Абсолютная пропускная способность центра А = λ Q; А = 0,25 * 0,967 = 0,242, т. е. в один час в среднем обслуживается 0,242 заявки.
Среднее число занятых ЭВМ:
= А /
;
= 0,242 / 0,033 = 0,725, т. е. каждая из трех ЭВМ будет занята обслуживанием заявок в среднем лишь на 72,5 / 3 = 24,2%.
Задание 3.2
Решить задачу для СМО с ограниченной длиной очереди:
На автозаправочной станции установлены m колонок для выдачи бензина. Около станции находится площадка на L машин для их ожидания в очереди. На станцию прибывает в среднем λ машин в минуту. Среднее время заправки одной машины мин. Требуется определить вероятность отказа Ротк
и среднюю длину очереди Мож
.
1. Н. Ш. Кремер, Б. А. Путко, И. М. Тришин, М. Н. Фридман. Исследование операций в экономике: Учебн. Пособие для вузов/ Под ред. проф. Н. Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 1997.
2. Е. В. Бережная, В. И. Бережной. Математические методы моделирования экономических систем: Учеб. пособие. – М.: Финансы и статистика, 2001.
3. Лабскер Л. Г., Бабешко Л. О. Игровые методы в управлении экономикой и бизнесом: Учеб. пособие. – М.: Дело, 2001. – 464 с.
4. Шикин Е. В., Чхартишвили А. Г. Математические методы и модели в управлении: Учеб. пособие. - М.: Дело, 2000. – 440 с.
5. Шапкин А.С., Мазаев Н.П. Математические методы и модели исследования операций: Учебник. – М.: Издательско-торговая корпорация "Дашков и К", 2004.