Автореферат (786271), страница 3
Текст из файла (страница 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) Заметим, что ге существует, поскольку при г = .и'. верно, что 'Р(Сн) > а, т.к. Сн З Ян и 'Г(Ян) =- а. Кроме того, при г =- р выполняется Г(Ср) < а при г =- р, поскольку Ср содержится в одном из полупрострапств вероятностной с мерой сх, которые образуют ядро Яр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
