ДПиДМО

252

3.6.Двойственный симплекс-метод

3.6.1.Двойственный симплекс-метод в строчечной форме

3.6.2.Двойственный симплекс-метод в столбцовой форме

3.7.Задачи

Глава 4. Транспортная задача

4.1.Постановка задачи и основные свойства

4.2.Унимодулярные матрицы

4.2.1.Задача о назначениях

4.3.Графовая характеристика планов транспортной задачи

4.4.Способы получения начального допустимого базисного вектора

4.4.1.Метод северо-западного угла

4.4.2.Метод минимального элемента

4.5.Пересчет базисного решения при изменении базы

4.6.Метод потенциалов

Глава 5. Целочисленное линейное программирование

5.1.Основные определения

5.2.Примеры задач целочисленного линейного программирования

5.2.1.Задача о рюкзаке

5.2.2.Задачи с фиксированными доплатами

5.2.3.Дихотомии

5.2.4.Задачи о выполнимости КНФ

5.2.5.Задача о «раскрое»

5.2.6.Задача коммивояжера

5.3.Идея метода правильных отсечений

5.4.Циклический алгоритм Гомори

5.5.Полностью целочисленный алгоритм

5.6.Прямой метод целочисленного программирования

5.7.Задача о рюкзаке. Динамическое программирование

5.8.Метод ветвей и границ

5.9.Задачи

254

1.4.2.3. Неполные адаптивные вероятностные модели Глава 2. Теоретические основы аналитического решения задач опти-

мизации

2.1.Обобщение условий экстремума на задачи векторной оптимизации

2.2.Условия оптимальности в дифференциальной форме для многокритериальных задач оптимизации специального и общего вида

2.2.1.Условия первого порядка

2.2.2.Условия второго порядка

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

Глава 3. Общие методы учета ограничений в задачах математического программирования

3.1.Общие методы учета ограничений, обзор методов

3.2.Метод внешнего штрафа

3.2.1.Общее описание и некоторые свойства

3.2.2.Исследование сходимости и алгоритм настройки коэффициента штрафа

3.2.3.Структура возникающих задач со штрафом и характер приближения оценок к решению

3.2.4.Оценки скорости сходимости метода внешнего штрафа

3.2.5.Недостаточность локальных методов при использовании метода штрафов

3.3.Метод модифицированных функций Лагранжа

3.3.1.Общая схема метода множителей Лагранжа и ее недостатки

3.3.2.Преобразование постановки задачи, сведение задач с неравенствами к задачам с равенствами

3.3.3.Построение модифицированной функции Лагранжа

3.3.4.Метод модифицированной функции Лагранжа для задач

сограничениями-равенствами

3.3.5.Метод модифицированной функции Лагранжа в задачах

сравенствами и неравенствами

3.4.Другие общие методы учета ограничений

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

3.4.2.Метод допустимой точки

3.4.3.Индексный метод учета ограничений

256

Глава 4. Математические основы построения и анализа алгоритмов оптимизации

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

4.1.1.Основные обозначения

4.1.2.Формальная модель и общая вычислительная схема

4.1.3.Сходимость и оценки решения

4.2.Принципы построения методов оптимизации

4.3.Одношагово-оптимальные методы оптимизации

4.3.1.Принцип одношаговой оптимальности

4.3.2.Метод ломаных как одношагово-оптимальный алгоритм

4.3.3.Информационно-статистический метод Р.Г. Стронгина

4.3.4.Одношагово-оптимальный байесовский метод Х. Кушнера

4.3.5.Одношагово-оптимальный метод на основе адаптивных вероятностных моделей для задач с ограничениями

4.3.6.Асимптотическая оптимальность

4.4.Теоретические основы сходимости одномерных алгоритмов глобального поиска

4.4.1.Характеристические алгоритмы оптимизации

4.4.2.Двусторонняя сходимость и условие остановки

4.4.3.Типология сходимости

4.4.4.Глобально-оптимальная сходимость

4.5.Анализ сходимости многомерных методов многоэкстремальной оптимизации. Т-представимые алгоритмы и их свойства

4.5.1.Описание класса задач

4.5.2.Класс Т-представимых алгоритмов, классификация, примеры

4.5.3.Теория сходимости Т-представимых алгоритмов

4.6.Анализ относительной плотности размещения испытаний при всюду плотной сходимости

4.6.1.Необходимые понятия и обозначения

4.6.2.Метод аналитического оценивания относительной концентрации испытаний

Глава 5. Многомерные задачи глобальной оптимизации и фундаментальные способы редукции размерности

5.1.Многоэкстремальные задачи и методы покрытий

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

257

5.3.Многошаговая схема редукции размерности

5.4.Свойства одномерных подзадач многошаговой схемы

5.4.1.Структура допустимых областей одномерного поиска

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

5.5.Редукция размерности на основе кривых Пеано

5.5.1.Кривые Пеано и методы их конструирования

5.5.2.Свойства редуцированных задач оптимизации

5.5.3.Приближенное построение кривых Пеано

5.5.4.Множественная развертка

5.5.5.Применение разверток в задачах с ограничениями

5.6.Компонентные методы

5.6.1.Метод деления на три

5.6.2.Диагональные компонентные методы Я. Пинтера

5.6.3.Эффективные диагональные компонентные методы на основе адаптивных диагональных кривых

5.6.4.Компонентные методы, основанные на триангуляции

области поиска Глава 6. Методы построения оценок множества слабо эффективных

точек, не использующие параметрических сверток

6.1.Основные принципы непараметрической скаляризации

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

6.1.2.Метод неравномерных покрытий Ю.Г. Евтушенко и М.А. Потапова

6.1.3.Точное сведение многокритериальной задачи к скалярной с помощью свертки Д.Л. Маркина, Р.Г. Стронгина

6.2.Реализация метода неравномерных покрытий Ю.Г. Евтушенко по схеме деления на три

6.3.Одношагово-оптимальный метод многокритериальной оптимизации на основе адаптивных стохастических моделей

6.4.Метод построения равномерной оценки множества слабо эффективных точек

Глава 7. Модели и методы поиска локально-оптимальных решений

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

7.1.1.Метод центров тяжести

7.1.2.Метод эллипсоидов

258

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

7.2.1.Общая структура методов поиска локального минимума, принцип локального спуска

7.2.2.Измерения локальной информации и роль модели задачи

вих интерпретации

7.2.3.Классификация траекторных методов локального поиска

7.2.4.Эффективные стратегии поиска вдоль направлений. Регуляризованные алгоритмы одномерного поиска

7.3.Аппроксимационные принципы построения алгоритмов. Анализ свойств классического градиентного метода и метода Ньютона

7.4.Эффективные методы второго порядка для гладких задач

7.4.1Расширение области сходимости метода Ньютона за счет регулировки величины шага

7.4.2.Стратегии модификации матриц Гессе при нарушении их положительной определенности

7.5.Методы первого порядка, явно изменяющие метрику пространства

7.5.1.Квазиньютоновские методы. Рекуррентные соотношения для оценок матриц Гессе по измерениям градиента в основных точках поиска

7.5.2.Модифицированные квазиньютоновские методы

7.5.3.Методы растяжения пространства (R-алгоритмы Н.З. Шора)

7.6.Методы сопряженных направлений

7.6.1.Сопряженные направления и их свойства

7.6.2.Метод сопряженных градиентов Флетчера–Ривса

7.7.Некоторые методы прямого поиска для негладких задач

7.7.1.Метод Нелдера–Мида

7.7.2.Метод Хука–Дживса

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

7.8.1.Специальные методы учета линейных равенств

7.8.2.Специальные методы учета линейных неравенств, методы рабочего набора

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

259

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

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

260