Опорний план

Матеріал з Вікіпедії — вільної енциклопедії.

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

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

\sum_{j=1}^n A_i x_i = B;\quad x_j \geq 0,\; j = 1, \dots, n, (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) тоді і тільки тоді, коли система

\sum_{i=1}^m A_{j_i}x_{j_i} = B

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

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


[ред.] Джерела інформації

[ред.] Дивіться також


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.