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