тематическая теория конфликтных ситуаций
Работа добавлена на сайт samzan.net:
1. Теория игр. Основные положения: задачи теории игр, виды игр, ходы в игре, стратегия. Формализованная постановка игровых задач. Платежная матрица. Ситуации, при которых происходит столкновение противоположных интересов называются конфликтными.
Теория игр — это математическая теория конфликтных ситуаций. Её цель — выработка рекомендаций по разумному поведению сторон в конфликтной ситуации. Ходом в игре называют выбор одного из предусмотренных правилами игры действия и его реализация. Ходы бывают личные и случайные. При личном ходе игрок сознательно выбирает и осуществляет тот или иной вариант действий. Пример: игра в шахматы, шашки.
При случайном ходе выбор осуществляется не волей игрока, а каким-то механизмом случайного выбора (напр., бросание монеты, бросание игральной кости). Некоторые игры состоят только из случайных ходов (напр., азартные игры).
Стратегией игрока называется совокупность правил, определяющих выбор им варианта действий при каждом личном ходе в зависимости от сложившейся ситуации. В зависимости от числа стратегий игры делятся на конечные и бесконечные. Игра называется конечной, если у каждого игрока имеется в распоряжении только конечное число стратегий. В противном случае игра называется бесконечной. Оптимальной стратегией игрока называется такая, которая обеспечивает ему наилучшее положение в данной игре, т. е. максимальный выигрыш. Задача теории игр — выявление оптимальных стратегий игроков.
В игре могут сталкиваться интересы двух или более игроков.Если в игре участвуют два игрока — игра называется парной. Если число игроков более двух — игра называется множественной. Участники множественной игры могут образовывать коалиции постоянные или временные. Поэтому следующей задачей теории игр является выявление разумных коалиций во множественной игре.
Парная игра с нулевой суммой называется антагонистической. Игра называется игрой с нулевой суммой, если сумма выигрышей всех игроков равна нулю (т. е. каждый игрок выигрывает за счет других).
Одноходовые игры заключаются в том, что игрок выбирает одну из доступных ему стратегий и тем самым делает один единственный ход.
В многоходовых играх игроки для достижения своих целей делают последовательно ряд ходов, которые могут ограничиваться правилами игры, либо могут продолжаться до тех пор, пока у одного из игроков не останется ресурсов для продолжения игры.
Решение матричных игр в чистых стратегиях.
Рассмотрим конечную парную игру с нулевой суммой, в которой участвуют два игрока «A» и «B», имеющие противоположные интересы. Так как выигрыш игрока «A» равен выигрышу игрока «B» с противоположным знаком, то нас может интересовать только выигрыш игрока «A» — «a». Естественно игрок «A» стремится максимизировать «a», а игрок «B» минимизировать «a».
Пусть у игрока «A» имеется «m» стратегий: «A1, A2, …, Am», а у игрока «B» — «n» стратегий: «B1, B2, …, Bn» (такая игра называется игрой m×n); «aij» — выигрыш игрока «A» в случае, если он воспользуется стратегией «Ai», а игрок «B» стратегией «Bj». Предположим, что для каждой игры стратегий «Ai — Bj» выигрыш «aij» известен, тогда можно составить прямоугольную таблицу (матрицу), в которой перечислены выигрыши игроков и их стратегии. Если такая таблица составлена, то говорят, что игра приведена к матричной форме (приведение игр к матричной форме является довольно сложной задачей). Если игра приведена к матричной форме, то многоходовая игра фактически сведена к одноходовой: от игрока требуется сделать только один ход — выбрать стратегию.
2. Методы и модели решения игровых задач. Принцип минимакса. Верхняя и нижняя цена игры. Решение игр в чистых стратегиях. Седловая точка. Решение игр в чистых стратегиях. В основе решения конечных игр в чистых стратегиях лежитиспользование критерия минимакса или максимина, т. е. при решении игр ищется наилучшее решение из наихудших.
Рассмотрим пример: пусть задана игра 3×4; игрок «A» имеет 3 стратегии: «A1, A2, A3»; игрок «B» имеет 4 стратегии: «B1, B2, B3, B4».
Минимум строк — минимальный выигрыш игрока «A». Гарантированный выигрыш игрока «A» maximinj=4 называется нижней ценой игры, а гарантированный минимальный проигрыш игрока minimaxj=4 — верхней ценой игры.
Если верхняя и нижняя цены игры совпадают, то говорят, что цена игры равна 4. Стратегии («A2», «B3») — чистые стратегии, соответствующие седловой точке.гиперболический параболоид
Пара чистых стратегий («A2», «B3») называется парой оптимальных стратегий.
Вывод: игра имеет решение в чистых стратегиях только тогда, когда нижняя и верхняя цены игры совпадают.
3. Доминирующие и дублирующие стратегии. Решение игр в смешанных стратегиях. Условия применения смешанных стратегий. Основная теорема теории игр. Решение игр в смешанных стратегиях. Пример: два игрока поочередно выкладывают на стол монеты, если совпадают «герб-герб» или «решка-решка», то игрок «A» выигрывает. Нижняя граница не равна верхней границе, значит нет решения в чистых стратегиях. Необходимо смешивать стратегии. Основная теорема теории игр (теорема Неймана). Каждая конечная игра имеет по крайней мере одно оптимальное решение, возможно, среди смешанных стратегий. Стратегия «Ai» игрока «A» называется доминирующей над стратегией «Ak», если в строке «Ai» стоят выигрыши не меньше, чем в соответствующих клетках строки «Ak» и из них, по крайней мере, один действительно больше, чем в соответствующей клетке «Ak».Если все выигрыши строки «Ai» равны соответствующим выигрышам строки «Ak», то стратегия «Ai» называется дублирующей. Аналогично определяется доминирование и дублирование для стратегий игрока «B»: доминирующей называется та его стратегия, при которой везде стоят выигрыши не больше, чем в соответствующих клетках другой и, по крайней мере, один из них действительно меньше; дублирование означает полное повторение одного столбца с другим. Естественно, что если для какой-то стратегии есть доминирующая, то эту стратегию можно отбросить, так же отбрасываются и дублирующие стратегии. Если игра не имеет седловой точки, то решение игры необходимо искать в смешанных стратегиях. В игре, в которой отсутствует седловая точка, в соответствии с основной теоремой теории игр оптимальное решение существует и определяется парой смешанных стратегий игрока «A» SA*=(p1*, p2*) и игрока «B» SB*=(q1*, q2*). p1*, p2* — оптимальные вероятности, с которыми игрок «A» использует первую и вторую стратегии (смешивает стратегии); q1*, q2* — —//— игрок «B» —//—. Выигрыш игрока «A» (проигрыш игрока «B») — случайная величина, математическое ожидание которой является ценой игры. Пусть игра задана матрицей 2×2 p1*, p2* — оптимальные вероятности (частоты), с которыми игрок «A» применяет стратегии «A1» и «A2»; q1*, q2* — оптимальные вероятности (частоты), с которыми игрок «B» смешивает стратегии «B1» и «B2».p1*+p2*=1
q1*+q2*=1 Средний выигрыш игрока «A», если он использует оптимальную смешанную стратегию SA*, а игрок «B» — чистую стратегию «B1», равен:
ν=a11*p1*+a21*p2*
ν=a12*p1*+a22*p2*
p1*+p2*=1
p1*=(a22-a21)/(a11+a22-a12-a21)
p2*=(a11-a12)/(a11+a22-a12-a21)
ν=(a22*a11-a12*a21)/(a11+a22-a12-a21)
Отыщем оптимальную стратегию игрока «B». Средний проигрыш игрока «B», соответствующий первой чистой стратегии игрока «A» («A1»), имеет вид: ν=a11*q1*+a12*q2* При использовании игроком «A» второй чистой стратегии («A2») средний проигрыш игрока «B» равен:
ν=a21*q1*+a22*q2*
ν=a11*q1*+a12*q2*
ν=a21*q1*+a22*q2*
q1*+q2*=1
q1*=(a22-a12)/(a11+a22-a12-a21)
q2*=(a11-a21)/(a11+a22-a12-a21)
ν=(a22*a11-a12*a21)/(a11+a22-a12-a21)
Нижняя цена игры совпала с верхней ценой игры, т. е. в смешанных стратегиях, также как и в чистых, существует седловая точка, соответствующая оптимальным смешанным стратегиям обоих игроков.
4. Задача Л. Эйлера. Граф. Основные понятия неориентированного графа (вершины, инцидентные ребра и вершины, степень вершины, висячие вершины, маршрут, цепь, диаметр графа). Эйлеров граф и эйлеров цикл. Граф G(X, U) — есть пара множеств X и U, где множество X≠Ø (не пустое), а пересечение множеств пусто X∩U=Ø. Каждому элементу множества U соответствует два элемента множества X. Элементы множества X — вершины, а элементы множества U — ребра.
(x1; x2)=(x2; x1) — ребро
(x1; x2)≠(x2; x1)—дуга (x1, x2 образуют упорядоченную пару) Граф, содержащий только ребра, называется неориентированным, а граф, содержащий только дуги, называется ориентированным графом. Вершина называется изолированной, если она содержит только одну петлю или ничего не содержит. Висячая вершина — это вершина, которая имеет ровно одно ребро.
Тупиковая вершина или вершина-сток — это вершина, в которую дуги только входят. Антитупиковая вершина или вершина-источник — это вершина, из которой дуги только выходят.
Вершина и ребро инцидентны, если эта вершина является одной из концевых вершин ребра. Две вершины называются смежными, если существует соединяющее их ребро. (a1’, a2’) — смежные
(a2’, a1’) — несмежные Два ребра называются смежными, если они имеют общую вершину.
Маршрут в графе — это последовательность вершин и ребер (x1, u1, x2, u2, …, xn-1, un-1, …, xn, un), таких что каждая вершина xi инцидентна ребрам ui-1, ui, т. е. каждая конечная вершина одного ребра является началом следующего ребра (нет разрыва). В маршруте ребра могут повторяться. Маршрут, в котором ребра не повторяются, называются цепью. В цепи вершины могут повторяться, а ребра нет. Цепь, в которой вершины не повторяются, называется простой цепью. Циклическим маршрутом называется маршрут, у которого начальная и конечная вершины совпадают. Если в циклическом маршруте ребра не повторяются, то такой маршрут называется циклом (вершины могут повторяться, а ребра — нет). Цикл, в котором вершины не повторяются, называется простым циклом.
Цикл в графе называется эйлеровым, если он содержит все ребра графа. Граф называется эйлеровым, если он содержит эйлеров цикл. Такой граф можно нарисовать, не отрывая карандаша от бумаги. Диаметр графа — это число, которое равно максимальному расстоянию из вершины «a» в вершину «b», взятого по всем вершинам (a, b)€X (принадлежащих множеству вершин). D=3
Степень вершины «a» (или локальная степень) — это число, равное количеству ребер инцидентных данной вершине. ρ(a)=3
5. Части графа. Связность графа. Дерево. Лес. Гамильтонов цикл и гамильтонов граф. Взвешенный граф. Рассмотрим граф G(X, U). Рассмотрим подмножество вершин X’cX и подмножество ребер U’cU. Подграф — это граф G’(X’, U’), представляющий собой пару множеств, которая порождается множеством X’. Если при этом X’ совпадает с множеством X, т. е. X’=X, то граф G’(X, U’) называется суграфом или остовным графом. Иногда говорят, что суграф — это пара множеств (X, U’), порожденная множеством U’.
Подграф и суграф являются частями графа. Полным графом называется граф, у которого любые две вершины смежны. Имеются специальные части графа, напр. звезда. Звезда вершины «a» — это часть графа, которая содержит вершину «a», все инцидентные ей ребра и вторые концы этих ребер.
Граф называется связным, если для любых двух вершин «a», «b» существует цепь из «a» в «b». Деревом называется конечный связный неориентированный граф, содержащий не менее двух вершин и не содержащий циклов. Граф называется конечным, если у него число вершин и ребер конечно. Если граф не является связным, а состоит из нескольких деревьев, то такой граф называется лесом. Циклическим маршрутом называется маршрут, у которого начальная и конечная вершины совпадают. Если в циклическом маршруте ребра не повторяются, то такой маршрут называется циклом (вершины могут повторяться, а ребра — нет). Цикл, в котором вершины не повторяются, называется простым циклом.
Простой цикл (простая цепь), содержащий каждую вершину графа, называется гамильтоновым циклом (гамильтоновой цепью). Граф, содержащий гамильтонов цикл, называется гамильтоновым графом. Граф называется взвешенным или графом с оценкой, если каждому ребру графа или каждой вершине, или и тем и другим поставлены в соответствие какие-либо числа. Напр., пропускная способность ребра (дуги), количество продуктов на складе и т. д.
6. Ориентированный граф. Путь и длина пути в графе. Простой путь и контур. Заходящие и исходящие дуги. Полустепень исхода и полустепень захода вершины. Матрица смежности графа. Матрица инциденций. Граф, содержащий только дуги, называется ориентированным графом.
Ориентированный маршрут — это маршрут, в котором направление каждой участвующей в нем дуги совпадает с направлением маршрута. Ориентированная цепь (орцепь, путь) — это ориентированный маршрут, в котором дуги не повторяются, а вершины могут повторяться.
Ориентированный цикл (контур, орцикл) — это циклический ориентированный маршрут, в котором дуги не повторяются. Простая орцепь (простой путь) — это путь, в котором вершины не повторяются. Простой контур (простой орцикл) — это контур, в котором вершины не повторяются.
Полустепень выхода (входа) для вершины «a» — это два числа ρ+(a) (полустепень выхода) и ρ-(a) (полустепень входа), которые равны числу дуг, входящих в вершину «a» (ρ-(a)) и выходящих из нее (ρ+(a)). Одной из форм представления графа являются матрицы смежности и инциденции.
Матриц смежности две: матрица смежности вершин и матрица смежности ребер. Наиболее часто применяется матрица смежности вершин. Она однозначно определяет структуру графа.
Рассмотрим матрицу смежности ребер для ориентированного графа. Она представляет собой квадратную матрицу, на главной диагонали которой стоят 0, а в клетке ij ставится 1 только в том случае, если дуга Ui непосредственно предшествует дуге Uj, 0 — в противном случае. Матрица инциденции для ориентированного графа представляет собой прямоугольную матрицу, в которой в клетку ij ставится 1 в том случае, если из вершины i выходит дуга ij, если в вершину i входит дуга ij, то в клетку ij ставится -1, в остальных случаях ставятся 0. Если граф взвешенный, то в матрице инциденции целесообразно в соответствующих клетках вместо +1 и -1 указывать «веса» дуги.
7. Понятие сети. Двухполюсная сеть. Сеть (транспортная сеть) — это совокупность следующих объектов: 1). Ориентированный граф G(X, U) конечный без петель и кратных дуг; 2). Вершина-источник, т. е. вершина, из которой дуги только выходят (обозн.: «a»); 3). Вершина-сток, т. е. вершина, в которую дуги только входят (обозн.: «z»); 4). Каждой дуге из множества «U» поставлено в соответствие число C(x, y)≥0 — пропускная способность дуги. Под C(x, y) понимается верхняя граница количества вещества, протекающего по дуге (x, y) Введем обозначения Γx — образ вершины x при отображении Γ, т. е. множество вершин, куда идут дуги из вершины x. Γx — прообраз вершины x при отображении Γ, т. е. множество вершин, из которых дуги идут в вершину x. Иногда в сети бывает несколько источников. Напр., заводы — поставщики продукции. Также в сети может быть несколько вершин-стоков. Напр., склады, принимающие на хранение продукцию.
8. Потоки в сетях. Свойства потока. Разрез сети. Теорема о максимальном потоке и минимальном разрезе. Потоком величины «U» в сети (X, U) из источника «a» в сток «z» называется функция, определенная на множестве дуг U, которая удовлетворяет следующим условиям: 0≤f(x, y)≤C(x, y) для всех (x, y)€U. f(x, y) — поток по дуге (x, y)
сумма потоков по дугам, выходящим из вершины-источника «a», равна «U». Сумма потоков, входящих в вершину-сток «z», равна «-U».
Для любой промежуточной вершины (x≠a, x≠z) сумма потоков по всем входящим в нее дугам равна сумме потоков по всем выходящим из данной вершины дугам. Условие 1 представляет собой систему «n» линейных уравнений, где «n» — число вершин (уравнение баланса потоков для каждой вершины). Неизвестными являются дуговые потоки f(x, y); их число равно «m» — числу дуг.
Условие 2 означает, что поток f(x, y) по дуге ограничен максимальной пропускной способностью дуги. Разрезом сети (X’, X’) называется множество дуг (xixj), для которых начало xi€x’, а xj€x’. разрез сети отделяет вершину-источник от вершины-стока, т. к. a€X’, z€X’, т. е. разрез сети — это множество дуг, удаление которых из сети делает сеть несвязной. Говорят, что разрез сети блокирует сток.
(X’, X’)={(x2, z), (x1, x5), (x4, x5)}
Пропускной способностью или величиной разреза C(x’, x’) называют сумму пропускных способностей дуг, т. е. которую берут по всем ориентированным дугам, соединяющим узлы, лежащие в x’, с узлами, лежащими в x’. C(x, x’)=C(x1, x2)+C(x3, x4)
По аналогии с пропускной способностью разреза можно определить значение потока на разрезе
Имеет место основная теорема теории потоков, которая формулируется следующим образом (Форда-Фалкерсона): для любой сети (X, U) максимальная величина потока равна минимальной пропускной способности разреза.
9. Постановка сетевых задач таможенной деятельности. Задача о максимальном потоке. Задача о потоке минимальной стоимости. Задача коммивояжера. Задача о замене оборудования. Задача поиска кратчайшего пути. Основной задачей теории потоков является задача определения величины максимального потока в сети, которая формулируется следующим образом: определить
при ограниченияхU≥0 0≤f(x, y)≤C(x, y) для всех (x, y)€U Данная задача является задачей линейного программирования. Однако, в данном случае при ее решении более эффективными являются сетевые методы, чем симплекс-методы. Задача о потоке минимальной стоимости. Дана двухполюсная сеть (X, U) с источником «a», и стоком «z». Для каждой дуги (x, y)€U задана максимальная пропускная способность C(x, y) и стоимость доставки по ней единицы потока r(x, y). Необходимо найти поток от источника в сток заданной величины U, имеющий минимальную стоимость доставки.
Математическая модель в задаче имеет следующий вид: при ограничениях 0≤f(x, y)≤c(x, y) для всех (x, y)€U Задача о замене оборудования.
C0=1,6 млн 1 год — 0,5 2 — 1,0 3 — 1,5 4 — 2,2
1 год — станок приобретен Станок печатный, который можно либо обновлять ежегодно, либо эксплуатировать. На каком году следует обновлять оборудование, чтобы минимизировать расходы? Станок можно обновлять на любом году.
1). Xij 2). 3). Xij≤Aij
Xij — двоичн. или Xij≥0 4). Строка «Всего»=Строка «Необходимо» Во «Всего»: «Итого» в столбце – «Итого» в строке
В «Итого»: сумма по строке, сумма по столбцу
В «Необходимо»: Год 1=1Год 5=-1 Год 2 — Год 4=0
Целевая функция: матрица стоимости*матрица неизвестных. Поиск кратчайшего пути. Компания занимается поставками продуктов в сеть различных пунктов. Необходимо определить кратчайший путь из вершины «H» в вершину «5». Одной из форм представления графа является матрица смежности вершин или ребер. Чаще используется матрица смежности вершин. Решение:
1. Разработка математической модели задачи
Целевая функция данной задачи имеет следующий вид: cij — длина ребра ij n — число вершин, n=8
xij=1, если i, j — смежны=0, если i, j — не смежны
10. Сетевое планирование. Правила построения сетевых моделей. Параметры построения сетевых моделей (ранний/поздний срок свершения j-го события, ранний срок начала/окончания работы, поздний срок начала/окончания работы, полный резерв времени работы, полный резерв времени пути). Методы расчета параметров сетевых моделей. Сетевое планирование основано на моделировании процесса с помощью сетевого графика и представляет собой совокупность расчетных методов, организационных и контрольных мероприятий по планированию и управлению комплексом работ. Сетевая модель представляет собой план выполнения некоторого комплекса взаимосвязанных работ, представленный графически в виде сетевого графика. С математической точки зрения сетевой график — это связный взвешенный ориентированный граф без петель и контуров. Сетевые графики составляются на начальном этапе планирования. В начале планируемый процесс разбивается на отдельные работы, составляется перечень работ и событий, продумываются их логические связи и последовательность выполнения, работы закрепляются за ответственными исполнителями.
Затем составляется сетевой график. После упорядочения сетевого графика рассчитываются параметры события и работ, определяются резервы времени и критический путь. Наконец проводятся анализ и оптимизация сетевого графика, который при необходимости вычерчивается заново с пересчетами параметров событий и работ.
При построении сетевого графика необходимо соблюдать ряд правил:
1). На графике рекомендуется иметь одно исходное и одно завершающее событие (как в теории потоков в сетях) 2). В сетевом графике не должно быть «хвостовых» событий, которым не предшествует хотя бы одна работа, за исключением первого
3). В сетевом графике не должно быть «тупиковых» событий, т. е. событий, из которых не выходит ни одна работа, за исключением завершающего события 4). В сетевом графике не должно быть циклов, контуров и петель 5). Любые два события должны быть связаны не более чем одной работой, т. е. не должно быть параллельно выполняемых работ
11. Анализ сетевых моделей. Определение критического пути. Оптимизация сетевых моделей. См. вопр. 10.
12. Понятие и предмет теории массового обслуживания. Составляющие СМО: каналы, заявки и процедуры обслуживания. Однородные каналы СМО. Фаза обслуживания. Системы массового обслуживания (СМО) — системы, на вход которых поступает поток заявок (требований). Примерами таких систем являются: ремонтные мастерские, магазины, парикмахерские, пункты таможенного контроля и т. д. Каждая СМО состоит из какого-то числа обслуживающих единиц, называемых каналами обслуживания. Каналами обслуживания могут быть: кассиры, продавцы, таможенник и т. д.
СМО могут быть одноканальными и многоканальными в зависимости от числа обслуживающих каналов. Каналы обслуживания, способные удовлетворять только одинаковые заявки, называются однородные. Итак, всякая СМО предназначена для обслуживания какого-либо потока заявок, поступающих в какие-либо случайные моменты времени. На практике часто обслуживание заявок осуществляется последовательно несколькими каналами обслуживания (так называемые
СМО). При этом, очередной канал обслуживания начинает работу по обслуживанию заявки только после того, как предыдущий канал завершит свою работу. В таких СМО процесс обслуживания носит многофазовый характер, а обслуживание одной заявки одним каналом называется фазой обслуживания. Обслуживание заявки продолжается какое-то случайное время, после чего канал освобождается и вновь готов к приему следующей заявки. Т. е. в СМО, кроме входящего потока заявок, существует еще поток обслуживания (поток обслуженных заявок).
Заявка, пришедшая в СМО и заставшая все каналы занятыми, или становится в очередь или покидает СМО. По данному критерию СМО делятся на: 1). СМО с ожиданием (с очередью); 2). СМО с отказами. Теория МО (ТМО) — область прикладной математики, которая занимается исследованием процессов в системах МО. Пример ТМО — построение математических моделей, связывающих заданные условия работы СМО (число каналов обслуживания, производительность каналов, характер потока заявок) с показателями эффективности СМО, описывающими ее способность справляться с потоком заявок. В качестве таких показателей могут применяться: среднее число заявок, обслуживаемых в единицу времени; среднее число заявок, стоящих в очереди; среднее время ожидания обслуживания.
13. Потоки событий. Регулярность и стационарность потоков. Потоки с/без последействия. Ординарность потоков. Простейший поток событий. Поток Пальма и поток Эрланга. Потоком событий называется последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени. Напр., поток покупателей в супермаркете, поток отказов компьютера и др. Поток событий называется регулярным, если события следуют одно за другим через определенные равные промежутки времени.
На практике чаще встречаются нерегулярные потоки со случайными интервалами времени между событиями. Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени.
Основной характеристикой потока является интенсивность потока событий (заявок) — λ.
λ=[1/c], [1/мин] Для стационарного потока λ=const (постоянна). Поток событий называется ординарным, если в нем вероятность одновременного прибытия двух и более событий равна нулю. Поток называется потоком без последействия, если для любых двух непересекающихся интервалов времени T1, T2 число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой. По сути это означает, что события, образующие поток, появляются в те или другие моменты времени независимо друг от друга, вызванные каждое своими собственными причинами. Напр., поток пассажиров, входящих в метро, практически не имеет последействий, а поток покупателей, отходящих от прилавка с купленными товарами, уже имеет последействия (хотя бы потому, что интервал по времени между отдельными покупателями не может быть меньше времени обслуживания каждого из них t0). Установлено, что минимальный интервал между событиями много меньше среднего интервала между ними:
tmin<<t, t=1/λ Поток событий называется простейшим, если он обладает сразу тремя свойствами: стационарен, ординарен, без последействия. Важным, основным свойством простейшего потока, отличающим его от других потоков, является то, что время между прибытиями двух соседних событий распределяется по экспоненциальному (показательному) закону:
P(t>T)=1-e-λT, T — случайное время между прибытиями двух соседних событий (заявок); λ — интенсивность потока событий. Простейший поток является предельным потоком, к которому стремятся суммы потоков, не являющиеся в отдельности простейшими. Простейший поток накладывает самые жесткие условия на СМО.
Поток событий называется рекуррентным (или потоком Пальма), если он стационарен, ординарен, а интервал времени между событиями является не экспоненциальным, а каким-либо другим.
14. Случайные процессы. Марковский случайный процесс. Условия возникновения Марковского процесса. Пусть СМО «S» представляет собой таможенный пункт с двумя точками досмотра. Тогда, при прибытии на пункт пассажиров, пункт может находиться в следующих состояниях: S0 — свободное, S1 — одна точка досмотра занята, другая — свободна, S2 — обе точки досмотра заняты. Вероятности состояний (вероятности нахождения СМО в состоянии S0, S1, S2) обозначим P0(t), P1(t), P2(t).
Получается так, что в любой момент времени t наша система может находиться в одном из состояний S0, S1, S2, поэтому можно записать
P0(t)+P1(t)+P2(t)=1. Эта формула называется нормировочным условием. С математической точки зрения процесс работы будет состоять в том, что наша система «S» случайным образом переходит из одного состояния «Si» в другое состояние «Sj» под воздействием входящего потока и времени досмотра пассажира (потока обслуживания). В этом случае говорят, что в системе «S» протекает случайный процесс. Случайный процесс, протекающий в СМО, представляет собой изменение случайным образом состояний системы под воздействием входящего потока заявок и возможностей системы по их обслуживанию.
Случайный процесс называется марковским или процессом без последействия, если для любого момента времени t0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент времени t0 и не зависит от того, когда и как система пришла в это состояние. Примеры: счетчик Гейгера, воздушный бой. На практике марковские случайные процессы в чистом виде почти не встречаются, но часто приходится иметь дело с процессами, для которых влиянием «предыстории» можно пренебречь. В этом случае можно применять при изучении подобных процессов марковские модели. Марковские случайные процессы делятся на два класса: 1). Процессы с дискретными состояниями; 2). Процессы с непрерывными состояниями.
Процесс называется процессом с дискретными состояниями, если его возможные состояния можно заранее перечислить (перенумеровать), переход от состояния в состояние происходит мгновенно.
В одном из кабинетов таможенного поста имеются 2 телефона. Возможны состояния телефонов: S0 — два телефона свободны, S1 — первый занят, второй свободен, S2 — первый свободен, второй занят, S3 — два телефона заняты. Процессы с непрерывными состояниями отличаются тем, что переход системы из состояния в состояние протекает плавно, непрерывно, постепенно. Эти процессы более характерны для экономических систем. Напр., непрерывное расходование товаров на складе.
На практике чаще (особенно в таможенной деятельности) встречаются процессы с дискретными состояниями. Процессы с дискретными состояниями в свою очередь подразделяются на 2 группы: 1). Процессы с дискретным временем перехода из состояния в состояние (цепи Маркова); 2). Процессы с непрерывным временем перехода из состояния в состояние. В практике таможенной деятельности чаще встречаются случайные процессы с дискретными состояниями и непрерывным временем перехода системы из одного состояния в другое. На характер протекания случайного процесса в СМО решающее значение оказывают входящий поток заявок и поток обслуживания (выходящий поток).
15. Граф состояний СМО. Уравнения Колмогорова. Как правило, СМО изображают ввиде размеченного (взвешенного) графа состояний. Система «S» может находиться в четырех состояниях «S1», «S2», «S3», «S4». Переход системы из состояния в состояние происходит под действием потоков с интенсивностями λij Имея размеченный граф состояний, можно найти все вероятности состояний pi(t) как функции времени. Для этого составляются и решаются уравнения Колмогорова — особого вида дифференциальные уравнения.
dp1(t)/dt=-λ12p1(t)-λ13p1(t)+λ21p2(t)
dp2(t)/dt=-λ21p2(t)-λ24p2(t)+λ12p1(t)+λ32p3(t)
dp3(t)/dt=λ13p1(t)+λ43p4(t)-λ32p3(t)
dp4(t)/dt=λ24p2(t)-λ43p4(t)
Обязательно добавляется еще одно уравнение:
p1(t)+p2(t)+p3(t)+p4(t)=1 (нормировочное условие)
Эта система линейных ДУ решается при начальных условиях: t=0; pi(t)=1; pj(t)=0; i≠j; i=1, …, n; pi(t) — вероятность какого-то состояния; pj(t) — все остальные вероятности. Решая систему линейных ДУ, можно получить вероятность всех состояний как функций времени: p1(t); p2(t); p3(t); p4(t).
Как меняются вероятности pj(t) со временем? Стремятся ли они к какому-либо пределу?
Оказывается, если СМО проработала достаточное количество времени, наступает в системе предельный стационарный режим. Условно пишут, что он наступает при t→∞. В данном режиме вероятности состояния системы pj(t) стремятся к своим предельным значениям, которые не зависят от времени: pj(t)→pj. Их называют финальными вероятностями. В этом случае в ДУ Колмогорова левые части приравниваются к 0, т. е. dpi(t)/dt=0, и система ДУ Колмогорова превращается в систему линейных уравнений.
0=λ21p2-(λ12+λ13)p1
0=λ12p1+λ32p3-(λ24+λ21)p2
0=λ13p1+λ43p4-λ32p3
0=λ24p2-λ43p4
По физическому смыслу финальная вероятность представляет собой среднюю долю времени нахождения системы в соответствующем состоянии. Напр., p1=20%. Это означает, что в среднем 20% времени СМО будет находиться в состоянии «S1».
Поскольку данная система (2) не содержит свободных членов, она имеет бесчисленное множество решений. Поэтому, чтобы ее решить, необходимо добавить такое условие
p1+p2+p3+p4=1 — нормировочное условие.
Работа СМО характеризуется показателями эффективности (характеристики СМО). Показатели эффективности рассчитываются только для предельного стационарного режима. Поэтому для определения показателей эффективности, необходимо составлять не ДУ Колмогорова, а систему линейных уравнений для финальных вероятностей.
16. Процессы «рождения-гибели» среди однородных Марковских процессов. Имея размеченный граф состояний, можно легко написать систему линейных уравнений для финальных вероятностей. Для некоторых случаев удается данные уравнения решить заранее в общем виде. В частности, это удается сделать, если граф состояния системы представляет собой так называемую «схему рождения и гибели» Особенностью данного графа является то, что все состояния системы можно «вытянуть» в одну цепочку. Термин «схема рождения и гибели» ведет начало от биологических задач, где подобной схемой описывается изменение численности популяции. Примером модели чистого рождения является процесс оформления свидетельства о рождении детей. В качестве модели чистой гибели может служить случайное изъятие хранящихся на складе запасов (без пополнения).
Пользуясь графом, составим и решим алгебраические уравнения для финальных вероятностей:
S0: 0=-λ01p0+λ10p1 => λ01p0=λ10p1 => p1=λ01p0/λ10 S1: 0=λ01p0-λ10p1-λ12p1+λ21p2 => -(λ10p1-λ01p0)-λ12p1=λ21p2 => λ12p1=λ21p2 => p2=λ12p1/λ21 => (подстановка p1) p2=λ01λ12p0/λ10λ21… p3=λ01λ12λ23p0/λ10λ21λ32
… pn=λn-1,n … λ12λ01p0/λn,n-1 … λ21λ10
Т. о., все вероятности состояний СМО p0, p1, p2, …, pn можно выразить через одну вероятность — p0.
Подставим выражения для всех вероятностей p1, p2, …, pn в нормировочное условие. Получим:
p0(1+λ01/λ10+λ12λ01/λ21λ10+…+λn-1,n…λ12λ01/λn,n-1…λ21λ10)=1 Отсюда: p0=(…)-1
Остальные вероятности вычисляются через p0. Полученные формулы используются при решении задач теории МО.
17. Одноканальная СМО с отказами в обслуживании и ее характеристики. Система с отказами: отсутствует очередь. λ(t)=const
μ=const Pk(t)=(λt)ke-λt/k! (распределение Пуассона)
k — количество событий за время t P(T<t)=1-e-λt (экспоненциальное распределение)
T — интервал времени между заявками
dP0/dt=-λP0+μP1
dP1/dt=-λP0-μP1
P0(0)=1
P1(0)=0
P0+P1=1
ρ=λ/μ<1
P0=μ/(λ+μ)+λe-(λ+μ)t/(λ+μ) — решение уравнения Колмогорова для нестационарного режима
P1=1-P0
Для стационарного режима:
P0=μ/(λ+μ)
P1=λ/(λ+μ)
q=μ/(μ+λ)
Абсолютная пропускная способность системы:
A=λq=λμ/(λ+μ)
Вероятность отказа (= вероятности занятости только для одноканальной системы):
Pотк=1-q=λ/(λ+μ)
18. Многоканальная СМО с отказами в обслуживании и ее характеристики. Примерами многоканальных СМО с отказами являются: офисы коммерческих предприятий с несколькими телефонными каналами и т. д.
Рассмотрим СМО с «n» каналами.
Размеченный граф состояний имеет следующий вид
S0 — все «n» каналов свободны
S1 — один канал занят, остальные — свободны
Задача ставится так: имеется «n» каналов (линии связи), на которые поступает поток заявок с интенсивностью λ. Поток обслуживаний имеет интенсивность μ. Требуется найти показатели эффективности данной СМО. Составим линейные уравнения для финальных вероятностей состояний системы. Получим:
S0: 0=-λp0+μp1
S1: 0=λp0-μp1-λp1+2μp2
…
Sn: 0=λpn-1-nμpn
p1+p2+…+pn=1
Размеченный граф соответствует «схеме рождения и гибели» => вероятности всех состояний системы p1, p2, …, pn можно выразить через p0.
Решим данную систему.
Из первого уравнения получим:
p1=λp0/μ; λ/μ=ρ
p1=ρp0
Из второго уравнения получаем:
p2=(λ/μ)2p0/2=ρ2p0/2
p3=ρ3p0/(1*2*3)
p4=ρ4p0/(1*2*3*4)
pn=ρnp0/n!
Подставив в нормировочное условие, получим:
p0=(1+ρ/1!+ρ2/2!+…+pn/n!)-1
λ=1/Tз
μ=1/Tобс
ρ=λ/μ
Вероятность того, что система свободна:
Вероятность того, что заняты «k» каналов:
Pk=ρkp0/k! Вероятность отказа (вероятность того, что заняты все каналы): Pотк=Pn=ρnp0/n!
Вероятность обслуживания (относительная пропускная способность): Q=Pобс=1-Pотк=1-ρnp0/n! Абсолютная пропускная способность:
A=λQ
Среднее число занятых каналов:
nз=A/μ=ρp0(1-ρn/n!)
Коэффициент занятости каналов:
kз=nз/n=ρPобс/n
Среднее время пребывания заявки в системе:
TСМО=nз/λ
19. Одноканальная СМО с ограниченной длиной очереди и ее характеристики. Варианты вычислений для ρ=1, ρ<1, ρ>1. Формула Литтла. См. вопр. 21.
P0=(1-ρ)/(1-ρm+2), ρ<1
m — количество мест в очереди
Вероятность того, что заняты «k» каналов и само устройство:
Pk+1=ρk+1P0
Вероятность того, что все места заняты (вероятность отказа):
Pотк=Pm+1=ρm+1P0
Относительная пропускная способность:
Q=1-Pотк=1-ρm+1P0
Абсолютная пропускная способность:
A=λQ=λ(1-ρm+1P0)
Средняя длина очереди:
Lоч=(1-ρm(m-mρ+1))ρ2P0/(1-ρ2)
Среднее время пребывания в очереди:
Tоч=Lоч/A
20. Одноканальная СМО с неограниченной очередью и ее характеристики.
m→∞
P0=1-ρ
Вероятность отказа:
Pотк=0
Относительная пропускная способность:
Q=1
Абсолютная пропускная способность:
A=λ
λ — поток заявок
Средняя длина очереди:
Lоч=ρ2/(1-ρ)
Среднее время пребывания в СМО:
TСМО=1/(μ(1-ρ))
21. Многоканальная СМО с ограниченной длиной очереди и ее характеристики. Рассмотрим многоканальную СМО, на вход которой поступают заявки с интенсивностью λ, требующие обслуживания. Размеченный граф данной системы имеет вид: Sn+m — все каналы заняты и все места в очереди заняты m — число, ограничивающее количество заявок в очереди Имея граф состояний, можно составить систему линейных уравнений для финальных вероятностей состояний системы:
S0: 0=-λp0+μp1
…
0=λpn+m-1-nμpn+m
p0+p1+…+pn+m=1
Введем обозначения:
λ/μ=ρ
Тогда выражения для финальных вероятностей состояний системы примут следующий вид:
p1=ρp0/1!
p2=ρ2p0/2!
…
pn=ρnp0/n!
pn+1=ρn+1p0/nn!
pn+2=ρn+2p0/n2n!
…
pn+m=ρn+mp0/nmn!
Поскольку граф соответствует «схеме рождения и гибели», финальные вероятности всех состояний системы можно выразить через вероятность начального состояния P0. Подставим все полученные выражения для финальных вероятностей в нормировочное условие. Получим:
p0=[1+ρ/1!+ρ2/2!+ρn/n!+ρn+1/nn!+ρn+2/n2n!+…+pn+m/nmn!]-1
Используя выражения для определения суммы членов геометрической прогрессии, формулу можно переписать в виде: Имея формулы для расчета вероятностей всех состояний системы, можно записать формулы для определения показателей эффективности СМО:
1). ρ=λ/μ
2). Pотк=Pn+m=ρn+mP0/nmn!
3). Q=Pобс=1-Pотк
4). A=λQ
5). Среднее число занятых в обслуживании канала:
nз=A/μ=ρQ
6). kз=nз/n
7). Вероятность образования очереди:
Иногда эту характеристику не рассчитывают, а рассчитывают сразу среднее число заявок, находящихся в очереди:
8). Lоч=(ρn+1/nn!)(P0(1-(ρ/n)m(m+1-mρ/n))/(1-ρ/n)2)
Данная формула имеет место, если ρ/n≠1, ρ≠n.
А если ρ/n=1, то длина очереди рассчитывается по следующей формуле:
Lоч’=(ρn+1/nn!)((P0m(m+1))/2)
9). Среднее время ожидания в очереди (формула Литтла):
Tоч=Lоч/A
Tоч’=Lоч’/A
10). Среднее время пребывания заявки в системе:
TСМО=Tоч+tобс
tобс=1/μ
22. Многоканальная СМО с неограниченной очередью и ее характеристики. Рассмотрим многоканальную СМО с неограниченной длиной очереди.Размеченный граф состояний данной системы имеет вид: Вероятности состояний полученных формул для многоканальной СМО с ограниченной длиной очереди при переходе к пределу при m→∞.
Сумма геометрической прогрессии в выражении для P0 расходится: при уровне загрузки ρ/n>1 очередь будет бесконечно возрастать, а при ρ/n<1 ряд сходится, что определяет установившийся стационарный режим работы СМО, для которого и определяются финальные вероятности состояний:
P0=[1+ρ/1!+ρ2/2!+…+ρn/n!+ρn+1/n!(n-ρ)]-1
Транспортная задача. Транспортная задача является одной их первых потоковых задач, которая была сформулирована и решена в 1914 г. американским ученым Хичкоком. Данная задача является частным случаем изученной ранее задачи о нахождении потока минимальной стоимости. В этой задаче рассматриваются предложения грузов (товаров) от «m» поставщиков в объемах «a1, a2, …, am» и спрос «n» покупателей в объемах «b1, b2, …, bn»; затраты на перевозку единицы груза от i-поставщика к j-покупателю составляют Cij; объемы перевозимых грузов соответственно составляют xij, которые необходимо определить.
Математическая модель имеет следующий вид:
xij≥0 Модель этой задачи может быть представлена в виде сети, если вершинам поставить в соответствие продавцов и покупателей, а ориентированным дугам — пути для перевозки грузов.
2. Тема- Налоги- понятие и значение Выполнила студентка 4 го курса
3. Первых Богов создал Страх primos deos fecit timorс Петроний ум
4. Внутренние болезни Определение
5. это окислы кремния алюминия железа и щелочных металлов
6. ТЕМА 2 Прийняття управлінських рішень
7. ~рекетті~ ма~ыздылы~ын к~рсеткен к~рнекті орыс ~алымы
8. О садоводческих огороднических и дачных некоммерческих объединениях граждан слов жилое строение на ин
9. Электрическое оборудование автомобиля Выполнил студент 051 г
10. КОНТРОЛЬНАЯ РАБОТА ПО ТРУДОВОМУ ПРАВУ
11. Ощущение
12. Теория бухгалтерского учета.html
13. Видеозанятия в системе обучения иностранной речи
14. і Аралас саба~ты~ ~~рылымы ~р т~рлі болады
15. Курсовая работа- Изучение программ CorelDraw и AutoCAD
16. Концепція невизначеності квантової механіки
17. Hog who hd mnymny friends He ws very kind hedgehog nd liked his friends very much
18. Реферат- Народный календарь и круг жизни русского крестьянина
19. Мой ребенок в 3 классе
20. первобытное искусство