Перегляд вихідного коду сторінки Основні властивості розв’язків задачі лінійного програмування

== Основні властивості розв’язків задачі лінійного програмування. ==
 

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

===Теорема 4.1.=== 
Множина всіх планів задачі лінійного програмування опукла.
Доведення. Необхідно довести, що коли <math> X_1 </math> та <math> X_2 </math> - плани задачі лінійного програмування (3.1)-(3.3), то їх опукла комбінація <br>
<math> X = \lambda_1X_1 + \lambda_2X_2 , \lambda_1 \ge 0, \lambda_2 \ge 0, \lambda_1 + \lambda_2 = 1 </math>  <br>
також є планом задачі. Так як  <math> X_1 </math> та <math> X_2 </math> та  - плани задачі, то виконуються такі співвідношення:

<math> AX_1 = A_0, X_1 \ge 0 ; AX_2 = A_0, X_2 \ge 0  </math> 

Якщо підставити в систему обмежень значення Х, то отримаємо: 

<math> ~ AX = A(\lambda_1X_1 + \lambda_2X_2) = \lambda_1X_1 + \lambda_2X_2 = \lambda_1AX_1 + \lambda_2AX_2 = \lambda_1A_0 + \lambda_2A_0 = (\lambda_1 + \lambda_2)A_0 = A_0  </math>

Отримали, що Х  задовольняє систему обмежень задачі лінійного програмування (3.2), і оскільки <math> X_1 \ge 0, X_2 \ge 0, \lambda_1 \ge 0 , \lambda_2 \ge 0 , </math> то й <math>X>0</math> , тобто задовольняють і умову (3.3). У такий спосіб доведено, що Х – план задачі лінійного програмування.

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


===Теорема 4.3.=== 
Якщо відомо, що система векторів <math>~ A_1,A_2 ... A_k (K \le n) </math>  у розкладі <math>~A_1X_1+A_2X_2 + ... + A_nX_n=A_0 , X\ge 0 </math>  лінійно незалежна і така, що 
<math>~ A_1X_1+A_2X_2 + ... + A_kX_k=A_0 </math>

де всі <math>X_j \ge 0</math>, то точка <math> X=(x_1,x_2,...,x_k,0,...,0) </math>  є кутовою точкою багатогранника розв’язків.
Доведення. Припустимо, що точка Х не є кутовою. Тоді вона може бути виражена опуклою лінійною комбінацією двох інших точок <math> X_1 </math> та <math> X_2 </math> багатогранника розв’язків, тобто:<br>

<math> X = \lambda_1X_1 + \Lambda_2X_2 , \lambda_1 \ge 0, \lambda_2 \ge 0, \lambda_1 + \lambda_2 = 1 </math> <br>

Компоненти векторів  <math> X_1 </math> та <math> X_2 </math>  , значення   <math>\lambda_1 </math> та <math> \lambda_2 </math>   невід’ємні і останні n-k компонентів вектора Х дорівнюють нулю, тому відповідні n-k компонент векторів  <math> X_1 </math> та <math> X_2 </math> також мають дорівнювати нулю, тобто
<math>~ X_1 = (x_1^1,x_2^1,...,x_k^1,0,...,0) </math>, <br>
<math>~ X_2 = (x_1^2,x_2^2,...,x_k^2,0,...,0) </math>, <br>
.
Оскільки <math> X_1 </math> та <math> X_2 </math> - плани, то
<math>~ A_1X_1^1+A_2X_2^1 + ... + A_kX_k^1=A_0 </math> <br>
<math>~ A_1X_1^1+A_2X_2^1 + ... + A_kX_k^1=A_0 </math> <br>

Віднімаючи від першого рівняння друге, отримаємо:

<math> A_1(X_1^1+X_1^2) + A_2(X_2^1+X_2^2) + ... + A_k(X_k^1+X_k^2) = 0 </math>

За припущенням вектори <math> A_1 , A_2 , ... A_k </math> лінійно незалежні, тому останнє співвідношення виконується, якщо 

<math> A_1(X_1^1+X_1^2) =0; A_2(X_2^1+X_2^2) =0; ... ;A_k(X_k^1+X_k^2) = 0 </math> 

Звідки: 
<math> X_1^1 = X_1^2; X_2^1 = X_2^2;...; X_k^1 = X_k^2;</math> <br>
Отже, Х неможливо подати як опуклу лінійну комбінацію двох інших точок багатокутника розв’язків. Значить, Х – кутова точка.

=== Теорема 4.4. ===
   Якщо <math> X=(x_1,x_2,...,x_k) </math> - кутова точка багатогранника розв’язків, то вектори в розкладі 
<math>~A_1X_1+A_2X_2 + ... + A_nX_n=A_0 , X\ge 0 </math>, що відповідають додатним <math> X_j </math> , є лінійно незалежними.

'''Наслідки:'''
# Оскільки вектори  <math> A_1 , A_2 , ... A_k </math> мають розмірність m, то кутова точка багатокутника розв’язків має не більше, ніж m додатних компонентів  <math> X_j > 0 (i=\overline{1,m}) </math> 
# Кожній кутовій точці багатокутника розв’язків відповідає  лінійно незалежних векторів системи <math> A_1 , A_2 , ... A_k </math> 
# наведених властивостей можна зробити наступні висновки: якщо функціонал задачі лінійного програмування обмежений на багатограннику розв’язків, то:
## існує така кутова точка багатогранника розв’язків, в якій лінійний функціонал досягає свого оптимального значення;
## кожний опорний план відповідає кутовій точці багатогранника розв’язків.

   Тому для розв’язання задачі лінійного програмування необхідно досліджувати лише кутові точки багатогранника (опорні плани), не включаючи до розгляду внутрішні точки множини допустимих планів.