Задачи нелинейного программирования

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Брянский государственный университет

имени академика И.Г. Петровского»

Институт экономики и права

Финансово-экономический факультет

Кафедра финансов и статистики

 

Реферат

по дисциплине: «Системы поддержки принятия решения в банковском деле»

на тему: Задачи нелинейного программирования

 

 

Работу выполнила

студентка очного отделения

по направлению подготовки

«Информационные системы и технологии

(в банковских системах)»

курс 3 группа 8

Немяко Е.И.

Руководитель:

Климова Е.М

 

 

 

 

 

 

Брянск 2014 г. 

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

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

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

Задачи нелинейного программирования можно классифицировать в соответствии с видом функции F(x), функциями ограничений и размерностью вектора х (вектора решений).

Общих способов решения, аналогичных симплекс-методу линейного программирования, для нелинейного программирования не существует.  
В каждом конкретном случае способ выбирается в зависимости от вида функции F(x).  
Задачи нелинейного программирования на практике возникают довольно часто, когда, например, затраты растут не пропорционально количеству закупленных или произведённых товаров.

Многие задачи нелинейного программирования могут быть приближены к задачам линейного программирования, и найдено близкое к оптимальному решению. Встречаются задачи квадратичного программирования, когда функция есть F(x) полином 2-ой степени относительно переменных, а ограничения линейны. В ряде случаев может быть применён метод штрафных функций, сводящей задачу поиска экстремума при наличии ограничений к аналогичной задаче при отсутствии ограничений, которая обычно решается проще.

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

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

• выпуклое программирование,
• квадратичное программирование,
• целочисленное программирование,
• стохастическое программирование,
• динамическое программирование и др.

Задачи выпуклого программирования – это задачи, в которых определяется минимум выпуклой функции (или максимум вогнутой), заданной на выпуклом замкнутом множестве. Эти задачи среди задач нелинейного программирования наиболее изучены.

Среди задач выпуклого программирования более подробно изучены задачи квадратичного программирования. В этих задачах целевая функция – квадратична, а ограничения – линейны.

В задачах целочисленного программирования неизвестные параметры могут принимать только целочисленные значения.

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

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

 

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

 

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

По количеству локальных критериев в целевой функции методы нелинейного программирования делятся на:

• однокритериальные,
• многокритериальные.

По длине вектора методы делятся на:

• однопараметрические или одномерные (n=1),
• многопараметрические или многомерные (n>1).

По наличию ограничений методы нелинейного программирования делятся на:

• без ограничений (безусловная оптимизация),
• с ограничениями (условная оптимизация).

По типу информации, используемой в алгоритме поиска экстремума методы делятся на:

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

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

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

Методы решения задачи

 

Одним из методов, которые позволяют свести задачу нелинейного программирования к решению системы уравнений является метод неопределенных множителей Лагранжа.

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

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

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

Существуют несколько методов для решения невыпуклых задач. Один подход заключается в использовании специальных формулировок задач линейного программирования. Другой метод предусматривает использование методов ветвей и границ, где задача делится на подклассы, чтобы быть решенной с выпуклыми (задача минимизации) или линейными аппроксимациями, которые образуют нижнюю границу общей стоимости в пределах раздела. При следующих разделах в определенный момент будет получено фактическое решение, стоимость которого равна лучшей нижней границе, полученной для любого из приближенных решений. Это решение является оптимальным, хотя, возможно, не единственным. Алгоритм можно прекратить на ранней стадии, с уверенностью, что оптимальное решение находится в рамках допустимого отклонения от найденной лучшей точки; такие точки называются ? (Эпсилон)-оптимальными. Завершение у ? (Эпсилон)-оптимальных точек, как правило, необходимое для обеспечения конечности завершения. Это особенно полезно для больших, сложных задач и задач с неопределенными расходами или значениями, где неопределенность может быть определена из соответствующей оценки надежности.

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