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

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

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

 

 

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

 

Группа задач	Целевая функция	Ограничения	Методы решения
1	Аналитически определена	Область допустимых значений, заданная ограниченными интервалами изменения переменных	Метод исключения интервалов, градиентный метод и т.д.
	Статистически определена		Стохастические методы поиска экстремума
	Не определена		Статистические методы планирования экстремальных экспериментов
2	Линейная	Линейные уравнения и неравенства	Методы линейного программирования
3	Линейная	Линейные уравнения и неравенства, дополненные условиями целочисленности	Методы целочисленного программирования
4	Нелинейная дифференцируемая на всем интервале изменения переменных	Нелинейные уравнения, дифференцируемые на всем интервале изменения переменных	Метод неопределенных множителей Лагранжа
5	Квадратичная	Линейные уравнения и неравенства	Методы квадратичного программирования
6	Сепарабельная (сумма функций одной переменной)	Сепарабельные функции в ограничениях - равенствах или неравенствах	Кусочно-линейная аппроксимация
7	Нелинейная	Линейные или нелинейные	Градиентные методы
8	Сепарабельная	Сепарабельные одно- или двусторонние ограничения, целочисленные или непрерывные переменные	Методы динамического программирования

 

Приведенная группировка задач и методов [11] весьма условна, так как многие задачи могут быть отнесены к нескольким группам и решаться разными методами.

Принято выделять три основных вида общей задачи мате­матического программирования: каноническая задача математи­ческого программирования, задача нелинейного программирования и задача линейного программирования.

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

В канонической задаче математического программирования все ограничения представляют собой равенства

.                       (1.2)

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

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

.

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

,                                             (1.3)

и ограничений в виде неравенств

                     (1.4)

Задача нелинейного программирования заключается в нахож­дении неотрицательных значений переменных, удовлетворяющих условиям (1.3), (1.4) и максимизирующих целевую функцию (1.1):

.

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

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

В задаче линейного программирования целевая функция является ли­нейной формой

,                      (1.5)

где с - заданный вектор-строка , и имеются ограничения двух типов: ограничения в виде неравенств

                       (1.6)

и условия неотрицательности

.                                            (1.7)

В векторной форме система ограничений имеет вид

где А - заданная матрица размерности m×n

.

Таким образом, задача линейного программирования заключается в нахождении неотрицательных значений переменных, удовлетворяющих ограничениям (1.6), (1.7) и максимизирующих заданную линейную форму(1.5):

.

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