Главная страница
Навигация по странице:

  • ЗАДАЧА 5

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


    Скачать 0.51 Mb.
    НазваниеЗадача 1 Полигон с четырьмя станциями А, Б, в и г должен пропустить суточные объемы вагонопотоков N
    Анкорматематическое моделирование
    Дата09.04.2022
    Размер0.51 Mb.
    Формат файлаdocx
    Имя файла7_variant_matematicheskoe_modelirovanie.docx
    ТипЗадача
    #457141
    страница3 из 3
    1   2   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) Каждой дуге uj U соответствует некоторое неотрицательное целое число с(uj) ≥ 0, с(uj) С(U), называемое пропускной способностью дуги.

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

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

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

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




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

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

    S1 = [(х12)36; (х27)32]

    S2 = [(х12)36; (х23)22; (х36)28; (х67)38]

    S3 = [(х12)36; (х25)28; (х56)52; (х67)38]

    S4 = [(х14)30; (х47)14]

    S5 = [(х14)30; (х43)28; (х36)28; (х67)38]

    S6 = [(х14)30; (х45)38; (х56)52; (х67)38]

    1. Находим максимальный поток и минимальный разрез с помощью алгоритма Форда-Фалкерсона. Составим матрицу С пропускной способности дуг заданной транспортной системы (Таблица 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. Рассмотрим всевозможные разрезы на графе варианта движения и убедимся в том, что согласно теореме Форда-Фалкерсона величина максимального потока от источника к источнику равна пропускной способности минимального разреза транспортной сети с17=43.

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

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

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

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

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

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

    S6 = [(х14)30; (х45)38; (х56)52; (х67)38]

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

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

    Таблица 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)= [(х12)36; (х25)28; (х56)22; (х67)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)= [(х12)28; (х27)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 вагона.
    1   2   3


    написать администратору сайта