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

• Иванов, Сергей Валерьевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Иванов, Сергей Валерьевич

Оглавление

Введение

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

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

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

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

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

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

лидера и последователя

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

в скалярном случае

1.7. Выводы по главе 1

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

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

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

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

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

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

2.2.2. Алгоритм улучшения известного гарантирующего решения

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

2.3.1. Пример задачи с дискретным распределением случайного вектора

2.3.2. Применение алгоритма, основанного на методе Бендерса

2.3.3. Пример задачи с гауссовским распределением случайного вектора

2.4. Выводы по главе 2

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

3.1. Задача оптимизации деятельности транспортного узла

3.1.1. Постановка задачи

3.1.2. Исследование модели в случае одного направления

3.1.3. Исследование модели в случае отсутствия конкуренции

3.1.4. Исследование модели в общем случае

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

3.2. Задача оптимизации структуры наземного космического комплекса

3.2.1. Описание математической модели

3.2.2. Исследование модели в случае отсутствия дополнительного инвестирования

3.2.3. Исследование модели в случае постоянных цен

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

3.3. Задача оценки эффективности проектов, направленных на экономию электроэнергии в интересах крупного предприятия

3.3.1. Описание математической модели

3.3.2. Анализ модели

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

3.4. Выводы по главе 3

Заключение

Список литературы

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

Введение

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

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

Впервые двухуровневая задача была рассмотрена Г. фон Штакельбергом при изучении моделей рынка [128]. однако интенсивное изучение данных задач приходится на последние три десятилетия. Основные результаты теории двухуровневых задач содержатся в монографиях Дж. Барда [58], Ш.Демпе [83] и обзорах Ш.Демпе [81,82], Л.Н.Висенто, П. Каламая [133] и Б. Колсона, П. Маркотте, Ж.Савара [75,76].

Приложения задач двухуровневого программирования имеют место в самых разнообразных отраслях. Иерархические модели экономики рассматривались в работах Ян Хая, М.Белла [141], транспортная задача изучалась X. Абу-Кандилом и П.Бертраном [55], задача проектирования сетей рассматривалась П. Маркотте [108] и И. Констанином, М. Флорианом [77], модели алю-

4

миниевой промышленности изучались М.Г. Николсом [110]. Задача конкурентного размещения предприятий в форме двухуровневой задачи целочисленного программирования изучалась в работах В. JI. Береснева [1], В. JI. Береснева, А. А. Мельникова [2], А. В. Кононова, Ю. А. Кочетова, А. В. Плясунова [37].

Приведём классическую постановку задачи двухуровневого математического программирования [58,83]. Пусть и £ U — стратегия верхнего уровня (стратегия лидера), U Cl" — множество допустимых стратегий задачи лидера. При выбранном и оптимальная стратегия нижнего уровня у* (и) £ У (и) — = {у £ Rfc | в(и,у) ^ 0} (стратегия последователя) является решением следующей оптимизационной задачи, называемой задачей нижнего уровня (задачей последователя):

у*(и) £ Y*(u) = Arg min в(и, у), (0.1)

y&Y{u)

где ©(•): Rn х Rfc —R1 — целевая функция задачи последователя, У {и) — множество допустимых решений задачи последователя, в(и, у): М" х Rfc —> Rm — функция, задающая ограничения задачи последователя. Множество оптимальных стратегий последователя Y*(u) может состоять не из одного элемента. Лидер при выборе своей стратегии может учитывать как наилучшую, так и наихудшую для себя стратегию последователя. В связи с этим выделяют оптимистическую и пессимистическую постановку задачи двухуровневого программирования [83].

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

min Ф(и. у*(и)) -> min, (0.2)

¡ЛО)еУ'(и) ' uzu' у 1

где Ф(-): R" х Rfc —у R1 — целевая функция задачи лидера. В задаче (0.2) предполагается, что последователь выбирает из своих оптимальных стратегий наиболее благоприятную для лидера.

Учёт наименее благоприятной для лидера оптимальной стратегии последователя порождает задачу лидера в пессимистической постановке:

тах Ф(и, у'(и)) -> min. (0.3)

y*{u)eY*{u) и&и v >

Большинство работ в области двухуровневого математического программирования посвящены изучению оптимистической постановки (0.2). Для решения задачи (0.2) обычно переходят к одноуровневой задаче условной оптимизации. Для этого используются необходимые условия Каруша-Куна-Таккера оптимальности стратегии нижнего уровня [83]. Если для каждой фиксированной стратегии лидера и задача последователя является задачей выпуклого программирования, то данные условия являются не только необходимыми, но и достаточными условиями оптимальности. В этом случае эквивалентная одноуровневая задача принимает следующий вид:

Ф(и.у)min (0.4)

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

Vlje(u;y) + vTVye(u,y) = о, 0(у./и) ^ 0, утв(и,у) = 0, v ^ 0,

где v — вектор двойственных переменных.

Трудность решения полученной задачи заключается в наличии равновесных ограничений vT6(u,y) = 0. Нетрудно заметить, что для выполнения этого ограничения необходимо выполнение либо равенства ьг — 0, либо равенства et(u,y) = 0, г = 1.ш. Таким образом, для решения задачи (0.4) могут быть применены алгоритмы, основанные на методе ветвей и границ. Данные алгоритмы представлены в работах Ф. А. Аль-Хайяля, Р. Хорста, П. М. Пардалоса [56], Дж. Барда, Дж. Мура [60], Дж. Барда, Дж. Фалька [59], X. Фортуни-Амата, Б. Маккарла [86], Т. Эдмундса, Дж. Барда [85].

Как и для широкого класса задач условной оптимизации, для решения двухуровневых задач используются методы штрафных функций. Данные методы предлагались в работах В. Ф. Демьянова, Ф. Факкинея [7], Ё Исидзуки, Э. Айёси [94], А. С. Стрекаловского, А. В. Орлова, А. В. Малышева [129].

Методы спуска для решения задач двухуровневого математического программирования предлагались, например, в работах Ж. Савара, Ж. Говина [123], Л. Н. Висенто, Ж. Савара, Ж. Ж. Жудисе [134], Хань Цзия, Лю Гошаня, Ван Шоуяна [91].

Ввиду того, что экономические системы, как правило, описываются линейными моделями, отдельного рассмотрения заслуживает класс линейных задач двухуровневого программирования, рассмотренный, например, у У. Биаласа, М. Карвана [64]. Линейная задача двухуровнего программирования является частным случаем задачи двухуровневого программирования при

У) = с2 У.

и — {и | Аги ^ 61}, ¥{и) = {у | А2и + В2у ^Ъ2)у> 0}.

и в оптимистической постановке имеет вид

+ тт (0.5)

кес/, у €У (и)

где

У* (и) = Arg min {¿¡у | А2и + В2у > b2, у ^ 0}, и

ие!" — стратегия лидера, у* £ Ж — оптимальная стратегия последователя, С! £ Rn, Ах £ Rlxn, 61 £ R1, с2 £ Rk, f £ Rk, А2 £ Rmxn, В2 £ Rmxk, b2 £ Mm.

В монографиях Дж. Барда [58], Ш.Демпе [83] сформулированы необходимые и достаточные условия оптимальности стратегии нижнего уровня и приведены методы решения данных задач. При использовании условий Каруша-Куна-Таккера (условий дополнительной нежёсткости) эквивалентная одноуровневая задача принимает вид

cju + /ту -> min (0.6)

u.y.v

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

A2u + B2y ^ b2, Bju ^ c2, vt(A2u + B2y - b2) = 0, yT(Bjv - ca) = 0, 0,

v ^ 0.

Решение данной задачи требует использования методов невыпуклой оптимизации. Однако, при некоторых предположениях полученная задача может быть сведена к смешанной целочисленной задаче линейного программирования. Данный метод был предложен X. Фортуни-Аматом и Б.Маккарлом [86]. Полученная задача может быть решена, например, методом ветвей и границ, что было предложено Ш. Оде, Ж.Саваром, В. Згалом [57].

Альтернативным подоходом к решению линейной двухуровневой задачи, предложенным Цзя Фучэнем, Ян Фэнмэем, Ван Шоуяном [96], является использование необходимых и достаточных условий оптимальности переменных задач последователя и двойственной к ней. Рассматривается задача

cju + vT(b2 - A2u) min (0.7)

11.у,V

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

Аги ^ ьь A2v + В2у ^ Ь2, Bjv ^ с2, cjv + fTy ^ h, У^о, v ^ 0.

При фиксированном h данная задача является задачей квадратичного программирования при линейных ограничениях. Из теории двойственности задач линейного программирования известно, что критериальная функция в задаче (0.7)

всегда неотрицательна. Если оптимальное решение задачи (0.7) обеспечивает нулевое значение критериальной функции, то соответствующие компоненты решения являются допустимыми в задачах последователя и двойственной к ней. Для поиска оптимального решения линейной задаче двухуровневого программирования необходимо найти минимальное значение h, при котором оптимальное значение критериальной функции в задаче (0.7) равняется нулю.

Разработке численных методов решения задачи (0.5), основанных на методах невыпуклой оптимизации посвящены работы А. С. Стрекаловского, А. В. Орлова, А. В. Малышева [51,129], Т. В. Груздевой, Е. Г. Петровой [6].

Для линейной двухуровневой задачи было доказано [64,68], что её решение достигается в вершине многогранного множества. Этот факт используется для построения алгоритмов решения задачи, основанных на переборе вершин многогранного множества, которые были предложены У. Кэндлером, Р. Таунслеем [68], Хоанг Туем. А. Мигдаласом, П.Вербрантом [131].

Стохастическая постановка задачи двухуровневого программирования впервые была предложена в работе М. Патрикссона и JL Винтер [114]. Данная постановка (в несколько более общей формулировке) имеет вид

М[Ф(м,у*(м.Х))1min (0.8)

aeu.y'i, )

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

у*(и,х) G Arg min Q(u,y,x),

где X — случайный вектор с реализациями х. В [114] был предложен алгоритм поиска локального оптимума. В работе С. Кристиансена, М. Патрикссона и JI. Винтер [74] были изучены свойства данной задачи. Изучению стохастической двухуровневой задачи, в которой стратегия последователя выбирается, исходя из условия минимума критериальной функции в форме математического ожидания, также посвящена работа А. С.Вернера [138]. В [138] приведены достаточные условия существования решения поставленной задачи, разработан алгоритм поиска локального оптимума, а также приводятся приложения сто-

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

Стохастическая двухуровневая задача с бинарными переменными последователя рассматривалась О. И. Озалтыном, О. АПрокопьевым и А. Й. Шефером в [112], где был предложен метод ветвей и границ для решения данной задачи.

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

Одна из возможных формулировок общего вида стохастической задачи двухуровневого программирования была предложена в обзоре Р. М. Ковачевича, Г. X. Пфлуга [105]. Данная постановка имеет следующий вид:

ф(и(Х):у(и(Х),Х).1Х)]^ min (0.9)

О'У'(-)

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

у*ы-),-)е Arg min 5[0(u(X),y(u(X),X),X)];

y(u(-),-)eY(u)

где X — случайная величина с реализациями х, определённая на вероятностном пространстве (Г2, Л, Р), £, Í? — некоторые вероятностные функционалы. Стратегия лидера и(-) и стратегия последователя у(и(■), •) ищутся в классе функций, измеримых относительно сг-подалгебр Т. Q (Т С Q) сг-алгебры Л соответственно. В качестве вероятностного функционала могут быть выбраны математическое ожидание, вероятностный и квантильный критерии [22], интегральная квантиль [36,115,118,119].

В [105] решение задачи (0.9) было найдено лишь для частной задачи с ограничением на значение интегральной квантили. В работе Чэн Лу, Вань Чжунпина, Ван Гуанминя [73] изучалась двухуровневая задача с критерием в форме интегральной квантили. Вероятностный критерий для задачи

стохастического двухуровневого программирования предлагался М. Сакавой, X. Катагири, Т. Мацуи [122]. Частный случай двухуровневой задачи с кван-тильным критерием рассматривался в работе А. Чена. Ч. Кима, Чжун Чжоу, П. Чутинана [72] в контексте задачи проектирования сетей с заданным уровнем надёжности. Для решения задачи был предложен генетический алгоритм. В работе X. Катагири, Т. Уно. К. Като и др. [99] рассмотрена двухуровневая задача в стохастической постановке с квантильным критерием для гауссовского распределения.

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

min{</> | Р{Ф(и, X) ^ ф, Q(u. X) < 0} ^ а} -> min, (0.10)

u£U

где Ф(-) — целевая функция потерь, Q(-) — функция, задающая дополнительное ограничение, а — уровень доверительной вероятности, и — оптимизационная стратегия, X — случайный вектор с реализациями х.

Исторически данная задача возникла из задач стохастического программирования с вероятностными ограничениями, изучавшихся А. Чарнсом, У.У.Купером [69,70], С. Гартской [89]. Т. Сантаи [130], А. Прекопой [116,117]. Впервые задача оптимизации функции квантили была рассмотрена в работе С. А. Катаоки [100]. Основные результаты теории и практики решения задач с вероятностным и квантильным критериями изложены в монографиях А. И. Кибзуна, Ю. С. Кана [22,101|.

Одним из основных методов решения данной задачи является обобщённый минимаксный подход, предложенный А. И. Кибзуном, В.В.Малышевым [24,38] и названный позднее в монографиях А. И. Кибзуна, Ю. С. Кана [22,101] доверительным методом. Суть метода заключается в переходе к детерминированной минимаксной задаче. Внутренний максимум в этой задаче берётся

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

Для поиска точного решения решения задачи (0.10) могут быть применены методы, основанные на процедуре стохастической аппроксимации. Данные методы изложены в работах А. И. Кибзуна, Ю. С. Кана [22,101], А. И. Кибзуна, В. Ю. Курбаковского [23], А. И. Кибзуна, Е.Л.Матвеева [25,102], Ю.С.Кана [20,21]. Недостатками данных методов являются низкая скорость сходимости и невозможность их применения для широкого класса задач.

В ряде частных случаев значение функции квантили может быть вычислено аналитически, что является основой для перехода к детерминированному эквиваленту. Метод детерминированного эквивалента для задач стохастического программирования с квантильным критерием был исследован Б. В. Вишняковым, А. И. Кибз}чюм [4]. Однако класс задач, к которым этот метод применим, является достаточно узким.

Специальный алгоритм решения задачи для случая полиэдральных фукнций Ф(-) и <5(-) при гауссовском распределении случайных параметров был предложен в работе А. И. Кибзуна. А. В. Наумова [26].

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

[125], А. Рущиньским [121], Й. Людтке, С.Ахмедом, Г. Л. Немхаузером [106],

A. Саксеной, В. Гойя л ом, М.А.Леженом [124]. Данный результат был обобщён на случай задач стохастического программирования с квантильным критерием

B. И. Норкиным [111], А. И. Кибзуном, А. В. Наумовым, В. И. Норкиным [32,35].

Интересная связь между двухуровневыми задачами и задачами оптимизации функции квантили была найдена Р. Т. Рокафелларом, С. П. Урясьевым [118]. Функция квантили является оптимальным решением задачи стохастического программирования с ограничениями на оптимальность переменных. Данный факт был использован в работе Пан Чон-Си [113] для решения задачи стохастического программирования с квантильным критерием с помощью методов двухуровневой оптимизации.

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

C.Уоллиса [98], Дж. Р. Бёржа, Ф.Луво [66]. Качественные свойства двухэтапных задач стохастического линейного программирования с критерием в форме математического ожидания исследованы в работах Дж. Р. Бёржа, Ф. Луво [66], П. Калла, С.Уоллиса [98], С. Сена [126], Д.У.Уокапа, Р.Дж.-Б. Вет-са [135], Р.Дж.-Б. Ветса [139,140]. Различные методы решения этих задач предлагались Дж. Р. Бёржем [65], Дж. Р. Бёржем, Ф.Луво [66], Дж. Р. Бёржем, Р.Дж.-Б. Ветсем [67], А.С.Величко [3], С.Гартской [88], И.Деакой и др. [79,80], П. Калл ом, Дж. Майером [97], А. Рущиньским [120], С. Сеном [126], С.Уоллисом, Янь Течэном [136], Э.Франьером, Я. Гондзё, Ж.-П.Вьялом [87], А. Чарнсом, У.У.Купером. Г.Томпсоном [71], А.Шапиро, Д. Денчевой, А. Рущиньским [127], Н. О. П. Эдирисинге, У. Т. Зембой [84]. Прикладные двух-этапные задачи стохастического программирования рассматривались в работах Дж. Р. Бёржа, Ф.Луво [66], П. Калла , С.Уоллиса [98], С.Уоллиса, У. Т. Зембы [137], Д.Б.Юдина [53,54]. Так же как и двухуровневые задачи, двухэтапные задачи описывают процедуру последовательного принятия решений. На первом этапе выбирается предварительная стратегия, которая корректируется в

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

Как и в случае двухуровневых задач стохастического программирования, вместо математического ожидания в двухэтапной задаче может быть использована квантиль. Критериальная функция в форме квантили для двухэтапных задач стохастического программирования была предложена в работе А. И. Кибзуна, А. В. Наумова [27]. Данная задача была рассмотрена для случая гауссовского распределения вектора случайных параметров, были сформулированы условия непрерывности и выпуклости критериальной функции, предложена теорема существования решения, сформулирована теорема об эквивалентности задач в априорной и апостериорной постановках. Двухэтапная задача стохастического программирования в априорной постановке, по сути, является задачей оптимального управления стохастической системой. А апостериорная постановка представляет собой результат применения метода динамического программирования к задаче в априорной постановке. В данной работе двухуровневая задача формулируется в апостериорной постановке. Дальнейшие результаты, связанные с исследованием качественных свойств линейной двухэтапной задачи квантильной оптимизации в случае дискретного распределения вектора случайных параметров, отражены в работе А. В. Наумова, И. М. Бобылёва [41]. В этой работе доказана непрерывность функции квантили минимального значения критерия задачи второго этапа и предложены условия существования решения задачи. Для скалярного случая предложен детерминированный эквивалент задачи.

Вопрос возможности использования аппроксимации непрерывного распределения дискретным приближением для двухэтапных задач стохастического программирования с квантильным критерием исследовался в работе А. И.Кибзуна, И.В.Никулина [34]. В работе А. И. Кибзуна, А.В.Наумова, В. И. Норкина [35] было показано, что данная задача может быть сведена к задаче смешанного целочисленного программирования.

Прикладные двухэтапные задачи квантильной оптимизации экономических систем рассмотрены в работах А.В.Наумова [39,40], А.В.Наумова, А.Б.Богданова [42], А.В.Наумова, С.В.Уланова [49]. В работах [39,40] исследуются задачи оптимального инвестирования по квантилы-юму критерию. В работах [42, 49] рассмотрены задачи оптимального распределения ресурсов, в частности в транспортных системах. Прикладные задачи оптимизации в авиационно-космической отрасли исследованы в работах А. И. Кибзуна, А.В.Наумова, С.В.Уланова, [33], А.В.Наумова, А. А. Хоревой, А. М. Чайки [50]. В работе [33] решена задача оптимизации летного расписания крупной авиационной компании. В работе [50] рассмотрена модель функционирования логистической транспортной авиационной компании.

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

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

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

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

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

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

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

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

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

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

ленными экспериментами.

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

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

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

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

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

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

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

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

портных и логистических систем, систем распределения ресурсов, оптимального инвестирования. Эффективность предложенных алгоритмов и методов продемонстрирована на примере трёх прикладных задач:

Список литературы диссертационного исследования кандидат наук Иванов, Сергей Валерьевич, 2013 год

Список литературы

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

Верссиев В.Л., Мельников A.A. Приближенные алгоритмы для задачи конкурентного размещения предприятии /, Дискретный анализ и исследование операций. - 2010. - Т. 17 - № 6. - С. 3-19.

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

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

Гаипиович В. А.. Еиифаицев С.Н., Овссйчук В. А. Экономическая страт ия и электрофпкация российских железных дорог . Под ¡редакцией Г.П. Ку-тового — М.: Эко-Пресс, 2012.

Груздева Т.В., Петрова Е.Г. Численное решение .линейной двухуровневой задачи //' Ж. вычиел. матсм. и матом, физ. — 2010. — Т. 50. — № 10. — С. 1715-1726.

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

Доении В.В. Динамическая логистика транс портных процессов. — М,-Компания «Спутник». 2010 — 246 с.

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

-lisio. Иванов C.B. Алгоритм решения дискретной задачи стохастического линейного программирования с квантильным критерием , Научно практическая конференция студентов п молодых учёных МАИ «Инновации в авиации и космонавтике — 2011». 26-30 апреля 2011 года. Москва. Сборник тезисов докладов. - М.: МЭЙЛЕР, 2011. - С. 104-105.

11. Ива,нов C.B. Двухуровневые задачи стохастического линейного программирования с квантильным критерием /7 Автоматика и телемеханика. — 2014. - № 1. - С. 95-108.

12. Ива,нов C.B. Двухэтапная двухуровневая задача оптимизации деятельности транспортного перевозчика в квантильной постановке / Московская молодёжная научно-практическая конференция «Инновации в авиации и космонавтике — 2012». 17-20 апреля 2012 года. Москва. Сборник тезисов докладов. — М.: ООО «Принт-салон», 2012. — С. 236-237.

13. Иванов С.U. Задача распределения инвестиций в развитие отраслей производства / ' Вопросы создания аэрокосмичсских и ракетных летательных аппаратов . Под ред. профессора Комарова IO.IO. — М.. Нзд-во Ваш полиграфический партнер. 2013. — С. 201-207.

14. Ива,нов СВ. О двухуровневой задаче стохастического линейного программирования с квантильным критерием / / 11-я Международная конференция «Авиация и космонавтика — 2012». 13-15 ноября 2012 года. Москва. Тезисы докладов. — СПб.: Мастерская печати. 2012. — С. 375-376.

15. Иванов C.B. О решении двухуровневой задачи стохастического программирования с квантильным критерием и дискретным случайным параметром // Ломоносов-2013: Материалы XX Международной научной конференции студентов, аспирантов и молодых ученых: секция «Вычисли те.ль-ная математика и кибернетика»: 9-12 апреля: Москва. МГУ имени М.В. Ломоносова, факультет ВМК: Сборник тезисов ' Сост. Месяц А.И.. Шев-

нова И.Г. — М.: Издательский отдел факультета ВМК МГУ (лицензия ИД 05899 от 24.09.2001), 2013. - С. 84-85.

16. Иванов C.B. Оптимизация структуры наземного космического комплекса

Свидетельство о государе г вен ной реплстрацип программы для ЭВМ Л- 2013019236 от 27 сентября 2013 г.

17. Иванов C.B.. Наумов A.B. Алгоритм оптимизации квангилыюго критерия для полиэдральной функции потерь и дискретного распределении случайных параметров ; ' Автоматика и телемеханика. — 2012. — № 1. — С. 116129.

18. Иванов C.B.. Наумов A.B. О квашплытои постановке задачи двухуровневого программирования на примере задачи распределения пнвеч гшшй ' ' Информацнонно-тслекоммуникацпонпые технологии и малсмаллшескос моделирование высокотехнологичных систем: тезисы док.ладов Всероссийской конференции с международным участием. Москва. РУДН. 23-27 апреля 2012 года. - М.: РУДН. 2012. С. 279-281.

19. Иванов C.B., Ha.yM.oe A.B. Сведение двухэл'апной задачи стохастического .линейного программирования с кваптильным критерием к одноэгапной задаче ; Всероссийская молодежная школа-семинар «Дискретные модели и методы принятия решений», Новосибирск. 21-23 июня 2013. Материалы школы-семинара. Новосибирск. Издательство института математики. 2013. - С. 255-256.

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

21. Кап Ю.С. О сходимости одного стохастического квазш радиешного a i-горитма квантильной оптимизации. !' Автоматика и телемеханика. — 2003. - Ш 2. - С. 100-116.

22. Кибзун А.И., Кап К).С. Задачи стохастического программировании с вероятностными критериями. — ТчI.: Физматлит, 2009.

23. Кибзун А.И.. Курбаковский В.Ю. Численные алгоритмы кваншлыюй оптимизации их применение к решению задач с вероятностными oi ранпчепи-ямп Известия РАН. Техническая кибернетика. — 1992 — № 1. — С. 7581.

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

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

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

27. Кибзун А.И., Наумов A.B. Двух» та иные задачи квант'ильного линейного программирования ' Автоматика и телемеханика. — 1995. — №1. — С. 8393.

28. Кибзун А.И.. Наумов A.B.. Иванов C.B. Алгоритмический аппарат для анализа и решения задачи оптимизации деятельности железнодорожного транспортного узла /7 Труды Первой научно-технической конференции «Интеллектуальные системы управления на железнодорожном транспорте» (ИСУЖТ-2012). Москва. 15-16 ноября '2012 г. - М.: ОАО «НИИАС». 2012. - С. 80-83.

29. Кибзун, А.И.. На/умов A.B., Ива,нов C.B. Двухуровневая задача оптимизации доя тельное тп железнодорожного гранепор i ного у з ia ' Управ юние большими системами. — 2012. — .Vе 38. — С. 140-160.

30. Кибзун A.M.. Наумов A.B., Иванов C.B. Об эквивалентности двухуровневых и двухэтапных задач стохастического программирования с квантпль-ным критерием // Международная конференция «Дискретная оптимизация и исследование операций». Новосибирск. Академгородок, 24-28 июня 2013. Материалы конференции. Новосибирск. Издательство института, математики. 2013. — С. 60.

31. Киб.зуи Л. И.. Наумов A.B.. Ива,нов C.B.. Чсрнобровов А. И. Оптимизация деятельности железнодорожного 'транспортного уз. ia в условиях случайного спроса на грузоперевозки и наличия конкуренции // Труды и пленарные доклады участников конференции УКИ'12 Научное издание. Электрон, текстовые дан. - М.: ИПУ РАН. 2012 - 1 электрон, опт. диск (CD-ROM) — ISBN 978-5-91450-100-3 - С. 1165-1176.

32. Кибзун А.И.. Наумов A.B., Норкин В.И. О сведении задачи квангильной оптимизации с дискретным распределением случайных данных к задачам смешанного целочисленного программирования / Автоматика и телемеханика. - 2013. - № 6. - С. 66-86.

33. Кибзун А.И., Наум,ов A.B., Уланов С.А. Оптимизация самолетного парка авиакомпании Автоматика и телемеханика. — 1999. — ,\s 8. — С. 126-137.

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

35. Кибзун А.И., Hay.,нов A.B., Норкин, В.И. Сведение задач двухэтапной вероятностной оптимизации с дискретным распределением случайных данных Ii Труды научного семинара в сборнике трудов Стохастическое программирование п его приложения / U.C. Кнопов. В.И. Зоркальцев. Я.М. Иваны) и др. — Иркутск: Институт систем энергетики им. Л.А. Мелентьева СО РАН. 2012. - С. 76-104.

3G. Кибзун А.И. Чернобровое А.И. Стохастический квазпградиопгный алгоритм минимизации функции интегральной квантили. — Автоматика и телемеханика. - 2012. - № 2. - Р. 41-60.

37. Кононов A.B.. Кочетов Ю.А.. Плясунов A.B. Конкурентные модели размещения производства. — Журнал вычислительной математики и математической физики. - 2009. - Т. 49. - № 6. - С. 1037-1054/

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

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

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

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

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

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

44. Наумов A.D., Иванов C.D. Двухэтапная модель оценки эффект пвпо-сти проектов, направленных на экономию элетроэнергии в интересах подразделения РЖД //' Интеллектуальные сисл'емы на транспорте: материалы Третьей международной паучно-пракгпческоп конференции «ИнтеллектТранс-2013». — М.: Издательство «Перо», 2013. — С. 183-188.

45. Наумов A.D., Ива,нов C.D. Задача распределения инвестиций в развитие отраслей наземного космического комплекса .' ' Электронный журна! «Труды МАИ». - 2012. - № 50.

46. Наумов A.D., Иванов C.D. Задача распределения инвестиций, выделяемых на реструктуризацию наземного космического комплекса / 10-я Международная конференция «Авиация и космонавтика — 2011». 8-10 ноября 2011 года. Москва. Тезисы докладов. — СПб.: Мастерская печати. 2011. — С. 272-273.

47. Наумов A.D., Иванов C.D. Исследовал не задачи стохастическою линейного программирования с кваптильным критерием Автоматика и телемеханика. - 20LI. - А"* 2. - С. 142-158.

48. Наумов A.D., Ива,нов C.D. Исследование одпоэтапной задачи стохастического линейного программирования с кваптильным критерием /'/ 15-я международная научная конференция «Системный анализ, управление и навигация». Крым. Евпатория. 27 июня - 4 июля 2010. — М.: Изд-во МАИ-ПРИНТ, 2010. - С. 144.

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

50. Наумов A.D.. Хорвва A.A. Ча,нка A.M. Управление деятельностью транспортной компании с учетом требований надежности. «Моделирование и анализ безопасности и риска в сложных системах»: Труды Международ-

ной школы МАБР-2007 (Россия. Санкт-Петербург. 4-8 сентября. 2007). — СПб.: ГОУ ВПО «СПбГУАП». 2007. - С. 394-399.

51. Стретловский А.С.. Орлов А.В., Малышев А.В. Численное решения одного класса задач двухуровневого программирования // Сибирский журнал вычислительной математики. — 2010. — Т. 13. — № 2. — С. 201-212.

52. Схрейвер А. Теория линейного и целочисленного программирования. — М.: Мир, 199J.

53. Юдин Д.Б. Математические методы управления в условиях неполной информации. — М.: Сов. Радио. J974.

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

55. Abou-Kandil Н.. Bertrand P. Government — private sector relations as a Stackelberg game: A degenerate case ' Journal of Economical Dynamics and Control. - 1987. - V. 11. - No. 4. - P. 513-517.

56. Al-Khayyal F.A., Horst R.. Pardalos P.M. Global optimization of concave fuctions subject to quadratic constraints: an application in nonlinear hilevel programming // Annals of Operations Research. — 1992. — No. 34. — P. 125— 147.

57. Aadet C.. Savard G.. Zghal W. New Branch-and-Cut Algorithm for Bilevel Linear Programming • .Journal of Optimization Theory and Applications. — 2007. - V. 134. - No. 2 - P. 353-370.

58. Bard J.F Practical Bilevel Optimization1 Algorithms and Applications. Dordrecht: Kluwer Academic Publishers. 1998.

■59. В a,I'd J.F., Fa,Ik J. An explicit solution to the multi-level programming problem 7 Computers and Operations Research. — 1982. — No. 9. — P. 77-100.

60. Bard J.F.. Moore J. A Branch and bound algorithm for the bilcvcl programming problem ■ ' SIAM Journal on Scientific and Statistical Computing. - 1990. - No. 11. - P. 281-292.

61. Beer K. Lösung großer linearer Oplimieiiingsaufgabeii. Beilin: Deutschet Verlag der Wissenschaften. 1977.

62. Benders J.F. Partitioning Procedures for Solving Mixed-Variables Programming Problems / Numerishe Mathematik. — 1962. — V. 4. — No. 1. - P. 238-252.

63. BemchouM.. Gauthier J. M.. Girod,et P.. He/ntqcsG., RilnereC., Vrncent O. Experiments in mixed-integer linear programming Mathematical Programming. - 1971. - V. 1. - No. 1. - P. 76-94.

64. Btalas W., Karwan, M. Two-level linear programming / Management Science. - 1984. - V. 30. - P. 1004-1020.

65. Birge J.R. Decomposition and partitioning methods foi multistage stochastic linear programs , , Operations Research. — 1985. — V. 33 — No 5. — P 9891007

66. Bvrge J.. Lotiveavx F. Introduction to Stochastic Programming. New York: Springer-Verlag. 1997.

67. Btrge J.R.. Wets 11 J.-B. Designing approximation schemes ior stochastic optimization problems, in particular, for stochastic programming with recourse 7 Mathematical Programming Study. - 1986. - V. 27. - P. 54-102.

68. Candler W., Townsley 11. A Lineal Two-Level Programming Problem Computers and Operations Research. — 1982. — V. 9. — No. 1. — P. 59-76.

69. Charnes A.. Cooper W. W. Chance-Constrained Programming Management Science. - 1959. - V. 6. - No. 1. - P. 73-79.

70. Charnes A.. Cooper W. W. Deterministic Equivalents for Optimizing and Satisfying under Chance-Constraints ' Operations Research. — 1963. — V. 11. - No. 1. - P. 18-39.

71. Charnes A.. Cooper W. IV.. Thompson G.L. Constrained Generalized Medians and Hypermedians as Deterministic Equivalents for Two-Stage Linear Programs under Uncertainty ' Management Science. — 19G5. — V. 12. — No. 1. - P. 83-112.

72. Chen A.. Kim J., Zhong Zh.. Chootinan P. Alpha Reliable Network Design Problem Transportation Research Record: Journal of the Tranportation Research Board. - 2007. - No. 2029. - P. 49-57.

73. Cheng L . Wan Zh.. Wang C. Bilevcl newsvcndor models considering retailer with CVaR objective // Computers k. Industrial Engineering. — 2009. -V. 57. - N. 1. - P. 310-318.

74. Christiansen S., Palnksson M.. Wynter L. Stochastic bilevel programming in structural optimization // Structural arid Multidisciplinary Optimization. — 2001. - V. 21. - No. 5. - P. 301-371.

75. Colson D.. Marrotte P., Savard C. An overview of bilevel optimization Annals of Operations Research. -2007. -V. 153. -No. 1. -P. 235-250.

76. Colson D , Marcotie P . Saaaid G. Bilevel progiamming A sune\ 40R. -2005. -V. 3. -No. 2. -P. 87-107.

77. Co'iistantm /.. Flonan M. Optimizing frequencies in a liansit network a nonlinear bi-level programming appioach /, International Transactions in Operational Research. - 1995. - No. 2. - P. 149-164.

78. Dantzig G.D. Linear programming under uncertainty ' Management Science. - 1955. - V. 1. - P. 197-206.

79. Dedk I. Testing successive regression approximations by large-scale two-stage problems. Annals of Operations Research. — 201L. — V. 186. — No. 1. — P. 8399.

80. Dedk /.. Pulik I.. Prekopa A.. Terlaky T. Convex approximations in stochastic programming by semidefinite programming // Annals of Operations Research. - 2012. - V. 200. - No. 1. - P. 171-182.

81. Denvpe S. Annotated Bibliography on Bilevel Programming and Mathematical Programs with Equilibrium Constraints / ; Optimization. — 2003. — V. 52. — No. 3. - P. 333-359.

82. Denvpe S. Bilevel Programming — A Survey /. Preprint TU Bergakademie Freiberg Nr. 2003-11. Fakultiit fur Mathematik unci Informatik., 2003.

83. Dernpe S. Foundations of Bilevel Programming. Dordrecht: Kluwer Academic Publishers. 2002.

84. Edirismghc N.C.P. Ziernba W.T. Bounds for Two-Stage Stochastic Programs with Fixed Recourse / Mathematics of Operation Research. — 1994.

V 19. - No. 2. - P. 292-313.

85. Edmunds T.. Bard J.F. Algorithms for nonlinear bilevel mathematical programs /'' IEEE Transactions on Systems, Man. and Cybernetics. — 1991. — No. 21. - P. 83-89.

86. Fortuny-Amal J., McCarl B. A representation and economic interpret,at ion of a two-level programming problem // Journal of the Operational Research Society. - 1981. - V. 32. - No. 9. - P.783-792.

87. Fiugmere E.. Gondzio •/.. Vi,(d,J.-P. Building and solving large-scale stochastic programs on an affordable distributed computing system Annals of Operations Research. - 2000. - V. 99. - P. 167-187.

88. Garstka. S.J.. Rutenberg D.P. Computation in Discrete Stochastic Programs with Recourse /'/ Operations Research. — 1973. — V. 21. — No. 1. — P. 112-122.

89. Gartska S. J. The Economic Equivalence of Several Stochastic Programming Models Stochastic Programming, ed. M. A. II. Dempster. Academic Press. New York. 1980. - P. 83-91.

90. Gov югу R. An algorithm for the mixed integer problem R. L. Graves. P. Wolfe (Eds.). Recent Advances in Mathematical Programming. McGraw-Hill., New York. 1969. - P. 269-302.

91. Han J., Liu G., Wang Sh. A new descent algorithm for solving quadratic bilevel programming problems // Acta Mathematicae Applicatae Sinica. — 2000. — V. 16. - No. 3. - P. 235-244.

92. IBM ILOG CPLEX V12.1. User's Manual for CPLEX. - International Business Machines Corporation. 2009. — 952 p.

93. Introduction to lp_solve 5.5.2.0 [Электронный ресурс]. — Режим доступа: http://lpsolve.sourc.eforge.net/5.5/. Дата обращения: 22.07.2013.

94. hhizvka Y., Aiyoshi E. Double penalty method for bilevel optimization problems ;' Annals of Operations Research. — 1992. — No 34. — P. 73-88.

95. Ivanoo S. V.. Naumov A. V. An algorithm for solving a linear discrete stochastic programming pioblem with the quantilo criteria Actual problems of aviat ion and aerospace systems. — 2011. — No. 2 (33). — V. 16. — P. 179.

96. Jia, F., Yang F., Wang S.-Y. Sensitivity analysis in bilevel linear programming // Systems Science and Mathematical Sciences. — 1998. — V. 11. — No. 4. — P. 359-366.

97. Kail P., Mayer J. Stochastic Linear Programming. — New York: Springer. 2005.

98. Kall. P., Wallace S. W. Stochastic Programming. - Wiley. Chichester. 1994.

99. Katagiri H., Uno Т.. Kalo К.. Tsv,da. И.. Tsubaki Н. Random iuzz.\ bilevel linear programming through possibility-based value at risk model

Intcrnational Journal of Machine Learning and Cybernetics. Preprint,. October 2012.

100. Kataoka S.A. Stochastic Programming Model /,.< Econometrica — 1963. — V. 31. - No. 1-2. - P. 181-196.

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

102. Kibzun .4.. Ma.tve.ev E. Optimization of the quantile criterion for the convex loss function bv a stochastic quasigradient algoiithni Annals of Operations Research. - 2012. - V. 200. - No. 1. — P. 183-198.

103. Kosuch S., Le. Bodic. P., Leung J.. Lisser A. On a stochastic bilevel programming problem with knapsack constraints. In Proceedings of the International Network Optimization Conference. 2009.

104. Kosuch S. Stochastic Optimization Problems with Knapsack Constraint Thèse présentée pour obtenir le grade de Docteur en Sciences de l'Université Paris XI. Orsay, 2010.

105. Kovacevu: R.M.. Pflug G.Ch. Electricity' Swing Option Pricing by Stochastic Bilevel Optimization: A survey and new approaches Piepiint submitted to Elsevier. 2013.

106. Luedike ./.. Ahmed S.. Nemhauser G'.L An integer programming approach for linear programs with probabilistic constraints , Mathematical Progiam-ming. - 2010. - V. 122. - No. 2. P. 247-272.

107. Maichand H.. Mai tin /1.. Weismantel R.. Wolsey L. Cutting planes in intcgei and mixed integer programming , / Discrete Applied Mathematics. — 2002. — V. 123. - No. 1-3. - P. 397-446.

108. Marcotte P. Network design problem with congestion effects: a case of bilevel programming. Mathematical Programming. — 1986. — V. 34. — P. 23-36.

109. Nawnov A. V.. Ivanov S. V. The problem of distribution of the investment capital allocated for reconstruction of the aeiospaee complex , Actual problems of aviation and aerospace systems. — 2012. — l\o. 1 (34). — V. 17. — P. 164.

110. Nv'JwHs M.G. Aluminum Production Modeling — A Nonlinear Bilevel Programming Approach // Operations Research. — 1995. — V. 43. — No. 2. — P. 208-218.

111. Norkm V. On mixed integer reformulations of monotonie probabilistic programming problems with discrete distributions // http:/Avww.optimization-onlme.org/DB_HTML/2010/05/2619. ht ml. 2010.

112. Ozaltvn, O.Y.. Prokopyev O.A.. Sc.hae.fer A.J. The bilevel knapsack problem with stochastic, right-hand sides ' ' Operations Research Letters. — 2010 -V. 38. - No. 4. - P. 328-333.

113. Pang J.-Sh.. Leyffer S. On the Global Minimization of the Value-at-Risk Optimization Methods and Software. - 2004. - V. 19. — No. 5. - P. 611-631.

114. Patriksson M., Wynt.er L. Stochastic nonlinear bilevel programming , , Technical report, PRISM. Université de Versailles - Saint Quentin en Yvelines. Versailles. France, 1997.

115. Pflug G.Ch. Some Remarks on the Value-at-Risk and the Conditional Value-at-Risk // Nonconvex Optimization and Its Applications. — 2000. — V. 49. — P. 272-281.

116. Prékopa .-4. Numerical Solution of Probabilistic Constrained Programming Problems ; Numerical Teehiques for Stochastic Optimization eds. Yu. Ei-moliev and R.J.13. Wets. Springer-Verlag. Berlin. 1980. - P. 123-139.

117. Prékopa A.. Szcintai T. Flood control reservoii s\srem design using stochastic programming '/ Mathematical Programming Studies. — 1978. — V 9. -P. 138-151.

118. Hockafellar R.T., Uryasev S. Conditional valuc-at-iisk for general loss distributions /'/ .Journal of Banking L Finance. - 2002. - No. 2G. - P. 1443-1-171.

119. Rockafellar R.T.. Uryasev S. Optimization of conditional value-at-risk / Journal of Risk. - 2000. - V. 2. - No. 3. - P. 21-41.

120. Ruszcynski .4. Parallel Decomposition of Multistage Stochastic Programming Problems ': Mathematical Programming. — 1993. — V. 58. — No. 1-3. — P. 201-228.

121. Ruszczynski .4. Probabilistic programming with disciete distributions and precedence constrained knapsack polyhedra Mathematical Programming. — 2002. - V. 93. - No. 2. - P. 195-215.

122. Sakawa M., Kaiagiri H.. Matsm T. Stackelbcrg solutions ior fuzzv random bilevel linear programming through level sets and probability maximization / Operational Research. - 2012. - V. 12. - No. 3. - P.271-286.

123. Snvnrd G.. Gaumn J. The steepest descent direction for the nonlinear bilevel programming problem ,, / Operations Research Letters. — 1994. — V. 15 — P. 265-272.

124. Saxena A.. Goynl. V.. Le]etine M.A. MIP reformulations of the probabilistic set covering problem , ' Mathematical Programming. Ser. A — 2010. — V 121. — No. 1. - P. 1-31.

12-5. Sen S. Relaxation for probabilistically constrained programs with disci ete random variables /'/ Operations Research Letters. — 1992. — V. 11. — No. 2. — P. 81-86.

126. Sen S. Subgradient Decompositon and Differentiability of the Recourse Function of a Two Stage Stochastic Linear Program / ' Operations Research Letters 1993. - V. 13. - No. 3. - P. 143-148.

127. Shapiro A., Dentcheva D., Ruszczynsh A. Ledures on stochastic programming: Modeling and theory. MPS/SIAM Series 011 Optinii/ation. 9. Philadelphia. PA Society for Industrial and Applied Mathematics (SLAM). 2009.

128. Stac.kdbc.rq H.F. Maiktfoini unci Glcic hgewicht. Berlin. Spiinger-Ycrlag. 1934

129. Strekalousky 4.5., Orlou A.V.. Malysher A.V. On computational search for optimistic solutions in bilevel problems /'/ Journal of Global Optimization. — 2010. - V. 48. - No. 1. - P. 159-172.

130. Szantai T. A Computer Code for Solution of Probabilistic-Constrained Stochastic Programming Problems / ' Numerical Techniques for Stochastic Optimization. eds. Yu. Ermoliev and R..1-B. Wets. Springer-Verlag. Berlin. 1980. — P. 229-235.

131. Tuy H., Migdalas A.. Vdrbrand P. A global optimization appioaeh for the1 linear two-level program / .Journal of Global Optimization. — 1993 — V. 3. — No. 1. - P. 1-23.

132. Vand.f'.rbcck F.. Savelsbergh, M. A generic view of Dantzig-Wolfe decomposition in mixed integer programming •' Operations Research Letters. — 2006. — V. 34. - No. 3. - P. 296-306.

133. Vicente L.N.. Calamai P.M. Bilevel and multilevel programming: A bibliogia-phy review /' Journal of Global Optimization. — 1994. — V. 5. — No. 3. — P. 291-306.

134. Vicente L.N.. Savard G., Juchce J.J. Descent approaches for quadratic bilevel programming . / Journal of Optimization Theory and Applications. — 1994. — V. 81. - P. 379-399.

135. Walkup D. W.; Wets R.J.-D. Stochastic Programs with Recourse ■ SIAM Journal on Applied Mathematics. - 1967 - V. 15. - No. 5. - P. 1299-1314.

136. Wallace S. W.. Van T. Bounding Multi-Stage Stochastic Programs from Above ■/ Mathematical Programming. - 1993. - V. 61. - No. 1-3. - P. 111-129.

137. Wallace S.W., Ziemba W.T. Applications of Stochastic Programming. SIAM. Philadelphia, 2005.

138. Werner A.S. Bilevel Stochastic programming problems: analysis and application to telecommunications / ' Dr. ing thesis. 2004 Section of Investment. Finance and Accounting. Dept of Industrial Economics and Technology Management. NUST. Noiwa\

139 Wets R J -D. Programming undei uncertainty the equivalent com ex piogiam SIAM Journal on Applied Mathematics - 1966. — V. 15. — No. 1 -P. 89-105.

140. Wets R.J.-D. Stochastic programs with fixed recourse: The equivalent deterministic program / ' SIAM Review. - 1974. - V. 16. - Xo. 3. - P 309-339.

141. Yang H.. Bell M G.H Transportation bilevel programming problems: Recent methodological advances Transpoitation Research. Part B. — 2001. -V. 35. - No. 1. - P. 1-4.