Programación lineal

Casos especiales

- Degeneración
- Solución no factible
- Soluciones optimas alternativas

Degeneración

La degeneración de una solución consiste en que el número de variablesbásicas es menor de las que deben ser. Se presenta cuando una de las variables en la base toma un valor de cero. Generalmente esto no deja de ser un hecho curioso ya que a menudo la degeneración cambia yse elimina durante el resto del proceso de solución.

En casos muy raros la degeneración puede causar que el proceso de solución se cicle sin llegar a encontrar jamás el óptimo. Sin embargo estoscasos son extremadamente raros.

Ejemplo

Max Z = 3x + 9y

S.A.
X + 4y ≤ 8
X + 2y ≤ 4
X, y ≥ 0

1) X + 4y = 8
Si x = 0 y = 8/4 y = 2
Si y = 0 x = 8

2) X + 2y = 4
Si x= 0 y = 4/2 y = 2
Si y = 0 x = 4

Max Z = 3x + 9y + 0S1 + 0S2

S.A.
X + 4y + S1 = 8
X + 2y + S2 = 4
X, y, S1 ,S2 ≥ 0

|Cj | |  |3 |9 |0 |0|

|Cj | |  |3 |9 |0 |0 |
| |  |B |X |Y |S1 |S2 |
|9 |Y |2 |0 |1 |1/2 |-1/2|
|3 |X |0 |1 |0 |-1 |2 |
|Zi |  |18 |3 |9 |3/2 |3/2 |
|Zi - Cj |  |0 |0 |3/2 |3/2 |Solución óptima

X = 0 N – m variables 0
Y = 2 4 – 2 = 2 variables 0
S1 = 0 Hay 3 variables 0
S2 = 0 Hay una degeneración
Z = 18

Soluciones óptimas alternativas

Este caso ocurrecuando la función objetivo es paralela a una restricción no superflua, la cual justamente esta limitando la optimización de Z. En tales casos la función objetivo puede tener el mismo valor óptimo en 2 omás soluciones básicas factibles diferentes.

Ejemplo

Max Z = 4x + 14y

S.A.
2x + 7y ≤ 21
7x + 2y ≤ 21
x, y ≥ 0

1) 2x + 7y = 21
Si X = 0 y = 3
Si y = 0 x = 10.5...