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

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

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

Теорема 4.1.

Множина всіх планів задачі лінійного програмування опукла. Доведення. Необхідно довести, що коли Неможливо розібрати вираз (невідома помилка): X_1

та Неможливо розібрати вираз (невідома помилка):  X_2 
- плани задачі лінійного програмування (3.1)-(3.3), то їх опукла комбінація 

Неможливо розібрати вираз (невідома помилка): X = \lambda_1X_1 + \lambda_2X_2 , \lambda_1 \ge 0, \lambda_2 \ge 0, \lambda_1 + \lambda_2 = 1

також є планом задачі. Так як Неможливо розібрати вираз (невідома помилка): X_1

та Неможливо розібрати вираз (невідома помилка):  X_2 
та  - плани задачі, то виконуються такі співвідношення:

Неможливо розібрати вираз (невідома помилка): AX_1 = A_0, X_1 \ge 0 ; AX_2 = A_0, X_2 \ge 0

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

Неможливо розібрати вираз (невідома помилка): ~ 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

Отримали, що Х задовольняє систему обмежень задачі лінійного програмування (3.2), і оскільки Неможливо розібрати вираз (невідома помилка): X_1 \ge 0, X_2 \ge 0, \lambda_1 \ge 0 , \lambda_2 \ge 0 ,

то й Неможливо розібрати вираз (невідома помилка): X>0
, тобто задовольняють і умову (3.3). У такий спосіб доведено, що Х – план задачі лінійного програмування.

Теорема 4.2.

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

Теорема 4.3.

Якщо відомо, що система векторів Неможливо розібрати вираз (невідома помилка): ~ A_1,A_2 ... A_k (K \le n)

 у розкладі Неможливо розібрати вираз (невідома помилка): ~A_1X_1+A_2X_2 + ... + A_nX_n=A_0 , X\ge 0 
 лінійно незалежна і така, що 

Неможливо розібрати вираз (невідома помилка): ~ A_1X_1+A_2X_2 + ... + A_kX_k=A_0

де всі Неможливо розібрати вираз (невідома помилка): X_j \ge 0 , то точка Неможливо розібрати вираз (невідома помилка): X=(x_1,x_2,...,x_k,0,...,0)

 є кутовою точкою багатогранника розв’язків.

Доведення. Припустимо, що точка Х не є кутовою. Тоді вона може бути виражена опуклою лінійною комбінацією двох інших точок Неможливо розібрати вираз (невідома помилка): X_1

та Неможливо розібрати вираз (невідома помилка):  X_2 
багатогранника розв’язків, тобто:

Неможливо розібрати вираз (невідома помилка): X = \lambda_1X_1 + \Lambda_2X_2 , \lambda_1 \ge 0, \lambda_2 \ge 0, \lambda_1 + \lambda_2 = 1

Компоненти векторів Неможливо розібрати вираз (невідома помилка): X_1

та Неможливо розібрати вираз (невідома помилка):  X_2 
 , значення   Неможливо розібрати вираз (невідома помилка): \lambda_1 
та Неможливо розібрати вираз (невідома помилка):  \lambda_2 
  невід’ємні і останні n-k компонентів вектора Х дорівнюють нулю, тому відповідні n-k компонент векторів  Неможливо розібрати вираз (невідома помилка):  X_1 
та Неможливо розібрати вираз (невідома помилка):  X_2 
також мають дорівнювати нулю, тобто

Неможливо розібрати вираз (невідома помилка): ~ X_1 = (x_1^1,x_2^1,...,x_k^1,0,...,0) ,
Неможливо розібрати вираз (невідома помилка): ~ X_2 = (x_1^2,x_2^2,...,x_k^2,0,...,0) ,
. Оскільки Неможливо розібрати вираз (невідома помилка): X_1

та Неможливо розібрати вираз (невідома помилка):  X_2 
- плани, то

Неможливо розібрати вираз (невідома помилка): ~ A_1X_1^1+A_2X_2^1 + ... + A_kX_k^1=A_0

Неможливо розібрати вираз (невідома помилка): ~ A_1X_1^1+A_2X_2^1 + ... + A_kX_k^1=A_0

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

Неможливо розібрати вираз (невідома помилка): 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

За припущенням вектори Неможливо розібрати вираз (невідома помилка): A_1 , A_2 , ... A_k

лінійно незалежні, тому останнє співвідношення виконується, якщо 

Неможливо розібрати вираз (невідома помилка): 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

Звідки: Неможливо розібрати вираз (невідома помилка): X_1^1 = X_1^2; X_2^1 = X_2^2;...; X_k^1 = X_k^2;

Отже, Х неможливо подати як опуклу лінійну комбінацію двох інших точок багатокутника розв’язків. Значить, Х – кутова точка.

Теорема 4.4.

  Якщо Неможливо розібрати вираз (невідома помилка):  X=(x_1,x_2,...,x_k) 
- кутова точка багатогранника розв’язків, то вектори в розкладі 

Неможливо розібрати вираз (невідома помилка): ~A_1X_1+A_2X_2 + ... + A_nX_n=A_0 , X\ge 0 , що відповідають додатним Неможливо розібрати вираз (невідома помилка): X_j

, є лінійно незалежними.

Наслідки:

1. Оскільки вектори Неможливо розібрати вираз (невідома помилка): A_1 , A_2 , ... A_k

мають розмірність m, то кутова точка багатокутника розв’язків має не більше, ніж m додатних компонентів  Неможливо розібрати вираз (невідома помилка):  X_j > 0 (i=\overline{1,m}) 

1. Кожній кутовій точці багатокутника розв’язків відповідає лінійно незалежних векторів системи Неможливо розібрати вираз (невідома помилка): A_1 , A_2 , ... A_k

1. наведених властивостей можна зробити наступні висновки: якщо функціонал задачі лінійного програмування обмежений на багатограннику розв’язків, то:
   1. існує така кутова точка багатогранника розв’язків, в якій лінійний функціонал досягає свого оптимального значення;
   2. кожний опорний план відповідає кутовій точці багатогранника розв’язків.

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