Введение
Глава 1. Построение двойственного описания полиэдра 12
1.1. Основные понятия и обозначения 12
1.2. Постановка задачи 21
1.3. Методы построения двойственного описания полиэдра 23
1.4. Оценки трудоемкости 26
1.5. Некоторые приложения 31
Глава 2. Новая модификация метода двойного описания 34
2.1. Задача построения двойственного описания полиэдрального конуса 34
2.2. Метод двойного описания 35
2.3. Использование идей алгоритма Quickhull в методе двойного описания 45
2.4. Описание алгоритма 46
2.5. Оценки трудоемкости 52
2.6. Вычислительный эксперимент 57
Глава 3. Быстрый способ проверки правил Черникова в методе исключения Фурье—Моцкина 62
3.1. Задача исключения переменных из системы линейных неравенств 62
3.2. Метод исключения Фурье-Моцкина 64
3.3. Быстрый способ проверки правил Черникова 70
3.4. Вычислительный эксперимент 75
3.5. Возможности использования параллельных вычислений 77
Глава 4. Удаление неравенств из фасетного описания полиэдра 79
4.1. Постановка задачи 79
4.2. Обзор методов решения 80
4.3. Инкрементный алгоритм 81
4.4. Новый алгоритм удаления неравенств 83
4.5. Вычислительный эксперимент 88
Заключение 91
Список литературы
