Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания
Дискретная оптимизация и моделирование в условиях неопределенности данных
Перепелица В. А., Тебуева Ф. Б.
Издательство: Академия Естествознания
Год издания: 2007
ISBN: 978-5-91327-013-9
Работа посвящена математическому моделированию задач дискретной оптимизации, исходные данные которых имеют неопределенный характер. Неопределенность данных представляет собой задание их в виде временных рядов, интервалов или нечетких множеств. В качестве инструментария для структурирования таких неопределенностей выбраны методы нелинейной динамики: фазовые портреты временных рядов, фрактальный анализ и клеточные автоматы. В процессе моделирования указанного класса задач возникает двухуровневый подход: нижний уровень – моделирование исходных данных, верхний уровень – решение оптимизационной задачи. На верхнем уровне рассматриваются теоретико-графовые задачи, для которых предлагаются алгоритмы их решения.
Для специалистов в области моделирования и управления сложными эволюционными процессами и системами, а также для преподавателей, студентов и аспирантов специальностей прикладной математики и теоретических основ информатики.
Глава 1. Необходимый минимум понятий в комбинаторике и вычислениях
1.1. Исторический экскурс в комбинаторику
1.2. Элементарные комбинаторные задачи
1.3. Понятие сложности вычисления и порождения. Время и емкость
1.4. Вычислимые функции и породимые множества. Перечислимые множества и разрешимые множества
1.5. Шкала оценки сложности комбинаторных задач
Глава 2. Основные понятия, примеры задач и методов дискретной оптимизации
2.2. Верхняя, нижняя и точная оценки оптимума Функция Шеннона
2.3. О некоторых элементарных задачах дискретной оптимизации
2.3.1. Вложение дискретной задачи в непрерывную и использование методов математического анализа
2.3.2. Симметрия и оптимизация
2.3.3. Изопериметрические соотношения
2.3.4. Оптимизация при диофантовых соотношениях
2.4. Методы типа покоординатного спуска для дискретных экстремальных задач.
Глава 3. Экстремальные задачи на графах
3.2. Алгоритмы нахождения кратчайшего пути (цепи) между вершинами графа
3.3. Некоторые обобщения задачи о кратчайшем пути
3.4. Задача о кратчайшем остовном дереве и ее приложения
3.5. Классификация задач об остовном дереве по признаку вычислительной сложности
3.5.1. Многообразие целевых функций
3.5.2. Вычислительная сложность 1-критериальных задач
3.5.3. Вычислительная сложность многокритериальных задач
3.6. Эйлеровы обходы (маршруты) в графах.
3.7. Проблема выделения гамильтонова контура (цикла). Задача коммивояжера
3.7.1. К вопросу о критерии распознавания гамильтонова графа
3.7.2. Решение задачи коммивояжера методом динамического программирования
3.7.3. Методы без использования принципа оптимальности Беллмана
4.1.1. Проблема неопределенности в реальном математическом моделировании
4.1.2. Нечеткие данные, возникающие в процессе математического моделирования
4.1.3. Дискретные задачи с интервальными данными
4.2. Прогнозирование эволюционных процессов и систем с памятью
4.2.1. Прогнозирование временных рядов на базе инструментария фазового анализа
4.2.2. Клеточно-автоматное прогнозирование
4.2.3. Гибридные модели прогнозирования
4.3. Концепция двухуровневого подхода к реальному моделированию эволюционных процессов и систем
Глава 5 Задачи оптимизации на графах с интервальными параметрами
5.1. Задачи на графах с интервальными параметрами.
5.2. Сведение интервальной задачи дискретной оптимизации к дискретной многокритериальной задаче.
5.3. Оценки вычислительной сложности
5.4. Полиномиально разрешимые подклассы интервальных задач на графах
5.5. Статистически эффективные алгоритмы
5.6. Асимптотически точный алгоритм