Тема. Оптимальность плана транспортной задачи.

Метод потенциалов

Пусть одним из рассмотренных в п.2.6 методов найден опорный план, содержащий n + m - 1занятых клеток (в некоторых из них могут стоять нули). Поставим в соответствие каждому пункту отправленияА_i некоторое числоu_i(i = l, ..., m) и каждому пункту назначенияB_j- числоv_j(j = 1, ..., n). Эти числа назовем потенциалами, соответственно, пунктов отправления и пунктов назначения.

Вопрос об оптимальности опорного плана решает следующая теорема:

Теорема 5.Если для некоторого плана X*= (x_ij), (i = l, ..., m; j = l, ..., n) транспортной задачи выполняются условия:

1. u_i+v_j=c_ijдляx_ij> 0 (для занятых клеток),          (2.22) 2.u_i+v_j<c_ijдляx_ij= 0 (для свободных клеток),     (2.23)

то план X* является оптимальным. Из теоремы следует, что если для некоторой свободной клетки u_i+v_j<c_ij, то план не является оптимальным.

Отметим, что система (2.22) (m + n - 1) уравнений содержит (m + n) неизвестныхu_i,v_j , и потому, приравнивая одно из них, напримерu₁ к нулю, однозначно определим остальные неизвестные.

Для «улучшения» опорного плана (при невыполнении условия (2.23)) выбирают свободную клетку с max (u_i + v_j - c_ij )и строят для нее цикл пересчета (сдвига).

Цикломназывают замкнутую ломаную линию, все вершины которой лежат в занятых ячейках, кроме одной, расположенной в свободной клетке, подлежащей заполнению, а звенья параллельны строкам и столбцам, причем в каждой строке (столбце) лежит не более 2-х вершин. Всем вершинам поочередно приписывают знаки «+» и «-», начиная со свободной клетки. Далее, в свободную клетку помещают груз величинойλ, равной минимальному значению из всех чисел в отрицательных ячейках цикла. Во все положительные клетки прибавляетсяλ, из отрицательных - вычитаетсяλ(сдвиг по циклу). Нетрудно подсчитать, насколько изменится (уменьшится) стоимость перевозок при новом плане:

, где- сумма тарифов в положительных вершинах,- в отрицательных вершинах цикла. Новый опорный план снова проверяют на оптимальность с помощью системы уравнений потенциалов. Заметим, что в результате пересчета по циклу может оказаться число занятых клеток меньше, чемn+m-1(план называется вырожденным). В этом случае следует заполнить числом «0» пустую клетку, имеющую минимальный тариф, и не образующую с занятыми клетками замкнутого прямоугольного контура.

Пример 2.7.1.

Свойство 1.Если, для некоторого оптимального планаX*= (x_ij ), (i = l, ..., m; j = l, ..., n) транспортной задачи, выполняется условие:u_i+v_j=c_ijдляx_ij=0 (для свободных клеток), то, существует как минимум еще один оптимальный план, для которого общая стоимость плана перевозок остается прежней, поскольку(u_i+v_j) –c_ij = 0.

Пример 2.7.2.

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

Тема. Открытые модели тз и усложнения в ее постановке.

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

Открытая модель ТЗ решается приведением к закрытой модели. В случае (а), когда суммарные запасы превышают суммарные потребности, т.е. , вводится фиктивный потребитель (столбецВ_n+1), потребности которого. В случае (б), когда суммарные потребности превышают суммарные запасы, т.е., вводится фиктивный поставщик (строкаA_m+1), запасы которого.

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

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

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

Пример 2.8.1

Рекомендации приведения задачи к обычной ТЗ

При решении конкретных транспортных задач приходится часто учитывать некоторые дополнительные ограничения: невозможность (запрет) поставки груза из A_kвВ_i(блокировка), обеспечение пунктаВ_j, заданным количествомa_ijединиц груза за счет пункта отправленияA_iи т.п. В этих случаях поступают следующим образом:

Запрет перевозок груза из A_iвВ_jосуществляется занесением в клеткуA_i В_jчислаc_ij = М > 0(здесь и в последующем М - сколь угодно большое число). При оптимальном плане эта клетка будет блокирована.

По условию задачи требуется доставить из A_iвВ_jα_ijединиц груза. Следует занести в начале заполнения таблицы в клеткуA_i В_jчислоα_ij, считать ее в дальнейшем свободной (c_ij= М), а потребностиb_jи запасыа_iуменьшить наα_ij. Найденный оптимальный план новой задачи будет оптимальным и для исходной (с добавлениемx_ij=α_ij).

Если требуется из A_iвВ_jзавести грузx_ij ≥ 0- заданного числа, то уменьшают запасыа_iи потребностиb_jнаα_ijи находят оптимальный план новой задачи, по которому определяют и решение исходной задачи (x*_ij=α_ij+x_ij, гдеx_ij> 0 - компонента плана новой задачи).

Иногда требуется перевезти из A_iвВ_jгруза не более заданного объемаx_ij<α_ij. Тогда, чаще всего, поступают следующим образом: в таблицу вводят дополнительный столбецВ*_jс тарифами, равными тарифам столбцаВ_j, кроме клеткиA_i В_j, где полагаютc_ij= М. При этом потребности пунктаВ_jсчитаются равнымиα_ij, aВ*_j- равнымиb_j-α_ij.

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

Лекция 5.Определение метода Монте-Карло.

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

Возникновение идеи использования случайных явлений в области приближённых вычислений принято относить к 1878 году, когда появилась работа Холла об определении числа “пи “ с помощью случайных бросаний иглы на разграфлённую параллельными линиями бумагу. Существо дела заключается в том, чтобы экспериментально воспроизвести событие, вероятность которого выражается через число \pi, и приближённо оценить эту вероятность. До появления ЭВМ метод не мог найти широкого применения.

Случайные величины использовались для решения различных прикладных задач достаточно давно. Примером может служить способ определения числа «пи», который был предложен Бюффоном еще в 1777 году. Суть метода была в бросании иглы длиной L на плоскость, расчерченную параллельными прямыми, расположенными на расстоянии r друг от друга :

Алгоритм:

p=int_{0}^{pi} int_{0}^{l} sin{ \heta frac{1}{r \pi}dA d\ heta, где

" A - расстояние от начала иглы до ближайшей к ней прямой;

" \heta - угол иглы относительно прямых.

Этот интеграл просто взять: p=\frac{2L}{r\pi,} (при условии, что r>L), поэтому подсчитав долю отрезков, пересекающих прямые, можно приближенно определить это число. При увеличении количества попыток точность получаемого результата будет увеличиваться.

В 1864 году капитан Фокс, выздоравливая после ранения, чтобы как-то занять себя, реализовал этот эксперимент по бросанию иглы. При этом вращение плоскости применялось (и как показывают результаты - успешно) для того, чтобы уменьшить систематическую ошибку.

Создание математического аппарата стохастических методов началось в конце 19-го века. В 1899 году Релей показал, что одномерное случайное блуждание на бесконечной решётке может давать приближенное решение параболического дифференциального уравнения. Колмогоров в 1931 году дал большой толчок развитию стохастических подходов к решению различных математических задач, поскольку он сумел показать, как цепи Маркова связаны с некоторыми интегро-дифференциальными уравнениями. В 1933 году Петровский показал, что случайное блуждание, образующее Марковскую цепь асимптотически связано с решением эллиптического дифференциального уравнения в частных производных. После этих открытий стало понятно, что, стохастические процессы можно описывать дифференциальными уравнениями и, соответственно, исследовать при помощи хорошо на тот момент разработанных математических методов решения этих уравнений.

Сначала Энрико Ферми в 1930-х годах в Италии, а затем Джон фон Нейман и Станислав Улам в 1940-х в Лос-Аламосе предположили, что можно использовать связь между стохастическими процессами и дифференциальными уравнениями "в обратную сторону". Они предложили использовать стохастический подход для аппроксимации многомерных интегралов в уравнениях переноса, возникших в связи с задачей о движении нейтрона в изотропной среде.

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

Появление первых электронных компьютеров, которые могли с большой скоростью генерировать псевдослучайные числа, резко расширило круг задач, для решения которых стохастический подход оказался более эффективным, чем другие математические методы . После этого произошёл большой прорыв и метод Монте-Карло применялся во многих задачах, однако его использование не всегда было оправдано из-за большого количества вычислений, необходимых для получения ответа с заданной точностью. Отечественные работы по методу Монте-Карло появились в 1955-1956 годах. С того времени накопилась обширная библиография по методу Монте-Карло. В 1950-х годах метод использовался для расчётов при разработке водородной бомбы. Большую работу в развитии метода проделали сотрудники лабораторий ВВС США и широко известной в некоторых кругах корпорации RAND.

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

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

Пример.

Вычисление интеграла по двумерной области методом Монте-Карло

Автор алгоритма Ник Маслов. Функция вычисляет интеграл вида:

Мы будем считать, что область Dвписана в квадрат [a_x , b_x ]*[a_y , b_y ], тогда полагаем:

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

где (x_i , y_i ) пара независимых равномерно распределенных случайных величин.

На вход функции подается параметры ax,ay,bx,by, которые определяют квадрат [a_x , b_x ]*[a_y , b_y ] на плоскости, в который вписана областьD. В блок-схеме предполагается, что определена функцияF(x,y), интеграл от которой необходимо вычислить, а так же функцияD(x,y), которая принимает значение истина в случае, когда точка (x,y) принадлежит области интегрированияDи ложь в противном случае.

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

 Применение в физике

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

Алгоритм Метрополиса

Традиционно метод Монте-Карло применялся для определения различных физических параметров систем, находящихся в состоянии термодинамического равновесия. Предположим имеется набор W(S) возможных состояний физической системы S. Для определения среднего значения overline{A} некоторой величины A необходимо рассчитать overline{A}=sum_{S} A(S)P(S), где суммирование производится по всем состояниям S из W(S), P(S) — вероятность состояния S.

Динамическая (кинетическая) формулировка

Прямое моделирование методом Монте-Карло

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

Примеры прямого моделирования методом Монте-Карло:

 Моделирование облучения твёрдых тел ионами в приближении бинарных столкновений.

 Прямое Монте-Карло моделирование разреженных газов.

 Большинство кинетических Монте-Карло моделей относятся к числу прямых (в частности, исследование молекулярно-пучковой эпитаксии).

Квантовый метод Монте-Карло

 Квантовый метод Монте-Карло широко применяется для исследования сложных молекул и твёрдых тел. Это название объединяет несколько разных методов. Первый из них это Вариационный метод Монте-Карло, который по сути является численным интегрированием многомерных интегралов, возникающих при решении уравнения Шрёдингера. Для решения задачи, в которой участвует 1000 электронов, необходимо взятие 3000-мерных интегралов, и при решении таких задач метод Монте-Карло имеет огромное преимущество в производительности по сравнению с другимичисленными методами интегрирования. Другая разновидность метода Монте-Карло — это диффузионный метод Монте-Карло.

Можно сказать, что метод Монте-Карло—метод решения математических задач при помощи моделирования случайных величин. В общем случае точность работы метода пропорциональна корню числа «испытаний».

Специалисты различают понятия имитационного и численного моделирования: в первом случае моделируется поведение всех компонентов системы, во втором — только наиболее существенных. Метод Монте-Карло относится к имитационному моделированию, в котором при расчете какой-либо системы воспроизводится и исследуется поведение всех ее компонентов. Как же можно моделировать сложную систему, не зная строгих математических законов, которым она подчиняется? Ответ на этот вопрос содержится в назывании категории метода — «имитационный». Если поведение системы достаточно сложно и нет возможности описать его строгими математическими формулами, необходимо поставить определенное число экспериментов (т.н. случайных испытаний) с каждым из узлов этой системы для того, чтобы оценить, как они себя ведут. После определенного числа случайных испытаний мы получаем случайный вектор, в котором содержатся значения отклика узла системы на каждое испытание. Очевидно, что элементы этого вектора имеют некоторое распределение, описывающее поведение данного узла.

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

Рассмотрим еще раз один пример:

Бюффон сформулировал задачу о нахождении вероятности того, что брошенная на разграфленный лист бумаги игла пересечет одну из линий. Оказалось, что эта вероятность связана с числом p, что сделало возможным поиск этого числа вероятностными методами, т.е. методом Монте-Карло! Эта задача захватила умы многих исследователей. И сейчас, уважительно называемая теоремой, она имеет ряд интересных приложений. Попытаемся и мы посчитать число p, имея в своем распоряжении такой мощный инструмент, как компьютер. На листе бумаги начерчены параллельные прямые, находящиеся друг от друга на расстоянии L. На лист брошена игла той же длины. Какова вероятность того, что игла пересечет одну из прямых? 

Положение иглы на листе полностью определяется двумя независимыми случайными величинами: углом fи высотой h центра иглы (0 < h < L). Таким образом, чтобы смоделировать одно выпадание иглы, нам необходимо «разыграть» величины f и h. С величиной h все просто. Будем считать, что центр иглы с одинаковой вероятностью может оказаться на всем отрезке [0,L]. Таким образом, получим h=rnd*L, где rnd — случайная величина, имеющая равномерное распределение. Теперь займемся поиском угла? , но будем моделировать не сам угол, а значение его синуса: 0 <sinf<1. Чтобы моделировать синус равномерно распределенного углаf, нам необходимо подобрать для него функцию распределения, а это можно сделать на основе эксперимента. Представим, что мы 10000 раз бросим иглу, и каждый раз будем записывать значение sinfПодсчитаем число испытаний, в которых получено каждое значение. Имея компьютер, нам необязательно заниматься бросанием иглы на самом деле, достаточно написать следующую программу на Фортране:do i=1,10000 rnd(i)=sind(180*rand()) enddo С ее помощью мы получили интересующий нас случайный вектор.

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

do i=1,10000 sinf=abs((rnd*exp(rnd**1.051))/ exp(1.)-1) enddo Визуально оба распределения похожи. Будем считать, что распределение для sin f мы подобрали. Теперь необходимо решить, как нам определять, произошло ли пересечение или нет. По схеме (см. выше) мы можем определить расстояние k (длина иглы принимается равной L/2): k = L sin f / 2 Очевидно, что при выполнении условий (L-h) < k (для верхней линии) и h < k (для нижней линии) игла пересечет одну из прямых. Для моделирования все готово, и мы можем рассчитать методом Монте-Карло вероятность p того, что игла пересечет линию. Вместе с тем известно, что эта вероятность выражается следующим соотношением (доказательство этого факта я приводить не буду, желающие всегда могут обратиться за дополнительной информацией к математическим справочникам): p = 2 / пи Откуда пи = 2 / p Теперь у нас все готово для расчетов. Воспользуемся для этого программой на Фортране.real(8) sinf,L,pi,k,x,x1,p,j,h,rnd integer i,n write(*,*) «Input L» read(*,*) L write(*,*) «Input n» read(*,*) n j=1 do i=1,n rnd=fiboa() sinf=abs((rnd*exp(rnd**1.051)) /exp(1.)-1) k=(L/2)*sinf h= rand()*L x=L-h x1=h if(x.LE.k.OR.x1.LE.k) then j=j+1 endif p=j/i pi=2/p enddo write(*,*) pi end Результаты нашего моделирования приведены в таблице.

Вычисление числа пи  методом Монте-Карло
Число испытаний	Генератор rand()
1000	3,1104
10000	3,1363
100000	3,1523
1000000	3,1439

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

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

Отыскание возможных значений случайной величины Х (моделирование) называют «разыгрыванием случайной величины».

Рассмотрим пример, иллюстрирующий метод статистических испытаний:

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

из них в течение времени Травна 5/6. Приборы выходят из строя независимо друг от друга. При отказе хотя бы одного прибора вся система перестает работать. Найти вероятностьРотктого, что система откажет за времяТ.

Решим задачу аналитически и методом статистических испытаний.

 Аналитическое решение. СобытиеА(выход из строя хотя бы одного из трех приборов за время Т) и событиеА(ни один из трех приборов не выйдет из строя за время Т) - противоположные. ВероятностьР (А) =(5/6)³.Искомая вероятность

Теперь решим задачу методом статистических испытаний. Напомним, что при использовании данного метода возможны два подхода: либо непосредственно проводят эксперименты, либо имитируют их другими экспериментами, имеющими с исходными одинаковую вероятностную структуру. В условиях данной задачи «натуральный» эксперимент- наблюдение за работой системы в течение времени Т. Многократное повторение этого эксперимента может оказаться трудноосуществимым или просто невозможным. Заменим этот эксперимент другим.

Для определения того, выйдет или не выйдет из строя за время Тотдельный прибор, будем подбрасывать игральную кость. Если выпадет одно очко, то будем считать, что прибор вышел из строя; если два, три, ..., шесть очков, то будем считать, что прибор работал безотказно. Вероятность того, что выпадет одно очко, так же как и вероятность выхода прибора из строя, равна 1/6, а вероятность того, что выпадет любое другое число очков, как и вероятность безотказной работы прибора, равна 5/6.

Чтобы определить, откажет или нет вся система за время Т,будем подбрасывать три игральные кости (или одну кость три раза). Если хотя бы на одной из трех костей выпадет одно очко, то это будет означать, что система отказала.

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

P=m/n.

2.    Случайные числа.

Ранее было указано, что метод Монте- Карло основан на применении случайных чисел; дадим определение (равномерно распределенных) случайных чисел. Обозначим через Rнепрерывную случайную величину, распределенную равномерно в интервале (0, 1).

Случайными числами называют возможные значенияr_jнепрерывной случайной величины R, распределенной равномерно в интервале (О, 1).

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

Случайная величинаR* обладает свойством: вероятность попадания ее в любой интервал, принадлежащий интервалу (0; 1) равна длине этого интервала.

Функция плотностиf_R*(x)=1; интегральная функцияF_R*(x)=x; математическое ожидание М_R*(x)=1/2; дисперсияD_R*(x)= 1/12

3.    Разыгрывание дискретной случайной величины.

Пусть требуется разырать ДСВ с известным законом распределения:

X	x1	x2	…	xn
p	p1	p2	…	pn

Обозначим равномерно распределенную СВ в интервале (0, 1) через R, а ее возможные значения (случайные числа) -r_j.

Разобьем интервал [0, 1) точками с координатами р₁, р₁+р₂, , р₁+р₂+р₃, …, р₁+р₂+р₃+…+р_n-1наnчастичных интервалов . Длина_iкаждого из них равна вероятностир_i .

Далее поступаем так: выбираем из таблицы случайных чисел какое –либо случайное число   r_j, если оно попало в интервал_i, то разыгрываемая СВ приняла возможное значение х_i.

4.    Разыгрывание противоположных событий.

Пусть требуется разыграть испытания в каждом из которых событие А появляется  с вероятностью р и не появляется с вероятностью 1-р.

Заменим противоположные  события А и  А случайной величиной Х. Будем считать, что, если  значение СВХ равно 0, то произошлоА, если  СВХ приняла значение 1, то произошло событие А. Тогда разыгрывание противоположных событий сводится к разыгрыванию ДСВХ с известным законом распределения.

Пример: Разыграть 5 испытаний , в каждом из которых событие А появляется с вероятностью р= 0,35.

Заменим А и АДСВХ, которая имеет закон распределения:

Х	1	0
Р	0,35	0,65

  Получим два интервала. (0, 0.35) ;(0.35,1)

5.     Разыгрывание полной группы событий.

При разыгрывании полной группы несовместных событий поступают также, как при разыгрывании противоположных событий. События полной группы заменяют какими- либо числами, например последовательностью натуральных чисел 1,2,3…, тогда получаем ДСВХ с известным законом распределения, правило разыгрывания значений которой уже было рассмотрено.

Пример: События А и В независимы и совместны. Разыграть 6 испытаний, в каждом из которых, вероятность появления А равна 0,6, вероятность появления В равна 0,2.

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

Возможны 4 исхода:

Проверка: 0,12+0,48+0,08+0,32=1.

Заменим события числами 1, 2, 3, 4 с соответствующими вероятностями, получим ДСВХ с законом распределения:

Х	1	2	3	4
Р	0,12	0,48	0,08	0,32

Разобьем интервал (0, 1) на частичные интервалы (0; 0,12), (0,12; 0,6), (0,6; 0,68), (0,68; 1).

Выпишем 6 случайных чисел: 0,45; 0,65; 0,06; 0,59; 0,33; 0,7.

Получим значения ДСВХ: 2, 3, 1, 2, 2, 4. Определяем соответствующие события: А₂, А₃, А₁, А₂,А₂, А₄.

6.     Разыгрывание непрерывной случайной величины.

6.1.Метод обратных функций.

Пусть требуется разыuрать НСВХ, зная функцию распределенияF(x). Воспользуемсятеоремой:

Еслиr_i- случайное число, то возможное значение х_iразыгрываемой НСВХ с заданной функцией распределенияF(x), соответствующееr_i, является корнем уравнения

F(x_i) =r_i.

На основании данной теоремы сформулируем правило разырывания значений НСВХ, знаяя ее функцию распределения F(x):

Необходимо выбрать случайное число r_i, приравнять его функции распределения и решить относительно х_iуравнение:F(x_i) =r_i .

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

Известно, что функция распределения при показательном законе имеет вид

Составим и решим относительно х уравнение: F(x)=r_j, откуда непосредственно получаем х.

Выбирая случайные числа r_i , подставляя их в полученную явную формулу, разыграем возможные значения НСВХ.

Если известна плотность распределения НСВХ, f(x) , то для разыгрывания значений НСВХ , решают уравнение:

6.2.Метод суперпозиции.

Пусть функция распределения разыгрываемой НСВХ задана линейной комбинацией двух функций распределения: F(x)=C₁F₁(x) +C₂F₂(x) , гдеC₁>0,C₂>0.

При х-> \infty каждая из функций распределения  стремится к единице, поэтому C₁+C₂=1.

Введем вспомогательную ДСВZс законом распределения:

Z	1	2
p	C1	C2

Выберем два независимых случайных числа r₁иr₂. По числуr₁разыграем возможное значениеZ. Еслиz=1, то возможное значение х найдем из уравненияF₁(x) =r₂, а еслиz=2, то из уравненияF₂(x) =r₂.

__