Slides pl - Degeneração

Degenera¸c˜ao
Aluno: Larissa de Andrade Silva
Universidade Federal do Amazonas - UFAM
Instituto de Ciˆ encias Exatas - ICE
Departamento de Matem´ atica 22 de Julho de 2015

1 / 21

Introdu¸c˜ao

Os PPLs que estudamos s˜ao de grande interesse pr´atico, pois representa v´arios problemas reais tais como problemas de mistura, planejamento, transporte etc., cujas restri¸c˜ oes, ou parte delas, s˜ao definidas por limitantes decorrentes de especifica¸c˜ oes t´ecnicas, demanda, e outros.
O SIMPLEX ´e um m´etodo de responder as PPLs. Estudaremos a
Degenera¸c˜ao, que est´a intimamente ligado a convergˆencia do
SIMPLEX, verificaremos como se origina e como ocorre a
Degenera¸c˜ao.

2 / 21

Degenera¸c˜ao

Defini¸c˜ao - Solu¸c˜ao B´asica Degenerada
Dizemos que uma solu¸c˜ao B´asica ´e DEGENERADA, ou um v´ertice
´e DEGENERADO, quando temos uma solu¸c˜ao b´asica vi´avel onde existe ao menos uma VB (vari´avel b´asica) nula.
Existem Condi¸c˜oes para que ocorra a degenera¸c˜ao:
a) O m´ınimo, calculado pelo crit´erio de sa´ıda do simplex, n˜ao ´e u ´nico.
b) A nova vari´avel b´asica que entra na base substitui uma VB nula.

3 / 21

Degenera¸c˜ao

Defini¸c˜ao - Solu¸c˜ao B´asica Degenerada
Dizemos que uma solu¸c˜ao B´asica ´e DEGENERADA, ou um v´ertice
´e DEGENERADO, quando temos uma solu¸c˜ao b´asica vi´avel onde existe ao menos uma VB (vari´avel b´asica) nula.
Existem Condi¸c˜oes para que ocorra a degenera¸c˜ao:
a) O m´ınimo, calculado pelo crit´erio de sa´ıda do simplex, n˜ao ´e u ´nico.
b) A nova vari´avel b´asica que entra na base substitui uma VB nula.

3 / 21

Degenera¸c˜ao

Defini¸c˜ao - Solu¸c˜ao B´asica Degenerada
Dizemos que uma solu¸c˜ao B´asica ´e DEGENERADA, ou um v´ertice
´e DEGENERADO, quando temos uma solu¸c˜ao b´asica vi´avel onde existe ao menos uma VB (vari´avel b´asica) nula.
Existem Condi¸c˜oes para que ocorra a degenera¸c˜ao:
a) O m´ınimo, calculado pelo crit´erio de sa´ıda do simplex, n˜ao ´e u ´nico.
b) A nova vari´avel b´asica que entra na base substitui