Ejercicio Resuelto Simplex. Algebra Lineal.

Docente: Francisco Gonzalez V.

A continuacion estudiaremos el siguiente ejercicio:

1. La corporacion CUAK tiene una pequena planta que fabrica 2 produc-tos. Las contribuciones mensuales a las utilidades para los productosson x1 = $10 y x2 = $12 respectivamente. Los productos pasan a travesde los 3 departamentos de produccion de la planta y el tiempo total deproduccion disponible en los respectivos departamentos se muestran enla siguiente tabla:

Depto. x1 x2 Total horas (mes)1 20 horas/hombre 30 horas/hombre 15002 30 horas/hombre 20 horas/hombre 15003 10 horas/hombre 10 horas/hombre 600

Los administradores de la corporacion desean determinar la mezcla deproduccion de los 2 productos que maximicen las utilidades, use meto-do grafico y compruebe usando simplex.

1

Para comenzar, extraeremos la informacion relevante del ejercicio:

1. Puesto que queremos maximizar la ganancia, entonces nuestra funcionobjetivo debera ser la funcion de ganancia. Es decir G(x1, x2) = 10x1 +12x2

2. Solo resta determinar las restricciones, las cuales se encuentran en latabla anterior. De esta tabla se puede decucir que:

20x1 + 30x2 ≤ 150030x1 + 20x2 ≤ 150010x1 + 10x2 ≤ 600

El primer paso es determinar la seccion solucion de este problema. Pa-ra ello, tomamos el sistema de ecuaciones asociado a las restriccionesanteriores (solo cambiar las desigualdades por signos igual), luego con-sideramos sus soluciones en el primer cuadrante, pues las cantidades x1

y x2 solo tienen sentido si son mayores o iguales a 0. Entonces:

20x1 + 30x2 = 150030x1 + 20x2 = 150010x1 + 10x2 = 600

A este sistema lo podemos reducir para obtener el siguiente:

2x1 + 3x2 = 1503x1 + 2x2 = 150x1 + x2 = 60

Podemos resolver este ejercicio mediante el metodo grafico, pero en es-ta ocacion lo resolveremos por el metodo Simplex. Primero tomamosla matriz de coeficientes junto con el vector resultado para construir laprimera tabla, en este caso obtenemos:

2 3 1 0 03 2 0 1 01 1 0 0 1

∣∣∣∣∣∣15015060

2

De esto, podemos ver que la primera tabla quedarıa como sigue:

10 12 0 0 0CB B XB a1 a2 a3 a4 a50 a3 150 2 3 1 0 00 a4 150 3 2 0 1 00 a5 60 1 1 0 0 1

z1 = 0 -10 -12 0 0 0

Puesto que la linea de base tiene numeros negativos, entonces debemoscontinuar el proceso.

El siguiente paso es encontrar el pivote. Para ello notemos que, de losnumeros negativos en la linea de base, el que tiene mayor valor absoluto es-12. Con esto ya sabemos que debemos escoger los numeros de la columnaa2 para dividir a los numeros de la columna resultado XB, y ası nos damoscuenta de que la division que resulta menor (solamente de los positivos) es15030

= 50. Entonces escogemos esa fila, la fila 1.En conclusion, debemos escoger la fila 1 y la columna 2, con lo cual el pivotese encuentra en la interseccion de ambas, es decir que el pivote es el numero 3.

El siguiente paso es tomar la matriz anterior, y mediante operaciones en-tre filas transformar el pivote en 1 y el resto de esa columna (columna a2) enceros. Dentro de todas las opciones, escogeremos las siguientes: 2 3 1 0 0

3 2 0 1 01 1 0 0 1

∣∣∣∣∣∣15015060

Para esta matriz, comenzaremos con F1 − F2. Entonecs obtendremos: −1 1 1 −1 0

3 2 0 1 01 1 0 0 1

∣∣∣∣∣∣0

15060

A continuacion, realizaremos F2 − 2F3, obteniendo ası: −1 1 1 −1 0

1 0 0 1 −21 1 0 0 1

∣∣∣∣∣∣03060

3

La siguiente operacion sera F3 − F1, con lo cual obtendremos: −1 1 1 −1 01 0 0 1 −22 0 −1 1 1

∣∣∣∣∣∣03060

Con esto logramos obtener un pivote igual a 1 y que el resto de esa colum-

na sea nula (solo ceros), pero necesitamos recuperar el resto de las columnasde la matriz identidad. Para ello, usaremos F3 − F2, con lo cual tendremos: −1 1 1 −1 0

1 0 0 1 −21 0 −1 0 3

∣∣∣∣∣∣03030

Continuaremos con F1 + F2, para obtener: 0 1 1 0 −2

1 0 0 1 −21 0 −1 0 3

∣∣∣∣∣∣303030

Finalizaremos con F2 − F3. Con esto logramos obtener la matriz que

buscabamos: 0 1 1 0 −20 0 1 1 −51 0 −1 0 3

∣∣∣∣∣∣30030

Con estos resultados podemos construir una segunda tabla, que serıa co-

mo sigue:

10 12 0 0 0CB B XB a1 a2 a3 a4 a512 a2 30 0 1 1 0 -20 a4 0 0 0 1 1 -510 a1 30 1 0 -1 0 3

z2 = 660 0 0 2 0 6

En esta segunda tabla no hay valores negativos en la linea de base, porlo tanto el proceso a terminado y hemos logrado encontrar el maximo enP = (30, 30).En conclusion, la maxima ganancia es G = 660 y se alcanza vendiendo 30unidades de X1 y 30 unidades de X2

4