3. Основні теореми та властивості задачі лп.

Запишимо задачу ЛП в векторній формі:

F(x)=(c,x) →max (7)

x₁P₁ + x₂P₂ + x₃P₃ +…… + x_nP_n= P₀ (8)

X≥0 (9)

P₁= (a_11,a₂₁,а₃₁…….a_m1) , P₂= (a_12,a₂₂,а₃₂…….a_m2) , ……….. P_n= (a_1n,a_2n,а_3n…….a_nm) ,

P₀=(b₁ ,b₂, b_3……. b_m) – m-мерні вектор столбці.

Означення 4. План Х=(х₁,х₂,х₃…….х_n) називається опорним планом задачі ЛП, якщо система векторів Р_j ,які відповідають додатним компонентам x_j плану Х, утворюють лінійно незалежну систему.

Так як вектори Р_j належать m-мірному простору, то з означення опорного плану витікає, що число його додатних компонент не може буди більш ніж m.

Означення 5. Нехай Х₁, Х₂, Х₃, ……, Х_n – вільні крапки евклідова простору R_n. Опуклою лінійною комбінацією цих крапок є сума λ₁Х₁+ λ₂Х₂+ λ₃Х₃+...... + λ_nХ_n, де λ_i≥0 та ∑ λ_i=1.

Означення 6. Множина U називається опуклою, якщо для будь яких n крапок Х₁, Х₂ , …Xn є U, до U належить будь яка опукла комбінація цих крапок, тобто [ λ₁Х₁+ λ₂Х₂+ λ₃Х₃+...... + λ_nХ_n] є U, де λ_i≥0 та ∑ λ_i=1.

Означення 7. Крапка Х опуклої множини є кутовою, якщо ця крапка не може бути означена в вигляді опуклої лінійної комбінації яких не будь n крапок даної множини.

Теорема 1. Опуклий n – мірний многогранік є лінійною комбінацією своїх кутових крапок.

Теорема 2. Множина планів задачі ЛП є опуклою множиною, якщо вона не поржня.

Означення 8. Не поржня множина планів задачі ЛП називається многогранником розв’язків , а будь яка кутова крапка многогранника розв’язків – вершиною.

Теорема 3. Якщо задача ЛП має оптимальний план, то максимальнє значення цільова функція задачі приймає в одній із вершин многогранника розв’язків.

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

Теорема 4. (Критерій кутової крапки многогранника розв’язків). Для того щоб крапка Х=(х₁,х₂,х₃…..х_к, ....... х_n), многогранника розв’язків була кутовою, небхіно і достатньо, щоб вектори Р_j, які відповідають додатним компонентам х_j, утворювали лінійно незалежну систему.

Висновки:

1. Не поржня множина задачі ЛП – опуклий многокутник.

2. Кожна вершина многокутника - опорний план.

3. В одній із вершині многокутника розв’язків цільова функція приймає максимальне значення.

4. Якщо, максимальне значення цільова функція приймає більш ніж в одній вершині – тоді таке ж значення цільова функція приймає і в лінійній комбінації цих вершин.