Основы теории графов

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

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

Контрольная работа 1. Основы теории графов. Математическое программирование

Задание 1

Задана симметрическая матрица Q неотрицательных целых чисел.

1. Нарисовать на плоскости граф (единственный, с точностью до изоморфизма), имеющий заданную матрицу Q своей матрицей смежности. Найти матрицу инцидентности графа G.

2. Нарисовать на плоскости орграф (единственный, с точностью до изоморфизма), имеющий заданную матрицу Q своей матрицей смежности. Найти матрицу инцидентности графа .

Решение

1) Матрицей смежности графа с множеством вершин называется матрица размера nn, в которой элемент q_ij равен числу ребер в G, соединяющих E_i с E_j. Матрица смежности графа G является симметрической, то есть .

Построим граф по заданной матрице смежности.

Поскольку данная матрица является симметрической матрицей четвертого порядка с неотрицательными элементами, то ей соответствует неориентированный граф с четырьмя вершинами. Разложив вершины на плоскости произвольным образом (рис. 1), соединяем их с учетом кратности ребер.



Рис. 1. Граф

Вспомним определение матрицы инцидентности графа с множеством вершин и множеством ребер . Так называется матрица размера mk, у которой:

Составим матрицу инцидентности графа :



Таким образом, имеем:

2. Заданная матрица Q имеет 4 строки и 4 столбца, следовательно, орграф имеет 4 вершины. Обозначим их соответственно , а матрицу представим в виде:

На плоскости строим 4 точки, обозначим их через . Построим ориентированный граф (орграф) по заданной матрице смежности.

Так как , то при вершине имеется петля; , значит, из вершины выходят две стрелки к вершине ; , значит, из вершины выходят две стрелки к вершине ; , значит, из вершины 1 выходит одна стрелка к вершине и т.д. (рис. 2).



Рис. 2. Ориентированный граф

Теперь запишем матрицу инцидентности орграфа . Орграф имеет 4 вершины и 13 дуг, т.е.: , .

Элемент матрицы равен 1, если точка является концом дуги, -1 - если началом дуги, если дуга является петлей, элемент матрицы запишем как ±1.

Матрица инцидентности орграфа будет иметь 4 строки и 13 столбцов:

Таким образом, имеем:



Задание 2

Решить задачу линейного программирования графическим методом.

,

Решение

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

Построение множества допустимых решений, удовлетворяющих всем ограничениям модели.

Нахождение оптимального решения на множестве допустимых решений.

Построим множество допустимых решений или, что то же самое, область допустимых решений. Проведем перпендикулярные оси координат: горизонтальная -- 0х₁, вертикальная -- 0х₂ (рис. 1). Условие неотрицательности переменной х₂ 0 показывает, что область допустимых решений будет лежать выше оси х₁.

Построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом) (рис. 1).

Построим уравнение x₁+x₂ = 12 по двум точкам.

Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = 12. Для нахождения второй точки приравниваем x₂ = 0. Находим x₁ = 12. Соединяем точку (0; 12) с (12; 0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1*0 + 1*0 - 12 ? 0, т.е. x₁+x₂ - 12? 0 в полуплоскости ниже прямой.

Построим уравнение 2x₁-x₂ = 12 по двум точкам.

Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = -12. Для нахождения второй точки приравниваем x₂ = 0. Находим x₁ = 6. Соединяем точку (0; -12) с (6; 0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 2*0 - 1*0 - 12 ? 0, т.е. 2x₁-x₂ - 12? 0 в полуплоскости ниже прямой.

Построим уравнение 2x₁-x₂ = 0 по двум точкам.

Для нахождения первой точки приравниваем x₁ = 1. Находим x₂ = 2. Для нахождения второй точки приравниваем x₂ = 1. Находим x₁ = 0,5. Соединяем точку (1; 2) с (0,5; 1) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 2*0 - 1*0 - 0 = 0, т.е. 2x₁-x₂ - 0? 0 в полуплоскости на прямой.

Построим уравнение 2x₁+x₂ = 4 по двум точкам.

Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = 4. Для нахождения второй точки приравниваем x₂ = 0. Находим x₁ = 2. Соединяем точку (0; 4) с (2; 0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 2*0 + 1*0 - 4 ? 0, т.е. 2x₁+x₂ - 4? 0 в полуплоскости выше прямой.



Рис. 1. Область допустимых решений

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

Обозначим границы области многоугольника решений (рис. 2).

Рис. 2. Границы области многоугольника решений



Таким образом, областью допустимых решений (ОДР) является многоугольник с вершинами ABCDE.

Рассмотрим целевую функцию задачи:

.

Построим прямую, отвечающую значению функции :

.

Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации Z(x₁, x₂). Начало вектора - точка (0; 0), конец - точка (2; 1). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией (рис. 3).

Рис. 3. Прямая целевой функции на минимум



Прямая пересекает область в точке A. Так как точка A получена в результате пересечения прямых, заданных уравнениями и , то ее координаты удовлетворяют уравнениям этих прямых.

Решаем систему уравнений:

Решив систему уравнений, получили:

x₁ = 1; x₂ = 2.

Откуда найдем минимальное значение целевой функции:

.

Поскольку функция цели параллельна прямой , то на отрезке AB функция будет принимает одно и тоже минимальное значение.

Для определения координат точки B решим систему двух линейных уравнений:

Решив систему уравнений, получили:

x₁ = 2; x₂ = 0.

Откуда найдем минимальное значение целевой функции:

.

Ответ. При заданных ограничениях целевая функция достигает минимального значения в двух точках: А(1; 2) и В(2; 0). При этом минимальное значение целевой функции в данных точках равно .

Задание 3

Решить симплексным методом следующую задачу.

Решение

Выполним переход к канонической форме с помощью введения дополнительных переменных:

-2x₁ + 1x₂ + 1x₃ + 1x₄ + 0x₅ + 0x₆ = 2;

-1x₁ + 1x₂ + 3x₃ + 0x₄ + 1x₅ + 0x₆ = 3;

1x₁-3x₂ + 1x₃ + 0x₄ + 0x₅ + 1x₆ = 1.

Решим систему уравнений относительно базисных переменных: x₄, x₅, x₆. Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0, 0, 0, 2, 3, 1).

Базис	В	x1	x2	x3	x4	x5	x6
x4	2	-2	1	1	1	0	0
x5	3	-1	1	3	0	1	0
x6	1	1	-3	1	0	0	1
Z(X0)	0	-1	-2	-1	0	0	0

Переходим к основному алгоритму симплекс-метода.

Шаг 1. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В индексной строке Z(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю. Вычислим значения D_i по строкам как частное от деления: b_i / a_i2 и из них выберем наименьшее:

.

Таким образом, первая строка является ведущей. Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки:

Базисные переменные	Коэффициенты целевой функции	Значение базисных переменных	x1	x2	x3	x4	x5	x6
x4 <	0	2	-2	1	1	1	0	0
x5	0	3	-1	1	3	0	1	0
x6	0	1	1	-3	1	0	0	1
	Z(X)=0	оценки	-1	-2 ^	-1	0	0	0

Формируем следующую часть симплексной таблицы.

Вместо переменной x₄ в план 1 войдет переменная x₂.

Строка, соответствующая переменной x₂ в плане 1, получена в результате деления всех элементов строки x₄ плана 0 на разрешающий элемент РЭ=1. На месте разрешающего элемента в плане получаем 1. В остальных клетках столбца x₂ записываем нули. Таким образом, в новом плане 1 заполнены строка x₂ и столбец x₂.

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

Элементы разрешающей строки делим на разрешающий элемент и записываем в соответствующей по номеру строке новой таблицы:

, при i = r.

Все остальные элементы новой таблицы рассчитываем по формулам:

, при i ? r

где - элемент новой симплекс-таблицы, a_ij, - элемент предыдущей симплекс-таблицы, a_rk - разрешающий элемент, a_ik - элемент разрешающего столбца, a_rj - элемент разрешающей строки.

После преобразований получаем новую таблицу:

Базис	В	x1	x2	x3	x4	x5	x6
x2	2	-2	1	1	1	0	0
x5	1	1	0	2	-1	1	0
x6	7	-5	0	4	3	0	1
Z(X1)	4	-5	0	1	2	0	0

Шаг 2. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю. Вычислим значения D_i по строкам как частное от деления: b_i / a_i1 и из них выберем наименьшее:

.

Таким образом, вторая строка является ведущей. Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки:

Базисные переменные	Коэффициенты целевой функции	Значение базисных переменных	x1	x2	x3	x4	x5	x6
x2	2	2	-2	1	1	1	0	0
x5 <	0	1	1	0	2	-1	1	0
x6	0	7	-5	0	4	3	0	1
	Z(X)=4	оценки	-5 ^	0	1	2	0	0

Формируем следующую часть симплексной таблицы.

Вместо переменной x₅ в план 2 войдет переменная x₁.

Строка, соответствующая переменной x₁ в плане 2, получена в результате деления всех элементов строки x₅ плана 1 на разрешающий элемент РЭ=1. На месте разрешающего элемента в плане получаем 1. В остальных клетках столбца x₁ записываем нули. Таким образом, в новом плане 2 заполнены строка x₁ и столбец x₁.

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

После преобразований получаем новую таблицу:

Базис	В	x1	x2	x3	x4	x5	x6
x2	4	0	1	5	-1	2	0
x1	1	1	0	2	-1	1	0
x6	12	0	0	14	-2	5	1
Z(X2)	9	0	0	11	-3	5	0

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

Ответ. Решения не существует, так как ОДР (область допустимых решений) не ограничена.



Задание 4

Имеются 3 пункта отправления , , однородного груза и пять пунктов , , , , его назначения. На пунктах , , груз находится в количестве , , тонн соответственно. В пункты , , , , требуется доставить соответственно , , , , тонн груза. Расстояния в сотнях километров между пунктами отправления (i=1, 2, 3) и пунктами назначения (j=1, 2, 3, 4, 5) приведены в матрице . Найти такой план перевозок, при котором общие затраты на перевозку грузов будут минимальными.

Указания: 1) стоимость перевозок считать пропорциональной количеству груза и расстоянию, на которое груз перевозится; 2) для решения задачи использовать методы северо-западного угла и потенциалов.

,

,

Решение

Представим исходные данные в виде таблицы:

Пункты отправления	Пункты назначения	Запасы груза
	4	1	2	4	5	50
	6	4	5	9	5	70
	3	1	6	5	9	110
Потребности	50	50	50	50	30

1) Построим экономико-математическую модель представленной транспортной задачи.

Обозначим через х_ij - объём перевозки груза из i-го пункта отправления в j-й пункт назначения. Тогда суммарные транспортные затраты на перевозку груза F(x) составят:

Проверим тип представленной транспортной задачи:

;

.

Так как , то данная задача является закрытой.

Заданные количества запасов груза в пунктах отправления и потребностей в пунктах назначения накладывают ограничения на значения перевозок груза x_ij.

а) Весь запас груза из пунктов отправления должен быть вывезен:

б) Потребности пунктов назначения должны быть удовлетворены:



в) Объемы перевозимого груза не могут быть отрицательными:

.

Экономико-математическая модель представленной транспортной задачи составлена.

2) Построим первый опорный план транспортной задачи с помощью метода северо-западного угла.

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

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

Пункты отправления	Пункты назначения	Запасы груза
	4[50]	1	2	4	5	50
	6	4[50]	5[20]	9	5	70
	3	1	6[30]	5[50]	9[30]	110
Потребности	50	50	50	50	30

Значение целевой функции для этого опорного плана равно:

F(x) = 4*50 + 4*50 + 5*20 + 6*30 + 5*50 + 9*30 = 1200.

Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.

3) Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0:

u₁ + v₁ = 4; 0 + v₁ = 4; v₁ = 4;

u₂ + v₂ = 4; 0 + u₂ = 4; u₂ = 4;

u₂ + v₂ = 4; 4 + v₂ = 4; v₂ = 0;

u₂ + v₃ = 5; 4 + v₃ = 5; v₃ = 1;

u₃ + v₃ = 6; 1 + u₃ = 6; u₃ = 5;

u₃ + v₄ = 5; 5 + v₄ = 5; v₄ = 0;

u₃ + v₅ = 9; 5 + v₅ = 9; v₅ = 4.

	v1=4	v2=0	v3=1	v4=0	v5=4
u1=0	4[50]	1	2	4	5
u2=4	6	4[50]	5[20]	9	5
u3=5	3	1	6[30]	5[50]	9[30]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij:

(2;1): 4 + 4 > 6; ?₂₁ = 4 + 4 - 6 = 2;

(2;5): 4 + 4 > 5; ?₂₅ = 4 + 4 - 5 = 3;

(3;1): 5 + 4 > 3; ?₃₁ = 5 + 4 - 3 = 6;

(3;2): 5 + 0 > 1; ?₃₂ = 5 + 0 - 1 = 4;

max(2,3,6,4) = 6.

Выбираем максимальную оценку свободной клетки (3;1): 3:

Пункты отправления	Пункты назначения	Запасы груза
	4	1[50]	2	4	5	50
	6	4	5[50]	9	5[20]	70
	3[50]	1[0]	6	5[50]	9[10]	110
Потребности	50	50	50	50	30

Значение целевой функции для этого опорного плана равно:

F(x) = 1*50 + 5*50 + 5*20 + 3*50 + 5*50 + 9*10 = 890.

Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0:

u₁ + v₂ = 1; 0 + v₂ = 1; v₂ = 1;

u₃ + v₂ = 1; 1 + u₃ = 1; u₃ = 0;

u₃ + v₁ = 3; 0 + v₁ = 3; v₁ = 3;

u₃ + v₄ = 5; 0 + v₄ = 5; v₄ = 5;

u₃ + v₅ = 9; 0 + v₅ = 9; v₅ = 9;

u₂ + v₅ = 5; 9 + u₂ = 5; u₂ = -4;

u₂ + v₃ = 5; -4 + v₃ = 5; v₃ = 9.

	v1=3	v2=1	v3=9	v4=5	v5=9
u1=0	4	1[50]	2	4	5
u2=-4	6	4	5[50]	9	5[20]
u3=0	3[50]	1[0]	6	5[50]	9[10]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij:

(1;3): 0 + 9 > 2; ?₁₃ = 0 + 9 - 2 = 7;

(1;4): 0 + 5 > 4; ?₁₄ = 0 + 5 - 4 = 1;

(1;5): 0 + 9 > 5; ?₁₅ = 0 + 9 - 5 = 4;

(3;3): 0 + 9 > 6; ?₃₃ = 0 + 9 - 6 = 3;

max(7,1,4,3) = 7.

Выбираем максимальную оценку свободной клетки (1;3): 2.

Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-»:

Пункты отправления	Пункты назначения	Запасы груза
	4	1[50][-]	2[+]	4	5	50
	6	4	5[50][-]	9	5[20][+]	70
	3[50]	1[0][+]	6	5[50]	9[10][-]	110
Потребности	50	50	50	50	30

Цикл приведен в таблице (1,3 > 1,2 > 3,2 > 3,5 > 2,5 > 2,3).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 5) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план:

Пункты отправления	Пункты назначения	Запасы груза
	4	1[40]	2[10]	4	5	50
	6	4	5[40]	9	5[30]	70
	3[50]	1[10]	6	5[50]	9	110
Потребности	50	50	50	50	30

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0:



u₁ + v₂ = 1; 0 + v₂ = 1; v₂ = 1;

u₃ + v₂ = 1; 1 + u₃ = 1; u₃ = 0;

u₃ + v₁ = 3; 0 + v₁ = 3; v₁ = 3;

u₃ + v₄ = 5; 0 + v₄ = 5; v₄ = 5;

u₁ + v₃ = 2; 0 + v₃ = 2; v₃ = 2;

u₂ + v₃ = 5; 2 + u₂ = 5; u₂ = 3;

u₂ + v₅ = 5; 3 + v₅ = 5; v₅ = 2.

	v1=3	v2=1	v3=2	v4=5	v5=2
u1=0	4	1[40]	2[10]	4	5
u2=3	6	4	5[40]	9	5[30]
u3=0	3[50]	1[10]	6	5[50]	9

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij:

(1;4): 0 + 5 > 4; ?₁₄ = 0 + 5 - 4 = 1.

Выбираем максимальную оценку свободной клетки (1;4): 4.

Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-»:

Пункты отправления	Пункты назначения	Запасы груза
	4	1[40][-]	2[10]	4[+]	5	50
	6	4	5[40]	9	5[30]	70
	3[50]	1[10][+]	6	5[50][-]	9	110
Потребности	50	50	50	50	30

Цикл приведен в таблице (1,4 > 1,2 > 3,2 > 3,4).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 40. Прибавляем 40 к объемам грузов, стоящих в плюсовых клетках и вычитаем 40 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план:

Пункты отправления	Пункты назначения	Запасы груза
	4	1	2[10]	4[40]	5	50
	6	4	5[40]	9	5[30]	70
	3[50]	1[50]	6	5[10]	9	110
Потребности	50	50	50	50	30

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0:

u₁ + v₃ = 2; 0 + v₃ = 2; v₃ = 2;

u₂ + v₃ = 5; 2 + u₂ = 5; u₂ = 3;

u₂ + v₅ = 5; 3 + v₅ = 5; v₅ = 2;

u₁ + v₄ = 4; 0 + v₄ = 4; v₄ = 4;

u₃ + v₄ = 5; 4 + u₃ = 5; u₃ = 1;

u₃ + v₁ = 3; 1 + v₁ = 3; v₁ = 2;

u₃ + v₂ = 1; 1 + v₂ = 1; v₂ = 0.

	v1=2	v2=0	v3=2	v4=4	v5=2
u1=0	4	1	2[10]	4[40]	5
u2=3	6	4	5[40]	9	5[30]
u3=1	3[50]	1[50]	6	5[10]	9

Опорный план является оптимальным, так как все оценки свободных клеток удовлетворяют условию u_i + v_j ? c_ij.

Таким образом, оптимальный план перевозок груза:

Минимальные затраты составят:

F(x)_min = 2*10 + 4*40 + 5*40 + 5*30 + 3*50 +1*50+5*10=780.

Ответ. Из пункта отправления А₁ необходимо груз направить в пункт назначения В₃ в количестве 10 единиц и в пункт назначения В₄ в количестве 40 единиц.

Из пункта отправления А₂ необходимо груз направить в пункт назначения В₃ в количестве 40 единиц и в пункт назначения В₅ в количестве 30 единиц.

Из пункта отправления А₃ необходимо груз направить в пункт назначения В₁ в количестве 50 единиц, в пункт назначения В₂ в количестве 50 единиц и в пункт назначения В₄ в количестве 10 единиц.

При использовании данного плана перевозок груза общие транспортные затраты будут минимальными и составят 780 денежных единиц.

Задание 5

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

1) найти решение графическим методом;

2) написать функцию Лагранжа и найти ее седловую точку, используя решение, полученное графически.



Решение

1) Найдем решение графическим методом.

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

Рис. 1. Область допустимых решений

Затем строим функцию цели. График целевой функции представляет собой окружность переменного радиуса с центром в точке (0, 2) (рис. 2).

Поскольку у нас задача минимума, то ищем первое касание окружности и области допустимых решений. В данном случае это точка (2;3) пересечения с прямой .

Рис. 2. График целевой функции

Определим минимальное значение целевой функции:

.

Ответ. ; .

2) Напишем функцию Лагранжа и найдем ее седловую точку, используя решение, полученное графически.

Запишем задачу в традиционном виде:



Функция называется функцией Лагранжа, а переменные _i - коэффициентами Лагранжа. Точка называется седловой точкой функции Лагранжа, если для любых выполняются неравенства: .

Если функции f, g дифференцируемы, то условия, определяющие седловую точку (условие Куна-Таккера) следующие:

;

;

.

Найдем седловую точку , используя решение задачи, полученное графически: .

Для вычисления запишем функцию Лагранжа :

Локальные условия Куна-Таккера:



;

;

;

.

Подставим в 1-е и 2-е уравнения:

;

.

Получаем: .

Таким образом, седловая точка функции Лагранжа: .

Ответ. Седловая точка функции Лагранжа: .



Контрольная работа 2. Теория массового обслуживания

Задание 1

На АТС поступает простейший поток вызовов. Среднее количество вызовов в течение часа равно m. Найти вероятности того, что за t минут: а) не придет ни одного вызова; б) придет хотя бы один вызов; в) придет не менее k вызовов.

.

Решение

Имеем систему массового обслуживания (СМО) с одним каналом (один телефонный номер). Интенсивность вызовов равна: вызовов в минуту.

Случайная величина Х - число вызовов за 2 минуты - распределена по закону Пуассона с параметром .

а) Определим вероятность того, что за 2 минуты не придет ни одного вызова.

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

В частности, если m=0, то вероятность равна:

.



б) Вероятность того, что за 2 минуты придет хотя бы один вызов, определим, используя теорему вероятности появления хотя бы одного события, по формуле:

.

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

.

Задание 2

При работе электронного технического устройства возникают неисправности (сбои). Поток сбоев считаем простейшим с интенсивностью сбоев в час. Если устройство дает сбой, то он немедленно обнаруживается, и обслуживающий персонал приступает к устранению неисправности (ремонту). Время ремонта распределено по показательному закону. Среднее время ремонта составляет минут. В начальный момент времени устройство исправно. Найти:

а) вероятность того, что через час устройство будет работать;

б) вероятность того, что за последующие T часов устройство даст хотя бы один сбой;

в) предельные вероятности состояний.

.

Решение

Имеем систему массового обслуживания (СМО) с одним каналом. Интенсивность потока обслуживания:

Интенсивность нагрузки:

.

а) Вероятность того, что через час устройство будет работать равна:

.

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

.

в) Определим предельные вероятности состояний СМО.

Вероятность того, что в очереди:

1 заявка: ;

2 заявки: ;

3 заявки: ;

4 заявки: .

Доля обслуживаемых заявок, поступающих в единицу времени: , следовательно, 90,9% из числа сбоев заявок будут исправлены. Приемлемый уровень обслуживания должен быть выше 90%.



Задание 3

АТС имеет k линий связи. Поток вызовов -- простейший с интенсивностью вызовов в минуту. Среднее время переговоров составляет минут. Время переговоров имеет показательное распределение. Найти:

а) вероятность того, что все линии связи заняты;

б) относительную и абсолютную пропускные способности АТС;

в) среднее число занятых линий связи. Определить оптимальное число линий связи, достаточное для того, чтобы вероятность отказа не превышала .

.

Решение

Рассматривается многоканальная система массового обслуживания (СМО) с отказами в обслуживании.

Для определения показателей работы СМО необходимо рассчитать значение интенсивности потока обслуживания:

.

Интенсивность нагрузки составит:

.

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

Далее находим вероятность того, что все линии связи свободны, по формуле:



.

Следовательно, 12,5% времени в течении часа все линии связи будут не заняты, время простоя равно t_пр = 7,5 мин.

Находим вероятность того, что обслуживанием занята одна линия связи:

.

Находим вероятность того, что обслуживанием заняты две линии связи:

.

Вероятность того, что обслуживанием заняты три линии связи:

.

Вероятность того, что обслуживанием заняты четыре линии связи:

.



Вероятность того, что обслуживанием заняты пять линий связи (вероятность того, что все линии связи заняты):

.

Находим вероятность отказа (доля заявок, получивших отказ), или вероятность одновременной занятости всех линий связи, по формуле:

Значит, 4,25% из числа поступивших заявок не принимаются к обслуживанию.

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

p_отк + p_обс = 1.

Относительная пропускная способность Q = p_обс:

p_обс = 1 - p_отк = 1 - 0,0425 = 0,957,

следовательно, 95,7% из числа поступивших заявок будут обслужены. Приемлемый уровень обслуживания должен быть выше 90%.

Среднее число занятых линий связи:



n_з = * p_обс = 2,1 * 0,957 = 2,011 линий связи.

Среднее число простаивающих каналов:

n_пр = n- n_з = 5 - 2,011 = 3 линии связи.

Коэффициент занятости линий связи обслуживанием:

.

Следовательно, АТС на 40% занята обслуживанием.

Абсолютная пропускная способность (интенсивность выходящего потока обслуженных заявок):

заявок/мин.

Среднее время простоя СМО:

мин.

Среднее число обслуживаемых заявок:

ед.

Среднее время пребывания заявки в СМО (формула Литтла):

мин.



Для определения оптимального числа линий связи, достаточного для того, чтобы вероятность отказа не превышала , воспользуемся формулой:

Для наших данных:

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

.

Задание 4

Железнодорожная сортировочная горка, на которую подается простейший поток составов с интенсивностью состава в час, представляет собой одноканальную СМО с неограниченной очередью. Время обслуживания (роспуска) состава на горке имеет показательное распределение со средним значением минут. Найти:

а) предельные вероятности состояний СМО;

б) среднее число составов, связанных с горкой;

в) среднее число составов в очереди;

г) среднее время пребывания состава в СМО; д) среднее время пребывания состава в очереди.

.

Решение

Исчисляем показатели обслуживания для одноканальной СМО.

Для определения показателей работы СМО необходимо рассчитать значение интенсивности потока обслуживания:

.

Интенсивность нагрузки составит:

.

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

Вероятность, что канал свободен (доля времени простоя канала):

.

Следовательно, 33,3% в течение часа канал будет не занят, время простоя равно мин.

Определим предельные вероятности состояний СМО.

Вероятность того, что в очереди 1 заявка:

.



Доля заявок, получивших отказ (вероятность отказа):

.

Относительная пропускная способность. Поскольку в рассматриваемой СМО ограничение на длину очереди отсутствует, то любая заявка может быть обслужена, поэтому . Вероятность того, что заявка будет принята в систему: .

Абсолютная пропускная способность (интенсивность выходящего потока обслуженных заявок):

заявок/час.

Среднее число заявок в очереди (средняя длина очереди):

.

Среднее время ожидания заявки в очереди (среднее время простоя СМО):

часов.

Среднее число обслуживаемых заявок:

.



Среднее число заявок в системе:

ед.

Среднее время пребывания заявки в СМО (как в очереди, так и под обслуживанием):

час.

Задание 5

Рабочий обслуживает m станков. Поток требований на обслуживание -- простейший с интенсивностью станков в час. Время обслуживания одного станка подчинено экспоненциальному закону. Среднее время обслуживания одного станка равно минут. Найти:

а) среднее число станков, ожидающих обслуживания;

б) коэффициент простоя станка;

в) коэффициент простоя рабочего.

.

Решение

Исчисляем показатели обслуживания для одноканальной СМО.

Для определения показателей работы СМО необходимо рассчитать значение интенсивности потока обслуживания:

.

Интенсивность нагрузки составит:



.

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

Вероятность, что канал свободен (доля времени простоя канала):

.

Следовательно, 80% в течение часа канал будет не занят, время простоя равно мин.

Определим предельные вероятности состояний СМО.

Вероятность того, что в очереди:

1 заявка: ;

2 заявки: ;

3 заявки: ;

4 заявки: .

Доля заявок, получивших отказ (вероятность отказа):

.



Значит, 0,13% из числа поступивших заявок не принимаются к обслуживанию.

Относительная пропускная способность. Доля обслуживаемых заявок, поступающих в единицу времени:

.

Следовательно, 99,87% из числа поступивших заявок будут обслужены. Приемлемый уровень обслуживания должен быть выше 90%.

Вероятность того, что заявка будет принята в систему: .

Абсолютная пропускная способность (интенсивность выходящего потока обслуженных заявок):

заявок/час.

Среднее число заявок в очереди (средняя длина очереди):

.

Среднее время ожидания заявки в очереди (среднее время простоя СМО):

часа.

Среднее число обслуживаемых заявок:



.

Коэффициент простоя заявки в очереди:

Среднее число заявок в системе:

ед.

Среднее время пребывания заявки в СМО (как в очереди, так и под обслуживанием):

часа.

Число заявок, получивших отказ в течение часа: заявок в час.

Номинальная производительность СМО: 1 / 0,1 = 10 заявок в час. Фактическая производительность СМО: 1,9974 / 10 = 20% от номинальной производительности.



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

матрица смежность линейный программирование

1. Акулич, И.Л. Математическое программирование в примерах и задачах: учеб. пособие / И.Л. Акулич. - Изд. 2-е, испр. - СПб. [и др.]: Лань, 2009. - 347 с.

2. Балдин, К.В. Математическое программирование: учебник / К.В. Балдин, Н.А. Брызгалов, А.В. Рукосуев; под общ. ред. К.В. Балдина. - М.: Дашков и К, 2009.- 218 с.

3. Грахов В.Б. Линейное программирование в упражнениях и задачах. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2006.

4. Казанская О.В., Юн С.Г., Альсова О.К. Модели и методы оптимизации. Практикум: уч. пособие - Новосибирск: Изд-во НГТУ, 2012.- 204 с.

5. Новоселов В.С. Методы оптимизации в экономических задачах. Москва, ГУУ, 2012 г.

6. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач / И.В. Орлова. - М.: Вузовский учебник, НИЦ ИНФРА-М, 2013. - 140 c.

7. Просветов Г.И. Методы оптимизации: Учебно-практическое пособие. / Г.И. Просветов. - М.: Альфа-Пресс, 2009. -168 с.

8. Соловьев В.И. Методы оптимальных решений. - М.: Финансовый университет, 2012. - 364 с.

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

...