logo search
Опорний конспект ОММ 4 Ф

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

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

Означення 6. Квадратичною формою відносно змінних x1, x2,….. xn називається функція Z, яка має вигляд Z=∑∑сjixixj.

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

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

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

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

Z=∑∑сjixixj.+ ∑djxj→max/ min (9)

за умов

∑aijxj ≤bi, (i=1,2…..m) ,

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

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

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

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

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

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

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