Опорний план
Матеріал з Вікіпедії — вільної енциклопедії.
Опорний план — розв'язок системи лінійних обмежень в задачі лінійного програмування, який неможливо представити у вигляді лінійної комбінації будь яких інших розв'язків.
Система обмежень задачі лінійного програмування в канонічній формі має вигляд
, (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).
[ред.] Джерела інформації
- Енциклопедія кібернетики, т. 2, ст. 129.
[ред.] Дивіться також
- Симплекс-метод
- Система лінійних рівнянь
| Це незавершена стаття з математики. Ви можете допомогти проекту, виправивши або дописавши її. |


