Автореферат (786271), страница 4
Текст из файла (страница 4)
Следующая лемма устанавливает соотношение между вероятностными мерами правильного многогранника С„, симметричного относительно нуля, с з' гранями, касающимися шара. Я„, и произвольного мпогогра.пника С, с тем же числом граней и содержащим Я,. ---15-- Исследуем задачу (29) с функцией максимума (31). Верно следующее утверждение. ЛЕММА 2.4. Задача (29) является задачей выпуклого программирования и и„существует, для всех г Е ~р, П1. Следующая лемма устанавливает свойство критериальной функции. ЛЕММА 2.5. Функция ф~, монотонно возрастает и непрерьина по х' е (р, И1. Рассмотрим теперь задачу (31) для двух случаев г — р и г — Л, где р — радиус ядра К гауссовской меры Г, а Л вЂ” радиус доверительного шара Ян Е У ., 'Г(Ян) — а.
Для нормального распределения Л (О, 1) радиус Л может оыть найден как решение трансцендентного уравнения: --16-- ЛЕММА 2.7. Если случайный вектор Х имеет распределение Л (О, т), то 'Г(С,) < 'Г(С„) длл любого г > 0 и любого,У > тт + 1. Для размерности п > 2 справедлива следующая теорема. ТкоремА 2.1 Для задачи (29) справедливы следтуютцие 'утвержден»»л Й го < т»,, где го = лп1',е~р,л1Сг: 'Г(С,) > а):, (тт) стттцествтует г Е [то, Й) такое, что Р(С,) > а и »р„<»р (и,) < у»,„< т~»тт, 7 = К 'т~(Х вЂ” т), который имеет распределение Л(0, т').
При такой замене переменных Х на У ограничения, задающие множество 7(и, х), преобразутотся в множество тт(и, г), ограничения которого будут иметь точно таку»о же структуру, как и огралплчсния, описываюплие множество 7(и, х). Таким образом, случай Х Л (тп» К) сводится к случаю Х Л (О, т'), рассмотреппому вьппс. Далее предлагается вычислительный алгоритм решения задачи (29). Рассмотрим вначале способ поиска точки го, используя алгоритм дихотомии в следующей модификации. Выберем точки г — р и г — т»., для которых Р(Ср) < а и Р(С»т) > а. Рассмотрим точку г — (р +»т»)/2 и найдем Р(С,) (алгоритм вычисления меры Р(С„) приводится далее).
Если Р(С,) > а, то оставляем точки р и г. Если жс Р(С„) < а» то оставляем точки г и тт'. И так долее производим деление пополам текущих отрезков неопределенности. Алгоритм сходится, поскольку 'Г(Ср) < а и Р(Стт) > а. Скорость сходимости алгоритма равна 1/2~, где й количество делений отрезков неопределенности пополам. Предложим теперь алгоритм вычисления Р(С,.) для произвольного т »= [р,т»»1. С этой целью дискретизируем меру так, как это предложено в первой главе. Пусть х»,, й = 1,К, -- точки, сгенерированные на основе плотности нормального распределения Л(0, 1).
Пусть р», = 1/К вероятностная мера, приписанная к точке хт, 1» К. Таким образом, получаем меру Р, аппрокси»»лирующую гауссову меру Р. Заменикл меру 'Г на меру Г при вычислении Р(С„). Пусть для некоторого г»= [р, Й1 найдены и„и т»», в результате решения задачи выпуклого программирования тт», — тшп тт»(Ь;» и), и,„— агн пйп ту(Ь'„, и).
,ес» и о (З6) Для решения задачи (36) можно использовать какие-либо эффективные методы выпуклого программирования, например метод внутренней точки. (ттт) если т'» < г», где гл,г» Е [го, й) и 'Г(С„„) > а, Р(С„) > а, то 'р»» т»»г» < 4 г Для более общего случая, когда случайный вектор Х имеет распределение Л» (тп, К), где К вЂ” невырожденная ковариационная матрица,, рассмотрим вектор - 17-- Найдем вероятностную меру 'Р(С„) множества С, = (х: сои, + х~А1и„+ таха (и,, х)и~ ( Ц.)- ~ =-1.,7 Поскольку Я„С С„, то исключим из рассмотрения точки х~ Е Я„. Отметим, что вероятностная мера Рф„) множества Я„известна и вычисляется по формуле (32), в которой нужно заменить Л на.
г, а о на получаемую меру Р(Ь'„). Тогда Р(С ) — Р(С ~Я ) + Р(Я ) — Р(С ~Ь ) + Р(Ь ) При этом мера 'Р(С,.~гЬ",) может быть найдена за счет перебора лишь точек х~, лежащих вне Ь;. Таким образом, вычисление вероятностной меры 'Р(С,.) множества С"„резко упрощается. По сути описанная процедура вычисления 'Р(С,) является реализацией метода Монте-Карло, из которой исключены точки, принадлежащие шару Ь'„.
Алгоритм решения задачи основан на том факте. что случайный вектор Х имеет нормальное распределение, но класс распределений случайного вектора может быть расширен, в частности, вектор случайных факторов может иметь сферически симметричное распределение. В этом случае почти все приведенные выше рассуждения остаются верными., изменяются только размеры доверительного шара и ядра вероятностной меры.
Основная трудоемкость предложенного алгоритма заключается в процедуре подсчета вероятностной меры многогранного множества. Однако за счет дискретизации меры нормального распределения и введения процедуры сокращения перебора точек, которые образук~т доверительное множество, удается сократить время счета.
В главе приводятся результаты численных расчетов, демонстрирующие применение разработанного алгоритма. В третьей главе рассматривается задача выбора оптимальной трассы с учетом случайной стоимости работ. Предполагается., что требуется проложить трассу между начальным и конечным пунктами., при этом стоимость прокладки трассы различна на каждом участке пути в связи с неоднородностью грунта, особенностями рельефа, естественными препятствиями и т.д. Оптимальной является трасса с наименьшими суммарными затратами по прокладке. Весь процесс прокладки трассы разделен на ряд последовательных этапов.
Существует множество трасс., каждая из которых связана с определенной стоимостью работ и характеризует управление процессом прокладки трассы. Решение поставленной задачи осу ществляется следук>щим образом, Рассматривается участок местности для предполагаемой прокладки трассы. На карту местности накладывается ~етка разбиения на мелки~ прямоугольники, где г =- 1, Л, ~ =- 1, ЛХ вЂ” число частей, на которые делятся стороны сетки разбиения по горизонтали и по вертикали соответственно, а.;-- стоимость прокладки трассы по горизонтали от точки (г, 7) до точки (г + 1, Я; 6; — стоимость прокладки трассы по вертикали от точки (х,~) до точки (г,~ + 1); с, — стоимость прокладки трассы --18-- по диагонали от точки (г, /) до точки (г + 1, ~ + 1).
Если г = 1, то ал,, — — сл, — — 0; а если г = ЛХ, то Ь," =- с,- = О. Текущее значение стоимости работ по прокладке Д трассы до точки х,, „= со1(гг,, гг,) обозначим через д~, причем Иг. ,> О. Рассмотрим динамическую систему, описывающую изменение текущего положения точки на сетке разбиения и текущее значение стоимости работ: г~.,л =гг,.+иг, гл —— О, гг,.+л — р + 1 — ил, + иг.„лгг,, гл — О, йл.,; =- Ю~ + д(гл, г~„., ил, ил.), 4 =- О., (37) если иг,. = 1,ггл = О,. если иг„. = О, если иг, = 1, ггл, = 1. а,,„ 1глдл ~ д(гл-, р, ил-, .ил-)— (38) Таким образом, тскуплсс положение системы полностью описывается вектором текущего состояния системы: ~л, — со1(г~., 7д, Й~), Л: — 1, Л + 1.
Суммарная стоимость работ по прокладке трассы от начальной точки хл л до конечной точки хд+л д.г л равна Иу.~.л. Предположим., что параметры а,, „. б,,~„, с,„,, Л: = 1, Х из (38), определяющие добавки к текущей стоимости в зависимости от управления,— случайные величины, зависящие от непредсказуемых локальных особенностей местностлл. Предгюлагается, что параметры а;, 6;г, с, независимы и имеют нормальное распределение алг ~(лгцг: О; ) > 1элг ~(ггглг: Огг) слл лч( лги~ ~лг) Поскольку стоимость прокладки трассы случайна, рассмотрим в качестве критерия оптимальности квантильный критерий: (39) где гг, — О, г., р — О, ЛХ вЂ” координаты точки на к — м шале по горизонтали и по вертикали соответственно; Й вЂ” номер шага,, Й вЂ” 1, Х; Х вЂ” общее число шагов, плах(г, ЛХ) < Х < г + Х1; хл л — — со1(гл, гл), где гл = О,~л —— О, — начальная точка; хулл уел = со1(гу+л,~улл),где гулл = Л, уу+л = Л(, — конечная точка; Ь иг,, ггг, — управление, которое выбирается из ллножества У вЂ” (О, Ц допустимых управлений, ил,,ггг, Е Г; д~ — стоимость прокладки трассы до Й вЂ” го участка включительно: д(ггч 7л„ил,, иг,) — добавка к текУщемУ значению стоимости Работ.
Система (37) описывает движение по трем направлениям сетки разбиения, а применение особой комбинадии управлений ил,,ггл, позволяет описать движение посредством всего двух управляющих переменных иг,, ил, Е (О, 1). В зависимости от выбранного управления добавка к текущей стоимости трассы будет определяться величиной: --19-- Задача оптимизации заключается в следующем (и" Н, и*(.)) — агд ппп р„(и(.), и( )). и,(-,), ю,(~,)е(0,1),л=л.х (40) В работе получен детерминированный эквивалент стохастической задачи [илу+1]а = л~х+1 + т~х ~йж+1, где (41) Для решения полученной задачи применяется алгоритхл, осноьанный л|а методе динамического программирования и методе ветвей и границ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
