Введение
1. Применение генетического алгоритма для решения больших оптимизационных задач 19
1.1. Генетический алгоритм как метод нахождения оптимальных решений 19
1.2. Метод решения задачи одномерного раскроя на основе генетического алгоритма 23
1.2.1. Общее описание задачи одномерного раскроя материалов 23
1.2.2.Метод генерации столбцов 27
1.2.3.Математическая постановка задачи раскроя стальных листов разных размеров 30
1.2.4.Генетический алгоритм для решения задачи раскроя стальных листов 34
1.2.5.Практические результаты применения алгоритма GA-CG для задачи раскроя 36
1.3. Использования генетического алгоритма для решения задачи покрытия множества 39
1.3.1.Постановка задачи о покрытии множества 39
1.3.2. Подход, основанный на генетическом алгоритме, для нахождения минимального покрытия 41
1.3.3.Результаты использования ГА для решения задачи покрытия множества 49
1.4. Оптимизация структуры атомного кластера с помощью генетического алгоритма 53
1.4.1.Задача конфигурационной оптимизации атомного кластера 53
1.4.2.Обзор предложенных методов 55
1.4.3.Генетический алгоритм оптимизации структуры атомного кластера 60
1.4.4. Параллельная реализация 63
1.4.5. Результаты численных экспериментов нахождения оптимальной структуры атомного кластера 64
2. Метод ньютона для решения задачи линейного программирования большой размерности 67
2.1. Нахождение проекции точки на множество решений двойственной задачи линейного программирования . 67
2.2. Программная реализация и результаты вычислений метода Ньютона для решения двойственной задачи ЛП . 81
3. Параллельная реализация обобщенного метода ньютона для решения задачи линейного программирования большой размерности 88
3.1. Параллельный итерационный алгоритм 88
3.2. Основные операции параллельного алгоритма 90
3.3. Схемы разбиения данных
3.3.1.Столбцовая схема
3.3.2.Строчная схема
3.3.3.Клеточная схема
3.3.4.Безматричная схема
3.4. Результаты численных экспериментов
Выводы 102
Цитированная литература 104
