ЗНЛП – это задача вида

ƒ(x₁,x₂,…,x_n)→opt.

g(x₁,x₂,…,x_n)≤≥=b_i; i=1,n (1)

x_j≥0; j=1,n;

 

Если система ограничений содержит только уравнения и функции ƒ_i и g_i непрерывны вместе со своими частными производными, то задача является задачей на условный экстремум и решается методом множителей Лагранжа:

1. Рассматриваем дополнительную функцию Лагранжа, вводя набор дополнительных переменных λ₁, λ₂, … λ_m

F(λ_i,x_j)=ƒ(x₁, x₂, …, x_n)+ λ_i (b_i-g_i (x₁, x₂, …, x_n)).

2. Находим безусловные экстремумы функции F, которые являются решением задачи.

Приближенные методы решения ЗНЛП:

Используя градиентные методы, можно найти решение любой ЗНЛП.

 

Метод Франка-Вульфа:

 

Если ƒ(x₁, x₂, …, x_n)→max и является вогнутой функцией на выпуклом множестве Ω, т.е

При условиях ∑a_ijx_j≤b_i ; i=1;m; x_j≥0, то применяется следующий алгоритм:

1. Найти исходное допустимое решение задачи

2. Найти градиент функции ƒ

3. Построить функцию

; найти ее максимальное значение, т.е Z^(k)

4. По формуле ; - произвольно, или находится как наименьшее решение уравнения

5. Проверить необходимость перехода к последующему допустимому решению, приняв в качестве критерия оценки неравенство

пункт 2, где x⁽⁰⁾=х ^(к). В противном случае решение задачи найдено.

Метод штрафных функций:

ƒ(x₁, x₂, …, x_n)→max ƒ вогнутая на Ω Ω: g_i(x₁, x₂,…, x_n)≤b_i x_j≥0, где g_i - выпуклые функции.

Алгоритм метода:

1. Найти исходное допустимое решение задачи

2. Выбрать шаг вычислений

3. Найти и

4. По формуле

Определить координаты точки определяющей новое решение задачи.

Где α_i(x₁,x₂,…,x_n)=0, если b_i-g_i(x₁,…x_n)≥0 и α_i(x₁,x₂,…,x_n)=α_i,если b_i-g_i<0 и

α_i – весовые коэффициенты.

Начинают итерационный процесс при малых α_i, постепенно их увеличивая.

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

В случае необходимости переходят к этапу 2, в противоположном случае решение найдено.

6. Устанавливают значение весовых коэффициентов и переходят к этапу 4

Замечание: Произвольный выбор значений α_i приводит к значительным колебаниям удаленности определяемых точек от области допустимых решений. Этот недостаток устраняется при решении задачи методом Эрроу – Гурвица, согласно которому на очередном шаге числа α_i выбирают по формуле:

α_i ⁽⁰⁾ – произвольное положительное число.