Математика

Параллельные алгоритмы целочисленной оптимизации

год издания — 1987, кол-во страниц — 224, тираж — 7100, язык — русский, тип обложки — мягк., масса книги — 200 гр., издательство — Радио и связь

цена: 299.00 руб

Сохранность книги — хорошая

Р е ц е н з е н т ы:
д-р техн. наук, проф. Б. А. Головкин
д-р техн. наук, проф. Д. Б. Юдин

Формат 84x108 1/32. Бумага писчая №1. Печать высокая

Настоящая монография посвящена актуальным проблемам, связанным с разработкой параллельных численных методов для решения типичных задач целочисленной оптимизации, которые возникают в различных приложениях и теоретических исследованиях.

В книге рассматриваются следующие вопросы: математические постановки прикладных задач; параллельные алгоритмы решения сформулированных задач; машинная реализация алгоритмов. Излагаемые вычислительные методы, реализованные с помощью средств параллельного программирования на реальной параллельной вычислительной системе, позволяют ускорить счёт в десятки и сотни раз. Это открывает путь к решению многих ранее недоступных важных практических задач, таких как обработка огромных массивов данных, выбор оптимального маршрута в различных случаях, оптимизация параметров сети ЭВМ и систем передачи данных, составление расписаний и др.

Для научных работников, специализирующихся в области вычислительной техники, программирования, электроники, связи, имеющих дело с оптимизацией. Она будет полезна инженерно-техническим работникам и аспирантам вузов.

Табл. 6. Ил. 34. Библиогр. 82 назв.

Задачи целочисленной оптимизации возникают в различных приложениях и теоретических исследованиях. Настоящая монография посвящена изучению численных методов целочисленной оптимизации с точки зрения их распараллеливания. Интерес к параллельным вычислениям обусловлен следующими тремя основными причинами:
параллельные алгоритмы необходимы параллельным вычислительным системам, уже созданным и проектируемым;
переход от привычных последовательных вычислений к параллельным открывает новые возможности для построения алгоритмов;
распараллеливание вычислений позволяет во много раз увеличить скорость счёта.

В первых двух главах книги даётся общая характеристика задач и методов, которые составляют предмет целочисленной оптимизации, и приводятся математические модели часто встречающихся прикладных задач. Эти модели представляют собой задачи оптимизации, в которых ограничения, как правило, линейные, а все переменные или их часть целочисленные.

Важнейшие преобразования задач целочисленной оптимизации содержатся в гл. 3. Практическое значение преобразований заключается в том, что они дают возможность свести огромное количество разнообразных задач к небольшому числу стандартных задач, для решения которых уже имеются программные средства.

Далее рассматриваются основные принципы построения параллельных алгоритмов (гл. 4), параллельные алгоритмы метода ветвей и границ для решения задач комбинаторной и целочисленной оптимизации (гл. 5) и параллельные алгоритмы метода секущих плоскостей для нахождения оптимального решения целочисленной и смешанной целочисленной линейных задач (гл. 6).

В последних главах анализируются и сравниваются различные вычислительные схемы для приведения целочисленной матрицы к специальному виду (гл. 7) и приводятся краткие сведения о десяти вспомогательных Алгол-процедурах для решения семи математических задач, встречающихся в качестве подзадач в методах целочисленной оптимизации.

Чтобы облегчить чтение монографии и активное усвоение излагаемого материала (по возможности без обращения к другим источникам), в книгу включены некоторые методы преобразования и решения задач целочисленной оптимизации (в достаточно общей форме), ряд последовательных алгоритмов и разнообразные примеры, формулируемые в виде упражнений для самостоятельной работы.

На вопрос, является ли распараллеливание алгоритмов магистральным путём целочисленной оптимизации, автор ответил бы следующим образом. В настоящее время, по-видимому, нет. Однако в ближайшем будущем параллельные вычисления, безусловно, станут преобладать в численных методах целочисленной оптимизации и её приложениях, как и в других разделах вычислительной математики. Для того чтобы это произошло, предстоит выполнить огромную работу в областях математики и программирования, высокопроизводительной вычислительной техники и электроники. Высказанное мнение автора разделяют и другие исследователи.

Ограниченный объём книги не позволил рассмотреть в ней вопросы параллелизма в таких разделах оптимизации, как преобразование задач комбинаторной оптимизации, анализ вычислительной сложности задач целочисленной и комбинаторной оптимизации, теория секущих плоскостей и др.

В заключение автор выражает глубокую благодарность рецензентам книги профессорам Б. А. Головкину и Д. Б. Юдину за содержательные критические замечания, а также всем, кто помогал ему в работе над книгой.

ПРЕДИСЛОВИЕ

Предисловие	3

Г л а в а 1. Задачи и методы целочисленной оптимизации	5

1.1. Постановка задач	5
1.2. Численные методы	12
1.3. Вычислительная сложность задач целочисленной
оптимизации	17
1.4. Элементы теории секущих плоскостей	21
1.5. Параллельные вычисления	25
1.6. Машинная реализация	28

Г л а в а 2. Целочисленные формулировки прикладных задач	29

2.1. Запись условий в бинарных переменных	30
2.2. Выбор оптимального варианта	37
2.3. Неделимые величины	38
2.4. Задачи о покрытии, разбиении и упаковке множества	40
2.5. Две задачи о назначениях	45
2.6. Задача о расписании работ на машинах	46
2.7. Учёт фиксированных доплат	47
2.8. Задачи о размещении предприятий	49
2.9. Задача о перевозке продукта	53
2.10. Сетевой график	54
2.11. Выбор оптимального маршрута	56

Упражнения	60

Г л а в а 3. Преобразования задач целочисленной оптимизации	66

3.1. Общие замечания	66
3.2. Уменьшение размеров задачи	70
3.3. Преобразование бинарной линейной задачи в задачи
о покрытии, разбиении и упаковке	75
3.4. Линейная релаксация задач о покрытии и разбиении	79
3.5. Задача о потоке минимальной стоимости	83
3.6. Преобразование задачи о ранце в задачу о кратчайшем
пути	88
3.7. Преобразования целочисленной линейной задачи над
конусом	89
3.8. Эквивалентность целочисленных линейных задач	93
3.9. Преобразование смешанной целочисленной линейной
задачи в целочисленную	97
3.10. Преобразование целочисленной линейной задачи в
линейную	99
3.11. Линеаризация нелинейной задачи	100

Упражнения	102

Г л а в а 4. Методы распараллеливания вычислений	106

4.1. Принцип распараллеливания данного
последовательного алгоритма	106
4.2. Метод сдваивания	111
4.3. Распараллеливание рекурсий	114
4.4. Умножение матрицы на вектор	118
4.5. Характеристика некоторых параллельных процессов	120

Упражнения	122

Г л а в а 5. Параллельные алгоритмы ветвей и границ	123

5.1. Выполнение p-ветвевого обхода дерева перебора	123
5.2. Общий p-алгоритм ветвей и границ	125
5.3. Линейная релаксация .	128
5.4. Неявный перебор	131
5.5. Коническая релаксация	140
5.6. Распараллеливание алгоритмов динамического
программирования	141
5.7. Приближенные p-алгоритмы	144

Упражнения	145

Г л а в а 6. Параллельные алгоритмы секущих плоскостей	147

6.1. Выполнение p-умножения двух матриц	147
6.2. Секущие плоскости	148
6.3. Прямые и двойственные алгоритмы	152
6.4. Алгоритм нахождения всех крайних лучей
заострённого конуса	155
6.5. Прямой алгоритм решения целочисленной линейной	158
6.6. Прямой алгоритм решения целочисленной линейной
задачи оптимизации	160
6.7. Обоснование алгоритмов	167

Упражнения	173

Г л а в а 7. Приведение целочисленной матрицы к
специальному виду	175

7.1. Оценка числа итераций алгоритма Евклида	176
7.2. Множители в представлении наибольшего общего
делителя	181
7.3. Элементарные преобразования целочисленной
матрицы	185
7.4. Алгоритмы приведения целочисленной матрицы к
трапецеидальному виду	188
7.5. Алгоритмы приведения целочисленной матрицы к
нормальному виду	192
7.6. Алгоритмы нахождения общего целочисленного
решения системы линейных уравнений	195
7.7. Машинная реализация и схемы распараллеливания	198

Упражнения	199

Г л а в а 8. Краткие сведения о вспомогательных
АЛГОЛ-процедурах	203

8.1. Общие замечания	203
8.2. Процедура нахождения множителей в представлении
наибольшего общего делителя	204
8.3. Процедуры приведения целочисленной матрицы к
трапецеидальному виду	205
8.4. Процедуры приведения целочисленной матрицы к
нормальному виду	205
8.5. Процедуры нахождения общего целочисленного решения
системы линейных уравнений	206
8.6. Процедура нахождения всех крайних лучей заострённого
конуса	207
8.7. Процедура нахождения всех вершин многогранника	208
8.8. Процедура решения линейной задачи оптимизации	209

Приложение. Основные обозначения и сокращения	211
Список литературы	218

Книги на ту же тему

Компьютер и задачи выбора, Журавлёв Ю. И., сост., 1989
Численные методы, алгоритмы и программы. Введение в распараллеливание: Учебное пособие для вузов, Карпов В. Е., Лобанов А. И., 2014
Введение в параллельные методы решения задач: Учебное пособие, Якобовский М. В., 2013
Параллельное программирование в среде MATLAB для многоядерных и многоузловых вычислительных машин: Учебное пособие, Кепнер Д., 2013
Современные языки и технологии параллельного программирования: Учебник, Гергель В. П., 2012
Итерационные методы для разреженных линейных систем: Учебное пособие. — В 2-х томах. Том 1, Саад Ю., 2013
Параллельные вычислительные системы, Головкин Б. А., 1980
Многоядерное программирование, Эхтер Ш., Робертс Д., 2010
Принципы работы и система программного обеспечения МП ЕС 2700, Семерджян М. А., Налбандян Ж. С., Гаспарян Л. X., 1988

http://knigoprovod.ru

/Наука и Техника/Математика

ОГЛАВЛЕНИЕ

Книги на ту же тему