Сравнительная характеристика методов решения задач оптимизации

Классификация методов математического программирования.

Матрицы

Матрицы

Определители

Понятие «определитель» возникло в связи с задачей решения систем линейных уравнений. Возьмем какое-нибудь поле К и рассмотрим простейшие системы уравнений 1-й степени с двумя и тремя неизвестными с коэффициентами из К.

Система двух линейных уравнений с двумя неизвестнымизаписывается в следующем виде:

где - заданные числа из К.

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

Если, то из этого уравнения и аналогичного уравнения, получающегося путем исключения, получим

Знаменатели выражений для неизвестных здесь одинаковы и представляют собой многочлен от элементов основной матрицы А. Значение этого многочлена называют определителем или детерминантом матрицы А и обозначают или.

Если матрица задана своей таблицей, то детерминант обозначают, заключая таблицу в вертикальные черты. Таким образом, по определению для любой квадратной матрицы 2-го порядка

С помощью определителей формулы (2) можно переписать в виде

Решая аналогичным путем систему трех уравнений

, (5)

с тремя неизвестными, получим

и аналогичные выражения для. Конечно, эти выражения имеют смысл лишь в том случае, когда знаменатель их отличен от нуля.

называются снова основной и расширенной матрицами системы уравнений (5). Знаменатель в формуле (6) называется определителем или детерминантом квадратной матрицы 3-го порядка А. Итак, согласно определению

Объединяя справа члены, содержащие элементы, и вспоминая формулу (3), получим

=. (8)

Формулу (8) легко запомнить. Для краткости вместо того, чтобы говорить определитель матрицы 2-го порядка, 3-го порядка, говорят определитель 2-го, 3-го порядка. Три определителя 2-го порядка в формуле (8) получаются из находящегося в ней определителя 3-го порядка вычеркиванием первой строки и соответственно 1-го, 2-го и 3-го столбцов. Далее, определитель 2-го порядка, получившийся вычеркиванием 1-й строки и j- го столбца, следует умножить на элемент, находящийся в первой строке и j- м столбце, все произведения снабдить чередующимися знаками и сложить. В результате и получится определитель 3-го порядка.

Математическое программирование предполагает построение алгоритмов решения задач оптимизации (задач оптимального планирования). В зависимости от свойств целевой функции и ограничений математическое программирование подразделяестся на: линейное; нелинейное (нелинейное при линейных ограничениях: выпуклое; сепарабельное; квадратичное; геометрическое). Это разделение неслучайно. Оно определяется отсутствием универсальных методов решения задач нелинейного программи­рования, для которого разработаны лишь эффективные методы решения отдельных классов задач. Задачи оптимизации связаны с вопросами эффективного использования или распределения ограниченных ресурсов для достижения желаемых целей. Характерной чертой задач оптимизации является большое число реше­ний, удовлетворяющих условиям задачи. Выбор конкретного решения, как "наилучшего", зависит от функции цели (показатель качества, критерий оптимальности, функция качества, критерий эффективности и т.д. - си­нонимы). Задача, допускающая лишь одно решение_, не требует оптимиза­ции.

В общем плане, существующие методы математического программирова­ния подразделяются на аналитические и численные

Аналитические методы включают в себя классические методы дифференциального и вариационного исчисления. Эти методы за­ключаются в определении экстремума функции f(х) путем нахож­дения тех значений х, которые обращают в нуль производные f(х) по х (здесь х n-мерный вектор). В случае поиска экстремума при наличии ограничений применяются такие методы, как метод множителей Лагранжа и метод ограниченных вариаций. Однако для решения больших задач чаще всего приме­нение аналитических методов невозможно.

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

Решение задач оптимизации численными методами представляет собой два этапа:

Первый этап - сбор информации об объекте;

Алгоритм сбора информации должен быть

1) прост;

2) должен обеспечивать процедуру решения наиболее полной информацией об объекте;

3) должен учитывать априорную информацию, полученную ранее, т.е. иметь возможность самообучаться.

На втором этапе строится процедура решения на базе проанали­зированной информации.

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

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

В настоящее время для решения оптимальных задач применяют в основном следующие методы:

1. Методы исследования функций классического анализа.

Методы, основанные на использовании неопределенных множителей Лагранжа.

Вариационное исчис­ление.

2. Методы исследования функций численного анализа.

2. 1. Линейное программирование.

2.2. Принцип максимума.

2.3. Нелинейное программирование.

2.4. Динамическое программирование.

В последнее время разработан и успешно применяется для реше­ния определенного класса задач также метод геометрического программи­рования.

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

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

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

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

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

1) Вид математического описания процесса;

2) Тип ограничений на переменные процесса;

3) Число переменных.

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

Таблица «Области применения методов оптимизации»

Примечания к таблице:

1. Эффективное применение метода.

2. Используется.

3. Возможно применение.

4. Используется как вспомогатель­ный метод.

5. Многостадийные процессы (размерность указывается для отдельной стадии).

6. Задачи с линейными критериями оптималь­ности и линейными ограничениями.

7. Используются множители Лагранжа.

8. Задачи с критериями и ограничениями в форме позиномов.

Виды описания процесса

Конечные уравнения

Дифференциальные уравнения

Тип ограничений на переменные

Нет

Равенства

Неравенства

Нет

Равенства

Неравенства

Число переменных n

≤3

>3

≤3

>3

≤3

>3

≤3

>3

≤3

>3

≤3

>3

Наименование метода

Методы классического анализа

Множители Лагранжа

-

-

-

-

-

-

-

-

Вариационное исчисление

-

-

-

-

-

-

2; 7

3; 7

-

-

Динамическое программирование

1; 5

3; 5

1;5;7

3;5;7

1;5

3;5

Принцип максимума

2;5

1;5

2;5

2;5

2;5

2;5

Линейное программирование

-

-

-

2;6

2;6

1;6

-

-

-

-

-

-

Методы нелинейного программирования

Геометрическое программирование

2;8

2;8

-

-

2;8

2;8

-

-

-

-

-

-

Дата добавления: 2014-01-04