Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

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

Диссертация, - 480 руб., доставка 1-3 часа, с 10-19 (Московское время), кроме воскресенья

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Наумов, Андрей Викторович. Методы и алгоритмы решения задач стохастического линейного программирования с квантильным критерием : диссертация ... доктора физико-математических наук : 05.13.01 / Наумов Андрей Викторович; [Место защиты: ГОУВПО "Московский авиационный институт (государственный технический университет)"].- Москва, 2012.- 221 с.: ил.

Введение к работе

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        Апробация работы. Результаты диссертации докладывались на научных семинарах кафедры теории вероятностей Московского авиационного института (рук. проф. Кибзун А.И.), кафедры математической кибернетики Московского авиационного института (рук. проф. Пантелеев А.В.), научном семинаре лаборатории № 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 научных статьях, опубликованных в журналах, входящих в перечень ВАК. Помимо этого, результаты частично опубликованы в других журналах, сборниках статей и трудах конференций на русском и английском языках, общее число публикаций - 32.

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

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