1

Degenerescência, ciclagem e

eficiência do Simplex

Prof.: Eduardo Uchoa

http://www.logis.uff.br/~uchoa/POI

2

Problema do Mix de Produção

xmad

5

xal

3,2

4,8

Z = 41,6

Modelo: maximizar z = 4,0 xmad

+ 6,0 xal

Sujeito a

1,5 xmad

+ 4,0 xal≤ 24

3,0 xmad

+ 1,5 xal≤ 21

1,0 xmad

+ 1,0 xal≤ 8

xmad

, xal≥ 0

2 3 5

4 3 5

1 3 5

3 5

24 2 3

5 5 5

21 3 39

5 5 10

16 2 8

5 5 5

208 4 14

5 5 5

x x x

x x x

x x x

z x x

= − +

= − +

= + −

= − −

Solução ótima:

x1 = 3,2

x2 = 4,8

Lucro = 41,6

Obs.:

x4 = 4,2 (folga da montagem)

3

Problema do Mix de ProduçãoAlterando a 2ª restrição:

Modelo: maximizar z = 4,0 xmad

+ 6,0 xal

Sujeito a

1,5 xmad

+ 4,0 xal≤ 24

1,0 xmad

+ 3,0 xal≤ 18

1,0 xmad

+ 1,0 xal≤ 8

xmad

, xal≥ 0

xmad

5

xal

4

Problema do Mix de Produção

Introduzir as variáveis de folga

maximizar z = 4,0 x1 + 6,0 x2

Sujeito a

1,5 x1 + 4,0 x2 + 1 x3 = 24

1,0 x1 + 3,0 x2 + 1 x4 = 18

1,0 x1 + 1,0 x2 + 1 x5 = 8

x1 , x2 , x3 , x4 , x5 ≥ 0

5

Problema do Mix de Produção

Montar o 1o dicionário isolando as variáveis de folga

3 1 2

4 1 2

5 1 2

1 2

324 4

2

18 3

8

4 6

x x x

x x x

x x x

z x x

= − −

= − −

= − −

= +

6

Problema do Mix de Produção

Qual variável vai sair da base?

3 1 2

4 1 2

5 1 2

1 2

324 4

2

18 3

8

4 6

x x x

x x x

x x x

z x x

= − −

= − −

= − −

= +

2

2

24 18 8min , ,

4 3 1

6

x

x

=

=

7

Problema do Mix de Produção

Qual variável vai sair da base?

3 1 2

4 1 2

5 1 2

1 2

324 4

2

18 3

8

4 6

x x x

x x x

x x x

z x x

= − −

= − −

= − −

= +

2

2

24 18 8min , ,

4 3 1

6

x

x

=

=

x3 e x4 empataram no critério de seleção da

variável que sairá da base.

Logo, existirão duas opções para o próximo dicionário.

x2 entra na base

8

Problema do Mix de Produção

1ª Opção: se x2 entrar e x3 sair da base:

2 1 3

4 1 3

5 1 3

1 3

3 16

8 4

1 30

8 4

5 12

8 4

7 336

4 2

x x x

x x x

x x x

z x x

= − −

= + +

= − +

= + −

9

Problema do Mix de Produção

2ª Opção: se x2 entrar e x4 sair da base:

3 1 4

2 1 4

5 1 4

1 4

1 40

6 3

1 16

3 3

2 12

3 3

36 2 2

x x x

x x x

x x x

z x x

= − +

= − −

= − +

= + −

10

Problema do Mix de Produção

2ª Opção: se x2 entrar e x4 sair da base:

3 1 4

2 1 4

5 1 4

1 4

1 40

6 3

1 16

3 3

2 12

3 3

36 2 2

x x x

x x x

x x x

z x x

= − +

= − −

= − +

= + −

Nas duas opções, tem-se uma solução degenerada,

onde uma variável básica

tem valor zero na solução

do dicionário.

11

Problema do Mix de Produção

Continuando na 2ª opção

3 1 4

2 1 4

5 1 4

1 4

1 40

6 3

1 16

3 3

2 12

3 3

36 2 2

x x x

x x x

x x x

z x x

= − +

= − −

= − +

= + −

12

Problema do Mix de Produção

Continuando na 2ª opção

3 1 4

2 1 4

5 1 4

1 4

1 40

6 3

1 16

3 3

2 12

3 3

36 2 2

x x x

x x x

x x x

z x x

= − +

= − −

= − +

= + −

1

1

entra na base

0 6 2min , ,

1 6 1 3 2 3

x

x

=

13

Problema do Mix de Produção

Continuando na 2ª opção

3 1 4

2 1 4

5 1 4

1 4

1 40

6 3

1 16

3 3

2 12

3 3

36 2 2

x x x

x x x

x x x

z x x

= − +

= − −

= − +

= + −

1

1

1

3

entra na base

0 6 2min , ,

1 6 1 3 2 3

0

sai da base

x

x

x

x

=

=

14

Problema do Mix de Produção

O novo dicionário:

1 3 4

2 3 4

5 3 4

3 4

0 6 8

6 2 3

2 4 5

36 12 14

x x x

x x x

x x x

z x x

= − +

= + −

= + −

= − +

15

Problema do Mix de Produção

1 3 4

2 3 4

5 3 4

3 4

0 6 8

6 2 3

2 4 5

36 12 14

x x x

x x x

x x x

z x x

= − +

= + −

= + −

= − +

Houve a mudança de base, mas a solução tem o mesmo valor da solução dada pelo dicionário anterior. Quando isso ocorre, tem-se uma iteração degenerada do Simplex.

16

Problema do Mix de Produção

Continuando:

1 3 4

2 3 4

5 3 4

3 4

0 6 8

6 2 3

2 4 5

36 12 14

x x x

x x x

x x x

z x x

= − +

= + −

= + −

= − +

4

4

4

5

entra na base

6 2min ,

3 5

2 5

sai da base

x

x

x

x

=

=

17

Problema do Mix de Produção

1 3 5

2 3 5

4 3 5

3 4

16 2 8

5 5 5

24 2 3

5 5 5

2 4 1

5 5 5

208 4 14

5 5 5

x x x

x x x

x x x

z x x

= + −

= − +

= + −

= − −

Este dicionário dá a solução

ótima do problema com:

x1 = 16/5

x2 = 24/5

z = 208/5

18

Degenerescência em PL

� Definição: Um PL é degenerado se há pelo

menos uma solução básica viável com uma

variável básica com valor zero (=0). Essa

solução é dita degenerada.

� Ao longo do Simplex, a degenerescência surge

quando há empate na seleção da variável que

sairá da base. A iteração seguinte pode uma

iteração degenerada.

19

Consequencias da Degenerescência

� Se um PL possui muitas soluções degeneradas,

o método Simplex pode demorar mais iterações

do que o usual para chegar na solução ótima.

� Em certos casos extremamente raros, pode

ocorrer ciclagem, o Simplex pode visitar uma

sequencia de soluções degeneradas (todas de

mesmo custo) que se repetem infinitamente.

� Nesse caso, o método não chegaria na solução ótima.

20

Ciclagem no método Simplex

� Não é fácil construir um PL que possa fazer o

Simplex ciclar.

21

Exemplo de um PL que pode ciclar

1 2 3 4

1 2 3 4

1 2 3 4

3

1 2 3 4

3 1min 20 6

4 2

1s. a 8 9 0

4

1 112 7 0

2 2

1

, , , 0

x x x x

x x x x

x x x x

x

x x x x

− + − +

− − + ≤

− − + ≤

≤

≥

22

Evitando a ciclagem

� Existem algumas escolhas dentro do método

Simplex que garantem que a ciclagem nunca vai

ocorrer. A mais simples é a Regra de Bland:

� Dentre as variáveis que podem entrar na base, escolha sempre a com menor índice; dentre as variáveis que podem sair da base também escolha a com menor índice

� Essas regras só precisam ser ativadas após

uma longa sequencia de iterações

degeneradas, quando se desconfia que está

ocorrendo ciclagem.

23

Eficiência do método Simplex

� O número de soluções básicas de um PL é finito

� Tomando um pouco de cuidado para não

ocorrer ciclagem, cada iteração do Simplex

visita uma solução básica diferente

O método Simplex sempre termina em um número finito de iterações

24

Eficiência do método Simplex

� Entretanto, o número de soluções básicas de

um PL pode ser muito grande:

� Existem alguns PLs criados artificialmente em

que o Simplex visita todas as soluções básicas

antes de chegar no ótimo!

( )

!

! !

n n

m m n m

=

−

25

Na prática o método Simplex é muito

eficiente!

� Na maioria dos casos, o Simplex visita menos

do que 2m soluções

� Quando o PL é muito degenerado isso pode

chegar a 10m.

� De qualquer forma, com software adequado,

problemas com milhões de variáveis/restrições

são resolvíveis em um notebook.

26

OBSERVAÇÃO

Este material refere-se às notas de aula do curso

TEP117 (Pesquisa Operacional I) da Universidade

Federal Fluminense (UFF) e foi criado a partir das

notas do Prof. Rodrigo A. Scarpel do ITA

(www.mec.ita.br/~rodrigo) e não pode ser

reproduzido sem autorização prévia de ambos os

autores. Quando autorizado, seu uso é exclusivo

para atividades de ensino e pesquisa em

instituições sem fins lucrativos.