metodo simplex

Prévia do material em texto

Pesquisa Operacional A 
*
*
*
PROGRAMAÇÃO MATEMÁTICA MÉTODO SIMPLEX
Professor: D.Sc. Dalessandro Soares Vianna
dalessandrosoares@yahoo.com.br
dalessandro@ucam-campos.br
dalessandro@pesquisador.cnpq.br
Pesquisa Operacional A 
*
*
*
Agradecimentos 
O material apresentado durante este curso é baseado nas notas de aula dos professores:
Edwin Benito Mitacc Meza e
Fermín Alfredo Tang Montané,
professores do programa de Mestrado em Pesquisa Operacional e Inteligência Computacional da Universidade Candido Mendes - Campos.
Solução de Modelos de PL
Método Gráfico
Método Simplex
Método Simplex Dual
Método Simplex 
Pesquisa Operacional A 
*
*
Método Simplex
Pesquisa Operacional A 
*
*
Método Simplex
Parte do valor da F.O. de um vértice qualquer que pertença a o espaço de soluções viáveis.
Caminha pelos vértices até encontrar uma solução que não possua soluções vizinhas melhores que ela
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
_1236437956.unknown
_1236438442.unknown
_1236438621.unknown
_1250489348.unknown
_1250489408.unknown
_1250489487.unknown
_1236438707.unknown
_1236438478.unknown
_1236438492.unknown
_1236438465.unknown
_1236438413.unknown
_1236438429.unknown
_1236438002.unknown
_1236437842.unknown
_1236437909.unknown
_1236437841.unknown
Pesquisa Operacional A 
*
*
Método Simplex
A solução ótima pode não existir:
Quando não há uma solução viável (restrições incompatíveis);
Quando não há um valor máximo (ou mínimo) da F.O. (1 ou mais variáveis tendem ao infinito e as restrições continuarem sendo satisfeitas).
Pesquisa Operacional A 
*
*
Fundamentos
Transformação de um PPL em um sistema de equações equivalentes
FORMA CANÔNICA
FORMA PADRÃO
Pesquisa Operacional A 
*
*
Procedimentos (forma canônicaforma padrão)
Para restrições de desigualdade “”: 
 
A conversão é feita adicionando à equação uma variável artificial fj 0. 
Para restrições de desigualdade “”: 
 
A conversão é feita subtraindo à equação uma variável artificial fj 0. 
Pesquisa Operacional A 
*
*
Procedimentos (forma canônicaforma padrão)
FORMA CANÔNICA
FORMA PADRÃO
O problema se transformou em encontrar uma solução de um sistema de equações lineares que maximize a F.O.
Variáveis: n=5 
Restrições: m=3
n > m
Pesquisa Operacional A 
*
*
Método de Enumeração das Soluções Básicas
Analisando, podemos dizer que atribuir zero a uma variável significa não produzir um dos produtos ou utilizar toda a disponibilidade de recursos.
O número de soluções básicas possíveis 
(n-m) variáveis iguais a zero  solução básica
soluções básicas possíveis 
Pesquisa Operacional A 
*
*
Método de Enumeração das Soluções Básicas
Variáveis não básicas: São as variáveis zeradas, igual a (n-m) variáveis.
Variáveis básicas: São as variáveis cujos valores são calculados pelo sistema de equações.
1ª Combinação:
Variáveis Não Básicas: 
Variáveis Básicas: 
Solução Básica: 
Solução Viável !!!
Pesquisa Operacional A 
*
*
Método de Enumeração das Soluções Básicas
2ª Combinação:
Variáveis Não Básicas: 
Variáveis Básicas: 
Solução Básica: 
Não existe !!!
Não existe Base Associada !!!!
Continuar .......
Pesquisa Operacional A 
*
*
Método de Enumeração das Soluções Básicas
Pesquisa Operacional A 
*
*
Método de Enumeração das Soluções Básicas
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
� EMBED Equation.DSMT4 ���
_1236437956.unknown
_1236438442.unknown
_1236438621.unknown
_1250489348.unknown
_1250489408.unknown
_1250489487.unknown
_1236438707.unknown
_1236438478.unknown
_1236438492.unknown
_1236438465.unknown
_1236438413.unknown
_1236438429.unknown
_1236438002.unknown
_1236437842.unknown
_1236437909.unknown
_1236437841.unknown
Pesquisa Operacional A 
*
*
Método de Enumeração das Soluções Básicas
Pesquisa Operacional A 
*
*
Desenvolvimento do Método Simplex
Problemas Reais
Método gráfico e enumeração
Inviável
Qual o sistema de equações que deve ser resolvido;
Qual é o próximo sistema a ser resolvido que fornecerá uma solução melhor que os anteriores;
Como identificar uma solução ótima, uma vez que tenhamos encontrado.
Pesquisa Operacional A 
*
*
Método Simplex - Passo 1 
Transformar o PPL da sua forma Canônica para sua forma Padrão. 
Pesquisa Operacional A 
*
*
Método Simplex - Passo 2 
Montar um quadro para ordenarmos as operações, colocando neles apenas os coeficientes das variáveis.
Quadro Inicial
A solução inicial será sempre obtida fazendo as variáveis originais do modelo iguais a zero e achando o valor das demais.
Pesquisa Operacional A 
*
*
Método Simplex - Passo 3 
Quadro Inicial
Das variáveis não básicas na primeira solução, qual deve-se tornar positiva ?
Das 3 variáveis básicas na primeira solução, qual deverá ser anulado?
Deve ser a variável que MAIS CONTRIBUI para o lucro
Entra: x2
4/0=
12/2=6
18/2=9
Será aquela associada à linha que tiver o menor quociente entre o elemento da última coluna e o correspondente elemento da coluna de entrada.
Sai: f2
Pesquisa Operacional A 
*
*
Método Simplex - Passo 3 
Quadro Inicial
EquaçãoPivô
Para a mudança da base (na busca por outra solução) emprega-se 2 operações de cálculo:
Na equação do Pivô:
Nas demais equações incluindo Z:
Gera uma nova solução básica
Pesquisa Operacional A 
*
*
Método Simplex - Passo 3 
Pesquisa Operacional A 
*
*
Método Simplex - Passo 3 
Pesquisa Operacional A 
*
*
Método Simplex - Passo 3 
Pesquisa Operacional A 
*
*
Método Simplex - Passo 3 
Pesquisa Operacional A 
*
*
Método Simplex - Passo 3 
Quadro I
Pesquisa Operacional A 
*
*
Método Simplex - Passo 3 
Quadro I
Quadro II
Pesquisa Operacional A 
*
*
Método Simplex - Passo 3 
Quadro II
Como todas as VARIÁVEIS NA ÚLTIMA LINHA tem COEFICIENTES POSITIVOS foi encontrado a SOLUÇÃO ÓTIMA.