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

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

Иванов Сергей Валерьевич

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

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

Автореферат

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

5 ПЛ 2013

005541987

Москва, 2013 год

005541987

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

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

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

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

Официальные оппоненты: Назин Александр Викторович,

доктор физико-математических наук, профессор, ведущий научный сотрудник Института проблем управления им. В. А. Трапезникова РАН;

Миллер Григорий Борисович,

кандидат физико-математических наук, научный сотрудник

Института проблем информатики РАН

Ведущая организация: Институт математики им. С. Л. Соболева

Сибирского отделения РАН

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

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

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

/¿/.//./3

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

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

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

. С. Северина

-3-

Общая характеристика работы

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

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

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

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

Приложения задач двухуровневого программирования имеют место в самых разнообразных отраслях. Иерархические модели экономики рассматривались в работах Ян Хая, М. Белла, транспортная задача изучалась X. Абу-Кандилом и П. Бертраном, задача проектирования сетей рассматривалась П. Маркотте и И. Констанином, М. Флорианом, модели алюминиевой промышленности изучались М. Г. Николсом. Задача конкурентного размещения предприятий в форме двухуровневой задачи целочисленного программирования изучалась в работах В. Л. Береснева, А. А. Мельникова, А. В. Кононова, Ю. А. Кочетова, А. В. Плясунова.

Ввиду того, что экономические системы, как правило, описываются линейными моделями, отдельного рассмотрения заслуживает класс линейных задач двухуровневого программирования, рассмотренный, например, у У. Биаласа, М. Карвана. Методы решения данных задач предлагались У. Кэндлером и Р. Таунслеем, Ш. Оде, Ж.Саваром и В. Згалом, X. Фортуни-Аматом и Б. Маккарлом, Хоанг Туем, А. Мигдаласом, П. Вербрантом, Цзя Фучэнем, Ян Фэнмэем и Ван Шоуяном.

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

Стохастическая постановка задачи двухуровневого программирования с кри-

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

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

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

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

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

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

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

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

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

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

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

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

чах, в том числе в области авиационной и ракетно-космической техники.

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

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

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

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

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

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

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

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

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

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

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

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

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

тоды и алгоритмы их решения (области исследования 1, 4, 5 специальности 05.13.01).

Апробация работы. Результаты диссертации докладывались на научных семинарах кафедры теории вероятностей Московского авиационного института (рук. проф. Кибзун А.И.), на 3-й и 4-й Традиционной молодёжной Школе «Управление, информация и оптимизация» (Россия, Ярополец, 2011 г.; Россия, Звенигород, 2012 г.), на Всероссийской молодёжной научной школе-семинаре «Дискретные модели и методы принятия решений» (Россия, Новосибирск, 2013 г.)

Материалы диссертации представлялись на следующих конференциях: 15-я и 16-я международные конференции «Системный анализ, управление и навигация» (Украина, Евпатория, 2010, 2011 гг.), 10-я и 11-я международные конференции «Авиация и космонавтика» (Москва, Россия, 2011, 2012 гг.), международная конференция «Дискретная оптимизация и исследование операций» (Россия, Новосибирск, 2013 г.), XX Международная научная конференция студентов, аспирантов и молодых ученых «Ломоносов-2013» (Россия, Москва, МГУ им. М.В. Ломоносова), Всероссийская конференция с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем» (Россия, Москва, РУДН, 2012 г.), 3-я Российская конференция с международным участием «Технические и программные средства систем управления, контроля и измерения» (Россия, Москва, 2012 г.), научно-практическая конференция студентов и молодых учёных МАИ «Инновации в авиации и космонавтике — 2011», московская молодёжная научно-практическая конференция «Инновации в авиации и космонавтике — 2012», Первая научно-техническая конференция «Интеллектуальные системы управления на железнодорожном транспорте» (Россия, Москва, 2012 г.).

Работа поддержана грантами РФФИ (09-08-00369-а, 11-07-00315-а, 1-07-13102-офи-м-2011-РЖД, 12-07-00191-а, 12-07-13108-офи_м_РЖД, 12-07-13114-офи_м_РЖД, 12-08-00453-а) и государственным финансированием ФЦП «Научные и научно-педагогические кадры инновационной России» (мероприятие 1.2.2, госконтракт № 14.740.11.1128).

Публикации. Основные результаты диссертации опубликованы в 4 научных статьях [1-4] в журналах, входящих в перечень ВАК, в 5 статьях [5-9] в различных журналах, сборниках и материалах конференций, в сборниках тезисов докладов конференций [10-21] на русском и английском языках. Общее число публикаций — 21. Зарегистрирована программа для ЭВМ [22].

Структура и объём диссертации. Диссертация содержит введение, три главы, заключение и список используемой литературы. Работа состоит из 130 страниц, включая 1 рисунок, 15 таблиц и список литературы, содержащий 141 наименование.

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

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

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

Пусть X — случайный вектор с реализациями х 6 Кт, и е U — стратегия лидера, U = {и € R" | Aiu ^ fei} — множество допустимых стратегий лидера, где А\ 6 Eixn, bi е Ш.1. Задача последователя формулируется в следующем виде:

min (1.1)

yeY(u,x)

где Y(u, х) = {у G Rfc | А^и + B^y ^ x, у ^ 0} — множество допустимых стратегий задачи последователя, Ai € Rmxn — технологическая матрица лидера, Вг е Ш.тУ'к — матрица рекурсии (технологическая матрица последователя), сг 6 R4 — вектор коэффициентов линейной функции потерь последователя. Через Y*(u,x) обозначается множество оптимальных решений задачи (1.1). В случае если для пары (и,х) не существует решения задачи (1.1), то есть Y(u,x) — 0, либо оптимальное значения целевой функции в (1.1) не ограничено снизу, предполагается, что Y*(u,x) = 0.

Потери лидера, связанные с реализацией стратегии последователя, имеют следующий вид:

{min /тгЛ если У* (и, х) Ф 0, »'^Н (1.2)

+оо, если Y*(u,x) = 0,

где / € Rk — вектор коэффициентов линейной функции потерь лидера, связанных со стратегией последователя. Если минимум в выражении (1.2) не достигается, то считается, что Ф(и,х) = —оо.

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

CiU + Фа(и) -> min, (1.3)

иеи

где ci G R™ — вектор коэффициентов линейной функции потерь лидера,

Ф„(и) ± min{v> | Р{Ф(и, X) < <р) > а}, (1.4)

а — фиксированный уровень надёжности, Р{-} — вероятностная мера, порождённая распределением случайного вектора X.

Изучаются свойства критериальной функции задачи. Предлагаются условия, обеспечивающие выполнение условия Липшица на множестве W — {(и, х) | Y(u,x) ф Ф 0} для функции Ф(-).

Теорема 1.1. Если существует пара (и, ж) € W такая, что |Ф(й,х)| < +оо, то |Ф(и,а:)| < +оо для всех (и,х) 6 W и функция Ф(-) липшицева по переменным (и, х) на множестве W.

Явный вид множества YV указать сложно. Поэтому предлагается следствие из теоремы 1.1, обеспечивающее свойство Липшица для функции Ф(-) на всём пространстве R" х Rm.

Следствие 1.1. Пусть V = € Rm+1 | (-с2 | В2)Т v < f,v > o| Ф 0,

0+F ± {v e Mm+1 | {-а | B2)Tv < 0,5 > 0} = {6}, Vi 4 {v e Rm | Bjv < < c2,v > 0} ^ 0, где 0 — нулевой вектор соответствующей размерности. Тогда Ф(-) липшицева по переменным (и,х) на Rn х Rm и |Ф(и,х)| < +оо для всех (и,х). В следствии 1.1 и ниже под (• | •) понимается блочная матрица.

Предлагается также другое условие, обеспечивающее совпадение УУ с К" х Ет.

Следствие 1.2. Пусть У2 = {и е К"11 BJt; < ^ 0} ф 0, = {и е £ Кт | В^у ^ 0, г? ^ 0} = {0}, Ф 0. Тогда Ф(-) липшицева по переменным (и, х) на Ё" х Мт и |Ф(и,х)| < +оо для всех (и,х).

В работе предлагаются условия непрерывности функции квантили (1.4).

ТЕОРЕМА 1.2. Пусть |Ф(и,а:)| < +оо для всех (и,х) € Ж Тогда функция квантили Фа(0> определённая формулой (1.4), является непрерывной па множестве Кг = {и е К" | (V® 6 X) У{и,х) ф 0}.

В теореме 1.2 и ниже под носителем X вероятностной меры Р{-} понимается пересечение всех замкнутых подмножеств Кт единичной вероятностной меры.

Предлагается следствие из теоремы 1.2, которое гарантирует непрерывность функции квантили на К" х М"1, а значит, и существование решения задачи (1.3).

СЛЕДСТВИЕ 1.3. Пусть и ф 0, 0+и = {А\и < 0} = {0} и выполнены условия следствия 1.1 или следствия 1.2, то решение задачи (1.1)—(1.4) существует.

Доказывается эквивалентность двухуровневой задачи (1.3) и двухэтапной задачи стохастического линейного программирования с квантильным критерием и равновесными ограничениями специального вида:

Теорема 1.3. Задача (1.1)—(1.4) эквивалентна по переменной и задаче (1.5). При этом выполнено равенство Ф(и,х) = Ф'(и,х) для всех (и,х) 6 и х X.

Под эквивалентностью задач по переменной и в теореме 1.3 и в последующих утверждениях понимается следующее:

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

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

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

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

В частном случае, когда интересы лидера и последователя совпадают (сг = /), доказана теорема об эквивалентности задачи (1.1)-(1.4) и одноэтапной задачи стохаг стического линейного программирования с квантильным критерием

cju + Фа(и) —min.

iiiiii,

иеи

(1.5)

где Фа{и) = min{y> | Р{Ф'(и, X) < </>} ^ а},

(1.6)

(1.7)

т -10- _

где Ф(и,х) = тах |(с1 — и+(у^) ] = 1,7 — вершины много-

гранного множества V = {г» 6 Ж"1 | В^у ^ с2, V ^ 0}, 7 — количество вершин множества V.

ТЕОРЕМА 1.4. Пусть сг = / и решение задачи (1.1) существует для любых пар (и, х) 6 и х X, тогда задачи (1.1)—(1.4) и (1.7) эквивалентны по переменной и.

В случае скалярного случайного параметра предлагается детерминированный эквивалент задачи (1.1)—(1.4). Пусть выполнено следующее предположение.

Предположение 1. В задаче (1.1)-(1.4) х е К1, Л2 = е М1хп, В2 = Щ € еЕ1х*, Ь21>0, си^О, 1 = 1, к.

Рассмотрим две задачи оптимизации:

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

ю ->■ min (1.8)

uei/,V6R

cju < <р, cju + - 0,2 и) < ip,

02i'

сТи ft* шах < 0, ——7—— > min, (1.9)

( 02i' J ueu

где i* e Argmin^^k I = Argmin-f^21}, xa = min{x | P{X ^ x} ^ <*}, xa =

t€X l ') i=l,k '

= - min{i | P{-X s? x} ^ a}.

теорема 1.6. Пусть выполнено предположение 1. Тогда если /,■• > 0, то задача (1.1)—(1.4) эквивалентна по переменной и задаче (1.8), а если fi• < 0, то задача (1.1)—(1.4) эквивалентна по переменной и задаче (1.9).

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

Предположение 2. Пусть выполнены следующие условия:

1) случайный вектор X имеет дискретное распределение с конечным числом реализаций хи = 1, N, с вероятностями ри = Р{Х = х"}, ри > 0, и = 1, N;

2) существует оптимальное решение и* € ¿7 задачи (1.1)—(1.4);

3) существует оптимальное решение у'(и,х) е Y*(u,x) задачи (1.1) для всех (u, z) € U х X;

4) известна оценка снизу 7 оптимального значения критериальной функции задачи (1.3):

7 < cju* + ФQ(u*);

5) известны оценки Г(х) такие, что неравенство

Г{х) ^ cfu* + fy'&^x)

выполнено для всех оптимальных и" и х е Х\

6) известна константа L > 0 такая, что неравенство

тах{\\А2и' + В2у*{и*,х") - х"^ ||v\u'tx,f,y*{u',x,'))\\00t

\\B^v\u*,x\y\u\xv)) - call«,, ИуЧи*,*")!!»} < L (2.10)

_ -11-

выполнено для всех v — 1,N и всех оптимальных решений и*; для каждого оптимального и* неравенство (2.10) выполнено хотя бы для одной соответствующей ему паре оптимальных (у*(и*,х"), v*(u* ,х" ,у*(и* ,х")), где v*(u,x,y) является оптимальным значением переменной v задачи (1.6) при фиксированных значениях х и у. Пути поиска соответствующих констант обсуждаются в главе. В предположении 2 для задачи (1.1)—(1.4) предлагается метод её сведения к смешанной целочисленной задаче линейного программирования

с7и + <р~* min (2.11)

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

/V - < (Г(х") - 7)(1 - í„),j/ = MV; А2и + B2yv > xu, Bfv" < c2, v = 1, N\

vu ^ L(em - if), A2u + B2y" - xv < Lrf, и = TJ7-, у" < L(ek - С), c2 - 52V ^ LC,

N

Aiu^bi; У^ 8vpv ^ q;

i/=1

y*>0,v">0,v= UV;

<5 6 {0,1}"; rf 6 {0, l}m, Г € {0, l}k,

где em, e" — векторы, составленные из единиц, размерностей т, п соответственно, С, ff — векторы дополнительных целочисленных неременных, позволяющие перейти к линейным ограничениям.

ТЕОРЕМА 2.1. Пусть выполнено предположение 2. Тогда задача (1.1)—(1.4) эквивалентна по переменной и задаче (2.11).

Предлагается алгоритм решения задачи (1.1)—(1.4), основанный на переходе к задаче (2.11) и методе декомпозиции Бендерса, позволяющий на каждой итерации получить двусторонние оценки критериальной функции.

Вводятся векторы вещественных и бинарных оптимизационных переменных

и £ col (и,<р,у\...,гАV1,. ..,VN) е

z ± col (S, ч1,..., vN, с1, • • ■, с") 6 {о, 1}<1+™+*>"

где col(-) — вектор-столбец, составленный из векторов и чисел, записанных в скобках. Задача (2.11) в матричном виде записывается следующим образом:

сти -» min (2.12)

при ограничениях Au + Bz ^ 6, где А е R((i+3m+3fc)iv+í+i)x(n+i+w(fc+m))j в 6 е R((l+3m+3fc)W-M+l)x((l+m+fc)iV) „ b g R{l+3m+3k)N+l+l _ матрицы „ веКТорЫ, ОПИСЫВШО-

щие систему ограничения задачи (2.11) в матричном виде, с 6 Rn+1+jV^+m' — вектор коэффициентов целевой функции, соответствующих вещественным переменным.

В качестве начальной оценки снизу оптимального значения критериальной функции задачи (2.12) берётся число А(0), являющееся оптимальным значением критериальной функции задачи

cTu min (2.13)

„gßn+l + tt+m)^ JeR(l+m+t)N

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

Ли + Вт, ^ Ь,

О ^ Zj ^ 1, i = l,(l+m + k)N.

Задача (2.13) получена из задачи (2.12) с помощью замены бинарных переменных, соответствующих вектору z, вещественными переменными z¿ 6 [0,1].

Зафиксируем бинарные переменные в задаче (2.12). Тогда вектор переменных в задаче, двойственной к (2.12), имеет вид w = col (w\, ui2,... wg), где щ_ = = col {w¡,wlw-1), i = ITT Wi € R, wv2,wvb,w% <5 Rm, tü^wjf.wf el1,^ 1, JV, €E R', wg £ R. Тогда множество допустимых значений переменных в двойственной задаче задаётся системой ограничений

Á¡w\ + ... + Á¡w% - Á$w¡ - ... - - Ajwg = ca;

-/tuj + -... Bjwv5 - < sj 0, v = TJ7; -B2wl - ... - B2w% - < + В2Ш7 < 0, v = ITiV;

u^i >0, i = 1,9.

Множество векторов w, удовлетворяющих данной системе уравнений, обозначается через W.

Алгоритм 2.1.

0. Определим величины 7, Г(х), L, удовлетворяющие предположению 2. Запишем задачу (1.3) в виде (2.12).

1. Выполним присваивание t := 0 для шага t. Определим А(0), решив задачу (2.13). В качестве начального значения вектора z(t) возьмём z(0) = (1,1,..., 1)т.

2. Решим задачу, двойственую к (2.12),

w(í) е Arg шах5T(í)w, (2.14)

view

где g(t) = (b — Bz(t)). Вычислим

9{t) ± gT(t)w(t).

Если решение задачи (2.14) не единственно, то w(í) следует выбрать из вершин множества W, в которых достигается отпимальное решение задачи (2.14). Если значение критериальной функции в задаче (2.14) не ограничено сверху, то в качестве w(t) возьмём такую точку множества W, что gr(t)w(t) обеспечивает оценку сверху оптимального значения критериальной функции задачи (2.12). В этом случае 0(t) = +00.

3. Если 0(f) = A(t), то z(i) — оптимальное значение вектора z в задаче (2.12), z* = z(t). Переходим к шагу 4. Если 0(t) > А(£), то найдём

z(í + 1) 6 Argzg{o mm+t)N {max {wT(r) (b - Bz)} | |>z¿ ^ a|. (2.15)

Определим A(í +1) = max {wT(r) (b - Bz(t + 1))} .

r=0 ,t

-13-

Присвоим t := t + 1 и переходим к шагу 2.

4. В качестве оптимального значения критериальной функции задачи (1.1)—(1.4) возьмём A(í), а оптимальную стратегию и* найдём, решив задачу (2.11) при фиксированных целочисленных переменных, соответствующих вектору z(í).

Справедлива теорема о сходимости алгоритма 2.1.

Теорема 2.2. Пусть выполнено предположение 2. Тогда алгоритм 2.1 сходится за конечное число шагов к решению задачи (1.1)—(1.4). При этом для всех t £ Z+ величина А(£) является оценкой снизу оптимального значения критериальной функции задачи, a 6(t) — оценкой сверху.

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

условиям фа = min < cju + sup Ф(гц х) >, üa е Arg min < cfu + sup Ф(и, х) >, где S —

uet/ I íes J «et/ L xe5 J

доверительное множество уровня а, т. е. Р{5*} > а.

Прй выборе доверительного множества в виде шара Sr радиуса г G [0,+оо) с центром в пуле задача поиска гарантирующего решения задачи (1.1)—(1.4) записывается в форме задачи линейного программирования

¥>-)■ min (2.16)

при ограничениях ^cj — (u(j')T A-^j и + Ци^'Цг ^ <р, j = 1, J, где j = 1, J — вершины многогранного множества V = {и € Rm | B^v ^ сг, и > 0}, ||i!^||r = maxima;.

XGSr

Оптимальное значение критериальной функции задачи (2.16) обозначается через </v, а множество её оптимальных стратегий и — через Ur. Выбор в качестве доверительного множества шара объясняется тем, что в случае гауссовского распределения X при а —» 1 значение <рг стремится к оптимальному значению критериальной функции задачи (1.1)—(1.4). Пусть и(г) — элемент множества Ur для произвольного г ^ О,

Сг 4 j* I max {(с? - (t;«)T A2) u(r) + (vW)Ta;} < Vr J.

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

0) Присваиваем q := 0, rq := 0. Выбираем целое К € [1,+оо) и фиксируем шаг алгоритма Дг := ф-, где R — радиус шара Sr, имеющего вероятностную меру а, с центром в нуле.

1) Решаем задачу линейного программирования (2.16) при г = rq и находим <prq. Если существует и(га) € Ur, такое, что Р{Сг,} ^ а, то переходим к шагу 3.

-142) Присваиваем r9+i := rq + Дr, q := q + 1. Переходим к шагу 1. 3) В качестве искомого гарантирующего решения (йк,фк) возьмём (u(rq), <рГя). Неравенство Р{CTq} ^ав общем случае проверяется с помощью метода Монте-Карло.

Сходимость данного алгоритма к гарантирующему решению доказана в [1]. В главе предлагается также алгоритм улучшения методами теории двойственности задач линейного программирования некоторого известного гарантирующего решения (й,ф) (например, найденного с помощью алгоритма 2.2). Для этого рассматривается аппроксимация доверительного множества в виде многогранного множества

С = jx | шах | (с? - (v^YЛ2) й + (vU)YхJ < £ j и следующая задача поиска гарантирующего решения:

ш ->• min (2.17)

ueU, ipeR '

при ограничениях max шах ( (cj — (v^)T Л2 ) и + < <р.

XеС j=i,J v 4 / >

Оптимальное решение задачи (2.17) обозначается через {й,ф). Пусть и1 = со1(и,</з), й1 = со1(й, ф),

Л1^

1(^)7

, Ь1 А АЧ\

/Ст-(^1))ТЛ2 -1\

; ; Ь1^

ё1 4 (0,..., 0, -1) е Мп+\ и1 4 {и1 I Ащ < М-Тогда задача (2.17) может быть записана в виде

ё1«1 тах (2.18)

и1 el/1

при ограничении max max {(Л])Тцг + (ßj)TxJ < 0. хес j=i,J

Оптимальное решение задачи (2.18) обозначается через й1. Справедлива следующая лемма.

jlemma 2.1 Задача (2.18) эквивалентна по переменной и\+1 задаче:

eV max (2.19)

при ограничениях А1 и1 ^ Л1«1, и при этом одно из её оптимальных решений равняется й1.

Лемма 2.1 обобщает аналогичное утверждение, доказанное в [1], где предполагалось, что ü1 = (и, ф) является гарантирующим решением, полученным с помощью алгоритма 2.1. В данной лемме й1 является произвольным гарантирующим решением.

Для построения алгоритма улучшения гарантирующего решения рассматривается задача, двойственная задаче (2.19):

(Р)Т w1 + bjw2 -»■ min (2.20)

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

(ci-^(i) ... cx-AjvW ) w1 + = б> (2.21)

J

= wl,w2^ 0, (2.22)

i=i

где ui1 £ RJ, w2 G R', w = co^w1, w2) — вектор двойственных переменных. Оптимальное решение задачи (2.20) обозначается через w* = col(wb, w2*)

Через А1, В1, b1 обозначаются матрицы и вектор, полученные в результате перестановки строк матриц Л1 и В1 и координат вектора Ь1 в порядке убывания величин соответствующих им двойственных переменных, т. е. координат вектора wu. Отсортированный в порядке убывания компонент вектор wu обозначается через w*.

Пусть s — номер строки матрицы Л1 и Б1, который соответствует минимальной, отличной от нуля, координате вектора w*. Трансформированное доверительное множество имеет вид Сд = Blx < -Älv} — д|, где Д € К17. Координаты вектора Д определены следующим образом:

W*; __1 _

Аз = JZT~Aь j = 1, s - 1, Д* =--Д2, Аj = -Д2, j = а + 1, J,

¡=1

где Дь Д2 € R1, Д1 ^ 0, Д2 ^ 0, н > 0 — скалярные параметры, задающие трансформацию доверительного множества таким образом, что выполнено вероятностное ограничение Р{Сд} ^ а.

Задача поиска улучшенного гарантирующего решения имеет вид

ux(Ai, Д2) = arg max eV (2.23)

u'eC/1

при ограничениях А1 и1 ^ А1«1 + Д.

Целью является выбор Д1 и Д2 таких, чтобы как можно меньшим оказалось значение критериальной функции равное Д2) по определению и1, при со-

хранении ограничения Р{С"д} ^ а.

- л

Пусть Д2 = xAi —тп—. Начальное значение параметра Д1 установим на уровне w; Y. л;

J = !

Äi = min А?™, где Af™ = maxi А,. | PIx | Bjx-bj+Älü1 s; -rf-Дх)

L ^ ЕЙ; j

j=i

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

Алгоритм 2.3

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

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

2) Если при Дг = Дг, справедливо неравенство Р{Сд} < а, то переходим к шагу 5.

3) Находим минимальное из Дг € [0; Дг] такое, что Р{Сд} ^ а.

4) Решаем задачу (2.23) при Дг = Д^, находим ^(Дх). Если й*+1(Дх) < то полагаем := й1(Дх).

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

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

7) В качестве искомого гарантирующего решения й^ возьмём и\.

Для нахождения улучшенного по отношению к й1 решения достаточно найти любое Дх € [0; Дх], при котором будут выполнены неравенства Р{Сд} ^ а и й!+1(Д,) ^ Доказательство сходимости данного алгоритма приведено в [1].

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

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

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

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

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

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

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

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

1. Исследованы свойства критериальной функции двухуровневой задачи стохастического линейного программирования с квантильным критерием; сформулированы условия существования решения задачи [4,18,20].

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

3. Доказана эквивалентность двухуровневой задачи стохастического линейного программирования с квантильным критерием и двухэтапной задачи стохастического программирования с квантильным критерием и равновесными ограничениями [4,18, 20].

4. Разработан метод сведения двухуровневой задачи стохастического линейного программирования с квантильным критерием и дискретным распределением случайных параметров к смешанной целочисленной задаче линейного программирования и алгоритм синтеза её оптимальной стратегии [2,4,11-13,19,20].

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

6. Решены три прикладные задачи, в частности задача оптимизации деятельности авиационного транспортного узла и задача оптимизации структуры наземного космического комплекса [3,5-9,14-17,22].

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

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

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

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

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

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

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

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

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

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

9. Иванов C.B. Задача распределения инвестиций в развитие отраслей производства // Вопросы создания аэрокосмических и ракетных летательных аппарате / Под ред. профессора Комарова Ю.Ю. — М.: Изд-во Ваш полиграфически партнер, 2013. - С. 201-207.

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

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

12. Ivanov S. V., Naumov A. V. An algorithm for solving a linear discrete stochasti programming problem with the quantile criteria // Actual problems of aviation and aerospace systems. — 2011. — No. 2 (33). — Vol. 16. — P. 179.

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

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

15. Naumov А. V., Ivanov S. V. The problem of distribution of the investment capital allocated for reconstruction of the aerospace complex // Actual problems of aviation and aerospace systems. — 2012. — No. 1 (34). — Vol. 17. — P. 164.

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

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

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

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

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

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

Программа для ЭВМ

22. Иванов C.B. Оптимизация структуры наземного космического комплекса // Свидетельство о государственной регистрации программы для ЭВМ № 2013619236 от 27 сентября 2013 г.

Подписано в печать: 13.11.13 Тираж: 100 экз. Заказ № 1001 Отпечатано в типографии «Реглет» г. Москва, Ленинградский проспект д. 74 (495)790-47-77 wwww.reglet.ru

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ (национальный исследовательский университет)

04201450490 „

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

Иванов Сергей Валерьевич

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

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

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

Научный руководитель:

доктор физико-математических наук,

доцент А. В. Наумов

Москва, 2013 год

Оглавление

Введение 4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение 111

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

Введение

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

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

Впервые двухуровневая задача была рассмотрена Г. фон Штакельбергом при изучении моделей рынка [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|.

Одним из основных методов решения данной задачи является обобщённый минимаксный подход,