1. Графы
Задание 1.1
1. Охарактеризовать граф.
2. Выписать матрицу смежности графа.
3. Вычислить степени вершин.
Решение:
Данный граф является неографом, так как его ребра не ориентированные и не имеют начало и конец.
Ст. V1
=3
Ст. V2
=3
Ст. V3
=3
Ст. V4
=3
Ст. V5
=2
Ст. V6
=2
Матрица смежности графа
| Х1
|
Х2
|
Х3
|
Х4
|
Х5
|
Х6
|
Х7
|
Х8
|
|
| V1
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
| V2
|
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
| V3
|
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
| V4
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
| V5
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
| V6
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
Задание 1.2
1. По матрице инцидентности нарисовать граф.
2. Охарактеризовать граф.
3. Назвать специальные вершины графа.
4. Вычислить полустепени вершин.
5. Выписать цикл, цепь, простой цикл, простую цепь.
Решение:
Данный граф называется орграфом, так как его ребра ориентированы и имеют начало и конец.
V4 и V6 – висячие вершины;
V5 – изолированная вершина.
Полустепень захода: V2 = 1; V3 = 3; V4 = 1; V6 = 1.
Полустепень исхода: V1 = 3; V2 = 1; V3 = 2.
Цепь:
Х1 Х2 Х6 Х3
Х5 Х6 Х3
Простая цепь:
Х1 Х2 Х3
Х5 Х3
Цикл: ????
V3 V3
Простой цикл: ????
V3 V3
Задание 1.3
1. Нагрузить граф задания 1.1. согласно матрице длин дуг и нарисовать.
2. По алгоритму окрашивания найти кратчайший путь между вершинами
V
1 и
V
6.
3. Построить покрывающее дерево с корнем в вершине
V
1.
| Х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
|
3 |
| отправка счета покупателю |
0,8 |
a8
|
a4
|
1 |
| проверка товара по счету
d>
|
0,9 |
a9
|
a7
|
2 |
| оплата счета |
1 |
a10
|
a8
|
12 |
| погрузка товара и проверка кол-ва |
1,1 |
a11
|
a9
|
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/ч). Найти вероятность отказа Ротк
и
m
3
– среднее число занятых ЭВМ.
| m |
3 |
| λ |
0,25 |
| Тобс
|
3 |
Решение:
Интенсивность потока обслуживаний = = = 0,33. Интенсивность нагрузки ЭВМ по формуле
р = ; р = = 0,75.
Предельные вероятности состояний:
р0
= (1 + р + + … + + … + )-1
; р0
= (1 + 0,75 + 0,752
/ 2! + 0,753
/ 3!)-1
= 0,476 (нет ни одной заявки);
рк
= рк
/ k! * р0
; р3
= (0,753
/ 3!) * 0,476 = 0,033 (заняты три ЭВМ).
Вероятность отказа (когда заняты три ЭВМ), таким образом, Ротк
= р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
машин для их ожидания в очереди. На станцию прибывает в среднем λ машин в минуту. Среднее время заправки одной машины
мин. Требуется определить вероятность отказа Ротк
и среднюю длину очереди Мож
.
| m |
3 |
| L |
3 |
| λ |
2 |
|
|
1 |
Решение:
= 1 / = 1 мин.
Нахожу:
р = λ / = 2 / 1 = 2, р / m = 2 / 3, тогда
р0
= [ + * ]-1
= [1 + 2 + 22
/ 2! + 23
/ 3! + 24
/ 3*3! * ]-1
0.122
Ротк
= Pm
+
L
= * p0
= (p/m)L
* (pm
/m!)*p0
= (2/3)3
* (23
/3!) * 0.122 = 0.048;
Мож
= i
= (0.122*23
/3!) * [2/3 + 2(2/3)2
+ 3*(2/3)3
] = 0.35
Таким образом, Ротк
= 0,048, Мож
= 0,35 машины.
4. Игры
Задание 4.1
1. Решить игру в чистых стратегиях.
2. Выписать седловые точки.
3. Вычислить цену игры.
| В1
|
В2
|
В3
|
В4
|
|
| А1
|
1 |
4 |
1 |
2 |
| А2
|
0 |
5 |
0 |
3 |
| А3
|
1 |
3 |
1 |
3 |
Решение:
Седловые точки: (А1,В1); (А3,В1); (А1,В3); (А3,В3). V (цена игры) = 1.
Задание 4.2
1. Решить игру.
Указание: использовать принцип доминирования.
| В1 |
В2 |
В3 |
В4 |
В5 |
|
| А1 |
-2 |
1 |
3 |
0 |
1 |
| А2 |
-3 |
-4 |
2 |
-1 |
-4 |
| А3 |
1 |
-5 |
6 |
3 |
-5 |
| А4 |
-2 |
1 |
3 |
0 |
1 |
Решение:
Задание 4.3
1. Решить игру 2 х
n
графическим методом.
| В1 |
В2 |
В3 |
В4 |
|
| А1 |
-1 |
1 |
-1 |
2 |
| А2 |
0 |
-1 |
2 |
-2 |
Решение:
B – верхняя цена игры
А = (0,4;0,6)
= 1.
5. Список литературы
1. Н. Ш. Кремер, Б. А. Путко, И. М. Тришин, М. Н. Фридман. Исследование операций в экономике: Учебн. Пособие для вузов/ Под ред. проф. Н. Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 1997.
2. Е. В. Бережная, В. И. Бережной. Математические методы моделирования экономических систем: Учеб. пособие. – М.: Финансы и статистика, 2001.
3. Лабскер Л. Г., Бабешко Л. О. Игровые методы в управлении экономикой и бизнесом: Учеб. пособие. – М.: Дело, 2001. – 464 с.
4. Шикин Е. В., Чхартишвили А. Г. Математические методы и модели в управлении: Учеб. пособие. - М.: Дело, 2000. – 440 с.
5. Шапкин А.С., Мазаев Н.П. Математические методы и модели исследования операций: Учебник. – М.: Издательско-торговая корпорация "Дашков и К", 2004.