Metodo Simplex

MÉTODO SIMPLEX CON RESTRICCIONES > ó =

Existen problemas lineales que no tienen una solución óptima única, sino que al contrario, tienen un número infinito de soluciones. Para detectar una solución múltiple en la tabla óptima, se deberá tener al menos una variable con su Zj-Cj=0 no básica. Ejemplo: Modelo estándar Max z=3x1+2x2

x1+x3=4

2x2+x4=12

3x1+2x2+x5=18

x1,x2,x3,x4,x5>=0

X1 X2 X3 X4 X5 SOL

Zj-Cj 0 0 0 0 1 18

X1 1 0 1 0 0 4

X4 0 0 3 1 -1 6

X2 0 1 -3/2 0 1/2 3

Solución x1=4 x2=3 x4=6 x3=x5=0 z=18

X3=0 es variable no básica por lo tanto se tiene una solución múltiple y para obtener alguna otra solución se deberá iterar tomando como variable de entrada en Zj-Cj=0

Variable degenerada

Una variable degenerada es una variable básica que vale 0. Gráficamente esto puede ocurrir cuando más de dos rectas se intersequen en el mismo punto.

Base

Conjunto de variables básicas. En el ejemplo anterior, la base es {X3, X4, X5, X6}

Variable no restringida

Es aquella que puede tomar toda clase de valores positivos, cero y negativos puede escribirse como la diferencia de dos variables no-negativas.

Ejemplo:

Sea x1 una variable no restringida, entonces:

x1=x2-x3

donde x2>=0, Nótese que si x2>x3, eso implica que x1>0: si x2=x3, entonces x1=0: si x2<x3, se tiene que x1<0.

Función objetivo:

Define la efectividad del modelo como función de las variables de decisión. Ejemplo: Max z= 5x1+2x2

Variables de entrada

Estas suelen encontrarse en un criterio que se conoce como “Condición de optimalidad”, en un modelo, ya sea de optimización o minimización, y se refiere a la variable no básica en el renglón “z” con el coeficiente más negativo, si se trata de una maximización, o el coeficiente mas positivo, si se trata de una minimización, la cual, en el la tabla de solución anterior, a excepción de la primer tabla, esta variable era una variable básica.

'Variables de salida

Esta variable es un punto extremo que se encuentra en un criterio conocido como “Condición de factibilidad”, en un modelo, ya sea de optimización o minimización, y se refiere a la variable básica asociada con la mínima razón no negativa con el coeficiente más negativo, si se trata de una maximización, o el coeficiente mas positivo, si se trata de una minimización, la cual, en el la tabla de solución siguiente, pasará a ser variable no básica.

Variables básicas Variables no básicas Variable de entrada Variable de salida

A X3, X4, X5, X6 X1, X2 X1 X2

B X3, X4, X5, X1 X6, X2 X2 X3

C X2, X4, X5, X1 X6, X3 X6 X4

D X2, X6, X5, X1 X4, X3 X3 X1

E X2, X6, X5, X3 X4, X1 X4 X2

Solución degenerada

La degeneración ocurre cuando en alguna iteración del método simplex existe un empate en la selección de la variable que sale. Este empate se rompe arbitrariamente. En este caso decimos

...