Método Simplex

Es un procedimiento sistemático y eficiente para encontrar y probar soluciones situadas en los puntos extremos de la región de soluciones factibles en un problema de programación lineal (PPL).

Principales características

Algoritmo eficiente y rápido para encontrar el óptimo.

Determina la solución óptima sin evaluar todos los puntos extremos factibles.

Capaz de detectar si existen múltiples soluciones, si la solución no está acotada, y si existe incompatibilidad de restricciones.

Ejemplo de PPLPara ilustrar el desarrollo del método simplex, consideremos el problema de los bolsos y mochilas presentado anteriormente, cuyo modelo matemático se expresa de la siguiente manera:

MAX Z = 3 x1 + 5 x2

s.a. x1 4

2 x2 12

3 x1 + 2 x2 18

x1 , x2 0

Hemos visto que este modelo matemático tiene la forma de un problema de programación lineal (PPL).

Ejemplo de PPLEl modelo anterior de PPL se puede expresar gráficamente de la siguiente manera, donde la recta en azul representa la FO en el punto óptimo:

62 4

6

4

2

x1

x2

x2 = 6

x1 = 4

3 x1 + 2 x2 = 18

Región Factible

3 x1 + 5 x2 = 36

Variables de Holgura

El método Simplex requiere que las restricciones sean ecuaciones. Para convertir cada restricción del tipo () en (=) se debe agregar una nueva variable positiva llamada variable de holgura (hi).

A las variables hi se les denomina de holgura porque representan la cantidad no utilizada del recurso i , es decir, es la diferencia entre la cantidad disponible del recurso i y la cantidad utilizada.

Variables de HolguraSi agregamos las variables de holgura al ejemplo anterior, obtenemos el siguiente modelo matemático:

MAX Z = 3 X1 + 5 X2

s.a. X1 + h1 = 4

2 X2 + h2 = 12

3 X1 + 2 X2 + h3 = 18

X1 , X2 0 h1, h2, h3, 0

Modelo PPL

El modelo matemático anterior es equivalente al siguiente sistema de ecuaciones, para las cuales se debe encontrar la solución que entregue el mayor valor para la variable Z, y se sabe que todas las otras variables deben ser mayores que cero:

Z - 3 X1 - 5 X2 = 0

X1 + h1 = 4

2 X2 + h2 = 12

3 X1 + 2 X2 + h3 = 18

Modelo PPL

En este caso existen 6 incógnitas (Z,X1,X2,h1,h2,h3) y sólo 4 ecuaciones.

Luego, para obtener una solución, se debe:

asignar un valor a 2 variables, y encontrar el valor de las otras 4 variables, resolviendo

el sistema de ecuaciones resultante.

Modelo PPL

Supongamos que en el sistema de ecuaciones anterior se asigna el valor cero a X1 y X2 (X1=X2=0), entonces se obtienen las siguientes ecuaciones:

Z = 0

h1 = 4

h2 = 12

h3 = 18

De donde se puede obtener en forma directa el valor de las otras variables.

Modelo PPL

Para el problema anterior, existen muchas alternativas para elegir las variables a las cuales les asignamos un valor, y para elegir el valor de estas variables.

Cuando se asigna un valor de cero a las variables en exceso (respecto al número de ecuaciones), y se obtiene el valor de las variables restantes, la solución obtenida se llama Solución Básica.

En la representación gráfica del problema, esta solución básica (Z,X1,X2,h1,h2,h3)=(0,0,0,4,12,18) corresponde al origen (X1=X2=0), y el valor de la FO es cero. El valor de las variables de holgura es igual a la disponibilidad total de recurso, porque cuando las variables de decisión son cero, no se consumen recursos.

Solución básica

Cuando se tiene N variables y n ecuaciones (n<N), entonces una solución básica está compuesta por:

N - n variables = 0 (var. no básicas) n variables > 0 (var. básicas)

Forma canónica

En el sistema de ecuaciones anterior, al hacer X1=X2=0, se obtuvieron en forma inmediata los valores de las otras variables (Z,h1,h2,h3).

Esto se debe a que las ecuaciones estaban en forma canónica para Z, h1, h2 y h3.

Siempre es posible llevar un sistema de ecuaciones a forma canónica, realizando operaciones algebraicas con las ecuaciones.

Forma canónica

Ejemplo:

Para el sistema de ecuaciones anterior, expresarlo en forma canónica para Z, X2, h1, h3, suponiendo que ahora X1, h2 valen cero.

Z - 3 X1 - 5 X2 = 0 (1)

X1 + h1 = 4 (2)

2 X2 + h2 = 12 (3)

3 X1 + 2 X2 + h3 = 18 (4)

Forma canónicaPara ello:

1 Se multiplica la ecuación (3) por 1/2.2 Se remplaza la ecuación (1) por (1) + 5 x (1 modificada).3 Se reemplaza la ecuación (4) por (4) - 2 x (1 modificada).

Con lo cual se obtiene lo siguiente:

Z - 3 X1 + 5/2 h2 = 30

X1 + h1 = 4

X2 + 1/2 h2 = 6

3 X1 - h2 + h3 = 18

Forma canónica

En el ejemplo anterior, se ha cambiado la solución, porque se ha cambiado una variable básica por una no básica, según se detalla a continuación:

Antes Después

Var Básicas (BASE) Z, h1, h2, h3 Z, h1, X2, h3

Var No básicas X1, X2 X1, h2

En la situación anterior, se dice que:

La variable X2 entró a la base (tomó un valor > 0)

La variable h2 salió de la base (tomó un valor = 0)

Ejemplo de PPLEn el modelo anterior de PPL, este cambio de solución básica equivale a moverse desde el punto (0,0) al punto (0,6) de la gráfica.

(Z,X1,X2,h1,h2,h3)=(0,0,0,4,12,18) ---> (Z,X1,X2,h1,h2,h3)=(30,0,6,4,0,18)

62 4

6

4

2

x1

x2

x2 = 6

x1 = 4

3 x1 + 2 x2 = 18

Región Factible

3 x1 + 5 x2 = 36

Ejemplo de PPLEs importante notar que cada vértice corresponde a una solución básica, y que las variables no básicas corresponden a las rectas que definen cada vértice.

Vértice Solución

(0,0) (0,0,0,4,12,18)

(0,6) (30,0,6,4,0,18) , y de igual forma para cada vértice

Vértice Vars No Básicas Rectas correspondiente

(0,0) X1 , X2 X1= 0 , X2 = 0

(0,6) X1 , h2 X1= 0 , 2 X2 + h2 = 12

Ejemplo de PPL

Pregunta:

Cuál es la solución básica y las rectas de definición correspondientes al vértice (2,6) ?

62 4

6

4

2

x1

x2

x2 = 6

x1 = 4

3 x1 + 2 x2 = 18

Región Factible

3 x1 + 5 x2 = 36

Fundamentos del método simplex

1 Los vértices de la región factible se llaman soluciones factibles en el vértice (FEV).

2 Si el problema es acotado (existe una región factible) entonces existe un número finito de soluciones FEV.

3 Si el problema es acotado, existe al menos una solución óptima factible que corresponde a una solución FEV.

Fundamentos del método simplex

4 Si una solución FEV es mejor (o igual) que todas las soluciones FEV adyacentes, entonces esta solución es óptima.

5 Las soluciones FEV siempre corresponden a una solución básica para el sistema de ecuaciones obtenido al agregar las variables de holgura al modelo de programación lineal.

Método simplex

Consiste en avanzar hacia el óptimo a través de los puntos extremos (vértices), en el sentido en que la función objetivo (Z) aumenta.

Para ello, utiliza una solución básica factible, evalúa si es óptima, y si no lo es, extrae una variable de la base y se introduce otra, de manera que aumente el valor de la función objetivo.

Método simplexINICIALIZACION

SOLUCION OPTIMA ? FIN

ITERACION:

1 DEFINIR VARIABLE QUE ENTRA (hacia dónde)

2 DEFINIR VARIABLE QUE SALE (hasta dónde)

3 DETERMINAR NUEVA SOLUCION BASICA

SI

NO

Presentación tabular Para trabajar se utiliza un cuadro resúmen llamado “Tableau”.

cm

zm-cm

hm

..

..

..

c2

z2-c2

h2

cn

zn-cn

xn

c2

z2-c2

x2

c1..c1

z1-c1..z1-c1Z

h1..x1XBCBVB

Max/Min

Variables de Decisión Variables de Holgura

Coeficientes en la Función Objetivo

Presentación tabular Para trabajar se utiliza un cuadro resúmen llamado “Tableau”.

cm

zm-cm

hm

..

..

..

c2

z2-c2

h2

cn

zn-cn

xn

c2

z2-c2

x2

c1..c1

z1-c1..z1-c1Z

h1..x1XBCBVB

Max/Min

Coeficientes de las variables en las ecuaciones

“Lado derecho” de las ecuaciones

Coeficientes en la FO de las variables básicas actuales

Presentación tabular Para trabajar se utiliza un cuadro resúmen llamado “Tableau”.

cm

zm-cm

hm

..

..

..

c2

z2-c2

h2

cn

zn-cn

xn

c2

z2-c2

x2

c1..c1

z1-c1..z1-c1Z

h1..x1XBCBVB

Max/Min

Variables básicas de la solución actual

Ejemplo de PPLEn la transparencia siguiente se muestra el problema de los bolsos y mochilas, expresado en le formato tabular (este cuadro corresponde al tableau inicial para el método simplex).

MAX Z = 3 X1 + 5 X2

s.a. X1 + h1 = 4

2 X2 + h2 = 12

3 X1 + 2 X2 + h3 = 18

X1 , X2 0 h1, h2, h3, 0

Ejemplo PPL en formato tabular