Algoritmo simplex

Professor Everton C.

Identidade verificada

• CPF verificado
• E-mail verificado

Respondeu há 4 anos

Olá Marcio!
Uma breve introdução pode ajudar...

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? r mxm , x? r m e b? r m 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 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.