ZAB1058 PESQUISA OPERACIONAL E OTIMIZAO
DE SISTEMAS AGROPECURIOS
PROGAMAO LINEAR:
MTODO SIMPLEX
MTODO SIMPLEX ANALTICO: CONCEITOS E DEFINIES
MTODO SIMPLEX ANALTICO: PROCEDIMENTO ITERATIVO
MTODO SIMPLEX TABULAR: CONCEITOS E DEFINIES
MTODO SIMPLEX TABULAR: PROCEDIMENTO ITERATIVO
Mtodo Simplex: forma analtica
Procedimento de soluo (para modelo j elaborado)
Transformao de inequaes (nas restries) em equaes
Introduzir variveis referentes diferena entre RHS e LHS
Determinao de uma soluo vivel inicial
incio
Aprimoramento iterativo at soluo tima
obter soluo
vivel inicial
Exemplo: Max Z = 5x1 + 5x2 + 3x3
sujeito a
x1 + 3x2 + x3 3
x1 + 3x3 2
2x1 x2 + 2x3 4
2x1 + 3x2 x3 2
x1 , x2 , x3 0
fim
sim
soluo
tima?
no
obter soluo
vivel melhor
Restries: inequaes equaes
Introduo de variveis de folga inequaes tipo
Compensar diferena entre LHS e RHS das inequaes
x4
x1 + 3 x2 + x3 3
x1 + 3x2 + x3 + x4 = 3
x5
x1 + 3x3 2
x1 + 3x3 + x5 = 2
x6
2 x1 x2 + 2 x3 4
2 x1 x2 + 2 x3 + x6 = 4
x7
2 x1 + 3x2 x3 2
2 x1 + 3x2 x3 + x7 = 2
Condio de no-negatividade (todas as variveis):
x1 , x2 , x3 , x4 , x5 , x6 , x7 0
Terminologia
Dicionrio conjunto de equaes resultantes
x4 = 3 x1 3 x2 x3
x5 = 2 + x1 3 x3
x6 = 4 2 x1 + x2 2 x3
x7 = 2 2 x1 3 x2 + x3
Z = 5 x1 + 5 x2 + 3 x3
Variveis bsicas lado esquerdo do dicionrio
Variveis no-bsicas lado direito do dicionrio
Soluo vivel inicial
Soluo bvia / trivial variveis no-bsicas nulas
x4
x
x1 = 0
5
x2 = 0 x6
x
x3 = 0
7
Z
= 3 x1 3 x2 x3
x4 = 3
= 2 + x1 3x3
x5 = 2
= 4 2 x1 + x2 2 x3 x6 = 4
= 2 2 x1 3 x2 + x3
= 5 x1 + 5 x2 + 3x3
x7 = 2
Z =0
Soluo vivel inicial: (0, 0, 0, 3, 2, 4, 2) Z = 0
aprimoramento iterativo a maximizar
Aprimoramento iterativo da soluo
Em cada iterao da busca pela soluo tima:
Alternncia entre variveis bsicas / variveis no-bsicas
Uma nica varivel entra no conjunto de variveis bsicas (base)
Uma nica varivel sai do conjunto de variveis bsicas (base)
Determinao da varivel que entra na base:
Maior incremento possvel para Z maior coeficiente positivo
Determinao da varivel que sai da base:
Condio de no-negatividade limitao varivel que entra
Atualizao do dicionrio devido alterao entre as variveis
Aprimoramento iterativo da soluo
1 iterao
Varivel que entra na base maior aumento possvel de Z
Z = 5 x1 + 5 x2 + 3 x3
Varivel que sai da base
x4
x1 0
x
x2 = 0 5
x6
x3 = 0
x7
(escolha arbitrria: empate c/ x2)
- Condio de no-negatividade
- Limitao ao crescimento de x1
= 3 x1 3x2 x3 0
x1 3
= 2 + x1 3x3 0
x1 2
= 4 2 x1 + x2 2 x3 0 x1 2
= 2 2 x1 3x2 + x3 0 x1 1
Aprimoramento iterativo da soluo
1 iterao (continuao)
Atualizao do dicionrio x1 em funo de x2, x3, x7
x4
x5
x6
x7
Z
= 3 x1 3 x2 x3
x4 = 2 32 x2 32 x3 + 12 x7
x entra x = 3 3 x 5 x 1 x
= 2 + x1 3 x3
2 3
2 7
2 2
5
1
x6 = 2 + 4 x2 3 x3 + x7
= 4 2 x1 + x2 2 x3
= 2 2 x1 3 x2 + x3 x7 sai x1 = 1 32 x2 + 12 x3 12 x7
= 5 x1 + 5 x2 + 3 x3
Z = 5 52 x2 + 112 x3 52 x7
Nova soluo bvia (trivial) vivel:
x1 = 1 , x2 = 0 , x3 = 0 , x4 = 2 , x5 = 3 , x6 = 2 , x7 = 0 Z = 5
Aprimoramento iterativo da soluo
2 iterao
Varivel que entra na base maior aumento possvel de Z
Z = 5 52 x2 + 112 x3 52 x7
Varivel que sai da base
- Condio de no-negatividade
- Limitao ao crescimento de x3
x4 = 2 32 x2 32 x3 + 12 x7 0
x7 = 0
5
3
1
x5 = 3 2 x2 2 x3 2 x7 0
x2 = 0
x6 = 2 + 4 x2 3x3 + x7 0
x3 0
x1 = 1 32 x2 + 12 x3 12 x7 0
x3
x3
x3
4
3
6
5
2
3
x3 2
Aprimoramento iterativo da soluo
2 iterao (continuao)
Atualizao do dicionrio x3 em funo de x2, x6, x7
x4 = 2 32 x2 32 x3 + 12 x7
x4 = 1 72 x2 + 12 x6
x5 = 3 32 x2 52 x3 12 x7 x3 entra x5 = 43 296 x2 + 56 x6 43 x7
x3 = 23 + 43 x2 13 x6 + 13 x7
x6 = 2 + 4 x2 3 x3 + x7
x1 = 1 32 x2 + 12 x3 12 x7 x6 sai x1 = 43 56 x2 16 x6 13 x7
5
5
11
Z = 5 2 x2 + 2 x3 2 x7
Z = 263 + 296 x2 116 x6 23 x7
Nova soluo bvia (trivial) vivel:
x1 = 43 , x2 = 0 , x3 = 23 , x4 = 1 , x5 = 43 , x6 = 0 , x7 = 0 Z =
26
3
Aprimoramento iterativo da soluo
3 iterao
Varivel que entra na base maior aumento possvel de Z
Z=
26
3
+ 296 x2 116 x6 23 x7
- Condio de no-negatividade
Varivel que sai da base
- Limitao ao crescimento de x2
x4 = 1 72 x2 + 12 x6 0
x7 = 0
x = 4 29 x + 5 x 4 x 0
x2 0 5 32 46 2 16 6 1 3 7
x3 = 3 + 3 x2 3 x6 + 3 x7 0
x6 = 0
x1 = 43 56 x2 16 x6 13 x7 0
x2
x2
2
7
8
29
x2 12
x2 85
Aprimoramento iterativo da soluo
3 iterao (continuao)
Atualizao do dicionrio x2 em funo de x5, x6, x7
x4 = 1 72 x2 + 12 x6
x5 = 43 296 x2 + 56 x6 43 x7 x2 entra
x3 = 23 + 43 x2 13 x6 + 13 x7
x1 = 43 56 x2 16 x6 13 x7 x5 sai
26
29
11
2
Z = 3 + 6 x2 6 x6 3 x7
28
21
x5 293 x6 + 29
x7
x4 = 291 + 29
8
6
5
8
x
=
x
+
x
x7
2
5
6
29
29
29
29
30
8
3
x3 = 29 29 x5 29 x6 291 x7
x = 32 + 5 x 9 x 3 x
1 29 29 5 29 6 29 7
Z = 10 x5 x6 2 x7
Nova soluo bvia (trivial) vivel soluo tima:
x1 =
32
29
, x2 =
8
29
, x3 =
30
29
, x4 =
1
29
, x5 = 0 , x6 = 0 , x7 = 0 Z = 10
Mtodo Simplex: forma tabular
Forma conveniente para soluo manual
Dicionrio substitudo por quadro
Simplex equivalente para registro
das informaes essenciais
- coeficientes / constantes
- variveis bsicas
- variveis no-bsicas
Operaes analticas manipulao da tabela
Critrio de parada das iteraes redefinir
Exemplo: Max Z = 5x1 + 2x2
sujeito a
x1 3
fim
x2 4
sim
incio
obter soluo
vivel inicial
soluo
tima?
no
x1 + 2x2 9
obter soluo
vivel melhor
x1 , x2 0
Dicionrio inicial modificado
Variveis (deciso, folga, objetivo) no lado esquerdo
x3 = 3 x1
x1 + x3
x4 = 4 x2
x2 + x4
x5 = 9 x1 2 x2
x1 + 2 x2 + x5
Z 5 x1 2 x2
Z = 5 x1 + 2 x2
=3
=4
=9
=0
Critrio de parada do procedimento iterativo
Mtodo analtico: maximizar Z coeficientes positivos
Mtodo tabular: maximizar Z coeficientes negativos
Parada equao de Z somente c/ coeficientes no negativos
Quadro Simplex: organizao
Estrutura (formato) do quadro Simplex:
Coluna inicial esquerda variveis bsicas, funo-objetivo
Coluna final direita termos independentes
Colunas internas coeficientes de todas as variveis
Opcional
varivel ndice
bsica da eq.
- 2 coluna esquerda ndice da equao
- Coluna extra direita resultado da diviso
coeficiente de:
Z
x1
x2
x3
x4
x5
termo valor da
indep. diviso
x3
x4
x5
Quadro Simplex: leitura, interpretao
Variveis bsicas e funo-objetivo: coluna esquerda
Valor correspondente coluna dos termos independentes
Variveis no-bsicas: ausentes na coluna esquerda
Valor correspondente nulo (na iterao corrente)
Soluo vivel inicial = (0, 0, 3, 4, 9) Z = 0
varivel ndice
bsica da eq.
coeficiente de:
Z
x1
x2
x3
x4
x5
a maximizar
termo valor da
indep. diviso
x3
x4
x5
Aprimoramento iterativo da soluo
Em cada iterao da busca pela soluo tima:
Soluo tima ? ausncia de coeficientes negativos (eq. 0)
Alternncia entre variveis bsicas / variveis no-bsicas
Uma nica varivel entra na base (coluna das variveis bsicas)
Uma nica varivel sai da base (coluna das variveis bsicas)
Determinao da varivel que entra na base:
Maior incremento para Z coeficiente mais negativo na eq. 0
Determinao da varivel que sai da base:
Limitao varivel que entra coeficientes positivos da coluna
Aprimoramento iterativo da soluo
1 iterao
Varivel que entra na base maior aumento possvel para Z
coeficiente mais negativo na equao 0 x1
Varivel que sai da base maior restrio ao aumento de x1
menor valor p/ termo independente coeficiente (>0) de x1 x3
varivel ndice
bsica da eq.
coeficiente de:
Z
x1
x2
x3
x4
x5
termo valor da
indep. diviso
x3
x4
x5
3
9
Quadro Simplex: atualizao
Terminologia
linha da varivel que est deixando a base
Linha piv
Coluna piv coluna da varivel que est entrando na base
Nmero piv valor da interseco da linha e coluna pivs
Determinao (dos valores) da nova linha piv
[nova linha piv] =
[antiga linha piv]
[nmero piv]
Determinao (dos valores) das novas linhas
[nova linha i ] = [antiga linha i ] [coef. col. piv] [nova linha piv]
Aprimoramento iterativo da soluo
1 iterao (continuao) atualizao da linha piv
varivel ndice
bsica da eq.
Z
x3
x4
x5
varivel ndice
bsica da eq.
Z
x1
x4
x5
coeficiente de:
Z
x1
x2
x3
x4
x5
coeficiente de:
Z
x1
x2
x3
x4
x5
termo valor da
indep. diviso
3
termo valor da
indep. diviso
3
Aprimoramento iterativo da soluo
1 iterao (continuao) atualizao da linha 0 (Z)
varivel ndice
bsica da eq.
coeficiente de:
Z
x1
x2
x3
x4
x5
termo valor da
indep. diviso
x1
x4
x5
varivel ndice
bsica da eq.
coeficiente de:
Z
x1
x2
x3
x4
x5
termo valor da
indep. diviso
15
x1
x4
x5
Aprimoramento iterativo da soluo
1 iterao (continuao) atualizao da linha 2 (x4)
varivel ndice
bsica da eq.
coeficiente de:
Z
x1
x2
x3
x4
x5
termo valor da
indep. diviso
x1
x4
x5
varivel ndice
bsica da eq.
coeficiente de:
Z
x1
x2
x3
x4
x5
termo valor da
indep. diviso
x1
x4
x5
Aprimoramento iterativo da soluo
1 iterao (continuao) atualizao da linha 3 (x5)
varivel ndice
bsica da eq.
coeficiente de:
Z
x1
x2
x3
x4
x5
termo valor da
indep. diviso
x1
x4
x5
varivel ndice
bsica da eq.
coeficiente de:
Z
x1
x2
x3
x4
x5
termo valor da
indep. diviso
x1
x4
x5
Aprimoramento iterativo da soluo
1 iterao (final) comparao entre os quadros
varivel ndice
bsica da eq.
coeficiente de:
Z
x1
x2
x3
x4
x5
termo valor da
indep. diviso
x3
x4
x5
varivel ndice
bsica da eq.
coeficiente de:
Z
x1
x2
x3
x4
x5
termo valor da
indep. diviso
15
x1
x4
x5
Aprimoramento iterativo da soluo
1 iterao (final) anlise dos resultados
Aumento do valor (termo independente) da funo-objetivo Z
Colunas das variveis bsicas s com 1 ( nica vez) ou 0
Nova iterao? linha 0 (Z) com coeficiente negativo?
varivel que entra na base (na 2 iterao) x2
varivel ndice
bsica da eq.
coeficiente de:
Z
x1
x2
x3
x4
x5
termo valor da
indep. diviso
15
x1
x4
x5
Aprimoramento iterativo da soluo
2 iterao (final) comparao entre os quadros
varivel ndice
bsica da eq.
coeficiente de:
Z
x1
x2
x3
x4
x5
termo valor da
indep. diviso
15
x1
x4
x5
varivel ndice
bsica da eq.
coeficiente de:
Z
x1
x2
x3
x4
x5
termo valor da
indep. diviso
21
x1
x4
0,5
0,5
x2
0,5
0,5
soluo
tima