Численные методы математического программирования 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Численные методы математического программирования



 

Численные методы математического программирования – раздел вычислительной математики, связанный с отысканием решения задач математического программирования в тех случаях, когда затруднено получение строго математического решения [1]. Численные методы оптимизации, численный вычислительный эксперимент считаются важным разделом системного анализа.

Численные методы представляют собой последовательность однотипных шагов, итераций.

Выделяют конечные и бесконечные численные методы [1].

Конечные методы позволяют получать решение за конечное (но обычно заранее неизвестное) число шагов. К ним относят:

симплекс-метод (с полной симплексной таблицей, с использованием обратной матрицы, с мультипликативным представлением обратной матрицы);

двойственный симплекс-метод;

метод последовательного сокращения невязок (комбинация обычного и двойственного симплекс-метода);

метод наискорейшего спуска;

• метод сопряженных градиентов для минимизации квадратичной функции;

• методы условной минимизации, основанные на теореме Куна-Такера.

Область применения конечных методов ограничена линейным программированием и квадратичным программированием.

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

К этой группе методов относят:

• метод Брауна-Робинсона [1], основанный на связи между парой задач линейного программирования (исходной и двойственной) и матричной игрой, т.е. на применении при решении задач математического программирования методов теории игр;

• метод штрафных функций или метод штрафов [1], базирующийся на использовании функций штрафов.

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

При этом выделяют 4 вида итераций.

1. Методы возможных направлений.

Строится последовательность хk, к = 0,1,..., так, что каждое хk удовлетворяет всем ограничениям задачи. Вблизи очередного приближения хk минимизируемая функция и ограничения (существенные для хk) аппроксимируются более простыми (как правило, линеными или квадратичными). Решая получающуюся вспомогательную задачу линейного или квадратичного программирования, находят возможное (т.е. не выходящее за пределы области допустимых решений) направление, являющееся одновременно и направлением убывания функции. Сдвиг по этому направлению приводит к новой точке хk+1.

Примерами могут служить симплексный метод в линейном программировании и метод проекции градиента и условного градиента, метод возможных направлений Зойтендейка в нелинейном программировании.

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

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

К этой группе относят двойственный симплекс-метод в линейном программировании, метод отсечения в выпуклом программировании), при этом точка хk отсекается путем добавления нового линейного ограничения.

3. Итерационный процесс ведется не только по исходным, но и по двойственным переменным (множителям Лагранжа, оптимальным оценкам).

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

К этой группе относится градиентный метод Эрроу-Гурвица-Удзавы.

4. Методы, основанные на учете ограничений с помощью штрафов.

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

Задачи могут решаться с помощью градиентного метода, метода сопряженных градиентов, метода Ньютона и т. д.

К численным методам относят также методы решения задач специального вида: транспортные (Транспортная задача), блочные (Блочное программирование).

В современных условиях при применении ЭВМ число методов расширяется. В частности, разрабатываются методы, основанные на использовании кусочно-линейной аппроксимации [5,6 и др.], комбинаторных алгоритмов [2], разработке непрерывных вариантов дискретных методов, строится непрерывная траектория х(t), задаваемая дифференциальными уравнениями.


Лекция 4.



Поделиться:


Последнее изменение этой страницы: 2017-02-07; просмотров: 236; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.210.126.232 (0.224 с.)