(Álgebra básica do método simplex para resolução de problemas de otimização linear) Considere um sistema linear A x=b, onde A é matriz m times n com m<n. Escrevemos A=[llB & N], onde B é a matriz quadrada de ordem n formada pelas n primeiras colunas de A, e N a matriz das n-m últimas colunas de A. Tomemos x=[lxB xN], onde xB é formado pelas n primeiras entradas de x e xN formado pelas n-m últimas entradas de x. O sistema A x=b pode ser então escrito como
[ll B & N ][l xB xN ]=b

Passo 1

O enunciado nos dá o sistema linear
A,x=b,
onde A é mtimes n com m<n. Partimos a matriz em duas partes
A = l[B;;Nr],
onde B é uma submatriz quadrada mtimes m (colunas básicas) e N é mtimes(n-m) (colunas não-básicas). Também dividimos o vetor
x em
x=xBxN,
com xBinR^m e xNinR^n-m. O objetivo é reescrever o sistema em função de xN e caracterizar a solução básica.

Passo 2

Reescrevemos
l[B;;Nr]xBxN =B,xB+N,xN =b
Supondo que B é invertível, isolamos xB:
B,xB = b-N,xN Longrightarrow xB = B^-1l(b-N,xNr)
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 B é obtida impondo xN=0. Logo
xB = B^-1b, xN=0
Esse l(xB,xNr) é o ponto básico. Se além disso B^-1b>=0, é uma solução básica viável.

Resposta

boxed xB = B^-1b - B^-1N,xN, e, para a solução básica, xN=0,; xB=B^-1b çãá

Exercícios relacionados