- Артикул:00-01117534
- Автор: В. И. Хохлюк
- Тираж: 7100 экз.
- Обложка: Мягкая обложка
- Издательство: Радио и связь (все книги издательства)
- Город: Москва
- Страниц: 224
- Формат: 84х108/32
- Год: 1987
Развернуть ▼
Настоящая монография посвящена актуальным проблемам, связанным с разработкой параллельных численных методов для решения типичных задач целочисленной оптимизации, которые возникают в различных приложениях и теоретических исследованиях.
В книге рассматриваются следующие вопросы: математические постановки прикладных задач; параллельные алгоритмы решения сформулированных задач; машинная реализация алгоритмов. Излагаемые вычислительные методы, реализованные с помощью средств параллельного программирования на реальной параллельной вычислительной системе, позволяют ускорить счет в десятки и сотни раз. Это открывает путь к решению многих ранее недоступных важных практических задач, таких как обработка огромных массивов данных, выбор оптимального маршрута в различных случаях, оптимизация параметров сети ЭВМ и систем передачи данных, составление расписаний и др.
Для научных работников, специализирующихся в области вычислительной техники, программирования, электроники, связи, имеющих дело с оптимизацией. Она будет полезна инженерно-техническим работникам и аспирантам вузов.
Содержание
Предисловие
Глава 1. Задачи и методы целочисленной оптимизации
1.1. Постановка задач
1.2. Численные методы
1.3. Вычислительная сложность задач целочисленной оптимизации
1.4. Элементы теории секущих плоскостей
1.5. Параллельные вычисления
1.6. Машинная реализация
Глава 2. Целочисленные формулировки прикладных задач
2.1. Запись условий в бинарных переменных
2.2. Выбор оптимального варианта
2.3. Неделимые величины
2.4. Задачи о покрытии, разбиении и упаковке множества
2.5. Две задачи о назначениях
2.6. Задача о расписании работ на машинах
2.7. Учет фиксированных доплат
2.8. Задачи о размещении предприятий
2.9. Задача о перевозке продукта
2.10. Сетевой график
2.11. Выбор оптимального маршрута
Упражнения
Глава 3. Преобразования задач целочисленной оптимизации
3.1. Общие замечания
3.2. Уменьшение размеров задачи
3.3. Преобразование бинарной линейной задачи в задачи о покрытии, разбиении и упаковке
3.4. Линейная релаксация задач о покрытии и разбиении
3.5. Задача о потоке минимальной стоимости
3.6. Преобразование задачи о ранце в задачу о кратчайшем пути
3.7. Преобразования целочисленной линейной задачи над конусом
3.8. Эквивалентность целочисленных линейных задач
3.9. Преобразование смешанной целочисленной линейной задачи в целочисленную
3.10. Преобразование целочисленной линейной задачи в линейную
3.11. Линеаризация нелинейной задачи
Упражнения
Глава 4. Методы распараллеливания вычислений
4.1. Принцип распараллеливания данного последовательного алгоритма
4.2. Метод сдваивания
4.3. Распараллеливание рекурсий
4.4. Умножение матрицы на вектор
4.5. Характеристика некоторых параллельных процессов
Упражнения
Глава 5. Параллельные алгоритмы ветвей и границ
5.1. Выполнение р-ветвевого обхода дерева перебора
5.2. Общий р-алгоритм ветвей и границ
5.3. Линейная релаксация
5.4. Неявный перебор
5.5. Коническая релаксация
5.6. Распараллеливание алгоритмов динамического программирования
5.7. Приближенные р-алгоритмы
Упражнения
Глава 6. Параллельные алгоритмы секущих плоскостей
6.1. Выполнение р-умножения двух матриц
6.2. Секущие плоскости
6.3. Прямые и двойственные алгоритмы
6.4. Алгоритм нахождения всех крайних лучей заостренного конуса
6.5. Прямой алгоритм решения целочисленной линейной
6.6. Прямой алгоритм решения целочисленной линейной задачи оптимизации
6.7. Обоснование алгоритмов
Упражнения
Глава 7. Приведение целочисленной матрицы к специальному виду
7.1. Оценка числа итераций алгоритма Евклида
7.2. Множители в представлении наибольшего общего делителя
7.3. Элементарные преобразования целочисленной матрицы
7.4. Алгоритмы приведения целочисленной матрицы к трапецеидальному виду
7.5. Алгоритмы приведения целочисленной матрицы к нормальному виду
7.6. Алгоритмы нахождения общего целочисленного решения системы линейных уравнений
7.7. Машинная реализация и схемы распараллеливания
Упражнения
Глава 8. Краткие сведения о вспомогательных АЛГОЛ- процедурах
8.1. Общие замечания
8.2. Процедура нахождения множителей в представлении наибольшего общего делителя
8.3. Процедуры приведения целочисленной матрицы к трапецеидальному виду
8.4. Процедуры приведения целочисленной матрицы к нормальному виду
8.5. Процедуры нахождения общего целочисленного решения системы линейных уравнений
8.6. Процедура нахождения всех крайних лучей заостренного конуса
8.7. Процедура нахождения всех вершин многогранника
8.8. Процедура решения линейной задачи оптимизации
Приложение. Основные обозначения и сокращения
Список литературы