Metodo simplex

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1274 palavras )
  • Download(s) : 0
  • Publicado : 8 de setembro de 2012
Ler documento completo
Amostra do texto
Método Simplex

A programação linear consiste no aprimoramento de uma técnica para a resolução de um sistema de inequações lineares, através das inversões sucessivas de matrizes. Seja qual for o algoritmo da formulação do problema a ser resolvido deve figurar a função objetivo e suas variáveis, que a princípio estas variáveis devem assumir somente valores positivos e estarem sujeitas a umasérie de limitações, isto é, restrições do problema que são normalmente representadas por inequações, as quais devem estar de acordo com a hipótese principal que todas as relações entre variáveis devem ser lineares. O método simplex é o algoritmo mais citado e utilizado na maior parte da literatura especializada e nos softwares de programação linear. Pois, o método simplex consiste na padronização domodelo e segue um processo sequencial para determinar soluções básicas factíveis para a otimização da função objetivo.
O Método Simplex é um procedimento matricial para resolver o modelo de programação linear na forma normal. Começando com X0 , o método localiza sucessivamente outras soluções básicas viáveis acarretando melhores valores para a função objetivo até ser obtida a solução ótima. Oprograma Linear possui uma forma padrão onde as restrições estão expressas por meio de equações lineares. Pode-se representar a forma padrão como:

Z= cx
Ax = b
x>=0

onde: A é a matriz mxn dos coeficientes;
b é o vetor coluna mx1 das constantes;
x é o vetor coluna nx1 das variáveis;
c é o vetor linha 1xn dos coeficientes.

Pode-se transformar qualquerprograma linear para a forma padrão, usando algumas transformações a seguir:

Transformando desigualdades em igualdades: Inclui-se novas variáveis, com isso desigualdades são transformadas em igualdades.

Ex: 5x1 +4x2<=6
Introduzindo xf>=0
5x1 +4x2 + xf =6

Variáveis Irrestritas em sinal: É preciso que o sinal não-negativo das variáveis. Caso no problema apareça uma variável xirrestrita em sinal, pode-se substituí-la por duas variáveis não-negativas, x1 e x2,com x1 representando a parte positiva e x2 a negativa de x.

Variáveis Não-Positivas: Quando a variável de decisão x não pode ser positiva troca-se de variável:
Ex: x=-x1 ,em que x1>=0

Transformando o problema de Maximização em Minimização: Utilizando a relação abaixo:
Máximof(x) = - Mínimo{-f(x)}Constante do Lado Direito Negativa: Apenas multiplica-se a equação por (-1) trocando os sinais e invertendo o sentido.

Trocando uma Equação por duas Inequações: Veja o exemplo:
Equação: 3x1+5x2 = 70
Trocando...
3x1+5x2 >= 70
3x1+5x2 <= 70

Método Simplex passo a passo:

Passo 1 Localize o número mais negativo da última linha do quadro simplex, excluída aúltima coluna, e chame a coluna em que este número aparece de coluna de trabalho. Se existir mais de um candidato a número mais negativo, escolha um.

Passo 2 Forme quocientes da divisão de cada número positivo da coluna de trabalho pelo elemento da última coluna da linha correspondente (excluindo-se a última linha do quadro). Designe por pivô o elemento da coluna de trabalho que conduz ao menorquociente. Se mais de um elemento conduzir ao mesmo menor quociente, escolha um. Se nenhum elemento da coluna de trabalho for positivo, o problema não terá solução.

Passo 3 Use operações elementares sobre as linhas a fim de converter o elemento pivô em 1 e, em seguida, reduzir a zero todos os outros elementos da coluna de trabalho.

Passo 4 Substitua a variável x existente na linha pivô eprimeira coluna pela variável x da primeira linha e coluna pivô. Esta nova primeira coluna é o novo conjunto de variáveis básicas.

Passo 5 Repita os passos de 1 a 4 até a inexistência de números negativos na última linha, excluindo-se desta apreciação a última coluna.

Passo 6 A solução ótima é obtida atribuindo-se a cada variável da primeira coluna o valor da linha correspondente, na última...
tracking img