Metodo Simplex Completo

06/05/2014

MÉTODO SIMPLEX

SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX
Vamos entender a solução analítica com o uso de um exemplo. Considere o seguinte modelo: max Z = 3*X1 + 2*X2 sujeito a
X1 + X2 ≤ 6
5*X1 + 2*X2 ≤ 20
X1, X2 ≥ 0

1

06/05/2014

SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX
INÍCIO
Colocar o problema em formato padrão, ou seja:






Equações lineares (igualdades);
Termos independentes (RHS) não negativos;
Variáveis de decisão não negativas.

Max Z = 3*X1 + 2*X2

(0)

sujeito a
X1 + X2 + X3
=6
(1)
5*X1 + 2*X2
+ X4 = 20 (2)
X1, X2, X3, X4 ≥ 0
(3)

SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX
PASSO 1
Encontrar uma solução básica inicial para o problema de PL.
Atribuir 0 às variáveis de decisão X1 e X2 (variáveis não básicas).


Assim:
VNB = {X1, X2} e VB = {X3, X4}
Solução básica factível: X3 = 6 e X4 = 20
Solução: {X1, X2, X3, X4} = {0, 0, 6, 20}
Função Objetivo: Z = 0

2

06/05/2014

SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX
PASSO 2
Teste de otimalidade: verificar os coeficientes das variáveis não básicas na função objetivo. Se estes não forem positivos, achou-se o ótimo e para-se as iterações. Se algum for positivo, ainda não estamos no ótimo e devemos determinar uma Solução Básica
Factível Adjacente melhor.
Para tanto temos 3 sub-passos:






Definir variável não básica que entrará na base
Definir variável básica que sairá da base
Transformar o sistema de equações e recalcular a solução básica

SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX


Sub-Passo 2.1: Definir VNB a entrar na base

A VNB a entrar na base é aquela que apresentar o maior coeficiente positivo na função objetivo.
No nosso exemplo, a F.O. é: max Z = 3*X1 + 2*X2
Dessa forma, a variável X1 entrará na base.

3

06/05/2014

SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX
Sub-Passo 2.2: Definir VB a sair da base
A VB a sair da base é a VB atual que mais restringe o crescimento da variável não básica escolhida para entrar na base.
Para definir isso, usamos as restrições que temos e atribuímos 0 às variáveis que permaneceram