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

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

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

Текст из файла (страница 3)

Тогда, задача первого этапа имеет следук>щий вид: р =- пни[с„и + р„(и) ~, и„=- агд ппп[с0 и + р (и)). иен ие~1 (7) Далее задача в апостериорпой постановке сводится к задаче смешанного целочисленного линейного программирования. Согласно доверительному методу, предложенному А.И. Кибзуном, В.В.

Малышевым, задача (7) эквивалентна следующей задаче Д, =- ппп ппп1с0и+ впр[а~~(х)и+ Ф(и,х))), хек (й„.,З,) = агд ппп 1с0и+ впр[а, (х)и+ Ф(и,х)~), аекже ~а хек (8) где Ф(и,х) определяется согласно (6), Я Е 2=„-- доверительное множество из Д семейства доверительных множеств У;, = (Я Е У': 'Р(В) > о), У' - борелевская сигма-алгебра, вероятностная мера 'Г соответствует дискретизированному распределению вектора Х.

Если зафиксировать доверительное множество Я Е У„и рассмотреть эквивалентную двойственную задачу для подзадачи (6), то есть Ф(и,х) = шах((аз(х) — А2(х)и) и), ьеГ где о Е В.' — вектор двойственных переменных, 1 — выпуклый многогранник вида à — (и: В о < с~, о; > О, г — 1, в1, получим Ф~(В) — ш1пФо ~~+- впр[пГ'(х)п+ шак((пз(х) — А2(х)п)'~Н)- аеь уея ахеи (9) Пусть векторы с~ и матрица В таковы, что множество Г = (и Е В': Втп < с~, о, > О, г = 1, з)- (10) Ю(Я) — тшп(с~~и+ впр[а, (х)и+ шах((аз(х) — А~(х)и) ~Я~. (11) ие~~ ~еЯ компактно. Поскольку 1' — ограниченное множество согласно теории двойственности и функция (аа(х) — А2(х)и) о линейна.

по ю для всех х и и, то ее максимум достигается в вершинах о~, 7' = — 1, 1, многогранника Ъ'. Поэтому задача (9) трансформируется в задачу --11-- Учитывая, тто после дискретизации меры случайный вектор Х принимает лишь конечное число значений х~, Л: = 1, К, то задача (11) превращается в задачу ~® = пнп~сд и+ тпах тпах[а, (х') и+ (аа(х') — А2(х")и) о'))-, (12) пей г — дй 1 — 17 где множество Я состоит из векторов х', г — 1, Л. Поскольку функция, стоящая под максимумом, линейпа по и, а максимум находится по конечному набору векторов 1х")~..~, (и'ф~, то функция, стоящая в фигурных скобках, оказывается кусочно-линейной и выпуклой по и Е Г. В случае если Г -- выпуклый многогранник, задача (12) превращается в задачу линейного программирования (13) ~~ -+ ш1п иеГ.е)0 при линейных ограничениях сти+ а1(х")и+ (из(х") — А ( -Я)и) ю3 ( 4, г = 1, Л, 7' = 1,,7.

(14) Ранее множество Я было зафиксировано, РЯ > а. Выберем оптимальное множество Я„в задаче (8). С этой целью введем булевы переменные, характеризующие принадлежность точек т~ доверительному множеству Я по правилу: ,ь / 1, еслих ЕЯ., О иначе. Обозначим р1, = Р(Х = т~) = 1(К, й = 1, К. Пусть известна величина у ) — оо, являющаяся оценкой снизу функций .у < а~(т~) и + (аз(х~) — А2(х~)и)~и~., й = 1, К, 7 = 1, 7. Рассмотрим программирования задачу смешанного целочисленного линейного (15) — ш1п иЕи,бь....бк.е>0 при ограничениях со и + у + К ~а, (х ') и + (аз(х ) — А2 (х") и) и' — у] < 6.

1 — 1, К. з — 1, 1. к ,,'~,барк > а, 6~ е (О, Ц, 1: == 1, К. Верно следующее утверждение. ТЕОРЕМА 1.3. Двухотапная задача (7) в апостериорной постановке эквивалентна задаче (15) — (16) смешанного целочисленного линейного программирования. Во второй главе рассматривается двухэтапная задача стохастического программирования следующей структуры. Пусть случайный вектор Х с реализациями х Е В," имеет нормальное распределение Л'(О, 1).

Введем функцию потерь, зависящую от стратегии первого этапа и Е Гэ С В. и реализаций х случайного вектора Х и учитывакнцую оптимальную стратегию второго этапа у: Ф(и,х) = сои+ х~Л~и+ 1п1 с1у, реУ(и,х) (17) где Х(и:х) =- Ь ~ У: х'Аг,и+с',и+6'у ~ азх+А.,~ = 1,з) (18) У = 1д ~= В~': д > О, у = 1, т11, со и с1 — заданные детерминированные вектор-столбцы размерности т и т1, соответственно, матрицы А1 и Аа, имеют размерность (и х т); с2;, 6, и аа;— вектор-столбцы размерности т, т1 и и, соответственно, а д; — константа. Отметим, что часть матриц А2; и векторов аг;, г =- 1, з, определяющих множество эЭ(и, х) допустимых стратегий второго этапа у, могут быть нулевыми. И тогда часть ограничений с теми же номерами г, соответствующими этим матрицам и векторам в множестве эЭ(и, х), будут детерминированными.

Пусть векторы с1 и 6,, г = — 1, з, таковы, что множество (19) - 12-- Получеппу1о задачу смешанного цело |исленпого линейного программирования предлагается решать с помощью стандартных программных пакетов оптимизации с применением приемов для сокращения перебора при нахождении оптимального множества э',, в частности с использованием понятия ядра меры. Ядро меры уровня а при больших а в случае дискретного распределения совпадает с выпуклой оболочкой всех точек из распределения случайного вектора Х за исключением крайних точек.

Поэтому в случае квазивьшуклости целевой функции по х достаточно перебрать только крайние точки из множества всех возможных значений. Стоит отметить, что при фиксированном д~,/с — 1,К, задана (15) — (16) представляет собой задачу линейного программирования. В случае если в критерии задачи вместо матрицы Л2(Х) рассмотреть просто случайный вектор Х, то задача (16) оказывается принадлежащей классу портфельных;задач, рассматриваемых в многих работах, в частности, в монографии А.И. Кибзуна и Ю.С. Кана.

Основным результатом главы является следующая теорема. ТЕОРЕМА 1.4. Многозтапная задача стохастического программирования в априорной постановке вида (5) для дискретного распределения Гк(х) специалы*ого вида,. сгенерированного на основе плотности р(х), эквивалентна в смисле определения 1.1 задаче смешанного целочисленного программирования (") () В главе приводятся результаты численных расчетов, демонстрирущие применение разработанного алгоритма. компактно, где д' 1 В— Ьт а ограничения на допустимые стратегии и первого этапа являются линейными: Г=1иб й.: А„и< 6„1,, Р„.(и) = Р(Х: с~~и+ Х Аги+ Ф(и.,Х) < р), (20) где Р— вероятностная мера, порожденная распределением ЛГ(0, 1), 1п1 с, д, У(и., Х) ~ Я, ф(, Х) ре~ (и,х) оо, У(и,Х) = Я, (21) и функцию квантили р .(и) = ппп~р: Р„(и) > а), а Е (О, Р*), (22) где Р"' = впр Р1Х: У(и, Х) ф О).

реп Сформулируем задачу первого этапа р = — 1п1:р„(и), и = агрппп р (и). иеь' иеУ (23) Согласно доверительному методу, задача (23) эквивалентна следующей задаче р — 1Ы ф(Ь', и), (и, Ь' ) — аги пш~ ~д(Ь', и), иеУ,ЯеУ,~ иеКЯеУ' (24) где введена функция максимума 6(Я, а) = с~~и + впр~х~Аги + Ф(и, х)), (20) а Я вЂ” доверительное множество. При этом выполняется р = р, и = й,, причем под допустимым решением задачи (23) понимается пара (и, р (и)), для которой р .

< р (и), и Е Г, а для задачи (24) тройка (и, Я, ~~(Я, и)), для которой р < ~(Я. и), Я Е У', и Е Г. где вектор 6 имеет размерность йг, матрица А„имеет размерность й~ х т, причем являются такими, что У вЂ” компакт. Рассмотрим функцию вероятности: ---14-- Рассмотрим подзадахлу (21), для которой зквивалсптпая двойственная задача с вектором двойственных переменных и Е Л' будет иметь вид: Ф(и.,х) =- вира (и,х)и, (26) иел' где атх итАтх+ 1~1 сти аз,х — и А2,х + д, — с2,и т,т т, т а(и,х) = Ат(и)х+ Ь(и) =- (27) ат итАт 31 21 А (и)= ат, тАт Зз 2и 6~(и) = (и1 с21и, " ав с2,и), - выпуклый ограниченный многогранник, введенный выше в (19). Пусть и',1 = 1,,1 -- вершины многогранника Ъ', являющегося выпуклым компактом. Тогда в связи с линейностью по и функции в (26) ее максимум на Г будет достигаться в вершинах Ъ': Ф(и, х) = тпах а (и, х) и1.

1Е1,2 (28) Рассмотрим подзадачу задачи (24) для фиксированного множества Я, в качестве которого выбирается доверительный шар Ян с радиусом Л и центром в нуле, Р(Яд) = о. Для простоты дальнейших обозначений далее будем использовать р = р, Л = Л, где р~ — радиус ядра вероятностнолй меры уровня а для случая нормального распределения случайного вектора Х, а ядро вероятностной меры представляет собой множество, содержащееся во всех полупространствах меры больше, чем о. 1 асс11лотРи~л слсДУюлЦУю заДа'1У Дли шаРа ~х с ЦснтРом в нУлс и псРсмснным радиусом г Е ]р, Л]: л~~„— лп1 ф(Я„, и)., и„— аги ппп файф,, и), иео иЕГ (29) где функция ф1(Ь"„, и) определяется согласно (25) для множества Я,, т.е.

лр(Ях, и) — сти+ впр[х~А1и+ Ф(и, х)]. хЕЯ„ (30) Поскольку функция под знаком апр в (30) согласно (27) и (28) кусо шолинейна и выпукла по х для каждого и Е Г, а шар Я, — компактное множество, то знак впр можно заменить па шах. Таким образом, функция лрф„, и) в задаче (29) преобразуется к виду ф(Я„, и) = сти + п1ах(х~А1и+ Ф(и, х)]. хеч„ (31) 1 ( ~),~ 1" 'ехр( — 1~,,2)й о (32) где Г( ) — гамма-функция. Следующая лемма устанавливает связь между решением задачи (24) и его верхней и нижней оценками. ЛЕММА 2.6. Для решения задачи (ЗД имеет место следующая двусторонняя оценка у' „<~ <р ( л„)<~юл„., (33) причем,.

~~я, — фр„— ~ О при а — ~ 1. Улучшим верхнюю оценку оптимального значения функции квантили о,, выбрав значение г Е ~р, Л) в задаче (29) такое, что р„< ф„< ~п. Рассмотрим для этой цели следующее множество С„= ~х: с<~~и + ххА1и, + гпах а~(и„, х)и~ < 6„) ~=па (34) и определим такое ге, что (35) Заметим, что ге существует, поскольку при г = .и'. верно, что 'Р(Сн) > а, т.к. Сн З Ян и 'Г(Ян) =- а. Кроме того, при г =- р выполняется Г(Ср) < а при г =- р, поскольку Ср содержится в одном из полупрострапств вероятностной с мерой сх, которые образуют ядро Яр.

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

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

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