Книга: Д.Н. Золотарёв, Н.М. Сальников, Б.П. Сердюков - Математические методы исследования операций в АСУ военного назначения

Распознанный текст из изображения:

Московский Государственный Университет им. М.В. Ломоносова

Конспект лекций по курсу

Москва 1999г.

Распознанный текст из изображения:

Исследование операций как наука

Формат 60х90/8,

гарнитура «Таймс», усл. печ. листов — 25,

тираж — 400 экз.

подписано в печать 29.04.1999

ООО «Народное Творчество»

в сотрудничестве с

ТБНТ 1.1С.

«Математические методы исследования операций в АСУ военного назначения»,

Москва, 1999 год, Военная Кафедра ПВО, цикл 25.

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

Золотарев Д.Й., Сальников Н.М., Сердюков Б.Й.

Данныгг лгсггггерггал ысчгользуется пргг чтенгги лекгггггг на военной кафедре ПВО АЯ Х гглг..Л!. В. Л!омоносовсг гго курсу «Матемсгпгггческие мепгоды исследования оггерагггггг в АСУ военного назначения» для студенпгов механико-мапгемапгического и экономы ческого фсгкул ьтепгов.

Мсггггерггалы могут быть полезны для самостоятельной работы спгуденпгов нры ггодгоггговке к зачетам ы экзаменам.

Тема 1. История развития и использования методов исследования

операций, их классификация

Занятие 1. История применения методов исследования операций и

их классификация

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

— Отражение воздушного удара средствами ПВО,

— Разведывательный поиск группы самолетов в тылу противника,

— Боевые действия армий двух воюющих государств и т.д.

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

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

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

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

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

Выполнение третьего этапа — поиск экстремума некоторого функционала при заданных ограничениях — может потребовать, помимо применения специальных математических методов; использования ЭВМ.

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

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

Распознанный текст из изображения:

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

В период Второй Мировой войны методы исследования операций' нашли применение в практике использования радарных установок для противовоздушной обороны, в разработке планов бомбардировок наземных объектов для нанесения максимального ущерба неприятелю, в выборе оптимального размера каравана судов для уменьшения опасности их торпедирования до минимума и т.п. В 1942 году командованию бомбардировочной авиации США, дислоцированной в Англии, было придано несколько специалистов по исследованию операций. В результате их работы в течении двух лет число снарядов, разорвавшихся ближе 300 м от цели, возросло с 15',4 в 1942г. до 60',4 в 1944г. от общего количества сбрасываемых во время воздушного налета бомб.

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

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

Методика проведения исследования операций

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

Требования, предъявляемые к моделям в исследовании операций, в общих чертах такие же, как и в других науках. Модель операции должна быть максимально проста и приближена к действительности равно настолько, чтобы сохранить главные черты натуры и те существенные факторы, влияние которых на данную операцию изучается. Например, предположим, что рассматривается стрельба отдельными управляемыми снарядами по воздушной цели. Требуется изучить, какое влияние оказывают на вероятность поражения цели способ наведения. снаряда и вес отдельных осколков. При теоретическом .исследовании данной операции модель явления будет определяться дифференциальными уравнениями, описывающими движение управляемого снаряда при вьюранном способе наведения и заданном закон движения цели. Кроме того, должны быть определены также класс помех, исключающих измеряемые значения координат цели и снаряда, зависимость координатного закона поражения данной цели (т.е, вероятности поражения цели при условии, что снаряд разорвался в некоторой определенной точке пространства) от веса осколков .и обший вес осколков. При внесении в модель других факторов, таких, например, как надежность обслуживающих систему технических устройств„плохие метеорологических условия, вероятность обнаружения цели, применение противником различных искусственных помех, состояние .. и моральный дух личного состава и т.п., будем усложнять модель и только, затушевывать влияние основных изучаемых факторов вероятности поражения цели.

Явления, изучаемые наукой об исследовании операций в военном деле, как правило, носят случайный характер. Например, выстрел может быть успешным или неуспешным, отказы в техническом устройстве могут произойти или не произойти по случайным причинам. Для того чтобы операцию можно было оценивать при случайных условиях, эта операция, а, следовательно, и ее модель, должны, по крайней мере в принципе, обладать свойством повторяемости. При вероятной трактовке модели какой-либо операции мы всегда имеем дело с множеством различных реализаций.

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

Построение рациональной модели операции существенно зависит от правильного выбора показателя эффективности. Насколько сильно влияние правильного выбора показателя эффективности на результат оценки операции показывает следующий пример:

Во время второй мировой войны на английских и американских судах устанавливались зенитные орудия для отражения ударов немецкой авиации. Однако число сбитых самолетов было незначительно — около 4'/о, а расходы на установку и обслуживание орудий велики. В связи с этим стали предлагать снять зенитные установки с транспортов. Перед тем как принять это решение, было проведено математическое исследование данной операции. Выяснилось, что к правильному выводу можно придти лишь после выбора критерия, отвечающего главной задаче — сохранению максимального числа судов. Исходя из этого, в качестве показателя эффективности был взят не процент сбитых самолетов, а потери в транспортах. Оказалось, что эти потери, благодаря снижению точности бомбометания самолетов под огнем зенитных по сравнению с бомбардировкой невооруженных судов, уменьшаются с 25'.4 до 15;4„то есть почти в 2 раза. Тем самым однозначно была доказана полная целесообразность оснащения транспортов зенитными орудиями.

Роль исследования операций в военном деле

Основными направлениями применения исследования операций в современных условиях

являются:

1) Оценка боевой эффективности средств поражения, которая может обеспечить:

а) обоснованный выбор тактико-технических характеристик боевых. средств;

б) выбор наиболее эффективных способов боевого применения оружия.

Оснащение вооруженных сил дорогостоящим оружием приводит к необходимости

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

использования.

2) Военно-экономическая оценка эффективности систем оружия и связанные 'с этим задачи выбора оптимального варианта развития вооружения и научно обоснованного планирования в области военного строительства.

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

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

Научное планирование развитие вооружения неотделимо от комплексного подхода к.

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

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

Высокая поражающая мощность современного оружия, автоматизация технических средств

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

Таким образом, роль исследования операций в военном деле, на современном этапе

исключительно велика. Дальнейший прогресс в области военного дела в настоящее время тесно связан с развитием и использованием методов исследования операций.

Распознанный текст из изображения:

М[Х]

Оценка точности метода

тзз М

х'= ~ — ', Р' , ) Ж ,ж) М

Пример 2. Вычисление числа л'.

Х

0

Действительно, пусть У = фх) — монотонная функция, тогда (при ах, ауу — + 0 ):

Р1х < Х < х+ сй) = Р(у < У < у+ ау] =~ /"(х)сй = ~(у)ау, где ~(х) = Р'(х),

М[У] = М[а[х)] = 1уу[у)Ыу = 1Б[х)Дх)сЕт .

МО сВ а[Х) непрерывно и М[н[Х)] = 1Х[х)дх)зЬт. Оценкой М[Х] является среднее

арифметическое реализации СВ Х, так как по теореме Чебышева '=' сходится по вероятности к

Ж

Дадим теперь два определения непрерывной СВ Х, распределенной равномерно в [а, Ь].

~ ~ .н, Р1Х е [а',Ь']1= ~/[а',Ь'] с:[а,Ь]. Ь' — а'

Ь вЂ” а

О е Непрерывная СВ Х называется равномерно распределенной в [а,Ь], если

1

хе[а,Ь]; /(х) = Ь вЂ” а

О, ха[а,Ь]. Докажем их эквивалентность:

Ь' — а' Р(Ь') — Р(а') 1 1 ==> 2: Р(а' < Х < Ь') = Р(Ь') — Р(а') =

Ь вЂ” а Ь' — а' Ь вЂ” а 2 ==> 1: Возьмем произвольный отрезок [а', Ь'] с: [а, Ь], тогда ь

ЬР

Р[Х а [а',Ь'] = ] Ах =

Площадь области а): !!а!! =ю/4. Введем понятие равномерно распределенной двумерной случайной величины (Х, У) . ' м.о

!! !! распределенной в области Й, если вероятность того, что (Х,У) ~ й равна — '[/в с: й.

!! !! Применительно к квадрату (1 х 1) на плоскости (Х, У) Р~ (х, у) е в] = ~г /4 . Проведем серию из У испытаний со СВ (Х,У). Испытание, успешно, если х,.'+у,.' <1 (О <х, <1, 0< у,. <1), и

Е

пусть 1, — число успешных испытаний. Тогда оценкой вероятности Р~(х,у) Е й)~ является —,

Ж

4Х

причем — — — + х [по теореме Бернулли).

у з'зс-воз

Пример 3. Вычисление определенных интегралов.

Ь

.т' = 1д[х)Ах. я[х), естественно, считается интетрируемой.

.з'=[Ь вЂ” а)]' Ш=[Ь вЂ” а)М[й[Х)]м[Ь вЂ” а) — А и[к).

д(х) ' 1

„Ь вЂ” а Ж,ж[

где х, — реализация СВ Х, которая равномерно распределена на отрезке-[а, Ь]. То есть необходимо

провести Ж испытаний над случайной величиной Х, равномерно распределенной в [а,Ь] и

1

вычислить значение статистики — ~ [ (х.) .

У ,ж)

Занятие 2в Оценка точности метода статистических

испытаний

В рассмотренных примерах требовалось найти либо МО случайной величины Х, либо

вероятность Р осуществления некоторого события У; х и Р— детерминированные величины. В

МСИ определяются оценки этих величин:

где х, — независимые реализации случайной величины Х в,Ф испытаниях, ~,. — независимые реализации случайной величины У в Ж испытаниях, причем РЯ = 1~ = Р, Р~У = 0~ =1 — Р. Сами оценки х, Р являются значениями СВ: х, Р

Пусть а — истинное значение оцениваемого параметра СВ А, а а = ~ — ' — его оценка,

;, Ф

причем а есть реализация СВ А . Требуется оп еделить число реализаций Ж, чтобы с заданной

точностью е и доверительной вероятностью [х Р а — А < е = а .

Проведем Й независимых серий испытаний со СВ А по Ж независимых испытаний в

каждой серии. Получим следующую таблицу:

Здесь А„А2,...,Аь, — независимые СВ, принимающие значения столбца таблицы, причем

Ф все А'=А — '. Все А,. распределены по тому же закону, что и СВ А. В соответствии с

,, Ж

центральной предельной теоремой теории вероятности можно утверждать, что СВ А распределена

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

Распознанный текст из изображения:

.Гг

й = ~/2Ыи

1 е "сз'и=Ф вЂ” '

= — ~~) М[А,]=М[А]=

м

М[А*] =

~2 2

==> У> ". (3)

2

а, = — чз х,. — ( — 2 х,.)~.

произведении, равен 0

тогда

а = (:г„, 'о = х

(х — )з)

2а

~(х) = е

/2ка

х (и-)з)

е " (Ь

2ха

Х вЂ” х

Следовательно, Х = сг,У+ х, У =

О„

Запишем следующее выражение:

10

Если случайные величины А],А„...,А), независимы, одинаково. распределены и имеют

конечные М и В, то А А,. при достаточно больших ЛГ асимптотически нормальна.

Считаем, что случайная величина Х имеет по условию математическое ожидание х и дисперсию сг2, а случайная величина У вЂ” М[У] = 1. Р+ О. (1 — р) = Р, сг„= М[(У вЂ” Р) ]=(1 — Р) Р+(Π— Р) (1 — Р) = Р(1 — Р), то есть конечны. Попутно заметим, что в обоих случаях й = М[А]. Вычислим

ЦА'] = М((А' — М(А'])'] =М 2 — ' — 2 ' =.—,М 2,(А, — М(А,.)))

"А,. М[А]

,ж, Ж ,ж, У У '

2 гз( (г 2

'з — М ") (А М[А])2+") (А М[А])(А — М[А ]) = — "~ о--', = — ",тоесть сг . = — ';

Зж) )и/ зм) М((А, — М(А])(А,. — М(А,])~= 0 при з и)' вследствие независимости Сй А,. и А,.

./ плотность вероятности ~(й,, а, ) = ~, (й, )~, (а, ) . Тогда

+со доз

М((А, — М(А, ])(А,. — М(А, ])~ = 1 1(а, — М(а, ])(а, — М(а,. ])г', (а,)Р);(а,)с(аз(а, =

ч- з +со

= 1(а, — М(а,])Я(а,)с)а, 1(а,. — М(аз])зз(а,)г(а,.:

-о

-аз

г ( ) (з — М(А] ) Е (а )с(а = (, то каждый из интегРалов, столшик

А' — М[А']

Рассмотрим случайную величину и докажем, что она распределена по

О

параметрами (0,1). Пусть случайная величина Х имеет плотность

1

У

а случайная величина У вЂ” ~(у) = е - '. Предположим, что

~~22г

нормальному закону с

(х х)2

~(х) = е

2лсгх

Х=аУ+Ь,где а>0,

х-)з

х — Ь " 1

Г(х) = Р(Х < х1= Р У < = — е ' аи = ч = йи+ Ь аи =—

а „~/2к

а

Р <е, =а (2) или )е зад=а. А'-М(А]

(АА 2аа „ В силу четности подынтегральной функции имеем:

Возрастающая функция Ф(х) подробно затабулирована. Таким образом, по заданной

доверительной вероятности а находим 1 . Из выражений (1) и (2) приходим к следующей

2

формулировке нашей задачи: определить количество реализаций, чтобы 1 О .< е или, после

А

2

возведения в квадрат и подстановки выражения для О „.:

'ГА

<Я

Ж

Последнее выражение отвечает и нашим интуитивным представлениям (Ж ) при б Е, Т (Х, Т с~„).

Вернемся теперь к исходным случайным величинам Х и У:

а) А = Х . Значение сгх неизвестно. На практике, чтобы воспользоваться неравенством (3), поступают следующим образом: над СВ Х проводят Ж испытаний, получают выборку из генеральной совокупности Ж: х,,...,х, и вычисляют эмпирическую дисперсию СВ Х:

Эта оценка получается из равенства:

М((Х вЂ” х) ~= М(х — 2хХ -ь Х'~ = М(Х'] — 2хМ(Х]-ь х' = М(Х'] — (М(Х]) .

Неравенство (3) в этом случае приобретает вид: Я > " . (4)

е

2

б) А=У. о =Р(1 — Р), где Р также неизвестно. В качестве эмпирической частоты (оценки

Г2

вероятности Р при 2"(' испытаниях) выбирают Р = —, где и — частота интересующего нас

Ж

г2 Р( р2)] 1 — Р()211

события. В этом случае имеем: Я > ' " ' ". (5)

е

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

Занятие 3. Моделирование случайных величин

Способы формирования равномерно распределенных случайных

величин

Пусть случайная величина Х равномерно распределена в [О,Ц, тогда

1, хе[ОЦ ~(х) =

О, хю[О,Ц

Распознанный текст из изображения:

1. Мо и и и ованный метр Неймана.

1) Выбирают два числа:

х 1

хйс =—

2, 2

х/ = (гх, 1)(гпос]2'), /

гх/, на 2 , где г — некоторое

2 1--,'

Р(а,. = 01 = Р(а, = 1~ = —, О < ~~ < ~~,„

1

2

Х;

— т=1, Т=б 10'.

2"

1 1 1

М[а/] = 0 — +1. — = —;

2 2 2

.0[а/] = М а,. — — = Π— — — — 1 ——

Тогда

/с ]

М[Д=~г-'М[п,1=- )- — „:

2 2"

1 — )й ] ]

ст[Д= ~4 '/УЫ1=

16 1- —,' 12

случайной величины Х,

х

распределенной по закону о'[х) = /у Яй .

1

~(х) = — (а <х < 6);

о — а

х

г 1 х — а

4 = ~ — а/~ = —, откуда

„6 †6 вЂ

х/ =(о — а).~,",. +а

/ (х) = Яе (х > 0) .

х

г) чл = ]яе "г/у = 1 — е , откуда

1

х = — — 1п(1 — ~ )

/с

1

или х = — — ]п~,' .

й /,.

12

13

Интегральный закон распределения случайной величины Х есть:

О, х< О

х, 0 < х < 1; ее математическое ожидание - М[Х] = 1, х>1

з'

1 1 1 1 1

дисперсия - 0[Х] = х — — сй = — х — — = —; -стх =

2 3 2 12 ' 2~/3

Х ' — непрерывная случайная величина В ЭВМ непрерывную СВ представить нельзя Если

"Й" — разрядность ЭВМ, то в пределах интервала [О,Ц можно разместить только 2" различных

/

чисел вида че = 2 г 'а,, тле а„...,аз — независимые случайные числа: а,. = Ом 1,

М[~] М[Х] 1,/2 //)[ц ~ ~)[Х] = 1/'12 . Такие числа называются квазиравномерно распределенными в [О,Ц. Случайные числа вырабатываются на ЭВМ программным . способом, с помощью какого-либо рекуррентного соотношения Х„„, = / (Хйч /„,..., Х„, ); / называют порядком последовательности. Получаемая при этом последовательность чисел, не являясь случайной, может удовлетворять различным статистическим критериям случайностей. Такие числа называют псевдослучайными. Случайные числа с любым законом распределения можно получить из случайных чисел, равномерно распределенных в [О,Ц (об этом будет сказано ниже), поэтому остановимся на способах получения псевдослучайных чисел с равномерным распределением в [О,Ц. Последовательность равномерно распределенных псевдослучайных чисел ~~~1, ~,"г,..., ~~/, в общем случае имеет структуру:

где ~,"„[,"2,...,~,"/ — различные числа, А — длина отрезка апериодичности, Т = Х вЂ” /+1 длина периода, то есть числа ~,. в пределах периода обладают статистическими свойствами случайных чисел, равномерно распределенными в [О,Ц.

а=а[2 +а,2 +...+а„2 ,В =Д2 '+/0,2 '+" +Рг/,2 '"

и находят произведение а ф = у, 2 + у, 2 +... + у4 2

2) Берут коэффициенты средней части у „,...,у,„ и строят первое число

последовательности ~~~1 = у„„ 2 ' +у ,, 2 + ... + у 2

3) Находят произведение 2-х последних чисел /// ~~1, выбирают коэффициенты средней

части и строят число ~г, далее ~,"1 ~," — средняя часть — + ~~ и так далее. Здесь порядок

последовательности т = 2. Длина периода Т = 10

6

л/~

х,. < 2 целое число, то есть х,. — целочисленный остаток от деления число, /г — разрядность ЭВМ.

Формирование последовательности случайных чисел,

распределенных по заданному закону

Требуется получить последовательность реализаций

Метр об атных нк ий.

Наидем распределение случайной величины К = Р (Х) . По определению функции распределения имеем: Г(у) = Р(У < у] = Р[Г(Х) < Р(х)1, вследствие монотонности функции распределения Р(Р(Х) < Г(х)1 = Р1Х < х1 = Р'(х) — у, причем 0 < у < 1. Таким образом, случаиная величина ]' распределена равномерно в [О,Ц и значения х/ случайной величины Х находятся как корни уравнения Р(х,.) = ~,, то есть х. = Г (".) где ~ — последовательность равномерно распределенных в [О,Ц случайных чисел, если /. (х) имеет обратную функцию.

Примеры.

Распознанный текст из изображения:

и'

1у (х)Ых

Критерий согласия г - Пирсона

2)

Х.

х

2

или, что то же самое, т

ир,

д' = ~С,.( — ' — Р,.~, с, =—

!

Справедлива следующая

15

14

Когда аналитически задачу решить не удается; используют приближенные методы

моделирования непрерывных случайных величин.

Мето Неймана.

1) Если область определения случайной величины Х неограниченна, то переходим к

и -~-о:

дх)сух < Л вЂ” усеченному распределению, так чтобы 1дх)с(х < Л н

3) Выберем пару чисел (,", и 7~,. из равномерно распределенных в [0,1] последовательностей © и ®. Вычислим х,. = (Ь вЂ” а)(~,. + а и у,. = Л„у7('. Теперь пара чисел (х,,у,) определяет реализацию )и,. случайной точки М в прямоугольнике [а,Ь|х [0,~„~. В качестве чисел с заданной плотностью /(х) будем принимать те числа х,, для которых у, < Дх,.), то есть абсциссы тех точек и,, которые лежат под кривой ~(х) . Если условие не выполняется, то данная пара (х„у,.) отбрасывается. Найдем

и

1 у(х)сух

Р1М ~Й~ = — вероятность того, что очередная реализация

(Ь-а) ~„(Ь-а)

случайной величины Х будет отобрана.

Р)(М е й)~ = " (*) — вероятность того, что отобранные значения случайной

~„,.(Ь-а)

величины Х будут лежать внутри (а',Ь') . Возьмем отношение количества чисел, которые отобраны

и лежат в (а, Ь )з к общему количеству отобранных чисел

Р~(М е ж~

= ~~(х)~Й, а это доказывает, что случайная величина Х распределена по

Р1М е й~

заданному закону ~(х) или (М е в~ = (М е й~ [х е (а', Ь')1 . События в правой части

независимы, так как независимы ~ и ~, поэтому Ру(М е ж~ = Р~(М е й~ Р~(х (= (а, Ь )1, отсюда

из (') следует Р(х и (а', (з )) = 1 ~(х)ссх, что и требовалось доказать.

и'

Имеется выборка объема и случайной величины Х: (х,,...,х„~. Принимается гипотеза о законе распределения случайной величины Х, то есть принимается, что ~(х) — плотность вероятности случайной величины Х . Чтобы проверить выборку [х),..., х„)~ на согласие с гипотезой о законе распределения поступим следующим образом:

разделим область определения Х на г непересекающихся интервалов Л ... Л и

) > з з

вычислим Р, = ')у (ку<Ъ, з'=!,р .

Пусть и,. — количество чисел из набора [х„...,х„)~, попавших в Л,. Тогда и,./и — частоты попадания в интервал Л, . Таким образом, имеем ряд вероятностей Р,,..., Р„, вычисленный на основе гипотезы и ряд частот и,/и,..., и,/и — данные опыта. Если гипотеза о законе распределения верна, то значения Р,. и и,./и будут близки и тогда опытные данные не противоречат гипотезе, то есть находятся в согласии с ней. В качестве меры близости К.Пирсон предложил величину

Распознанный текст из изображения:

2. Ситуация А А, - пропуск цели,

':А - амплитуда сигнала,

ю - несущая частота,

Х ~т)

А = А„Х е й, (х) А = А„Х е й,(х)

и Л1

18

Наилучшим из решений ~ будет такое, которое обеспечивает минимум среднего риска. Чтобы получить конкретный алгоритм. обработки, необходимо задать в явном виде г' (Я, ~), знать в(Я, Х) или Р(Я, Х) и применить к выражениям (1) и (2) операцию определения минимума.

Получение выражения для принятия решения (вычисления) у и будут оптимальными алгоритмами обработки, представленными в математической форме. Оптимальными они являются потому, что учитывают статистику случайных событий в законах в(5',Х) или Р($,Х) и отражают интересы принимающего решения, заключенные в Е(5, Х). Такой подход к построению решающих правил применим в любых системах, где есть необходимость принятия решения в условиях неопределенности.

Постановка задачи обнаружения радиолокациойных сигналов

Так как наряду с полезными сигналами на входе радиолокационного приемника постоянно

действуют различного рода помехи (шумы), то входной сигнал можно представить в

'видеХ(А,~) = Я(А,~)Э п(~), где 'Я(А, 1) = А . яп(Оф+ щ, ) - полезный сигнал, '

~Р - начальная фаза сигнала,

П(1) - колебания помехи,

Э - знак композиции сигнала и шума.

Пусть А принимает только одно из двух возможных значений:

А =. О - сигнал отсутствует и А, ~ О, (А, = 1) - есть полезный сигнал.

Известны априорные вероятности появления сигнала ~ и его отсутствия,р (уэ + ~ = 1) ' т.е. Р(А ) = р, Р(А, ) = д .

Известна априорная плотность распределения помехи Р(п). Известен вид функции Я(А, 1) и характер композиции сигнала и шума.

Пусть за время наблюдения О < 1 < Т получена выборка наблюдаемого сигнала

Х(г) = (х„х„..., х„~.

По полученной выборке необходимо принять решение о наличии или отсутствии в ней полезного сигнала. С геометрической точки зрения каждая выборка Х(1) = 1х„х2,..., х„'1 представляется вектором, конец которого занимает вполне определенное (в зависимости от выборки) положение в области определения случайной величины Х(1).

Правила принятия решений..

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

В общем виде это можно записать так:

Способы оптимального разбиения области й(Х)на две подобласти йо(Х) и й,(Х) будут рассмотрены ниже.

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

Общий подход к формированию критериев.

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

1. Ситуация А, .А - ложная тревога,

Ф

3. Ситуация А, А, - правильное обнаружение,

Ф

4. Ситуация А А - правильное не обнаружение,

Где А и А, - условия отсутствия и наличия сигнала соответственно, а то же со

звездочкой соответствующее решение. Вероятности возникновения этих ситуаций имеют внд:

Р, =Р1А, А,)=Р1А,) Р1А,'(А,)=р а

Р„= Р(А, А,)=Р(А,) Р(А,'~А,)= д ф

Р, =Р(А, А,)=Р(А) Р(А;/А,)=д(1 —,В)=д,В'

Р„= Р1А, А,)= Р1А,) Р1А;1А,)= р11-а)= р а'

Здесь,1э и ~ - априорные вероятности отсутствия и наличия сигнала соответственно.

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

М~С~ = = С,ргх+ С,д~

Величина г в общем случае зависит от сигнала Х и принятого решения у . Поэтому величина +, Х) называется средним риском или функцией риска. Очевидно, что чем меньше величина среднего риска, тем лучше система обнаружения. Поэтому стремятся достичь минимума среднего риска. Критерий, обеспечивающий это условие, называется критерием минимума среднего риска или критерием Байеса.

Метод последовательного анализа

В классическом случае процесс наблюдения разбивается на ряд последовательных

интервалов малой длительности

Распознанный текст из изображения:

Наблюдается реализация принимаемого сигнала Х(!) длительностью и. Л1. На основе этой реализации для любого правила принятия решения вычисляется отношение правдоподобия л(х)='(' ='

~(~) Р(х, н,)

и сравнивается с порогом Ь. Если Л(Х) > Ь, то принимается решение А = А,, если Л(Х)< Ь, то А = А . Решение принимается только в конце интервала наблюдения. При последовательном же обнаружении интервал заранее не фиксируется; поэтому к концу интервала и с!! возможно не два, а три различных ответа: 1. "Сигнал есть" - А = А, 2. "Сигнала нет" - А = Ао Решение (1) !',2) вынести с достаточной уверенностью невозможно. Необходимо продолжить наблюдение. Поэтому при последовательном обнаружении устанавливается не один, а два порога А и В (А > В).

Решение о наличии или отсутствии сигнала принимается после каждого интервала Л1 с учетом ранее полученной информации. Это означает, что по прошествии первого интервала наблюдения Л1: Если окажется, что Л(Х,) > А, то А = А, "сигнал есть" если Л(Х,)< В,то А = А = О "сигнала нет" если окажется, что В < Л(Х, ) < А, то решение не выносится и наблюдение продолжается. Здесь Х! = х!. По прошествии двух интервалов наблюдения, имеется выборочное значение х! и Х2, т.е. выборка Х~ = 1х!,х . Снова вычисляется отношение правдоподобия Л(Х2 ) и снова проводится сравнение с двумя порогами.

Процесс наблюдения и принятия решения продолжается до тех пор, пока на какой-то ступени Й отношение правдоподобия Л(х!,) Х~ — — 1х„...,х не окажется больше чем А или меньше, чем В и будет принято соответствующее решение. Таким образом, при последовательном анализе пространство принимаемых сигналов Й(х) разбивается на три соприкасающиеся области Йо(х) ~2!(Х) ~22(х) !',см. рис. 1).

Если при каком-то значении Й вектор

Х~ попадает в области й!(Х) или й2(х), а (х)

то принимается соответственно решение ! ~

"сигнал есть" или "сигнала нет". Если же а,(х) вектор 1 соответствует промежуточной области Й (Х)„то решение не принимается и 2 наблюдение продолжается. Разбиение пространства й(х) на области й (Х) ,Й!(Х) и й (Х) может быть произведено Рис. 1 Пространство принимаемых многими сиособами, так что основная проблема

с игналов в теории последовательного анализа заключается в оптимальном, с точки зрения некоторого критерия, разбиения Й(х). Согласно принципу последовательного анализа необходимо сформировать отношение правдоподобия и сравнивать его с порогами А и В. Удобно проводить преобразование не с самим отношением правдоподобия, а с некоторой монотонной функцией от отношения правдоподобия, допустим, с логарифмом отношения правдоподобия. Л = 1пЛ(Х)= 1п -- ',тогда

Р(Х/А,)

= Р(Х(~)

— (,/А,) —, Р( Л,'А,) Р(х, ~)' ' Р(х,х„~)'

Р(х! з х„...з х„; А, ) 7„=1п- - '-' " '- '-"', '- 12)

Р(х!з х2 р", х„/Ао)

В случае если х„хз,..., х„независимые одинаково распределенные выборочные значения, тс Р(х„хз,...,х„/А) = Р!х1~А) Р(х /А) ... Р[!х„(А) Тогда г„- случайная величина, являющаяся суммой независимых одинаково

— Р(х, /А, ) распределенных случайных величин 7„ = ~~~ Л,, где и,. = !П вЂ” '

Теперь процесс принятия решения при последовательности анализе можно пояснить следующим рисунком !рис.2).

Т На рисунке У, = г,, У, = г, + г,, г„= ~, + ~, + ... + ~„ Ь! =1пА, Ь2 =1пВ.

П теперь Й,(Х)= Х: ~л; >й,

!=! аЛХ)= Х:~л, <й, /=1

П за, !х) = х: !з, > 2 и,. > !т,

р=!

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

Очевидно, в рассматриваемой ситуации величины г! - номер интервала, когда закончится наблюдение и Т = и Л~ длительность процедуры являются случайными.

Как в классических процедурах, в процедуре последовательного анализа возможны ошибочные решения двух видов — ложные тревоги и пропуски сигнала, с вероятностями Р, и Рз или а и,В . Очевидно разбиение пространства принимаемых сигналов Й(х) при последовательном анализе на области й (Х),'й!(Х) и й (Х) должно быть наилучшим с точки зрения критерия, учитывающего вероятность ошибок, их стоимость, длительность наблюдений и потери, обусловленные временем наблюдения: Я =с, а р+с,,В д+с,.Т Т = Р(Н,). Т, + Р(Н!) Т, Здесь, как и ранее:

20

21

Распознанный текст из изображения:

Х!, ей

Р ~Х„г= й! / А, ~ Р~!Х,е й! /Ао~ или Р~Х,е й! /А, ~> А Р~Х„е й! /А,

Усеченный последовательный анализ.

Решение

А=А,

Гипотеза

Р~Х„я Й! /А!~=1—

Но

Ао

Рис. 3 Определение порога

Р(Х, а, /Н,

г

23

22

р Р(Н ) и д — Р(Н ) априорные вероятности отсутствия гя ' наличия сигнала

(вероятности гипотез Но и Н, ), где

То - среднее время наблюдения, при условии, что сигнала нет;

Т, - среднее время наблюдения, при условии, что сигнал есть;

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

Очевидно, чем меньше Р, тем лучше обнаружитель. Рассмотрим множество всех решающих правил, у которых одинаковые ошибки первого и второго рода. Поскольку при последовательном анализе мы минимизируем функцию Р = с, а р+ с,,В. ч+ с., Т, то

наше решающее правило минимизирует и Т . Следовательно, правило последовательного анализа

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

правилами.

Определение порогов А и В.

Величины порогов А и В очевидно связаны с заданными вероятностями а и ф. Определим возможные значения порогов А и В, снова рассматривая пример обнаружения сигнала (А, =1,А =О). Пусть после Й испытаний выбрана гипотеза Н,. Это означает, что

о

Х~ такая последовательность результатов испытаний, которая приводит к принятию

гипотезы Н, (см. рис. 3).

Она принимается, когда верна гипотеза Н, с вероятностью Р~Х„е й! / А, ~ = 1 —,В, а

также, когдавернагипотеза Но с вероятностью Р~Х е Й! /А ~= а.

1 — В

Следовательно Л(Х ) = — > А.

а

Таким же образом можно показать, что для всех Х„е Й

Р~Х„а, /Н!~

Р~Х„е й, /Но~1

вероятность выбрать гипотезу Но когда верна. Н!, а Р~Х~ е й2 / Но - вероятность

выбрать Но, когда она верна, т.е. не выбрать гипотезу Н,, когда верна Но.Они равны ф и

1 — а соответственно. Отсюда В > . Мы получили верхнюю границу для верхнего порога

В

1 — а

А и нижнюю границу для нижнего порога В .

Вычисление точных значений А и В довольно сложно. В работах ф)/а показано, что А = (1 — ~В)/а и В =,В /(1 — а) равенства достаточно близки к точным значениям А и В для заданных а и ~В, и практически не увеличивают времени принятия решения. 1 — а) Теперь сформулируем основное утверждение последовательного анализа

Х каковы бы ни были вероятности ошибок а и !В, потери с„с,с и априорные вероятности Р(Н-) и Р(Н,), никакой способ наблюдения не дает меньших значений средних длительностей наблюдений Т ''.и Т,, чем наблюдение, основанное на последовательном анализе. При этом пороги А и В должны определяться по формулам А = (1 — ф)/а, В = !В/(1 — а) (эти формулы верны при а и ~В < 0,5).Последовательное обнаружение, определенное таким образом называется оптимальным последовательным обнаружением.

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

Заранее устанавливается максимальное время Т„=. и Л1, по истечении которого

анализ должен закончиться. Пока длительность наблюдений не превышает Т„, последовательное

наблюдение проводится по етгпеням обычным, обршом: о = ~я, - логарифм отношения

!ю1

правдоподобия сравнивается с двумя порогами 1п А и 1п В . На ступени и' устанавливается

всего один порог С . Если до шага и' не произойдет пересечения порогов 1п А > У . > 1п В, то

П

на и' шаге при У . < 1пС принимается гипотеза Н, а при У . > 1пС - гипотеза Н .

Пороги А = (1 — !В) / а, В = ~В /(1 — а) обеспечивающие в не усеченном анализе

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

вероятностям ошибок. Действительно, если имеет место гипотеза Но может случиться, что ~?„на

и' шаге окажется больше 1пС(Л„> 1пС) и будет принята гипотеза Н,, в то время как

продолжение наблюдения по последовательному анализу привело бы к У . < 1й В и ошибки бы

ы .ргб

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

последовательной процедуре удовлетворяет неравенству:

а' < гт(п')= а т Р!о, < !пг. г'Н,;

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

Распознанный текст из изображения:

,0' <,0(п') =,0 к- Р(о . > 1п С ! Н,

А = А,,л(х) > "'

у(Х) =

А = А„Л(Х)<

( .) 1пС вЂ” и' Ё(ао)

~)л .Й У(а,)

!пС вЂ” д' д(а,)

'п .О У(а1)

$

и! =и!

дА(Х„..., Х„.'а„..., а„).

да„

в(Х) = ехр — (Х вЂ” а„)

,.2к 2

а ее логарифм

(», — а,).

2 (Х,. — а,) = О, откуда

и,=и,

24

25

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

з'

воспользоваться нормальной аппроксимацией (следующими формулами)

Занятие 2. Элементы общей теории статистических

решений

Правило максимальной апостериорной вероятности

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

Р(АО) = р и наличия Р(А,) = д полезного сигнала, а также условные плотности вероятностей Р(Х~А ) и Р(х/А1). Последние, после проведения эксперимента (вектор Х стал известен) становятся функцией только аргумента А. Поэтому, при условных вероятностях Р(Х,,'АО) и Р(Х~А1), когда опыт произведен, 'введены специальные обозначения АУ.(А), которая получила название функции правдоподобия.

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

Р(А) Р(Х,'А)

)Р(А) Р(Х,'А)0а(А) п(А)

Р(А) Р(Х,~А)

~ Р(А). Р(ХУА)

Р(А,) = р,Р(А,) = д,Р(Х, А,) = г(А,)

Если учесть, что сигнала необходимо вычислить

Р(А,) Р(Х(А,) дг(А,)

Р(А,) Р(Х~А,)+ Р(~) Р(Х~~) дК(А,)+ рК(~) Р(А (Х) = --- — — — — -- — — и сравнить их между собой. Если Р(А, /Х) > Р(Ао,~Х),

Р~(~)

рХ(А,)+ дХ(А1) то А = А,, т.е. сигнал есть. Если Р(А, ~х) < Р(А /Х), то А = А, т.е. сигнала нет. Другими

Р(А, (х) дь(А,) г(А,) словами нужно найти отношение — — — -' — -- — = — — ' . Обозначим ' = Л(Х) и назовем

М )- Р.() .(;)

его отношением правдоподобия. Следовательно правило принятия решения будет иметь вид

Принцип максимального правдоподобия

Наиболее правдоподобно то значение параметра А, для которого функция правдоподобия АУ.(А) принимает максимальное значение. Этот принцип принимается как постулат.

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

Применение этого принципа не требует знания априорной вероятности Р(А), что является его достоинством. Для оценки параметра А необходимо знать только функцию правдоподобия Е(А)= А(а1,а2,...,ап), максимум которой необходимо найти. Математически это означает решить систему уравнений:

дХ,(Х„..., Х„. а„..., а„)'

да,

д'г д'Л

При условии, что < О,..., < О

да' . да,',

и,=и!

о о о

тогда а,,а,...,а„, полученные из решения этой системы, есть оценки по методу

максимума правдоподобия для параметров а„а,..., а

Если опыты по измерению Х независимы, то метод максимального правдоподобия есть метод наименьших квадратов.

Например, требуется найти оценку максимального правдоподобия параметра а,, случайной величины Х, распределенной по нормальному закону с параметрами а, и о„= 1.

Пусть в результате эксперимента получены "и" независимых значений Х,, Х,,..., Х„

Функция правдоподобия выборки равна:

и ЦХ„Х„...,Х„,'а„) = охр — 2 (Х, — а„)

2л 21,

!по(Х„Х„...,Х„:а,) = 1п — ~~к(Х, — а,)

2 2д 2;,

Оценка параметра производится из решения уравнения правдоподобия

Распознанный текст из изображения:

а,= ~Х,

и,,

А =зА,', ' = Л(Х))1

Л(А,)

г(А,') =

А=А,, ' =Л(Х)<1

г(А,)

= 'Л(А,)=

Ошибки первого и второго рода.

а (х)

~о (Х

Решающее правило может быть записано так:

А=4,Х~Хо А=А„Х Х,

2б

Таким образом, оценкой максимального правдоподобия для их является среднее арифметическое по ансамблю наблюдений.

В случае принятия решения по методу максимального правдоподобия в задаче обнаружения, необходимо найти значение функции правдоподобия для случая наличия и отсУтствиЯ сигнала Е(А,) и АУ.'(Ао). Решающее пРавило имеет вид:

Мы ввели понятие функции правдоподобия Л(А), под которым понимаем условную

плотность вероятностей Р(Х А) распределения выборки Х при условии отсутствия или

наличия сигнала. Как подтверждено многочисленными исследованиями, плотность вероятностей

Р(Х А ) и Р(Х А,) имеют нормальное распределение с параметрами:

М[Х1 = О - для случая отсутствия полезного сигнала,

М[Х1 = Х вЂ” если полезный сигнал имеется,

2

О[х] = сг — для обоих случаев.

На рисунке показаны плотности вероятности случайной величины Х при условиях

отсутствйя сигнала А = А = О и его наличия А = А~ = 1.

где Хо - некоторый порог принятия решения или точка разбиения области определения

случайной величины Х на две подобласти Й (Х), где принимаются решения об отсутствии

сигнала и Й (Х) - о его наличии.

Как видно из рисунка, графики Р(Х. А ) и Р(Х: А,) пересекаются, что может приводить к

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

площадям под кривыми Р(Х,'А, ) и Р(Х. А, ). При отсутствии полезного сигнала, когда

А = Ао = О случайная величина Х может оказаться больше порога Хо, в результате чего будет

принято ошибочное решение о наличии полезного сигнала, Вероятность такого события равна

а = ) Р(х 'А )сй' и называется ошибкой первого рода.. В математической статистике а называется

Х(,

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

может возникнуть ситуация, когда полезный сигнал есть, т.е. А = А,, а будет принято решение о его

Хи

отсутствии. Вероятность такого события равна 22 = )Р(Х((А()гуХ. Величина (б называется

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

1 — Р' называется мощностью правила выбора решения. Из соотношений для а и ф и рисунка

видно, что невозможно выбором порога Хо одновременно минимизировать и а и Р .

Оптимальное решение должно обеспечить минимизацию лишь той или иной комбинации

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

правильного не обнаружения Я .

УУ' = (Р(Хг. А,)~Х; а' = ч(Р(Х. А,);

Очевидны соотношения: ф +)У = 1, (.'б'+ сб' = 1.

Критерий минимума среднего риска (Критерий Байеса)

Выбор решающей функции Байеса состоит в минимизации среднего риска. Подставим для

в выражение для среднего риска значения ошибок 1 и 2 рода.

зз Хи

г(у, х) = С р /Р(Х(Ае)((Х -> Сз(( ) Р(х А()((х ((( т к.

и

кк -оз

)Р(Х'Ае)с(х )Р(Х~А()схХ' )Р(Х'Ае)(УХ 1 )Р(х!А )(Ух

и

то равенство (1) перепишем в виде:

хп Хо

г(у, х) = С, р — С, р ) Р(Х А, )аХ ч Ср,(2 ) Р(Х А()пХ (2(

— (о -со

Дифференцируя (2) по Х, получим уравнение для нахождения оптимальной точки

ХохоруразбиенияобластивозможныхзначенийслучайнойвеличиныХ,надве

соприкасающиеся области, обеспечивающей минимизацию +, Х) .

С р Р(Х Ао)+ С д ' Р(Х. А ) = О

о

с,д Р(х А,),, = с р Р(х А,),,

Р(Х:А) С р

Р(Х А ) С,д

Величина Ь называется порогом принятия решения.

Распознанный текст из изображения:

дГ

— = — 2

да,

~> Х,. — ~а,1,.'

с=!

уравнений относительно а,

сп д

()

у~+~

(!)

у~+~

~~с;."'а, = ~с,.'Хй„,г = 0,1,...,лт

)жО С=!

Выбираем систему координат 1 = 0(1 < Й < ю),тогда 1,. =(1 — 7с)Ж, 1=1,...,ю Ж =сопк1;

са .с л

~~ (с — гс)' слс а,. = ~~~ (с — тс) Х, или е матричной форме Д Та = )сХ 11), где

х1 2

х

, ~=0,1,...,п — я.

образом

ат2

(ат)

б+~

Рэд

1+.с+1

э! э2

У у" +л+!

с=!

1жО =!

~л(1- й)са

1=!

,"и" (г — й)""'

~л(1-й)

1ж!

0

1 0

.0 Ле

,Т=

0

0

0 0

(1 — ге )

г=!

~л(1 — 1г)

1=1

Х1

а,

Х,

а,

, а=

а„,

В результате решений линейной системы уравнений (1), задаваясь конкретными ю, Й, и, Л1, Х,,

можно получить параметры а, (1'=0,1,...,и), которые могут быть использованы для нахождения

значений сглаживающей функции и производной сглаживающей функции в момент времени Г„.

са

у„= р(Г„) = Уа,1",.

гиа

Атаккак ~ =О,то

у(') = р(О)=а,

у(') = р(')(0)=11а,, 1=1,2,...,и

Тогда у = Ф а, где

(о)

у(!)

О! О 0 0

0 1! 0 0 . 0 0 и!

к У=

Используя выражение (1), получим у = РХ, где Р = ФТ 'Я ''К

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

~глежиееюшей функиии уй,.„= ла,,(),,с) = су(к),.„) = ~(л — )с.>1) (ЛС)та,.

1О

или у „„, = д 7а, где а = (1, (л — Ж ч- 1),..., (л — )с -с- 1)',..., (л — с! + 1) )

Используя выражение(1) получим:у, = Р, Х, где Р, = уД 'Я = 1Р„,1=1,2,...,ю

35

34

1

1 †2 — й

(1 — ~)' (г — ~)'

(1-~)"' (г-~)

= О, г = 0,1,..., и, т.е. получаем систему линейных

Представление общей схемы алгоритма обработки результатов

измерений

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

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

о

Рог Ро

Рш — Ро,. - коэффициенты для сглаживания,

Р,, (1 = 1,..., л; у' = 1,.-.„и) -' коэффициенты для дифференцирования,

Є— Рэд - коэффициенты для экстраполяции результатов измерений

Если )х „.„— у „.„~ ) Лх, то значение измерений х -„.„заменяется

экстраполированным у~„.„.

Данная схема алгоритма находит широкое применение в АСУ ПВО. Например, если под

Х„Х„...,Х„подразумевать измеренные значения дальности до цели, а под у„у,,...,у„

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

характеристики цели:

(о)

у, - сглаженную дальность до цели,

(!) !' (!) !

У, ~0~, ! - скорость движения цели,

у~,„ф' ~ ! - ускорение цели, т.е. указывает на маневр цели по скорости и т.д.

Распознанный текст из изображения:

М12 н 2...2 Приравняв 112 нулю, получим ф2ф = или ф2ф = . В новых осях

11 22 О1 ~2 г = 0 и ~ (~1, ~2 ) = ~1 (~1 ) ~2 (~2 )'ж где

(~,-Д М)=,

!

Это означает, что случайные величины Е1 и Б независимы между собой. Для нормального закона из некоррелируемости следует независимость. Для других законов, в общем случае, это не так.

, Приведенные выше рассуждения справедливы в основном и для трехмерного случая. Отметим только некоторые особенности, В этом. случае, с выбором главных осей:зсвязано понятие картинной плоскости. точку встречи снаряда с целью перпендикулярно к вектору их относительной скорости. Оказывается, что главные оси рассеивания 1,"1, ~ лежат: в картинной плоскости и их направления определяются, как было получено выше, а направление оси ~," совпадает с направлением вектора средней относительной скорости снаряда. Круговое вероятное отклонение, главный эллипс рассеивания, правило Зо

1 Рааамотрим соотношение Р1Х вЂ” х) < Е ) = — для случайной величины Х, распределенной

2 по нормальному закону Ж(х,о'„), Ех называется круговым вероятным отклонением случайной величины Х.

2

х+Е, хд хи Р1Х вЂ” х <Е,)= / е ' ' г2х= )е ' ' г2хь =

/2л' сг„,— е . ~Г2л»т„, —; зать = Г2гу,гзз = ) е ' гуз = Ф * —.фуллння лапласа

1 Корень уравнения Ф (Р) = — равен р = 0,477, тогда 2

Е„ Ех = Р~Г2о„= 0,674~т„сг, =

Р,Г2 Л главных осях рассеивания 1»,,» ), 7 1»,» ) через Е, = Е и Е '= Е запишется в

9из 992

2

Р у:2 Г2 виде: 7 ф и з ) = е ' ' . Линиями уровня дифференииаяьного распределения

тс Е,Е, являются эллипсы. Действительно, из ~ф Д ) = С, ==> — + — = С (*), где С1 и Сг 41 42

1 2 произвольные постоянные.

~ гь называются эллипсами рассеивания.

г 2 Эллипс + =1 (**), принадлежащий семейству (*), называется главным

4о1 аког

(4Е,) (4Е,) эллипсом рассеивания.

Длина осей главного эллипса рассеивания составляет восемь круговых вероятных отклонений

по каждому из направлений ~1, ~ .

Подсчитаем вероятность того, что траектория ЗУР пересечет картинную плоскость внутри

главного эллипса рассеивания:

Р11м,,щ,)и 27) = Це " " сз»,Ы»,, где 77 — область, лежащая внутри л ЕЕ,„

Е,

кривой (**). Произведем замену переменных д, = —,,",, = ~,, = — 'у, (2 =1,2); при этом кривая

(**) преобразуется ' ' + ' " =1 ==> 2~ +2~ =16Р— окружность радиуса 4Р с

(4Е,) Р' (4Е2) Р'

центром в начале координат (ц1,д ).

Перейдем к полярным координатам:

д1 =~ СОЗЕ

; 0<я <22г; 0<~ <4р.

Ггг =~ ЯШ

Исходные переменные выразятся через (1, Е) следующим образом:

~1 = ~1 + — '~ СОЫ,

Р

,", =,", +=~созе.

Р

Якобиан преобразования:

Е

— 'созе — — '~яп к

Р Р

Е, . Е,

=яп я — '~созе

Р Р

Теперь имеем:

СОБ2 с+ 1 2 251П2 Ь' =

Р Р Р

Р8Е„Ез)е 22)= — )ззе )Зе ' злу = — — — е ' =1 — е '" = 098.

1 р, 22г 1

2

Понятие главного эллипса рассеивания широко используется при обосновании правил

стрельбы ЗУР. В пространственном случае имеем главный эллипсоид рассеивания:

~~:»)',~» -» ),~» 2)'.,

(4Е1 ) (4Е ) (4Ез)

ЗОх 3

Найдем вероятность Р1Х вЂ” х~ < Згт ) = Ф * = Ф 0997.

Д х Л

Сформулируем правило 3-х о: вероятность того, что случайная величина Х, распределенная по нормальному закону, примет значение, отстоящее от математического ожидания не более чем на Зо,, равна 0,997 независимо от параметров нормального закона.

Занятие 2в Особенности закона рассеивания снарядов

Закон рассеивания для дистанционных снарядов с неконтактными

взрывателями

Закон рассеивания снарядов при одиночных выстрелах зависит от вида снарядов и типов взрывателей. Различают снаряды дистанционные и ударные. Ударные снаряды могут поражать цели только при непосредственном попадании в нее. Дистанционные снаряды поражают цель как при прямом попадании в нее, так и при разрыве на некотором расстоянии от цели.

40

41

Распознанный текст из изображения:

г='1

45

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

меньше размеров области рассеивания снарядов (1 <( о „, г„ст. — СКО координат точки разрыва снаряда относительно главных осей рассеивания) или области их поражаюшего действия.

Показатели эффективности операции, содержание которой составляет стрельба по одиночной малоразмерной цели, является вероятность И' поражения цели. В обшем случае величина И' определяется формулой:

= 1" 16„(а„...,а.)Р(а„...,а„)АО, .~6„,

где Я вЂ” совокупность координат (х,, у,, ~! );

! !'!а)Аа = 1 ! ! Р !л;, у,, в,)2 Аунг;,

~(Я,...,Д„) — закон рассеивания при и стрельбах,

б„(Я,..., Д„) — координатный закон поражения цели.

6Щ„...,Д„)=Р(А/Ц,...,Д„), тле А обозначае~ событие: идель поражена", те.

координатный закон поражения есть вероятность поражения цели при условии, что 1 -тый снаряд

разорвался в точке с координатами Я, г = 1,..., п .

Координатному закону поражения можно придать различную форму в зависимости от типа

снарядов !'дистанционные и ударные) и'характера стрельбы !'с накоплением и без накопления ущерба).

Накоплением ущерба называется явление, состоящее в том, что цель может быть поражена

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

поразил бы.

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

один цель сразу поражается, при попадании в другие вообще не поражается, т.е. 'поражение цели

осуществляется одним удачно попавшим снарядом. В отсутствие накопления ушерба выстрелы в

смысле поражения цели независимы, поэтому модель олерации, построенная в предположении, что

накопления ущерба нет, будет существенно проще для исследования, чем модель с накоплением

ущерба.

Найдем выражение для б„(Я,..., Д„), когда накопление ущерба отсутствует. Тогда при

г-ом выстреле Р 1А Я ! = 6, (Я). Вероятность не поразить цель Р)А Д,.) = 1 — 6, (Я).

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

б!(Д) — характеристика уязвимости цели, определяется либо экспериментально, либо с

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

представить в виде ступенчатой функции.

Для ударных снарядов: б„(Я,, Д„) = б (ш), когда Я,..., Я е Ц, где 7!,..., ~„, — различны, б (ю) — вероятность поражения цели при условии, что в цель попало и

снарядов; Ц вЂ” область пространства, занятая целью. б(т) называют законом поражения !'в отличие

от координатного закона поражения).

Очевидные свойства б (т):

б(0) = 0;

б( +1)>б(т);

б(т) -+ 1.

др — + со

Покажем на.примере, как вычисляется б(т), когда имеет место накопление ущерба. Пусть

цель состоит из трех агрегатов, проекции у которых на картинную плоскость имеют площади Я,, Я,

Я,. Площадь цели 5, +5 +Я,. Вследствие малых размеров цели по сравнению с размерами

области рассеивания снарядов замена закона рассеивания ~(х,у) в картинной плоскости в пределах

размеров цели на константу не приведет к большой погрешности. Следовательно, вероятность

попадания снаряда в область (Я,.) при условии, что он попал в цель, пропорциональнаЯ,, т.е.

5'!

Р 16, ~ В) = — ' = !;. (! = 1, 2, 3), где через 6,. обозначено событие: "снаряд попал в (Я ) ", а через

В: "снаряд попал в область (5) ".

Пусть цель поражается, когда хотя бы один снаряд попал в (Я,), 2 снаряда — в (5' ), 3

снаряда — в (5' ). Тогда при попадании одного снаряда в цель вероятность поражения б (1) сводится

к вероятности попадания в (Я!):

3

б(1) = ~;, б(2) = ~! + ~:; +2~!/ +2~; /з, действительно, поражению цели двумя

снарядами благоприятны следующие исходы:

оба снаряда попали в (Я,) или (Я ),

Снаряд 1 — (5',) и Снаряд 2 — (5 ), или Снаряд ! — (5,) и Снаряд 2 — (5',), или

Снаряд! (Я,) и Снаряд2 (Я ), или Снаряд ! - (Яз) и Снаряд2- (Я ).

2

б (3) = 1 — 3 ~ ~;, здесь имеем следующие благоприятные исходы:

Снаряд ! — (Я ) и Снаряд 2 — (Я,) и Снаряд 3 — (5',), или Снаряд 1 — (Я,) и

Снаряд2- (5',) и СнарядЗ вЂ” (Яз), или Снаряд ! (Я,) и Снаряд2- (5 ) и СнарядЗ- (Я,).

б (4) = 1 и т.д.

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

поражения принимает вид:

д!

6(т) =1 — П!! — 6,(Д,.))=1 — (! — и)"', где д = 6, (Д,) — вероятность поражения цели

!=!

одним попавшим в нее снарядом. б(т) в таком виде называют показательным законом поражения

цели.

Возможные упрощения формулы определения вероятности

поражения цели

Рассмотрим возможные упрощения формулы для И". При этом будем предполагать, что координатные оси х, у, ~ приблизительно параллельны главным осям рассеивания для каждого выстрела, а зависимость выстрелов, если она есть, сводится к схеме двух групп ошибок. Для обзора всех возможных случаев составим таблицу:

Распознанный текст из изображения:

Дистанционные

Ударные

Снаряды

без накопления

'ущерба

без накопления

ущерба

Стрельба

с накоплением

ущерба

с накоплением

ущерба

Выстрелы

незав.

зав.

зав.

незав.

незав.

зав.

незав.

зав.

Взрыватели

№ случая

д н

д н д н 3 4 5 б

д н

1 2

7 8

1О

12

Первые две строки таблицы определяют вид координатного закона поражения, а следующие

две — закона рассеивания.

Случаи 1 и 2.

Для дистанционных снарядов без накопления ущерба:

6„(Ц,...,~„) =1 — П(! — 6,(Д,г)1;

из независимости стрельб:

П

Р(Я,...,д„) = П у,. ф,), тогда

1=!

рр= )'™ 1'1-П(1-6,(а)1 ПСХ(а)уи .~а,

г=!

=' — П ((1-6 (Ы)1ХЬ,)уЮ =! — П 1 — 16,(0!)Х(Ы)ДЮ

Зм! Ре!

— са

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

! (.,—.;) (К,-У,) (=,-=,)

-+

2

з

х(а)=

(2х)гз сг„сг„сг

Для неконтактных: о (х,,у,.), Г,(х,,у,.).

Случаи 3 и 4,

Зафиксируем групповые ошибки. Тогда рассеивание в группе будет только индивидуальное и

случайные величины Х,. = Х,. +Х+(у',, К. = у, +у+ )у,. и А', = Г,. +г+ рр',. станут независимы.

Поэтому условная вероятность поражения цели при фиксированных групповых ошибках может быть

вычислена как для независимых стрельб:

а

оо

т (х,у, г) = 1 — П 1 — 16> ф; )!, (гА, ~ х, у, г)с!Я, где для дистаниионных взрывателей:

рм!

1 (х,— х,.— х) (у,— у,— у) (г,.— г,— г)

(2ю)'~ „, с 2,, 2,', 2

для неконтактных о„, (х,,у,), Г,.(х,, у!). Зная функцию О(х,у,~) и закон группового

рассеивания

ф(х,уз2)= 3

1

(2х)гзах а'г ах

рК = ) ()т(х,у,г)ф(х,у,г)ахсгус!г.

Сл чаи5 б 7и8.

При накоплении ущерба многомерный интеграл в общем случае. не распадается на произведение интегралов меньшей кратности. Поэтому в этих случаях практически единственный инструмент — метод Монте-Карло.

г~РН) г

Пусть требуется вычислить 1 = ~ ~ф(х,,...,хры)сй ...ах

где ф(х,,..., х„,) — непрерывна в ограниченной замкнутой области Я, при этом а! < х, < Ь,. (~ = 1,...,т). Интеграл преобразуется так, чтобы новая область интегрирования сг была расположена внутри единичного т -мерного куба. Произведя замену переменных х, = (Ь, — а,.)~,. + а„О < б,", <1,

Гф( Ю" ".,Ы.,)1 Ы., 4~=П(б,—,)

преобразуем интеграл:

~1Л" ""»1Л1 „ф("('"" 1"

1'' т

Пусть в т-мерный единичный куб случайно и равномерно бросается точка г',(б,,...,б„,),

тогда Х = /!. Р (у и а 1 М (ф (о)), где ф (о) = ф (х (б' ),..., х,„(й",„)1. если в п случаях из Ж

а

1

а

~очка А, и а, то ! = ~ г' = †. — ~ф (2,. ) или ! = — П (Ь, — и )~ф (2, ).

Ж И,м! У,

Случай 9.

Имеем частный случай формулы для И' из случаев 1, 2.

РР = ! — П(! — р;к) ле

р,. — вероятность попадания ~ -го снаряда в цель;

~ — вероятность поражения цели при условии попадания, т.е. ~ = б (1).

Сл чаи 1О, 11 12.

зз

й обигем случае формула ыя р!г переходит в формулу Колмогорова: Рг' = ~6 (т) р,„„,

т=!

где рры „— вероятность того, что т снарядов из и попало в цель. В 1О и 12 случаях РРА „ищут

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

аналитическое решение.

Если А,. — и ~ -тый снаряд попал в цель", а А, — противоположное событие, то

р „= Р А, ...А А„„, ...А„+...+А, ...А„тА„„„, ...А„=

= l все слагаемые — несовместные события ! =

= Р А, ...Ат А„„, ...А„+...+ Р А, ...А„А„,,;.А„.

Пусть выстрелы независимы, т.е. события А,,..., А„независимы и

Р(А,)= р,.; Р(А,)=1-р,. = ст,, тогда

Ргзг,гз = Р! "РазЧаз+! "Чгг+" +Ч! "Чгз-азрзз-а,+!" Р.

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

46

47

Распознанный текст из изображения:

Р ~1 х(Ь|) > 1 ~ = 0(Л~) .

Простейший поток событий

то

1 ° ф< 1~ ) э~=-и -л~~ ~ )

~=о

случайными моментами их появления ~„..., ~„...

55

54

Тема 7. Методы оценки эффективности боевых

действий войск с использованием теории

массового обслуживания

Занятие 1. Основные понятия теории массового

обслуживания

Классификация систем МО и их основные элементы

Многие задачи оценки эффективности боевых действий войск и деятельности

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

специальной ветви теории вероятностей - теории массового обслуживания.

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

известными следующие характеристики:

1. Входящий поток требований или заявок на обслуживание. Первопричину этих

требований называют источником.

2. Должна быть определена обслуживающая система, состоящая в общем случае из

накопителя и узла обслуживания. Узел обслуживания представляет собой одно или

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

одновременно может обслуживать только одну заявку. Заявка, поступив на вход СМО,

может найти все приборы занятыми. Если при этом заявка не входит в систему, то СМО

называется системой с отказами. Если заявка поступает в накопитель, где становится в

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

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

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

5. Должно быть определено, является ли СМО разомкнутой или замкнутой. СМО— разомкнута, если число заявок можно считать неограниченным. В противном случае СМΠ— замкнута.

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

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

Обозначим через х(Л) случайное число событий происходящих в течение интервала

времени Л . Поток событий задан, если известен закон распределения случайной величины (СВ)

х(Л) при любом фиксированном Л, т.е.

Р ( х(Л) = /с ~, Й = 0,1,... Рассмотрим поток событий, удовлетворяющий следующим свойствам: ~ ---( '=0-*,.„„. * 1-

Р (х(Л~) >1 ~= ЛЛ~+ 0(Л~), где Л не зависит от Л1, а 0(Л1)- бесконечно малая более высокого порядка малости по сравнению с Л1, причем

2. Ста иона ность — закон распределения СВ х(Л) не зависит от расположения интервала Л на оси 1, а зависит только от величины Л. В частности для ординарного потока отсюда следует, что Я = сопИ, т.е. не зависит от времени 1 и наоборот, если у ординарного потока Л не зависит от 1, то поток стационарный. 3. Отс тствие после ействия — пусть Л„...,Л - непересекающиеся интервалы, тогда

отсутствие последействия означает независимость СВ х(Л~),..., х(Л ).

Поток событий ~ 1„~, удовлетворяющий свойствам 1-3, называется простейшим. Покажем, что простейший поток является стационарным пуассоновским. Разобьем заданный интервал времени (О, ~) на П равных непересекающихся интервалов Л,,..., Л», где

Л, = —, (Й =1,п)

и

и представим общее число событий за время 1 в виде суммы независимых СВ:

и

х(1) = „> х(Л,)

1=1

Найдем производящую функцию СВ х(1):

Р(.(Л,) =1~= Л вЂ” ',

п тогда производящая функция СВ х(Л ) есть

1 ф„<„>(г) =1 — Л вЂ” +Л вЂ” г+О—

и п и В силу независимости СВ х(Ь ), производящая функция СВ х(1) равна произведению

ф„(Л,),(й =1,п) т.е. ф~,",~(г) = 1+1 — (г — 1)+Π—, так как ф~",~ (~) — + ф„<,1(г), при п — + со,

и, согласно определению производящей функции:

„, (Л)"

Р ( х(~) = /~ ~ = е,1к = 0,1,...) — распределение Пуассона с параметром Я~.

Распознанный текст из изображения:

Найдем математическое ожидание и дисперсию СВ х(1):

М[ ()1=~ "'( ) = "В~(

= И-!)'

М [х(~)1

— среднее число событий за единицу времени называется плотностью

2

пуассоновского потока событий..0~х(1)1= а, — а, где а,. — ~-ый начальный момент СВ

х(~) для ~ =1,2:

а, = М[х(~)1=Л,

~~~~~~2 -й (Ж) д~%~~~~ — ь ('~~) ~~ ~(~ !) -ь ( ) ~~)~~ -Аг ( )

И вЂ” !)' = И вЂ” !)' ~= И вЂ” !)'

=,1,г(Л -1);

.. В[х(~)~= Л.

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

Найдем закон распределения длины промежутка Т между соседними событиями в простейшем потоке. Интегральный закон распределения СВ Т есть

НЯ = Р ~1Т < ~ ~ = 1 — Р ( Т > ~ ~ = 1 — Р ( х(~) > 0.~ = 1 — е ', (~ > О) — показательный закон распределения и Ь(~) = Яе, (~ > О) — плотность вероятности.

Найдем

сй. 1 г, и=г;аЪ=е 'айаг

,Й = — = — ~ге 'с~г =

~о Ыи=а~г;т =е '

м~т~= !ха Й = т = Ас

о

1

'Иг

Л'

— ге',+ е

о

2

Л-'

и=г;сЬ=

е 'Нг !

= — — г'е ' "„+ 2р 'сй. =е '

Ыи = 2Ыг;~

2 1 1

й[Т1 = — „— — = —,

Л" 12 Л2

М [х(т)] 1

м [т|

Показательное распределение обладает следуюшим важным свойством: если СВ Т

распределена по показательному закону и в рассматриваемый момент времениТ > г, т.е. на

промежутке длины г' не появилось ни одного события потока, то СВ (Т вЂ” г) также распределена

по показательному закону. Условный закон распределения СВ (Т вЂ” г) при условии Т > г есть

Р~Т-т <.~г~т > г~ Р~т < Т <~+г~

Н,Я = Р~1Т вЂ” т<~ / Т> г ~=

Н(1+ т) — Н(г) — е '"'+ е ' -л.

1- Н(г) е ~'

Получили чтоН,Я = Н(г) и не зависит от г. Покажем теперь, что если длина

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

закону, то поток событий простейший. Пусть Л1 — малый интервал, тогда

Р ~1 х(Л|) > ! ~ = Р ~1 Т < Л~ ~ = ! — е ~' = ЛЛ~ + о(Л1) .

Отсюда следует:

1. Поток ординарный, так как вероятность того, что за промежуток Л1 произойдет одно событие намного больше вероятности одновременного осуществления нескольких событий и Р~Х(Л~) =1 ~= ЯЛ1' и Р~Х(Л~) >1 ~= О(Л~).

2. Поток стационарный, так как Я = еойБ| и, следовательно, вероятности появления событий не зависят от 1.

3. Поток без последействия, т.е. СВ х(Л,),х(Л,),... независимы, если Л,,Л,... не

пересекаются.

Покажем, что х(Л,) и х(Л,) — независимые СВ С точностью до членов более высокого

порядка малости Т < Л, + Л,

Р(х(Л,) =1! х(Л,) =О~=Р(Т-Л, <Л, ~ т>Л ~=Р~Т<Л,~=1-е "- =ЛЛ, =

= Р1х(Л,) = !

Три оставшиеся условные вероятности рассматриваются аналогично. Вместо Л, и Л,

можно взять любые другие интервалы, таким образом все х(Л„) независимы.

Время обслуживании

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

Р!Т„,, <~~=! — е "', где~>0 и р=

= м[т„„~

Если прибор бесперебойно снабжается заявками, то выходной поток обслуженных заявок будет простейшим потоком с плотностью,и. Рассмотрим пример, когда закон распределения Т„д можно считать показательным. Одиночная малоразмерная цель обстреливается потоком независимых выстрелов со скорострельностью Л. Вероятность поражения при одном выстреле р. Чтобы не учитывать точно момент каждого выстрела, предположим, что они происходят в случайные моменты времени 1 и образуют простейший поток с плотностью Я . Выделим из этого потока поток успешных выстрелов. Так как исходный поток простейший, а каждый выстрел может стать успешным с вероятностью о, то успешные выстрелы тоже образуют простейший поток с плотностью Л = Лр. Действительно, обозначим через х(1) — количество выстрелов, а за у(1) — количество успешных выстрелов за время 1, тогда из ординарности входящего потока

Р [х(Л1) = 1 ~ = ЛЛ1+ о(Л1) следует

Р ~1 у(Л1) = 1 ~ = АрЮ + о(Л~)

— вероятность одного успешного выстрела за время ЛГ равна вероятности того, что за время Л1 произойдет один выстрел, умноженной на вероятность того, что он будет успешным, Р ~ у(Л~) > 1 ~ = О(Л~), т.к. Р ~ Х(Л~) > 1 ~ = О(Л~), поэтому выходящий поток будет ординарным с плотностью Л = Яр . Стационарность следует из того, что Л не зависит от ~ и ординарности входящего потока, а отсутствие последействия обусловлено независимостью успешных выстрелов, т.е. числа успешных выстрелов за непересекающиеся интервалы времени Л, и Л,, где ~Л,-, Л,. — независимы. Таким образом,

Р ~у(~) = к ~ = е ", для ~ = 0,1,2,...

Заметим, что модель работает для любого Й, хотя цель будет поражена первым же

успешным выстрелом. Найдем теперь функцию распределения Т„,, (в нашем случае времени от

начала стрельбы до поражения цели).

56

Распознанный текст из изображения:

Н(~) = Р1 Т„е < ~ 1= Р (у(~) > 1 ~ = 1 — Р (1 уЯ = 0 ~ = 1 — е "

М [Т1

теперь, зная закон распределения, можем, например, найти М [ Ти 1 = — = — =

Л,~р р

где М [Т1 — средняя длина промежутка времени между соседними выстрелами.

Характеристики СМО в основном зависят от М [Тюб] и сравнительно слабо зависят от вида закона распределения времени обслуживания. Поэтому в теории массового обслуживания, для упрощения исследования, часто пользуются допущением, что время обслуживания распределено по показательному закону.

Занятие 2. Система МО с Я приборами и ограничениями

на очередь

Вывод прямых и обратных дифференциальных уравнений СМО

Рассмотрим простейшую разомкнутую СМО с одним прибором и одной очередью, на вход

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

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

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

Л вЂ” э 000 00 -+,и

х

х(~) у(~)

здесь у(() — случайное число обслуженных заявок за время ~. Обозначим через Е»

состояние, при котором в системе находятся 1 требований. Рассмотрим возможные переходы

состояний в интервале времени (Г,(+й) и соответствующие им вероятности с точностью до

бесконечно малых более высокого порядка.

При 1=0:

Ео + Ео

Р ~ х(й) = 0 ~ = 1 — ЬЙ

Р~х(й) =1 ~= Ы~

ЕО -Э Е)

При у!с > 1:

Е, -+ Е, Е„ — + Е,

Р ~(х(й) = О ~ х Р (у(й) = 1 ~ = (1 — ЫР> рй =,»»й

Р ( х(й) = О ~ х Р )(у(й) = 0 ~+ Р )(х(й) = 1 ~ х Р ( у(й) = 0 ~ =

= (1 — Щ) х (1 — рй) + 7иИ х,ий = 1 — (Я + р)й

Е, — + Е„Р )(х(й) = 1 ~х Р ~(у(й) = 0 ~ = Ы1(1 —,ий) = Ьд

Обозначив Р»(() = Р~(Е»(() ~ — вероятность того, что система в момент времени 1

находится в состоянии Е», придем к следующим разностным уравнениям:

~ = 0 Р, (с + й) = Р, (~)(1 — Хй) + Р, Я рй

Ус > 1 Р, (~ + й) = Р» ) Я7иИ + Р» (~) [1 — ((, + р) й~~~+ Р»,! Я~ий

Или, после предельного перехода к дифференциальным уравнениям:

)с =О

о ~Р()+ Р()

Й

й>1 ЙР»

' = ЯР» 1Я вЂ” (1+ Р)Р,Я+»»Р»„1Я

й

Начальные условия Р„(0) = 1, Р»(0) = 0 при )уО ~ и. Это прямые дифференциальные

уравнения СМО. При всех»» = 0,1,2, ... они представляют полную модель СМО. Выведем систему

уравнений, эквивалентную прямым уравнениям, но такую, в которой в каждое уравнение входят

только вероятности, относящиеся к одному и тому же состоянию Е» в момент времени

Обозначим через Р» (1) — вероятность перехода системы из состояния Е„в состояние Е„за

(и)

время 1. Рассмотрим возможные изменения состояния СМО за интервал времени (О,»+й).

Разобьем его на два соседних интервала (О, Й) и (й, Е+ й) .

если в начальный момент система находилась в состоянииЕО, то в состояние Е» в

момент времени 1+Й она может попасть следующим образом: либо за интервал (О,й)

состояние не изменилось, а за интервал (Й, 1+ Й) она перешла от ЕО к Е», либо за интервал

(О, й) она перешла от Е к Е,, а за интервал (й, ~ + Й) она перешла от Е, к Е» . В

соответствии с этим имеем:

Р~" (! л-с(!) = Р(х(с1!) = О )х Р~ Ес(с)!) — ' — еЕл(!+с») ~+

-; Р ( х(суд) = 1 ) х Р (Е (с)а) — '— е Ес (у+ пг!) 1= (1 — рсИ)Рлсю(у) РиууРссп(!) .

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

состоянии Е„, и > 1 приводят к соотношению

Р(")(~+ й) = яи41Р(" ')Я+ [1- Л+ Ф)4Р(")(~)+ ЫР(" )(~).

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

п=О ~Р(о);

д ' Р) =-ЛР,'"(~)+Лри)0)

й

п>1 г'") (р)

()= Ф,— (,) (Л,ЯР, (,)+ХР, (,)

Р». '10) = 1,Р»("'(0) = 1 при и ~ )УО. При всех Й = 0.1.2.... это полная модель СМО, представленная обратными уравнениями.

Установившийся режим

Говорят, что для данной системы существует установившийся режим, если при 1 — Ф со

длл любого» сУществУет пРедел 1гт Рспп(!) = Рс > О, ле зввислший от и и ~~г Рс =1 1 длл

/-всю

»=О

прямых уравнений можно также писать Р» (() вместо Р» (() ). Все другие режимы, отличные от

(дс)

установившегося, называют переходными. В установившемся режиме

1ип Р»(")(~+ Й) = 1ип Р»(")(~) = Р,,

у-дсо l — усе

Распознанный текст из изображения:

ХРо — (Л+ р)Р, +,иР, = О, тогда Р, =

1-р '

2.Если о

накопителе

фР» + ~~Р»„= 0 следует

»+1

Л

Р,.

Р

Р, Л

Р о (~~+ Р Н

Я

Для — < 1 имеем:

Р

Р, Л

=1- Р, =1

Я ц

1 ——

Р

>>> »> Я

»=о »=о Ф

или, переписывая в другом виде,

р > 1 очередь растет больше средней длины

интервала между поступлениями требований — .

системы обратных

Т„, распределено по

~2 ~)> Т ~з

[ (~)1

М[Т~

61

60

л'„(")

поэтому = 0 и из прямых уравнений следует:

й

Я

— ЯР + ф~ = О, тогда Р, = — Ро;

Р

Л Если Р» = — Ро, то из й -ого уравнения ЯР», — (Я+

Р

Я' Следовательно, для всех й = 0,1,2,... Р„= — Р .

ф

получим:

Л = (1 — Ро),и — уравнение непрерывности.

1

Отношение = — — называется коэффициентом использования системы. При ((~ <1

Ф

имеем условие существования установившегося режима. Когда

1

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

ф

Выразим Р через: Р =1 — у~, тогда Р„= р (1 — р).

Заметим, что Р„действительно не зависит от и . Для

йР,(")

дифференциальных уравнений при = 0 получаем:

й

,1Р(о) + ДР<') — 0 — Р(') — Р(') .

,иР~ ) — (Л+,и)Р~ ~+АР~ ) =0 ==> Р® = Р() ит.д.

Таким образом, Р = Р ' = Р„= ... для всех и и каждого й = 0,1,2,.... Это

(о) (1) (2)

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

Числовые характеристики простейшей СМО

Найдем некоторые числовые величины, характеризующие СМО в установившемся

режиме. 1. Пусть У вЂ” случайное число требований в СМО, тогда

— )=КР> =~ "(1-~)Кк'=г"

»=1 >'=о среднее число требований в системе

4>> >>> ~ >О ~Г 1 ° =мМ=Х»р =«-ч «~~»ш" '=(1-~)~ — К~" =(1-~)~—

»=)»=) ~~ »=о Ыр 1-у

т.о. Р))И>и ~.=р" и п = —,

и

1'-р

— случайное число требований в накопителе, то среднее число требований в

>>>

» = ~ [» 1 = Я»Р>,> = (1- ц~ ру' я, »>р' ' = —, > 0. >> = = > »» .

1-у 1 — у

' Обозначим через 1 „— среднее время пребывание требований в СМО, 1, — среднее

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

через СМО проходит в среднем Л заявок, имеем:

и 1 у~ 1 — ~' и ()у

Л Л 1- у,ц(1 — ((~) Л . (, р(1 — Р)

1

вспомним, что 1„д = М[Т„о1 =—

ф

1

с другой стороны ~,б =~,„, — ~.:

ц(1-Ч ) И(1-()~) И

Вывод дифференциальных уравнений системы МО с Я приборами

Задано:

1. Входящий поток заявок — пуассоновский с плотностью Л .

2. СМО имеет одну упорядоченную очередь.

3. СМΠ— разомкнута. Если все Б приборов заняты, то заявка поступает в накопитель, где

ожидает случайное время Т„, Р1Т„< ~ (=1 — е ", ~ > О. Если к моменту

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

4. Время обслуживания одной заявки одним прибором

показательному закону Р ~(Т, < ( ~ = 1 — е ~, ~ > О.

Отменим различия входящего и выходящего потоков. Для входящего потока имеем:

и т. д. Л вЂ” среднее число заявок, поступающих в систему за единицу времени. Для потока

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

Распознанный текст из изображения:

условия

ЙР» Я~

ж ~,„

и имеет вид

Р» = ~у РО,при й=0 "~Я;

Ы

Замечание о расширении модели СМО

5+1

1 О

"я+ — '

Ф

Р,,г =

1. Средняя длина очереди:

и =~гР,. „,

г!

или, обозначив и = Я+ Р'

65

Рассмотренный класс СМО допускает установившийся режим. Решение находится из

1

5+2

р — Р,, в общем случае

Я+ — Я+2—

Я+г

Р,, при / =1,2,....

"и(" -„')

1 Так как р Р» — — 1,то Р— О к+г Я Я лЪ+1

Р

Условием установившегося режима является сходимость ряда

г=1

1~/

частности, он сходится при — = — < 1. Этим решением охватываются все случаи 1-3.

Я Яр

Числовые характеристики СМО с Я приборами

и = ~(л — Я)Р„.

о=Ь'+!

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

Я-1

р = ~~> (Я вЂ” »)Р„.

»=О

3. Вероятность отказа в установившемся режиме:

Р

Я~

отл.

!.)у — среднее число заявок, покидающих очередь необслуженными в единицу времени

11 (вспомним величину гу ).

Л, — среднее число заявок, поступивших в систему в единицу времени 11 .

Величина д = 1 — Р . называется пропускной способностью системы. Она представляет

отл

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

4. Оптимальное число приборов. Пусть С вЂ” плата за простаивание одного, прибора в

единицу времени, а СΠ— плата за ожидание одного требования в единицу времени,.тогда для

полной стоимости потерь в единицу времени получим

ю-! <О

С(я) = С ~(г — п)Р„+С, ~(я — п)Р„.

о=О п=ю+1

ЯО, при котором достигается ппп С(ю), называется оптимальным числом приборов.

У

Можно дополнительно ввести выход приборов из строя следующим образом. время

работы прибора до выхода из строя — СВ, распределенная по показательному закону

Р(Т<г1=1 — е ', ~>0, Т= —.:

Я

Такие модели СМО применяются для анализа боевых действий группировок.

Можно рассматривать также и восстановление приборов

Р~Т<~)~=1 — е ", ~>0, Т= —.

в 1

р

Здесь Т вЂ” среднее время выхода из строя и восстановления приборов соответственно.

Распознанный текст из изображения:

Ф -1

=-Л,т,1!) тс!!) — ~ЙР,"'!!) =

66

Тема 8. Метод динамики средних и его применение для

исследований аналитических моделей динамики боевых

действий

Занятие 1. Обоснование метода динамики средних

Сущность метода динамики средних

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

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

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

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

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

Вывод уравнения для вероятностей состояния единиц

Рассмотрим две противоборствующие группировки. Пусть 1-я группировка имеет в своем

составе Ф1, а 2-я Ж2однородных боевых единиц. Каждая непораженная боевая единица

производит пуассоновский поток выстрелов по непораженным единицам противника. Обозначим

через Л„и Л, средние скорострельности одной боевой единицы соответственно 1-ой и 2-ой

группировок, а через Р, и Р2 — вероятности успешных выстрелов. В силу независимости успешных

выстрелов перейдем от пуассоновских потоков с плотностями Л„и Л, к пуассоновским потокам

успешных выстрелов с плотностями Л, = Я)Р, и Л = Я Р . Л,, Л вЂ” эффективные

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

Пусть Р1(г) (Р2 (г) ) есть вероятность того, что в момент времени г в 1-ой группировке

(во 2-ой группировке) сохранилось г ( 1 ) боевых единиц, где 0 < ! < Ж1 (О < г < У ). Найдем

Р, '(г+ Йг) . Эта вероятность равна вероятности того, что в момент времени г 1-я группировка

состоит из У1 единиц, умноженной на вероятность того, что за время й 2-я группировка не

смогла произвести успешного выстрела. Учитывая, что:

Л1у Л!

Р !!)=1,и яамеияя т = "гсссР Я,

)=О 1=1

получаем Рся'1!ой) = Рс"'!!) Р, 'с-~~~ Р~1!)11 — !сЛ.,Й)

= РЯ'!!) ! — ~)сРгь!!) Л,су! = Р, '1!)[! — т,ЯЛ с!![

.": ' 1!=1

Для к, удовлетворяющему двойному неравенству 0 < 11, < 1"1'1, имеем:

Р, 1! + й) = Р,"1!)[! — та 1!)Лес)!]ь Р> "ЯтгЯЛьс)!, гле тя1!)Лай — аероятиоегь того, что

2-я группировка произведет один успешный выстрел за время Й, а 1 — т (г)Л Йг — вероятность

того, что 2-я группировка не произвела ни одного успешного выстрела за время й, И, наконец,

Р,'(г+ й) = Р,':(г)+ Р1'(г)т,(г)Л,Й.

Переходя от разностных уравнений к дифференциальным, будем иметь:

— (г)Р '().

й

= — Л,т,(г)Д (г) — Р1 (г)Дя 1<1 ~1 — 1; ' = Л,т,(г)Р) (г).

Аналогично, для второй группировки имеем:

2 () Лт(г)Р~,(г)

й

= -Л,тс1!) [~,'!!) - Ря" !г)], ! < сс < Лг, - 1;

й

~Ро

~~' () =Л т ()Р (),

й

причем при г=О Р,"'=1, Р, ' '=...=Р, =0; Р2'=1, Рз' '=...=Р2 =О

согласно условию.

Вывод уравнения для среднего числа единиц и дисперсии числа

сохранившихся единиц

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

Л! -1 Ф-1 Ф -1

~~) ссР,"'!!) = ~!/се-!)Р,"1!) +Рс'!!) — Р,'1!) — ~гЬР,"'!!) =

~!Р,'1!) — 2 Р,'1!) =т,!!) -[! — Р,'1!)] = -Л,т,1!)[! — Р,'1!)].

1=1 1=1

Для второй группировки:аналогично. Таким- образом, приходим к следующей системе уравнений:

Ит)(г):

. ='— Лять!!)[! — Рс'!!)]

Йи, (г) = — Лст,1!)[! - Р, 'Я] с начальными условиями т! (0) = Ж1, т2(0) = Уз .

Распознанный текст из изображения:

с=!

Р~Х (г,) — т,(г,)]< с]=Б.

Действительно, пусть

~Х! (~, ) — т) (~, )~

,('З,(гг)

=о", отсюда

е'Й=Ф,—

Е

МОЖНО ПОЛОЖИТЬ Г = И

2у,(г )

следовательно, ф

Е

=о.

/2с, (с„)

Уравнение боя Ланчеетера (модель А)

Л( -1

= — Лттт(г) с,(г) — ( Й'Р,""(г)

68

Оценка боя в среднем (на уровне математических ожиданий) имеет смысл лишь при

большом числе боевых единиц, когда индивидуальные особенности отдельных единиц

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

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

боеспособность. Поэтому решения системы дифференциальных уравнений ищем при 0 < 1 < т,

где 2 определяем из условия: '

т! (~) = Л. Ж! л: т, (~) =. 2з -. 2')('„(О < Л <1), =

но тогда получим: Р, (1) = О, Р, (~) = 0 .

Окончательно получим уравнения боя Фр Ланчестера (модель А):

дт;(~)

й

— ~2Р222 ~),

Йн,(~)

,Й

= — Л!т)(~) .

До сих пор мы предполагали, что противники ведут' прицельный огонь по каждой

непораженной единице. Предположим теперь, что. стрельба ведется без переноса огня, то есть

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

,И т2Р)

единицам. Тогда вероятность попасть в непораженную единицу будет ' или

1 2

Эффективные скорострельности Л, и Л:примут вид:

Л =Я)Р! 2()

1 ! Л), >

2

Л, =Я,Р,'

1

где Р), Р— вероятности успешных выстрелов при условии, что выстрел пришелся на

1 1 1 1

непораженную единицу. Обозначив Л! = Я„Р), Л2 — — Х Р,, получим уравнения боя Ланчестера

(модель Б):

сКт)(~) Л,

= — — т, (1)т2(1),

й Ж,

от,(~) Л',

= — — 1т!(~)т,(~) с

2

с начальными условиями т! (О) =. 2)(1; т (0) = 2")(

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

(для модели А).

В,(г) = 2 [/с — т,(г)~ Р, (с) =

АюО

Л(! . ', ' 'Л(! М! = ~ !с'Р,'Я вЂ” 2т (!)2 гсР,"(г)+т,'(!)~~~ Р,'(!) = с,Я вЂ” т,'(г),

)жО Ьио ЛыО где с, (1) — второй начальный момент. Отсюда: сИ! (~) сУс, (~) а~т! (~)

Й. Й й

= 2. гс' ' = -Л;: , Я .ЛгтР, '(!) + 2 /сг [Р,' (!) — Р,"'(!)] =

Л( -1 ЛУ -1 Л(-1

(сР,'" (г) = 2 (Iс ч!)'Р,"'(с) +Р, '(г) — Р, '(г) — 22 )сРы'(с) =

!ею! )с=! Ьж!

= с, (с) — 2т, (с) -ь 1 — Ре (г) ]] =

= -Л,т,(г)[2т (с) — [1 -Р,'(г)] .

Так же как и раньше полагаем Р, (1) ж О, тогда — '= — 2Л2т!(1)т (1)+Л2т (Е).

сКс, (к)

Окончательно имеем: ' = — 2Л2т!(к)т2(к)+Л т2(к) — 2т!(г)[ — Л т2(г)1= Л2т2(~).

2'~) (~)

сй

Ж2 (К)

Аналогично, = Л т (~) .

й

Найдем начюьные условт: 2У, (О) = ~ (й — Лг, )л Р,'(0) = О, так «т толью

Р,"'(0) и 0 [с' '(0) и1), но при гс = Л, первый сомножитель равен нулю лнюогично, с) (0) = О. Итак, в любой момент времени 0<1 <г мы можем определить математические ожидания и дисперсии количеств боевых единиц двух группировок. Обозначим эти случайные величины через Х!(!) и Х2(1) соответственно. Разобьем интервал ~0,2] на и частей й =О, ~„...,$„=2, и представим Х,(с ) = 2 Х,'(г„), где Х, (у ) = О, если о' -твл единииа первой группировки помьжева

к моменту времени 1 и Х'(1 ) =, если не поражена. На основании центральной предельной теоремы теории вероятностей случайная величина Х, (1 ) распределена асимптотически нормально с математическим ожиданием т! (1 „) и дисперсией Й! (1 ) . тогда, задавшись значением доверительной вероятности О, можно определить доверительный интервал Е из соотношения

уд Х

2

!е

2

Б = — ') е т с!т = ') е ' о".с = =

!о

Так как С,д(Ъ,(гь) лолжно быть < и, то

Занятие 2. Применение метода динамики средних для

построении аналитических моделей

Пусть Л, =соий и Л, =сот1; ' = — Л, ' =Л!Л2Рл!(~).

!2~и,(г) йп,(~)

й ' Й

Общее решение дифференциального уравнения имеет вид:

Распознанный текст из изображения:

Из начальных условий следует:

т,(0) =Ж! =с, +с,;

ат1(г)

= — Лайт = с,д/Л1Лт — стч/Л,Л,,

,=о

С2 =Ж! — С,,

,/Л, Л, !с, ч. с, — Ж, ) = — Л,Лг,;

Уравнение боя Ланчестера (модель Б)

1 Л2М2 'Ф, 1

г,!лл, ' г =г

2

1

с = — Ж+

2 1

2

1

,/л,л,~

2 2 1

1

т1(~)=- Ф;—

2

—,/л,л2с

д'е' 2 8

= тт',с1гт — М д1тт, где т = л~Л,Л у .

Введем также безразмерные переменные:

л~(г) т,(~) У,

,и =~,,и2 =, к=

и, и, и,— и,

откуда ф2 = —,и, + С,, С, =1 — — = и, и, и,

аи!

2 2 1

где — ' ' =маг, с, = — 'с =

уи1(Я! + с2)

70

1 ,и1 = СЬТ вЂ” — ЯЬТ

к

,и, =СЬг — кяЬт

к называется коэффициентом преимущества: когда к ) 1 — побеждает первая группировка, к < 1 — вторая, а при к = 1 — ничья.

Область, где решение имеет смысл.

Каждой паре кривых.,и, =,и1(т),,и =,и (Г) на плоскости безразмерных переменных (2 „и) соответствует целый класс подобных процессов (боев) в размерных переменных. Например, два боя с Ф! = а, У2 = Ь, Л, = с, Л, = И и Ж! = 2а, У2 = Ь, Л, = с, Л, = 4Ы

а будут изображаться одной парой кривых.на плоскости (т,р), отвечающей к = —, хотя

Ь второй бой в действительности будет в два раза быстротечнее: для первого боя т=т/Л,Л у, = готгу,, дле второго т=2чЯут, откуда у =у,!2. Заметим, что если ЛГ,

увеличить в к раз, то и К увеличится в к раз, а если Л! увеличить в к раз, то К увеличится в

~/к раз, то есть увеличение численности дает большие преимущества, чем такое же увеличение

скорострельности. Такой характер зависимости к от У,. и Л, получил название квадратичного

закона Ланчестера.

ат! (~) Л,

й Ж!

йп2(1) Л,

= — — 'т1(~)т2(г);

й Ж2

,и, = '(), (2 =1,2).

Ж,.

После замены:

ар, лж,

— И! И2

й Ж!

Л,Ж,

ди! Ф2

~г

Л1Ж! Л2Ж2

Обозначим и = ' ', и

1 ~ ' 2

Окончате но имеем:

фМ,

и2 и1Ф2

Ф2

и! и1,и2

Разделим второе уравнение на первое:

а!,и2

— — с~,и = — а~и

4~~

После подстановки ф в первое дифференциальное уравнение получим:

— = — и2,и„—,и, +с, = — и,,и,,и, +с,—,

тык! ! 2

Умножим обе части последнего уравнения на С и преобразуем:

С 241 4и Ф!

— — — =с ий.

2 1

,и,(~и!+с,) и, +с, и!

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

1П(~и! + С2) — 1П,и! = С2и!l + Сз, где Сз = 1П(1 + С2) .

В результате преобразований получим:

Распознанный текст из изображения:

т=1

Прямая задача; х = ~ р,.х, -+ тах

!<ж!

тп

ч! Ь,у,<р, !'=1,...,п; у,.>0,

Ьж)

Сопряженная задача: н = ~С,.у,. -+ тт

для допустимых решений.

пнп ~2 > гпах ~

Покажем, что

тл и

о = ~ с,. у,. > 2м у,. 2м Ь„. х,.

Ьм1

Ьж!

ппп~ > гпахг.

76

р, г

Рассмотрим семейство прямых х = — — х, + — с параметром 2. Из рисунка видно,

Р Р2

что максимальному значению г отвечает прямая, проходящая через точку М . Теперь

предположим, что прямые семейства параллельны прямой ВМ , тогда в качестве точки

! О О

М (х,,х ), дающей оптимальное решение задачи ЛП, можно принять любую точку, лежащую

на отрезке ВМ: х1 = ЛХ1 +(1 — Л)х,"; х = Ь +(1 — Л)0 = у1х~~, т.е. выпуклую линейную

комбинацию точек В и М.

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

прямые семейства, соответствующие целевой функции 2 параллельны МВ, тогда оптимальным

решением будет любая точка прямой МВ, лежащая правее точки М .

Если в рассматриваемой задаче изменить область определения функции г и при этом

прямая МВ примет положение МВ', то линейная форма может возрастать неограниченно, т.е.

оптимального решения не существует. Если же МВ примет положение МВ" в результате

изменения балансных условий, то функция г достигает гпах в единственной точке М, не

смотря на неограниченность области определения 2. (Решения задачи ЛП не существует, если

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

г = р)х, + р,х, + р,х,; Ь„х, + Ь„х, < с,, Ь„х, + Ь„х, < с, . На Х не наложено

ограничений(при Рз ~ 0).

Выпуклость области определения решения

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

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

что и в общем случае область определения решения задачи ЛП вЂ” выпуклая.

~ о

~М'(Х),...,Х„) Е 6 и М" (Х,,...,Х„) Е 6 М(Х,,...,Х„) Е б, где Х,. =,Ь,:,+(1 — Я)Х,

0< 1 <1.

Пусть точки М (х„..., х„) и М (х,,..., х„) удовлетворяют условиям:

и и

ч! Ь,,х,.<с,; х,.>0; 2 Ь,,х,<с,; х,.>0,

!ж! 1=1

где ~ = 1, ..., т; у = 1, ..., У1, т.е. принадлежит области определения функции 2

тогда для х, = у!х,. +(1 — у1,)х,. имеем

. и и и

~Ь,,х,. = д2 Ь„х, ч-!1 — 2)2 Ь,,х,. < 2с, о!1 — Я)с,. = с,,

1ж! 1=1 !ж!

где х > 0 так как х . е,"х ., х,, а оба конца отрезка неотрицательны (или

.! ~ ./з /Л'

х,. = Ях,. + (1 — Я)х,. > 0 так как Л > О, 1 — уО > О, х,. > 0 и х,. > 0).

Следовательно, выпуклая линейная комбинация точек М, М также принадлежит

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

В трехмерном случае балансные и граничные условия задают в пространстве (х„х, х )

выпуклый многогранник, а целевая функция — однопараметрическое семейство параллельных

плоскостей (2) направления возрастания функции 2: СУЙС!' ~ = (,01, р „Уз) . В трехмерном

пространстве, если задача ЛП имеет решение, то возможны следующие случаи:

1. Плоскость (г) проходит через вершину многогранника. В этом случае задача ЛП

имеет единственное решение;

2. Плоскость (г) проходит через ребро многогранника. Любая точка ребра

оптимальное решение;

3. Плоскость (г) проходит через грань многогранника. Любая точка грани

оптимальное решение. Если грань образуется Й вершинами М,. (х,', х х3),

! =1,...,Й, .то произвольная точка грани М(х„х„х,) представляется в виде

выпуклой линейной комбинации точек М,:

х, = 2 2х!., / = 1,2, 3, где 2,. > О, ч! А, = 1.

Прямая и двойственная задачи линейного программнр. '":- ия

и

; 2 Ьх,. < с,, ! =1,...,тп; х, > О, !'=1,...,п.

1=1

и и! и

= ~ х,. ~Ь, у, > ~ р,.х,. = х, итак о > я чу! и ~х . Откуда

!ж! т=1 у=!

Распознанный текст из изображения:

Игры различаются:

максимальный платеж а = гпаха/ = таХгп1па//

/ з /

79

.. Тема 1О. Методы теории игр и их применение к

исследованию эффективности боевых действий войск.

Занятие 1. Основные понятия теории игр.

Нижняя и верхняя цена игры. Принцип минимакса.

Игра — набор правил, регламентирующих поведение участников игры. Участники игры

называются игроками, партнерами, сторонами. Партия игры — возможная реализация правил.

Стратегии игроков — способы проведения игры каждым из участников. Ход игрока — момент времени,

когда игрок выбирает одну из возможных стратегий. Саму выбранную стратегию называют выбором.

1) По числу участников: игры 2 — х и более лиц.

Когда мы говорим «Игра и лиц», то это означает, что согласно правилам игры игроки

разделены на л непересекающихся множеств, причем в одно множество объединяются

участники с. общими интересами.

2) По организации платежей: игры с нулевой и ненулевой суммой.

Рассмотрим игру //лиц. Пусть а,. (~ = 1, ..., п ) — плате ~ -того игрока в конце партии. Если

а,. < О, то й,. — выигрыш, а если а/ > О, то й/ — проигрыш ~ -того игрока.

При и, = О партия игры называется партией с нулевой суммой. Если все партии игры с

нулевой суммой, то сама игра называется игрой с нулевой суммой. В парной игре с нулевой

суммой выигрыш одного игрока равен проигрышу другого. Теория игр с ненулевой суммой

применяется для изучения экономических процессов, приводящих к созданию или

уничтожению общественного богатства;

3) по количеству ходов и числу стратегий: конечные и бесконечные игры.

Если каждая партия игры состоит из конечного числа ходов и число стратегий у каждого

игрока конечно, то игра называется конечной. Все другие игры бесконечны;

4) по информации, которой располагают участники: игры с полной и с неполной

информацией.

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

полной информацией. В противном случае — игра с неполной информацией.

Рассмотрим игру двух лицХи 1'размерности т х и, т.е. игрок Х имеет т стратегий

х,, х2,..., х„„а игрок 1' — П стратегий У,, у2,..., У„. Партия состоит в том, что игроки Хи У выбирают

по одной из своих стратегий х, и У,,в результате чего, платеж игрока Х составляет величину й~, а

платеж игрока У при игре с нулевой суммой (- й,, ). Таблицу ~(~, ~) = й~, задаваемую функцией целочисленных аргументов 7 = 1, ..., ~п и

/ = 1, ..., и сопоставляющей паре стратегий х,.иу,. платеж а,,, называют платежной матрицей игр, а

игру, заданную платежной матрицей, называют игрой, приведенной к нормальной форме.

В общем случае решить игру — значит указать, какие стратегии и как часто следует применять

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

а игроку 1'минимизировать свой проигрыш.

Решение игр основывается на принципе минимакса, который состоит в следующем: какую бы

стратегию х не выбрал игрокХ, игрок Уответиттакой стратегией У., чтобы /./,= гп1пй„..

/ /

./

Следовательно, игроку Х из всех своих стратегий нужно взять такую х,, которая обеспечит

Величина а называется нижней ценой игры, а стратегия х/ — минимаксной стратегий

игрока Х. Нижняя цена игры является гарантированным выигрышем игрока Х при любой стратегии

игрока 1'.

С другой стороны, на всякую стратегию У,. игрока 1' игрок Х ответит стратегией х/,

обеспечивающей платеж /В/ = тах а/, . Следовательно, из всех своих стратегий игрок у выбирает такую У, которая обеспечивает

минимальный платеж /В = гпах,В,. = пип тах а/, .

т /

Величина Р называется верхней ценой игры, а стратегия у,.о — минимаксной стратегией

игрока 1'. Верхняя цена игры — это тот гарантированный уровень, больше которого игрок 1' не

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

применял игрокХ.

Прямоугольные игры с сейловои точкои

В общем случае Я <,О. Если же оказывается Я =/О, то мнимаксные стратегии х,о и У,.

принимают за решение игры; а элемент т/у' = и„„; — шах пип а„. = пцп п1ах а//, называют ценой

! / / т

игры. При этом (гО, ~0) является седловой точкой функции ~(г, ~) = ~,, г = 1, ...,/и; / = 1, ..., и.

Онйейенение: Точка к и Х, уе и у называется сеаяовой точкой вещественной функции ~(х, у), определенной на множестве х х )х, если

Лх Уо) < Лхо з Уо) ~х '= ~

Х(хо уо) < Х(хо у) ~у ~ )

Предположим, что существуют величины а = тах пцп ~(х, у) и,0 = Ппп тах,/ (х, у) .

ХйЛ йЕУ уй/ хйЛ

Покажем, что всегда й' < Р.

По определению максимума функции:

~(х,у) < тахтах,у);

по определению минимума функции:

Распознанный текст из изображения:

ппп~(х,у) < ~(х,у).

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

пип~(х,у) < гпах~(х,у), у~хе Х, чу != У.

уеУ хеХ

Правая часть неравенства не зависит от х, поэтому:

гпахппп~(х,у) < гпахДх,у), '!7у е г'.

, хеХ уеУ хеХ

Аналогично рассуждая для у, получим:

гпах пипках,у) < пипгпах~(х, у), т.е. а < р'.

хеХ уеУ уеУ хеХ

Таким образом, нижняя цена игры не болу«ше верхней.

Определим необходимые и достаточные условия сушествования седловой точки функции

Л у)

Необхо имое словце: если точка (хо, уо ) — седловая точка функции ~ (х, у), то

~(х„уо) = гпахпип~(х,у) =пиптах~(х,у).

хеХ уеУ уеУ хеХ

По определению седловой точки Х(х> уо) < Х(хо > уо) ~х ~ Х хо ~ Х ° уо ~ 1'.

Поэтому

гпах~(х,уо) < ~(х„уо).

По определению минимума функции имеем:

пипгпах Дх,у) < гпах~(х,уо) < ~(х„уо).

уеУ хеХ «еХ

С другой стороны,

Х(хо>уо) < Х(хо>У), ~у~~ хо ~Х, Уо '=- ~ ~(х„уо) < пап ~(х„у) < пих гшп Дх, у) .

уеУ хеХ уеУ

Откуда

Таким образом

гшпгпах~(х,у) < ~(х„уо) < гпахпип~(х,у),

уеУ хеХ хеХ уеУ

или ф < Дхо, уо) < а.

Учитывая полученное ранее соотношение а < )О, получаем ~х = Дхо, у ) = р.

остаточное словие: если существуют величины а = гпах пип ~(х, у) и

хеХ уеУ

ф=пипгпахДх,у), и а=ф, то функция ~(х,у) имеет седловую точку.

уеУ хеХ

Из сушествования и следует, что существует такое х е Х,что п1гпДх„у) =а.

уеУ

Из существования уВ следует, что существует такое уо Е,у', что гпах Дх,уо) = р.

«еХ

Так как а=р, то пипках„у)=гпах Дх,уо).

уеУ хеХ

По определению минимума функции:

пип ~(х„у) < Дхо, у,) .

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

гпахДх,у,) < ~(х„уо) =~ Дх,уо) < Дх„уо), ~хе Х.

По определению максимума функции:

Дх„уо) < гпах~(х,уо).

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

~(х„уо) < пип Дх„у) =~ ~(х„уо) < ~(хо,у), Чу ~ г'

заметим, что из всех точек (хо, Уо ), УдовлетвоРЯющих соотношению се =)8 седловыми будут лишь те, которые удовлетворяют также соотношениям: пип ~(х„у) = а и гпах Дх, у, ) = р'.

реУ «еХ

Все определения и свойства, относящиеся к ~(х, у), могут быть без изменения перенесены на вещественную функцию двух наборов переменных ДХ, У), где

Х = (х,,...,х„,), г'=(у,,...,у„).

Прямоугольные игры без седловых точек.

Если СУ = Р', то решение игры ищется в так называемых чистых стратегиях, т.е. во всех партиях игроки будут использовать свои минимаксные стратегии хуо и у о .

уо ' Если же а= гпахпипа„..< пипгпаха„. = ф и функция ~(г, у) не имеет седловой точки,

1 / / то решение игры ищется в смешанных стратегиях

~ ")* совокупность неотрииательных чисел Р =! у>,, у>т, ..., Р,„) таких, что чь р, = 1, причем р, есть частота (вероятность), с которой игрок Х выбирает стратегию ху. Для игрока у' соответственно имеем:

Д = '1 сУ,, |Уг, ..., сУ„, ) таких, что Чь сУ, = 1.

Обозначим через Я„, и Я„множества всех смешанных стратегий игроков Х и У соответственно. Игра с применением чистой стратегии х~ для игрока Хесть игра со смешанной стратегией Р =( ру, р,, ..., О„, ), где р„= 1, аостальные Ру = О.

Математическое ожидание выигрыша игрока Х при применении игроками смешанных стратегий ( Р, Д ) есть Е У Р,Ц ) = ~~а,,р,су, = чь су,.~а„.р, .

у=!

У=! 1=!

В соответствии с принципом минимакса игрок Х выбирает такую стратегию Р е 5'„„чтобы достичь гпах пип Е(Р, Д), а игрок У вЂ” такую стратегию Д е Я„, чтобы достичь

Р .5п, УУ .5„ пи'и гпах Е(Р, Я, Р ~ Я„„Д ~ Я„. Де5'л РеЯп,

В качестве решения игры принимают седловую точку ( Ро, До ) функции Е ( Р, Д ), так как в этом случае: Е(Р 0о) -Е(Ро Оо) '~Р Е ( Ро. Оо ) < Е ( Ро 0 ) . Ю ~ ~„ что заставляет игроков применять стратегии ( Ро, Д ) как взаимно выгодные. Про ( Ро, До ) говорят, что это стратегическая седловая точка. Ро и До называются оптимальными смешанными стратегиями игроков Хи У, а величина >' = Е ( Ро,Я, ) = гпахпппЕ(Р,Д) = ппптахЕ(Р,Д)

РеЯп, Ое5л Де5„РеЯл,

называется ценой игры.

80

Распознанный текст из изображения:

Рассмотрим игру (2 х 2) с платежной матрицей:

Геометрически видно, что Г < Е (.Р,,1) 7,' =О; Г < Е ( Ро, 2) 7 2 = О.

84

Пусть тах Е ( /,Я, ) < 1у, но тогда и подавно Е ( /, Д, ) < 1у', откуда получим:

Ю )П

Е 'т 'ю 'мо ) =2 Е/г',дс)р,' < )г 2'р'.

/=1

что противоречит тому, что 1" — цена игры.

Аналогично доказывается и второе равенство.

2. Еслидля какого-либо Й (1< Й < //2 ) выполняется условие Е ( Й Д ) < ру то в

~о )

оптимальной смешанной стратегии Р р = О.

о

пусть р/, >О, тогда Е ( /ус, Я, ) р„< /у" р . так как Е ( г, Я, ) р,. < Е" р для всех

/

остальных г, то получим: Е ( Р, Я, ) < /" . Получили противоречие.

Аналогично, еслидля какого-либо 1(1<1< и ) выполняется условие: Е ( Р 1) > ~'. то

. о

в оптимальной смешанной стратегии Д величина ~, = 0;

о

Элементарные методы решения игр 2х 2 и 2 х и.

При использовании игроком Х смешанной стратегии р, а игроком У вЂ” чистых стратегий,

получим:

Е ( Р,1) = а„р+а„(1 р);

Е ( р,2)= а„р+а„(1-р). Полученные равенства можно изобразить графически:

Оптимальной стратегии игрока Х соответствует выполнение условия

тахпипЕ(р, //).

0<р<1 /=1,2

Для определения р = ро запишем уравнение в вида:

(аы а21) Р+(а12-а22 )(1 — р ).= 0; =~ (ан — а„— а„+ а, ) р = а„а„.

22 21

Ро =

а11 — а12 — а, + а

Для игрока У соответственно можем записать:

Е ( д, 1) = а„д+а„(1 — д );

Е ( Д, 2 ) = а21 Я+ а22 (1 — ч/ ).

Оптимальной стратегии соответствует условие:

тшптах Е(1,д).

О~О51 рж1,2

Рассмотрим игру (2 х /2).с платежной матрицей вида:

Графическое изображение выигрыша при использовании игроком Х смешанной стратегии, а игроком

У вЂ” чистых стратегий будет иметь вид:

Для игрока Урешение свелось к игре (2х2), т.к. его оптимальная смешанная стратегия есть Д = (О, О,

а, 1-а).

О если в игре (т х и ) заданной платежной матрипей 1 аг ~ выполняется условие

/ а.,<2 зяа,,(*)гдезя>,/г=),...,/;2 Л =),/=),...,п,г' и0,2,...,т)тоговорят,

что ~ -ая строка подчинена выпуклой линейной комбинации строк с номерами 11, г, „г/, или, что

2

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

можно оторосита л -ую строку в матриие ~ а,,1, и перейти к игре Г', размерности ((т — )) х и ),

Если неравенства (*) выполняются как строгие, то говорят о строгом доминировании (превосходстве).

При этом решения игры Г' представляют все решения игры Г. При нестрогом доминировании часть

решений игры Г может быть потеряна.

Распознанный текст из изображения:

Х(~)= „, Х(0)=Ь„; Х(0)=0

Задача об оптимальном управлении.

86

По свойству оптимальных стратегий:

Е ( ?',Я,') ~ у", ?=1, ..., л — 1, я+1, ...,т;

Е(Ро' 1) )~"..1=1,",и;

уу уу у у а

Е ( Я, Дк ' ) = ~~~~ а, д' < ~ ~ ккка,. Ук?' = 2 кк 2 а, У)У, =

у=! у=! у=! ?=1 =1

.у=

у у

=~Д,Е(к„д,') <~,У,У = У"

у=! А=!

Первая группа неравенств выполняется и для у = х. Величину Е ( Р, ' )

О, / У МОЖНО

представить в виде:

и

Е(ук.у)=а(рк',у)к.ан. О= куа,.рк~.а .а у=1 а

у=!

Таким образом, при ~' = 1'", Д = Ц, получаем:

Е(г,Я,) <Г, г=1,...,т;

Е(Р,3) >Г,у=1,...,и.

Следовательно, стратегии Р =(Р, ... Р. О Р, Ро'

о = ! ". ь-!» ь+! и)и ~о =~Ы! "' Ы )являются

оптимальными смешанными стратегиями игроковХи Ув игре Г, у' = к"' — Г,

игре,а = -ценаигры Г,но Р

не обязатеЛьно должно быть авно л

р ну ю, а поэтому возможны другие оптимальные стратегии

(~,. — ). Есу?и же хотя бы одно неравенство (*) выполнено как стр

Ро

как строгое, то можем записать:

Е(Я О ~=~Гц о(р ро

«.Чу Ь = Π— ПосвойетВУ ОПтИМаЛЬНЫХ СтратЕ ° й

у=!

у

гр:,с, у цу?, — ц;, — выпуклая линейная комбинация стратегий у, у

Дляи окаУ: э Я ц.. <

у=!

гии, ..., у,.

подчинена стратегии у„, т.е. заведомо невыгодна для игрока К.

Сущность метода динамического программирования

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

брошенная с поверхности земли вертикально вверх со скоростью ~~ .

Найти (пах Х(у'); 1уо — число.

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

задач: )у„— + У вЂ” параметр..

2. Представим п1ах Х(у) как функцию параметра

? (1Г) = гпахХ(?) и напишем для ~ (Г) рекуррентное

соотношение. Так как Х(у) = уу. — ф, то, положив? = уь, где уь— малая величина, получим:

,у'(у') =Ю+ ~(à — ф~) . (*) Если ? (1у ) непрерывно дифференцируема, то

д~ д~ Р' ?'(1у' — дЛ) = Дуу') — ф~, откуда дГ - д~' д

2 Очевидно /(О) = О, тогда ~'(1У') = . В частном случае 'Ч = Чо, ~(1~ )

2~ 2д Заметим, что для решения задачи можно непосредственно воспользоваться соотношением (*), последовательно полагая У = дЛ, 2дЛ, ..., у?дЬ = Чо.

дан функнионал уу = 16(у,Х(у),н(у))куу — и ткну,

и(у)ей

о

При условии

дХ(~)

= у?(у,Х(у),и(у)); Х(0) =Хо; б и у? — заданные функции;

и(у) — управление, Хо и Т вЂ” заданные числа, Й вЂ” определенная область. В общем случае

Х(у) — у? -мерный, а и(у) — т -мерный векторы.

1. Параметризуем задачу:

?'

УУ' = У)6(у,Х(к),и(к))к?к -+ т(п

у (.ъ ) ей, у < 5

у

дХ(я)

= Ь(ю,Х(ю),и(ю)); Х(я)~,, =Х(~);

Я

и Х(у) — варьируемые параметры. В каждый изменяемый момент времени 1 будет

рассматриваться множество возможных начальных состояний Х(у) .

Распознанный текст из изображения:

Построим таблицу:

2. Введем функцию Беллмана

Алгоритм численного решения задачи

тах М[Х„] = тах 2 [1 — [1 — к,)"'],

П1,...,ПЕ П/,...,иа

придадим ип ] ряд значений:

89

88

т

т/а //' = ]/кк[/,Х[к),и[к))а/а = Т[/,Х(/));

и(а)ей

/

Установим для нее рекуррентное соотношение

Г /+/а Т

б~6 = бсй+ бсЬ

/ / /+/1

Применим к этому равенству оператор

ппп = ппп( пп'и )

и(я)ей и(.к)ей и(я)ей

/йх~7' /+/а~х~г

(**) ~(г,ХЯ~ = ппп [ б(~,Х(~),и(~))Л+~(1+А,Х(~+А)) ], где

и(х)ей

Х(~ + Л) = Х(~) + Ь(е, Х(е), и(е))Л .

Функциональное уравнение (**) называется уравнением Беллмана. Заметим, что

т

/ [Т,Х) =О, так как 16[/,Х,и)/// =О.

Разобьем отрезок [О, Т ] на интервалы Л = Т(и . Положим ~ = йЛ, Х, = ХфЛ), и, = и(М), б„(Х„, и„) = бай,Х„,и,)[з,

Ь,(Х„и,) = ЬЯЬ,Х„,и,)Л, ~'„(Х„) = ~ЯК,Х,). Во введенных обозначениях уравнение Беллмана запишется: ~„(Х„) = пип [ б,(Х,,и )+~'„„(Х, + Ь,(Х,,и„)) ] Таким образом, непрерывный управляемый процесс мы заменили дискретным. Поскольку ~„(Х ) = О, т.к. ~(Т,Х) = О, то при /с = и — 1 имеем: ~„](Хп,) = ппп бп,(Хп „ип ]).

и„ /Ей Построим следующую таблицу: зафиксируем Хп, = Х,( ),,

/ 6

ии ] = иП ], ии ], ...Ей

ик-/Ей

Далее проведем те же вычисления для Хп, = Х,(, ), + ЛХ и т.д. до некоторого Х,(,

(2) (]) (м)

Когда 1 = )3 — 2, то

~„2(Хп 2) = ппп [ бп 2(Хп ~,цп ~)+ ~'~,(Х -]- Ь (Х 1/,)) ]

При /г = О начальное значение Хо =Х(0) нам задано, поэтому варьировать Хо не надо и

таблица вырождается в строку:

Л(Хо) = гп]п [ бо(ХоА)+Х(Хо+Ьо(Хо,по)) ]

Найдем ио, как и раньше, и ~ (Х„) будет искомым значением функционала. Теперь можно

построить оптимальную траекторию фазовой координаты Х(/) и найти оптимальное управление

// (/). Х] = Х(Л) = Хо-)-Ь,(Х,,и,), по соответствующей таблице находим

и] (Х,) = и (Л) ~ Х, = Х(2Л) = Х, +Ь, (Х],и)') -+ и,(Х,) = и (2Л) -+...

— ~ Хп = Х(иЛ) = Хп~+Ь„,(Х„„.„',)

Для данной задачи принцип Беллмана (необходимое условие оптимальности) можно сформулировать следующим образом: если процесс Х(/) — оптимальный, то каково бы ни было начальное состояние Хо и достигнутое к произвольному моменту времени 1 промежуточное состояние Х(/), дальнейшее продолжение процесса оптимально.

Занятие 2. Вычислительнаи схема динамического

программироВания

Задача об оптимальном распределении ресурсов

Пусть требуется распределить /2 выстрелов по Ж единицам рассредоточенной ГЦ, чтобы

обеспечить

где ц+и +...+и/, < и, )", — вероятность поражения 1-ой единцы при одном выстреле.

В общем случае:

К (Х„...,Х„) = д](Х])+...+д,(Х„) -+ гпах

Х,,...,Х,

при ограничениях Х,+...+Х, < Х„; Х >О (могут быть и целочисленными); д](Х])—

доход от г -того ресурса.

1. Параметризуем задачу:

Я„(Х„...,Хп) = д](Х])+...+д„(ХО)

л — параметр, )2 = О,, Ж, Х]+...+Х;, < Х вЂ” параметр.

2. Введем функцию Беллмана:

~,(Х) = гпах ~п(Х],...,Хп)

Х, Х„

и установим рекуррентное соотношение. Зафиксируем некоторое количество т/-того ресурса

Хп; доход составит дп(Хп) . Оставшуюся часть ресурсов Х-Хп оптимально распределим по

( т/ — 1) ресурсу, получим доход ~, ] (Х вЂ” Хп) . Общий доход:

Кп(Х„)+ /и 1(Х Х„)

Распознанный текст из изображения:

Начальное условие /в(Х) = О.

.Булевы функции

Алгоритм решения задачи

При и= 1 имеем:

1,(Х) = тах д,(Х,)

1

~,(Х) = тах [ д,(Х,)+~(Х вЂ” Х,) 1

о~х,~х

1 (Х) = гпах [д„(Х )+~~,(Х вЂ” Х„)1

При и=2:

При и= Ж:

Составим таблицу:

1,(И) =тах д,(1Д)

ПриХ=ЙД:

у, (О)+ ~ (/АД)

д,(д)+~(м — д)

~;(М) = гпах [ д,(1д)+~(И вЂ” 1д) 1 =

Правила булевой алгебры.

д,(И)+~(0)

Х„(Х,) = х~Д;

Х вЂ” (Хо ~м Д)

Х„,(Х, — ю„Д вЂ” я„,Д) = з~,,Д;

90

Если Х„также выбирается из условия оптимальности, то получим:

~„(Х) = пзах [ д„(Х„)+~„,(Х вЂ” Х„) ~

Ю'-

Х,(Ы) = [~,,(1д).~,,~,Кд-1д)1, ~ = 1,

Покажем, что Х,(ЙД) = гД, где О< г < к, к= 1, ..., 1п.

При ~ = 1 имеем:

При и=2 и Х = Д имеем ~(д) =- [. (1д)+~(д -1д) ~ = а'(') "(')

д,(Д)+ ~ (О)

К2(™)+~! фд — Уд); Х2(М) = уД и т.д.

Для заданного Х0 = т Д по таблице найдем:

Х~(Х0 — ~мД-- -~2Д) = ~~Д'

Х,. = л,.д, ~' =1, У,

что и есть решение задачи.

Тема 12. Применение методов алгебры логики к решению

задач обработки смысловой информации.

Занятие 1. Основные понятия алгебры логики

Алгеброй называется непустое множество элементов вместе с заданным набором операций,

которые можно совершать над элементами, не выходя за пределы множества. Элементами алгебры

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

сказать истинно оно или ложно. Будем обозначать высказывания буквами А, В, С...

В алгебре логики определены три операции:

1. Логическое сложение (дизъюнкция) - соответствует объединению высказываний союзом "или".

Обозначается А+ В, Ач В. Читается "А или В". А+ В истинно, если истинно хотя бы одно из

высказываний А' или В.

2. Логическое умножение (конъюнкция)'- соответствует объединению 'высказываний союзом "и".

Обозначается А ® В, А л В . Читается "А и В ". А ® В истинно, когда истинны и А и В.

3. Отрицание - одноместная операция. Обозначается А, 4, Читается "не А ", А истинно когда А

ложно.

В результате применения операций 1-3 к какому-либо исходному набору элементов

А, В, С... получаются сложные высказывания, которые называются булевыми функциями от

соответствующих аргументов: ~(А, „ф...); Х(А, В,С,...) и т.д.

Рассмотрим некоторые булевы функции:

1. Импликация: А+ В.

Допустим, что А+ В истинное высказывание, тогда, если А - истинно, то и В также

истинно, если В ложно, то и А тоже ложно. Однако, если В истинно, то А может быть как

истинно, так и ложно. Читается "если А то В ", или "из А следует В". Записывается А -+ В.

2. Эквивалентность: А ® В+ А © В

Пусть это высказывание истинно, тогда А и В имеют одинаковые значения истинности, т.е.

А и В либо оба истинны, либо обаложны. Читается" А эквивалентно В" Записывается А = В.

3. Тавтология - всегда истинная булева функция при 'любых комбинациях значений

истинности аргументов: все тавтологии обозначаются 1, поэтому

А+А=1;А~В+В=1

Вместе с этим символ ! используется для обозначения связей между элементами:

А+ А = 1 — тоже, что и А — + А;

А ® В + А э В = 1 — означает эквивалентность А = В .

Отрицание 1, т.е. 1 = 0 — тавтологически ложный элемент.

Распознанный текст из изображения:

№(А е В е С) = 00001000; №(А е В е С) 00000100, № (А е В е С) = 00000010; №(А е В е С) = 00000001;

№(А ВеС) =10000000; №(А е В е С) = 01000000; №(А е В е С) = 00100000; №(А е В е С) = 00010000;

0123

№А=0101

20

№В=ОО! !

Операции над изображающими числами

= 00010001+ 00001100 = 00011101

0 1 234567

Логическая зависимость

где *=О ч1

93

92

Базис и изображающие числа булевых функций

Булева функция считается заданной, если мы можем указать значения истинности этой функции при всех возможных комбинациях входящих в нее элементов. Таблица чисел, которая представляет все возможные комбинации значений истинности заданного набора элементов А, В, С... называется базисом для этих элементов. Стуока этой таблицы, соответствующая, например, элементу А, называется изображакицим числом и обозначается № А. Обозначим 1 - истина, О - ложь, тогда для одного элемента №А = 01;для двух:

Для и элементов базис будет содержать 2" столбцов. Колонки базиса можно занумеровать

теми двоичными числами, которые представляют сами колонки. Если номера колонок упорядочены по

возрастанию слева направо, то базис называется стандартным: 0,1,...,2" — 1 и обозначается в 1'А,В,С...].

1. №(А+В) =№А+№В поразрядно, без переноса в старшие разряды, по правилу: 0+0=0;

0+1 ='1+0 =1; 1+1 =1. В базисе в 1"А,В] № А = 0101,№В = 0011,№(А+ В) = 0011;

2. № (А е В) =№ Ае№ В поразрядно по правилу: 0 ® 0 = 0; 0 ~1 = 1 ° 0 = 0; 1 е 1 = 1; № (А ~ В) = 0001.

3. №(А) = (№ А) поразрядно по правилу: 0 = 1; 1 = О, №(А) = 1010 .

Теперь можно вычислять изображающие числа функций 1(А,В,С,...) по отношению к

базису в ~А,В,С,...1, например:

№ ((А ~ В) + В е С) = (№ А) е (№ В) е (№ С) =

= 01010101~ 00110011+11001 ! Оое 00001111 =

Следовательно, данная функция истинна только при таких комбинациях значений истинности элементов А,В,С, которые соответствуют 3,4,5 и 7 столбцам базиса. Изображающим числом 1 является №1 =11...11, а Π— №О = 00...0. Заметим, что Х = У тогда и только тогда, когда №Х =№У и Х вЂ” + У тогда и только тогда, когда №У имеет единицы, по крайней мере, в тех разрядах, в которых № Х содержит единицы или (№ Х+№ У =№ 1) .

Нахождение явного вида булевой функции по изображающему числу

а) представление булевой функции в дизъюнктивной нормальной форме. Составим всевозможные, так называемые, элементарные произведения для трех элементов А,В и С и выпишем их изображающие числа по отношению к в 1А, В, С]:

ДНФ булевой функции является суммой элементарных произведений, причем суммировать

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

изображающее число булевой функции. Например,

00011101 =№(А е В е С)+№ (А ~ В е С)+№(А е В е С)+№ (А е В е С) =

=№(Ае В+ В~С)

6) представление булевой функции в конъюнктивной нормальной форме. Составим

всевозможные элементарные суммы для А, В, С, и выпишем их изображающие числа:

№(А+В+С) =11111110; №(А+В+С) =11101111;

№(А+ В+ С) = и ! ! !1О1; №(А+ В+ С) = ! ! О1! ! ! 1;

№(А+В+С) =11111011; №(А+В+С) =10111111;

№(А+ В+ С) = 11110111; №(А+ В+ С) = 01111111;

00011101 =№((А+ В+ С) (А+ В+ С) е (А+ В+ С) е (А+ В+ С)) =

=№ ((А + (В + С)) е (А+ (В+ С)) ~ ((А+ В) + С) ® ((А + В) + С)) =

=№((В+С)е(А+В)) =№(А®в+АсС+Се В) =№(А®В+ВеС)

Х(А,В,С,...),...,Х,(А,В,С,...)

Х( 1> 2»"' т)»"'71( 1> 2»'" п>)

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

Чтобы установить, зависимы или нет функции Л, 1 2,..., 1 „, нужно относительно в ~А,В,С,...] вычислить:

№1„(А,В,С,...) =4'*...~

Колонки набора (4) будем рассматривать как двоичные числа. Тогда, если в наборе содержатся все 2" чисел от 0 до 2" — 1, то функции независимы, в противном случае зависимы.

Распознанный текст из изображения:

Таблица №!

Рассмотрим следующий пример:

Найдем №Х и № У относительно в [А,В,С,...].

Таблица №2

О

' 0,1

1,1

1,0,1 0,1,1

0,0 0,1

0,0 1,1

1,1 0,1

№Х

1

При е=одля пары (Х,У) =(0,0) имеем (000)е О =О для левой части уравнения, а

0

Решение системы булевых уравнений

для правой (1,10) е 1 = 1' 0 ф 1; длЯ этой паРы УРавнение не УдовлетвоРЯетсЯ; длЯ паРы

1 0

(110) О =0; 0=0

уравнение

(1,О) (~ = 1) (ООО) 1 = О;

0 1

удовлетворяется. Запишем эту пару в таблицу 2 и т.д.

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

Х = Ае В+ АеВ

2 3

гу 0 1

О 0 0 0

0

~012 3

1 1 1 1 0 1 О 0 0 0 1 1

= (с,)

4 5 6 7

Составим таблицу:

о~2з

~ =АеВ+АеВ; №~ =1001

12 = А е В+ А е В, Ф 12 — 0110

В наборе нет чисел О и 3, поэтому ~;(А,В) 'и ~' (А,В)- зависимы. Найдем явный вид зависимости этих функций в форме ЕЯ, 1 ) = 1 . Отсутствие чисел О и 3 говорит о том. что Л и

не могут принимать значения нулевого и'третьего столбцов базиса в [Л,1 ) .

Положим, №ЕЯ, ~;) — 0110 — №Я е ~; + /; е ~;)

относительно в [Л, ~' ), откуда имеем' Л е ~; + 1, е ~', = 1 Действительно,

№~е№~;+~ е~; =1001е1001+0110е0110=1111 в ~А,В~.

Итак, для построения №Р' в базисе в 1Л,~' „,1„) необходимо в те разряды №Г, номера которых содержатся в наборе (~) поставить единицы, а в остальные - нули или, другими словами, 1'' принимает значение "истина" для всех возможных комбинаций значений истинности функций

и значение ."ложь" для комбинаций, которьгх вообще не может быть, поэтому Г(Л, ~2,..., ~„) = 1 для всех возможных комбинаций значений истинности высказываний А, В, С,...

Примеры:

Хе(А+В) = Ае В;

1. №(А+ В) = 0111; №Ае В = 0001;

№Х е 0111 = 0001 =~№Х = х001;

Х - либо О, либо 1,

отсюда: Х = А е В

2. Хе(А+В)~АеВ; №Х=хоох отсюда №Хе0111=000х

Х=.АеВ; АеВ; 0; АеВ+АеВ

Заметим, что уравнение в форме импликации всегда можно записать как соотношение эквивалентности:

Хе(А+В)+АеВ =1 или Х+Ае В+ АеВ =1

Общий подход к решению булевых уравк.ний рассмс;рим на следующем примере:

А + В е Х е '+ С е х' = А = Х е .' + В ~ Х -' С ~ А е В

1 2 3 4 5 6 7

1 0 0 0 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1

0 0 1 1 0 1 1 1 О 0 1 1 0 1 1 1

0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1