Veamos el siguiente problema de programación lineal
Se agregan dos variables de holgura 
y 
, y resolvemos usando el método simplex
La regla 1 muestra que esta es una solución óptima. Cabe
destacar que la variable 
que no está en la base aparece con un valor de
cj - zj igual a 0. Si aumentamos el valor de la variable
(su valor actual es 0) , eso no cambiará el valor de z. Aumentar
el valor de
produce cambios en las otras variables, al pivotear, es decir vamos a obtener
una solución básica diferente pero que tiene el mismo valor
de la función objetivo z=2.
.
Fijese que ahora el coeficiente de cj-zj para la variable
es 0. Si entramos
y pivoteamos recuperariamos la solución anterior!
Degeneración
Resolvamos el problema usando el método simplex. En el tableau
inicial podemos elegir 
como la variable que entra (Regla 1)
Note que esta solución básica tiene una variable
básica
cuyo valor es cero!. Cuando esto ocurre decimos que la solución
básica está degenerada . Qué sucede si continuamos
iterando?. Por la Regla 1
entra a la base. Por la Regla 2 hay que elegir entre 
y 
. El menor es 0, entonces pivoteando se obtiene
Es decir, obtenemos exactamente la misma solución!. La única
diferencia es que hemos intercambiado los nombres de las variables no-básicas
con las de una variable básica que degenera el tableau. La Regla
1 nos dice que no estamos en la solución óptima. Si continuamos
deberemos ingresar
obteniendo el siguiente tableau:
Óptimo No-acotado
Por el método simplex se obtiene:
La Regla 1 elige
para entrar a la base, pero no se puede calcular el bi/aij,
ya que no hay aij mayores que cero en la columna de
.
Asi el problema es no-acotado.
Problemas No-factibles.
Las restricciones cubren espacios de búsqueda diferentes y no hay una región de factibilidad para el problema global.
Propiedades de los problemas de programación lineal
Un problema de programación lineal tiene tres posibilidades: ser no-factible, ser no-acotado o tener una solución óptima.
Si tiene una solución óptima se denomina una solución
básica óptima. Recuerde que el número de
variables en la base es igual al número de restricciones del problema,
digamos m. Asi si el total de variables es igual a n, y es mayor que m,
a lo más m de esas variables pueden tener un valor positivo en la
solución básica óptima.
Answer:
(a) The solution is 
, 
, objective 15. It is optimal since cost row is all at least 0.
(b) It is not unique (since
has reduced cost 0 but is not basic). Alternative found by pivoting in
(question could have asked for details on such a pivot) for solution 
, 
, objective 15.