O Método Simplex

3- O MÉTODO SIMPLEX

3.1- Introdução

O Método Simplex é uma técnica utilizada para se determinar,

numericamente, a solução ótima de um modelo de Programação Linear. Será

desenvolvido inicialmente para Problemas de Programação Linear, na forma

padrão, mas com as seguintes características para o sistema linear de

equações:

i) Todas as variáveis são não-negativas:

3.1- Introdução

O Método Simplex é uma técnica utilizada para se determinar,

numericamente, a solução ótima de um modelo de Programação Linear. Será

desenvolvido inicialmente para Problemas de Programação Linear, na forma

padrão, mas com as seguintes características para o sistema linear de

equações:

i) Todas as variáveis são não-negativas:

ii) Todos os bi’ são não-negativos;

iii) Todas as equações iniciais do sistema são do tipo “ £ “. Assim, na forma

padrão, só encontra-se variáveis de folga.

Se uma das características vistas não ocorrer, então, casos especiais do

método devem ser considerados e esses serão vistos na seção 3.8, como o

Método Simplex de Duas Fases.

3.2- Introdução e fundamentos teóricos para o Método Simplex

3.2.1- Determinação de soluções básicas em um sistema de equações

lineares m x n , m £ n (sistemas lineares)

Se ao resolver-se um sistema Ax=b, onde AÌ rmxm, xÎ rm e bÎ rm e

A fosse uma matriz inversível, então a solução seria facilmente determinada.

Porém, se dado um sistema Ax=b, onde:

A

b

x

m n

mxn

m

n

ÎÂ

ÎÂ

ÎÂ









£ (3.1)

Tal que m£ n, ou seja, sistema é retangular, como determinar soluções

de Ax=b?

O sistema acima sempre tem solução?

30

Teorema 3.2.1.1:

Seja a matriz A Î Âmxn com m £ n. Se a matriz A possui m colunas

a1, a2,…, am linearmente independentes (LI’s), então para qualquer b Î Âm , o

sistema Ax=b tem ao menos uma solução em Ân .

Definição 3.2.1.1:

Seja Ax=b, A Î Âmxn , b Î Âm, x Î Ân (m £ n).

Se A possui uma submatriz B Î Âmxn onde det B¹ 0 então diz-se que B

é uma submatriz base de A, o que é equivalente a dizer:

“Se A tem m colunas LI, então a matriz B formada por estas colunas

é uma base para Âm”.

Definição 3.2.1.2 - Variáveis básicas e não básicas:

Considerando-se