Властивості розв’язків задачі лінійного програмування
Розглянемо канонічну задачу у векторній формі
; 
, 
, 
. 
де 
; 
; ... ; 
, 
.
Запис означає, що 
є лінійною комбінацією векторів 
.
Означення 1 План 
задачі , називається опорним, якщо система векторів-стовпчиків 
, які відповідають додатним координатам 
, лінійно незалежна.
Оскільки вектори мають по 
координат, то лінійно незалежними можуть бути не більше координат. Це означає, що в опорному плані є не більше m строго додатних координат.
Базисні розв’язки системи з невід’ємними координатами є опорними планами.
Приклад 4.1 Перевірити, чи план 
є опорним, якщо система обмежень така
, 
, 
.
Додатним координатам плану 
і 
відповідають вектори
, 
.
Перевіримо, чи вони лінійно незалежні. Для цього знайдемо ранг матриці
,
обчислимо визначник 
.
Отже, вектори 
і 
лінійно незалежні, а план 
- опорний.
Означення 2. Опорний план називається невиродженим, якщо число його додатних координат рівне m, і виродженим,якщо число додатних координат менше m.
У прикладі план невироджений.
Нехай ранг матриці 
дорівнює .
Означення 3. Базисом опорного плану називається система з лінійно незалежних векторів-стовпчиків матриці 
, яка містить всі вектори, що відповідають додатним координатам опорного плану.
У прикладі вектори і утворюють базис опорного плану .
Таким чином, базис невиродженого опорного плану визначається однозначно, а у виродженого їх може бути декілька.
Запишемо задачу - у вигляді
; 
; 
; 
і розглянемо основні властивості розв’язків цієї задачі.
Теорема 1. Множина всіх розв’язків системи 
опукла, якщо вона непорожня.
Доведемо, що якщо 
, 
– розв’язки задачі - , то їх лінійна комбінація опукла: 
,
, 
, 
.
Оскільки , – плани, то 
, 
, 
, 
. Тоді
.
Отже, задовольняє систему .
Оскільки, , , , , то 
, тобто виконується .
Опуклу множину планів задачі лінійного програмування позначимо 
. Можна довести, що буде опуклим многокутником (обмеженим чи необмеженим).
Теорема 2. Якщо цільова функція 
має максимум на опуклому многограннику допустимих розв’язків , то він досягається у вершині цього многогранника.
Нехай многогранник обмежений і має скінченне число кутових точок 
. Точку, в якій досягає максимуму, позначимо 
.
Якщо серед вершин 
, 
, є хоч одна, в якій досягає 
, то теорема доведена.
Нехай не є кутовою точкою. Тоді 
, 
.
Якщо – не кутова, то вона є опуклою лінійною комбінацією кутових, тобто
, 
, 
.
Тоді
.
Отже, 
– суперечність. Тому – одна з кутових точок .
Отже, екстремум цільової функції досягається в вершині многогранника розв’язків, але не обов’язково у одній точці.
Теорема 3. Якщо цільова функція має максимум більше, ніж в одній вершині, многогранника , то цей максимум досягається у будь-якій точці, яка є опуклою лінійною комбінацією цих вершин.
Нехай цільова функція 
досягає максимуму у вершинах 
многогранника , тобто 
, 
. Тоді для довільної прямої лінійна комбінація цих вершин
, , 
Маємо: 
Отже, для знаходження 
досить дослідити всі вершини .
Теорема 4. Вектор є опорним планом задачі - тоді і лише тоді, коли є вершиною многогранника розв’язків .
З теореми випливає, що алгебраїчне поняття опорного плану еквівалентне до геометричного поняття вершини многогранника розв’язків.
Наслідок 1. Кожна вершина многогранника має не більше ніж додатних координат.
За означенням опорного плану, є 
додатних координат.
Наслідок 2. Кожній вершині многогранника відповідає 
лінійно-незалежних розв’язків-стовпців 
, .
Це означення опорного плану.
Висновок. Якщо цільова функція обмежена на , то існує кутова точка (опорний план), в якій досягається . Тому для розв’язування задач лінійного програмування треба дослідити тільки вершини многогранника (опорні плани) задачі лінійного програмування.