Шпоры по ЭММ

1.ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ. Операция – действия направленные на достижение некоторых целей. Операция д.б.спланирована желательно оптимальным образом. Для этого полезно составить ее ЭММ. Она выглядит следующим образом : W = W (а1, а2,…, аm ; х1,х2, … ,хm ) При этом W – прибыль (целевая функция) или потери(функция потери). а1, а2,…, аm - известные параметры операции, они не управляемы. х1,х2, … ,хm -управляемые параметры

их можно выбирать самим, но на них м.б.положены какие-либо ограничения. Задача заключается в оптимизации операции, т.е. в нахождении значений х1,х2, … ,хm при котором целевая функция была бы max-ой или функция потерь была бы min-ой. Одну из этих функций можно перевести в др.изменив знак. Описанная модель является детерминированной. Модель м.б.и не детерминированной.

H > W = W (а1, а2,…, аm ; в1,в2,…, вk; х1,х2, … ,хm) , где в1,в2,…, вk - неизвестные параметры Обычно предполагается в1,в2,…, вk - это случайные величины с известными распределениями чтобы математическое ожидание (ср.значение W) была max, если целевая функция или min, или функция потерь. 2.ЛИНЕЙНОЕ ПРГРАМИРОВАНИЕ (ПЛАНИРОВАНИЕ). Пример: 1) задача о рационе питания. Найти неотрицательные х1,х2, … ,хm жиров?15; белков?10; углеводов?5;витамины?20; цена д.б. min

Модель: W= 150х1 +10х2 +20х3 +15х4 +20х5+50х6 110х1 +х2+0х3 +3х4+0х5 +0х6 ?15 40х1+2х2+20х3+15х4+3х5+2х6 ?10 Х1 +0х 2+0х3 +5х4+6х5+15х6?20 Min функцию 1 при ограничении 2 хi ?0 2)Транспортная задача. Имеется S1, S2… Sm на котором соответственно находится в1,в2,…, вk . имеется Р потребителей Р1,Р2,…Рn которым соответственно требуется а1, а2,…, аm этого продукта. Перевозка этого продукта со склада S > потребителю

Рi,потребителю стоит Pj . Пусть заявки удовлетворим, т.е. а1+…+аn ? в1 +…+вn Требуется, составит план перевозок с min стоимостью. Пусть хij -кол-во товара перевозимого из Si>Рj , тогда стоимость всех перевозок = : W = tij xij При этом должны выполнятся следующие условия: ? хij =аj j=1,2,…n Всего с i склада мы вывозим ? хij ? вi i=1,2,…m Требуется найти неотрицательное значение переменных

хij ( m*n штук), которые min-уют функцию 3 при ограничении 4 . имеются много др.операций кот-ых и функция W и ограничения линейны, т.е. представляют ? переменных с несколькими коэф-и. 3.ОСНОВНАЯ ЗАДАЧА ЛИНЕЙНОО ПОГРАМИРОВАНИЯ. Требуется найти неотрицательное значение переменных х1,х2, … ,хn при которых функция W=С1х1 +С2х2+…+Сnхn Принимает min значение и кроме того выполнены ограничения а11х1+а12х2+…+а1mхn = в1 а21х1 +а 22х2 +…+а2m хn= в2 …. аm1х1 +аm2х2+…+аmnхn = вn

Неотрицательное значение х1… хn называется допустимым решением если они удовлетворяют ограничение (2) .Оптимальное решение это допустимое решение(ДР) min-щее функцию (1) ОЗРП необязательно имеет решение, что система (2) вообще не имеет решений или допустимых решений. ДР есть, но среди них нет ОР. Система (2) совместна (теорема Кронекера - Капелли), когда ранг матрицы системы = рангу расширенной матрицы.

Пусть система совместима и ранг r = n (числу переменных). В этом случае система (2) имеет единственное решение. Если оно является допустимым (неотриц.), то оно же является и ОР. Пусть m = r < n в этом случае k = n-m ~ n-vможно выбрать произвольно свободную переменную, тогда остальные переменные х1,х2, … ,хn (зависимые – базовые)переменные однозначно определяются по выбранным

значениям свободных переменных. Система (2) имеет бесконечное множество решений среди которых м.б.и допустимые, а из них можно выбрать ОР. 4.ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРИТАЦИЯ ОЗЛП. Пусть k = n-m = 2, т.е. 2 переменные для определения х1 и х2 являются свободными, тогда разрешая систему (2) относительно остальных переменных получим х3 = L31x1 + L32x2 + x2?3 x4 = L41x1 + L42x2 +…+?n x5 =

L51x1 + L52x2 +…+?n предоставляем (3) поучаем выражение : W = х1 + х2+? Т.о.остается выбирать значение х 1и х2, так чтобы (3) тоже неотрицательными, а функция (4)-min. Возьмем систему координат х и х , тогда каждому набору переменных х1и х2будет соответствовать точка (х1 ;х2 ). Все переменные д.б.неотриц-ми. Рассмотрим прямую: х1 =0 L1: x1 =0 L2: x2=0 L3: x3=0 L31x1+L32x2+?3=0 Аналогично получаются остальные

L4: x4? 0 и т.д. ОДР представляет собой многоугольник Среди ОДР есть ОР. Найдем ОР. Рассмотрим L5: x5= 0 L: W = j1x1 + j2x 2+ =0 Следовательно, если прямую L ¦ себе перемещать в указанном стрелкой направлении, то W – уменьшается W д.б.min, значит, что нужно взять крайнее положение линии

L при котором она имеет общие точки. ОР-min возможное решение. Т.о. ОР находится в крайнем положении линии L, которая есть вершиной многоугольника. Вершины многоугольника, точку которые пересекаются (хотя бы 2) прямых Li,т.е. по крайней мере 2 прямых ОР = 0. Пусть теперь свободных переменных 3: х1,х 2,х3. Набор х1,х2,х3 представляем точкой в трехмерном пространстве.

Остальные переменные х4,х5 … хn мы выразим через х1,х2, хn получим уравнение аналогичное (3). Р1: х1 ? 0 х20 х3 Р2: х2 =0 х10 х3 Р3: х3=0 х 10 х2 Р4= х4= ?41х1+ ?42х2+ ?43 х3+?4= 0 Остальные плоскости Р5 …Рnограничат нам пространство многоугольник. Рассмотрим плоскость Р: W = 0. аналогичная картина и при большем числе свободных переменных.

Технически выполнить эти построения сложно. 5.ОЗЛП С ОГРАН-ЫМИ НЕРАВЕНСТВАМИ. ПЕРЕХОД ОТ РАВЕНСТВ К НЕРАВЕНСТВУ И НАОБОРОТ. А) неравенство> равенство Пусть имеется ограниченное неравенство а11х1 +а12х 2+…+а1nх n? в1 а 21х1+а22х2 +…+а2nхn? в2 … Переведем первые два неравенства к виду в1- а11х1 +а12х 2+…+а1nх n ?0 а 21х1+а22х2 +…+а2nхn - в2 > 0 введем вспомогательные обозначения у1 = в1- а11х1 – а12 х2 - …-

а1n хn ?0 у2 = а21х1 +а22 х2 +…+а2n хn - в2 W- при этом не изменяется Введем вместо ограничения (1) ограничение (3), которое является равенством. Все переменные в новом ОЗЛП д.б 0, в том числе у1 ,у2 . будет выполнено ограничение (2), а ограничение (1) , т.о. вместо каждого неравенства можно записать ограничение , но при этом увел.кол-о элементов на кол-о определенного нерав-а. Б) равенство > неравенство.

Пусть имеются ограничения рав-ва. Выражая базовые переем-е через свободное получаем: xk+1 =Lk+1 x1 +…+ Lk+1 xn +?k+1 xn = L2n x1 + … + Lnk xn + ?­n W = j1 x1 + … + x2 + По смыслу задачи все переменные д.б. не отрицательными, поютому переем-е хk+1 … хn можно из задачи исключить. Каждое равенство заменненое на неравенство уменьшает кол-во переменных на ед-цу. Lk+1 x1 + … + Lk+1 xk + ?k+1 ? 0 …… 6.СМПЛЕКС МЕТОД.

Если число переем-ых больше 2, то задачу лин-го прогр-я геометрически решить нельзя. В таких случаях прим-ся симплекс метод. Пр-р: min-ть функцию w = 5х1-2х3 -5х1 – х2 +2х3 ? 2 -х­1 – х3 + х4 ? 5 -3х1 +3х4 ? 7 Переходя к ограничениям рав-ва получаем: у1 = 5х1 + х2 - 2х3 +2 у2 = х1 – х3 – х4 + 5 у3 = 3х1 +3х4 + 7 Имеются m = 3(урав) переем-ых n = 7 r = 3 след-но k = n-r =7-3=4 – своб-ых переем-ых,т.е. в вершинах ОДР 4 переем-ых = 0. пусть это будут всегда свободные

переем-е.выберем 4 своб-ых переем-ых, напр-р: х­1,х2 ,х3 ,х4 если все они = 0, то из (3)мы получаем у1 =2 у2 =5 у3 =7 –это допустимое решение. В этой вершине W = 5*0-2*0=0 Посмотрим нельзя ли W умень-ть? Смотрим на выражение (1) W-будет уменьшаться,если уменьшается х1 , но х1 =0 и умен.его нельзя. W – будем уменьшат, если увеличивать х3 . Из (3) следует,что (из 1 урав-я) видно, что х можно увеличить

до 1 , из 2 ур-ия до 5. Т.о. х3 можно увеличить до 1. Пусть х3 =1,при этом у­1 =0 – это 4-й 0 вместо х3 . Т.о свободными переем-ми будут: х 1 ,х2 ,х3 ,у1 . Систему (3) мы должны разделить относительно остальных переем-ых х3 =5/2х­1 +1/2х­2 у1 +1 у2 =3/2 х1 х2 у1 –х4 + 4 у3 =3х1 -5х4 +7 W = -х2 + у1 - 2 В опорной точке х1 = х2 =х4 =у1 =0 х3 =1 у2 =4 у3 =7

W= -0 + 0 – 2 Посмотрим нельзя ли его еще уменьшить? Можно увел-ть х3 из выражения (5) и в 1 ур-ии нет ограничений. Во 2-ом yр-ии х3 -можно увел-ть до 1 В 3 ур-ии нет огранич-ия до 1 при этом у2 =0, свободные перем-ые х1 ,х4 ,у1,у2 . Получим х2 = -3х1 -2х4 +у1 -2у2 +8 х3 = х1-х4 +5 у3 = 3х1 - 5х4 +7 W = 3х1 +2х4 - 2у2 -10 В нашей опорной точке где переем-е ?

0; Х1 =х4 =у1 =у2 =0 х2 =8 х3 =5 у3 =7 улучшить решение здесь нельзя,т.к. из (7) следует что надо уменьшить х1 ,х4 ,у1,у2, но т.к. они = 0 это невозможно. Т.о. оптимальным решением этой задачи яв-ся х1 =0, х2 =8, х3 =5, х4 =0, Wmin = -10 7.ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ. В неск-их задачах помимо хi ?0, м.б. требование целочисленности хi ,т.е. (0,1,2…)это когда дробное значение не применимо по смыслу. Такие задачи называют задачи целочисленного программирования.

Не всегда ОР получается как округление дробного решения. ОДР - узлы сетки. ДР – многоугольник . построим новую вершину, так чтобы ее вершины были целочисленными. Это метод отсекающих плоскостей. Задача от-ся к решению обычной задачи прогр-ия. 8.НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. W = W( х1 … хn ) = 0 …… f1 (х1 … хn) = 0 ……… fm (х1 … хn) = 0 ОР м.б.как внутри так и на границе. Если внутри – это точка локального min функцию.

Вне этой точке все частные произв-е =0, т.е. w/ x1 = 0 i= 1…n Если решение на границе – переменные связаны условиями 2, эта задача называется задача на условные экстремумы решения как множ-и Лагранже. 9.ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ.(д/п) В д/п рассматривается многошаговые операции, напр-р: планирование работы предприятия на неск-ко месяцев, лет. Требуется спланировать повышение произв-ти труда (ПТ) и соц-х условий в течении 6 лет, от начала

уровня S0 до конечного S1 . Каждый год мы повышаем только ПТ ли соц.условия, т.е. S0 к S1 можно двигаться в право, либо вверх. Если в право то увел. ПТ, если вверх то уменьш-ся . на линиях соединяющих состояние рассмотрим стоимость этих переходов. требуется найти самый путь из S0 в S1 min ст-ти. Задача м.б. решена методом полного перебора.

Выберем все пути и найдем оптим это очень или совсем не возможно. Всего у нас 6 шагов: 3раза вправо и 3раза вверх. Рассмотрим последний 6 шаг: он м.б. сделан из состояния А­1 и А2 . Если мы находимся в состоянии А1 ,то на 6шаге идти в S1 . А1 след-но S1 это переход будет нам ст-ть 17. если мы оказались в состоянии А2 ,то сле-но Sf и ст-ть будет 14. Это для поведения на последнем шаге и ст-ть оставшегося пути – условно

оптимальное управление (УОУ). Рассмотрим 5 шаг: В1 > А1 15+17=32 В2 > А2 7+14=21 В3 > А2 8+14=22 – идем в А2 4 шаг С1 > В1 44 С2 > В2 33 С3 > В3 28 С4 > В4 31 3 шаг Д1 > С1 41 Д2 > С3 36 Д3 > С4 37 2 шаг Е1 > Д1 42 Е2 > Д2 42 1 шаг S0 >

Е1 51 Т.о.мы получим инструмент поведения для каждого шага, т.е.УОУ, кроме того получим условно min затраты на этом заключается 1 этап решения задачи от конца к его началу. Переход ко 2 этапу: > ОР – путь из S0 > Е1 > Д1 > С3 > В3 > А2 > Sf 10.ОБЩАЯ ДИНАМИЧЕСКАЯ ЗАДАЧА ЭК-ГО ПРОГР-ИЯ(ОДЗБ) И ЕЕ РЕШЕНИЯ.

Имеется система ? (завод, п/п) которая в каждый момент t находится в состояние S. Начальное состояние S0 принадлежит некоторому множеству S0 ; S0 S0 состояние S1 принадлежит Sf . Система управляемая, т.е. под влияния она с течением времени переводится из S0 в Sf . Если в системе применить уравнение U, то мы получаем выигрыш W(U). Задача заключается в поиске управления, который этот выигрыш max-ся.

При этом оптимальное управление Wmax = max W(U) U = arg maxW(U) Решение: разобьем управление на n шагов, т.е. U = ( U1… Un). Пусть wi(S, Ui)выигрыш на i-ом шаге управления,если этот шаг сделан из состояния S при управлении Ui , определена смена состояния S’ = ?i (S, Ui ), в которое переходит система из состояния S при управлении

Ui . Обозначим через Wi (S)- условно-оптимальный выигрыш (УОВ), т.е. max выигрыш, который можно получить стартуя перед i-ым шагом из состояния S . Для последнего n-ого шага : Wn(S) = max Wn (S’ Un ), где S’ = ?n (S , Un ) S1 (3) дает УОВ на последнем шаге УОУ: Un = arg maxWn ( S, Un) Рассмотрим i-ый шаг, который делается из состояния

S. Применив упр-ие U­i , получим выигрыш Wi(S, Ui) и прейдем к состоянию S’ = ?i(S , U i).Если дальнейшее упр-ие производится оптимальным образом, то мы получим дополнительно Wi+1(S’) = Wi+1(? (S; Ui)) Значит, всего мы получим, начиная с i-го шага: wi(S,U­i) + Wi+1(? (S; Ui)) Очевидно U надо выбрать так, чтобы ый выигрыш был max-ым. Wi(S) = max [Wi(S,U­i) + Wi+1(? (S; Ui))] (5)- основное ур-ие динамического прграм-ия или yр-е

Беллемана. Используя это ур-ие, мы поможем найти УОВ Wi(S), зная Wi+1(S) или УОВ на след шаге. Используя (5) можем найти Wn(S), Wn-1(S), Wn-2(S), …, W1(S). По ходу дела мы находим УОУ как точки min: Ui= arg max [Wi(S,Ui) + Wi+1(? (S; Ui))] По формуле (5) мы находим числа в кружочках, в пр-ре.

А по формуле (6) мы расставляем те сааме стрелочки. На этом заканчивается 1 этап. Рассмотрим 2 этап: У нас S0 не конкретное число, а множество. Если S0 одно, т.е. S0 =S0 , то упр-ие начинается от S0 по найденным УОУ. Если же имеется целое множество начальных состояний

S0,то надо выбрать то из них в кач-ве S0 , для которого W1(S) max . Замечание: если W(S) выражает не выигрыш, а потери, то в ур-ии (5) нужно вместо max взять min и при выборе начального состояния, где W1(S) min. 11.НЕВРЕМЕННЫЕ ШАГИ. Шагив методе динамического прогр-ия необяз-но временные, т.е. когда ур-ие проходит с течением t. шаг м.б. просто номером. Рассм-м к пр-ру единовр-ое распр-ие ресурсов.

Имеются предприятие Е1, Е2… Еn и R0- ресурсов. Если пред-ию Еi выделить х-ресурсов,то за рассм-мый период оно произведет fi(x) –доход. Причем х д.б ri , т.е. это пред-ие не может освоить > ri . Требуется так распределить R0 -рес-ов, чтобы произвести max продуктов. Упр-ем явл-ся распр-е ресурсов х1,х2 , … ,хm рес-ов х -инвестиции в i-ом пред-ии

Еi. при этом все 0? хi? ri х1 + х2 + … + хm = R0 Будем распр-ять ресурсы поочередно: сначала Е1, Е2… Еn,и выдадим ресурсы одновр-но. 1-ый шаг – опред-ие инвест-ий в первое пред-ие и т.д. Начальное состояние S0= R0 -все имеющиеся ресурсы R0 – х1 и т.д. S’ = ? (S, Ui) = ? (R, xi) = R – xi Перед i-ым шагом имеется рес-ы R выделим предприятие

R – x, т.е. Ri= R0 – x1 –x2 -…-xn-1 Условно оптимальный выигрыш (УОВ) на последнем n-ом шаге Wm(R) = fm( R ) R ? rm Fm( rm) R > rm xm = R, R ? rm rm , R > rm основным ур-ем динам-го прогр-ия Wi(R) = max [ f (xi) + Wi+1( R – xi)] – УОВ на всех шагах. 12.ДИНАМИЧЕСКОЕ ПРОГАРММИР-ИЕ С МУЛЬТИПЛИКАТИВНОЙ ЦЕЛЕВОЙ ФУНКЦИЕЙ.

Ранее целевая функция W была аддитивна (сумма), т.е. W = w1 + w2 +…+ wm Встречаются задачи и с мультипл-ой целевой функцией W = w1 * w2 *…* wm По прежнему требуется max-ть W. Во-первых, нужно прологарифм-ть (2) и перейти к новой цел-ой фун-ии W’ = ln W = ln w1 + … + ln wm = w’1 + … +w’m А можно и проще, взяв в основу ур-е динам-го прогр-ия знак

+ на знак * . Wi(S) = max [ wi(Ui ) * Wi+1 (? (S; Ui )) ] Пр-р: max-ся надежности Изделие ? состоит из элементов Е1 , Е2 … Еm , если только работают все ее элементы. След-о ндежность системы Р (вер-ть ее безотказной работы). Р = Р1 *Р2 * … * Рm ,где Рi - надежность i-го элемента

Задача. Если в изготовление элемента Еi вложить х – средств то она будет иметь надежность Рi = fi (x). Требуется распределить R0 - ресурсов между этими элеметами так чтобы надежность системы была max. Решение Wi (R) = max [ fi(xi ) * Wi+1(R – xi) ] Wm ( R) = fm( R) на последнем шаге Круг задач решаемых методом програм-ия широк. 13.ТЕОРИЯ ИГР .ЛСНОВНЫЕ ОПРЕДЕЛЕНИЯ. В эк-ке и др.областях деят-ти часто возникают конфл-ые ситуации.

Пр-ры, конкуренция на рынке, карьерные дела, азартные игры, война … . такие ситуации объединяют общим понятием - игра. Рассмотрим игры 2-х и более лиц. Игра м.б. коалиционной. Будем рассм-т только игры 2-х участников А(мы), В(противник). Игра наз-ся антагонистической, если наш выигрыш = проигрышу противника. Игра G – есть последовательность действий или ходов.

Правила игры определены, т.е. известны все возможные ходы и уровень инф-ии играков др. о др. Известен также результат игры для любой послед-ти ходов. Ходы бывают личными и случайными. Личные каждый выбирает сам а случайные происходят случайным образом. Есть игры только с личными ( шахматы), только со случайными (игры в орлянку) и смешанные игры (карты). Задача теории игр – найти оптимальную стратегию для каждого игрока.

Т.е. набор правил, руководствуясь которыми мы (они) ведем (-ут) игру наилучшим образом. Игра конечная, если каждый игрок имеет конечное число стратегий и наоборот. Основной принцип теории игр – считается что наш противник делает все возможное, чтобы нам навредить. 14.ПЛАТЕЖНАЯ МАТРИЦА. А (мы) имеем m стратегий, а именно А1,А2 ,…,Аm . В имеет n стратегий В1 ,В2 , …, Вn .

Если мы принимаем стратегию Аi , а противник Вj ,то мы выигрываем аij . при наличии случайных ходов результат игры будет случайным, тогда пусть аij будет средний выигрыш, (М- матем-ое ожидания). Из величин аij, составим платежную матрицу: Пр-р1: игра в прятки. А имеет 2места, чтобы спрятаться: М1 и М2 ,т.е. имеет 2 стратегии А1 и А2 . В ищет в одном из этих мест В1 и В2 . Если

В сразу находит, то мы ему платим 1, в противном случае - он нам платит. Составим платежную матрицу. Если мы выберем стратегию А1 и будем постоянно ее придерживаться, то В - это заметит и будет все время нас находить. То же самое будет, если мы выберем А2 и будем постоянно выбирать ее. Такие постоянные ситратегии наз-ся чистыми стратегиями, т.о. у нас нет хороших чистых стратегий.

То же самое с игроком В. Если он примет чистую стратегию В1 , то мы выберем А2 след-но у В нет чистых стратегий. Поступим по др.: будем менять стратегию регулярным образом А1 ,А2 ,А1 ,А2 ,… . Игрок В и это поймет, т.е.какая бы не была постоянная стратегия, ее можно разгадать. Видимо оптимальной стратегией явл-ся случайный выбор

А­1 и А2 (В1 и В2 ). Такие стратегии наз-ся смешанными. Пр-р2: игра в 3 пальца. А и В одновр-о показывают 1,2 или 3 пальца. Если ? на пальцах = К и К - четная, то Авыигрывает, если К – нечетное, то В – выигрывает. Составим платежную матрицу: у А 3 стратегии А1 ,А2 ,А3 . Как и в пр-ре1 хороших чистых стратегий нет.

Пр-р3: Ревизия. Пусть А – ревизор и у него есть 3 способа проведения ревизии А1 ,А2 ,А3. В – бухгалтер. У него есть 3 способа сокрытия доходов В1 ,В2 ,В3 . Eсли В применяет способ Вj , а А свой способ Аi , то пусть аij -вер-ть того, что злоупотребление будет обнаружено. Пара чистых стратегий А1 В2 явл-я устойчивой, обоим игрокам не выгодно менять стратегию.

Т.о эта игра имеет решение в чистых стратегиях. 15.ВЕРХНЯЯ И НИЖНЯЯ ЦЕНА ИГРЫ. Пр-р минимакса: рассм-м игру m*n Если мы выберем чистую стратегию Аi , то В выберет стратегию Вj с min для нас выигрышем ?i = min ?ij т.о. наш гарантированный выигрыш при страт-ии Аi есть ?i . игроая осторожно, мы выбираем ту стратегию, при кот-ом ?i max и получим гарантир-ый выигрыш.

? = max ?i = maxmin aij . Нижняя цена игры – (2). Рассм-им поведение игрока В. Он стремится min – ть наш выигрыш. ?j = max aij aij - min числа в строке ?j - max в своем столбце. Если В выиграл стратегию ?j ,то мы (А) > чем ?j выиграть не может. Наилучшым для В явл-ся выбор стратегии с min ?j ,т.е. ? = min max ?j Как ба А не играл > чем ? он выиграть не может. ? – верхняя цена игры.

Т.о. выигрыш g игрокаА всегда находится g ? Оба играют с умом. Вычислим ?i и ?j для пр-ра. Страт-ии опред-ые формулами (2) и (4) наз-ся минимаксами. В пр-ре3 нижняя и верхняя цена игры совпали (? = ? = 0,7). В этом случае = ? = ? – наз.чистой ценой и пара страт-й соотв-их чист.цене А1 ,В2 явл-я устойчивой и наиболее выгодной для обоих играков и игра имеет чистое решение. явл-я min

в своей строке и max в воем столбце. Такие точки наз-я седловыми точками, такая игра наз-я игрой с седловой точкой. Седл-ых точек м.б. и неск-ко, но все они имеют одно и тоже значение ,так что все равно какую взять (неск-ко решений). Т.о. если игра имеет седловую точку, то она имеет решение в чистых стратегиях. Теорема: любая игра с полной информацией имеет седловую точку, след-но и решение в чистых стратегиях. 16.РЕШЕНИЕ ИГР В СМЕШАННЫХ СТРАТЕГИЯХ. Расм-им игру с безусловной точкой.

Если игрок А использует свою чистую минимаксную страт-ию, то он будет иметь огромный выигрыш =-ый нижней цене игры. Возникает вопрос: а не может ли он получить выигрыш побольше? Да, если использовать подходящую смежную страт-ию SA = ( р1,р2 , … ,рn ) Т.е. он будет использовать стратегию Аi с вер-ью рi , где рi ? 0 , а р1 +…+ рm =1. точно также

В может использовать смешанную страт-ию SB = ( q1 ,q2 , … ,qn ) т.е. ?j с вер-ью qi , qi ? 0 q1 +… +qn =1. Теорема: осн-ая теорема о теории игр: любая конечная игра имеет решение, т.е. пару страт-ий игроков А и В облад-их след-ми св-ами: если один из игроков придерживается своей оптимальной страт-и, то др.игроку следует придерживаться своей оптим-ой страт-ии. Выигрыш игрока А, соответствующей этой паре оптим-ых страт-ий наз-ся чистой ценой игры.

При этом ? Пусть SA и SB -оптим-ые страт-ии, нек-ых из рi и qi м.б. нулями,т.е. нек-ые страт-ии не использ-ся. Используемые страт-ии ( с нулевыми положительными вер-ми) наз-ся активными страт-ми. Перенумеруемстрат-ии так, чтобы в начале были активные SA = (p1,p2 ,…,pk , 0,0,…,0) SB = (q1 ,q2 ,…,qk , 0,0,…,0) Теорема2: теорема об активных стратегиях: если 1 из игроков исп-ет свою оптимальную смеш-ую страт-ию,

то результат игры остается неизменным как бы др игрок не использовал свои активные стратегии. 17.УПРОЩЕНИЕ ИГР. Если стратегии Si и Sj какого-то игрока эквив-ны, то одну из них можно исключить; если Si хуже, чем Sj ,то Si надо убрать. Пр-р: стратегии А4 и А3 эквив-ны, поэтому А3 м искл-ть из игры. А2 хуже чем А1 ,значит А2 следует удалить. Из А1 и А4 нельзя определить какая хуже, поэтому их за ранее удалить

нельзя. Для игрока В: В3 хуже чем В4 . он ее удаляет. После упращения получается игра с матрицей. 18.ДВА НА ДВА – ИГРА. Рассм-им игру без Седловой точки. Найдем ее решение, т.е. SA (p1 ,p2 ) SB (q1 ,q2 ). В силу теоремы об активных стратегиях, если мы используем свою оптимальную стратегию SA (p1 ,p2 ) ,то наш выигрыш j будет неизменным как бы

В не использовал свои стра-ии. Если он использует чистую стратегию В1 ,то наш выигрыш все равно ? = но с др стороны наш выигрыш ? = а11 р1 + р2 а21 = если же В будет исп-ть чистую страт-ию В2 , то мы а12 р1 +а22 р2 = ? Кроме того р1 + р2 = 1 а11 р1 + р2 а21 = ? а12 р1 +а22 р2 = ? р1 + р2 = 1 получим ? = (a22 a11 – a12 a21) / (a11 + a22 – a12 a21) –чистая цена p1 = (a22 – a21) / (a11 + a22 – a12 a21) p2 = (a11 – a12)

/ (a11 + a22 – a12 a21) Точно так же находим оптимальную страт-ию игрока В. q1 = (a22 – a12­) / (a11 + a22 – a12 a21) q2 = (a11 – a21) / (a11 + a22 – a12 a21) Пр-р: игра в прятки. j= (1-1) / (-1-1-1-1) = 0/-4 =0 Значит в ср ни один из игроков ничего не выигрывает. p1= (-1-1) / -4= ? p2= ? q1= (-1-1) /-4 = ? q2= ? Оптим-ми страт-ми явл-ся SA ( ? ; ? ), SB ( ? ; ? ).как же играть?

А каждый раз выигрывает место с вер-ью В с вер-ью ? ищет место. Может лучше др вер-ти? Рассм-им для сравн-ия SA = ( 2/3; 1/3 ) в 2 раза чаще под кровать, игрок В заметит это и тогда будет все время нас искать, тогда с вер-ю 2/3 В будет нас выигрывать и наш выиграш будет -1 * 2/3 + 1 * 1/3 = -1/3 –это хуже чем SA =( ? ; ? ) 19.ГЕМЕТР-АЯ ИНТЕГРАЦИЯ РЕШЕНИЯ. Будем по оси абсц откладывать.

Рассм-им случай когда 2 =0 мы используем чистую страт-ию А1 . Если В использует страт-ию В1 . если р2 = 1, то мы исп-ем А2 , если В исп-ет В1 ,то наш выигрыш А2 . Рассм-им выигрыш при смешанной страт-ии при этом пусть В исп-ет В1 ( 0 < p2 <1),то выигрыш = В1 : а11 р1 +а21 р2 = а11 (1-р2 ) + а21 р2 = (а21 – а11 ) р2 +а11 . График нашего выигрыша. U1 - наш ср выигрыш, если мы используем

SA (p1 ,p2 ), а В исп-ет страт-ию В1 . U2 - наш выигрыш, если мы исп-ем В выбираем наихудшую для нас страт-ию, след-но, он выбирает В1 . Т.о В на нушу страт-ию SA (p1 ,p2 ) будем отвечать так, что наш выигрыш будет находиться на выделенной линии, эта линия наз-ся нижней границей игры. Наш, естественно, наиболее выгодной явл-ся т. N - наивысшая т. границы игры и оптим-ое значение p2 .

Из пропорции этого рисунка можно получить формулы (1), (2), т.е. найти оптим-ую страт-ию игрока А. Аналог-ую картину можно составить с т.зр.игрока В. Если q =0, то он использует страт-ию В, т. М страт-ия для игрока В. Жирная линия – верхняя граница игры и выбирают самую нижнюю точку, из этого рис м. получить формулу (3). 20.2*n –ИГРЫ И m* 2 – ИГРЫ. Рассм-им 2*n- игру без седловых точек.

При нашей стратегии SA (p1 ,p2 )мы м.построить наш ср выигрыш при всех страт0ях игрока В как делали на 2*2- игры. В будет выбирать свою стратекию, при кот-ом наш выигрыш min. В т. N пересекаются, по крайней мере 2 страт-гии игрока В: В1 и В5 . это и будет его акт.страт-ия в ответ на нашу оптим-ую страт-ию и игра превращ-ся в игру 2*2, решаем по формулам (1) – (3). В игре m*2 нужно рассм-ть игру с т.зр.игрока

В, и опять эта игра превр-ся в игру 2*2. Решение. m*n – игроки используют линейное прогр-ие. Рассм-им m*n – игру без Седловой точки. Неизв-ым явл-ся SA = ( р1 ,р2 , … ,рm ) SB = ( q1 ,q2 , … ,qn ) Ели в матрице игры есть отриц-ые эл-ты и М = min аij,то прибавляя М ко всем эл-ам матрицы мы избавляемся от отриц.эл-ов в этой матрице. Цена игры станет положительной (? > 0 ), а оптим-ая страт-ияне изменится.

Будем считать, что в нашей игре, если необходимо, то это добавка М сделана и чистая цена игры положит-а. Пусть А использует свою оптим-ую страт-тю SA ,а В исп-ет чистую страт-ию Вj ,тогда наш выигрыш будет = Uj = а1j р1 +а2j р2 + … + аmj рm . Наша страт-ия оптим-я, поэтому Uj т.е. а1j р1 +а2j р2 + … + аmj рm j = 1,2, …,n Разделим эти рав-ва на ? и введем новые переменные:

Х1 = р1 /? х2 = р2 /? … хm = рm /? получим а1j x1 +а2j x2 + … + аmj xm ? 1 j = 1,n при этом х1 +х2 +…+хm = ? мы хотим чтобы наш выигыш, т.е был как можно >, т.е растет, то первая часть (4) была бы <, т.е. W = х1 +х2 +…+хn = min Получим задачу линейного программирования,найти не отриц-ое значение переем-ых х1,…,х1 удовл-их ограничению (3) и min-щему ф-ию (5). Решим эту задачу и получим ?= 1 / (х1 +х2 +…+хm ) р = ? * хi из (2) мы найдем

SA найдем оптимальную стратегию игрока В, вводя новые переменные: у1 = q1 / … , yn = qn /? получим задачу лин-го пргр-ия: найти неотриц-ые знач-ия переем-ых у ,…, у теперь max-щую ф-ию W: W = у­1 + у2 +…+ уn = max При ограничениях аi1 у1+аi2 у2 + … + аin уn ? 1 i = 1,n решая эту задачу получаем: ?= 1 / (у­1 + у2 +…+ уn ) qj = ? у+j Пр-р: игра в 3 пальца. Есть отриц-ые числа, min из них – 5.

Прибавим 5 ко всем числам, получим Найдем оптим-ую стратегию игрока А с помощью лин-го прогр-ия, т.е. ограничителей (3) и (5): найти неотриц-ое значения переем-ых х1, х2, х3 удовл-их огранич-ям а1j х1 +а2j х2 + … + аmj хm ? 1 j = 1,n 7х1 +2х2 +9х3 ? 1 2х1 +9х2 +0х3 ? 1 9х1 +0х2 +11х3 ? 1 W = х1 + х2 +…+ х3 Применяя симплекс метод, находим решение х1 = 1/20 ; х2 = 2/20 4 х3 = 1/20 (решения

задачи) след-но ?’ = 1/ (x1 + x2 + x3) = 1/(4/20)= 5 на самом деле для исходной задачи: ? = ?’ – 5 = 0 р1 = х1 ?’ = 1/20 *5 = ? p2 = x2?’ = 2/20*5 = ? p3 = x3 ?’ = 1/20 *5 = ? SA ( ? ; ?; ? ) Аналогично можем подучить SB ( ? ; 2/4; ? ) Игроку А (как и игроку В) нужно взять 4 бумажки. На одной написать 1, на двух – 2, еще на одной – 3 (П/10; -

П/10). Взять одну полоску в клеточку Выбирая на ней произвольную точку. 21.СТАТИСТИЧЕСКИЕ РЕШЕНИЯ ИГРЫ С ПРИРОДОЙ. Основные определения. В теории игр мы предпологали, что наш противник В делает все, чтобы уменьшить наш выигрыш, возможно и др ситуация, когда мы для нашего противника безразличны. Принцип теперь такой – природа нам враждебна, но не злонамеренно.

Для выборки стратегии прим-ся теория статист-их решений. Ситуацию можно так же описать платежной матрицей. Напр-р: Теперь ? – состояние пр-ды, а не ее страт-ии. Риском А, использующем страт-ию А в условиях В наз-ся разница между его выигрышем, который он мог бы получить зная, что будет именно эти условия, и выигрышем а . очевидно, риск = max аij – аij = ?j –аij

. 22.КРИТЕРИИ, ОСНОВАННЫЕ НА ЗНАНИИ ВЕРОЯТНОСТИ СОСТОЯНИЯ. Пусть известны вер-ти qj = Р (Вj ). Это можно квалифицировать как известную смешанную стратегию игрока В SB ( q1 , q2 ,…,qn ). Тогда, если мы исп-ем страт-ию Аi , то получим ср выигрыш аi = аij q1 +ai2 q2 +…+ain qn , i = 1,2, …n. Естественно, выбирать ту страт-ию Аi ,при котором аi =max.

Если вер-ти qj не известны, то бывает возможно разложить их по убыванию. Напр-р: наиболее вер-но среднее лето, менее вер-но – сухое, более ве-но – мокрое. qj , qj ,…, qjn . составим пропорцию: n: (n-1) : (n-2) : … : 1, т.е. (n(n+1))/2 Pjk=(2(n-k+1))/(n(n+1)) если же мы не можем расположить эти вер-ти по ранжиру, то приходится считать их одинаковыми, т.е. qj = 1/n. В этих ситуациях можно рассматривать min среднего риска вместо max ср

выигрыша, результат будет тот же самый. 23.МАКСМИННЫЙ КРИТЕРИЙ ВАЛЬДА. (критерий крайнего пессимизма) Следует выбрать наилучшую страт-ию для самых плохих условий, т.е. мы думаем что нам не повезет, или случится самое плохое из того, что может случится. Если мы выберем страт-ию Аi ,то случается такие условия Вj ,что наш выигрыш будет min-ым ?i = min аij . Естественно выбрать страт-ию, при котором ? = max ?i

= max min аij 24.МИНИМАКСНЫЙ КРИТЕИЙ СЭВИДЖА Рекомендуется выбрать стратегию с min риском в самых плохих условиях, т.е. ri = max r+ij естественно выбрать страт-ию с min ri , т.е. r = min max rij 25КРИТЕРИЙ КРАЙНЕГО ОПТИМИЗМА. Всегда случается самое благоприятное. Если применить страт-ию Аi ,то ?i = max xij естественно применить страт-ию с max тогда ? = max max aij 26.КРИТЕРИЙ УМЕРЕННОГО ОПТИМИЗМА - ПЕССИМИЗМА ГУРВИЦА.

Т.з.: случится что-то среднее между наихудшим (min аij ) и наилучшим ( max аij ), т.е. при применении стратегий А наш выигрыш будет = min а + (1 - )max а , где - коэф-нт оптимизма 1 - - коэф-нт пессимизма Естественно выбрать стратегию с max , т.е. = max [ min a + (1 - )max a ]. 27.ОБЩИЕ ЗАМЕЧАНИЯ О СТАТИСТИЧЕСКИХ РЕШЕНИЯХ. Нам довольно часто приходится применять различные решения. Решение – это действия для достижения какой-то цели.

РешениеU выбирается из множества альтернатив U. решение применяется с учетом наблюдений z Z( z- множество всевозможных наблюдений). Решения принимаются в условиях s S. Условие s на данный момент обычно неизвестно. Хотя и частично об условиях S можно судить по имеющимся условиям z. Ели мы в условиях S выберем решение U, то мы понесем потери q (U, S).

Нам необходимо иметь решающее правило, позволяющее выбрать решение при имеющихся набл-ях. Нужно оптимальное решающие правил j обесп-ет миним.ср потери (min ср.риск). всевозможные методы оптимизации укладываются в эту схему. 28.ЦЕПИ МАРКОВА. Рассм-м систему которая в каждый момент времени t = 0,1,2… находится в одном из возможных состояний S1 ,S2 ,…,Sm . При этом если ? в момент времени К находится в состоянии

Si , то в следующий момент вр (К+1) она переходит в состояние Sj с вер-ью рij (эти вер-ти наз-ся переходными вер-ми за 1 шаг): Рij = рij очевидно, все рij ? 0 и рi1 + рi2 +…+ рim =1 эти вер-ти можно собрать в матрицу: Это переходная матрица цепи Маркова за 1 шаг р = р У этой матрицы элементы не отрицательны и ? элементов в каждой строке = 1. такие матрицы наз-ся стохастическими

(вер-ми). Из этого описания следует, что состояние системы в момент к+1 зависит от состояния системы в момент К. И если это состояние системы в момент вр К известно, то состояние в более ранние моменты уже никакого влияния не оказ-ет. Если известно настоящее, то прошлое на будущее уже не влияет. Если это так, то процесс наз Марковский с дискретным и дискретным состоянием.

Пр-р: пациент ( ? ) он м.б. в одном из 2-х состояний S1 – здоров, S2 – болен. Пусть переходная матрица будет: Р12 -вер-ть перейти из первого состояния во 2 за 1 шаг. Найдем переходные вер-ти Рij за n-шагов – это веет-ть того что в момент времени К, находится в состоянии Si , то через n-шагов, т.е. в момент вр

К+П она будет находится в состоянии S j с вер-ью рij . Найдем Р Значит (1) рij = Рi1 Р1j + Рi2 Р2j +…+ Рim Рmj -это формула умножений матриц, т.е. Р(2) = РР = Р2 Зная вер-ть перехода за 1 шаг, можно узнать за несколько шагов. P(n) = Pn Эта формула дает вер-ть перехода за любое кол-во шагов.

Р(2) = Р2 Р(3) = Р3 У элементов в столбцах разница все меньше и меньше, т.е. при увеличении n - строки прибавляются др к др. При n > ? строки становятся равными, т.е. Это означает, что по прошествии большого времени n вер-ти состояний систем практически не зависит от ее начального состояния в момент вр t = 0. Вер-ти q1 ,q2 ,…,qь наз-ся предельными вер-ями, состояниями системы. Найдем эти предельные вер-ти. Р(n+1) =Р(n)

Р Переходя в этом неравенстве к пределу при n> получим Р(?) =Р(?) Р. Отсюда q1 P­11 + q2 P21 + q3 P31 +…+ qm Pm1 = q1 q1 P12 + q2 P22 + q3 P33 +…+ qm Pm2 = q2 …… q1 P1m + q2 P2m + q3 P3m +…+ qm Pmm = qm получим ( РT - Е ) q = 0 q1 + q2 +…+qm =1 Из этой системы найдем предельные вер-ти.

В пр-ре: с пациентом (4) принимает вид: q1 + q2 = 1. -0,3q1 +0,2 q2 =0 0,3q1 – 0,2q2 =0 q1 + q2 = 1. 0,5q1 = 0.2 q1 =0.4 q2 =3/5 = 0.6 придельные вер-ти ( 0,4 ; 0,6 ) Т.о. независимо от начального состояния (здоров или болен) по прошествии большого вр он у нас окажется здоровым с вер-тью Р = 0,4 и больным с Р = 0,6. это означает и то, что 40% этого длительного времени здоров и 60% болен. 29.МАРКОВСКИЕ ПРОЦЕССЫ

С ДИСКРЕТНЫМ СОСТОЯНИЕМ И НЕПРЕРЫВНЫМ ВРЕМЕНЕМ. Пусть система ? в каждый момент непрерывного времени t находится в одном из состояний S1 ,S2 … Sm . Переходы из состояния в состояние происходят скачками в случайные моменты времени, т.е. Рассм-м систему с 4-мя состояниями. Введем плотности переходов ?ij = lim Где Рij ( ?t ) – вер-ть того что система перейдет из состояния Si в Sj за время ?t. Тогда при малых ?t1 Рij (?t) ~ ?ij ?t

Задача заключается в нахождении вер-ти. Рi (t) – вер-ть того, что система находится в состоянии Si в момент времени t. Найдем: Рi (t + ?t ) = Рi ( t ) P1i ( ?t ) + P2 ( t )/ P2i (?t )+…+Pm (t) Pmi (?t ) Вычтем из обоих частей этого ур-ия Рi (t) Рi (t + ?t ) – Рi ( t ) = Pi (t) P1i (?t ) +…+ Pm (t) Pmi (?t ) –

Рi ( t ) Разделим на ?t: (Рi (t + ?t ) – Рi ( t )) / ?t = ((Pk(t) P1k(?t)) / ?t) + ((P2(t) P2k(?t)) / ?t) +((Pk-1(t) Pk-1,k(?t)) / ?t) + ((Pk(t) Pk,k(?t)) / ?t) +((Pk+1(t) Pk+1,k(?t)) / ?t) +…+((Pm(t) Pmk(?t)) / ?t) Переходя к приделу при ?t > 0, получим: Рk ( t ) = ?1k P1 ( t ) + ?2k P2 ( t ) +…+ ?k-1,k

Pk-1 ( t )+ ?k+1,k Pk ( t ) +…+ ?mk Pm ( t ) – ( ?k1 +?k2 +…+?k-1 +?k+1,k +…+?km )* Pk ( t ) 1 – Pkk (?t ) – вер-ть того, что система выйдет из состояния К и в него не вернется. В более полном виде эта система будет: Р’k ( t ) = ? ?ik Pi ( t ) – Pk ( t ) ? ?k Кроме того нужно добавить условия Р1( t ) + Р2 ( t ) + …+ Рm ( t ) = 1 Р’k ( t ) = ? ?ik

Pi ( t ) – Pk ( t ) ? ?ki В системе (3) стрелочки ведущие в состояние S учитывается со знаком «+» , выходящие из S «-« . Кроме того (3) и (4) нужно задать начальные условия, т.е. начальное состояние системы. Напр-р: Р2 ( 0 ) = 1 Р1 ( 0 ) = Р3 ( 0 ) = … = Рm ( 0 ) = 0 Для пр-ра на рис-ке сис-ма ур-ий выглядит следующим образом

Р’1( t ) = ?31 P3( t ) – ?12 P1 ( t ) Р’2( t ) = ?12 P1 ( t ) + ?42 P4 ( t ) – ( ?32 + ?24 ) Р2 (t ) Р’3( t ) = ?32 P2( t ) – ( ?31+ ?34) Р0(t ) Р’4( t ) = ?24 P2( t ) + ?34 P3 ( t ) – ?42 P4 ( t ) Р1 ( t ) = P2( t ) + P3( t ) + P4( t ) = 1/ Особый интерес представляют предельные вер-ти

Qi = Pi ( ? ) если в ( 3 ) и (4) взять t > то Рi (t ) > qi и Pk (t) > 0 и мы получим для предельных вер-ей систему: ? ?ik qi – qk ? ?ki = 0 q1 + q2 +…+ qm =1 пр-р: Р’T( t ) = ? P2( t ) – ? P1( t ) Р’2 ( t ) = ? P1( t ) – ? P2 ( t ) Р1( t ) + Р2( t ) = 1 Р2( t ) = 1 – Р1( t ) Р’1( t ) = ? ( 1 – Р1( t ) ) – ? Р1( t ) – ? – ( ? + ? )

Р1( t ) Р’1 ( t ) + ( ? + ? ) Р1( t ) = ? Р1( t ) = С1 е-(?+?) + С2 Р1( 0 ) = 1 Р2( 0 ) = 0 P1= (?/(?+?)) + (?/ (?+?))e-(?+?)t P2(t) = (?/ (?+?)) - (?/ (?+?))e-(?+?)t Найдем придельные вер-ти с помощью системы (7) ? q2 q1 = 0 ? q1 q2 = 0 q1 + q2 =1 q1= ?/(?+?) q2= ?/ (?+?) 30.ПОТОК СОБЫТИЙ. Одинаковые события А, которые происходят в какие то моменты времени.

Пр-р: приходят клиенты на обслуживание, рождение детей, смерть … . След-но поток событий – этой приход клиентов. Поток м.б. регулярным,когда события происходят через одинаковые промежутки вр (бой курантов). Случайный поток (звонок на АТС ) 10) поток наз-ся стационарной, если ср кол-во ( мат.ожилание) событий за промежуток времени ?t = ? ?t незав-мо от положений интервалов ?t на числовой оси.

20) поток явл-ся поток без последствия, если наступление событий не сказывается на наступление событий в последний момент времени. 30) поток наз-ся ординарным, если вер-ть наступления 2-х и более событий за малый промежуток ?t, есть величина большего порядка малости, чем вер-ть наступления одного события, т.е. события не происходят парами, тройками … . Тем не менее неординарный поток (поток в ЗАГС) можно представить ординарным, если за событие принять пару.

Поток имеющий все 3 св-ва наз-я простейшими или Пуассоновскими. Можно показать, что если взять промежуток вр Т, то за это вр произойдет событие ? = ?Т, где ? – плотность потока ( ср кол-во событий, происх-их за ед-цу вр ) Вер-ть того, что за вр Т произойдет ровноm событий имеет распр-ие Пуассона Pm= ((am) / m! ) e-a m = 0,1,2 Пр-р: в ср за год происходит 5 аварий.

Найти вер-ть того, что за 0,5 года не будет ни одной аварии. ? = 5 аварий/год Т = ? года а = 5 * ( ? ) = 2,5 P0= (2,50 / 0! ) e-2,5 = e-2,5 время между 2-мя событиями есть величина случайная, она имеет плот-ть распр-ия вер-ти: f ( ) = ?е и функцию распространения F (U) = P ( < U) = 1 – е U мат.ожидание m = 1/? ? = 1/? Ср квадр-ое отклонение. 31.ПОТОКИ ПАЛЬМА. Это поток событий, интервалы, между которыми имеет одно и

тоже распр-ие. 32.ПОТОКИ ЭРЛАНГА. Расм-м простейший поток и будем учитывать только каждое k-ое событие, т.е. рассм-м поток с прореживанием. m = к/? Ср вр между событиями. ?(k) = к/? Ср квад-ое отклонение> Полученный поток является Пуассоновский с параметром ? = ?/к Пусть ? = ? = const, для этого исходный непрерывный поток должен иметь плотность. ? = к тогда m(k) =1, а ?(k) = к/? = к/к? = 1/ к ?

При к > ?: ?(k) > 0 след-но поток становится регулярным. Если к = 1 поток Пуас-й, если к = 2,3, … - поток все более регулярный. След-но выбирая подходящее к, мы можем получить потоки с любой степенью регулярности и случайности. 33.СИСТЕМА МАССОВОГО ОБСЛУЖИВАНИЯ (СМО). Основные определения. СМО обслуживает поток заявок СМО определяет каналы обслуживания ( напр-р, мастера в парикмахерской).

СМО м.б. детерминированными и случайными ( поток заявок случайный и случайное время обслуживания). Важн-ие харак-ки: 1) пропускная способность – ср кол-во заявок, которых система обслуживает в ед-цу вр. 2) вер-ть отказа 3)ср время ожидания в очереди 4) ср вр нахождения в СМО 5) ср 6) ср число занятых каналов 7) ср доход Основные типы СМО. 1. одноканальная 2. многоканальная 3. с отказами (если все каналы заняты, заявка уходит) 4. с ожиданием

- неограниченное вр или очередь - ограниченное вр или очередь. 5. разомкнутые (заявки приходят из вне этой СМО ) 6. замкнутые (заявки находятся в самой СМО ) 7. со взаимопомощью между каналами или без нее. 34.ОДНОКАНАЛЬНАЯ СМО С ОТКАЗАМИ. Имеется всего 1 обслуживающий канал. Приход – ая заявка обслуживается, если канал оказался свободным, и уходит если канал занят.

Пусть поток заявок Пуассоновский с плот-тью Вр обслуживания распр-но по показ-ому знаку с плот-тью ?е t это значит что, если канал будет работать без остановок, то поток обслуживаемых заявок будет т.ж. Пуассоновский с плот-тью Представим эту СМО в виде: S0 S1 S0 – канал свободен S1 – канал занят Получается Марковский процесс с дискретным состоянием и непрерывным вр.

Можно найти вер-ти: Р0 = ( ? / (?+?)) – (?/ (?+?)) е-(? + ?) t Р1 = ( ? / (?+?)) – (?/ (?+?)) е-(? + ?) t Особый интерес представляют пред-е вер-ти ( t > ? ) Р0 = ? / (?+?) Р1 = ? / (?+?) Относ-ая пропускаемая способ-ть – доля обслуж-ых заявок: q = р0 = ? / (?+?) Абсолютная пропускная способность – ср кол-во заявок, обслуженных за ед-цу вр: А = q? = ( ) / (?+?) Вер-ть отказа: Ротк = 1-q = ? / (?+?)

Не обслужено заявок за ед-цу вр: ?Ротк = ?2 / (?+?) пр-р1: в парикм-ой имеется 1 мастер. Ср вр обслуж-ия = 1.5 часа ( tобсл ) ? = 1 / tобсл = 2/3 – ср кол-во клиентов обслуж-ых за час ? = 0,8 кл/час – клиентов в час приходит q = (2/3) / ( 0,8 + 2/3 )= 0,455 Ротк = 1 – 0,455 =0,545 А = q? = 0,8 * 0,455= 0,364 кл/час В = 0,8 * Ротк = 0,436 кл/час ? = 2/3 = 0,667 кл/час 35.МНОГОКАНАЛЬНАЯ

СМО С ОТКАЗАМИ. Пусть имеется n каналов. Тогда СМО будет иметь (n+1) состояние S0 ,S1 ,…,Sn - занято 0,1 n каналов S0 : - ?р0 + ?р1 = 0 S1 : -(?+?)р1 +?р0 + 2?р1 = 0 ……… Sn-1 : -( (n-1)?)р­n-1 + ?рn-2 + n?рn = 0 Sn : -n?рn + ?рn-1 = 0 Р0 + р1 +…+рn =1 Если ввести параметр = ?/ то решением системы будет: Р = (1+( /1!)+( /2!) +…+ ( /n!) )-1 Р = ( /к!)р0 Харак-ки системы -

Ротк = Р = ( /n!)р0 - g = 1 - Ротк - А = ?q = ?(1- ( /n!)р0) - ср число занятых каналов к = А/?= q Пр-р2: n=3 = ?/? = 0,8/(2/3) = 1,2 Р0 = (1+(1,2/1!)+(1,22/2!) + (1,23/n!) )-1= 0,312 Р 1= 1,2 / 1! Р0 = 0,374 Р2 = 0,224 Р3 = 0,090 = Ротк q = 1- р3 = 0,91 А = ?q = 0,728 к = А/? = 0,728/(2/3) = 1,09 ср число занятых(из 3 работает 1 в среднем) 36.ОДНОКАНАЛЬНОЕ СМО С ОЖИДАНИЯМИ. Пусть имеется 1 канал, а в очереди m мест.

S0 – канал свободен S1– канал занят S2 – канал занят, в очереди 1 заявки S3 – канал занят в очереди 2 заявки. Sm+1 – канал занят, в очереди (m + 1 )заявки. В системе ур-ий вместо 2 3? … (пр.1) будем просто Получим решение системы: Р0=(1-p) / (1+ m+2) Рк = kР0 Харак-ти - Ротк = Рm+1= - q = 1- Ротк = - - r (ср длина очереди) = - ср время ожидания = tож = r/? -

А = ?q Пр-р3: в пр-ре 1 возьмем m= 2, =1.2 Р0 = (1-1,2)/(1-1,22+2) = 0,186 Р1 = 0,244 Р2 = 0,268 Р3 = 0,322 = Ротк q = 1- Ротк = 0,678 А = ?q = 0,542 r = 0,912 tож = 0,912/0,8 = 1,14 37.НЕОГРАНИЧЕНАЯ ОЧЕРЕДЬ. (m>?) Тогда все заявки рано или поздно будут обслужены. Но если т.е. ?1, то очередь будет неогр-о возрастать.

Пусть <1, то Р0 = 1- Рк = (1- ) q=1 А = ?q= ? r = /(1- ) tож = /(1- ) пр-р4: пусть в парикм-ой 1 мастер с ? = 1,2 tоб =1/? = 5/6=50мин; ? = 0,8 = 0,2/1,2 = 2,3 Р0 = 1- = 1- 2/3 = 1/3 q =1 А=?=0,8 r = (2/3)2 / (1- 2/3) = 4/3 tож = (2/3) / (1-2/3) = 2часа 38.МНОГОКАНАЛЬНАЯ СИСТЕМА С ОЖИДАНИЕМ. m- мест в очереди n- мастеров (каналов) S0- все каналы свободны, очереди нет S1- 1 канал занят, очереди нет …

Sn- все каналы заняты, очереди нет … Sn+m- все каналы заняты, в очереди m заявок 39.ТЕОРИЯ ГРАФОВ. Графом наз-ся пара G=(X, U), где Х = {Х1, Х2,…, Хn}- множ-во вершин графа, U = {U1,U2,…, Um}- множ-во ребер графа. Пр-р1: Ребра указывают связи между вершинами. Ребра бывают 3-х видов: 1) дуга или направ-ое ребро на графе м.б. изображено стрелой(хi>xj) 2) неориент-ое ребро (хi xj)=(

xj хi ) 3)петля (хi xj) Напр-р: вершина- населенные пункты; ребра- связывающие их дороги, тогда дуга- дорога с односторонним движением, ребро- дорога с 2-х сторонним движением, петля- въехали в одном месте, выехали в другом. Граф м.б. неоринт-ым, если в нем нет дуг. Ориент-ый граф (орграф)- если все ребра ориент-ы. Max-ое кол-во ребер между 2-я вершинами в графе наз мультическим числом ( m).

Если m?2, то это мультиграф. Напр-р: Граф можно представить матричной смежности А={ aij}, где aij – кол-во ребер ведущих из xi в xj . для пр-ра ! матрица имеет вид: Если граф неориент-ый, то А- матрица симмет-ая. Если нет петель – то на главной диагонали будут «О». Элементы aij = кол=ву путей, длины 1, ведущих из xi в xj . оказывается что Ак = {aij } – состоит из aij = кол-ву путей, длины k, ведущих из xi в xj.

Путем в графе наз послед-ь ребер. Путь наз целью, если он не проходит 2-ды не по какому ребру. Замкнутая цепь наз циклом. Цикл, проходящий по всем ребра графа наз Эймеровым, а ее граф Эймером. Граф наз Эймером если все локальные степени – вершины четные. Локальная степень вершины- кол-во контак-ых с ней ребер. 1.начать с любой вершины 2. проходя по ребру – «вычепкиваем» его 3. если есть выбор путей, то не ходить

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

40.ЗАДАЧА О РАСКРАСКЕ ГРАФОФ. Имеется геграф-ая карта, нужно ее раскрасить, чтобы соседние гос-ва не были одного цвета. Вершины - гос-ва. 2 гос-ва соеденены ребрами, если у них есть общая граница. Нужно разбить множ-во вершин, на множ-во подмнож-в. Хроматич число граф- кол-во цветов для его раскраски. Доказано, что 5 цветов, достаточно для раскраски любой карты.

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