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

На правах рукописи

Наумов Андрей Викторович

МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ АДАЧ СТОХАСТИЧЕСКОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С КВАНТИЛЬНЫМ КРИТЕРИЕМ

Специальность 05.13.01 Системный анализ, управление и обработка информации (авиационная и ракетно-космическая техника)

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

2 ОЕЗ Ш

Москва — 2012 год

005009126

005009126

Работа выполнена на кафедре теории вероятностей

Московского авиационного института (национального исследовательского университета)

Научный консультант — доктор физико-математических наук

профессор Кибзун Андрей Иванович ■

Официальные оппоненты — доктор физико-математических наук,

профессор Хрусталев Михаил Михайлович

— доктор физико-математических наук, профессор Чуличков Алексей Иванович

— доктор физико-математических наук, профессор Волков Игорь Куприянович

Ведущая организация — Учреждение Российской академии наук

Институт проблем управления имени В.А. Трапезникова РАН

Защита гпгтпптгчт^'^ ^ W4L заседании Диссертационного Совета Д 212.125.04 Московского авиационного института по адресу: 125993, Москва, А-80, ГСП-3, Волоколамское шоссе, 4

С диссертацией можно ознакомиться в библиотеке Московского авиационного института по адресу: 125993, Москва, А-80, ГСП-3, Волоколамское шоссе, 4, Ученый совет МАИ

д , Z^.OÍ. 2¿>i¿

Автореферат разослан __ ^

Отзывы просим отправлять в 2-х экземплярах, заверенных печатью, по адресу: 125993, Москва, А-80, ГСП-3, Волоколамское шоссе, 4, Ученый.совет МАИ

Ученый секретарь

Диссертационного Совета Д 212.125.04 кандидат физико-математических наук, доцен1

✓-■"Ротанина М.В.

-3-

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

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

Исторически теория оптимизации вероятностных критериев качества возникла как специальный раздел теории задач стохастического программирования с вероятностными ограничениями, интенсивно развиваемой примерно с конца 50-х годов прошлого столетия благодаря исследованиям А. Чарнса, В. Купера, Г. Саймондса, Л. Миллера и X. Вагнера, а также Дж. Вайды, С. Гартски, Ж. Дупачевой, П. Калла, В.В. Колбииа, Г. Майера, А. Прекопы, Дж. Сенгупты, С. Уолласа, Т. Шантая, Д.Б. Юдина. Квантильный критерий впервые введен в рассмотрение С. Катаокой. Развитие теории и практики решения задач с квантильным критерием связано с именем Э. Райка и его учеников Р. Леппа и Э. Юби. Эта школа математиков по сути заложила фундамент теории вероятностной и квантильной оптимизации, исследовав основные свойства функции вероятности и квантили. Дальнейшее развитие эта теория получила в работах российских исследователей Ю.С. Капа, К.А. Карпа, А.И. Кибзу-на, В.В. Малышева. Необходимо также отметить вклад Ю.М. Ермольева, К. Марти, В.И. Норкина, Н.В. Роенко, С.П. Урясьева.

Современное состояние теории и практики решения задач вероятностной оптимизации связано с именами С. Ахмеда, П. Беральди, С. Вогела, Д. Денчевой, Г. Кала-файоре, М. Кампи, Ю.С. Кана, А.И. Кибзуна, Дж. Людке, К. Марти, А. Немировского, В.И. Норкина, А. Прекопы, А. Ружински, С.П. Урясьева, А. Шапиро.

Специальная техника решения задач вероятностной оптимизации с дискретным распределением случайных параметров отражена в работах П. Бералди, Б. Визвари, Д. Денчевой, Дж. Людке, Д. Моргана, Н. Нойана, А. Прекопы, А. Ружински, А. Саксе-на, С. Сена, М. Таннера. Исследования задач с дискретным распределением вектора случайных параметров является важным направлением в стохастическом программировании. Во-первых, это связано с традиционным использованием в стохастическом программировании сценарного подхода. При таком подходе для описания модели неопределенных параметров задачи рассматривается ряд их возможных значений (сценариев), вероятности реализации которых оцениваются экспертами. Получаемые при

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

Отдельно нужно выделить современную российскую школу вероятностной квантильной оптимизации А.И. Кибзуна и его учеников Ю.С. Кана, В.В. Вишнякова В.А. Ефремова, Е.А. Кузнецова, В.Ю. Курбаковского, В.Л. Мирошкина, А.Н. Сотск го, Г.Л. Третьякова, а также A.B. Сысуева. В монографиях А.И. Кибзуна и Ю.С. Кан систематически изложена теория вероятностной и квантильной оптимизации и продол жено развитие предложенного ранее В.В. Малышевым и А.И. Кибзуном обобщенн минимаксного подхода, получившего название доверительного метода. Суть подх да заключается в замене исходной задачи квантильной оптимизации на эквивалент ную минимаксную задачу, где внутренний максимум от функции потерь берется п всем возможным значениям случайных параметров из некоторого доверительног множества соответствующей вероятностной меры, а внешний минимум по стратеги оптимизации и всем доверительным множествам этой вероятностной меры. В раб тах Ю.С. Кана, А.И. Кибзу на, В.В. Малышева, Г.Л. Третьякова исследованы ка чественные свойства квантильного и вероятностного критериев. Методы построени асимптотически точных решений задач квантильной оптимизации отражены в раб тах Ю.С. Кана, А.И. Кибзуна, В.Ю. Курбаковского, Е.Л. Матвеева. В основном эт методы построены на основе процедуры стохастической аппроксимации, требующе? построения квазиградиента функции квантили. Для этого требуется находить оценк значения функции квантили ввиду отсутствия возможности получения ее явного вида. Способы нахождения оценок функций вероятности и квантили рассмотрены в работ; В.В. Вишнякова, В.А. Ефремова, Ю.С. Кана, А.И. Кибзуна, Е.Л. Матвеева. Развита квазиградиентных методов решения задач квантильной оптимизации сопряжено с значительными вычислительными затратами, которые часто становятся непреодолимыми. Для борьбы с этими трудностями в последнее время усилиями А.И. Кибзуна начал развиваться подход, связанный с использованием методов параллельных вычислений в подобных процедурах.

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

Одним из них является теория задач стохастического линейного программирования с вероятностными ограничениями. Родоначальниками этого класса задач являются А. Чарнс, В. Купер, Г. Саймондс, Миллер и Вагнер. Дальнейшее развитие эта теория получила в работах таких математиков как С. Ахмед, Д. Денчева, П.Калл, Т. Шантай, Дж. Людтке, Г. Майер, А. Немировский, В.И.Норкин, А. Прекопа, А. Ру-жински, А. Шапиро, в работах которых эта теория получила, в частности, обобщение на более широкий класс задач стохастического программирования, выходящий за границы применимости линейных моделей.

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

Другим направлением развития стохастического линейного программирования являются исследования в области двухэтапных задач с критериальной функцией в форме математического ожидания. Двухэтапные и многоэтапные задачи стохастического программирования можно рассматривать как промежуточный шаг от задач стохастического программирования к динамическим задачам управления с учетом влияния случайных факторов. В таких задачах изначально выбирается стратегия первого этапа, которая корректируется в будущем, па втором шаге, а зависимости от реализм ции случайных факторов, учитываемых в задаче. Таким образом, поиск оптимальной стратегии в задаче второго этапа должен осуществляться в классе функций, зависящих от стратегии первого этапа и возможной реализации случайных параметров. Однако, исследователя на первом этапе решения подобных задач, как правило, не интересует оптимальная стратегия в задаче второго этапа. Она необходима ему лишь для учета потерь от будущей коррекции выбираемой оптимизационной стратегии в критериальной функции первого этапа. Это привело к возникновению апостериорной постановки двухэтапиой задачи, которая, по сути, является результатом применения метода динамического программирования к исходной двухшаговой задаче стохастического оптимального управления. Традиционно результат коррекции на втором этапе учитывался при выборе стратегии первого этапа путем добавления к критериальной функции (функции потерь) задачи первого этапа математического ожидания минимального значения функции потерь задачи второго этапа. Впервые такая постановка задачи была сформулирована в работах Е. Биля и Дж. Данцига. Толчком к развитию теории двухэтапных и многоэтапных задач послужило активное использование математических методов теории оптимизации при решении различных прикладных задач в первую очередь экономического характера. Этим объяснялось использование оператора математического ожидания при учете потерь от коррекции на втором эта^ пе, так как средние потери представлялись естественным критерием в экономических приложениях. Качественные свойства двухэтапных задач стохастического линейного программирования наиболее полно исследованы в работах Дж. Бержа, Д. Валкупа, Р.Дж. Ветса, П. Калла, Ф. Ловайо, С. Сена, Д.Б. Юдина. В монографиях П. Калла, Дж. Бержа и Ф. Ловайо предложены условия выпуклости критериальной функции и множества допустимых стратегий задачи первого этапа. Это позволило сформулировать условия существования решения двухэтапиой задачи линейного стохастического программирования.

Методы,решения линейных двухэтапных задач стохастического программирования с критерием в форме математического ожидания приведены в работах Дж. Бержа, Р.Дж. Ветса, Дж. Данцига, П. Калла и Г. Майера, Ф. Ловайо, А. Чарнса, В. Купера

и Г. Томпсона, Н. Эдириеайна и В. Зиембы. Линейность оператора математического ожидания в случае дискретного распределения параметров задачи позволяет свести ее к задаче линейного программирования большой размерности. Поэтому многие методы решения двухэтапных задач с критерием в форме математического ожидания сводятся к построению специальных алгоритмов решения ЗЛП большой размерности. Специальная блочная структура матрицы ограничений в этих задачах позволяет использовать методы декомпозиции.. Применение подобных методов исследовано в работах Дж. Бержа, A.C. Величко, Дж. Данцига, Ф. Ловайо, А. Ружински, С. Сена. В частности Дж. Дантцигом и Г. Инфангером предложен алгоритм на основе метода Бендерса, а Дж. Бержем и Ф. Лавайо - L-shaped алгоритм на основе метода двойственных отсечений. Анализ двухэтаппых задач стохастического программирования методами теории двойственности проведен также в работах Р.Дж. Ветса, М. Ейсне-ра и П. Олсена, А. Мадански, Р. Рокафеллара и Р.Дж. Ветса. Другое направление в разработке методов решения двухэтапных задач стохастического линейного программирования с критерием в форме математического ожидания связано с построением оценок оптимального значения критерия в задаче второго этапа. Подобные методы рассматривались, например, в работах Дж. Бержа, Р.Дж. Ветса, В. Зиембы, Ф. Ловайо, С. Уолласа, Н. Эдерисайна, Т. Яна. Попытка использовать градиентные методы выпуклого программирования для решения этих задач предпринята в работе С. Сена. Численные алгоритмы решения двухэтапных и многоэтапных задач стохастического программирования приведены в работах Дж. Бержа и Ф. Ловайо, Дж. Бержа и Р.Дж. Ветса, С. Гартски и Д. Рутенберга., X. Ли и Дж. Ваига, К. Фраэндорфера, П. Калла и Г. Майера, Е. Фрагнера, Дж. Гонцио и Дж. Виала.

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

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

Прикладные двухэтапные и многоэтапные задачи стохастического программирования рассмотрены в работах М. Аоки, Дж. Бержа, Ф. Ловайо, М. Вазана, Я. Вальтера, Ю.М. Ермольева, П. Калла, В.А. Кардаша, Т.Ш. Сартания, С. Уолласа и В. Зиембы, Д.Б. Юдина. Использование в качестве критерия математического ожидания даже в экономических задачах может привести к парадоксальным результатам, когда стратегия оптимальная в среднем оказывается недопустимой (не удовлетворяет ограничениям в задаче) с очень высокой вероятностью. Еще более важным по сравнению с экономическими приложениями оказывается получение гарантированного по вероятности результата в технических приложениях. Высокие требования к надежности в задачах анализа и синтеза авиационных и космических систем и необходимость получения гарантированного по вероятности результата требуют рассмотрения нового класса задач двухэтапной квантильной оптимизации.

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

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

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

— низкую скорость сходимости;

— достаточным условием сходимости таких алгоритмов как правило является дифференцируемость целевой функции, которая отсутствует у полиэдральной целевой функции в задачах стохастического линейного программирования;

— необоснованность сходимости этих алгоритмов при наличии дополнительных вероятностных ограничений;

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

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

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

средних уровнях доверительной вероятности а (0.7-0.9), разумных в ряде приклад ных задач, выбор доверительного множества в форме эллипсоида может оказатьс далеким от идеала. Это говорит об актуальности разработки специальных методо и алгоритмов построения качественных многогранных аппроксимаций оптимальног доверительного множества.

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

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

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

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

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

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

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

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

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

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

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

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

1. Предложены достаточные условия непрерывности, выпуклости критериаль

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

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

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

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

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

4. Исследован новый класс задач стохастического программирования — двух-этапные задачи стохастического линейного программирования с квантильным критерием:

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

- предложены достаточные условия существования решения задачи.

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

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

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

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

— задача оптимизации функционирования летного парка авиакомпании;

— двухэтапная задача логистики для транспортной авиационной компании;

— двухэтапная задача квантильной оптимизации инвестиционного проекта;

— двухэтапная задача оптимизации бюджета госпиталя.

Апробация работы. Результаты диссертации докладывались на научных семинарах кафедры теории вероятностей Московского авиационного института (рук. проф. Кибзун А.И.), кафедры математической кибернетики Московского авиационного института (рук. проф. Пантелеев A.B.), научном семинаре лаборатории № 7 Института проблем управления РАН (рук. проф. Поляк Б.Т.), кафедры компьютерных методов физики физического факультета МГУ (рук. проф. Пытьев Ю.П.), кафедры математического моделирования МГТУ им. Н.Э.Баумана (рук. проф. Крищенко А.П.), научном семинаре по стохастическому программированию факультета исследования операций университета штата Мичиган (рук. проф. Дж. Верж).

Материалы диссертации представлялись на следующих международных конференциях: международная конференция "Системный анализ и управление космически-

ми комплексами" ( Евпатория, Украина, 2001, 2003 - 2011 г.); международная конференция "Моделирование и анализ безопасности и риска в сложных системах" (Россия, Санкт-Петербрг, 2002, 2006, 2007, 2010); 15-й международный симпозиум по математическому программированию (Апн-Арбор, США, 1994 г.); международная конференция "Бортовые интегрированные комплексы и современные проблемы управления" ( Россия, Ярополец, 1998 г.); всероссийская конференция "Научные чтения школы академика В.С.Пугачева" (Москва, Военный авиационный технический университет, 1999 г.); 1-я и 2-я международные конференция по проблемам управления (Москва, ИПУ, 1999, 2003 гг.); 7-я международная конференция "Авиация и космонавтика", (Россия, Москва, 2008 г.), 10-я международная конференция "Авиация и космонавтика 2011", (Россия, Москва, 20-23 октября 2011 г).

Работа поддержана грантами РФФИ (96-01-00789-а,, 99-01-01033-а, 01-01-00416-а, 04-01-00758-а, 05-08-17963-а, 09-08-00369-а, 11-07-00315-а, 11-07-13102-офи-м-2011-РЖД, 11-07-13120-офи-м-2011-РЖД, 11-07-90407-Укр-ф-а) и государственным финансированием целевых программ "Научные и научно-педагогические кадры инновационной России"(мероприятие 1.2.2, госконтракт № 14.740.11.1128).

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

Структура и объем диссертации. Диссертация содержит введение, шесть глав, заключение и список используемой литературы. Работа состоит из 221 страниц, включая 5 рисунков, 17 таблиц и список литературы, содержащей 249 наименований.

Содержание диссертации

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

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

В качестве целевой функции потерь рассматривается выпуклая полиэдральная (кусочно-линейная) функция

Ф(ы, х) = max {AJ(U + В^х + Ьи}. (1.1)

Дополнительные ограничения в задаче описываются с помощью функции

Q{u, х) = тах{А£:ы + В%х + Ь2;}, (1.2)

i-lfa

где и £ U С К" — оптимизационная стратегия, подлежащая выбору; х € R'" — реализация вектора случайных параметров Х\ Ajit Bjit ВJ — строки матриц Ai, Bi, А2, В2 соответственно; Ьц, i = и Ь2j> j — 1, — заданные координаты

векторов Ъ\ и Ьг соответственно. Рассмотрим вероятность такого события, что целевая функция не превосходит некоторый порог ip и при этом выполнено дополнительное ограничение, т.е. Pv(u) = Р{Ф(ы,Х) ^ ip, Q(u,X) ^ 0}, где Р{-} — вероятностная мера, порожденная распределением случайного вектора^.

Функция квантили определяется как минимальное значение порога <р, при ко-

-11-

тором выполнено вероятностное ограничение:

а 6 (О,Р*); (1.3)

где Р* = sup.aeUP{Q(u,X) ^ 0}; а — выбранный заранее уровень доверительной вероятности. В случае, если при и е U для всех ¡р выполнено Р^(и) < а, будем считать по определению Ф„(к) = +оо.

Будем считать, что множество допустимых стратегий является выпуклым многогранным множеством U = {и 6 К": А^и < &з}, где вектор Ьз имеет размерность кз, а матрица € RfcjXn.

Окончательно задача стохастического линейного программирования с кван-тильным критерием формулируется следующим образом:

и„ = arg min Фа(и). (1.4)

nef

Задача записана при условии существования ее решения, при этом оптимальное значение критерия равно tpa = ФU(uu). Обычно в прикладных задачах содержательный смысл имеют уровни доверительной вероятности а > 1/2. Поэтому далее будем рассматривать а 6 (1/2, Р*).

Задача (1.4) эквивалентна следующей задаче стохастического линейного программирования с вероятностными ограничениями, записанной в матричной форме:

ш —» min

при ограничении: Р+ В\Х + Ь\ < ф А^а + В2Х + 62 ^ 0} ^ а, где ф = (<р,..., tp)T S R*1, а 0 - нулевой вектор соответствующей размерности. В этой задаче в роли переменных оптимизации выступают вектор и и переменная Здесь и далее будем предполагать, что все векторные ограничения в задачах понимаются покомпонентно.

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

XçMMseR™: Q(ti,i)<0},

Р(и) â P{XQ(u)}, и'а^{иеЖп: Р(и) > а}.

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

Теорема 1.1. Если случайный вектор X имеет плотность распределения f(x) > 0 (почти всюду по мере Лебега), при этом Р(и) > 0, ||5i,|| ф 0,г = l,fci, то функция квантили Фа(и) в задаче (1-4) является непрерывной по а & (0,Р(и)). Здесь || • || — евклидова норма вектора. Условия непрерывности и выпуклости функции квантили в задаче (1.4) по стратегии и £ U'a при фиксированном а устанавливает следующая теорема.

Теорема 1.2. Если вероятностная мера Р{-}, порожденная распределением случайного вектора X, является квазивогнутой на Rm и абсолютно непрерывной относительно мери Лебега, ||.B2¡]| Ф 0, i = 1, fo, то множество U'a является выпуклым, а функция квантили Фа(и) в задаче (1-4) является выпуклой и непрерывной функцией на U'n при любом а € (0,Р*). _

Заметим, что требование ||B2i|| ^ 0, г = 1, ¿2 не сужает класса рассматриваемых задач, т.к. если для некоторого i £ {1,2,..., k-¿\ окажется ||fhi|| = 0, то ограничение А^и -I- &2» ^ 0 можно добавить к системе ограничений, описывающих множество U. При этом получится эквивалентная задача.

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

Теорема 1.3. Пусть 11ф0,Р*>Оиа£ (О, Р"), тогда функция квантили Фа(гг) в задаче. (1-4) является полунепрерывной снизу функцией на U при любом ае(0,р*).

Заметим, что теорема справедлива для любого распределения случайного вектора X. Приведенные выше утверждения позволяют сформулировать теорему существования решения задачи (1.4).

Теорема 1.4. Пусть U ф 0, Р* > 0 и а £ (О, Р"), тогда если мнооюество {и 6 Rn: А$и ^ 0} состоит только из нулевого вектора, то решение задачи (1.4) существует.

Заметим, что теорема также сформулирована в отсутствие каких-либо предположений относительно распределения случайного вектора X.

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

Пусть существует решение задачи (1.4). Тогда, согласно доверительному методу, эта задача эквивалентна следующей минимаксной задаче:

фа— niin {sup$(u,x)| supQ(u,:r) ^ 0}, SeS^ueU хеs xeS

(ün,S„) = &Tg min {sup<Í>('u,:e)|sup<3(m,:z:) < 0}, (1.5)

se£a,ueu xeS xes

где £a есть семейство всех доверительных множеств S С Rm уровня а, т. е. таких, что P{S} ^ а. Эквивалентность здесь понимается в следующем смысле.

1) фа — <ра\

2) для каждой стратегии иа, оптимальной в задаче (1.4), найдется доверительное множество Se £ £„, такое, что пара (иа, Sa) является оптимальной в задаче (1.5);

3) для каждой пары (üa, §а), оптимальной в задаче (1.5), стратегия йа является также оптимальной и в исходной задаче (1.4).

Выбор оптимального доверительного множества Sa £ Sa является сложной маг тематической задачей. Тем не менее задача (1.5) при фиксированном доверительном множестве S дает возможность получить допустимое решение исходной задачи, доставляющее оценку сверху минимальному значению критерия <ра.

Согласно доверительному методу оптимальное доверительное множество имеет

вид

Sa = {X: Ф(иа,х) < <ра, Q(ua,x) ^ 0}, где (иа,<Ра) — неизвестное оптимальное решение задачи (1.4). В нашем случае, с учетом полиэдрального вида функций Ф(и,х) и Q(u,x), множество Sa — выпуклое зал-мкнутое многогранное множество. Векторами нормалей к граням этого множества являются строки матриц В\ и Вг-

Рассмотрим следующую задачу:

(ün.§) = arg min < sup Ф(и,х) | sup Q(u,x) < 0 > ,

v > иеи,оев |ieCfe) xeC(9) I

фа = min < sup Ф(и,х) I sup Q{u, x) < 0 > , (1.6)

ueu.eee ^xeC(W) xec{e) J

где C(ö) — подкласс многогранных а-доверительных множеств, параметризованный параметром в € 6.

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

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

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

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

Рассмотрим следующую, задачу:

шг — mm

r neu

max тах{/1^ц + В^х +

reAV j=l,fci

Ur = Arg min

u<= и

—14—

max тах{Л^-и + В^х + Ьц} (2.1)

при ограничении

max тах{Л^ц + В%х + 62;} ^ О,

x6Sr i=l.Jfc2

где ST — шар радиуса г € [0, +оо) с центром в точке М = М[Х] (при условии существования М[Х\). Без ограничения общности будем полагать, что математическое ожидание X равно нулевому вектору. Эта задача может быть сведена к задаче линейного программирования вида

tpr — min w, Ur = Arg min со (2.2)

ue.u,<peR R • v '

при ограничениях

Alu + ||ß1(||r + hi<<P,i = 1Л; AjjU + I|ß2j||r + b2j < 0,j = IM,

где II • Л — евклидова норма вектора. Для решения этой задачи может быть использован, например, стандартный симплекс-метод. Заметим, что решение полученной задачи зависит от г.

Пусть и(г) — элемент множества UT для произвольного г > 0. Рассмотрим следующее множество:

Ст = {х : тах{Л£и(г) + Bj{x + ¿>и} < (рг, тах{А%и(г) + В%х + 62i} < 0}. (2.3)

l = l.fcl i=lyk'2

Справедлива теорема.

Теорема 2.1. Если у случайного вектора X существует математическое оокидание М[Х] и существует. R G [0, оо) такое, что Urj^ 0 и P{Stj} ^ а, тогда справедливы следующие утверждения:

1) Uг ф- 0 для любого г 6 [0, Л];

2) существует, непрерывная по г £ [0, Л] функция и(г) такая, что u(r) € Ur для любого г € [0, Л];

3) функция ipr непрерывна и монотонно возрастает по г;

4) функция Р{Сг} полунепрерывна сверху по г G [0, Л], и существует г* =

min{r 6 [0, Л]: P{Cr} ^ а);

5) пара (и(г*),<рг») является гарантирующим решением задачи (1.4).

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

С точки зрения поиска гарантирующего решения устраивает любое значение параметра г е [0, Л], при котором Р{С,.} ^ а. Однако в силу монотонного возрастания <рг по г наилучшую оценку оптимального значения критерия будет давать ipr*, где г* = min{r б [0,Л]: Р{Cr} ^ а}. Очевидно, что если Р{СГ} > а при г = 0, то среди всех гарантирующих решений (и(г), <рТ) наименьшим значением критерия будет обладать (и(0),(ро).

Приведепная теорема позволяет предложить следующий алгоритм поиска улучшенного по отношению к (и(Д),</>д) гарантирующего решения (й,ф) задачи (1.4) такого, что ф <

Алгоритм 1.

0. Полагаем q := 0, гц := 0. Выбираем целое К € [1,+оо) и фиксируем шаг алгоритма Дг :=

1. Решаем задачу линейного программирования (2.2) при г — гп и находим <рг . Если существует иГч € [/г, такое, что Р{С,а} ^ а, то переходим к шагу 3.

2. Присваиваем г(/+х гд + Дг, д :— <7 + 1. Переходим к шагу 1.

3. Полагаем искомое гарантирующее решение {йк, фк) равным текущему решению {ии,<рТч).

Неравенство Р{СГ9} ^ а проверяется с помощью метода Монте-Карло, а, например, для дискретных распределений случайного вектора X с конечным числом реализаций Р{С,?} может быть найдена точно.

Параметр Дг является настроечным параметром алгоритма. Его выбор зависит от размерности задачи, свойств меры Р{-} и т. д. При любом фиксированном К алгоритм по построению сходится за число шагов К. ^ 2К, так как при К. = 1К выполняется г/с = Д, а следовательно, ~Р{СГк} ^ а, так как С С1Х, а Р{5я} ^ а по определению Я. Если Дг = то, несмотря на немонотонность функции Р{СГ} по г, фк будет монотонно не возрастать по К, а следовательно, последовательность фк, в силу ограниченности снизу величиной <рг., будет иметь предел при К —> +оо. Таг ким образом, выбрав достаточно большое Л", получим новое гарантирующее решение задачи (1.4), которое обозначим [й,ф). При этом ф < </?д.

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

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

В качестве начальной многогранной аппроксимации оптимального доверительного множества выбирается множество С = {ж: тах;=щ{Л£й 4- В^х + Ьи] < ф, + В^х + М ^ 0}, где (й,ф) -

гарантиругощее решение, найденное при фиксированном К с помощью алгоритма 1. Рассмотрим следующую задачу линейного программирования:

(й, <р) = arg min ip (2.4)

при ограничениях

max тах{А^ц 4- В^х + Ьц} < ip, тах тах{Л^:ц + В^х + Ьг;} ^ 0.

хес •=1,*1 i=1,кг

Перепишем задачу (2.4) в матричном виде для удобства дальнейшего представления алгоритма. Для этого введем расширенный вектор оптимизационных переменных u1 = col(u, 1р), гарантирующее решение ü1 = col(ü, ф) и введем следующие блочные матрицы и векторы:

е* = (0,..., О, —1) 6 Rn+1,

где е — единичный вектор соответствующей размерности, 0 — нулевой вектор соответствующей размерности, 6i 6 Жк\ Ь2 6 МЧ Обозначим U1 = {и1: А3и ^ Ь3}. Тогда задача (2.4) может быть записана в виде

й1 = arg max elul (2.5)

«'ei/1

при ограничении тах1е^тах;=т^^{(Д')Ты1 + (Bl)Тх ~~ &«■} ^ Справедлива следующая лемма.

Лемма 2.1. Задача (2.5) эквивалентна задаче:

й1 = arg max elv} (2.6)

ü'ei/1

при ограничениях А1«1 < Л1«1, и при этом й1 = м1.

В лемме 2.1 й1 - гарантирующее решение, найденное алгоритмом 1 и участвующее в построении множества С в задаче (2.5). Таким образом, лемма 2.1 позволяет избавится в задаче (2.5) от операции максимизации иох G С.

Идея предлагаемого алгоритма заключается в трансформации исходного доверительного выпуклого множества С путем параллельного переноса его граней с сохранением его вероятностной меры. Изменение границ множества С будет осуществляться в направлении антиградиента критериальной функции в задаче (2.6), как функции правых частей ограничений, получаемой при переходе к двойственной задаче. Антиградиентом является оптимальный вектор двойственных переменных. Для его поиска рассмотрим задачу, двойственную по отношению к (2.6). Она может быть записала следующим образом:

У* = afg minßW + bW + bh3} (2-7)

г,г,г

при ограничениях Afy1 + Ajy2 + Ajy3 = 0, = 1, у> > 0, j = 1,2,3, где

у1 6 К.*1, у2 £ Rk2, у3 6 R*3, у = collj/.y2,?/3) — вектор двойственных переменных,

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

Выделим подвектор у" = col{уи,у2*)- Переставим строки матриц Л1 и В1 и элементы вектора i1 в порядке убывания величии соответствующих им двойственных переменных, т.е. координат подвектора вектора у*. Полученные в результате сортировки матрицы обозначим соответственно Л1, В1, б1, а отсортированный вектор у* обозначим у*.

Пусть I — номер строки матрицы А1.к В1, который соответствует минимальной, отличной от нуля, координате вектора у*. Тогда трансформированное доверительное множество имеет вид £7д = jz: Blx < Ь1 - Л1«1 - д|, где Д е Координаты вектора Д определены следующим образом:

A¡ = T-f-Дь г = 1,1-1, Д/ = -iДа, Д4 = -Д2, i = i + 1, fo + k2. j=i

Здесь Ai, Д2 € R1, Д1 ^ О, Д2 > 0 — некоторые скалярные параметры, при которых выполнено вероятностное ограничение Р^д} ^ а.

Согласно лемме 2.1 улучшенное гарантирующее решение является решением задачи:

и:(Дь Д2) = arg max eV (2.8)

и16 и1

при ограничениях Alv}

г$ Älül + Д.

Целью предложенного в разделе алгоритма является выбор Д} и Д2 таких, чтобы как можно меньшим оказалось гарантирующее значение критерия равное

u^+1(Ai,Ä2) по определению и1, при сохранении ограничения Р{С"д} ^ а. В разде-

'

ле показано, что —«*+1(Дь Дг) < — ф + (г/*)тД. По построению (г/*)тД =

j=i

i

поэтому справедливо неравенство ф — и*+1(Дх, Д2) ^ Vj^j-

j=1

Полученная оценка дает возможность при фиксированном Дх найти границы изменения параметра Д2, в которых значение критерия задачи (2.8) может окаг

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

i

«,11+1(Ai, Д2) < ф, необходимо, чтобы Y1 Щ^з ^ 0- Отсюда получаем интервал инте-

;'=i '

ресующих значений параметра Д2 в виде: [0, Д2],

ё (у))2

Д2 é 2AlJ-^r¡—. (2.9)

v:tv]

3=1

Справедлива следующая теорема.

Теорема 2.2. Пусть для некоторого Aj при Д2 = Ä2 решение задачи (2.8) существует и Р{Сд} ^ а.

Тогда для этого Дх справедливы следующие утверждения:

1) их(Дх, Дг) — решение задачи (2.8) существует для любого Дг € [0; Д2].

2) Дг) непрерывна и монотонно возрастает по Дг £ [0; Дг].

3) функция Р{С"д} полунепрерывна сверху и монотонно не убывает по Дг €

[0;Д2].

4) существует А*2 = тт{Дг € [0; Дг]: Р{Сд} ^ «}.

5) ¡^(Дх) = '^(Дх, Д£) является гарантирующим решением задачи (1.4) при фиксированном значении параметра Дх.

К сожалению, в общем случае функция й*+1(Дх), являющаяся оценкой сверху оптимального значения критерия в задаче (1.4), не является монотонной по Дх- Поэтому задача нахождения нового гарантирующего решения сводится к задаче поиска глобальнохч) минимума функции 'й,\+1(Дх) скалярного аргумента Дх. Скалярность параметра Дх позволяет утверждать, что с вычислительной точки зрения полученная задача существенно проще задачи минимизации по доверительному множеству в (1.5). Кроме того, решение предлагаемой задачи облегчается возможностью указать верхнюю границу Дх, превышение которой параметром Дх точно не будет приводить к улучшению гарантирующего решения.

Для всех г £ {1,...,/ — 1} справедлива следующая оценка: Р{Сд} <

р|ж: В]х - £>■ 4- А\й1 < —г^-Дх Для всех г € {1, ...,£ — 1} определим величины 1 }

1=1

Д™ах, удовлетворяющие уравнениям Д™1Х = тах^Дх > 0: р|а:: В}х - Ц + А}й1 ^ -р^-Дх} > а >. Пусть Дх = тт Д?18*. Тогда если Дх > Дх, то для любого Д2 > 0

£{} J J

выполнено неравенство Р{Сд} < а.

Таким образом, Дх следует искать на промежутке [0; Дх]. Величина Дх может быть вычислена априорно с использованием в общем случае метода Монте-Карло.

Поиск нового гарантирующего решения (йа, фа) осуществляется минимизацией функции й*,+1(Дх) простым перебором на сетке значений скалярного параметра Дх на интервале [0, Дх] с шагом 8 = где Ь — число узлов сетки, выбранное априорно. Теорема 2.2 позволяет предложить для этого следующий алгоритм. Алгоритм 2.

0. Устанавливаем текущее гарантирующее решение и\ := й1, где й1 — гарантирующее решение, найденное алгоритмом 1. Решаем двойственную задачу (2.7). Определяем I. Присваиваем 1о ~ I. Находим Дх и 5 — начальное значение параметра Дх и шаг оптимизации соответственно. Присваиваем Дх := Дх.

1. Если Дх = 0, то переходим к шагу 7.

2. Если при Дг = Дг, где Дг определяется (2.9), справедливо неравенство Р{Сд} < а, проверяемое в общем случае методом Монте-Карло, то переходим к шагу 5.

3. Находим с заранее выбранной точностью £х минимальное Д| из Дг £ [0; Дг] такое, что Р{Сд} > а. Для того можно воспользоваться процедурой, аналогичной

алгоритму 1 , или, имея в виду согласно теореме 2.2 монотонность Р{Сд} по Дг, процедурой, основанной на методе дихотомии, с дополнительной проверкой неравенства

Р{Сд} > а-

4. Решаем задачу (2.8) при Дг = Д-j, находим Если u}t+1(Ai) < uln+1, то полагаем и\ := u1(Ai).

5. Если I > 2, то присваиваем I := I — 1 и переходим к шагу 2.

6. Присваиваем Д1 := Д1 — 0,1 := 1ц и переходим к шагу 1.

7. Полагаем искомое гарантирующее решение uj, := и\.

Для нахождения улучшенного по отношению.к и1 гарантирующего решения достаточно найти любое Дх € [0;Дх], при котором будут выполнены неравенства Р{(7д} ^ а и й^+1(Дх) iC Ип+i- Предложенный алгоритм 2 состоит из заранее выбранного числа шагов L. Поэтому, так как при Дх = О решение задачи (2.8) является гарантирующим, алгоритм 2 за эти L шагов находит некоторое гарантирующее решение исходной задачи (1.4). Заметим, что так как теорема 2.2 доказана в отсутствие каких-либо предположений о законе распределения случайного вектора X, то алгоритм 2 будет работать при любом распределении вектора случайных параметров.

В разделе 2.3 предложен способ сведения одноэталиой задачи стохастического линейного программирования с квантильным критерием для случая дискретного распределения к детерминированной задаче линейного программирования, часть переменных которой булевы. Если случайный вектор X имеет дискретное распределение, оптимальное доверительное множество состоит из реализаций случайного вектора X, суммарная вероятность которых не меньше а. Таким образом, в обобщенно минимаксной задаче (1.5) можно заменить оптимизацию по доверительным множествам на оптимизацию по всем, имеющим вероятностную меру не меньше а, подмножествам множества X = {х": v = 1, N}. Введем вектор 5 g {0,1}л' с координатами <$„, и = 1,N, по правилу:

д 11, если xv S S, " ~ [О, если xv i S,

где S С X. Итак, каждому возможному значению вектора 8 соответствует некоторое подмножество S множества X и наоборот.

Пусть известна величина 7, являющаяся оценкой снизу величин В^х", I — 1,2, i = ITfcb v = 1JV, т. е. 7 «S min,=12.^py {Bfixv}.

v=l,N

Рассмотрим следующую задачу:

ip -* min (2.10)

при ограничениях

' Alu + 7 + ¿„(ßiV ~ 7) + Ьц ^tp,i= 1Л, v = MV, + 7 + ¿„(В^ж" - 7) + h2i < 0, г = и = ljJ, AjiU ^ bsi, г = 1,к3,

N

^ а,

5„ е {0,1}, и = V/V.

-20В задаче (2.10) (п + N + 1) переменных и ((&! + А^ + к3 + 1) ограничений. Пусть (и*,(р*,6*) — оптимальное решение задачи (2.10). Справедлива следующая лемма.

Лемма 2.3 Задачи (1.5) и (2.10) эквиваленты в следующем смысле:

1) оптимальное значение критерия фп в задаче (1.5) равно (р*;

2) и* является оптимальной стратегией в задаче (1.5);

3) одно из оптимальных доверительных множеств в (1.5) имеет вид .5* =

Согласно теореме 1.4 одним из условий существования оптимального решения задачи (1.4) является условие 0 < а < Р*. В связи с этим возникает задача вычисления Р*, которая может быть записана следующим образом:

N

Р^тях'УрЛ (2.11)

1/=1

при ограничениях

А1и + 7 + - 7) + Ь2г < 0, г = I/ = М?,

¿¡/ 6 {0,1}, V = Т^Ж

Справедлива следующая теорема.

Теорема 2.3 Пусть и ф 0. Тогда Р* = Р, если задача (2.11) имеет решение, и Р* = 0 в противном случае.

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

В разделе 2.4 приведены три примера, иллюстрирующие эффективность разработанных алгоритмов. Рассмотрим один из них.

Найдено гарантирующее решение задачи (1.4) алгоритмами 1 и 2 для случая:

и б к2, х ~ що, I), где / ^ (;;),*« (; , *=(}0 _210), *=(_°5),

¿2 =(10 -10) , В2 = (-3 -1), Ьа = (-2) .

В этом примере, используя в качестве стартовой точки гарантирующее решение, найденное алгоритмом 2, удалось применить стохастический квазиградиентный алгоритм оптимизации функции квантили, предложенный А.И. Кибзуном и Е.Л. Матвеевым и позволяющий найти точное решение задачи (1.4). В данном примере указанный квазиградиентный алгоритм сошелся к некоторому решению, которое можно считать приближенным к оптимальному, несмотря на формальное отсутствие обоснования применимости этого алгоритма в нашем случае из-за недифференцируемости целевой функции и наличия дополнительных ограничений, описываемых функцией С}(и,х). Результаты работы алгоритмов отражены в таблице 2.1. Для а = 0,9 улучшение. значения критерия, полученное алгоритмом 2 по отношению к гарантирующему

-21-

Таблица 2.1. Результаты численного эксперимента.

а Алгоритм «1 «2 Ч>

0,0 1 1) 0,3218 18,050

2 0 1,440 14,674

квазиградиентный алгоритм -0,0025 1,337 13,906

решение на ядре 0 2,048 13,306

0,8 1 0 0,2032 13,234

2 0 1,480 8,511

квазиградиентный алгоритм -0,0050 1,084 7,943

решение на ядре >9,, 0 0,6563 6,954

решению, найденному на. доверительном шаре, составляет 22,6% по значению критерия, а отличие гарантирующего значения критерия от оптимального составляет и 5% по значению критерия. Трансформация границ доверительного множества отражена на рисунке 2.1.

Рисунок 2.1. Трансформация доверительного множества.

На рисунке 2.1 изображено изменение доверительного множества для а = 0,8 в результате применения алгоритмов 1 и 2. Оси х\, х2 соответствуют координатам реализации х 6 М2 случайного вектора X. Пунктиром изображено исходное многогранное доверительное множество, внутрь которого вписан доверительный круг. Точками изображены границы множества С, полученного в результате применения алгоритма 1. Сплошные линии соответствуют новому доверительному множеству, най-

денному в результате применения алгоритма 2. Прямая 1 соответствует ограничению бйх — 6«2 + Xi + 2x2 ^ Ф, 2 соответствует щ + йг + lCtei — 10x2 — 5 ^ ф, 3 соответствует 10«! — 10Й2 ~ 3^1 — Х2 — 2^0. Малой окружностью изображена граница ядра гаус-совской меры уровня 0,8, на котором получается оценка снизу оптимального значения критерия, а большой окружностью — граница доверительного круга.

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

В третьей главе представлен новый класс задач стохастического программирования - двухэтапные задачи стохастического линейного программирования с квантильным критерием, и исследованы качественные свойства задач в предложенной постановке. Пусть X — вектор случайных параметров с реализациями х £ X С R'n и заданным законом распределения; Р{-} — вероятностная мера, порожденная распределением случайного вектора X. Двухэтапной задачей стохастического линейного программирования с квантильным критерием в апостериорной постановке называется задача вида:

иа = arg min(cfu + Фа(и)). (3.1)

и е£/

где U = {и £ Rn: А\и SJ 61} — множество допустимых стратегий первого этапа и € К"; cj е 1"- вектор цеповых коэффициентов критериальной функции первого этапа; Ai б М!хп — матрица, задающая ограничения в задаче первого этапа; а 6 (1/2,1) — заданный уровень доверительной вероятности. Обозначим оптимальное значение критерия в задаче (3.1) как ipa = min(cfu + Фа(и)). В задаче (3.1)

и еи

Фа(и) = min{y? G К1: Р{Ф(и,Х) < <р} > а} — функция квантили оптимального значения критерия задачи второго этапа:

imin Y(u, х) Ф 0

i&rM^" f ■ (3.2)

+00, Y(u, х) = 0

где Y(u,x) = {у £ Ш.к: В2У ^ х - А2и, щ > 0, j = 1,£} — множество допустимых стратегий второго этапа у £ К*; А2 € Rmxn, Вг £ — технологические матрицы соответственно первого и второго этапов. Задача (3.1) сформулирована при условиях существования ее решения, которые приводятся далее в виде соответствующих утверждений.

Двухэтапные задачи стохастического линейного программирования в апостериорной постановке с критерием в форме математического ожидания широко известны с середины 50-х годов прошлого столетия. Они используются- для описания процесса принятия решения в экономических системах с иерархической структурой. Как правило исследователь в таких задачах интересуется лишь оптимальным выбором стратегии и, которая затем может быть скорректирована на втором этапе принятия решения по факту возникновения реализации х случайного вектора X. Платой за коррекцию является оптимальное значение критерия задачи второго этапа Ф(и,ж), которая учитывалась в критерии первого этапа в виде средних потерь (математического ожидания

случайной величины Ф(и,Х)). Для получения гарантированного по вероятности результата в данной главе предложен иной способ учета платы за коррекцию в виде функции квантили Ф„(и), то есть уровня потерь, который но может быть превышен с выбранной заранее доверительной вероятностью а.

Рассмотрим множество иг ' (u G (/; Р{Ф(и, X) < 00} = 1}, определяющее множество допустимых стратегий первого этапа, для которых с вероятностью 1 существует решение задачи второго этапа. Из теории двухэтагшых задач с критерием в форме математического ожидания известно, что Ui является выпуклым замкнутым многогранным множеством, а функция Ф{и,х) является полиэдральной (кусочно линейной) выпуклой функцией на Ui х X. Это позволяет утверждать, что функция Ф(и, X) является случайной величиной при фиксированной стратегии первого этапа и для нее определена функция квантили Ф«(и).

В главе рассмотрена также априорная постановка задачи (3.1):

#4= Ф„(и,?/(•)); «,№,(■)) = arg , min■ Ф„(и',?;(•)), (3.3)

где У = Ы-): Mm Rfc | Va: у(х) > 0},

Ф0(«,»(-)) = mm{ip:.P{^u + ^y{X) < ip, А2и + В2у(Х) > X} > а}.

Справедлива следующая теорема

Теорема 3.1. Если существует решение задачи (3.1), тогда задачи (3.1) и (3.3) эквивалентны в следующем смысле:

1) для любого иа, оптимального в (3.1), найдется уа{-) такая, что пара (■иа,уа(•)) является оптимальной в задаче (3.3);

2) для любой пары (и'а, у,,(■)), оптимальной в задаче (3.3), и'а является оптимальной в задаче (3.1);

3) <ра = ц/а.

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

В главе приводятся ряд утверждений, характеризующих качественные свойства исследуемой задачи (3.1). Обозначим V = {v G.ffiL"1: Bjv < с2, Vi ^ 0,?' = 1 ,m} — множество допустимых значений переменных в задаче двойственной к (3.2). Рассмотрим конусы рецессивных направлений многогранных множеств U н V соответственно: 0 +U = {« 6 К", Ах и > 0} и 0+V 4 {« 6 Еш, Bv < 0}, где Аг = с ol(AuI), В2 = сol(Bj,I2), I2 = —Ii, I и Ii — единичные матрицы размерности (n х п) и (т х т) соответственно.

Справедлива следующая теорема:

Теорема 3.2. Если U ^ 0, то функция Фа(и) полунепрерывна снизу nou&U для любого а G (0,1).

Данное утверждение позволяет предложить достаточные условия существования решения задачи (3.1).

Теорема 3.3. Если U\ ф 0 и 0+U = {О1}, то решение задачи существует для любого а 6 (0,1) и оптимальное значение критерия конечно.

-24В теореме (3.3) О1 6 R" — пулевой вектор соответствующей размерности, а условие О +U — {О1} гарантирует ограниченность множества допустимых стратегий U. Условия выпуклости функции Фа(и) устанавливает следующая теорема:

Теорема 3.4. Если t/j ф 0 и Р{-} квазивогпута, то функция квантили Фа(и) выпукла по и £ Ui для любого а € (0,1).

Гарантировать выпуклость функции Фа(«) на множестве U можно лишь в случае, когда U = U\. Достаточные условия для этого равенства устанавливает следующая лемма

Лемма 3.4. Если Q+V = {б2}, V ф0,то11 = UV

Условия леммы 3.4 в совокупности с U Ф 0 являются, в частности, достаточными условиями существования решения задачи (3.1).'Достаточные условия непрерывности функции Фа(и) устанавливает следующая теорема.

Теорема 3.5. Если U\ ф 0 и Р{-} имеет ограниченный носитель, то функция квантили Фи(и) непрерывна noue U\ для любого a S (0,1).

Очевидно, что совокупность условий теоремы 3.5 и леммы 3.4 обеспечивают

непрерывность Фа(и) на U ф 0.

В главе предложены методы решения двухэтапной задачи стохастического линейного программирования с квантильным критерием. В случае скалярности случайного параметра задачи (3.1) в главе предложен детерминированный эквивалент для этой задачи:

(м1<у1) = argmin(e[u + cj'</), (3.4)

при ограничениях: А2и + В2у>ха, Aiu<bu у > 0, где ха — квантиль уровня а распределения случайной величины X. Справедлива следующая теорема.

Теорема 3.6. Если 0+V = {б2}, V ф 0, 0+U = {01} и X скалярная случайная величина с известным законом распределения, то для любого а 6 (0,1) задачи (3.1) и (3.4) эквивалентны, т.е. является решением задачи (3.1) и <ра = cïula + cIvl.

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

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

ûa = argmin(cjii + max min cÇy), (3.5)

«et/ xç.Ea yeY(u#)

где Ea — некоторое фиксированное а-доверительное множество.

Воспользовавшись эквивалентным переходом к двойственной по отношению к (3.2) задаче, можно записать (3.5) в следующей эквивалентной форме:

ûa = argmin(c7w + max (х - A2u)Tv). (3.6)

ueU xeEa,vev

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

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

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

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

Рассмотрим задачу двойственную к (3.2)

Ф(и, х) = max{(i - A2u)tv}, (4.1)

veV

где V={d6 Rm: B\v ^ C2, f,- ^ 0, г = 1, rn} — по-прежнему множество допустимых стратегий второго этапа.

Так как множество V является компактным многогранником, критериальная функция (х — /12m)tv билинейна по х и v, функция Ф(и, х) может быть записана в следующем эквивалентном виде:

Ф (u; х) = max (z - -A2u)V , (4.2)

i=I7

где {V, г — 1,1} — вершины множества V.

Обозначим fli^j.Be R(m+*)xm) Д А ^ ; .. : ^ , Д £ ¡Г»™.

Найдем множество G, состоящее из всех вершин множества V. Пусть Вв е Rmxm — базисная подматрица (невырожденная квадратная подматрица т х т матрицы В), В^ е j^fcx-rrt _ подматрица матрицы В, составленная из строк В, которые не вошли в соответствующую базисную подматрицу В\

Рассмотрим вектор сг = ( с^ 0)т , Сг € Rm+i:. Пусть св € R"' — подвектор вектора сг, составленный из. тех элементов сг, номера которых совпадают с номерами строк матрицы В, вошедшими в матрицу Вв. Пусть с1^ € Rk — соответствующий подвектор вектора ¿2, составленный из элементов £2, которые не вошли в св. Тогда множество G представимо в виде G = {-у* € V, Вви% = св, B^v' < с^, i — 1, /}.

Таким образом, для нахождения всех вершин множества V необходимо перебрать I < невырожденных квадратных подматриц матрицы В, последовательно решая системы:

BBv = с'д, BLv < г'

(4.3)

ЧГ - "в-

Заметим, что задача поиска всех вершин множества V решается априорно, независимо от решения исходной двухэтапной задачи квантильной оптимизации, так как множество V не зависит от х и и.

Таким образом исходная двухэтапная задача стохастического линейного программирования с квантильным критерием (3.1) эквивалентна следующей

иа = argmin-fc^« + min{^ : P{max (х — Л2ы)тг/ <</?}> а}}. (4.4)

ueu i=u

Введем в рассмотрение функцию Фх(м, x) = maxi=^ ({cj — (vl)TA2)u + (иг)тх). Рассмотрим также функцию квантили Фв(и) = min{^ : Р{Фх(и, X) < <р) > а).

Тогда задача (3.1) эквивалентна следующей одноэтапной задаче стохастического линейного программирования с квантильным критерием

иа = а^ттФа(ы). (4.5)

ueic

Заметим, что переход к одпоэтаппой задаче совершен без каких-либо предположений относительно закона распределения вектора случайных параметров. Заметим также, что задача (4.5) является классической задачей квантильной оптимизации без дополнительных вероятностных ограничений, детально изученной в монографиях Ки-бзуна А.И. и Кана Ю.С.

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

фа = min (сТи + ф}(xj - A2u)tv1 <ф,г = TJ,j = 177), (4.6)

и

где {xi}j=l — вершины многогранной аппроксимации Е = {х : W{X < Zi,: i — 1,L} оптимального доверительного множества.

Анализ эквивалентной одноэтапной задачи (4.5) позволяет на основе доверительного метода сделать вывод о структуре оптимального доверительного множества. В качестве строк матрицы W должны быть выбраны векторы, задающие координаты вершин многогранного множества V, то есть Wj — vl,i = 1,1. Величины Zi,i — 1 ,L изначально могут быть выбраны в результате вписывания в многогранное множество {ж : W{X < Zi,: г = 1,L} доверительного шара, а затем уточнены с помощью алгоритма 1 оптимизации по радиусу этого шара. Дальнейшее уточнение полученной аппроксимации оптимального доверительного множества может быть осуществлено с помощью алгоритма 2.

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

Для иллюстрации природы многопериодных двухэтапных задач рассмотренная в разделе модель снабжена экономической интерпретацией в форме задачи управления ресурсами. Введем следующие обозначения: п - число плановых периодов; и 6 Ы1 - планируемое количество единиц собственного ресурса (целочисленная переменная первого этапа); С\ - стоимость содержания (эксплуатации, обслуживания) единицы собственного ресурса в период, приходящаяся на единицу удовлетворяемого им спроса; С2 - стоимость аренды единицы ресурса в период, приходящаяся на единицу удовлетворяемого им спроса; с - цена покупки единицы ресурса; у[ - объем спроса, удовлетворяемый собственным ресурсом в ] - й период; -у^ - объем спроса, удовлетворяемый арендованным ресурсом в у - й период; X* - случайная величина спроса, которую необходимо удовлетворить в 3 - й период; И - объем спроса, удовлетворяемый единицей собственного ресурса.

Предполагается, что компоненты случайного вектора X = (Хг,Х2,... ,Хп)т независимы и имеют нормальное Ы(т]х,а]х), j — 1,п распределение. Единицы собственного ресурса приобретаются до начала планируемого периода, а в случае их нехватки для удовлетворения случайного спроса некоторое количество единиц ресурса нанимается дополнительно в этом плановом периоде по более дорогой цене.

Задача второго этапа выглядит следующим образом:

(4.7)

2/2 + 2/1 >

тА/О < и, (4.8)

1/Ы>0,

где х = (х1, х2,..., хп)Т, х'■> - реализация случайной величины X1. Первое ограничение в (4.8) обусловлено тем, что издержки за аренду единицы ресурса меньше, чем прибыль, полученная при удовлетворении части спроса с помощью единицы ресурса, то есть спрос выгодно удовлетворять весь.

Рассмотрим функцию квантили

Фа(и) = пнп{<р : Р{Ф(и, х) < <р} > а}, (4.9)

где Р{-} - вероятностная мера, порожденная распределением случайного вектора X = (X1, X2,..., Хп)т. Тогда, окончательно, двухэта.пная задача квартальной оптимизации может быть сформулирована в следующем виде:

Iра = тш(си + Фа(м)); иа = а^тт(си + Фа(и)).

■ц>0 и

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

Ф (и, х) = 1шп V Ыс! + г4с2]

при ограничениях

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

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

В разделе 5.1 предложен алгоритм поиска гарантирующего решения, основанный на методе двойственных отсечений. Пусть U ф 0 и выполнены условия леммы 3.4, а X — дискретный случайный вектор с конечным числом возможных реализаций х € X = {xv g Rm, v = 1 , L} и заданными вероятностями реализаций Р{Х = х"}=р„, v=l,L.

Для дискретного распределения с конечным числом реализаций доверительное множество Е g £а для любого а G (0; 1) состоит из конечного набора реализаций случайного вектора X.

Зафиксируем доверительное множество Eq = {xv € X, и £ J9}, где Jq — множество индексов реализаций случайного вектора X, принадлежащих доверительному множеству Eq. Пусть по-прежнему. G множество вершин {г>'}(=1 многогранного множества V. Пусть 0+V = {0 }, V ф 0, тогда V — выпуклый компакт, поэтому так как критериальная функция (ж — Лги)тг; билинейна по х и v, а Ед состоит из конечного числа элементов, задача поиска гарантирующего решения двухэтапной задачи (3.1) может быть записана в следующем виде

üa = arg шт{с7« + тр(и)}, (5.1)

где ф(и) = _тах (х" — Atu^v*. Пусть фа = cjüa + ф(йа).

■i=i,i, veJq

В силу выпуклости и непрерывности ф{и) как максимума линейных функций и компактности множества U гарантирующее решение, построенное описанным выше образом, существует для любого доверительного множества Eq £ £а.

Зная вершины Vх, г — 1,1, многогранника V, задачу (5.1) можно записать в виде следующей, эквивалентной по стратегии йа, задачи линейного программирования

(йа, фа) = arg min {cju + ф\(з? - Л2и)ти1 < ф, г = l77, и & JJ. (5.2)

Число ограничений в задаче (5.2) может оказаться весьма большим. Однако можно предложить следующую процедуру уменьшения числа ограничений.

Из I х d(Jq) ограничений в задаче (5.2), где d(Jq) — число элементов множества Jg, будем рассматривать только I, оставив для каждого v%, г — 1,1, лишь тот для которого справедливо: (г/'У^х"^') > (ul)T(x"), W g Jq, i> ф v(i). Если я"'1) определяется не единственным образом, то выберем ту реализацию вероятность которой меньше. Если же таких реализаций несколько, то выберем любую из них.

Очевидпо, другие ограничения в задаче (5.4), соответствующие вершине ?/', можно не рассматривать как заранее пассивные.

Для удобства введем следующие обозначения:

/ („уд, \

A3 = I ••■ I — матрица размерности (I х п), Ф = (ф,t/?)T € Е7,

V Ь'ТЛ2)

Ьз = col{(vi)T3;1'^'} — вектор-столбец размерности (I х 1). Тогда задачу (5.2) можно записать в следующем матричном виде:

(,йа,фа) - argmin{cfw + ф}, (5.3)

¡>

при ограничениях: A-ju + Ф > Ьз, А\и < bi.

Задача линейного программирования (5.3) позволяет получить гарантирующее решение и„ исходной задачи. Остается открытым вопрос о выборе доверительного множества Eq. Рассмотрим двойственную по отношению к (5.3) задачу:

z(Eq) = arg max {[&J| - 6j] z} ,

tU* = h_

^¡>0, ¿ = 1, (/ + /),

где z(Eq) 6 R;+i — оптимальный вектор двойственных переменных, [•]•] — блочная матрица, Eq — некоторое доверительное множество, позволяющее получать оценку сверху оптимального значения критерия. Из теории двойственности известно, что каждой ненулевой координате вектора z(Eq) соответствует некоторое активное ограничение прямой задачи. Кроме того, изменение свободного члена ограничения, которому соответствует максимальная координата вектора z(Eq) оказывает наибольшее влияние на оптимальное значение критерия прямой задачи.

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

0. Проверить выполнение требуемых для функционирования алгоритма условий (V ф 0, 0+V = {01}, 0+1/ = {0}), задать уровень доверительной вероятности а, присвоить q := 0. Выбрать множество Е0, состоящее из всех возможных реализаций вектора X в качестве начального приближения оптимального доверительного множества. Таким образом, d(Jo) = L, a. P(i?o) = 11. Решая системы (4.3), найти все вершины множества V, перебрав С%+к квадратных базисных подматриц матрицы В.

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

3. Решить задачу линейного программирования (5.3) и получить текущее гарантирующее решение uq исходной задачи. Обозначим через (pq получаемую на этом решении оценку сверху оптимального значения критерия задачи (3.1).

4. Решить двойственную к (5.3) зада.чу (5.4), произвести сортировку по убыванию координат вектора z(Eq) и определить соответствие ограничений задачи (5.3)

отсортированным координатам вектора z(Eq). Каждому ограничению задачи (5.3) соответствует реализация xn^q\ t = 1.J случайного вектора X. В силу того что на шаге 2 произведено исключение пассивных ограничений, реализации хп<л\ t = 1..I определяются единственным образом. Далее задать параметр ц = 1 и перейти к шагу 5.

5. Определить новое доверительное множество Eq+\ путем исключения из доверительного множества Eq реализации Eq+\ := Eq\xr^q\ Если P(ß9+i) < а и д = I, то перейти к пункту 6. Если P(B9+i) < а и ц < I, то присвоить ¡л := ц + 1 и снова перейти к шагу 5. В противном случае переприсвоить значения параметров q и Jq следующим образом: q :— q + 1, Jq := Jq\fi- Затем перейти к шагу 2.

6. В качестве аппроксимации Еа оптимального доверительного множества взять Eq. В качестве искомого гарантирующего решения йа положить и4.

Справедлива следующая теорема

Теорема 5.1 Если Q+V = {б1}, V -ф- 0, 0+U = {6} и дискретный случайный вектор X имеет конечное число реализаций х", v = 1,L, то для любого а € (0; 1) справедливо:

1. предложенный алгоритм сходится за конечное число шагов q* < L к гарантирующему решению uq' исходной двухэтапной задачи (3.1);

2. для любого q = 0,g* — 1 выполняется: <ра < < V®. В разделе 5.2 выделен подкласс двухэтапных задач квантильной оптимизации, для которых выполнены условия леммы 3.4. Для задач этого класса предложен метод поиска точного решения, основанный на сведении исходной двухэтапной задачи стохастического линейного программирования с квантильным критерием и дискретным распределением случайных параметров к детерминированной задаче линейного программирования, часть переменных которой являются булевыми. Согласно доверительному методу исходная двухэтапная задача (3.1) при дискретном распределении случайных параметров эквивалентна по стратегии первого этапа следующей минимаксной задаче

(иа,Ю = агк min {c7u + max (х" - А2u)Tv'},

где хи 6 J(E) — реализации случайного вектора X принадлежащие доверительному множеству Е из семейства а-доверительных множеств £а, а v', i = \,I — вершины многогранного множества V допустимых значений двойственных переменных в задаче второго этапа. Эта задача может быть записана в следующей эквивалентной по (иа, Еа) форме

(иа,Еа, фа) = arg min {c^u + ф}, (5.4)

иеи,Ее£а.ф

при ограничениях (х" — Лги)^' < 'ф, v е J{E), г = 1,1.

Введем, как это было сделано в разделе 2.3 вектор S G {0,1}L с координатами 8U, v = 1, L, по правилу:

А 11, если х" 6 Е, и ~~ 1 0, если xv <£ Е.

Каждому возможному значению вектора S соответствует некоторое подмножество Е множества X и наоборот. Тогда минимизация но Е £ £„ в задаче (5.4) может быть заменена на минимизацию по вектору 6. Найдем величину 7, являющаяся оценкой снизу величин (xi')Tx;I> г = 1,7, и = 1,7/, т.е.

7 С min (г^г/).

¿=17 L J ■

Тогда (5.4) эквивалентна по стратегии (иа, фа) следующей задаче линейного программирования

{ип,6п, •</>«) = arg min {cju + 'ф}, (5.5)

иеи,б,-фе W

при ограничениях

7 + ¿„(Л' - 7) - (Аги)Ч < V», v = 171, г = 177

L

У^ t>vPv > а,

е=1

€ {0,1}, i/= lTZ.

Задача (5.5) может содержать большое количес.тво ограничений и значительное количество переменных. Число переменных булевого типа равно количеству возможных реализаций случайного вектора X. Однако оптимальное значение части координат вектора 5 можно определить заранее, аналогично тому, как это было сделано в разделе 2.3.

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

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

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

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

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

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

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

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

Основные результаты, выносимые на защиту

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

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

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

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

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

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

7. Решены несколько прикладных задач стохастического линейного программирования с квантильным критерием, в том числе задача оптимизации функционирования летного парка авиакомпании и задача логистики для авиационного грузоперевозчика [3-5,7,8].

Публикации в изданиях, входящих в перечень ВАК

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

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

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

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

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

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

7. Наумов A.B., Богданов А.Б. Решение двухэтапной задачи логистики в квантильной постановке. // Автоматика и телемеханика:. — 2006.— № 12.— С. 36-42.

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

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

10. Наумов A.B., Иванов С.В. Алгоритм оптимизации, квантильного критерия для полиэдральной функции потерь и дискретного распределения случайных параметров. // Автоматика и телемеханика. — 2012. — № 1. — С. 95-108.

11. Наумов A.B., Бобылев И.М. О двухэтапной задаче стохастического линейного программирования с квантильным критерием. // Автоматика и телемеханика,- 2012,- № 2. С. 61-72. .

Публикации по теме диссертации в других изданиях

12. Наумов A.B., Иванов С.В. Задача распределения инвестиций в развитие отраслей наземного космического комплекса. // Электронный журнал "Труды МАИ".- 2012.-№50.

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

14. Kibzun АЛ., Naumov А. V. Optimal Investment to the Regional Water-Supply System // Proceedings of International Conference Mathematics, Computer, Control and Investments. — Russia, Moscow, 1993. — Pp. 72-78.

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

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

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

18. Naumov A.V. Linear Two-Stage Quantile Optimization Problem. // 15th International Simposium on Mathematical Programming.Program and Abstracts.— The University of Michigan, Ann-Arbor, USA, August 15-19, 1994.— Pp. 152.

19. Кибзун А.И., Наумов A.B., Уланов C.B. Оптимизация распределения грузоперевозок с учетом случайного грузопотока и случайных характеристик транспортных средств. // Тезисы Международной Конференции "Бортовые интегрированные комплексы и Современные проблемы управления", — Россия, Ярополец, 8-11 июня, 1998.

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

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

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

23. Наумов A.B. Алгоритм решения целочисленной задачи квантильной оптимизации. // Тезисы 6-ой международной конференции "Системный анализ, управление и навигация", — Крым, Евпатория, 2001.

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

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

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

-3627. Наумов A.B., Богданов А.Б. Решение двухэтапной задачи стохастического линейного программирования с квантильным критерием для логистической компании. // Тезисы 11-ой.международной конференции "Системный анализ, управление и навигация", — Крым, Евпатория, 2005. М: МАИ-ПРИНТ, — С. 81

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

29.' Кибзун А.И., Наумов A.B. Алгоритм нахождения гарантирующих решений в линейных моделях квантильтной оптимизации // Тезисы 14-ой международной конференции "Системный анализ, управление и навигация",— Крым, Евпатория, 2009, М: МАИ-ПРИНТ, - С. 100

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

31. Наумов A.B., Семенова Н.В. Алгоритм нахождения гарантирующего решения двухэтапной задачи квантильной оптимизации начальных инвестиций в проект. // Тезисы 7-й международной конференции "Авиация и космонавтика 2008",- Россия, Москва, 20-23 октября, 2008, М: МАИ-ПРИНТ,- С. 81

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

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

Множительный центр МАМ (НИУ) Заказ от2,8J2. 2011 г- ТиражвО экз.

Введение

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].

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

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

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

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

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

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

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

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

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.