Виды задач оптимизации

В общем случае задача оптимизации может быть записана следующим образом:

Система (1) представляет собой общий случай математической постановки задачи оптимизации. Она включает целевую функцию Е = f (x_j); ограничения g_i (x_j) <= b_i; граничные условия d_i<= x_j <= D_{j .} Суть такой постановки задачи заключается в следующем: необходимо определить такие значения x_{j ,} которые, находясь в граничных условиях d_j<= x_j <= D_j, удовлетворяли бы ограничениям g_i (x_j) <= b_i и при этом придавали бы целевой функции Е = f (x_j) искомое оптимальное значение.

Функция f (x) имеет максимум в точке x = a, если, в достаточной близости от этой точки всем значениям x (как большим, так и меньшим a) соответствуют значения f (x) меньшие, чем f (a). Функция f (x) имеет минимум в точке x = a, если в достаточной близости от этой точки всем значениям x соответствуют значения f (x) большие, чем f (a).

Максимум и минимум объединяются понятием “экстремум”. (Латинское слово “экстремум” означает “крайнее”). Экстремум не может быть на границе рассматриваемого интервала. В задачах оптимизации нас интересует наибольшее (наименьшее) значение целевой функции, включая значения целевой функции на границах d_j<= x_j <= D_j. Наибольшее (наименьшее) значение целевой функции, включая ее значения на границах интервала [ d_jD_j ], называют оптимальным значением или оптимумом.

Если при нахождении экстремума накладываются дополнительные условия – ограничения на зависимости между переменными – то экстремум называется условным. Поскольку оптимум, как правило, определяется при наложении ряда дополнительных условий – ограничений, термин “условный оптимум” обычно не применяется. Задача (1) представляет собой задачу нахождения оптимума.

В каждом конкретном случае система (1) определяется видом переменных x_j и зависимостей f (x_j) и g_i (x_j). Различные виды переменных и зависимостей между ними требуют различных методов решения задачи оптимизации. В зависимости от классов математических описаний задач элементы системы (1) могут быть различными (рис. 1).

1. Зависимости между переменными в (1) входят в

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

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

Задачи оптимизации, содержащие линейные алгебраические зависимости в целевой функции и ограничениях, являются задачами ЛП. Для задачи ЛП система (1) будет иметь вид (2):

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

На рис. 2 дана графически задача НЛП на плоскости. Из рисунка видно, что даже в том случае, когда только одно ограничение будет нелинейным (рис. 2, а), оптимальным решением задачи оптимизации будут координаты не вершины, а какой-то произвольной точки. Аналогичное положение будет и в том случае, когда все ограничения линейны, а нелинейна только целевая функция (рис. 2, б). Такое положение существенно усложняет решение задач НЛП, так как метод перебора вершин, применяемый для задач ЛП, в данном случае оказывается непригодным.

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

Дискретные переменные, в свою очередь могут быть целочисленными, заданными и булевыми. Целочисленными переменными называются также переменные, которые могут принимать только целые значения. В ряде случаев переменные могут принимать лишь определенные заданные значения. Например, диаметр трубы не может быть произвольным, он должен соответствовать ГОСТу и быть равным одному из заданных размеров: 100, 150, 200, 250 мм и т.д.

Важным видом дискретных переменных являются булевые переменные. Булевые переменные могут принимать только два значения: 0 или 1. Если принимать, что 1 соответствует «да», а 0 – «нет», то с помощью булевых переменных можно решать логические, комбинационные и ряд других специфических задач.

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

Решение задач ЦП на плоскости приведено на рис. 3. Оптимальное решение в данном случае будет не в вершине ОДР (в точке А), а в узле сетки, имеющем целые значения переменных. При этом в случае, например, максимизации целевой функции её целочисленное значение будет меньше непрерывного. Следовательно, требование целочисленности, как и любое дополнительное требование, ухудшает значение целевой функции.

Результат решения задачи оптимизации, т.е. значения величин в оптимальном решении, является функцией заданных величин, входящих в модель, например, для задач ЛП функцией c_j, a_ij, b_i. Если эти величины являются детерминированными, то и величины x_j, как функции детерминированных величин, будут также детерминированными. Если же хотя бы одна из заданных величин будет случайной, то величины x_j, как функции случайных величин, будут также случайными величинами.

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

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