Решение потоковых задач с помощью Excel

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

Содержание

Задача 1

Задача 2

Задача 3

Задача 4

Список используемой литературы

Задача 1

На уровне значимости = 0,01 принять решение о целесообразности проведения капитального ремонта изделия железнодорожного транспорта по результатам его эксплуатации:

1) изделие эксплуатируется q раз, i = 1,…, q на p уровнях времени работы T, j = 1,…, p,

2) в каждом испытании подсчитываются, числа отказов nij,

3) результаты испытаний представлены в таблице при q = 5, p = 4.

Для принятия решения исследовать влияние времени работы изделия на число появления отказов nij. Использовать метод однофакторного дисперсионного анализа. программный экранный индикаторный

i	Т 1	Т 2	Т 3	Т 4
1	140	150	190	180
2	160	200	220	150
3	175	190	200	170
4	200	185	240	160
5	190	210	230	175

Решение. Данная задача сводится к проверке выдвигаемой нулевой гипотезы Н 0:. а 1= а 2=…= аm о равенстве математических ожиданий, осуществляемой в дисперсионном анализе. т.е. нужно проверить гипотезу о том, что на уровне значимости б = 0,05 (с надежностью 0,95) различие во времени работы изделия не оказывает существенное влияние на число отказов.

Имеем

i	Т 1	Т 2	Т 3	Т 4
1	140	150	190	180
2	160	200	220	150
3	175	190	200	170
4	200	185	240	160
5	190	210	230	175
Среднее,	173	187	216	167

Среднее по всей совокупности: = (173 + 187 + 216 + 167)/4 = 185,75.

Определим общую, факторную и остаточную суммы квадратов отклонений от среднего:

.

Разделив суммы квадратов на соответствующее число степеней свободы, получим общую, факторную и остаточную дисперсии:

Сравним факторную и остаточную дисперсии по критерию Фишера-Снедекора. Для этого найдем наблюдаемое значение в критерии:

.

Для уровня значимости б = 0,05, чисел степеней свободы 3 и 16 находим F_крит из таблицы распределения Фишера-Снедекора:

F_крит(0,05; 3; 16) = 3,24.

Так как F_набл > F_кр, то различие групповых средних значимое, следует отклонить нулевую гипотезу Н₀, т.е. время работы изделия оказывает существенное влияние на число отказов. Следовательно, целесообразно провести капитальный ремонт изделия железнодорожного транспорта.

Решим задачу с помощью Excel.

Введем в Excel данные для дисперсионного анализа:

Рис. 1.

Выполним команды: Сервис - Анализ - Однофакторный дисперсионный анализ.

Рис. 2.

В результате получим:

Рис. 3.

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

В столбце F критическое расположено F-критическое значение, рассчитываемое по числу степеней свободы и величине Альфа. F-статистика и F-критическое значение используют критерий Фишера-Снедекора.

Так как F-статистика больше F-критического значения, то можно утверждать, что различия между группами данных носят неслучайный характер. т.е. на уровне значимости б = 0,05 (с надежностью 0,95) нулевая гипотеза отвергается: время работы изделия оказывает существенное влияние на число отказов.

Задача 2

Имеются три пункта отправления однородного груза и пять пунктов его назначения. На пунктах отправления груз находится в количестве a₁ = 70, a₂ = 50, a₃ = 90, в пункты назначения требуется доставить соответственно b₁ = 10, b₂ = 40, b₃ = 70, b₄ = 20, b₅ = 70 груза. Известна стоимость перевозки единицы груза из каждого пункта отправления в каждый пункт назначения (матрица D). Найти такой план перевозок, при котором необходимо вывезти все запасы груза, полностью удовлетворить все потребности и обеспечить при этом минимум общих затрат на перевозку. Задачу решить методом потенциалов.

Решение.

Таблица 1

Потребители Базы	В1	В2	В3	В4	В5	Запасы
А1	8	4	5	1	3	70
А2	3	3	8	5	7	50
А3	8	1	9	3	2	90
Потребности	10	40	70	20	70

Найдем сумму запасов баз:

= 70 + 50 + 90 = 210,

и сумму потребностей заказчиков:

= 10 + 40 + 70 + 20 + 70 = 210.

Так как общее количество запасов совпадает с общим количеством потребностей, то имеем транспортную задачу с закрытой моделью.

Определим начальный план методом минимальной стоимости.

Запишем последовательность заполнения клеток:

x₁₂ = min(90; 60) = 60;

x₁₃ = min(90-60; 50) = 30;

x₃₁ = min(110; 10) = 10;

x₃₃ = min(110-10; 50-30) = 20;

x₃₅ = min(110-30; 70) = 70;

x₃₄ = min(110-100; 40) = 10;

x₂₄ = min(30; 40-10) = 30.

Таблица 2

Потребители Базы	В 1	В 2	В 3	В 4	В 5	Запасы
А 1		9		1		1		7		6	90
	-		60		30		-		-
А 2		6		4		7		8		9	30
	-		-		-		30		-
А 3		2		9		3		5		3	110
	10		-		20		10		70
Потребности	10	60	50	40	70	230

Отметим, что в таблице 5 столбцов и 3 строки, а в полученном плане 7 занятых клеток. Так как 7 = 5 + 3 - 1, то этот план является невырожденным. Общая стоимость перевозок:

F(X1) = 601 + 301 + 308 + 102 + 203 + 105 + 703 = 670.

Проверим план по методу потенциалов. Сначала определим потенциалы поставщиков и потребителей. На этом этапе составляем систему уравнений для потенциалов, используя только занятые клетки.

u1 + v2 = 1,

u1 + v3 = 1,

u2 + v4 = 8,

u3 + v1 = 2,

u3 + v3 = 3,

u3 + v4 = 5,

u3 + v5 = 3.

В этой системе 8 неизвестных и 7 уравнений. Для однозначного разрешения положим u1 = 0.

Теперь система однозначно разрешима, ее решение записаны в заголовочных клетках таблицы 3.

Таблица 3

Потребители Базы	В 1v1 = 0	В 2 v2 = 1	В 3 v3 = 1	В 4 v4 = 3	В 5 v5 = 1	Запасы
А 1 u1 = 0		9		1		1		7		6	90
	-		60		30		-		-
А 2 u2 = 5		6		4		7		8		9	30
	-		-		-		30		-
А 3 u3 = 2		2		9		3		5		3	110
	10		-		20		10		70
Потребности	10	60	50	40	70	180

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

cij - (uij + vij) = sij

(выделено в таблице 4 жирным шрифтом):

s₁₁ = 9 - (0 + 0) = 9;

s₁₄ = 7 - (0 + 3) = 4;

s₁₅ = 6 - (0 + 1) = 5;

s₂₁ = 6 - (5 + 0) = 1;

s₂₂ = 4 - (5 + 1) = -2 < 0;

s₂₃ = 7 - (5 + 1) = 1;

s₂₅ = 9 - (5 + 1) = 3;

s₃₂ = 9 - (2 + 1) = 6.

Поскольку не все sij 0 из соотношения

cij - (uij + vij) = sij

для клеток с прочерком, то опорный план не является оптимальным. Следовательно, опорный план нуждается в модификации. Пересчет начнем с отрицательной клетки (А 2; В 2).

Таблица 4

Потребители Базы	В 1 v1 = 0	В 2 v2 = 1	В 3 v3 = 1	В 4 v4 = 3	В 5 v5 = 1	Запасы
А 1 u1 = 0	9	9		1		1	4	7	5	6	90
	-		60	-	30	+	-		-
А 2 u2 = 5	1	6	-2	4	1	7		8	3	9	30
	-		-	+	-		30	-	-
А 3 u3 = 2		2	6	9		3		5		3	110
	10		-		20	-	10	+	70
Потребности	10	60	50	40	70	180

Из всех отрицательных вершин цикла выберем наименьшее: .

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

Таблица 5

Потребители Базы	В 1 v1 = 2	В 2 v2 = 1	В 3 v3 = 1	В 4 v4 = 5	В 5 v5 = 3	Запасы
А 1 u1 = 0	7	9		1		1	2	7	3	6	90
	-		40		50		-		-
А 2 u2 = 3	1	6		4	3	7		8	3	9	30
	-		20		-		10		-
А 3 u3 = 0		2	8	9	2	3		5		3	110
	10		-		-		30		70
Потребности	10	60	50	40	70	180

Пересчитаем стоимость нового плана:

F(X2) = 401 + 501 + 204 + 108 + 102 + 305 + 703 = 630.

Проверим на оптимальность новый план и найдем оценки свободных клеток. Результаты расчетов помещены в заголовочные клетки таблицы 5.

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

Запишем решение транспортной задачи:

,

Fmin = F(X*) = 630.

Вывод. Для уменьшения расходов необходимо перевозить:

- из п. А 1 в п. В 2 40, в п. В 3 50 тонн груза;

- из п. А 2 в п. В 2 20, в п. В 4 10 тонн груза;

- из п. А 3 в п. В 1 10, в п. В 4 30, в п. В 5 70 тонн груза.

При этом общая стоимость перевозок составит 630 рублей.

Решим задачу в Excel. Задача ставится следующим образом:

при ограничениях

Создадим экранную форму задачи:

Рис. 1.

В ячейки В 12:F14 будет записан оптимальный план задачи.

Целевая функция в ячейке J15: =Сумм производная (B4:F6;B12:F14) .

Ограничения в ячейках G12:G14:

=СУММ(B12:F12)

=СУММ(B13:F13)

=СУММ(B14:F14)

Ограничения в ячейках A15:А 15:

=СУММ(B12:B14)

=СУММ(C12:C14)

=СУММ(D12:DC14)

=СУММ(Е 12:Е 14)

=СУММ(F12:F14)

Выполним команду: Сервис - Поиск решения.

Рис. 2.

Установим параметры:

Рис. 3.

В результате получим:



Рис. 5.

Задача 3.

Задана матрица транспортной сети G(X, U, C(U)). Построить диаграмму и найти максимальный поток и минимальный разрез.

(1,2) 10

(1,3) 16

(1,5) 22

(2,5) 14

(3,6) 18

(4,3) 14

(4,7) 8

(5,3) 12

(5,4) 20

(5,7) 12

(6,4) 8

(6,7) 10

Решение.



Рис. 1

Воспользуемся алгоритмом Форда-Фалкерсона.

Шаг 1. Зададим начальное значение потока (и) = 0. На дугах орграфа рядом с пропускными способностями в скобках будем помещать очередное значение потока.

Выбираем, цепь G1 = 1 - 2 - 5 - 7.

.

Так как , то и .

Увеличиваем величину потока в цепи G1 на величину :

Рис. 2

Шаг 2. Построим цепь G2 = {1 - 5 - 7}.

.

Увеличиваем величину потока в цепи G2 на величину :

Рис. 3

Шаг 3. Построим цепь G3 = {1 - 3 - 6 - 7}.

.

Увеличиваем величину потока в цепи G3 на величину :

Рис. 4.

Шаг 4. Построим цепь G4 = {1 - 5 - 4 - 7}.

.

Увеличиваем величину потока в цепи G4 на величину :

Рис. 5.

N	(1,2)	(1,3)	(1,5)	(2,5)	(3,6)	(4,3)	(4,7)	(5,3)	(5,4)	(5,7)	(6,4)	(6,7)
	10	16	22	14	18	14	8	12	20	12	8	10
1	+10			+10						+10
2			+2							+2
3		+10			+10							+10
4			+8				+8		+8
	10	10	10	10	10	0	8	0	8	12	0	10

Помечаем вершины, начиная с 1. Вершине 1 присваиваем метку +1. Из вершины 1 идут ненасыщенные дуги (1, 3), (1, 5). Вершинам 3 и 5 присваиваем метку +2. Продолжая, таким образом, процесс присваивания меток, мы на вершине 6 остановим процесс присваивания меток, так как из вершины 6 нет насыщенных дуг.

Вершина t не помечена, следовательно, нет маршрута прорыва и ранее полученный поток является максимальным. Величина максимального потока - сумма потоков по дугам из источника 10 + 10 + 10 = 30.

Эта величина равна, также, сумме потоков по дугам, входящим в сток: 8 + 12 + 10 = 30.

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

Из рис. 4 видно, что в минимальный разрез входят дуги (4-7), (5-7) и (6-7). Сумма их пропускных способностей равна 10 + 8 + (10+2) = 30.

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

В ячейки столбца А введены номера начальных узлов дуг, в столбец В - конечных узлов, в ячейке столбца С введены пропускные способности дуг. Ячейки столбца F зарезервированы для определения потоков по дугам сети. В ячейку F8 помещена целевая функция - сумма потоков по дугам, выходящим из источника s (у нас выходят три дуги, суммируются ячейки в столбце F, соответствующие ячейкам столбца А со значением "1"): =F2+F3+F4.

В столбец J введены формулы (1), т.е. складываются ячейки столбца F, которые соответствуют ячейкам с индексом i в столбце А, и вычитаются ячейки, которые соответствуют ячейкам с индексом i в столбце В:

Рис. 6.

В ячейки столбца К введены фиксированные потоки, равные 0 для всех узлов, кроме источника и стока. В стоке фиксированный поток определен противоположным по знаку значению целевой функции.

Выполняем команду - Сервис - Поиск решения:

Рис. 7

Здесь ограничения заданы в соответствии с формулами (2).

В результате получим:

Рис. 8

Максимальный поток равен 30 (ячейка F14).

Найдем минимальный разрез в Excel. Задача ставится следующим образом:



при ограничениях

В ячейки столбца А введены номера начальных узлов дуг, в столбец В - конечных узлов, в ячейке столбца С введены пропускные способности дуг.

Рис. 9

Ячейки столбца E определяем для нахождения потенциалов узлов, ячейки столбца Н - для нахождения индикаторных переменных k. В ячейку E14 заносим формулу для определения значения целевой функции: =сумм производных (H2:H13;C2:C13)

В ячейки столбца Е вводим ограничения:



Рис. 10

Выполняем команду - Сервис - Поиск решения:

Рис. 11



Рис.12

Минимальный разрез осуществляется по дугам (4-7), (5-7), (6-7) и равен 30.

Задача 4.

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

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

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

3. Рассчитать характеристики эффективности

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

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

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

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

Так как ч = 1,5 > 1 или k = 3 < с = 6, то не существует стационарный режим. Очередь будет неограниченно возрастать. Таким образом, исходные данные не являются адекватными условиям применения математической модели системы массового обслуживания.

2. Примем решение по управлению системой массового обслуживания с целью приведения ее в соответствие с условиями применения описывающей математической модели. Нужно получить неравенство

.

На интенсивность л потока холодильников, требующих ремонта, мы повлиять не можем. Достаточно либо увеличить количество мастеров k, либо увеличить производительность труда м каждого из мастеров, внедряя более производительные технологии. Примем на работу еще 4-х мастеров:

k = 3 + 4 = 7 > 6 = .

Следовательно,

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

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

раб. дня или часов;

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

,

Где

Тогда

.

раб. дня или часа.

3) средняя длина очереди:

Решение в Excel:



Рис. 1

В режиме формул:

Рис. 2

Список используемой литературы

1. Алгоритмы решения транспортных, сетевых задач и задач о назначении. Часть вторая. Учебное пособие. /В.С. Асламова, И.М. Кулакова, М.Н. Колес-ник.- Ангарск. - АГТА: 2008 г. - 190 с. [Электронный ресурс].

2. Гмурман В.Е. Руководство к решению задач по теории вероятностей и математической статистике. - М.: Высш. шк., 1979.

3. Гмурман В.Е. Теория вероятностей и математическая статистика. М: Высшая школа, 2001.

4. Решение потоковых задач в MS Excel [Электронный ресурс]. Режим доступа: http://lib.sfi.komi.com

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

...