Опорний план

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

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

${\displaystyle \sum _{j=1}^{n}A_{i}x_{i}=B;\quad x_{j}\geq 0,\;j=1,\dots ,n}$, (1)

де B = (b₁, …, b_m)^T, A_j = (a_1j, …, a_mj)^T, (j = 1, …, n) — відомі вектори, ^T — знак транспонування, а X = (x₁, …, x_n) — вектор змінних. Розв'язок X^* є опорним планом тоді і тільки тоді, коли множина векторів A_j, для яких x_j^* > 0, лінійно незалежна.

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

${\displaystyle \sum _{i=1}^{m}A_{j_{i}}x_{j_{i}}=B}$

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

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

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

• Енциклопедія кібернетики, т. 2, ст. 129.

Див. також

• Симплекс-метод
• Система лінійних рівнянь