PROFILPELAJAR.COM

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

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

\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_j₁, …, A_{j_m} є базисом задачі лінійного програмування з обмеженнями (1) тоді і тільки тоді, коли система