КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Сравнительная характеристика методов решения задач оптимизации
Классификация методов математического программирования. Матрицы Матрицы Определители Понятие «определитель» возникло в связи с задачей решения систем линейных уравнений. Возьмем какое-нибудь поле К и рассмотрим простейшие системы уравнений 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. Задачи с критериями и ограничениями в форме позиномов.
Дата добавления: 2014-01-04; Просмотров: 1352; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |