Экономико-математическое моделирование

1. Графы

Задание 1.1

1. Охарактеризовать граф.

2. Выписать матрицу смежности графа.

3. Вычислить степени вершин.

Решение:

Данный граф является неографом, так как его ребра не ориентированные и не имеют начало и конец.

Ст. V₁ =3

Ст. V₂ =3

Ст. V₃ =3

Ст. V₄ =3

Ст. V₅ =2

Ст. V₆ =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. По алгоритму окрашивания найти кратчайший путь между вершинами 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. Построить критический путь, вычислить критическое время, нанести критический путь на сетевой график.

Решение:

t_ij - время выполнения работ;

T_p - ранний срок наступления события;

K - номер вершины, при движении из которой было получено значение T_p;

T_п - поздний срок наступления события;

R_ij - полный резерв времени;

r_ij - свободный резерв времени.

- критический путь.

Резервы нашла по формуле:

R_ij = - T_i - t_ij

r_ij = - - t_ij

На критическом пути резервов времени нет.



3. Система массового обслуживания (СМО)

Задание 3.1

Решить задачу для СМО с отказами:

В вычислительный центр с m ЭВМ поступают заказы на вычислительные работы. Если работают все m ЭВМ, то вновь поступающий заказ не принимается. Пусть среднее время работы с одним заказом составляет часов. Интенсивность потока заявок равна л (1/ч). Найти вероятность отказа Р_отк и m₃ - среднее число занятых ЭВМ.

m	3
л	0,25
Тобсср	3

Решение:

Интенсивность потока обслуживаний = = = 0,33. Интенсивность нагрузки ЭВМ по формуле

р = ; р = = 0,75.

Предельные вероятности состояний:

р₀ = (1 + р + + … + + … + )^-1; р₀ = (1 + 0,75 + 0,75²/ 2! + 0,75³ / 3!)^-1 = 0,476 (нет ни одной заявки);

р_к = р^к / k! * р₀; р₃ = (0,75³ / 3!) * 0,476 = 0,033 (заняты три ЭВМ).

Вероятность отказа (когда заняты три ЭВМ), таким образом, Р_отк = р₃ = 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, тогда

р₀ = [ + * ]^-1 = [1 + 2 + 2² / 2! + 2³ / 3! + 2⁴ / 3*3! * ]^-1 0.122

Р_отк = P_m+L = * p₀ = (p/m)^L * (p^m/m!)*p₀ = (2/3)³ * (2³/3!) * 0.122 = 0.048;

М_ож = ⁱ = (0.122*2³/3!) * [2/3 + 2(2/3)² + 3*(2/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.