EJEMPLO DE SIMPLEX PARA PROBLEMA DE PROGRAMACIÓN LINEAL CASO DE MAXIMIZAR Prof.: MSc. Julio Rito Vargas Avilés

CONSTRUCCION DE LA TABLA INICIAL DEL MÉTODO SIMPLEX Una vez que el alumno ha adquirido la destreza para transformar cualquier problema de Programación Lineal a forma estándar se enfrenta con el problema de su resolución y el primer paso que debe llevar a cabo es la construcción de la primera tabla del Simplex. Para facilitarle esta tarea, este material muestra de una forma visualmente atractiva, cómo disponer los elementos necesarios para la construcción de dicha tabla inicial, identificando las variables básicas y la solución básica inicial. Se han distinguido los siguientes pasos: determinación del número de filas y columnas de la tabla, rellenado del interior de la tabla con los coeficientes de las variables de holguras, inclusión de los costos o utilidades, identificación de las variables básicas, identificación de los costes básicos y, finalmente, identificación de la solución básica inicial. Sea el siguiente modelo de un PPL en su forma estándar: Max z=40X1 + 60X2

Se trata de un problema de maximización con dos variables y tres restricciones. Sujeto a: Todas las restricciones son menores o iguales. 2X1 + X2 ≤ 70 Para resolver este problema por el método simplex, lo primero que hacemos es convertir las inecuaciones en ecuaciones. Por lo que se X1 + X2 ≤ 40 hará necesario introducir una variable en cada inecuación del X1 + 3X2 ≤ 90 modelo. Esas variables reciben los nombres de “Variables de holguras”. X 1 , X2 ≥ 0 Las variables de holguras que me han permitido convertir las restricciones en ecuaciones, formarán parte de la función objetivo pero con coeficiente “cero” para que no se altere el óptimo el modelo. El modelo quedará de la siguiente forma: Max z=40X1 + 60X2 + 0H1 + 0H2 + 0H3 Sujeto a: 2X1 + X2 + H1 X1 + X2 X1 + 3X2

= 70 + H2

= 40 + H3 = 90

X1, X2, H1, H2, H3 ≥ 0 El Segundo paso es formar la tabla inicial del Simplex. Para lo que debemos explicar la estructura de la tabla del simplex. JULIO RITO VARGAS A.

1

2.1 En la primera fila se deben colocar todos los coeficientes de la función objetivo, en nuestro caso los coeficientes son utilidades. C j= (

40

60

0

0

0)

2.2 La primera columna de la tabla está encabezada por XB, es decir las variables básicas. En la tabla inicial las variables básicas estarán formada por las variables de holgura. XB H1 H2 H3 2.3 La segunda columna de la tabla del simplex es encabezada por los coeficientes de utilidades de las variables básicas, como se indica: CB 0 0 0 2.4 La tercera columna de la tabla del simplex es encabezado por “b” los valores de los lados derechos de las ecuaciones que forman las restricciones. b 70 40 90 2.5 Las columnas 4ta. a la 8va. Son encabezadas por los nombres de las variables del modelo con sus respectivos coeficientes. X1 2 1 1

X2 1 1 3

H1 1 0 0

H2 0 1 0

H3 0 0 1

2.6 La columna novena es el Ratio o cocientes. Ratios 70 40 30 JULIO RITO VARGAS A.

2

2.7. La fila seis corresponde a los Zj es la suma de los CB*Coeficientes de cada variable del modelo. Zj=

(

0

0

0

0

0)

2.8 La fila siete corresponde a los Cj - Zj es la diferencia de los valores de la primera fila y los de la fila seis.

Cj - Zj =(

40

60

0

0

0)

La tabla 1 del Simplex tendrá la estructura que se observa:

TABLA 1 DEL SIMPLEX F1

Cj

40

60

0

0

0

F2

XB

CB

b

X1

X2

H1

H2

H3

Ratios

F3

H1

0

70

2

1

1

0

0

70

F4

H2

0

40

1

1

0

1

0

40

F5

H3

0

90

1

3

0

0

1

30

F6

Zj

0

0

0

0

0

F7

Cj - Zj

40

60

0

0

0

Una vez que la tabla inicial está construid; hemos obtenido la primera solución básica factible del modelo, que es H1=40; H2=60; H3=0; para un Z= 40*0 + 60*0 + 0*70 + 0*40 + 0*90= 0

PROCESO DE ITERACIONES PARA OBTENER EL VALOR ÓPTIMO ¿Cuál es el paso siguiente? Debemos observar los valores del vector Cj - Zj o fila F7, si existe algún o algunos Cj - Zj>0 debemos iniciar lo que llamaremos un proceso de iteración en busca de la solución óptima. Como se puede observar en los Cj - Zj existen dos valores mayores que cero, pero solo debemos elegir uno, el criterio es seleccionar el valor máximo de {40,60}= 60. El valor 60 elegido indica que la variable X2 entrará como variable básica. Eso indica que una de las tres básicas actuales conformada por H1, H2, y H3 deberá salir para dar lugar a la nueva variable. Para saber que variable debe salir se calculan los cocientes de los lados derechos (b) entre los coeficientes de la variable X2 y los resultados los ponemos en la columna última de la tabla que hemos encabezado con la palabra Ratio o razón. Los valores que se obtuvieron son 70, 40, 30 de ellos se elige el mínimo en ese caso será 30. La elección del valor mínimo nos indica que la variable básica que saldrá es H3 porque en esa fila se obtuvo el valor mínimo. JULIO RITO VARGAS A.

3

Ahora procedemos a hacer un conjunto de transformaciones, las que detallaremos con el propósito de que los actuales coeficientes de la variable X2 formen una columna de la matriz identidad tres x tres. Ha podido observar que los actuales coeficientes son 1, 1, y 3. Como 3 es el número pivote (intersección de la columna y fila de las variables seleccionadas) ese valor lo convertiremos en 1 y los otros dos coeficientes en ceros. Es importante indicar que los cambios o transformaciones se deben de ir reflejando en la nueva tabla del Simplex que será la tabla. La F1 no sufrirá ningún cambio en todas las transformaciones que se hagan. En la tabla 2 se debe proceder a remplazar a H3 por X2 en la primera columna y en la segunda columna el respectivo costo o utilidad de la variable X2 que es 60. Las otras dos variables básicas se mantienen iguales con sus costos o utilidades. La fila cinco (F5) de la tabla 1 se divide por 3, y se afectará a las celdas de las columna 3 a la 8. Los resultados se reflejaran en la tabla 2 como se muestra. Los coeficientes de X2 en la fila F3 y F4 que en la tabla 1 son 1 y 1 respectivamente deberán ser cero. Para la cual se deberá hacer los siguientes cálculos:  

La fila F3 de la tabla 1 se restará de fila F5 y el resultado deberá registrarse en la F3 de la tabla 2. Esto es: F3 – F5  F3. Ver resultados en la tabla 2. La fila F4 de la tabla 1 se restará de la fila F5 y el resultado deberá registrarse en la F4 de la tabla 2. Esto es: F4 – F5 F4. Ver resultados en la tabla 2.

Ahora calculamos los Zj de la tabla 2, que como indicamos anteriormente se obtienen de la suma de productos de los CB por los coeficientes de cada variable. Como se puede ver en la fila F6 de la tabla 2. Para obtener los Cj - Zj solo restamos los coeficientes de la primera fila (F1) de la tabla 2 de los valores Z de la fila F6, los resultados se muestran en la fila F7 de la tabla 2.

TABLA 2 DEL SIMPLEX F1

Cj

40

60

0

0

0

CB

b

X1

X2

H1

H2

H3

Ratios

H1

0

40

1.667

0

1

0

-0.333

24

F4

H2

0

10

0.667

0

0

1

-0.333

15

F5

X2

60

30

0.333

1

0

0

0.333

90

0

0

20

0

0

-20

F2

XB

F3

F6

Zj

20

F7

Cj - Zj

20

0

Ahora hemos obtenido la segunda solución b{asica factible del modelo, que es: H1=0; H2=0; X2=60; para un Z== 40*0 + 60*30 + 0*40 + 0*10 + 0*0= 1800.

JULIO RITO VARGAS A.

4

¿Es ese valor el óptimo o no? La respuesta a la pregunta es NO, porque podemos observar que en la fila F7 de la tabla 2 hay Cj - Zj >0, por lo que todavía no hemos llegado al óptimo es decir debemos volver a iterar. Ahora el valor máximo de los Cj - Zj >0 solo es 20, eso indica que la variable que entrará a las básicas será X1. Para conocer la variable que debe salir de las básicas, se deben obtener los cocientes de los lados derechos o (b) sobre los coeficientes de X1. Los resultados son 24, 15, y 90. Como lo puede ver en la columna Ratio de la tabla 2. De los tres valores seleccionamos el mínimo, que corresponde a 15. Por lo que la variable que sale es H2. El número pivote es 2/3 o 0.667. Ese valor lo transformaremos en 1. Multiplicándolo por su reciproco 3/2. Los resultados se mostrarán en la tabla 3 fila F4. Se actualiza la columna de las variables básicas XB incorporando a X1 en sustitución de H2 y actualizamos el CB de la nueva variable básica que hemos incorporado, como se muestra en la tabla 3. Los coeficientes de la columna de X1 (tabla 2) en la F3 y F5 son diferentes de cero, por lo que debemos transformar esas filas de manera que esos coeficientes sean cero, dado que esa columna será parte de la matriz identidad. Para lograr eso procederemos de la siguiente manera: 



La fila F3 de la tabla 2 menos los 5/3 por la fila F4 de la tabla 3, el resultado debe quedar en la fila F3 de la tabla 3. Esto es: F3 – 5/3*F4  F3. Ver los resultados en la fila F3 de la tabla 3. La fila F5 de la tabla 2 menos 1/3 por la fila F5 de la tabla 3, el resultado debe quedar en la fila F5 de la tabla 3. Esto es: F5 – 1/3*F4 F5. Ver los resultados en la fila F5 de la tabla 3.

Ahora calculamos los Zj de la tabla 3, que como indicamos anteriormente se obtienen de la suma de productos de los CB por los coeficientes de cada variable. Como se puede ver en la fila F6 de la tabla 3. Para obtener los Cj - Zj solo restamos los coeficientes de la primera fila (F1) de la tabla 3 de los valores Z de la fila F6, los resultados se muestran en la fila F7 de la tabla 3. F1 F2 F3 F4 F5 F6 F7

XB H1 X1 X2

TABLA 3 DEL SIMPLEX Cj 40 60 CB b X1 X2 0 15 0 0 40 15 1 0 60 25 0 1 Zj 40 60 Cj - Zj 0 0

0 H1 1 0 0 15 -15

0 H2 -2.5 1.5 -0.5 30 -30

0 H3 0.5 -0.5 0.5 10 -10

Ratios

JULIO RITO VARGAS A.

5

Ahora hemos obtenido la tercera solución básica factible: H1=15; X1=15; X2=25; para un Z= 40*15 + 60*25 + 0*15+ 0*0 + 0*0= 2100. ¿Es ese valor el óptimo o no? La respuesta a la pregunta es SI, hemos alcanzado el óptimo, podemos observar que en la fila F7 de la tabla 3 no hay ningún Cj - Zj >0, por lo que todos los valores o son ceros o negativos. Es decir la última solución básica factible es la SOLUCIÓN ÓPTIMA. En forma resumida sería:

La solución óptima es: X1=15; X2=25; para un Z= 40*15 + 60*250 2100.

JULIO RITO VARGAS A.

6