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

• Автор: Иванов, Сергей Валерьевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 130 с. : ил.

Оглавление
Введение
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. Выводы по главе
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. Выводы по главе
Список литературы

Введение
Важной задачей системного анализа является разработка математических моделей, описывающих управление иерархическими системами. Процесс принятия решения в подобных системах должен осуществляется последовательно на нескольких уровнях. Стратегия, выбираемая на нижнем уровне, зависит от стратегии, выбранной на верхнем уровне. При этом интересы субъектов, принимающих решения на различных уровнях могут отличаться, а значит, оптимальные стратегии на различных уровнях выбираются исходя из различных критериев оптимальности. Для математического описания подобных систем используется аппарат двухуровневых и многоуровневых задач математического программирования.
Двухуровневые задачи носят игровой характер. Предполагается наличие двух игроков: лидера и последователя. Первым выбирает стратегию лидер, решая задачу верхнего уровня (задачу лидера). Последователь выбирает свою стратегию из оптимальных решений задачи нижнего уровня (задачи последователя), зная стратегию лидера. Лидер при выборе стратегии может определить оптимальный ответ последователя на эту стратегию.
Впервые двухуровневая задача была рассмотрена Г. фон Штакельбергом при изучении моделей рынка [128], однако интенсивное изучение данных задач приходится на последние три десятилетия. Основные результаты теории двухуровневых задач содержатся в монографиях Дж. Барда [58], Ш. Демпе [83] и обзорах Ш. Демпе [81,82], Л.Н.Висенто, П. Каламая [133] и Б. Колсона, П. Маркотте, Ж. Савара [75,76].
Приложения задач двухуровневого программирования имеют место в самых разнообразных отраслях. Иерархические модели экономики рассматривались в работах Ян Хая, М. Белла [141], транспортная задача изучалась X. Абу-Кандилом и П. Бертраном [55], задача проектирования сетей рассматривалась П. Маркотте [108] и И. Констанином, М. Флорианом [77], модели алю-

V(и,х) = 0), то не существует вектора v, удовлетворяющего свойствам (1.12), (1.13), и Ф(и, х) = +оо. Таким образом, Ф(и.х) может быть определено как оптимальное значение целевой функции задачи (1.11), то есть Ф(и,ж) = Ф'(и,х). Значит, задачи (1.4) и (1.10) имеют одинаковые целевые функции и ограничения, поэтому по лемме 1.1 задачи (1.4) и (1.10) эквивалентны по переменной и. Л
Задача (1.10) является двухэтапной задачей стохастического программирования с равновесными ограничениями (1.13) и кваптильным критерием. Доказанная теорема показывает, что задачи класса двухуровневых задач стохастического линейного программирования с квантильным критерием могут быть сведены к задачам класса двухэтапных задач стохастического программирования с квантильным критерием и нелинейными равновесными ограничениями.
1.5. Сведение двухуровневой задачи стохастического линейного программирования с квантильным критерием к одноэтапной задаче стохастического линейного программирования с квантильным критерием в случае совпадения коэффициентов целевых функций лидера и последователя
В данном разделе изучается случай равенства вектора коэффициентов с2 целевой функции последователя и вектора коэффициентов / функции потерь лидера, связанных со стратегией последователя. Как было отмечено ранее, данная задача является двухэтапной задачей стохастического линейного программирования с квантильным критерием. В данном разделе описывается метод сведения рассматриваемой задачи к одноэтапной задаче стохастического линейного программирования с квантильным критерием.
Рассмотрим следующую задачу:
min jeр | Р |ф(гг. X) < £ j ^ а j —э min, (1-14)
где Ф(и, х) = max j (сч — и + (i^j))T ж|, j = 1, J — вершины мно-
гогранного множества V = {?) € Rm | Bjv ^ с2, v ^ 0}, J — количество вершин множества V.
Справедлива следующая теорема.