Найти max/min целевой функции f(x1,x2,…,xn) при наличии ограничений в виде

· неравенств g_i(x₁,x₂,…,x_n)³0

· равенств p_i(x₁,x₂,…,x_n)=0

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

1. Если целевая функция линейная и ограничения тоже линейные, то такая задача называется задачей линейного программирования. Задачи ЛП изучены хорошо, поэтому существует метод линеаризации – преобразования задач нелинейных к линейному виду.

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

В настоящее время продолжает развиваться теория кубического программирования. Она еще до конца не разработана.

3. Если ограничения на целевую функцию отсутствует или имеют простой вид ± x_i ³ a (ограничения только на переменную), то такая задача называется задачей безусловной оптимизации.

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

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

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

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

(ограничения в виде равенств) (ограничения в виде неравенств)

Совокупность х_i называется вектором неизвестных. Решением задачи тогда будет значение этого вектора неизвестных, при котором функция f обладает максимумом или минимумом. Коэффициенты c_i также образует вектор, который называется вектором ресурсов. Элементы b_i образуют вектор с названием вектор запасов. Для удобства решения принято приводить задачу от общей постановки к специальному стандартному виду.

Требования к стандартному виду задачи ЛП:

1) Параметры х_i должны быть больше или равны нулю (х_i³0). Если есть такое ограничение, которое допускает отрицательное значение х_i, то делают замену переменных так, чтобы новое х_i не было отрицательным.

2) Ограничения в виде неравенств преобразуются в ограничения в виде равенств.

3) Элементы, стоящие справа должны быть неотрицательными в равенствах, то есть b_i³0.

Дата добавления: 2015-07-11