Контрольная работа: Экономико-математическое моделирование

1. Графы

Задание 1.1

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

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

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

Решение:

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

Ст. V₁ =3

Ст. V₂ =3

Ст. V₃ =3

Ст. V₄ =3

Ст. V₅ =2

Ст. V₆ =2

Матрица смежности графа

Задание 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.

Решение:

Окрасила вершину V1. d(V1) = 0, d(x) = для любого x V1 и x = V1.

1. в (V2) = 4

d (V3) = 6

d (V4) = 3 – наименьшее; закрашиваю вершину V4 и дугу (V1, V4) или (V4, V2)

y = V4

2. в (V2) = 4 – наименьшее; закрашиваю вершину V2 и дугу (V1, V2)

d (V3) = 6

d (V5) = min (6; 3+3) = 6

d (V6) =

y = V2

3. в (V3) = 6 – наименьшее; закрашиваю вершину V3 и дугу (V2, V3)

d (V5) = 6

d (V6) =

y = V3

4. в (V5) = 6 – наименьшее; закрашиваю вершину V5 и дугу (V4, V5)

d (V6) = min (8; 6+2) = 8

y = V5

5. в (V6) = 8 – закрашиваю вершину V6 и дугу (V5, V6)

Кратчайший путь

V1 V3 V6.

Покрывающее дерево:

2. Сетевое планирование

Задание 2.1

1. Для задачи планирования поставки товаров оптовым покупателям построить сетевой график, привязанный к оси времени, согласно структурно-временной таблицы. Задание конкретного варианта расположено в одной из пяти правых колонок таблицы.

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 ₃ – среднее число занятых ЭВМ.

Решение:

Интенсивность потока обслуживаний = = = 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 машин для их ожидания в очереди. На станцию прибывает в среднем λ машин в минуту. Среднее время заправки одной машины мин. Требуется определить вероятность отказа Р_отк и среднюю длину очереди М_ож .

Решение:

= 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,В1); (А3,В1); (А1,В3); (А3,В3). V (цена игры) = 1.

Задание 4.2

1. Решить игру.

Указание: использовать принцип доминирования.

Решение:

Задание 4.3

1. Решить игру 2 х n графическим методом.

Решение:

B – верхняя цена игры

А = (0,4;0,6)

= 1.

5. Список литературы

1. Н. Ш. Кремер, Б. А. Путко, И. М. Тришин, М. Н. Фридман. Исследование операций в экономике: Учебн. Пособие для вузов/ Под ред. проф. Н. Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 1997.

2. Е. В. Бережная, В. И. Бережной. Математические методы моделирования экономических систем: Учеб. пособие. – М.: Финансы и статистика, 2001.

3. Лабскер Л. Г., Бабешко Л. О. Игровые методы в управлении экономикой и бизнесом: Учеб. пособие. – М.: Дело, 2001. – 464 с.

4. Шикин Е. В., Чхартишвили А. Г. Математические методы и модели в управлении: Учеб. пособие. - М.: Дело, 2000. – 440 с.

5. Шапкин А.С., Мазаев Н.П. Математические методы и модели исследования операций: Учебник. – М.: Издательско-торговая корпорация "Дашков и К", 2004.