Методы и алгоритмы решения задач стохастического линейного программирования с квантильным критерием тема диссертации и автореферата по ВАК РФ 05.13.01, доктор физико-математических наук Наумов, Андрей Викторович

• Наумов, Андрей Викторович
• доктор физико-математических наук
• 2012

Оглавление диссертации доктор физико-математических наук Наумов, Андрей Викторович

Введение

1 Одноэтапные задачи стохастического линейного программирования с квантильным критерием. Свойства и методы решения.

1 1 Постановка одноэтапной задачи стохастического линейного программирования с квантильным кри1ерием

12 Свойства одноэтапной задачи стохастическою линейного программирования с квантильным критерием

1 3 Методы решения одноэтапных задач стохастического линейного программирования с квантильным критерием

1 4 Выводы по главе

2 Алгоритмы решения одноэтапных задач стохастического линейного программирования с квантильным критерием.

2 1 Алгоритм 1 поиска гарантирующего решения, основанный на параметризации доверительного множества радиусом вписанного шара

2 2 Алгоритм 2 поиска гарантирующего решения, основанный на трансформации доверительного множества методом двойственных отсечений

2 3 Алгоритм поиска точного решения в случае дискретного распределения случайных параметров методом сведения к эквивалентной задаче линейного программирования смешанного типа

2 3 1 Сведение к задаче смешанного линейного программирования 61 2 3 2 Алгоритм решения полученной задачи смешанного линейного программирования

2 4 Результаты численных экспериментов

2 4 1 Пример

2 4 2 Пример

2 4 3 Пример

2 5 Выводы по главе

3 Двухэтапные задачи стохастического линейного программирования с квантильным критерием. Свойства и методы решения.

3 1 Постановка двухэтапной задачи стохастического линейною программирования с квантильным критерием

3 2 Свойства двухэтапной задачи стохастического линейного программирования с квантильным критерием

3 3 Методы решения двухэтапных задач стохастического линейного программирования с квантильным критерием

3 4 Выводы по главе

Алгоритмы решения двухэтапных задач стохастического линейного программирования с квантильным критерием в случае непрерывного распределения вектора случайных параметров.

4 1 Сведение двухэтапной задачи стохастического линейного программирования с квантильным критерием к одноэтапной задаче

4 2 Алгоритм поиска гарантирующего решения многопериодной двухэтапной задачи стохастического линейного программирования с квантильным критерием

4 3 Результаты численных экспериментов

4 3 1 Результаты решения двухэтапной задачи стохастического линейного программирования с квантильным критерием ангори!мом 2 в случае равномерною распределения вектора случайных парамефов

4 3 2 Результаты решения многопериодной двухэтапной задачи квантильной оптимизации

4 4 Выводы rio главе

Алгоритмы решения двухэтапных задач стохастического линейного программирования с квантильным критерием в случае дискретного распределения вектора случайных параметров.

5 1 Модификация алгоритма поиска гарантирующих решений, основанного на методе двойственных отсечений, для случая дискретного распределения вектора случайных параметров

5 2 Решение двухэтапной задачи методом сведения к детерминированной задаче линейного программирования смешанного типа

5 3 Результаты численных экспериментов

5 3 1 Результаты решения двухэтапной задачи модификацией алгоритма основанного на методе двойственных отсечений

5 3 2 Резупыа1ы решения двухэ!апной задачи, полученные путем сведения ее к задаче линейного программирования смешанного типа

5 4 Выводы по главе

6 Прикладные задачи стохастического линейного программирования с квантильным критерием.

6 1 Оптимизация функционирования летного парка авиакомпании

6 11 Постановка задачи 140 6 12 Математическая модель функционирования летного парка авиакомпании

6 13 Алгоритм решения задачи

6 14 Результаты численного эксперимента 157 6 2 Оптимальное бронирование фрахта логистической компанией пользующейся услугами авиаперевозчика

6 2 1 Описание модели

6 2 2 Исследование свойств модели

6 2 3 Алгоритм решения задачи

6 2 4 Результаты численного эксперимента

6 3 Оптимизация бюджета госпиталя

6 3 1 Постановка задачи

6 3 2 Поиск гарантирующего решения доверительным методом 168 6 3 3 Поиск гарантирующего решения методом сведения к односнапной задаче

6 3 4 Результаты численною эксперимента 171 6 4 Двухэтапная задача квантильной оптимизации инвестиционного проекта

6 4 1 Описание задачи

6 4 2 Математическая постановка задачи

6 4 3 Алгоритм поиска гарантирующего решения задачи

6 4 4 Результаты численного эксперимента

6 5 Выводы по главе

Введение диссертации (часть автореферата) на тему «Методы и алгоритмы решения задач стохастического линейного программирования с квантильным критерием»

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

Исторически теория оптимизации вероятностных критериев качества возникла как специальный раздел теории задач стохастического программирования с вероятностными ограничениями, интенсивно развиваемой примерно с конца 50-х годов прошлого столетия благодаря исследованиям

А. Чарнса, В. Купера, Г. Саймондса [139,140,230], Миллера и Вагнера [194],

Дж. Вайды [238], С. Гарстки [162], Ж. Дупачевой [153-155], П. Калла [166-168], 5

B.В. Колбина |182[, Г. Майера |167], А. Прекопы [208—213], Дж. Сенгупты |228|,

C. Уолласа [168], Т. Шантая [217,231], Д.Б. Юдина [114-116,118]. Квантильный критерий впервые введен в рассмотрение С. Катаокой [173]. Развитие теории и практики решения задач с квантильным критерием связано с именем Э. Райка [102-105] и его учеников Р. Леппа [68,69,183], Э. Тамм [108,109,232] и Э. Юби [112, 113]. Эта школа математиков по сути заложила фундамент теории вероятностной и квантильной оптимизации, исследовав основные свойства функции вероятности и квантили. Дальнейшее развитие эта теория получила в работах российских исследователей Ю.С. Кана [33, 174], К.А. Карпа [70,71,178], А.И. Кибзуна [33,40-43,72,174,178], В.В. Малышева [40-43,70-72,178]. Необходимо также отметить вклад Ю.М. Ермольева [12,158], К. Марти |191, 193], В.И. Норкина [74, 101, 158, 201|, Н.В. Роенко [101|, С.П. Урясьева [110,234-237].

Современное состояние теории и практики решения задач вероятностной оптимизации связано с именами С. Ахмеда [188,189], П. Беральди [127-130], С. Вогела [241], Д. Денчевой [229], Г. Калафайоре [138], М. Камни [138], Ю.С. Кана [10, 20, 25, 33, 174], А.И. Кибзуна [29-33, 35, 37, 44, 45, 47, 48, 59, 65, 174, 177, 181], Дж. Людке [187-189], К. Марти [192], А. Немировского [198,199], В.И. Норкина [101,201], А. Прекопы [152,214,215], А. Ружински [128-130,152,202,203,214,223,224,229], С.П. Урясьева [181,237], А. Шапиро [198,199,214,224,229].

Специальная техника решения задач вероятностной оптимизации с дискретным распределением случайных параметров отражена в работах П. Бералди [128, 130], Б. Визвари [240], Д. Денчевой [152], Дж. Людке [188, 189], Д. Моргана [195], Н. Нойана [202, 203], А. Прекопы [152, 208], А. Ружински [128, 129, 129, 130, 152] , А. Саксена [225], С. Сена [227], М. Таннера [233|. Иссследования задач с дискертным распределением вектора случайных параметров является важным направлением в стохастическом программированиии. Во-первых, это связано с традиционным использованием в стохастическом программировании сценарного подхода.

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

Отдельно нужно выделить современную российскую школу вероятностной и квантильной оптимизации А.И. Кибзуна [14,21,22,29-39,43-49, 59-65,170,174-177,181],и его учеников Ю.С. Кана [10,16-26,33,34,170,171,174], Б.В. Вишнякова [29,31,32], В.А. Ефремова [14], Е.А. Кузнецова [35-38,176], В.Ю. Курбаковского [39,175], E.JI. Матвеева [44-47], В.Л. Мирошкина [48,49,73],

A.Н. Сотского [60,61], Г.Л. Третьякова [62-64], а также A.B. Сысуева [25]. В монографиях А.И. Кибзуна и Ю.С. Кана [33, 174] систематически изложена теория вероятностной и квантильной оптимизации и продолжено развитие предложенного ранее В.В. Малышевым и А.И. Кибзуном [72] обобщенно-минимаксного подхода, получившего название доверительного метода. Суть подхода заключается в замене исходной задачи квантильной оптимизации на эквивалентную минимаксную задачу, где внутренний максимум от функции потерь берется по всем возможным значениям случайных параметров из некоторого доверительного множества соответствующей вероятностной меры, а внешний минимум по стратегии оптимизации и всем доверительным множествам этой вероятностной меры. В работах Ю.С. Кана [23,25,33,34,170,171,174], А.И. Кибзуна [33-35,38,45,51,52,170,174],

B.В. Малышева [72], Г.Л. Третьякова [62-64] исследованы качественные свойства квантильного и вероятностного критериев. Методы построения асимптотически точных решений задач квантильной оптимизации отражены в работах Ю.С. Кана [16, 17, 33, 174], А.И. Кибзуна [33, 39, 47, 174], В.Ю. Курбаковского [39], E.J1. Матвеева [46, 47]. В основном эти методы построены на основе процедуры стохастической аппроксимации, требующей построения квазиградиента функции квантили. Для этого требуется находить оценки значения функции квантили ввиду отсутствия возможности получения ее явного вида. Способы нахождения оценок функций вероятности и квантили рассмотрены в работах Б.В. Вишнякова [32], В.А. Ефремова [14], Ю.С. Кана [33, 174], А.И. Кибзуна [14, 32, 33, 46, 174], Е.Л. Матвеева [46]. Развитие квазиградиентных методов решения задач квантильной оптимизации сопряжено со значительными вычислительными затратами, которые часто становятся непреодолимыми. Для борьбы с этими трудностями в последнее время усилиями А.И. Кибзуна [30,44] начал развиваться подход, связанный с использованием методов параллельных вычислений в подобных процедурах.

Традиционно в теории стохастического программирования класс задач, обладающих линейной структурой, выделялся особым образом в первую очередь в сил}' большого количества прикладных задач в основном экономического характера, удовлетворительно описываемых такими моделями. В теории стохастического линейного программирования рассматривают различные математические постановки задач, позволяющие учитывать случайную природу части параметров обычной задачи линейного программирования. Основные результаты этой теории отражены в монографиях Дж. Бержа, Ф. Ловайо [134] и П. Калла |166|. Явно выделяются два основных направления развития этой теории.

Одним из них является теория задач стохастического линейного программирования с вероятностными ограничениями. Родоначальниками этого класса задач являются А. Чарнс, В. Купер, Г. Саймондс 1139,140,230]; Миллер и Вагнер [194]. Дальнейшее развитие эта теория получила в работах таких математиков как С. Ахмед [188, 189], Д. Денчева [229], П.Калл [166, 167], Т. Шантай [231], Дж. Людтке [187-189], Г. Майер [167], А. Немировскип

199], В.И.Норкин |201], А. Прекопа |208, 211, 213, 215], А. Ружински |202, 214, 223, 224, 229], А. Шапиро [199, 214, 224, 229], в работах которых эта теория получила, в частности, обобщение на более широкий класс задач стохастического программирования, выходящий за границы применимости линейных моделей.

Одноэтапные задачи квантильной оптимизации, рассмотренные в монографиях А.И. Кибзуна и Ю.С. Кана [33, 174], в случае полиэдральной выпуклой функции потерь, являются обобщением классических задач стохастического линейного программирования с вероятностными ограничениями. Этот класс задач требует разработки специальных методов решения, так как попытки использовать стохастические квазиградиентные процедуры оптимизации функции квантили наталкиваются в этом случае на значительные трудности, связанные с недифференцируемостью целевой функции потерь, отсутствием возможности получения в явном виде выражения для функции квантили и низкой скоростью сходимости квазиградиентных процедур.

Другим направлением развития стохастического линейного программирования являются исследования в области двухэтапиых задач с критериальной функцией в форме математического ожидания. Двухэтапные и многоэтапные задачи стохастического программирования можно рассматривать как промежуточный шаг от задач стохастического программирования к динамическим задачам управления с учетом влияния случайных факторов. В таких задачах изначально выбирается стратегия первого этапа, которая корректируется в будущем, на втором шаге, в зависимости от реализации случайных факторов, учитываемых в задаче. Таким образом, поиск оптимальной стратегии в задаче второго этапа должен осуществляться в классе функций, зависящих от стратегии первого этапа и возможной реализации случайных параметров. Однако, исследователя на первом этапе решения подобных задач, как правило, не интересует оптимальная стратегия в задаче второго этапа. Она необходима ему лишь для учета потерь от будущей коррекции выбираемой оптимизационной стратегии в критериальной функции первого этапа. Это привело к возникновению апостериорной постановки двухэтапной задачи, которая, по сути, является результатом применения метода динамического программирования к исходной двухшаговой задаче стохастического оптимального управления. Традиционно результат коррекции на втором этапе учитывался при выборе стратегии первого этапа путем добавления к критериальной функции (функции потерь) задачи первого этапа математического ожидания минимального значения функции потерь задачи второго этапа. Впервые такая постановка задачи была сформулирована в работах Е. Биля [125] и Дж. Данцига [143]. Толчком к развитию теории двухэтапных и многоэтапных задач послужило активное использование математических методов теории оптимизации при решени различных прикладных задач в первую очередь экономического характера. Этим объяснялось использование оператора математического ожидания при учете потерь от коррекции на втором этапе, так как средние потери представлялись естественным критерием в экономических приложениях. Структура прикладных задач экономического характера способствовала выделению, как наиболее адекватного, класса двухэтапных задач стохастического линейного программирования с критерием в форме математического ожидания. Качественные свойства двухэтапных задач стохастического линейного программирования наиболее полно исследованы в работах Дж. Бержа [131,134,135], Д. Валкупа [242], Р.-Дж. Ветса [242,246], П. Калла [1бб-168|, Ф. Ловайо [134, 185], С. Сена [226], Д.Б. Юдина |115|. В монографиях П. Калла [166], Дж. Бержа и Ф. Ловайо [134] предложены условия выпуклости критериальной функции и множества допустимых стратегий задачи первого этапа. Это позволило сформулировать условия существования решения двухэтапной задачи стохастического линейного программирования.

Методы решения двухэтапных задач стохастического линейных программирования с критерием в форме математического ожидания приведены в работах Дж. Бержа [131—135|, Р.Дж. Ветса [135, 242. 246, 247|, Дж. Данцига [144, 145], П. Калла и Г. Майера [167], Ф. Ловайо [134, 185], А. Чарнса, В. Купера и Г. Томпсона [141], Н. Эдирисайна и В. Зиембы [156]. Линейность оператора математического ожидания в случае дискретного распределения параметров задачи позволяет свести ее к задаче линейного программирования большой размерности. Поэтому многие методы решения двухэтапных задач с критерием в форме математического ожидания сводятся к построению специальных алгоритмов решения ЗЛП большой размерности. Специальная блочная структура матрицы ограничений в этих задачах позволяет использовать методы декомпозиции. Применение подобных методов исследовано в работах Дж. Бержа [131, 134], A.C. Величко [6], Дж. Данцига [144|, Ф. Ловайо [134,185], А. Ружински [222], С. Сена [164.226|. В частности Дантцигом и Г. Инфангером [144] предложен алгоритм на основе метода Бендерса, а Дж. Бержем и Ф. Лавайо [132, 134] - L-shaped алгоритм на основе метода двойственных отсечений. Анализ двухэтапных задач стохастического программирования методами теории двойственности проведен также в работах Р.Дж. Ветса [245], М. Ейснера и П. Олсена [157], А. Мадапски [190], Р. Рокафеллара и Р.Дж. Ветса [220,221]. Другое направление в разработке методов решения двухэтапных задач стохастического линейного программирования с критерием в форме математического ожидания связано с построением оценок оптимального значения критерия в задаче второго этапа. Подобные методы рассматривались, например, в работах Дж. Бержа и Ф. Ловайо |134|, Дж. Бержа и Р.Дж. Ветса [136], С. Уолласа и Т. Яна |243|, Н. Эдерисайна и В. Зиембы [156]. Попытка использовать градиентные методы выпуклого программирования для решения этих задач предпринята в работе С. Сена [226]. Численные алгоритмы решения двухэтапных и многоэтапных задач стохастического программирования приведены в работах Дж. Бержа и Ф. Ловайо [134], Дж. Бержа и Р.Дж. Ветса [135], С. Гартски и Д. Рутепберга [163], X. Ли и Дж. Ванга [184], К. Фраэндорфера [161], П. Калла и Г. Майера [167]. Е. Фрагнера, Дж. Гонцио и Дж. Виала [159].

Развитие теории двухэтапных задач стохастического программирования в направлении расширения линейного класса задач привело к рассмотрению задач с выпуклой функцией потерь. Свойства задачи в случае выпуклой функции потерь второго этапа исследованы в работах Дж. Бержа и Ф. Ловайо [134], А. Шапиро, Д. Денчевой и А. Ружински [229].

Ю.М. Волиным и Г.М. Островским [7] рассмотрена смешанная постановка двухэтапной задачи стохастического программирования в случае, когда часть параметров задачи второго этапа являются неопределенными.

Многоэтапные задачи стохастического программирования являются обобщением двухэтапных задач и следующим шагом на пути получения конечномерных приближений задач стохастического оптимального управления. Различные постановки многоэтапных задач и их анализ содержатся в работах Р.Дж. Ветса [218,219], Ф.Ловайо [185], П. Олсена [204-206], Р. Рокафеллара [218,219], С. Уолласа и Т. Яна [243], К. Фраэндорфера [160].

Практическая значимость класса двухэтапных и многоэтапных задач стохастического линейного программирования с критерием в форме математического ожидания в первую очередь связана с их применением для описания и оптимизации различных экономических систем. Прикладные двухэтапные и многоэтапные задачи стохастического программирования рассмотрены в работах М. Аоки [1], Дж. Бержа, Ф. Ловайо [134], М. Вазана [4], Я. Вальтера [5], Ю.М. Ермольева [13], П. Калла [166], В.А. Кардаша [27,28], Т.Ш. Сартания [106], С. Уолласа и В. Зиембы [244], Д.Б. Юдина [114,116]. Использование в качестве критерия математического ожидания даже в экономических задачах может привести к парадоксальным результатам, когда стратегия оптимальная в среднем оказывается недопустимой (не удовлетворяет ограничениям в задаче) с очень высокой вероятностью. Еще более важным по сравнению с экономическими приложениями оказывается получение гарантированного по вероятности результата в технических приложениях. Высокие требования к надежности в задачах анализа и синтеза авиационных и космических систем и необходимость получения гарантированного по вероятности результата требуют рассмотрения нового класса задач — двухэтапной квантилъной оптимизации.

В последнее время большой популярностью среди специалистов по исследованию операций пользуются двухуровневые задачи оптимизации, поскольку математические модели, построенные на базе данных задач логично отражают иерархический процесс принятия решений на практике, когда стратегии нижнего уровня (стратегия последователя) выбираются уже после принятия решения на верхнем уровне и зависят от выбранных стратегий верхнего уровня (стратегий лидера). Изначально двухуровневые задачи возникли как раздел математического программирования, описывающий иерархические системы принятия решений без учета влияния случайных факторов. Исследованием двухуровневых задач оптимизации посвящено большое количество работ как российских,так и зарубежных ученых. Среди них можно выделить И. Айоши [119,120], Дж. Барда [122-124], В.Л. Береспева [3], В.Ф. Демьянова [9], С. Демпе [3, 121, 147-151], В. Калашникова [3].Ю.А. Кочетова [67]. При этом области применения разработанных моделей включают исследования в области экономики, оптимизации транспортных инфраструктур [248], алюминиевой промышленности [200], экологии.

Двухуровневые задачи в стохастической постановке значительно менее изучены к настоящему времени ввиду сложности математической постановки задачи. К авторам, получавшим результаты в этой области можно отнести М. Лукчеттии [186], М. Патриксона и Л. Винтера [207]. В то же время двухэтапные задачи стохастического программирования можно рассматривать как частный случай двухуровневых задач, когда стратегия последователя не учитывается в явном виде в задаче лидера, но критериальная функция последней содержит в качестве аддитивной добавки оптимальное значение критерия задачи последователя, зависящее от стратегии лидера. В этом смысле использование в двухэтапных задачах стохастического программирования квантильного критерия способно расширить рамки практического применения двухуровневых задач, включив класс прикладных задач стохастического программирования, где требуется получение гарантированного по вероятности результата, включающий и задачи авиационной и космической техники.

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

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

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

В-третьих, в силу отсутствия постановки задачи, позволяющий получать гарантированный по вероятности результат в задачах двухэтапной и многоэтапной структуры.

Указанные трудности говорят об актуальности исследования единого класса одноэтаиных и двухэтапных задач стохастического линейного программирования с квантильным критерием, включающего в себя и задачи стохастического линейного программирования с вероятностными ограничениями и новый класс — двухэтапные задачи квантильнон оптимизации. Актуальным является также развитие алгоритмов поиска гарантирующих решений данного класса задач, то есть допустимых решений, на которых достигается качественная верхняя оценка оптимального значения критерия. Гарантирующие решения имеют самостоятельный прикладной смысл и могут служить хорошими стартовыми точками, обеспечивающими быструю сходимость новых адаптированных под рассматриваемый класс задач алгоритмов поиска асимптотически точных решений. Доверительный метод, развитый в монографиях Кибзуна А.И. и Кана Ю.С., позволяет для высоких, близких к единице, уровнях доверительной вероятности а получать качественные гарантирующие решения из минимаксной задачи, в которой стратегия выбирается при наихудшем значении реализации случайного параметра, принадлежащей некоторому доверительному множеству вероятностной меры не меньше, чем а. Например в случае гауссовского распределения случайных параметров, в качестве доверительного множества обычно выбирают эллипсоид с центром в точке математического ожидания. Однако с помощью того же доверительного метода можно показать, что в задачах стохастического линейного программирования оптимальное доверительное множество имеет многогранную структуру. Поэтому при средних уровнях доверительной вероятности а (0.7-0.9), разумных в ряде прикладных задач, выбор доверительного множества в форме эллипсоида может оказаться далеким от идеала. Это говорит об актуальности разработки специальных методов и алгоритмов построения качественных многогранных аппроксимаций оптимального доверительного множества.

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

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

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

Для достижения выбранной цели необходимо решить следующие задачи

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

2) Разработать эффективные алгоритмы поиска гарантирующих и точных решений одноэтапных задач стохастического линейного программирования с квантильным критерием.

3) Исследовать свойства двухэтапных задач стохастического линейного программирования с квантильным критерием. Установить связь априорной и апостерионой постановок задачи. Исследовать свойства критериальной функции задачи в апостериорной постановке. Установить условия существования решения этой задачи.

4) Разработать эффективные методы и алгоритмы поиска гарантирующих решений двухэтапных задач стохастического линейного программирования с квантильным критерием.

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

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

Научная новизна.

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

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

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

- алгоритм, основанный на параметризации многогранного доверительного множества радиусом вписанного шара.

- алгоритм, основанный на последовательном улучшении аппроксимации оптимального доверительного множества методом двойственных отсечений

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

-184. Исследован новый класс задач стохастического программирования — двухэтапные задачи стохастического линейного программирования с квантильным критерием: предложены достаточные условия непрерывности и выпуклости критериальной функции, условия выпуклости множества допустимых стратегий первого этапа, предложены достаточные условия существования решения задачи.

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

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

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

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

Структура и объем диссертации. Диссертация содержит введение,

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Наумов, Андрей Викторович

Основные результаты главы опубликованы в [57,77,78,88,100].

Заключение

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

На защиту выносятся следующие результаты.

1) Получены условия непрерывности, выпуклости критериальной функции и выпуклости множества допустимых стратегий в одноэтапной задаче стохастического линейного программирования с квантильным критерием [51,94];

2) Разработан алгоритмический аппарат поиска гарантирующих стратегий одноэтапных задач стохастического линейного программирования с квантильным критерием. Разработаны два алгоритма. Один основан па параметризации многогранного доверительного множества радиусом вписанного шара. Другой основан на последовательном улучшении аппроксимации оптимального доверительного множества методом двойственных отсечений [51.94];

3) Разработан способ сведения одноэтапной задачи стохастического линейного программирования с квантильным критерием в случае дискретного распределения к задаче линейного программирования, часть переменных которой являются булевыми [90|;

4) Получены достаточные условия непрерывности и выпуклости критериальной функции, выпуклости и компактности множества допустимых стратегий первого этапа, а также условия существования решения двухэтапной задачи стохастического линейного

192 программирования с квантильньгм критерием в апостериорной постановке [52,84];

5) Выделен класс двухэтапных задач стохастического линейного программирования с квантильным критерием для которых удается предложить эквивалент в форме одноэтапной задачи квантильной оптимизации. В случае скалярной случайной величины получен детерминированный эквивалент двухэтапной задачи стохастического линейного программирования с квантильным критерием в форме задачи линейного программирования [84,91];

6) Разработано алгоритмическое обеспечение поиска гарантирующего решения двухэтапной задачи стохастического линейного программирования с квантильным критерием [52,84,87,99];

7) Решены несколько прикладных задач стохастического линейного программирования с квантильным критерием, в том числе задача оптимизации функционирования летного парка авиакомпании и задача логистики для авиационного грузоперевозчика [57,77,78,88,99].

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

Вместе с этим, имеются широкие перспективы применения полученных результатов к задачам других классов.

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

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

В-третьих, с появлением теории и методов решения двухэтапных задач квантильной оптимизации актуальным становится вопрос рассмотрения нового класса двухуровневых задач оптимизации при наличии случайных параметров. Интересным представляется исследование подобных задач с вероятностными критериями качества.

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

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

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

Список литературы диссертационного исследования доктор физико-математических наук Наумов, Андрей Викторович, 2012 год

1. Аоки М. Оптимизация стохастических систем. /'/ М. Наука,— 1971.

2. Ашманов С.А. Линейное программирование. // М: Наука,— 1981.

3. Береснев В. Л. Верхние оценки для целевых функций дискретных задач конкурентного размещения предприятий. // Дискретн. анализ и исслед. опер. 2008. - т. 15. - № 4. - С. 3-24.

4. Вазан М. Оптимизация стохастических систем. // М.: Мир,— 1974.

5. Валтер Я. Стохастические модели в экономике. // М.: Статистика,— 1976.

6. Величко A.C. Об алгоритме двойственных отсечений для задачи двухэтапного стохастического программирования. // Известия высших учебных заведений. Математика. — 2006. — № 4. — С. 78-81.

7. Волин Ю.М, Островский Г.М. Оптимизация технологических процессов в условиях недостаточной экспериментальной информации на этапе функционирования. // Авт,омат,ика и телемеханика.— 2005.— № 8.— С. 3-21.

8. Данциг Дж. Линейное программирование, се обобщение и применение. // М: Прогресс,— 1966.

9. Демьянов В.Ф., Факкиней Ф. Задачи двухуровневой оптимизации и штрафные функции. // Изв. вузов. Матем. — 2003. — № 12. — С. 49-61.

10. Дзотцоев A.A., Кан Ю.С., Шахлевич П.К. Оптимизация площади взлетно-посадочной полосы. // Изв. РАН. Теория и системы управления.— 2007. X« 6. С. 44-49.

11. Еремин И.И. Линейная оптимизация и системы линейных неравенств. // М.: Академия,— 2007.

12. Ермольев Ю.М. Методы стохастического программирования. // М.: Наука,— 1976.

13. Ермольев Ю.М., Яст.ремский А.И. Стохастические модели и методы в экономическом планировании. // М.: Наука,— 1979.

14. Ефремов В.А., Кибзун А.И. Оптимальные экстремальные порядковые оценки квантили. // Автоматика и телемеханика. — 1996.— № 12.— С. 3-15.

15. Интернет-ресурс. Специальные алгоритмы решения задач линейного, смешанного и целочисленного программирования. // -http://Ipsolve. sourceforge. net/5.5/.

16. Кан Ю.С. Квазиградиентный алгоритм минимизации функции квантили. // Изв. РАН. Теория и системы управления.— 1996. — № 2. С. 81-86.

17. Кан Ю.С. О сходимости одного стохастического квазиградиентного алгоритма квантильной оптимизации. // Автоматика и телемеханика.— 2003. — Д"2 2. С. 100-116.

18. Кан Ю.С. Оптимизация управления по квантильному критерию. // Автоматика и телемеханика. — 2001. — № 5. — С. 77-88.

19. Кан Ю. С. Стабилизация квазилинейной системы со случайными ошибками в канале управления. // Автоматика и телемеханика. — 1994. — № 1,— С. 184-187.

20. Кан Ю.С., Краснопольская А.Н. К проблеме формирования портфеля ценных бумаг с фиксированным доходом. // Автоматика и телемеханика— 2006. — № 4. С. 97-104.

21. Каи Ю.С., Кибзуи А.И. Оптимальное управление линейной системой по квантильному критерию. // Автоматика и телемеханика.— 1990.— № 1, — С. 37-43.

22. Ка,п Ю.С. Кибзуи А.И. Стабилизация квазилинейной системы, находящейся под действием неопределенных и случайных возмущений. // Автоматика и телемеханика. — 1990. — № 11. — С. 75-84.

23. Каи Ю.С., Мистрюков A.A. Качественные исследования функций вероятности и квантили. // Изв. РАН. Теория и системы управления — 1996. № 3. С. 36-40.

24. Кан Ю.С., Русяев A.B. Задача квантильной минимизации с билинейной функцией потерь. // Автоматика и телемеханика,— 1998.— № 7. С. 67-75.

25. Кан Ю.С., Сысуев A.B. Сравнение квантильного и гарантирующего подходов при анализе систем. // Автоматика и телемеханика.— 2007. — № 1. С. 57-67.

26. Каи Ю.С., Тузов Н.В. Минимизация квантили нормального распределения билинейной функции потерь. // Автоматика и телемеханика.— 1998. — № 11. С. 82-92.

27. Кардаш В. А., Раппорт, Э.О. Введение в стохастическую оптимизацию. Кн. 1 и 2. // Новочеркасск: Изд. НГТУ- 1996.

28. Кардаш В.А., Раппорт Э.О. Моделирование экономических процессов в сельском хозяйстве. // Новосибирск: Наука.— 1979.

29. Кибзун А. И., Вишняков Б. В. Оптимизация двухшаговой модели изменения капитала по различным статистическим критериям. // Автоматика и телемеханика.— 2005. — № 7. — С. 126-143.

30. Кибзун А.И. Распараллеливание алгоритмов оптимизации функции квантили. // Автоматика и телемеханика.— 2007. — № 5. — С. 59-70.

31. Кибзун А И Вишняков Б В Детерминированные эквиваленты дня задач стохастического программирования с вероятностными критериями / / Автоматика и телемеханика— 2006 — № 4 — С 126-143

32. Кибзун А И, Вишняков Б В Применение метода бутстрепа для оценивания функции квантили // Автоматика и телемеханика — 2007 — № 11 — С 46 60

33. Кибзун А И, Кан Ю С Задачи стохастического программирования с вероятностными критериями // М Физматлит — 2009

34. Кибзун А И, Кан Ю С Свойства выпуклости функций вероятности и квантили в задачах оптимизации // Автоматика и телемеханика — 1996 Л'» 3 - С 82-102

35. Кибзун А И, Кузнецов Е А Выпуклые свойства функции квантили в задачах стохастического программирования // Автоматика и телемеханика — 2004 — N° 2 — С 33-44

36. Кибзун А И, Кузнецов Е А Оптимальное управление портфелем ценных бумаг // Автоматика и телемеханика— 2001 — № 9 — С 101-113

37. Кибзун А И, Кузнецов Е А Позиционная стратегия формирования портфеля ценных бумаг // Автоматика и телемеханика— 2003 — № 1 С 151-166

38. Кибзун А И, Кузнецов Е А Сравнение критериев VaR и CVaR // Автоматика и телеметаниъа — 2003 — №7 — С 153-164

39. Кибзун А И, Курбаковский В Ю Численные алгоритмы квантильной оптимизации и их применение к решению задач с вероятностными ограничениями // Изв РАН Техн киберн — 1992 — N° 1 — С 75-81

40. Кибзун А И, Лебедев А А , Малышев В В О сведении задачи с вероятностными ограничениями к эквивалентной минимаксной / / Изв РАН Теория и Системы Управления — 1984 — JV0 4 С 73-80

41. Кибзуп А.И., Малышев В. В. Обобщенный минимаксный подход к решению задач с вероятностными ограничениями. // Изв. РАН. Теория и Системы Управления — 1984. — № 1. С. 20-29.

42. Кибзун А.И., Малышев В.В. Обобщенный минимаксный подход к решению задач с вероятностными ограничениями. // Изв. РАН. Теория и Системы Управления.— 1989. — № 1. С. 46-55.

43. Кибзун А.И., Малышев В.В., Чернов Д.Э. Два подхода к решению задач стохастической оптимизации. // Изв. РАН. Техн. киберн,— 1988. — т. 20.— № 3. С. 20-25.

44. Кибзун А.И., Матвеев E.JI. Алгоритм распараллеливания процесса оптимизации функции квантили. // Вестник Московского Авиационного Института.- 2008. — т.15 — № 2. С. 51-58.

45. Кибзун А.И., Матвеев Е.Л. Достаточные условия квазивогнутости функции вероятности. // Автоматика и телемеханика,— 2010. — № 3. С. 54-71.

46. Кибзун А.И., Матвеев Е.Л. Оптимизация функции квантили на основе ядерных оценок. // Автоматика и телемеханика,— 2007. — № 1. С. 68-81.

47. Кибзун А.И., Матвеев Е.Л. Стохастический квазиградиентный алгоритм минимизации функции квантили. // Автоматика и телемеханика,— 2010. № 6. С. 64-78.

48. Кибзун А.И., Мирошкин В.Л. Об одной математической модели движения К А в декартовых координатах. / / Математическое Моделирование.— 2009. № 6.

49. Кибзуи А.И., Наумов A.B. Гарантирующий алгоритм решения задачи квантильной оптимизации // Космические исследования, — 1995.— Т. 33, № 2. С. 160-165.

50. Кибзун А.И., Наумов A.B. Двухэтапные задачи квантильного линейного программирования // Автоматика и телемеханика, — 1994.— № 12.— С. 83-93.

51. Кибзун А. И., Наумов A.B. Задача оптимизации деятельности транспортной авиационной компании // Тезисы 12-ой международной конференции "Системный анализ, управление и навигация",— Крым, Евпатория, 2-9 июля 2007 г, М: МАИ-ПРИНТ, С. 92

52. Кибзун А.И. Наумов A.B. Уланов C.B. Моделирование и оптимизация системы пассажироперевозок. // Тезисы Всероссийской Конференции "Научные чтения школы академика В.С.Пугачева",— Москва, Военный Авиационный Технический Университет, март, 1999 г.

53. Кибзуи А.И. Наумов А. В., Уланов C.B. Стохастический алгоритм управления летным парком авиакомпании // Автоматика и телемеханика. — 2000. — № 8. — С. 126-136.

54. Кибзун А.И., Наумов A.B., Уланов C.B. Стохастический анализ и управление летным парком авиакомпании / / Тезисы I Международной Конференции по проблемам управления. — Россия: Москва, ИПУ, 1999.

55. Кибзун А.И., Никулин И. В. Дискретная аппроксимация линейной двухэтапной задачи стохастического программирования с квантильным критерием. // Автоматика и телемеханика. — 2001. — № 8. — С. 127-137.

56. Кибзун А. И., Сотский А.Н. Алгоритм вычисления квантили для покоординатно-квазивыпуклой функции случайного вектора с независимыми компонентами. // Изв. РАН. Теория и системы управления. — 1995. — № 6. — С. 107-115.

57. Кибзун А.И., Сот,ский А.Н. Задача управления линейной стохастической системой по критерию вероятности. // Автоматика и телемеханика.— 1995. № 5. - С. 78-85.

58. Кибзун А. И., Третьяков Г. Л. Дифференцируемость функции вероятности. /'/ Докл. РАН. 1997. - т.354,- № 2. - С. 159-161.

59. Кибзун А.И., Третьяков Г.Л. О гладкости критериальной функции в задаче квантильной оптимизации. // Автоматика и телемеханика.— 1997. № 9. - С. 69-80.

60. Кибзун А.И., Третьяков Г.Л. О дифференцируемое™ функции вероятности. // Изв. РАН. Теория и системы управления. — 1996. — № 2. С. 63-85.

61. Кибзун А.И., Чернобровое А.И. Алгоритм решения обобщенной задачи Марковица. // Автоматика и телемеханика,— 2011.— № 2. С. 77-92.

62. G6. Корбут A.A. Финкельштейн Ю.Ю. Дискретное программирование. // -U.: Наука — 1969.

63. Кочетов Ю.А., Пащенко М.Г. Нижние границы в задаче выбора состава двухуровневой системы технических средств. // Дискретн. анализ и исслед. опер. — 1995. — т.2. — № 4. —

64. Лепп Р. Максимизация функции вероятности при простых ограничениях. // Изв. АН ЭССР, физ.-мат„,— 1979.— Vol. 28.— № 4. С. 303-309.

65. Лепп Р. Минимизация гладкой функции при вероятностных ограничениях. // Изв. АН ЭССР, физ.-мат.,— 1980.— Vol. 29.— № 2. С. 140-144.

66. Малышев В.В„ Карп К. А. Методы оптимизации вероятностных критериев. // М.: МАИ, — 1994.

67. Малышев В.В„ Карп К.А. Численные методы вероятностного анализа. // М.: МАИ,.- 1993.

68. Малышев В.В., Кибзун А.И Анализ и синтез высокоточного управления JIA. // М.: Машиностроение,— 1987.

69. Мирошкин В. Л. Алгоритм квантильного оценивания неизвестного параметра. // Изв. РАН.Теория и Системы Управления.— 1996.— т.2.— № 2. С. 56-80.

70. Михалевич B.C., Гупал A.M., Норкин В. И. Методы невыпуклой оптимизации. // М: Физматлит.— 1987.

71. Наумов A.B. Двухэтапная задача квантильной оптимизации бюджета госпиталя // Известия РАН. Теория и системы управления.— 1996.— № 2. С. 87-90.

72. Наумов A.B. Двухэтапная задача квантильной оптимизации инвестиционного проекта. / / Известия РАН. Теория и системы управления.— 2010. — № 2. — С. 40-47.

73. Наумов A.B. Учет риска в двухэтапных задачах оптимального распределения ресурсов / / Труды международной научной школы МАБР-2002 — Россия: Санкт-Петербург, 2002.

74. Наумов A.B. Целочисленная двухэтапная задача оптимального распределения ресурсов при случайно возникающем спросе. // Тезисы II Международной Конференции по проблемам управления. — Россия: Москва, ИПУ, 2003.

75. Наумов A.B. Целочисленная двухэтапная задача оптимального распределения ресурсов при случайно возникающем спросе. // Тезисы 8-ой международной конференции "Системный анализ, управление и навигация", — Крым, Евпатория,2003 г.

76. Наумов A.B., Бобылев И.М. Двойственный алгоритм нахождения гарантирующего решения линейной дискретной двухэтапной задачиквантильной оптимизации // Труды международной научной школы МАБР-2010 Россия Санкт-Петербург, 2010 - С 224-230

77. Наумов АВ, Бобылев ИМ О двухэтапной задаче с гохаы ическо1 о линейного программирования с квантильным критерием //' Автоматика и телемеханика — 2012 К" 2 — С 61-72

78. Наумов А В , Богданов А Б Алгоритм решения линейной двухэтапной задачи квантильной оптимизации с дискретным распределением случайных параметров / / Труды международной научной школы МАБР-2006— Россия Санкт-Петербург, 2006 С 438-441

79. Наумов А В, Богданов А Б Исследование двухэтапной задачи стохастического программирования с критерием в форме квантили // Тезисы 10-ой международной конференции "Системный анализ управление и навигация" — Крым, Евпатория,2005 г

80. Наумов А В Богданов А Б Исследование двухэтапной целочис ленной задачи квантильной оптимизации // Известия РАН Теория и системы управления — 2003 — Л-0 5 — С 62-69

81. Наумов А В Богданов А Б Решение двухэтапной задачи логистики в квантильной постановке // Автоматика и телемеханика — 2006 — К» 12 С 36-42

82. Наумов A.B., Иванов C.B. Задача распределения инвестиций, выделяемых на реструктуризацию наземного космического комплекса. / / Тезисы 10-й международной конференции "Авиация и космонавтика 2011", — Россия, Москва, 20-23 октября 2011 г.

83. Наумов A.B., Иванов C.B. Алгоритм решения дискретной задачи стохастического линейного программирования сквантильным критерием. // Тезисы 16-ой международной конференции "Системный анализ, управление и навигация", — Крым, Евпатория, 2011 г. С. 136-137.

84. Наумов A.B., Иванов C.B. Исследование задачи стохастического линейного программирования с квантильным критерием. // Автоматика и телемеханика. — 2011. — № 2. — С. 142-158.

85. Наумов A.B., Иванов C.B. Исследование одноэтапной задачи стохастического линейного программирования с квантильным критерием. // Тезисы 15-ой международной конференции "Системный анализ, управление и навигация", — Крым, Евпатория, 2010 г.

86. Наумов A.B., Кибзун А.И. Электронный учебно-методический комплекс по курсу "Теория вероятностей и математическая статистика "для дистанционного обучения. // Вестник компьютерных и информационных технологий. 2008. — № 8. — С. 36-43.

87. Наумов A.B., Уланов C.B. Учет риска в двухэтапных задачах оптимального распределения ресурсов. // Автоматика и телемеханика. — 2003. — № 7. — С. 109-116.

88. Наумов A.B., Хорева A.A., Чайка A.M. Управление деятельностью транспортной компании с учетом требования надежности // Труды международной научной школы МАБР-2007— Россия: Санкт-Петербург, 2007. С. 394-399.

89. Норкин В.И., Роенко Н.В. а-вогнутые функции и меры и их приложения. // Кибернетика и системный анализ,— 1991. — № 6. — С. 7788.

90. Райк Э. Дифференцируемость по параметру функции вероятности и стохастический псевдоградиентный метод для ее оптимизации. // Изв. АН ЭССР, физ.-мат.,— 1975. Vol. 24. - № 1. - С. 3-9.

91. Райк Э. Качественные исследования в задачах стохастического нелинейного программирования. // Изв. АН ЭССР, физ.-мат.,— 1971. — Vol. 20.- № 1,- С. 8-14.

92. Райк Э. О задачах стохастического программирования с функционалами вероятности и квантиля. // Изв. АН ЭССР, физ.-мат.,— 1972. — Vol. 21. — № 2. — С. 142-148.

93. Схрейвер А. Теория линейного и целочисленного программирования. // -М: Мир, Т. 1.-3.,- 1991.

94. Тамм Э. О квазивыпуклости функций вероятности и квантили. // Изв. АН ЭССР, физ.-мат.,— 1976. Vol. 25. - № 2. - С. 141-144.

95. Тамм Э. О минимизации функции вероятности. // Изв. АН ЭССР, физ.-мат.,— 1979. Vol. 28. — № 1. — С. 17-24.

96. Урясьев С.П. Адаптивные алгоритмы стохастической оптимизации и теории игр. // М.: Наука,— 1990.

97. Ху Т. Целочисленное программирование и потоки в сетях. // М.: Наука,— 1969.

98. Юби Э. Минимизация функции вероятности методом статистического моделирования. // Труды Таллинского политехнического института,—1976,-Vol. 411,- С. 57-76.

99. Юби Э. Статистическое исследование задач стохастического программирования и метод их решения. // Изв. АН ЭССР, физ.-мат,.,—1977. Vol. 26. - № 4. - С. 369-375.

100. Юдин Д.Б. Задачи и методы стохастического программирования. // М. : Красанд,— 2010.

101. Юдин Д.Б. Задачи и методы стохастического программирования. // М.: Советское радио,— 1979.

102. Юдин ДБ, Голъштейн ЕГ Специальные направления в линейном программировании // М Красанд,— 2010

103. Aishizuka Y , Aiyoshi Е Double penalty method for bilevel optimization problems // Annals of Operations Reseaich — 1992 — N 34— pp/ 73-88

104. Aiyoshi E , Shimizu К Hierarchical decentralized systems and its new solution by a barnci method // IEEE Transactions on Systems, Man, and Cybernetics 1987 — N 11- pp/ 444-449

105. Ayalew Getachew Mersha Dempe S Linear bilevel progiammmg with upper level constiamts depending on the lower level solution // Applied Mathematics and Computation 2006 - V 180- N 1 - pp/ 247-254

106. Baid J Bilevel Optimization Algorithms and Applications //Kluwer Academic Publishers, Dordrecht,— 1998

107. Bald J Falk J An explicit solution to the multilevel programming problem // Computéis and Operations Research — 1982 — N 9— pp/ 77-100

108. Bard J , Moore J A Bianch and bound algonthm foi the bilevel programming problem // SIAM Journal on Scientific and Statistical Computing — 1990 — N 11-pp/ 281-292

109. Beale E M L On minimizing a convex function subject to lmeai inequalities // J Royal Statistical Society — 1955 — Series В,— N 17 — Pp 173-184

110. Beialdt P Rubztzytbki A A Bianch and Bound Method foi Stochastic Integer Problems Under Probabilistic Constraints // Optimization Methods and Software 2002 Vol 17 - N 3- Pp 359-382

111. Beialdi P , Rvszczycsh A Beam seaich heuristic to solve stochastic integer problems under probabilistic constraints // European Journal of Operational Research 2005 Vol 167 - N 1- Pp 35-47

112. Beraldi P , Ruszczycsh A The Probabilistic Set-Covering Problem // Opei-ations Research 2002 Vol 50 - N 6- Pp 956-967

113. Birge J R Decomposition and partitioning methods for multistage stochastic lmeai programs // Operat Research — 1985 — N 33 — Pp 989-1007

114. Bnge J R The relationship between the L-shaped method and dual basis factorization for stochastic linear programming // m Y Ermohev and R/ Wets, Eds Nymerical Techniques for Stochastic Optimization— Springer-Verlag, Berlin 1988 - Pp 267-272

115. Birge J R , Holmes D F Efficient solution of two-stage stochastic lmeai programs using mtenro point methods // Comp Optim and Appl — 1992 — N 1 Pp 245-276

116. Buqe J R , Louveaux F Introduction to stochastic piogiammmg //- Sprmgei-Verlag, NY— 1997

117. Bnge J R , Wets R J -B Designing approximation schemes foi stochastic optimization problems, m particular foi stochastic piogiammmg with lecourse // Mathematical Programming Study — 1986 — N 27 — Pp 54-102

118. Birge J R Wets R Sublmear upper bounds for stochastic programs with re-couise // Mathematical Programming — 1989 — N 43 — Pp 131-149

119. Borell C. Convex set functions in d-Space. // Period. Math. Hung.— 1975.— V. 6- N. 2- pp/ 11-136.

120. Calafiore G.C., Campi M.C. Uncertain convex programs: Randomized solutions and confidence levels. /'/ Math. Program.— 2005. N. 102— Pp. 25-46.

121. Charnes A., Cooper IV. W. Chance-Constrained Programming // Management Sci. 1959. - N. 5. - Pp. 73-79.

122. Charnes A., Cooper W.W. Deterministic Equivalents for Optimizing and Sat-isficing under Chance-Constraints // Oper. Res. — 1963. — N. 11. — Pp. 18-39.

123. Charnes A., Cooper IV. W., Thompson G.L. Constrained Generalized Medians and Hypermedians as Deterministic Equivalents for Two-Stage Linear Programs under Uncertainty. // Management Science.— 1965. — N. 12. — Pp. 83112.

124. Dantzig G. Aircraft allocation problem, in Linear Programming and Extensions. // Prinection University Press.— 1963. — V. 40 — N. 1— pp/ 572—597.

125. Dantzig G.B. Linear programming under uncertainty. // Management Science- 1955. N. 1. - Pp. 197-206.

126. Dantzig G.B., Infanger G. Large-Scale Stochastic Linear Programs-Importance Sampling and Benders Decomposition. // Computational and Applied Mathematics.— 1992. N. 1. - Pp. 111-120.

127. Dantzig G.B. Madansky A. Onthe solution of two-stage linear programs under unsertainty. // Proceedings of the Fourth Borkeley Symposium on Mathematical Statistics and Probability.— University of California Press, Barkeley, CA. — 1961.

128. Deak I. omputation of multiple normal probabilities. //P. Kail and A. Prekopa (eds.). Recent Results in Stochastic Programming.— N. Y.: Springer-Verlag,— 1980. pp/ 107-121.

129. Dempe S. A simple algorithm for the linear bilevel programming problem. // Optimization. — 1987. — N. 18— pp/ 373-385.

130. Dempe S. Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints. // Optimization. — 2003.— N. 52 — pp/ 333-359.

131. Dempe S. Bilevel Programming A Survey. // Preprint TU Bergakademie Freiberg. — Fakultet fur Mathematik und Informatik, — 2003.

132. Dempe S. Foundations of Bilevel Programming. // Dordrecht, The Netherlands: Kluwer, — 2002.

133. Dempe S., Kalashnikov V. Kalashnykova N. LOptimality conditions for bilevel programming problems. // ptimization with Multivalued Mappings: Theory, Applications and Algorithms,— Springer Science+Bu.— 2003. — pp. 3-28.

134. Dentcheva D., Prekopa A., Ruszczycski A. Concavity and efficient points of discrete distributions in probabilistic programming. // Math. Program.— 2000. N. 89- Pp. 55-77.

135. Dupacova J. Stability and sensitivity analysis for stochastic programming. // Annals of Operations Research— 1990. N. 27— Pp. 115—142.

136. Dupacova J. The minimax approach to stochastic linear programming and the moment problem. // Ekonom.-Math. Obzor.— 1977. N. 13— Pp. 297—307.

137. Dupacova J., Wets R.J.-B. Asymptotic behavior of statistical estimators and of optimal solutions of stochastic optimization problems. // Annals of Statistics— 1988. N. 16- Pp. 1517-1549.

138. Edirisinghe N.C.P. Ziemba W.T. Bounds for Two-Stage Stochastic Programs with Fixed Recourse. // Mathematics of Operation Research.— 1994. — N. 19. Pp. 292-313.

139. Eisner M J Ohen P Duality for stochastic programming interpreted as L P in Lp-space // SIAM J Appl Math 1975 - N 28 - Pp 779-792

140. Ermohev Yu Norkvn V Wets R J -B Minimization of Discontinuous Functions //Molhfier Subgradients Working Paper WP-92-73, IIASA Laxenburg, Austria,— 1992

141. Fragniere E , Gondzio J , Vial J -P Building and solving laige-scale stochastic programs on an affordable distributed computing system // Annal Opeiat Research 2000 - N 99 - Pp 167-187

142. Fraaendoijei K Multistage Stochastic Programming Eiror Analysis for the Convex Case // ZOR 1994 - N 39 - Pp 93-122

143. Frauendorfer K Solving SLP Recourse Problems with Arbitrary Multivariate Distributions The Dependent Case / / Mathematics of Operations Research — 1988 — N 13 - Pp 377-394

144. Gartska S J The Economic Equivalence of Several Stochastic Programming Models //In Stochastic Programming, ed MAH Dempster Academic Press, New York, 1980 - Pp 83-91

145. Garstka S J, Rutenberg D P Computation m Discrete Stochastic Programs with Recourse // Operations Research — 1973 — N 21 — Pp 112-122

146. Higle J L Sen S Stochastic Decomposition An Algotithm for Two-stage Linear Programs with Recourse // Mathematics of Operations Research — 1991 X 16 - Pp 650-669

147. Iyengar G Erdogan E Ambiguous chance constrained pioblems and lobust optimization //Math Program — 2006 N 107—Pp 17-31

148. Kail P Stochastic Linear Programming //Berlin Springer-Vei lag — 1976

149. Kali P Mayer J Stochastic Linear Programming // Springer New York — 2005

150. Kail P , Wallace S W Stochastic Programming // Wilev, Chichester— 1994

151. Kan Yu S, Kibzun A I Sensitivity Analysis of Worst-Case Distribution foi Probability Optimization Problems // In Piobabihstic Constrained Optimization Thcoiy and Applications (S P Uiyascv, cd ) — Kluwer Acadcmic Publishers—2000—Pp 31-46

152. Kan Yu S, Mistrukov A A On the Equivalence m Stochastic Programming with Probability and Quantile Objectives // ect Notes in Economics and Mathematical Systems 1998 - N 458- Pp 145-153

153. Kao E P C , Queyranne M Budgeting costs of nursing m a hospital // Management Scicnse — 1985 Vol 31 - N 5 - Pp 608-621

154. Kataoka S A Stochastic Programming Model // Econometnca,— 1963 — Vol 31 N 1-2 - Pp 181-196

155. Kibzun A I, Kan Y S Stochastic Programming Problems with Probability and Quantile Functions // Chichester, New York, Brisbane, Toronto, Singapore John Wiley and Sons — 1996

156. Kibzun A I Kurbakovskiy V Yu Guaranteeing Approach to Solving Quantile Optimization Problems // Annals of Operations Research — 1991— N 30— Pp 81-93

157. Kibzun A I, Kuznetsov E A Analysis of Criteria VaR and CVaR // Journal of Banking and Finance 2006 - V 30 - N 2- Pp 779-796

158. Kibzun A I, Lepp R Discrete Approximation m Quantile Problem of Portfolio Selection // Stochastic Optimization Algorithms and Applications ed S

159. Uryasev and P M Pardalos,— Kluwer Academic Publishers, Norwell — 2000 — Pp 119-133

160. Kibzun A I Malyshev V V Karp K A A Minimax Approach for Statistical Simulation of Complex Technical Systems // Advances m Modelling and Simulation AMSE Pi ess - 1988- V 10 -N 3-Pp 35-46

161. Kibzun A I, Naumov A V Optimal Investment to the Regional Water-Supply Svstem // Pioceedmgs of International Confeience Mathematics, Computer, Control and Investments — Russia, Moscow, 1993 — Pp 72-78

162. Kibzun A I and I V Nikulin Discrete Approximation of Quantile Linear Two-Stage Problem m Stochastic Programming // Proc 11th International Baikal Workshop on Optimization Methods and Applications — Irkutsk Institute of Eneigv Svstem — 1998 Pp 161-165

163. Kibzun A , Uryasev S Differentiability of Probability Function // Stochastic Analysis and Applications 1998 Vol 16 - N 6- Pp 1101-1128

164. Kolbm V V Stochastic Programming // D Reidel, Dordrecht — 1977

165. Lepp B Approximation Type Algorithm for the Maximization of the Probability Function // Eesti NSV Teaduste Akadeemia Toimetised, Fuusika and Matemaatika,— 1983 — Vol 32 — N 2 — Pp 150-156

166. Li X Wang J Approximate Feasible Direction Method for Stochastic Programming Problems with Recourse Linear Inequality Deterministic Constraints // Optimization — 1990 — N 21 — Pp 401-407

167. Louueaui F V Multistage stochastic programs with block-separable re-couise // Mathematical Programming Study,— 1986 — N 28 — Pp 48-62

168. Lucchetti R , Mignanego F Pieri G Existence theorem of equilibrium points m Stackelberg games with constraints // Optimization — 1987 — A 18 — pp/ 857-866

169. Luedtke J New Formulations for Optimization Under Stochastic Dominance Constraints // SIAM J Optim 2008 Vol 19 - N 3-Pp 1433-1455

170. Luedtke J Ahmed S A sample approximation approach for optimization with probabilistic constiamts //SIAM J Opum 2008 Vol 19 — N 2-Pp 674699

171. Luedtke J, Ahmed S, Nemhauser G An integer programming approach for lmeai programs with probabilistic constraints // Math Progiam— 2010 Vol 122 N 2- Pp 247-272

172. Man dan sky A Dual Variables in Two-Stage Lmeai Programming under Uncertainty // J Math Anal Appl 1983 - N 6 - Pp 98-108

173. Marti K Approximations and Derivatives of Probability Functions // In Approximation Probability and Related Fields, eds G Anastassiou and S T Rachev, Plenumn Press, New York — 1994

174. Marti K Stochastic Optimization Methods // Berlin Heidelberg Spnnger — 2005

175. Marti K Stochastic Optimization Methods in Structural Mechanics // ZA-MM Applied Mathematics and Mechanics,— 1990 — Vol 70 — Pp 742-745

176. Miller L B , Wagner H Chance-constramed programming with joint constraints //Operations Research — 1965 N 12—Pp 930-945

177. Morgan D , Eheait ) W, Valorrhi A Aquifer remediation design under uncertainty using a new chance constiamed programming technique // Water Resources Research — 1993 N 29— Pp 551-561

178. Murty K G Linear progiammmg // John Wiley Ink , N Y — 1983

179. Naumov A V Linear Two-Stage Quantile Optimization Problem // 15th Intci-national Simposium on Mathematical Programming Piogram and Abstracts — The Universitv of Michigan Ann-Arbor, USA August 15-19 — Pp 152

180. Nernirovski, A., Shapiro A. Convex approximations of chance constrained programs. // SIAM J. Optim — 2006. N. 17- Pp. 969-996.

181. Nernirovski A., Shapiro A. Scenario approximation of chance constraints. // In G. Calafiore and F. Dabbene (Eds.). Probabilistic and Randomized Methods for Design Under Uncertainty— London: Springer.— 2005. — Pp. 3-48.

182. Nicholls M.G. Aluminium production modelling a non-linear bi-level programming approach. // Operations Research. — 2001. — N. 43— pp/ 208-218.

183. Noyan N., Rudolf G., Ruszczycski A. Relaxations of linear programming problems with first order stochastic dominance constraints. // Operations Research Letters.- 2006. Vol. 34. N. 6- Pp. 653-659.

184. Noyan N., Ruszczycski A. Valid Inequalities and Restrictions for Stochastic Programming Problems with First Order Stochastic Dominance Constraints. // Math. Program. Ser. A,- 2008. Vol. 114. - N. 2. - Pp. 249-275.

185. Olsen P. Multistage Stochastic Programming with Recourse : The Equivalent Deterministic Problem. // SIAM J. Control and Optimization.— 1976. — N. 14,- Pp. 495-517.

186. Olsen P. Multistage Stochastic Programming with Rescourse as Mathematical Programming in an Lp Space. // SIAM J. Control and Optimization.— 1976. — N. 14. Pp. 528-537.

187. Olsen P. When is Multistage Stochastic Programming Problem Well-defined. // SIAM J. Control and Optimization.— 1976. — N. 14. — Pp. 518-527.

188. Patriksson M., Wynter L Stochastic mathematical programs with equilibrium constraints. // Oper. Res. lett. — 1999. — V. 25—N. 1— pp/ 159-167.

189. Prekopa A Dual method for the solution of one-stage stochastic programming problem with random RHS obeying a discrete probability distribution // ZOR—Methods and Models of Operations Research — 1990 N 34 — Pp 441461

190. Prekopa A Loganthmic Concave Measures and Related Topics //In Stochastic Programming, ed M A H Dempstei London Academic Press — 1978 — Pp 63-82

191. Prekopa A Logarithmic Concave Measures with Application to Stochastic Programming //Acta Sci Math (Szeged)1971 — N 32 Pp 301-316

192. Prekopa A Numerical Solution of Probabilistic Constrained Programming Problems // In Numerical Techiques for Stochastic Optimization, eds Yu Ermoliev and R J B Wets Sprmgci-Vcrlag, Berlin — 1980 — Pp 123139

193. Prekopa A On Logarithmic Concave Measures and Functions // Acta Sci Math (Szeged) 1973 - N 34 - Pp 325-343

194. Prekopa A On probabilistic constrained programming // In HW Kuhn (Ed ), Proceedings of the Princeton Svmposium on Mathematical Programming, Princeton NJ Princeton University Press — 1970 Pp 113-138

195. Prekopa A Probabilistic programming // m A Ruszczynski, A Shapiro (Eds) Stochastic Piogrammmg Handbooks Oper Res Management Sci— 2003 N 10 New York Elsevier Pp 267-351

196. Prekopa A Stochastic programming // Boston Kluwer Scientific — 1995

197. Piekopa A , Szantai T Flood contiol leservoir system design // Math Pro Study, North-Holland 1978 — N 9- pp/ 138-151

198. Prekopa A Szantai T Multivariate Gamma Distubution and Its Fitting to Empirical Streamflow Data // Water Resources Research — 1978 — N 14 — Pp 19-24

199. Rockafellar R T Weft R J -B Continuous versus Measurable Recourse in N-Stage Stochastic Programming // J Math Anal Appl — 1974 — N 48 — Pp 836-859

200. Rockafellar R, T , Wets R J -B Measures as Lagiange Multipheis m Multistage Stochastic Programming //J Math Anal Appl 1977 — N 60 - Pp 301313

201. Rockafellar R T, Wets R J B Stochastic convex piogiammmg Basic duality // Pacific J Math 1976 - Vol 62 - N 1 - Pp 173-195

202. Rockafellar R T Wets R J -B Stochastic convcx programming Singular multipliers and extended duality singular multipheis and duality // Pacific J Math 1976 - Vol 62 - N 2 - Pp 507-522

203. Rvszcynski A Parallel Decomposition of Multistage Stochastic Programming Problems // Mathematical Programming — 1993 — N 58 — Pp 201-228

204. Ruszczycski A Probabilistic piogiammmg with discrete distributions and precedence constrained knapsack polyhedra // Math Program — 2002 \ 93— Pp 195-215

205. Ruszczycski A , Shapiro A Stochastic programming //-Amsteidam Elsvi-er — 2003

206. Saxena A , Goyal V Lejeune M A MIP reformulations of the probabilistic set coveung Pioblem //Math Program, Ser A — 2010 N 121—Pp 1-31

207. Sen S Subgradient decompositon and Differentiability of the Recourse Function of a Two Stage Stochastic Linear Program // Operations Research Letters 1993 - N 13 - Pp 143-148

208. Sen S Relaxation for probabilistically constrained programs with discrete random variables // Operations Research Letters — 1992 N 11— Pp 81-86

209. Sengupta J K Stochastic Programming Methods and Applications //-North-Holland Amsterdam,— 1972

210. Shapno A Dentcheva D , Ruszczycski A Lectuies on Stochastic Programming Modeling and Theory //Philadelphia SI AM — 2009

211. Symonds G U Deterministic Solution for a Class of Chance-Constrained Programming Problems // Oper Reseaich, — 1967 — Vol 15 — N 3 — Pp 495512

212. Szantai T A Computer Code for Solution of Probabilistic-Constrained Stochastic Programming Problems //In Numerical Techniques foi Stochastic Optimization, eds Yu Ermoliev and R J-B Wets Springei-Verlag, Berlin,— 1980 - Pp 229-235

213. Tamm E On Minimization of a Function under an Equality Chance Constraint // Math Operationsforsch Statist , Ser Optimization,— 1981 — Vol 12 N 2 - Pp 253-262

214. Uryasev S Differentiation Formula for Integrals over Sets Given by Inclusion // Computational and Applied Mathematics — 1995 — N 56

215. Uiyasev S Differentiation Formula foi Integrals over Sets Given bv Inclusion // Numencal Functional Analysis and Optimization,— 1989 — Vol 10 — N 7,8 Pp 827-841

216. Uiyasev S Differentiability of an Integral ovei a Set Defined bv Inclusion // Cybernetics,- 1988 Vol 24 - N 5 - Pp 638-642

217. Uryasev S, Rockafellar R T Conditional Value-at-Risk Optimization Approach // In Stochastic Optimization Algorithms and Applications

218. S.Uryasev and P.M.Pardalos, eds.).— Kluwer Academic Publishers— 2001. Pp. 411-435.

219. Vajda J. Probabilistic Programming. // Acad. Press, New York, London,—1 nr?r> ±y (z.

220. Vela A., Salaun E., Solak S., Feron E., et al. A Two-Stage Stochastic Optimization Model for Air Traffic Conflict Resolution under Wind Uncertainty. // Proc. 28th Digital Avionics Syst. Conf. DASC '09.- IEEE/AIA A 28th.- 2009.

221. Vizvari B. The Integer Programming Background of a Stochastic Integer Programming Algorithm of Dentcheva-Prekopa-R.uszczvski. // Optimization Methods and Software.- 2002. Vol. 17. N. 3- Pp. 543-559.

222. Voge S. Qualitative stability of stochastic programs with applications in asymptotic statistics. // Statistics and Decisions — 2005. N. 23— Pp. 1001-10030.

223. Walkup D. W., Wets R.J.-B. Stochastic Programs with Recourse. //' SIAM J. Appl. Math.,- 1967. N. 15. - Pp. 1299-1314.

224. Wallace S.W. Yan T. Bounding Multi-Stage Stochastic Programs from Above. // Mathematical Programming — 1993. — N. 61. — Pp. 111-129.

225. Wallace S.W., Ziemba W.T. Applications of Stochastic Programming. // SIAM 2005.

226. Wets R.J.-B. Duality relations in stochastic programming. // In Symposia Mathemat.ica, Vol. XIX (Convegno sulla Programmazione Matematica e sue Applicazioni), INDAM, Rome.— 1976. — Academic Press, London. — Pp. 341355.

227. Wets R.J.-B. Programming under uncertainty: the equivalent convex program. // SIAM J. Appl. Math.,- 1966,- N. 14. Pp. 89-105.

228. Wets R.J.B. Stochastic programs with fixed recourse: The equivalent deterministic program. // SIAM Review,— 1974. — N. 16. — Pp. 309-339.

229. Yang H. and Bell M.G.H. Transportation bilevel programming problems: Recent methodological advances. // Transportation Research, Part B. — 2001. — N. 35 — pp/ 1-4.

230. Yen J. W., Birge J.R. A stochastic programming approach to the airline crew scheduling problem. // Transportation Sci.— 2006. — V. 40 — N. 1 — pp/ 3—14.