Задачі опуклого програмування.

Розглянемо задачу квадратичного програмування, яка є окремим випадком задач опуклого програмування.

Означення 6. Квадратичною формою відносно змінних x₁, x₂,….. x_n називається функція Z, яка має вигляд Z=∑∑с_jix_ix_j.

Означення 7. Квадратична форма Z називається додатньо (від’ємно) – визначеною, якщо Z(Х)>0 ( Z(Х)<0) для всіх значень змінних Х, окрім крапки Х=(0,0,……0).

Означення 8. Квадратична форма Z називається додатньо (від’ємно) – напіввизначеною, якщо Z(Х) ≥0 ( Z(Х) ≤0) для будь якого набору значень змінних Х =(x₁, x₂,….. x_n) і, крім того, існує такий набір змінних Х^*, де не всі змінні одночасно рівні нулю, що Z(Х) =0.

Теорема 5. Квадратична форма є опуклою функцією, якщо вона додатньо-напіввизначена.

Постановка задачі квадратичного програмування має вигляд:

Z=∑∑с_jix_ix_j.+ ∑d_jx_j→max/ min (9)

за умов

∑a_ijx_j ≤b_i, (i=1,2…..m) ,

x_j ≥0 (j=1,2…..n) ,

де ∑∑с_jix_ix_j - від’ємно (додатньо) – напіввизначена квадратична форма.

Алгоритм знаходження розв’язку задачі квадратичного програмування.

1. Складаємо функцію Лагранжа.

2. Записуємо необхідні і достатні умови існування сідловок точки для функції Лагранжа.

3. Використовуючи метод штучного базису, встановлюємо відсутність сідловок крапки для функції Лагранжа, або знаходимо ії координати.

4. Записуємо оптимальний план початкової задачі й обчислюємо значення цільової функції.