математическое моделирование. Задача 1 Полигон с четырьмя станциями А, Б, в и г должен пропустить суточные объемы вагонопотоков N

• Название: Задача 1 Полигон с четырьмя станциями А, Б, в и г должен пропустить суточные объемы вагонопотоков N
• Анкор: математическое моделирование
• Дата: 09.04.2022
• Размер: 0.51 Mb.
• Имя файла: 7_variant_matematicheskoe_modelirovanie.docx
• Тип: Задача; #457141
• страница: 3 из 3

ЗАДАЧА 4

Задана матрица транспортной сети G(X,U,C(U)).

Построить диаграмму и найти максимальный поток и минимальный разрез. Исходные данные:

G(X,U,C(U))
(1,2)	(1,4)	(2,3)	(2,5)	(2,7)	(3,6)	(4,3)	(4,5)	(4,7)	(5,6)	(6,7)
36	30	22	28	32	28	28	38	14	52	38

РЕШЕНИЕ

Транспортная сеть – сеть, характеризуемая следующими признаками:

1) имеет только одну вершину входа, называемую источником,

2) имеет только одну вершину выхода, называемую стоком,

3) Каждой дуге u_j U соответствует некоторое неотрицательное целое число с(u_j) ≥ 0, с(u_j) С(U), называемое пропускной способностью дуги.

Транспортная сеть является связанным графом без контуров и петель.

Связанный граф – граф, в котором для любых двух его вершин существует маршрут (путь), соединяющий эти вершины.
Задача определения максимального потока является одной из основных при анализе и синтезе транспортной сети, решается с помощью понятия «разрез сети » на основе теоремы Форда-Фалкерсона: в любой транспортной сети величина максимального потока от источника к стоку равна пропускной способности минимального разреза.
Ориентированным разрезом транспортной сети G(X,U,C(U)) называется множество дуг c началом в подмножестве вершин А и с концом в подмножестве вершин В

Пропускной способностью или величиной разреза С( ) называется сумма пропускных способностей дуг разреза транспортной сети.

1. 
   Построим граф транспортной сети в соответствии с заданной матрицей (рис. 3.1).
   

Рис. 3.1. Граф транспортной сети

2. 
   По графу составим возможные пути от вершины входа к вершине выхода
   

S1 = [(х₁;х₂)36; (х₂,х₇)32]

S2 = [(х₁;х₂)36; (х₂;х₃)22; (х₃;х₆)28; (х₆;х₇)38]

S3 = [(х₁;х₂)36; (х₂;х₅)28; (х₅;х₆)52; (х₆;х₇)38]

S4 = [(х₁;х₄)30; (х₄;х₇)14]

S5 = [(х₁;х₄)30; (х₄;х₃)28; (х₃;х₆)28; (х₆;х₇)38]

S6 = [(х₁;х₄)30; (х₄;х₅)38; (х₅;х₆)52; (х₆;х₇)38]

3. 
   Находим максимальный поток и минимальный разрез с помощью алгоритма Форда-Фалкерсона. Составим матрицу С пропускной способности дуг заданной транспортной системы (Таблица 3.1).
   

Таблица 3.1. Матрица С

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		36		30
Х2			22		28		32
Х3						28
Х4			28		38		14
Х5						52
Х6							38

Рассмотрим путь S1.

Пропускная способность пути S1.

P1 = min(36;32)=32.

В матрице С из значений дуг пути S1 вычтем Р1=32 получив матрицу С1 (Таблица 3.2).

Таблица 3.2. Матрица С1

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		4		30
Х2			22		28		0
Х3						28
Х4			28		38		14
Х5						52
Х6							38

Рассмотрим путь S2(C1)= [(1;2)4; (2;3)22; (3;6)28; (6;7)38].

P2(C1)=min(4;22;28;38)=4.

Преобразуем матрицу С1 в С2 вычтя P2=4 из значений дуг пути S2(C1).

Таблица 3.3. Матрица С2

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		0		30
Х2			18		28		0
Х3						24
Х4			28		38		14
Х5						52
Х6							34

Рассмотрим путь S4(C2)= [(1;4)30; (4;7)14].

P3(C2)=min(30;14)=14.

Преобразуем матрицу С2 в С3 вычтя P3=14 из значений дуг пути S3(C2).
Таблица 3.4. Матрица С3

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		0		16
Х2			18		28		0
Х3						24
Х4			28		38		0
Х5						52
Х6							34

Рассмотрим путь S5(C3)= [(1;4)16; (4;3)28; (3;6)24; (6;7)34].

P4(C3)=min(16;28;24;34)=16.

Преобразуем матрицу С3 в С4 вычтя P4=16 из значений дуг пути S4(C3).

Таблица 3.5. Матрица С4

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		0		0
Х2			18		28		0
Х3						8
Х4			12		38		0
Х5						52
Х6							18

Элементы первой строки равны нулю, процесс завершен.

Максимально возможный поток Pmax = P1+P2 + P3+P4 = 32+4+14+16=66.

Вычтем из элементов матрицы С элементы матрицы С4 получив матрицу С5.

Таблица 3.6. Матрица С5

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		36		30
Х2			4		0		32
Х3						20
Х4			16		0		14
Х5						0
Х6							20

Построим граф варианта движения, реализующего величину максимального потока (Рис.3.2).



Рис. 3.2. Граф варианта движения, реализующего величину максимального потока

4. Рассмотрим всевозможные разрезы на графе варианта движения и убедимся в том, что согласно теореме Форда-Фалкерсона величина максимального потока от источника к источнику равна пропускной способности минимального разреза транспортной сети с₁₇=43.

Поток в транспортной сети удовлетворяет требуемый условиям:

1) для любой дуги значение потока не превышает пропускной способности,

2) в каждой вершине соблюдается условие непрерывности потока.

В еличина разреза: 36+30=66.

Рис. 3.3. Минимальный разрез

5. Проверим результаты расчета, выбрав другой путь:

S6 = [(х₁;х₄)30; (х₄;х₅)38; (х₅;х₆)52; (х₆;х₇)38]

Р’₁=min(30;38;52;38)=30

Преобразуем матрицу С в С’₁

Таблица 3.8. Матрица С’1

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		36		0
Х2			22		28		32
Х3						28
Х4			28		8		14
Х5						22
Х6							8

Рассмотрим путь S3 (C’1)= [(х₁;х₂)36; (х₂;х₅)28; (х₅;х₆)22; (х₆;х₇)8].

P’2(C’1)=min(36;28;22;8)=8.

Преобразуем матрицу С’1 в С’2 вычтя P’2=8 из значений дуг пути S3(C’1).

Таблица 3.9. Матрица С’2

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		28		0
Х2			22		20		32
Х3						28
Х4			28		8		14
Х5						14
Х6							0

Рассмотрим путь S1(C’2)= [(х₁;х₂)28; (х₂,х₇)32].

P’3(C2)=min(28;32)=28.

Преобразуем матрицу С’2 в С’3 вычтя P’3=28 из значений дуг пути S’1(C’2).
Таблица 3.10. Матрица С’3

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		0		0
Х2			22		20		4
Х3						28
Х4			28		8		14
Х5						14
Х6							0

Остальные пути пройти невозможно. Решение найдено.

Максимально возможный поток Pmax = P’1+P’2 + P’3= 30+8+28=66.

Вычтем из элементов матрицы С элементы матрицы С’3 получив матрицу С’4.

Таблица 3.9. Матрица С’4

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		36		30
Х2			4		0		32
Х3						20
Х4			16		0		14
Х5						0
Х6							20

Вывод: Результаты расчета совпали с величинами максимального потока и минимального разреза при выполнении условия сохранения потока в промежуточных вершинах.

ЗАДАЧА 5

В депо по ремонту вагонов работает n=2 бригад. В среднем в течение дня поступает в ремонт λ=10 вагонов и при семичасовом рабочем дне каждая из бригад ремонтирует µ=2,5 вагонов. Рассматривая депо как систему массового обслуживания, требуется:

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

2. В случае неадекватности принять решение по управлению параметрами работы депо с целью приведения в соответствие с условиями применения описывающей математической модели, а именно, выбрать необходимый уровень значений n, λ, µ.

3. Рассчитать характеристики эффективности 1) среднее время ремонта 1-го вагона, 2) среднее время ожидания начала ремонта для каждого вагона, 3) среднюю длину очереди.

РЕШЕНИЕ

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

Имеем СМО с неограниченной очередью.

По условию: λ = 10 (ваг/смену), μ = 2,5, n = 2.



>1, следовательно, очередь будет расти до бесконечности.

Исходные данные не адекватны условиям модели СМО.

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

2. Примем решение по управлению параметрами работы депо с целью приведения в соответствии с условиями применения описывающее матмодель, а именно, увеличим число ремонтных бригад с 2-х до 5-ти.

Получим новые исходные данные:

n=5, =10, =2,5

тогда

3. Рассчитаем характеристики интенсивности.

3.1) среднее время ремонта 1-го вагона.



=0,4 рабочего дня или =2,8 час.

3.2) среднюю длину очереди.







вагона

3.3) среднее время ожидания начала ремонта для каждого вагона.



рабочего дня или =1,55 час.

Ответ: 1) Среднее время ремонта одного вагона равно 2 часа 48 минут;

2) Среднее время ожидания начала ремонта для каждого вагона равно 1 час 33 минуты;

3) Средняя длина очереди равна 2,22 вагона.