(Álgebra básica do método simplex para resolução de problemas de otimização linear) Considere um sistema linear
, onde
é matriz
com
. Escrevemos
, onde
é a matriz quadrada de ordem
formada pelas
primeiras colunas de
, e
a matriz das
últimas colunas de
. Tomemos
, onde
é formado pelas
primeiras entradas de
e
formado pelas
últimas entradas de
. O sistema
pode ser então escrito como
Passo 1
O enunciado nos dá o sistema linear
onde
é
com
. Partimos a matriz em duas partes
onde
é uma submatriz quadrada
(colunas básicas) e
é
(colunas não-básicas). Também dividimos o vetor
em
com
e
. O objetivo é reescrever o sistema em função de
e caracterizar a solução básica.
Passo 2
Reescrevemos
Supondo que
é invertível, isolamos
:
Isto nos dá a forma paramétrica de todas as soluções factíveis do sistema.
Passo 3
A solução básica associada à base
é obtida impondo
. Logo
Esse
é o ponto básico. Se além disso
, é uma solução básica viável.