Задачи поиска минимума функций при наличии ограничений. Линейное и нелинейное програмирование

Задача эта называется задачей математического программирования.

Пусть - некоторая функция.

,

Пусть . Задача поиска точки

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

Задачи без ограничений: .

В задачах математического программирования область X задается в виде ограничений двух видов: неравенств и равенств.

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

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

a_j1x₁ + … + a_jnx_n > b_j, j = 1, …, m₁

a_j1x₁ + … + a_jnx_n = b_j, j = m₁ + 1, …, m₁

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

2 класс. Выпуклое программирование.

3 класс: внутри второго - квадратичное программирование.

2 класс, - выпуклая, в X, а функция, задающая ограничения, вогнутая функция

вогнутые в Rⁿ.

Из вогнутости функции q_j следует, что множество X, заданное неравенством q_j ≥ 0, j = 1, …, m является выпуклым. Задача выпуклого программирования это задача поиска выпуклой функции на выпуклом множестве.

3 класс - квадратичная функция

=

квадратичную часть можно в векторной форме записать:

а ограничения линейные:

a_j1x₁ + … + a_jnx_n > b_j, j = 1, …, m₁

a_j1x₁ + … + a_jnx_n = b_j, j = m₁ + 1, …, m₁

Задача линейного программирования.

Каноническая запись задачи

= С₀ + С₁х₁ + … + С_nх_n.

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

х_i ≥ 0, i = 1, …, n.

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

a_j1x₁ + … + a_jnx_n > b_j;

x_n+1 < 0;

a_j1x₁ + … + a_jnx_n – x_n+1 > b_j;

x_n+1 ≥ 0.

Первое отражение заменяется вторым с двумя членами: один в виде равенства, другой в виде неравенства.

Геометрическую интерпретацию удобнее давать в виде нера­венств.

Задачу с числом переменных m < n и числом ограничений меньших, чем число ограничений, можно записать как задачу с меньшим числом: переменных m - n и таким же числом m ограничений типа неравенств.

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

= С₀ + С₁х₁ + … + С_nх_n

ограничения

n= 2.

Ограничения образуют выпуклый многоугольник в пространстве пере­менных x₁, …, x_n:

В пространстве m - n свободных переменных - выпуклый много­гранник в канонической форме записи.

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

Алгоритм решения задач линейного программирования основан на так называемом симплекс-методе. Его сущность состоит в направ­ленном переборе вершин многогранника допустимых решений, в процес­се которого значение уменьшается.

Машинный метод решения задач основан на постановке задачи в канонической форме.

ЛЕКЦИЯ 5

ВЫБОР ОПТИМАЛЬНЫХ ВАРИАНТОВ РЕШЕНИЯ ТЕХНИЧЕСКИХ ЗАДАЧ