Методы отсечения в задачах оптимизации

• Автор: Булатов, Валерьян Павлович
• Шифр специальности: 05.13.02
• Научная степень: Докторская
• Год защиты: 1984
• Место защиты: Иркутск
• Количество страниц: 259 c. : ил

ВВЕДЕНИЕ

Глава I. МЕТОДЫ ОПОРНЫХ ВЫПУКЛЫХ МНОЖЕСТВ В ВЫПУКЛОМ

ПРОГРАММИРОВАНИИ.

I. Методы минимизации выпуклой функции на выпуклом многограннике

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

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

аппроксимация графика минимизируемой функции кусочнолинейными формаг.ш

Обсуздение методов

Приложение методов .

2. Методы минимизации на выпуклых множествах .

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

Аппроксимация границы допустимой области семейства опорных плоскостей .
3. Методы погружения без вложения .
Методы опорных множеств.
Метод опорного конуса
Глава 2. МЕТОДЫ 1ЩТРИР0ВАННЫХ ОТСЕЧЕНИЙ В ВЫПУКЛОМ
ПРОГРАММИРОВАНИИ.
I. Введение
2. Методы центров тяжести .
3. Задача покрытия П мерным симплексом усеченного
П мерного ортогонального симплекса
Постановка задачи
Редукция к экстремальной задаче
Решение экстремальной задачи .
Гарантированная оценка уменьшения объема . .
4. Первый алгоритм решения задачи.
5. Задача оптимального покрытия г. мерным симплексом правильного усеченного симплекса .
Постановка задачи.
Редакция к экстремальной задаче .
Решнке экстремальной задачи .
Гарантированная оценка уменьшения объема .
6. Второй алгоритм решения задачи.
7. Метод чебышевских точек
Идея методов.
Первый метод решения задачи С 12 .
Второй метод решения задачи 12 .
8. Комментарии.
Глава 3. МЕТОДЫ ПОИСКА ЛОКАЛЬНОГО РЕШЕНИЯ НЕКОТОРЫХ ЗАДАЧ
ВОГНУТОГО ПРОГРАММИРОВАНИЯ
I. Задача вогнутого программирования
2. Метод локального решения задачи вогнутого програм
мирования с ограничениям в форме неравенств . . . .
3. Метод локального решения задачи вогнутого программирования с ограничениями в форме равенств
Глава 4. МЕТОДЫ РЕШЕНИЯ МНОГОЭКСТРЕМАЯЬНЫХ ЗАДАЧ ГЛОБАЛЬНЫЙ ПОИСК
I. Минимизация вогнутой функции на многограннике
Метод решения задачи 1.1, 1.2 .
Некоторые интерпретации метода .
2. Минимизация функции, удовлетворяющей условию Липшица на ограниченной областиМ
3. Методы аппроксимации
г Ц.
4. Отсечения в .
5. Метод поиска абсолютного минимума в выпукловогнутых задачах математического программирования . . .
6. Достаточные условия сходимости методов погружения
Глава 5. МИНИМИЗАЦИЯ ФУНКЦИЙ НА ДОПУСТИМОЙ ЦЕЛОЧИСЛЕННОЙ
РЕШЕТКЕ ВЫПУКЛОГО МНОГОГРАНШЖА
I. Методы отсечения .
Описание метода .
Обоснование правильности отсечений
Сходимость метода .
2. Эффективные правильные отсечения .
Критерии эффективности отсечений .
3. Связь с методом Гомори и другими методами
4. Отсечения по ортогональному конусу .
Глава 6. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕКОТОРЫХ ИГРОВЫХ ЗАДАЧ I. Методы решения минимаксных задач
Методы решения задачи I.
Методы решения задачи
2. Методы поиска минимума выпуклой функции при ограничениях под знаком i тазОУ
Первый метод решения задачи 2.2.
Второй метод решения задачи 2.
3. Методы поиска точек равновесия игр г. лиц
Свойства точек равновесияК
Первый метод поиска точки равновесия
Второй метод з
4. Численные методы поиска максимина минкмакса . . .з9г
Глава 7. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ТЕОРИИ ОПТИМАЛЬНЫХ ПРОЦЕССОВ
I. Решение задач с обыкновенными дифференциальными
связями.
2. Решение некоторых задач оптималтного управления
с распределенными параметрами .
3. Минимизация вогнутой функции на конечном состоянии линейной системы обыкновенных дифференциальных
уравнений.
Глава 8. ПРИЛОЖЕНИЕ. ПРИМЕНЕНИЕ МЕТОДОВ ОТСЕЧЕНИЯ ПРИ
ИССЛЕДОВАНИИ БОЛЬШИХ СИСТЕМ ЭНЕРГЕТИКИ.
I. Выпуклое программирование
Задача распределения резервов мокроети в электроэнергетических системах ЭЗС
задача оптимального распределения водных ресурсов .
Оптимизация нормальных режимов электроэнергетических систем.
2. Многоэкстремальные задачи
Оптимизация трассировки трубопроводных систем 3 3. Целочисленное программирование
Задача выбора оптимального числа работающих агрегатов электростанции .
4. Игровые задачи
Задача выбора коэффициентов усиления регуляторов возбуждения в ЗЗС.
5. Оптимальное управление.
Управление переходными процессами в ЭЗС . . .
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Последняя версия метода опорного конуса для решения общей задачи выпуклого программирования авторы И. А.Александров и П. Т.Семеней использовалась для решения одной задачи стохастического программирования, связанной с оптимальным распределением водных ресурсов при планировании производства сельскохозяйственной продукт модель разработана в ВЦ АН СССР, г. Москва. Предложенный автором метод опорной гиперплоскости применялся в Отделе энергетики АН МССР для оптимизации режима гидротепловой энергосистемы г. Кишинев. Методы погружения при глобальной оптимизации использовались в институте нефтехимической и газовой промышленноети им. И.М. Губкина г. Москва при оптимизации системы газосырьевых комплексов. Сотрудниками лаборатории методов оптимизации СЭИ СО АН СССР по предложенным в работе методам разработан ряд программ на БЭСМ6, которые использовались для решения следующих прикладных задач распределение резервов мощности в электроэнергетических системах, оптимальное распределение водных ресурсов, оптимизация трассировки трубопроводных систем, выбор оптимального числа работающих агрегатов электростанции, выбор коэффициентов усиления регуляторов возбуждения в электроэнергетической системе и управление переходными процессами в электроэнергетических системах , юбю. Результаты, нашедшие отражение в диссертации, докладывались на П,У и УПХ Всесоюзных шкожгах по методам оптимизации и теории управления в гг. У1 Сибирских школахсеминарах по
методам оптимизации и их приложениям в гг. У1 Всесоюзных конференциях по проблемам теоретической кибернетики г. Новосибирск , гг. Ш Всесоюзных конференциях по теории игр и исследованию операций, П1У Всесоюзных конференциях по теории игр и исследованию операций, П1У Всесоюзных симпозиумах по экстремальным задачам гг. У конференциях по методам математического программирования и программному обеспечению г. Свердловск, гг. Гродно, г. ХУ1 Международной конференции Математическая оптимизация п. Зеллин, ГДР, г. Международной конференции по стохастическому программированию г. Киев, г. ВЦ АН СССР, ИМ СО АН СССР, МММ УНЦ АН СССР, ИК АН УССР. Основное содержание диссертации освещено в статьях, одной монографии и одном препринте. Глава . I. Постановка задачи. Сх с, Х ь
где С матрица размеров тп. РСое . Утьиг. Хп пи 1. Аппроксимация надграфика функции пересечением выпуклых опорных множеств. V. П V н , где V и Vпн множества граничных точек V, V пи . Итерационный процесс решения задачи I. I состоит в построении последовательности выпуклых опорных множеств к надграфину функции У ос с последующей минимизацией на их пересеченш. Пусть X , X решение, подученное на Уом шаге итерационного процесса. Л . РСос. С4. Теорема 1. Ппн V , . Със1 осО зс, г У г у. Подставляя 1. Так как по построению рСхЗР ,
р а Сзсг оХ е ос. С
Р , ЬгЛ
р р
1. Используя соотношения и , усилим неравенство 1. Из ограниченной последовательности ос внделим сходящуюся подпоследовательность . Тогда из 1. РР и теорема доказана. Приведем примеры построения последовательности множеств
3. Аппроксимация графика минимизируемой функции кусочнолинейными формами. ДЛЯ е
ас. Опорное полупространство 1. О., . X 9 i 4i0УеР. УС О. Приведем два алгоритма решения задачи 1. Первый метод аппроксимации графика функции РСэе . А V С ii ,
4 а. ФкСх о. Ркн хе О. Итерационный процесс начинается с V У6 Ь . Теорема 1. Пусть II аРЦ с , г , Я,. Тогда существует Фет фаСог. Р . Доказательство. Известно, что задача ,6 эквивалентна следующей задаче линейного программирования. РС0 аЧх 1. ЦС. УСос э. Как и в большинстве итеративных методов, в изложенном алгоритме выбор стратегии на каждом шаге формирование членов последовательности , 1 зависит от значения некоторого параметра XПричем в силу теоремы 1. Л . Естественно желание в некотором смысле оптимально задавать значение Х о, лЦ . Очевидно, что оптимальный, в определенном смысле, выбор Л на каждом шаге может оказаться х. М шагов итеративного процесса. Тогда по аналогии с шаговым методом наискорейшего спуска можно ввести понятие шагового оптимального метода аппроксимации.