Немає перевірених версій цієї сторінки; ймовірно, її ще не перевіряли на відповідність правилам проекту.

Опорний план — розв'язок системи лінійних обмежень в задачі лінійного програмування, який неможливо представити у вигляді лінійної комбінації будь-яких інших розв'язків.

Система обмежень задачі лінійного програмування в канонічній формі має вигляд

, (1)

де B = (b1, …, bm)T, Aj = (a1j, …, amj)T, (j = 1, …, n) — відомі вектори, T — знак транспонування, а X = (x1, …, xn) — вектор змінних. Розв'язок X* є опорним планом тоді і тільки тоді, коли множина векторів Aj, для яких xj* > 0, лінійно незалежна.

Кількість додатних компонент опорного плану не перевищує m. Якщо кількість цих компонент дорівнює m, опорний план називається невиродженим, а множина відповідних векторів Aj утворює базис. Множина Aj1, …, Ajm є базисом задачі лінійного програмування з обмеженнями (1) тоді і тільки тоді, коли система

має єдиний розв'язок, та xji ≥ 0, i = 1, …, m.

Різним опорним планам відповідають різні базиси. Зворотне твердження вірне лише у випадку невиродженості всіх опорних планів системи (1).

Джерела інформації

ред.

Див. також

ред.