Introducao Ao Metodo Simplex

ESCOLA POLITÉCNICA
CURSO DE SISTEMAS DE INFORMAÇÃO
DISCIPLINA DE PESQUISA OPERACIONAL

INTRODUÇÃO AO MÉTODO SIMPLEX

O desenvolvimento de um método (ou algoritmo) que determine a solução de um problema de programação linear (PPL) torna necessária a redução do problema a uma forma tal que permita a aplicação direta deste algoritmo.

No caso de programação linear, o algoritmo mais utilizado é o simplex.

Para que o simplex seja aplicado, é fundamental reduzir o PPL à forma-padrão.

FORMA-PADRÃO DE UM PPL

Definição. A forma-padrão do PPL com m restrições e n variáveis pode ser representada como segue, com os coeficientes do lado direito necessariamente não negativos ( bi  0, i = 1,2, ... , m).

Os dois últimos conjuntos de equações normalmente são denominados restrições do PPL;
O último denomina-se condição de não negatividade;
A primeira equação representa a função objetivo.

NOTAÇÃO MATRICIAL

onde

A = matriz (m x n) dos coeficientes tecnológicos;
X = vetor coluna ( n x 1 ) das variáveis de decisão; b = vetor coluna ( m x 1 ) do lado direito das restrições; b  0, ou vetor dos recursos disponíveis; c = vetor linha ( 1 x n ) dos lucros (ou custos).

TRANSFORMAÇÃO DE UM PPL QUALQUER À FORMA PADRÃO

A forma-padrão implica que o primeiro grupo de restrições envolva somente igualdades e que todas as variáveis do modelo sejam não negativas.

a) DESIGUALDADE DO TIPO MENOR OU IGUAL

Seja uma restrição linear do tipo

Esta será convertida em igualdade pela adição de uma nova variável, não negativa, ao lado esquerdo da desigualdade.

Esta variável é numericamente igual à diferença entre os valores à direita e à esquerda da desigualdade e é conhecida como variável de folga.

Ela representa o desperdício acarretado pela parte do sistema modelado pela restrição em pauta.

SISTEMA CANÔNICO

É aquele em que todas as restrições são do tipo menor ou igual.