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

ФГОУ СПО

Санкт-Петербургский колледж Информатизации и управления

(СПбКИУ)

КУРСОВОЙ ПРОЕКТ

по предмету «Математические методы»

Тема: «Двойственная задача и n-канальная Система Массового Обслуживания (СМО)»

Выполнил:

студент группы 442

Родригес Ф.Л.

Проверил:

Преподаватель

Колесник А. В.

Содержание

Введение……………………………………………………………………….…………………3

Двойственная задача.…………………………..………………………….……………………4

Пример «Двойственная задача».…………………………………………….…………………6

Система Массового Обслуживания.....……………...…………………….…………………...8

Пример «Система Массового Обслуживания»…………….………….……...………………10

Заключение…………….………………………………………………...……….……..………13

Список литературы…………….………….……….……………………………………..…….14

Введение

Курсовой проект рассматривает решения задач по предмету математические методы, а именно Двойственная задача и Системы Массового Обслуживания (СМО), в данном случае n-канальное. Также содержит небольшую теоритическую часть по этим темам.

Двойственная задача

Оптимальное решение задачи линейного программирования определяется

Теми условиями, которые нашли отражение в модели в момент ее формирования.

В реальной жизни условия, формирующие модель, не остаются неизменными.

В связи с этим особое значение приобретают средства, позволяющие оценить

Изменения в оптимальном решении, вызванные изменениями в параметрах

Исходной модели. Таким средством является анализ чувствительности. Он

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

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

Двойственная задача — это задача, формулируемая с помощью определенных правил

непосредственно из прямой задачи. В этом разделе рассмотрены правила

построения двойственных задач.

При изложении теории двойственности часто рассматривают формулировки

двойственной задачи в зависимости от различных видов прямой задачи, которые

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

Стандартная форма записи задачи предполагает выполнение следующих требований.

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

2. Все переменные неотрицательные.

Напомним, что задача ЛП в стандартной форме записывается следующим образом.

Максимизировать или минимизировать целевую функцию

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

В состав переменных xj входят также дополнительные переменные. Стандартная форма задачи ЛП предполагает выполнение следующих условий.

1. Все ограничения записаны в виде равенств с неотрицательной правой частью.

2. Все переменные неотрицательны.

3. Оптимизация определяется как максимизация или минимизация целевой функции.

Стандартная форма задачи ЛП порождает стандартную таблицу симплекс-

метода. Поэтому, как будет показано ниже, решение двойственной задачи можно

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

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

стандартной формы прямой задачи, после вычислений симплекс-метода мы автоматически получаем решение двойственной задачи.

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

1. Каждому из m ограничений прямой задачи соответствует переменная двойственной задачи.

2. Каждой из n переменных прямой задачи соответствует ограничение двойственной задачи.

3. Коэффициенты при какой-либо переменной в ограничениях прямой задачи

становятся коэффициентами ограничения двойственной задачи, соответствующей этой переменной, а правая часть формируемого ограничения равна

коэффициенту при этой переменной в выражении целевой функции.

4. Коэффициенты целевой функции двойственной задачи равны правым частям

ограничений прямой задачи.

Графически эти правила представлены в табл. 1.

Таблица 1. Формирование двойственной задачи из прямой

Переменные двойственной задачи	Переменные прямой задачи
X1	X2		Xj		Xn
C1	C2		Cj		Cn
Y1	A11	A21	…	A1j	…	A1m	B1
Y2	A12	A22	…	A2j	…	A2m	B2
…	…	…	…	…	…	…	…
…	…	…	…	…	…	…	…
Yn	…	…	…	Anj	…	Anm	Bn
j-e ограничение двойственной задачи	Коэффициенты целевой задачи функции двойственной

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

Таблица 2. Правила определения типа оптимизации и ограничений

Целевая функция прямой задачи	Двойственная задача
Целевая функция	Тип ограничений	Переменные
Максимизация	Минимизация	>	Свободные
Минимизация	Максимизация	<	Свободные

Пример

1. Составим таблицу, умножив значения целевой функции на -1.

Базисные переменные x5, x6, x7.

	х1	х2	х3	х4	х5	х6	х7	СЧ
x5
x6
x7				-2
L	-4	-2	-2	-1

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

	х1	х2	х3	х4	х5	х6	х7	СЧ
x5
x6
x7				-2
L	-4	-2	-2	-1

Разделим ведущую строку на ведущий элемент

0,5

ведущая строка

Складываем ведущую строку с остальными строками таблицы, предварительно умножив ее на элемент того же столбца с противоположным знаком.


-1	-0,5	-0,5	-1	-0,5	-5
	0,5	0,5		-0,5

первая преобразованная строка

			-2
-1	-0,5	-0,5	-1	-0,5	-5
	0,5	1,5	-3	-0,5

вторая преобразованная строка

-4	-2	-2	-1

четвертая преобразованная строка

Составим новую таблицу. Базисные переменные x1, x5, x7.

	х1	х2	х3	х4	х5	х6	х7	СЧ
x5		0,5	0,5			-0,5
x6		0,5	0,5			0,5
x7		0,5	1,5	-3		-0,5
L

Так как в строке целевой функции не осталось отрицательных элементов, то задача решена.

Решение двойственной задачи.

	y1	y2	y3	y4	y5	y6	СЧ
y4				-1
y5					-1
y6						-1
F

Отнимаем от строки y5 строку y4

-1

-2

Отнимаем от строки y6 строку y4

-1

-2

Отнимаем от строки f строку y4 умноженную на 8

-6

-2

-32

	y1	y2	y3	y4	y5	y6	СЧ
y4				-1
y5		-1			-1		-2
y6		-1				-1	-2
F		-6	-2				-32

Умножим y5 на -1

-1

Отнимаем от строки y4 строку y5 * 2

-2

Прибавляем к строке y6 строку y5

-1

Прибавляем к строке f строку y5*6

-2

-20

	y1	y2	y3	y4	y5	y6	СЧ
y4					-2
y5				-1
y6						-1
F			-2				-20

Прибавляем к строке f строку y6*2

-2

-20

Отнимаем от строки y4 строку y6

-3

	y1	y2	y3	y4	y5	y6	СЧ
y4					-3
y5				-1
y6						-1
F						-2	-20

Решением являются:

Система Массового Обслуживания (СМО)

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

к кассам в продовольственных магазинах и выстраиваемся в очередь в почтовых

отделениях. Однако феномен ожидания характерен не только для людей: детали,

поставленные в очередь для обработке на станке; группа пассажирских самолетов,

ожидающих разрешения на посадку в аэропорту; автомобили, движение которых

приостановлено сигналом светофора на пути их следования и т.п. К сожалению,

феномен ожидания нельзя исключить без чрезмерных расходов. И лишь на одно

мы можем надеяться — на возможность сокращения времени нежелательного

ожидания в очереди до некоторых терпимых пределов.

Основными элементами модели массового обслуживания являются клиент (заявка или требование на обслуживание либо просто "объект обслуживания") и сервис (обслуживающее устройство, средства обслуживания и т.п.). Клиенты поступают в систему обслуживания из источника. Поступив в сервис, они могут сразу же попасть на обслуживание или ожидать в очереди, если сервис занят. После завершения процедуры обслуживания сервис автоматически "выбирает" из очереди (если она имеется) одного из клиентов с тем, чтобы приступить к его обслуживанию. Если же очередь отсутствует, то сервис становится незанятым до прибытия нового клиента.

Поступление клиентов в систему обслуживания характеризуется интервалом

между их последовательными поступлениями, а обслуживание — временем об-

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

как, например, в работе почтового отделения, и детерминированными, как, на-

например, прибытие на собеседование кандидатов на вакантную должность.

В анализе систем обслуживания определенную роль играет длина очереди, ко-

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

обслуживающими устройствами, и бесконечной, как у обслуживающих операторов

почтовых отделений.

Важным фактором при анализе систем обслуживания является дисциплина

очереди (или принцип построения очереди), определяющая порядок, в соответствии с которым выбираются клиенты из очереди для обслуживания. Наиболее распространенный принцип построения очереди основан на правиле "первым пришел — первым обслуживаешься" (это правило часто обозначается аббревиатурой FIFO — от английского First-In-First-Out, т.е. "первым вошел — первым вышел"). Среди других правил, определяющих принципы построения очередей, укажем правило "последним пришел — первым обслуживаешься" (обычно обозначается как LIFO — от английского Last-In-First-Out, т.е. "последним вошел — первым вышел") и дисциплину очереди, определяемую случайным правилом отбора клиентов (иногда обозначается как SIRO — от английского Service-In-Random-Out, т.е. "обслуживание по случайному принципу"). Кроме того, клиенты могут выбираться из очереди в соответствии с заданным приоритетом. Например, в производственном цехе срочные работы выполняются раньше обычных.

При анализе систем с очередями важным фактором является также поведение

индивидуума, нуждающегося в обслуживании. Такие индивидуумы, выступающие

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

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

какое-то время и придя к выводу, что и так уж слишком много времени потеряно.

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

При рассмотрении общих систем массового обслуживания предполагается, что

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

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

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

Введем следующие обозначения.

n — число клиентов в системе обслуживания (в очереди и на обслуживании),

λ — интенсивность поступления в систему клиентов при условии, что в системе

уже находится п клиентов,

µ — интенсивность выходного потока обслуженных клиентов при условии, что

в системе находится п клиентов,

Pn — вероятность того, что в системе находится п клиентов.

В общей модели системы массового обслуживания устанавливается функциональная зависимость вероятностей Pn от λ и µ. Эти вероятности используются затем при определении функциональных характеристик обслуживающей системы, таких

как средняя длина очереди, среднее время ожидания и средний коэффициент использования сервисов.

Вероятности Pn определяются из диаграммы интенсивностей переходов, представленной на рис. 1. Обслуживающая система находится в состоянии n, если

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

n > 0 состояние n может быть изменено в двух возможных направлениях:n- 1, когда с интенсивностью µ обслуженный клиент выбывает из системы, и n + 1, когда клиенты поступают с интенсивностью λ. Состояние 0 может измениться лишь к состоянию 1, когда имеет место поступление клиента с интенсивностью λ. Заметим, что µ когда n = 0 не определено, так как клиенты не могут выбывать из пустой системы обслуживания.

Рис. 1. Диаграмма интенсивностей переходов

…

n-1

n+1

Рис. 1

При выполнении условий стационарности ожидаемые интенсивности входного и выходного потоков в состоянии n (n > 0) должны быть равны. Так как состояние n

может изменяться лишь к состояниям n - 1 и n + 1, отсюда следует

(ожидаемая интенсивность входного потока в состоянии n) =

Аналогично

(ожидаемая интенсивность выходного потока в состоянии n) =

Приравнивая эти две интенсивности, получаем следующее уравнение баланса.

n = 1.2,...

Как видно из рис. 17.3, уравнение баланса, соответствующее п = 0, имеет вид

Р₁=λ/µ*Р₀

Пример

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

n = 3 (всего каналов)

m = 2 (мест в очереди)

Составим граф.

С помощью уравнения Колмогорова выразим необходимые для решения формулы:

S0:

S1: по формуле для S0 получается

S2: по формуле для S1 получается

S3: по формуле для S2 получается

=> по этим формулам можно заметить закономерность и поэтому формула для Sn будет выглядеть так

Выведем формулу для подсчета Pn

По этим формулам тоже видна закономерность

Теперь как видно по формуле нам нужно узнать чему равен Р0.

Так как сумма вероятностей всегда = 1 (из теории вероятностей) у нас получается равенство:

Подставим полученные ранее формулы вместо Р1...Р5, вынесем Р0 за скобку, и разделим равенство на полученную скобку =>

Пусть:

Тогда формула для Р0 примет вид:

Ранее полученное уравнение подходит только для S0 – S3 (для каналов). В очереди 3µ повторяется для очереди своя формула

а так как по начальным данным у нас l = 4, m = 2 следовательно r = 2 тогда подставляя данные в формулы получится:

P1=2*P0= 0.255924

=0.255924
=0.170616

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

Чем ближе результат к 1 тем точнее мы определили вероятности Р0…Р5

ЗАКЛЮЧЕНИЕ

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

Список литературы

1 Кузнецов А.В., Сакович В.А., Холод Н.И. ”Высшая математика. Математическое программирование ”, Минск, Вышейшая школа, 2001г.

2 Таха, Хемди А. Введение в исследование операций. Седьмое издание. Москва: Вильямс, 2005

3 Е.В.Бережная, В.И.Бережной. Математические методы моделирования экономических систем. Издание второе. Москва: Финансы и статистика, 2006.