Параллельные алгоритмы целочисленной оптимизации, Хохлюк В.И.

Параллельные алгоритмы целочисленной оптимизации, Хохлюк В.И.

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




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

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

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

ОГЛАВЛЕНИЕ.
ПРЕДИСЛОВИЕ
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. ПРОЦЕДУРА РЕШЕНИЯ ЛИНЕЙНОЙ ЗАДАЧИ ОПТИМИЗАЦИИ.
ПРИЛОЖЕНИЕ. ОСНОВНЫЕ ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ.
СПИСОК ЛИТЕРАТУРЫ.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Параллельные алгоритмы целочисленной оптимизации, Хохлюк В.И. - fileskachat.com, быстрое и бесплатное скачивание.

Скачать djvu
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - djvu - Яндекс.Диск.




Теги: учебник по математике :: математика :: Хохлюк