Metodo Simplex

Casos especiales en la aplicación del método simplex

Consideraremos casos especiales que pueden presentarse en la aplicación del método simplex, entre los que se encuentran:

1. Degeneración.

2. Opciones óptimas.

3. Soluciones no acotadas.

4. Soluciones inexistentes (o infactibles).

DEGENERACION

En la aplicación de la condición de factibilidad, una coincidencia de la razón mínima se debe descomponer en forma arbitraria para los fines de determinar la variable que sale. Cuando suceda esto una o más veces de las variables básicas, será necesariamente igual a cero en la siguiente iteración. En este caso, decimos que la nueva solución es degenerada.

Ejemplo (Solución óptima degenerada)

Maximizar z = 3x1 +9x2

Sujeto a

x1 + 4x2  8

x1 + 2x2  4

x1,x2  0

Tabla 3-2

Tres rectas cruzan el óptimo. Como éste es un problema bidimensional, se dice que el punto está más que determinado (o sobre determinado), ya que solo necesitamos dos rectas para identificarlo. Por este motivo, concluimos que una de las restricciones es redundante. Desafortunadamente no existen técnicas confiables para identificar restricciones redundantes directamente a partir de la tabla.

Figura 3-4

Desde el punto de vista teórico, la degeneración tiene dos implicaciones. La primera tiene que ver con el fenómeno del ciclaje o reciclaje. Si se observan las iteraciones 1 y 2 de la tabla 3-2, se verá que el valor de la función objetivo no ha mejorado (z=18). Por lo tanto, es posible, en términos generales, que el procedimiento simplex repetiría la misma sucesión de iteraciones, sin mejorar nunca el valor de la función objetivo ni poner fin a los cálculos.

El segundo punto teórico se presenta en el examen de las iteraciones 1 y 2. Ambas iteraciones, pese a diferir en la clasificación de las variables como básicas y no básicas, producen valores idénticos de todas las variables y el valor de la función objetivo, es decir,

x1 = 0, x2 = 2, x3 = 0, x4 = 0, z = 18

Por lo tanto, se genera un argumento relacionado con la posibilidad de suspender los cálculos en la iteración 1 (cuando aparece la degeneración), aunque no es óptima. Este argumento no es válido porque, en general, una solución puede ser temporalmente degenerada.

OPCIONES ÓPTIMAS:

Cuando la función objetivo es paralela a una restricción de enlace (o sea, una restricción que se satisface en el sentido de la igualdad a través de la solución óptima), la función objetivo tomara el mismo valor optimo en más de un punto de solución. Por esta razón reciben el nombre de opciones óptimas.

Ejemplo (Infinidad de soluciones)

Maximizar z = 2x1 + 4x2

Sujeto a

x1 + x2  5

x1 + x2 4

x1, x2 0

En términos algebraicos sabemos que el método simplex es capaz de encontrar soluciones en puntos extremos exclusivamente.

Figura 3-5

Como es de esperarse, el método simplex sólo determina los puntos extremos B y C. Matemáticamente podemos determinar todos los puntos (x1, x2), del segmento de recta BC, como un promedio ponderado no negativo de los puntos B y C. Esto es, dada la relación 0    1 y

B: x1 =0, x2=5/2

C: X1=3, x2=1

Tabla 3-3

SOLUCION NO ACOTADA

En algunos modelos de programación lineal los valores de las variables se pueden aumentar en forma indefinida sin violar ninguna de las restricciones, lo que significa que el espacio de soluciones es no acotado cuando menos en una dirección. Como resultado, el valor de la función objetivo puede crecer (caso de maximización) o de crecer (caso de minimización) en forma indefinida. En este caso decimos que el espacio de soluciones y el valor "óptimo" de la función objetivo son no acotados.

La

...