ВВЕДЕНИЕ 3
1. МЕТОДЫ ЦЕНТРОВ 6
1.1. Классический метод центров 6
1.2. Линеаризованный метод центров 8
2. МЕТОД ОТСЕЧЕНИЙ С АПРОКСИМАЦИЕЙ НАДГРАФИКА
ЦЕЛЕВОЙ ФУНКЦИИ 9
3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ 12
4. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ И ПРОВЕДЕНИЕ
ЭКСПЕРИМЕНТОВ 13
4.1. Классический метод центров 13
4.2. Модифицированный метод центров 27
5. ЧИСЛЕННОЕ СРАВНЕНИЕ КЛАССИЧЕСКОГО И
МОДИФИЦИРОВАННОГО МЕТОДОВ ЦЕНТРОВ 31
5.1. Классический метод центров 33
5.2. Модифицированный метод центров 35
6. ПРИМЕНЕНИЕ ЛИНЕАРИЗОВАННОГО МЕТОДА ЦЕНТРОВ ДЛЯ
ЭКОНОМИЧЕСКОЙ МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ 39
ЗАКЛЮЧЕНИЕ 52
СПИСОК ЛИТЕРАТУРЫ 54
ПРИЛОЖЕНИЕ 1
Методы оптимизации находят все более широкое применение в науке и технике. К данным методам обращаются разработчики систем автоматизированного проектирования, инженеры-конструкторы, экономисты и многие другие. С развитием промышленности и ограниченностью ресурсов встала вопрос оптимального использования материалов, энергии, рабочего времени и др. Сюда можно отнести, например, задачи планирования производства для получения максимальной прибыли при заданных ресурсах, задачи управления системой водохранилищ и гидростанций для получения максимальной электроэнергии, задачи о космических перелетах из одной точки пространства в другую с наименьшей затратой энергии или самым быстрым способом и т.д.
В связи с этим разработка новых методов математического программирования, а также численные исследования уже известных методов остаются актуальными.
Данная выпускная работа посвящена численному исследованию методов решения задачи условной минимизации. Один из известных классов методов решения задач нелинейного программирования образуют так называемые методы центров. Для отыскания итерационных точек в этих методах требуется решать задачи безусловной минимизации некоторых вспомогательных функций максимума. Эти вспомогательные задачи не являются простыми, даже в том случае, когда ограничения исходной задачи выпуклого программирования заданы линейными функциями. В выпускной работе исследуется предложенный руководителем вариант метода центров, названный условно линеаризованным методом центров, в котором вспомогательные функции максимума строятся на основе линеаризации
Целью магистерской диссертации является численное исследование упомянутого выше модифицированного метода центров, а также сравнение его с традиционным методом.
Отметим, что в исследуемых методах заложена возможность приближенного решения вспомогательных задач отыскания итерационных точек. Для решения этих задач и в классическом, и в модифицированном методах можно применять многие из известных методов безусловной минимизации. Однако в большинстве из них нет возможности оценивать на каждом шаге точность решения. К методам, где на каждой итерации можно получить оценку близости итерационного значения целевой функции к её оптимальному значению, относятся методы отсечений с аппроксимацией надграфика целевой функции. Именно этим определен выбор одного из методов отсечений для решения вспомогательных задач в исследуемых методах.
С целью численного исследования методов была проделана следующая работа:
1. Изучена отечественная и зарубежная литература, посвященная методам центров [6 с. 74-110], а также методам отсечений с погружением надграфика целевой функции[7-8,14-16];
2. Программно реализованы традиционный и модифицированный методы центров с привлечением процедур отсечений для решения вспомогательных задач;
3. На основе серии численных экспериментов проведен сравнительный анализ классического и модифицированного методов центров и сделаны определенные выводы;
оптимизационная экономическая задача.
Для практической реализации работы использовались пакеты прикладных программ математического моделирования MatrixLaboratory. Программирование осуществлялось на высокоуровневом интерпретируемом языке программирования МА^АВ [10,22].
Магистерская диссертация состоит из введения, шести разделов, заключения, списка литературы из 23 наименования и приложения. В тексте работы содержится 16 таблиц и 26графиков. Общий объем работы 75 страниц.
Первый раздел посвящен описанию традиционного и модифицированного методов центров.
Во втором разделе выпускной квалификационной работы описан метод отсечений, применяющихся в исследуемых методах центров.
В третьем разделе описана программная реализация (работа с программным комплексом, описание процедур).
В четвертом разделе описаны результаты проведенных экспериментов с классическим и модифицированным методами центров.
В пятом разделе описано численное сравнение классического и модифицированного методов центров.
И в последнем шестом разделе приведено решение экономической задачи со многими критериями с помощью линеаризованного метода центров.
В ходе исследования классического и линеаризованного методов центров для решения задачи на экстремум, а также разработки программного комплекса для магистерской диссертации были достигнуты следующие результаты:
> Изучена отечественная и зарубежная литература по тематике работы, посвященная методам центров, а также методам отсечений с погружением надграфика целевой функции;
> Программно реализованы классический и линеаризованный методы центров для решения задачи условной минимизации с привлечением процедур отсечений для решения вспомогательных задач на языке программирования MATLAB;
> На основе серии численных экспериментов проведен сравнительный анализ классического и линеаризованного методов центров и сделаны определенные выводы;
> Линеаризованным методом центров решена многокритериальная оптимизационная экономическая задача.
Из вышесказанного можно сделать вывод о том, что цель работы была полностью выполнена. Результаты магистерской диссертации могут быть применены в многокритериальной оптимизации, планирования бюджета и организации производства.
Также в ходе работы подтвердилась гипотеза о том, что линеаризованный метод решает задачу минимизации быстрее, чем классический. На практике разница оказалась 15%, а при линейных ограничениях линеаризованный метод быстрее классического в 3 раза.
В дальнейшем можно улучшить алгоритм метода сформировав более общий метод выбора начальных отсечений вычисления, используя методы распараллеливания алгоритмов.
