Математическое моделирование систем и процессов

Размещено на http://www.allbest.ru/

Федеральное агентство железнодорожного транспорта

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Российский университет транспорта» (МИИТ)

Кафедра: «Высшая математика и естественные науки»

Контрольная работа №1

Математическое моделирование систем и процессов

Москва 2017-2018



Задача №1

Полигон с четырьмя станциями А, Б, В и Г должен пропустить суточные объемы вагонопотоков N_АГ и N_БГ по заданному назначению в соответствии с нормативными показателями работы сортировочных парков на станциях А, Б и В.

Требуется:

1. Составить план формирования поездов.

2. Выполнить вероятностный анализ плана и рассмотреть возможные его варианты с учетом случайного характера суточных объемов вагонопотоков N_АГ и N_БГ.

Исходные данные	станция
Вагонно-часы простоя под накоплением, T = cm	А	800
	Б	1100
	В	800
Экономия от проследования станции без переработки, tэк, ч/ваг	Б	1
	В	6
Среднее квадратическое отклонение вагонопотоков, у		56
Параметр «a» в равномерном распределении		50
Среднесуточные вагонопотоки	АГ	250
	БГ	200
Законы распределения вагонопотоков	АГ	Н
	БГ	Э3

Примечания: 1.у - среднее квадратическое отклонение в нормальном законе распределения вагонопотока, 2. Условные обозначения законов распределения: Н - нормального, П - показательного, Р -равномерного, Э2, Э3, Э4 - Эрланга 2-, 3-, 4-го порядков.

Решение

1. Определим критическое значение вагонопотоков N_АГ и N_БГ:

2. Устанавливаем всевозможные варианты плана формирования поездов, соответствующие следующим случайным событиям:

3. Каждое из рассмотренных событий равносильно одновременному наблюдению соответствующих двух независимых событий. Поэтому из основания теоремы умножения вероятностей независимых событий получаем:

4. Определим вероятность реализации вариантов 1,2,3,4 плана формирования поездов, как вероятности случайных событий А₁, А₂, А₃, А₄ согласно заданным законам распределения вероятностей вагонопотоков

Согласно равномерному закону распределения:



Где разность границ

Согласно теореме сложения вероятностей противоположных событий:

Согласно показательному закону распределения:

Согласно теореме сложения вероятностей противоположных событий:

Используя полученные результаты, определяем:

5. События А₁, А₂, А₃, А₄ являются несовместимыми и составляют полную систему событий. На основании теоремы о вероятности суммы событий, составляющих полную систему при суммировании вероятностей событий А₁, А₂, А₃, А₄ должны получить 1:



Полученный результат свидетельствует о правильности выполненного вероятностного анализа плана формирования поездов в соответствии с исходными данными примера.

6. Вариант 4, соответствующий событию А₄, предусматривает организацию вагона потока через станцию Б и В и вагонопотока через станцию В с переработкой, без сквозного назначения. Однако в силу случайного характера вагонопотоков их величины могут быть таковыми, что возможны два несовместимых подварианта 4:

Если имеет место подвариант 4б, то открывается возможность сформировать на станции Б суммарный вагонопоток , который проходит сквозным назначением через попутную станцию В до станции Г.

7. Определим вероятности Р(4а) и Р(4б)) подвариантов 4а и 4б.

7.1 согласно анализу события А₄ с помощью рис.1.1 имеем два случая.

Случай 1:

Разобьем треугольник события 4а и 4б трапеции, которые заменим равными по площади прямоугольниками 1,2,3,4.

Используя заданные в условии задачи законы распределения определим вероятности событий, которые являются площадями соответствующих прямоугольников:

Вероятности, соответствующие основанию прямоугольникам определяются по равномерному закону распределения:

Тогда

математический моделирование вагонопоток

Вероятности, соответствующие высотам прямоугольников, рассчитываются по показательному закону распределения:

Вероятность подварианта 4а:

Случай 2:

Вероятность подварианта 4б:

8.Строим схему полигона и варианты плана формирования поездов

Задача №2

На грузовой станции отправления формируются вагонопотоки на 2 назначения А и Б. Определить оптимальный ежесуточный объем вагонопотоков, обеспечивающий РЖД максимальную прибыль при доставке грузов к станциям назначения, если формирование осуществляется с помощью 3 технологических операций:

1) осмотр 1 вагона назначения А требует t₁₁ часа, назначения Б - t₁₂ часа,

2) формирование 1 вагона в вагонопоток назначения А - t₂₁ часа, назначения Б - t₂₂ часа,

3) погрузка 1 вагона назначения А - t₃₁ часа, назначения Б - t₃₂ часа.

Прибыль от доставки груза 1 вагоном на станцию назначения А составляет с₁, на станцию назначения Б - с₂ денежных единиц.

Технологические операции, t час/вагон	А	Б
Осмотр, t11 , t12	0,2	0,2
Формирование, t21 , t22	0,22	0,18
Погрузка, t31 , t32	0,24	0,16
Прибыль, с1, с2	14,3	13,3
Вагонопоток, х1, х2	52	66
Прибыль, СА, СБ	743,6	877,8
Общая прибыль на РЖД, С	1621,4

Решение

1. Математическая модель стандартного вида для данной задачи. Суммарная прибыль:

Общее время проведения i-ой технологической операции:



Где b - заданное время формирования объема вагонопотоков, b=24 часа.

Максимальное значение целевой функции:

Запишем уравнения математической модели для конкретной задачи согласно уравнениям (2.1),(2.2),(2.3)

2. Введем балансовые переменные

Обращая неравенства (2.5) в равенства

3. Исследуем систему (2.7) на совместимость. Поскольку ранг матрицы А и расширенной матрицы равны и меньше числа n=5



То в соответствии с теоремой Кронекера-Капелли систему (2.7) является совместной и неопределенной, базисных переменных 3, свободных 2.

4. Для поиска оптимального решения симплексным методом представим выражения (2.4) и (2.7) в базисной допустимой форме согласно условиям:

1) в каждом выражении (2.7) должна входить только базисная переменная с коэффициентом ;

2) свободные числа системы уравнений (2.7) должны быть неотрицательными;

3) целевая функция (2.4) должна быть выражена только через свободные переменные.

В качестве базисных переменных принимаем переменные, а свободных - Х₁, Х₂, тогда выражения (2.4) и (2.7) соответствуют условия базисной допустимой формы и позволяют получить 1-е базисное допустимое решение поставленной задачи при равенстве нулю свободных переменных

Х₁=(0,0,24,24,24) (2.8)

f(Х₁)=0 (2.9)

Решение (2.8) и (2.9) - опорное.

5. Перейдем к новой базисной допустимой форме и получим на ее основное новое базисное допустимое решение, улучшающее значение целевой функции f(Х).

1) в системе (2.7) выразим базисные переменные через свободные переменные



2) пусть х₁?0, х₂=х₃=х₄=х₅=0:

Тогда min (120,109,100)=100=Х_1min при х₅=0.

Получаем новые свободные переменные х₂=0 и х₅=0 и новые базисные переменные х₁?0, х₃?0, х₄?0.

3)Из уравнения (2.10) выразим х₁ через х₂ и х₅.

И подставим в (2.10) и (2.4)

Получим новую базисную форму:



4) Из уравнения (2.11) и (2.12) получим 2-е базисное решение при х₂=х₅=0

Вывод: из (2.12) видно, что при увеличении х₂ целевая функция f(Х) увеличивается, при увеличении х₅ - уменьшается, поэтому принимаем х₅=0, х₂?0 и находим допустимое значение х₂.

6. От базисной допустимой формы (2.11), (2.12) перейдем к новой базисной форме:

1) пусть х₂?0, х₁=х₃=х₄=х₅=0

Тогда min(149,67,57)=57=Х_2min при х₃=0.

Получаем новые свободные переменные х₃=0 и х₅=0 и новые базисные переменные х₁?0, х₂?0, х₄?0.

2) Из уравнения (2.11а) выразим х₂ через х₃ и х₅

И подставим в (2.11б), (2.11в) и (2.12)

Получим новую базисную форму:

4) из уравнения (2.14) и (2.15) получим 3-е базисное решение при

Вывод: из (2.15) видно, что при увеличении х₃,х₅ уменьшается f(Х).

Симпликс процесс завершен.

Ответ: при объеме суточного вагонопотока х₁=52, включенного в назначение А, и х₂=66 вагона, включенного в назначение Б, РЖД получит максимальную прибыль f(Х)=1621,4 денежных единиц. Графическое решение задачи представлено на рис 2.1.

Задача №3

Задана матрица транспортной сети G(X, U, C(U)). Построить диаграмму и найти максимальный поток и минимальный разрез. (1,2)4, (1,4)6, (1,6)12, (2,3)3, (2,5)3, (2,7)7, (3,7)2, (4,2)3,(4,6)3, (4,7)1,(5,6)2, (6,7)5

Решение

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

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

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

4. Согласно порядку применения алгоритма вначале по графу (рис.3.1) или по матрице С (табл.3.1) произвольно выбираем один из путей от вершины входа х₁ к вершине выхода х₇. Рассмотрим путь S₁(С). Пропускная способность пути S₁. Р₁=min(4,3,2)=2



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

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		4		6		12
Х2			3		3		7
Х3							2
Х4		3				3	1
Х5						2
Х6							5

5. В матрице С (табл.3.1) из значений пропускных способностей (4,3,2) дуг пути S₁ вычтем Р₁= 2, получив матрицу С₁ (табл.3.2). В преобразованной транспортной сети определена избыточная пропускная способность S₁

Таблица 3.2 - Матрица С₁

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		2		6		12
Х2			1		3		7
Х3							0
Х4		3				3	1
Х5						2
Х6							5

5. По матрице С₁ (таблице.3.2) произвольно выбираем один из путей от вершины входа к вершине выхода. Рассмотрим путь . Его пропускная способность Р₂=min(2,7)=2

В матрице С₁ (табл.3.2) из значений пропускных способностей дуг пути S₂(С₁) вычтем Р₂=2, получим новую матрицу С₂(табл.3.3)



Таблица 3.3 - Матрица С₂

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		0		6		12
Х2			1		3		5
Х3							0
Х4		3				3	1
Х5						2
Х6							5

6. По матрице С₂ (таблице.3.3) произвольно выбираем один из путей от вершины входа к вершине выхода. Рассмотрим путь . Его пропускная способность Р₃=min(6,3,7)=3

В матрице С₂ (табл.3.3) из значений пропускных способностей дуг пути S₇(С₁) вычтем Р₃=3, получим новую матрицу С₃(табл.3.4)

Таблица 3.4 - Матрица С₃

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		0		3		12
Х2			1		3		2
Х3							0
Х4		0				3	1
Х5						2
Х6							5

8. По матрице С₃ (таблице.3.4) произвольно выбираем один из путей от вершины входа к вершине выхода. Рассмотрим путь . Его пропускная способность Р₄=min(3,3,5)=3

В матрице С₃ (табл.3.4) из значений пропускных способностей дуг пути S (С₃) вычтем Р₄=3, получим новую матрицу С₄(табл.3.5)



Таблица 3.5 - Матрица С₄

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		0		0		12
Х2			1		3		2
Х3							0
Х4		0				0	1
Х5						2
Х6							2

7. По матрице С₄ (таблице.3.5) произвольно выбираем один из путей от вершины входа к вершине выхода. Рассмотрим путь . Его пропускная способность Р₅=min(12,2)=2

В матрице С₄ (табл.3.5) из значений пропускных способностей дуг пути S (С₄) вычтем Р₅=2, получим новую матрицу С₅(табл.3.6)

Таблица 3.6 - Матрица С₅

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		0		0		10
Х2			1		3		2
Х3							0
Х4		0				0	1
Х5						2
Х6							0

Так как в строке 1остались данные, но новые пути из точки 1 невозможны. Максимально возможный поток

Рmax=Р₁+Р₂+Р₃+Р₄+Р₅=2+2+3+3+2=12.

Вычтем из элементов матрицы С элементы матрицы С₅ получив матрицу С₆ (табл.3.7)



Таблица 3.7 - Матрица С₆

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		4		6		2
Х2			2		0		5
Х3							2
Х4		3				3	0
Х5						0
Х6							5

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

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

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

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

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

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



Р'₁=min(4,7)=4

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

Таблица 3.8 - Матрица С'₁

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		0		6		12
Х2			3		3		3
Х3							2
Х4		3				3	1
Х5						2
Х6							5

Р'₂=min(6,1)=1

Таблица 3.9 - Матрица С'₂

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		0		5		12
Х2			3		3		3
Х3							2
Х4		3				3	0
Х5						2
Х6							5

Р'₃=min(5,3,3,2)=2

Таблица 3.10 - Матрица С'₃

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		0		3		12
Х2			1		3		3
Х3							0
Х4		1				3	0
Х5						2
Х6							5

Р'₄=min(3,3,5)=3

Таблица 3.11 - Матрица С'₄

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		0		0		12
Х2			1		3		3
Х3							0
Х4		1				0	0
Х5						2
Х6							2

Р'₅=min(12,2)=2

Таблица 3.12 - Матрица С'₅

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		0		0		10
Х2			1		3		3
Х3							0
Х4		1				0	0
Х5						2
Х6							0

Так как в строке 1 остались данные, но новые пути из точки 1 невозможны. Максимально возможный поток



Р'max=Р'₁+Р'₂+Р'₃+Р'₄+ Р'₅=4+1+2+3+2=12.

Вычтем из элементов матрицы С элементы матрицы С'₄ получив матрицу С'₅ (табл.3.13)

Таблица 3.13 - Матрица С'₅

Конец Начало	Х1	Х2	Х3	Х4	Х5	Х6	Х7
Х1		4		6		2
Х2			2		0		4
Х3							2
Х4		2				3	1
Х5						0
Х6							5

Строим граф движения, реализовавшего величину максимального потока (рис.3.3)

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

Размещено на Allbest.ru