Главная » Просмотр файлов » Автореферат

Автореферат (786271), страница 4

Файл №786271 Автореферат (Оптимизация стохастических линейных относительно стратегий систем по квантильному критерию) 4 страницаАвтореферат (786271) страница 42019-03-12СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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) Для решения полученной задачи применяется алгоритхл, осноьанный л|а методе динамического программирования и методе ветвей и границ.

Характеристики

Список файлов диссертации

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6367
Авторов
на СтудИзбе
309
Средний доход
с одного платного файла
Обучение Подробнее