Simplex passo a passo

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) ii) iii) Todas as variáveis são não-negativas: Todos os bi’ são não-negativos; 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.
A ∈ℜ mxn

Porém, se dado um sistema Ax=b, onde: b ∈ℜ m x ∈ℜ n

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?

29

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 o sistema Ax=b, definido em (3.1) e B ∈ ℜmxm uma submatriz base de A, então, as variáveis associadas à submatriz B ∈ ℜmxm são denominadas variáveis básicas. Notação: variáveis básicas: xB. Definida a submatriz base B restam