PESQUISA OPERACIONAL SIMPLEX

Prévia do material em texto

UCB - UNIVERSIDADE CATÓLICA DE BRASÍLIA
	
	Prof. Jean Robert Batana
	
	PESQUISA OPERACIONAL
MÉTODO SIMPLEX
INTRODUÇÃO
O termo pesquisa operacional foi citado pela primeira vez em meados de 1939, embora se acredite que tenha sido “criado” durante a revolução industrial. As técnicas de P.O. se aplicam a processos de seleção de alternativas e de decisão, desde que se apresentem de maneira estruturada.
As primeiras áreas a utilizarem esta técnica foram os processos de produção e fluxo (transporte, etc.). Alguns processos que não pareciam estruturados, tais como finanças, marketing, economia e medicina, foram sendo modelados e parcialmente estruturados, com isso tornaram-se objeto de aplicação da pesquisa operacional.
As técnicas utilizadas para solução dos problemas que normalmente ocorrem na vida real são bastante úteis, uma vez que estes apresentam dificuldades das mais variadas naturezas. 
Normalmente o procedimento para análise compreende (visão global):
perceber o problema;
estabelecer o objetivo;
dar a concepção do problema.
Com isso, podemos definir pesquisa operacional como sendo uma metodologia de estruturar processos aparentemente não estruturados por meio da construção de modelos. Para isso, utiliza-se um conjunto de técnicas quantitativas com o intuito de resolver os aspectos matemáticos dos modelos.
	Todo problema relacionado à área de pesquisa operacional envolverá as seguintes fases: 
Formulação do problema;
Identificar variáveis exógenas e endógenas ao sistema, assim como seu inter-relacionamento;
Construção do modelo;
Obtenção da solução;
Teste do modelo e avaliação da solução;
O modelo estabelecido será utilizado para prever, investigar e normatizar.
Os métodos mais comuns para se obter a solução de um problema relacionada a pesquisa operacional são a solução gráfica, método simplex e equações de transporte. Complementando estes, temos a dualidade, degeneração e análise de sensibilidade. 
2. MÉTODO SIMPLEX	
É uma técnica matemática desenvolvida em 1947 por George B. Dantzig. O Método Simplex indica a melhor solução para problemas que tem diversas soluções. É normalmente empregado onde se tem mais de três variáveis.
Trata-se de um método seqüencial de otimização e pode ser empregado tanto para maximizar quanto para minimizar uma resposta.
A idéia do Método Simplex é de partir de uma solução básica de um problema na forma padrão para outro, de tal maneira que o valor diminua continuamente até que um mínimo seja alcançado ou aumentar continuamente até que um máximo seja alcançado. 
O procedimento de otimização começa pela escolha dos n + 1 pontos onde será feita a avaliação da resposta.
A otimização começa com os pontos A, B, C.
O resultado obtido será validado contra as demais respostas para que o processo possa prosseguir.
Nota-se que no triângulo ABC, A mostra ter a pior resposta dos três.
Neste caso o Simplex será refletido de modo que o ponto D, oposto a A seja obtido.
Um experimento será conduzido agora nas condições experimentais do ponto D.
Os pontos B e C junto com o ponto D formam um novo Simplex.
O procedimento é repetido sucessivamente, descartando-se a pior resposta. Com isso, força-se o Simplex a mover-se para a região de resposta ótima. As decisões requeridas para que isso aconteça constituem as chamadas “regras” do procedimento Simplex.
2.1 – FORMA GERAL
Um problema típico apresenta-se na seguinte forma: 
Max (ou Min)	Z = c1x1 + c2x2 + ... + cnxn
 
Esta forma é conhecida como forma padrão. Na notação matricial, a forma padrão é representada por:
Max (ou Min):	Z = cx
Sujeito a:		Ax = b
x ( 0
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)
2.2 – TIPOS DE SOLUÇÕES
Dado o problema de programação linear abaixo,
Max (ou Min)	Z = cx
Sujeito a:	Ax = b
 x ( 0
Define-se:
Uma solução factível, viável ou compatível é um vetor x que satisfaz as condições Ax = b e x ( 0;
Região factível, viável ou compatível é o conjunto de todas as soluções factíveis; se essa região é vazia, o programa linear é impossível ou inviável;
Solução básica para Ax = b é uma solução obtida fazendo n - m variáveis iguais a zero (variáveis não básicas) e resolvendo em relação às demais (variáveis básicas).
Solução básica degenerada é quando uma ou mais variáveis básicas em uma solução básica tem valor zero.
Solução básica factível ocorre quando se tem uma solução factível e básica ao mesmo tempo.
Solução básica factível degenerada ocorre quando temos ao mesmo tempo uma solução básica degenerada e factível.
Solução ótima ou básica factível ótima é a solução básica factível que dentre todas as soluções básicas factíveis, nos dá o valor ótimo (valor mínimo), isto é, um valor que irá otimizar a função objetivo Z = cx.
A solução pode ser única ou podem haver ótimos alternativos 
quando 
.
Antes de se iniciar a solução de um problema linear utilizando-se o Método Simplex, exige-se que o problema esteja na forma padrão.
2.3 – TRANSFORMAÇÃO DE UM PROBLEMA GERAL PARA A FORMA PADRÃO
2.3.1 - Desigualdade do tipo menor ou igual
Suponha que certa restrição do sistema seja x1 ( 3. Neste caso, para colocar na forma padrão, introduz-se uma variável qualquer para eliminar o sinal de desigualdade. Esta variável é conhecida como variável de folga e deve ser do tipo xi ( 0. Para esta restrição, x1 ( 3, teríamos, após a introdução da variável de folga: x1 + x3 = 3, com x1, x3 ( 0.
Denomina-se sistema canônico, aquele em que todas as restrições são do tipo menor ou igual. Matricialmente teremos:
Max (ou Min):	Z = cx
Sujeito a:		Ax ( b (b ( 0)
 x ( 0
Sistemas na forma canônica apresentam as seguintes vantagens:
A passagem para a forma padrão se faz pelo simples acréscimo de uma variável de folga para cada equação;
A forma padrão resultante sempre consiste em um sistema que tem uma solução óbvia;
A solução consiste em zerar as variáveis originais e resolver o problema em relação às variáveis de folga.
2.3.2 - Desigualdade do tipo maior ou igual
Suponha que agora a restrição do sistema seja x2 ( 9. Do mesmo modo que o anterior, introduziremos uma variável de excesso para eliminar o sinal de desigualdade e colocar na forma padrão. Com isso teremos: x2 - x4 = 9, com x1, x4 ( 0; onde x4 é a variável de excesso.
2.3.3 - Variável sem restrição de sinal:
Se uma variável puder assumir valores tanto positivos quanto negativos, então ela poderá ser substituída por outras duas:
2.3.4 - Lado direito negativo:
Neste caso, basta multiplicar a expressão por -1.
2.3.5 - Transformação de uma igualdade:
Uma igualdade pode ser escrita como duas desigualdades. Exemplo:
2.3.6 - Equivalência entre maximização e minimização:
Sabe-se que o mínimo de uma função é equivalente ao máximo do simétrico dessa função. Assim:
MIN 	3x1 + 4x2 - x3 	eqüivale a MAX - 3x1 - 4x2 + x3
Exemplo: Transformar o sistema, a seguir, para a forma padrão:
MAX	Z = 2x1 + 3x2 - x3, sujeito a:
 x1 - 2x2 - x3 ( 1
 x1 + x2 + x3 ( - 4
5x1 - 3x2 + 4x3 = - 7
 x1, x3 ( 0
 x2 sem restrição de sinal
Solução: Operações necessárias para deixá-lo na forma padrão:
a. Substituir x2 por 
;
b. Incluir a variável de folga x4 na inequação 1 e a variável de excesso x5 na inequação 2;
c. Multiplicar por (-1) a equação 2 e a equação 3;
d. Com isso obtém-se a seguinte forma padrão:
2.4 – ALGORITMO PARA SOLUCIONAR UM PROBLEMA PELO MÉTODO SIMPLEX
Para se iniciar o uso do Método Simplex, é necessário conhecer uma soluçãofactível básica (chamada solução inicial) do sistema. O método verifica se a presente solução é ótima. Se for, o processo está encerrado. Se não, o método passa para o próximo ponto (no extremo adjacente). Inicia-se novamente o processo, até chegar ao ponto ótimo. Com isso, teremos o seguinte algoritmo:
Achar uma solução factível básica inicial;
Verificar se a solução atual é ótima. Se for, pare.
Determinar a variável não-básica que deve entrar na base.
Determinar a variável básica que deve sair da base.
Achar a nova solução factível básica, e voltar ao passo 2.
2.5 – EXEMPLO
Maximizar a função abaixo:
Max Z = 5x1 + 2x2, 	
sujeito a x1 ( 3
 x2 ( 4
x1 + 2x2 ( 9
x1, x2 ( 0
Solução:
Como as condições estão em forma de desigualdade ((), é necessário a introdução de variáveis de folga, x3, x4, x5, para deixá-lo na forma padrão. O sistema ficará então:
Max. 	Z = 5x1 + 2x2, 	
sujeito a x1 + x3 = 3
 x2 + x4 = 4
 x1 + 2x2 + x5 = 9
 x1, x2, x3, x4, x5 ( 0
 
Neste sistema teremos: 	variáveis básicas: x3, x4, x5 
 	variáveis não básicas: x1, x2
Passando o sistema acima para a forma matricial, teremos a seguinte solução factível básica óbvia:
	
�� EMBED Equation.3 
Verificar se a solução atual é ótima. Se for, pare. 
Para achá-la, substitui-se os valores de x1 e x2 na função objetivo (Z = 5x1 + 2x2). Verificamos que Z = 0. Conclui-se então que a solução ótimo não foi atingida, uma vez que qualquer valor que utilizarmos para x1 e x2 aumentará o valor de Z. 
É necessário saber agora qual variável não-básica deverá entrar na base para poder aumentar o valor da função objetivo.
( Utiliza-se neste caso, a variável não-básica com maior coeficiente positivo na função objetivo.
No problema em questão, “pegaremos” x1. Como estará entrando uma variável não-básica na base, no caso x1, deveremos eliminar uma variável básica. Para se determinar qual variável deverá ser eliminada, colocaremos todas as variáveis básicas em função das não-básicas:
x3 = 3 - x1		
x4 = 4 - x2	
x5 = 9 - x1 - 2x2	
A análise para se efetuar a eliminação é feita do seguinte modo: 
Objetivo é conseguir o maior valor possível de x1 ao mesmo tempo que nenhuma variável do sistema se torne negativa. 
Tira-se da base aquela variável básica que se anular mais rapidamente quando se aumenta o valor de x1.
Verificando como x1 influencia os valores das variáveis básicas x3, x4, x5, teremos:
x3 = 3 - x1	(x1 ( 3) 	(1)
x4 = 4 - x2	(x1 < () 	(2)
x5 = 9 - x1 - 2 x2	(x1 ( 9) 	(3)
para qualquer valor de x1 positivo, nota-se que x3 e x5 diminuem de valor. x4 permanece inalterado. Conclui-se então que das equações acima, x3 é a variável que se anula mais rápido. Portanto x1 entrará no lugar x3.
A nova base será formada pelas variáveis x1, x4 e x5. Como deve haver somente uma variável básica para cada equação, deve-se eliminar x1 da equação (3). Para tal, multiplicaremos a equação (1) por –1 e somamos à equação (3). Deste modo teremos:
x1	 + x3	 = 3			
x2	 + x4	 = 4			
2x2 - x3 + x5 = 6
Resolvendo o sistema, teremos:
	
Note que os valores de x1, x4 e x5, variáveis básicas, foram obtidos diretamente da matriz identidade acima, repetida abaixo.
Necessitamos agora avaliar se a presente solução é a solução ótima. Inicialmente não podemos substituir direto na equação objetivo porque houve mudanças, isto é, x1 é agora uma variável básica e a nova variável não-básica, x3, não está presente na equação Z = 5x1 + 2x2.
Como a função objetivo tem de estar em termos de variáveis não-básicas, substituiremos x1 por 3 - x3 (x1 + x3 = 3, equação base 1). Com isso obtemos:
Z = 5x1 + 2x2 = 5(3 - x3) + 2x2 = 15 + 2x2 - 5x3
Substituindo estes valores, obtemos Z = 15.
A solução obtida ainda não é ótima, visto que quando x2 entrar na base, aumentará o valor da função objetivo. A variável x3 não deve entrar na base, pois se tal ocorrer, o valor de Z será decrementado. 
Visto que x2 é a variável a entrar na base, deveremos determinar qual variável básica deverá sair. Colocando as variáveis básicas em função das não básicas, teremos:
 x1 + x3 	= 3			x1 = 3 - x3			(x2 < ()	(1)
 x2 + x4 = 4			x4 = 4 - x2 			(x2 ( 4)	(2)
2x2 - x3 + x5 = 6			x5 = 6 - 2x2 - x3		(x2 ( 3)	(3)
Verifica-se que x5 é a variável que se anula mais rapidamente com o aumento de x2.
Novamente, como deve haver somente uma variável básica para cada equação, deve-se eliminar x5 da equação (3), fazendo com que o nova base seja formada por x1, x2 e x4. Deste modo teremos:
 x1 + x3 	 = 3
	
	Semelhante à solução feita na primeira interação, obtemos os valores das variáveis x1, x2, x3, x4 e x5:
 x3= x5 = 0
 x1 = 3
 x2 = 3
x4 = 1
Colocando a função objeto em termos das variáveis não-básicas, teremos:
Z = 15 + 2x2 - 5x3		(	Z = 21 - 4x3 - x5, com Z = 21
Verifica-se que tanto x3 quanto x5 se entrarem na base, diminuirão o valor da função objetivo. Portanto estamos diante da solução ótima.
Então:
Z* = 5x1* + 2x2* ou Z* = 21 - 4x3* - x5* ; com x1 = 3 e x2 = 3.
Uma outra solução para o problema, é utilizar quadros. Os quadros visam apenas simplificar os cálculos da solução anterior.
	Relembrando a função do exemplo,
Max Z = 5x1 + 2x2, 	
sujeito a x1 ( 3
 x2 ( 4
x1 + 2x2 ( 9
x1, x2 ( 0
Semelhante ao método anterior, devemos passar para a forma padrão do Simplex. Com isso, a função acima ficará:
Máx 	Z = 5x1 + 2x2, 	
sujeito a x1 + x3 = 3
 x2 + x4 = 4
 x1 + 2x2 + x5 = 9
 x1, x2, x3, x4, x5 ( 0
 
onde x3, x4, x5 são as variáveis básicas e x1, x2 são as variáveis não básicas.
	Antes de prosseguir à montagem do quadro, deveremos “reorganizar” a função objetivo, fazendo com que os membros à direita da igualdade seja formado apenas por elementos que não sejam variáveis, semelhante às equações das restrições. Deste modo, a nossa função objetivo ficará:
Z = 5x1 + 2x2 => Z - 5x1 - 2x2 = 0
E o sistema (função objetivo e restrições) ficará:
Z - 5x1 - 2x2 	= 0
 x1 + x3 	= 3
 x2 + x4 = 4
 x1 + 2x2 + x5 = 9
 
Feito esta etapa, podemos montar o quadro. Este deverá apresentar estrutura semelhante ao quadro abaixo:
 	
	
	Z
	x1
	x2
	x3
	x4
	b
	Base
	1
	c1
	c2
	0
	0
	0
	x3
	0
	a11
	a12
	1
	0
	b1
	x4
	0
	a21
	a22
	0
	1
	b2
	Para o nosso problema, o quadro apresentará inicialmente a seguinte constituição:
	Base
	Z
	x1
	x2
	x3
	x4
	x5
	b
	
	1
	-5
	-2
	0
	0
	0
	0
	x3
	0
	1
	0
	1
	0
	0
	3
	x4
	0
	0
	1
	0
	1
	0
	4
	x5
	0
	1
	2
	0
	0
	1
	9
Sendo nulos os coeficientes de x3, x4 e x5 na linha (0), a função objetivo já se encontra somente em termos de variáveis não básicas (x1 e x2). Pode-se então afirmar que a presente solução não é ótima, uma vez que Z = 0 (valor de b na linha (0)). 
Para sabermos qual variável não básica irá entrar, basta utilizar a que tender ao ponto de maximização mais rápido, isto é, a que tiver o maior coeficiente negativo. No nosso caso, será x1. Em relação ao método anterior, é o oposto, uma vez que nele pegávamos a variável que possuía o maior coeficiente positivo. Atente-se que ambos métodos fazem exatamente a mesma coisa, pois Z - 5x1 - 2x2 = 0 é a mesma coisa que Z = 5x1 + 2x2 apenas os sinais que estão trocados. 
 Quanto a variável básica que deverá sair, devemos fazer análise semelhante ao método anterior, isto é, determinar qual o maior valor que x1 deverá tomar sem tornar negativa nenhuma outra variável. Paraisto, façamos uma relação entre os coeficientes relacionados a x1 e os coeficientes do vetor independente b:
Linha (1): 
Linha (3): 
Note que a linha (1) possui o menor coeficiente. Com isto, x1 tenderá a zero mais rápido. Portanto, x3 deverá sair da base e se tornará uma variável não básica e x1 se tornará a nova variável básica. 
( dica: se todos os ais forem menores ou iguais a zero, pare, pois Z = infinito.
Visto que x1 entra no lugar de x3, o próximo quadro deverá apresentar a seguinte base:
	Base
	Z
	x1
	x2
	x3
	x4
	x5
	b
	
	1
	0
	
	
	0
	0
	
	x1
	0
	1
	
	
	0
	0
	
	x4
	0
	0
	
	
	1
	0
	
	x5
	0
	0
	
	
	0
	1
	
Observe que na função objetivo os coeficientes x1, x4 e x5 foram colocados iguais a zero, pois é necessário tê-la apenas em termos das variáveis não básicas. A equação (1) será a nossa linha pivô (por ser a linha associada à variável que sai da base), sendo o elemento relacionado a x1 na linha (1) o nosso pivô. 
	Voltando ao nosso exemplo, tínhamos:
	Base
	Z
	x1
	x2
	x3
	x4
	x5
	b
	
	1
	-5
	-2
	0
	0
	0
	0
	x3
	0
	1
	0
	1
	0
	0
	3
	x4
	0
	0
	1
	0
	1
	0
	4
	x5
	0
	1
	2
	0
	0
	1
	9
onde havíamos determinado que x1 entraria na base e x3 sairia. 
Resta agora zerar a coluna relacionada ao pivô (coluna em escuro. Para tal tarefa, utilizaremos pivotamento.
L0 ( 5 x L1 + L0
L3 ( (-1)x L1 + L3
Com isso obteremos um novo quadro:
	Base
	Z
	x1
	x2
	x3
	x4
	x5
	b
	
	1
	0
	-2
	5
	0
	0
	15
	x1
	0
	1
	0
	1
	0
	0
	3
	x4
	0
	0
	1
	0
	1
	0
	4
	x5
	0
	0
	2
	-1
	0
	1
	6
 Neste novo quadro, A função objetivo terá a seguinte forma (ver linha (0)):
Z = 15 + 2x1 - 5x3 
que coincide com a equação obtida na primeira interação do método anterior. Nota-se que a mesma está totalmente em função de variáveis não básicas.
Pelo coeficiente (-2) na linha (0), podemos afirmar que a solução ainda não é ótima. Então a nova variável a entrar na base será x2. Resta determinar quem irá sair.
Aplicando o mesmo raciocínio que na primeira tabela, teremos:
Linha (2): 
Linha (3): 
Deve sair da base a variável associada a linha (3), isto é, x5. A linha pivô será portanto a linha (3). Zerando a coluna relacionada ao elemento pivô de x2 na coluna (3), 2, teremos: 
L0 ( 1 x L3 + L0
L2 ( (-1/2)x L3 + L2
L3 ( (1/2)x L3
O novo quadro ficará:
	Base
	Z
	x1
	x2
	x3
	x4
	x5
	b
	
	1
	0
	0
	4
	0
	1
	21
	x1
	0
	1
	0
	1
	0
	0
	3
	x4
	0
	0
	0
	1/2
	1
	-1/2
	1
	x5
	0
	0
	1
	-1/2
	0
	1/2
	3
	A presente solução é a ótima, pois não existe nenhum coeficiente negativo na linha (0) do quadro acima. A função objetivo será: 
Z = 21 - 4x3 – x5 
que coincide com a equação obtida do método anterior. x1 e x2 terão os seguintes valores (tirados da tabela): x1 = 3 e x3 = 3. 
2.6 – CASOS ESPECIAIS:
	Veremos agora alguns casos que podem ocorrer nos modelos de programação linear.
Problema de minimização:
Nos casos em que quando se solicitar ao invés da maximização for a minimização, pode-se utilizar uma das seguintes alternativas para solucionar o problema:
Inverter o teste de otimização e o critério de entrada na base. Vá resolvendo até que todos os coeficientes da função objetivo nos quadros sejam nulos ou negativos; neste caso a presente solução é ótima. 
Transformar o problema de minimização em um problema de maximização. Exemplo:
MIN Z = 2x1 + 3x2 – 5x3 	equivale a	 MAX W = - 2x1 - 3x2 + 5x3 
Na solução final, fazer Z = -W
Empate na entrada:
Quando mais de uma variável não básica tiverem o mesmo valor para seus respectivos coeficientes, deve-se escolher a variável que entrará na base de maneira aleatória. O que poderá acontecer é escolher um caminho mais longo ou mais curto. 
Empate na saída (na variável que irá sair da base):
Esta situação ocorre quando dois ou mais coeficientes bi/ais possuem o mesmo valor. Do mesmo modo que no caso anterior, escolher arbitrariamente quem sairá.
Exemplo: Deseja-se maximizar a função abaixo, submetida a certas restrições:
Máx. Z = 5x1 + 2x2, sujeito a 
 x1 ( 3
	 x2 ( 4
 	 4 x1 + 3x2 ( 12
	 x1, x2 ( 0
	Colocando-se as variáveis de folga no modelo e montando a tabela, teremos:
	Base
	Z
	x1
	x2
	x3
	x4
	x5
	b
	
	1
	-5
	-2
	0
	0
	0
	0
	x3
	0
	1
	0
	1
	0
	0
	3
	x4
	0
	0
	1
	0
	1
	0
	4
	x5
	0
	4
	3
	0
	0
	1
	12
A próxima etapa será escolher qual variável que sairá da base. Da tabela acima teremos:
Linha (1):	
Linha (3):	
Em ambos os casos, temos x1 ( 3. Como houve um “empate”, devemos escolher arbitrariamente qual variável deverá sair. Vamos então escolher x3 para sair da base. Com isso, a linha pivô será a linha (1) e o novo quadro será então: 
	Base
	Z
	x1
	x2
	x3
	x4
	x5
	b
	
	1
	0
	-2
	5
	0
	0
	15
	x1
	0
	1
	0
	1
	0
	0
	3
	x4
	0
	0
	1
	0
	1
	0
	4
	x5
	0
	0
	3
	-4
	0
	1
	0
( dica: note que a variável básica x5 é nula. Isso sempre ocorrerá quando houver um empate na saída. 
Como a solução ótima ainda não foi encontrada, deveremos novamente determinar quem entrará na base e quem deverá sair. Do quadro acima tiramos:
Linha (2):	
Linha (3):	
x5 sairá da base e x2 entrará no seu lugar. A linha pivô será a linha (3) e o novo quadro ficará então:
	Base
	Z
	x1
	x2
	x3
	x4
	x5
	b
	
	1
	0
	0
	7/3
	0
	2/3
	15
	x1
	0
	1
	0
	1
	0
	0
	3
	x4
	0
	0
	0
	4/3
	1
	-1/3
	4
	x2
	0
	0
	1
	-4/3
	0
	1/3
	0
que será a solução ótima (Z = 15, x1 = 3, x2 = 0).
Vamos ver o que aconteceria se ao invés de x3 fosse escolhido x5 para sair da base. Da tabela inicial temos:
	Base
	Z
	x1
	x2
	x3
	x4
	x5
	b
	
	1
	-5
	-2
	0
	0
	0
	0
	x3
	0
	1
	0
	1
	0
	0
	3
	x4
	0
	0
	1
	0
	1
	0
	4
	x5
	0
	4
	3
	0
	0
	1
	12
Colocando então x1 no lugar de x5, teremos:
	Base
	Z
	x1
	x2
	x3
	x4
	x5
	b
	
	1
	0
	7/4
	0
	0
	5/4
	15
	x3
	0
	0
	-3/4
	1
	0
	-1/4
	0
	x4
	0
	0
	1
	0
	1
	0
	4
	x1
	0
	1
	3/4 
	0
	0
	1/4
	3
que será a solução ótima (Z = 15, x1 = 3, x2 = 0).
Veja neste exemplo que quando adotamos x3 para sair da base, chegamos a solução ótima com duas interações. Já adotando x5 para sair da base, com apenas uma interação já chegamos a solução ótima. 
soluções múltiplas:
Assim como na solução gráfica, alguns problemas poderão apresentar mais de uma solução ótima. Quando se trabalha com duas variáveis, é fácil de se observar, pois podemos utilizar do recurso da solução gráfica para nos auxiliar. E para mais de três variáveis, onde os gráficos são mais complicados, senão impossíveis de serem feitos ? – quando isto ocorrer, felizmente, o método Simplex é capaz de acusá-lo. Vamos ver no exemplo abaixo, uma aplicação desta situação e ver como o Simplex irá detectar que há soluções múltiplas.
Suponha o problema de maximização abaixo, com suas restrições.
Máx. Z = x1 + 2x2, sujeito a 
 x1 ( 3
	 x2 ( 4
 	 x1 + 2x2 ( 9
	 x1, x2 ( 0
	Introduzindo as variáveis de folga x3, x4 e x5 e montando o quadro, teremos:
	Base
	Z
	x1
	x2
	x3
	x4
	x5
	b
	
	1
	-1
	-2
	0
	0
	0
	0
	x3
	0
	1
	0
	1
	0
	0
	3
	x4
	0
	0
	1
	0
	1
	0
	4
	x5
	0
	1
	2
	0
	0
	1
	9
1a interação: entra x2 e sai x4. A nova tabela ficará então: 
	Base
	Z
	x1
	x2
	x3
	x4
	x5
	b
	
	1
	-1
	0
	0
	2
	0
	8
	x3
	0
	1
	0
	1
	0
	0
	3
	x2
	0
	0
	1
	0
	1
	0
	4
	x5
	0
	1
	0
	0
	-2
	1
	1
2a interação: entra x1 e sai x5. A nova tabela ficaráentão: 
	Base
	Z
	x1
	x2
	x3
	x4
	x5
	b
	
	1
	0
	0
	0
	0
	1
	9
	x3
	0
	0
	0
	1
	2
	-1
	2
	x2
	0
	0
	1
	0
	1
	0
	4
	x1
	0
	1
	0
	0
	-2
	1
	1
que caracteriza a solução ótima. A função objetivo será portanto: 
Z = 9 – 0x4 – x5, com x1 = 1 e x2 = 4
	Note que a variável não-básica x4 na função objetivo é nula. Poderá ser um problema com soluções múltiplas. ( Para verificarmos esta hipótese é necessário fazer mais uma interação. Se não houver mudança no resultado final, é sinal que o problema possui soluções múltiplas. 
	Como x4 entrará na base, qualquer que seja o valor que ela assuma, a função objetivo ficará com seu valor inalterado. Para testar esta afirmação façamos esta interação. 
	x4 é quem entrará na base e quem deverá sair será x3. Com isso o quadro ficará:
	Base
	Z
	x1
	x2
	x3
	x4
	x5
	b
	
	1
	0
	0
	0
	0
	1
	9
	x4
	0
	0
	0
	1/2
	1
	-1/2
	1
	x2
	0
	0
	1
	-1/2
	0
	1/2
	3
	x1
	0
	1
	0
	1
	0
	0
	3
	Nesta nova solução, também ótima, temos a função objetivo idêntica a anterior, só modificando a variável, que deixa de ser x4 e passa a ser x3. A única modificação real foi a coordenada do vértice que passa a ser (3,3) - valores estes de x1 e x2. 
	Se fizermos novamente outra interação, x3 entrará na base e retornaremos ao quadro da primeira solução. Com isso, concluímos que este problema apresenta solução múltipla, cujas soluções são os vértices (1,4) e (3,3). 
Soluções infinitas:
	( Ocorre quando uma variável não-básica com coeficiente negativo na linha (0), em problemas de maximização, não tiver coeficientes positivos nas demais linhas. 
	Vejamos o exemplo abaixo:
Máx. Z = 5x1 + 2x2, sujeito a 
 x2 ( 4
 	 x1 + 2x2 ( 9
	 x1, x2 ( 0
	Introduzindo as variáveis de folga e excesso e montando a tabela, teremos:
	Base
	Z
	x1
	x2
	x3
	x4
	b
	
	1
	-5
	-2
	0
	0
	0
	x3
	0
	0
	1
	1
	0
	4
	x4
	0
	1
	2
	0
	-1
	9
	Após a 1a interação teremos:
	Base
	Z
	x1
	x2
	x3
	x4
	b
	
	1
	0
	8
	0
	-5
	45
	x3
	0
	0
	1
	1
	0
	4
	x1
	0
	1
	2
	0
	-1
	9
Próxima variável a entrar na base é x4. Falta determinar quem irá sair. Vamos fazer uma rápida análise: x4 possui coeficientes 0 e –1. Se x4 aumentar, a variável x3 permaneça inalterada enquanto que x1 aumenta indefinidamente. Concluiu-se então que Z = (.
Para uma rápida identificação basta aplicar o “macete” dado no início, isto é, quando uma variável não-básica com coeficiente negativo na linha (0), em problemas de maximização, não tiver coeficientes positivos nas demais linhas, o problema terá soluções infinitas. Veja o quadro abaixo, repetido do quadro acima. 
	Base
	Z
	x1
	x2
	x3
	x4
	b
	
	1
	0
	8
	0
	-5
	45
	x3
	0
	0
	1
	1
	0
	4
	x1
	0
	1
	2
	0
	-1
	9
2.7 – BIBLIOGRAFIA BÁSICA
MIRSHAWKA, Victor; “Programação Linear”; Livraria Nobel; São Paulo, 1971.
LUENBERGER, David G.; “Introduction to Linear and Nonlinear Programming”; Addison-Wesley Publishing Company; Massachusetts, USA, 1973.
BOLDRINI, José Luiz; Outros; “Álgebra Linear”; Editora Harbra ltda; São Paulo, 1980, 3a edição.
BREGALDA, Paulo F.; Outros; “Introdução à Programação Linear”; Editora Campus Ltda; Rio de Janeiro, 1981.
Sujeito a
� EMBED Equation.3 ���
� EMBED Equation.3 ���
� EMBED Equation.3 ���
� EMBED Equation.3 ���
� EMBED Equation.3 ���
� EMBED Equation.3 ���
� EMBED Equation.3 ���
Sujeito a:
� EMBED Equation.3 ���
Nesta coluna colocar todas as variáveis básicas
Nesta linha deverá ser colocado o valor dos coeficientes das variáveis que compõem a função objetivo
Nas linhas restantes colocar o valor dos coeficientes das variáveis que compõem as restrições.
(0)�
�
(1)�
�
(2)�
�
(3)�
�
(0)�
�
(1)�
�
(2)�
�
(3)�
�
(0)�
�
(1)�
�
(2)�
�
(3)�
�
(0)�
�
(1)�
�
(2)�
�
(3)�
�
Linha pivô
Pivô
A coluna relacionado ao pivô deverá ser zerada.
(0)�
�
(1)�
�
(2)�
�
(3)�
�
O elemento pivô deverá ter valor unitário.
(0)�
�
(1)�
�
(2)�
�
(3)�
�
(0)�
�
(1)�
�
(2)�
�
(3)�
�
(0)�
�
(1)�
�
(2)�
�
(3)�
�
(0)�
�
(1)�
�
(2)�
�
(3)�
�
(0)�
�
(1)�
�
(2)�
�
(3)�
�
(0)�
�
(1)�
�
(2)�
�
(3)�
�
(0)�
�
(1)�
�
(2)�
�
(3)�
�
(0)�
�
(1)�
�
(2)�
�
(3)�
�
(0)�
�
(1)�
�
(2)�
�
(3)�
�
(0)�
�
(1)�
�
(2)�
�
(0)�
�
(1)�
�
(2)�
�
(0)�
�
(1)�
�
(2)�
�
� EMBED MSPhotoEd.3 ���
_1001072219.unknown
_1001102461.unknown
_1001533557.unknown
_1001590609.unknown
_1001590640.unknown
_1001880908.bin
_1001533590.unknown
_1001528907.unknown
_1001528923.unknown
_1001526552.unknown
_1001074273.unknown
_1001102407.unknown
_1001074230.unknown
_1001065576.unknown
_1001066256.unknown
_1001071485.unknown
_1001066093.unknown
_1001060220.unknown
_1001060428.unknown
_1001060677.unknown
_1001060732.unknown
_1001060777.unknown
_1001060637.unknown
_1001060255.unknown
_1001059262.unknown
_1001060104.unknown
_1001059197.unknown
_1001058250.unknown