Опорний план

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

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

$\sum _{j=1}^n{A}_i{x}_i=B;x_j\ge 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) тоді і тільки тоді, коли система

$\sum _{i=1}^m{A}_{j_i}{x}_{j_i}=B$

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

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

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

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

Див. також

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