Классификация оптимизационных задач

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

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

2) задача нелинейного программирования – хотя бы одна из функций нелинейна;

3) задача квадратичного программирования – целевая функция является квадратичной функцией, ограничения линейны;

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

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

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

Разделение задач оптимизации по методам нахождения решения

1. Динамическое программирование – основано на принципе последовательной оптимизации. Этот принцип требует расчисления оптимизируемого процесса на ряд шагов. Решение, принимаемое на каждом последующем шаге, должно быть оптимальным при условиях, определяемых решениями, принятыми на предшествующих шагах.

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

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

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

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