Математические задачи исследования операций, которые основаны на нелинейном программировании

реферат

Введение

  • Реферат посвящен решению задач исследования операций с помощью нелинейного программирования.
  • Методы нелинейного программирования применяются для решения задач с нелинейными функциями переменных.
  • Как известно, в общем случае задача математического программирования записывается в виде:
  • (1.1)
  • Если хотя бы одна функция в модели (1.1) нелинейная, имеем задачу нелинейного программирования (НП). Размерность задачи характеризуется размерностью вектора переменных n и числом условий m1+m2. Однако сложность задачи определяется не столько размерностью, сколько свойствами функций цели и ограничений.
  • Разнообразие задач НП очень велико. Универсальных методов решения таких задач не существует. Имеется весьма ограниченное число точных методов и намного больше приближенных.

    Наиболее развиты методы решения задач выпуклого программирования. К этому классу относятся задачи НП с выпуклым допустимым множеством и выпуклой целевой функцией при минимизации или вогнутой при максимизации. Допустимое множество выпуклое, если все функции линейные и выпуклы при неравенстве или вогнуты при . Например, условие x12+x22 r2 порождает выпуклое множество, пересечение которого с прямой x1+x2=0 дает тоже выпуклое множество. Очевидно, что задачи НП относятся к этому классу. Главная особенность задач выпуклого программирования в том, что они унимодальные, то есть любой их локальный оптимум является глобальным. Для ряда задач выпуклого программирования с дифференцируемыми функциями разработаны точные методы. Наибольшие сложности возникают при решении многоэкстремальных задач, которые по определению не относятся к классу выпуклых.

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

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

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

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

    Делись добром ;)