РАЗРАБОТКА И РЕАЛИЗАЦИЯ СПЕЦИАЛИЗИРОВАННОГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ДЛЯ КУРСА «МЕТОДЫ ОПТИМИЗАЦИИ»

РЕФЕРАТ 3
Введение 6
Постановка задачи 7
1 Теоретическая часть. Анализ предметной области 9
1.1 Градиентные методы поиска экстремума функции 9
1.1.1 Градиентный спуск 9
1.1.2 Наискорейший спуск 10
1.1.3 Покоординатный спуск 11
1.1.4 Метод Гаусса - Зейделя 11
1.2 Овражные методы поиска экстремума функции 12
1.2.1 Первый овражный метод 13
1.2.2 Второй овражный метод 14
1.3 Прямые методы поиска экстремума функции одной переменной 14
1.3.1 Метод золотого сечения 14
1.3.2 Метод ДСК (Дэвиса-Свенна-Кэмпи) 14
1.3.3 Метод Пауэлла 15
1.4 Симплекс-метод решения задачи линейного программирования 16
1.5 Транспортная задача и её решение методом потенциалов 17
2 Разработка архитектуры программного обеспечения 19
1.1 Используемые технологии 19
1.2 Общее описание архитектуры 20
1.3 Базовый модуль 21
1.4 Модули методов 21
1.5 Графический модуль 23
1.6 Модуль отчётов 24
3 Описание реализации программного обеспечения 26
3.1 Вспомогательные структуры 26
3.1.1 Многомерная точка (class Point) 26
3.1.2 Многомерная функция (class Function) 27
3.1.3 Класс многомерных функций (class ClassOfFunctions) 29
3.2 Базовый модуль (class BaseModule) 31
3.3 Графический модуль (class PlotModule) 33
3.4 Модуль отчётов (class ReportModule) 34
3.5 Главное окно (class MainWindow) 34
3.6 Модули методов 36
3.6.1 Градиентные методы (class GradientMethods) 36
3.6.2 Овражные методы (class RavineMethods) 38
3.6.3 Методы прямого поиска (class DirectSearchMethods) 40
3.6.4 Симплекс-метод (class SimplexAlgorithm) 41
3.6.5 Транспортная задача (class TransportationTheory) 42
Заключение 44
Литература
Купить

Задачей методов оптимизации в общем случае является выбор какого-либо действия х* из множества допустимых действий D, при этом соблюдаются два условия:
1. Каждому действию х из D взаимно однозначно соответствует величина, характеризующая его качество: f (х);
2. f (х) достигает экстремума в точке х*.
Целями лабораторных работ курса «Методы оптимизации» является формирование у студентов общего представления о специфике оптимизационных задач, а также для наглядной демонстрации преимуществ и недостатков тех или иных методов решения таких задач.
Для выполнения этих целей в 2001 году было разработано специализированное программное обеспечение, однако при его анализе был обнаружен ряд недостатков:
- проблемы совместимости с современными операционными системами ;
- отсутствие файлов с исходным кодом (для внедрения улучшений и исправлений);
- отсутствие кроссплатформенности;
- неудобный и громоздкий интерфейс.
Ввиду вышеперечисленных причин имеется необходимость в разработке нового программного обеспечения, обладающего тем же функционалом, но лишённого вышеперечисленных недостатков. При этом такое решение предпочтительнее использования готовых пакетов прикладных программ, поскольку:
1. Даёт возможность выполнения лабораторных работ вне университета ;
2. Выполнение лабораторных работ возможно студентами, не обладающими опытом работы с пакетами прикладных программ ;
3. Программное обеспечение проще адаптировать при изменении инфраструктуры,
в то время как в случае использовании пакетов прикладных программ это может
потребовать больших затрат.
Для разработки программного обеспечения был выбран язык C++,
обеспечивающий хорошее быстродействие, что имеет существенное значение в тех лабораторных работах, где необходимо проводить большое количество вычислений. Кроме того, при разработке использованы библиотеки Qt, обеспечивающие кроссплатформенность и позволяющие уменьшить связность компонент программного обеспечения.
Постановка задачи
В лабораторных работах курса "Методы оптимизации" в настоящее время рассматриваются методы 5 разделов:
1. Минимизация функции градиентными методами
2. Минимизация функции овражными методами
3. Минимизация функции методами прямого поиска
4. Решение задачи линейного программирования симплекс-методом
5. Решение транспортной задачи методом потенциалов
В каждом из методов пользователем задаются различные исходные данные и параметры, необходимые для работы метода.
На основе этих входных данных требуется выполнить выбранный метод и вывести на экран результаты его работы (графически или в виде текстового отчёта). В некоторых методах требуется интерактивное взаимодействие с пользователем.
Для реализации этих методов программное обеспечение должно обладать следующими возможностями:
- работа с функциями многих переменных различного типа с высокой точностью (не менее 0.5*10-5);
- изображение графика функции одной переменной и линий уровня функции двух переменных;
- включать в себя систему генерации различных видов функций в зависимости от введённого варианта;
Кроме того, для упрощения сопровождения и возможности последующего развития (например, добавление новых методов и алгоритмов при изменении программы курса), программное обеспечение должно быть легко модифицируемым и расширяемым. Этой цели можно достигнуть разделением программного обеспечения на несколько модулей, слабо связанных между собой.
Для осуществления обозначенной задачи служат следующие подзадачи:
1. Разработка общей архитектуры программного обеспечения;
2. Разработка и реализация базового модуля;
3. Разработка и реализация графического модуля;
4. Разработка и реализация модуля генерации отчётов;
5. Реализация всех разделов курса "Методы оптимизации";
5.1. Разработка системы вариантов для генерации функций (необходимы для методов минимизации функций);
5.2. Реализация всех 11 методов курса.

Купить