Capítulo 5 Método Simplex

Transcripción

1 Capítulo 5 Método Simplex Cj M 0 0 V.B. b X1 X2 X3 X4 X5 X6 X7 5 X1 13/ /15 4/15 7/45 4/45 NO 3 X3 14/ /15-1/15 2/45 14/45 70/3-2 X2 1/ /15 3/15-2/15 1/15 NO Zj - Cj 101/ /15 M+11/15 53/45 56/45 Introducción El método algebraico es muy dispendioso, en razón a que trabaja con todos los datos de las ecuaciones, para mejorar éste aspecto se creó el método simplex cuya gran virtud es su sencillez, método muy práctico, ya que solo trabaja con los coeficientes de la función objetivo y de las restricciones. Ilustraremos su funcionamiento mediante un ejemplo, pero previamente mostraremos las reglas de decisión para determinar la variable que entra, la que sale, la gran M, y cómo determinar que estamos en el óptimo; Todas éstas reglas de decisión fueron deducidas del método algebraico, solamente que aquí se han acomodado para ser usadas en el tipo de tablero simplex que se usará. Criterio de decisión Maximizar Minimizar Gran M en la función objetivo - MXj +MXj Variable que entra Variable que sale La más negativa de los Zj - Cj La más positiva de los Zj - Cj La menos positiva de los, Siendo a > 0, de lo contrario no restringe La menos positiva de los, Siendo a > 0, de lo contrario no restringe a la variable que entra Solución óptima Cuando todos los Zj Cj > 0 Cuando todos los Zj Cj < 0 Adicionalmente se presentan las siguientes notas a tener en cuanta: 83

2 Si en el tablero simplex de la solución óptima queda al menos una variable de Super avit ó artificial dentro de las variables básicas, con un valor > 0, el problema no tiene solución, esto quiere decir que al menos existen dos restricciones excluyentes, por lo tanto no existe área de soluciones factible y menos una solución, en éste caso se debe revisar la formulación del problema. Si al escoger la variable que sale, ninguna de las variables básicas restringe el crecimiento de la variable no básica escogida para entrar, el problema tiene solución indeterminada y se debe revisar la formulación en busca de una nueva restricción que no se tuvo en cuenta en la formulación inicial. Si en el tablero simplex del óptimo, al menos una de las variables no básicas tiene coeficiente cero (0) en la función objetivo, esto es su Zj Cj = 0, el problema tiene múltiples soluciones y se nos está ofreciendo una de ellas. Ejemplo 1 Maximizar Z = X 1 + X 2 5X 1 + 3X 2 < 15 3X 1 + 5X 2 < 15 Xj > 0 ; j = 1, 2 Todo problema de programación lineal que se formule de la forma Maximice, con todas sus restricciones < y con la condición de no negatividad, se le llama Forma Estándar ó Forma Normal Aquí, al igual que en el método algebraico, debemos conseguir una solución básica factible, empleando las variables de holgura y/o artificiales, quedando el sistema de ecuaciones así: Maximizar Z = X 1 + X 2 5X 1 + 3X 2 + X 3 = 15 3X 1 + 5X 2 + X 4 = 15 Xj > 0 ; j = 1,2,3,4 Las variables básicas son X 3 y X 4 y por su puesto en la función objetivo Z. Este ejercicio es el ejemplo 1 del capitulo de método algebraico. Compare los resultados entre los dos métodos. A continuación construimos la siguiente tabla: Cj V.B. b X 1 X 2 X 3 X 4 0 X X Zj - Cj El valor de la función objetiva Z, se encuentra frente a la casilla de Zj Cj, en éste caso vale cero (0) y se calcula multiplicando el vector fila (en la tabla es la columna inmediatamente anterior a la de las variables básica V.B.) que contiene los coeficientes de 84

3 las variables básicas en la función objetiva original por el vector columna de los términos independientes b C XB = Vector fila de los coeficientes en la función objetivo original de las variables básicas actuales, sus valores se encuentran en la primera columna del tablero. b = Vector columna de los términos independientes de las restricciones, que al mismo tiempo son los valores de las variables básicas actuales, sus valores se encuentran bajo la columna denominada b 15 C XB = (0,0) ; b = (0,0) 15 = (0)(15) + (0)(15) = Cj V.B. b X 1 X 2 X 3 X 4 0 X X Zj - Cj El valor de los Zj Cj se calcula multiplicado el vector fila C xb por el vector apuntador a j de la columna de la variable j-ésima, menos el Cj, esto es: Zj Cj = C xb a j Cj ; Los cálculos se efectúan así: 5 Z 1 C 1 = C xb a 1 C 1 = (0,0) - 1 = (0)(5)+(0)(3) 1 = Z 2 C 2 = C xb a 2 C 2 = (0,0) - 1 = (0)(3)+(0)(5) 1= Z 3 C 3 = C xb a 3 C 3 = (0,0) - 0 = (0)(1)+(0)(0) 0 = Z 4 C 4 = C xb a 4 C 4 = (0,0) - 0 = (0)(0)+(0)(1) 0 = 0 1 Cj V.B. b X 1 X 2 X 3 X 4 a > 0 0 X /5 = 3 (1/5) 0 X /3 = 5 Zj - Cj Variable que entra X 1 Variable que sale X 3 Recuerde que la columna de se calcula, siempre y cuando el denominador sea a > 0 ; de lo contrario la variable básica respectiva no restringe el valor de la variable escogida para entrar, los valores de a, están en el respectivo vector apuntador de la variable j-ésima 85

4 escogida para entrar, en ésta iteración son 5 y 3 y el calculo respectivo 15/5 = 3 y 15/3 = 5; Lo que significa que la variable básica X 3 restringe el crecimiento de la variable que entra X 1 hasta 3 (no la deja tomar valores superiores a 3) y la variable básica X 4 restringe el crecimiento de la variable que entra X 1 hasta 5 (no la deja tomar valores superiores a 5). Por supuesto la variable básica que restringe más el crecimiento de la variable que entra X 1 es X 3 por lo tanto es la variable básica escogida para salir. La fila de la variable básica escogida para salir se divide por el elemento que se encuentra en la intersección de dicha fila con la columna de la variable que entra, la fila resultante es la fila pivote y se coloca en un nuevo tablero, desde el que se suman múltiplos de la fila pivote a las demás filas del tablero anterior de tal forma que se eliminen de cada una de ellas la variable escogida para entrar, en nuestro caso X 1, este procedimiento se denomina, hacer un uno (1) en la intersección y el resto de la columna ceros (0), por lo tanto en dicha columna aparecerá un vector unitario, el procedimiento se repite en cada iteración, hasta que todos los Zj Cj sean mayores ó iguales a cero en el caso de maximizar ó menores ó iguales a cero en el caso de minimizar. A continuación se muestran todas las iteraciones y en cada fila los valores por los cuales fueron multiplicadas para ser sumadas a otras filas, ello se expresa como sumar múltiplos de una fila a otra. Fíjese que se suman múltiplos de las restricciones a la función objetivo para eliminar las variables básicas de ella. Cj V.B. b X 1 X 2 X 3 X 4 a > 0 1 X /5 1/5 0 5 (-3) 0 X /5-3/5 1 15/8 = 1,875 (5/16) Zj - Cj 3 0-2/5 1/5 0 Cj V.B. b X 1 X 2 X 3 X 4 1 X 1 15/ /16-3/16 1 X 2 15/ /16 5/16 Zj - Cj 15/ /8 1/8 Variable que entra X 2 Variable que sale X 4 Solución óptima: X 1 * = 15/8 X 2 * = 15/8 Z * = 15/4 Conclusiones: La solución es única: X 1 * = 15/8 ; X 2 * = 15/8 ; Z* = 14/4 El método simplex es más práctico que el método algebraico 86

5 Ejemplo 2 Minimizar Z = 6X 1 + 4X 2 + 2X 3 6X 1 + 2X 2 + 6X 3 > 6 6X 1 + 4X 2 = 12 2X 1-2X 2 < 2 Xj > 0 ; j = 1, 2, 3 Minimizar Z = 6X 1 + 4X 2 + 2X 3 + MX 5 + M 6 6X 1 + 2X 2 + 6X 3 X 4 + X 5 = 6 6X 1 + 4X 2 + X 6 = 12 2X 1-2X 2 + X 7 = 2 Xj > 0 ; j = 1, 2, 3, 4, 5, 6, 7 Las variables básicas son X 5 = 6, X 6 = 12 X 7 = 2 Este ejercicio es el ejemplo 2 del capitulo de método algebraico. Compare los resultados entre los dos métodos, en cada iteración. Cj M M 0 V.B. b X 1 X 2 X 3 X 4 X 5 X 6 X 7 M X (1/6) M X X Zj - Cj 18M 12M-6 6M-4 6M-2 -M Cj M M 0 V.B. b X 1 X 2 X 3 X 4 X 5 X 6 X 7 6 X /3 1-1/6 1/ (-6) (-2) M X (1/2) 0 X /3-2 1/3-1/3 0 1 NO Zj - Cj 6M+6 0 2M-2-6M+4 M-1-2M Cj M M 0 V.B. b X 1 X 2 X 3 X 4 X 5 X 6 X 7 6 X /3 1/3-1/6 0 4 X /2-1/2 1/2 0 0 X /3-5/3 4/3 1 Zj - Cj M -M+1 0 Solución Óptima: Variables de decisión: X 1 * = 0, X 2 * = 3, X 3 * = 0, Z* = 12 Variables de holgura : X 4 * = 0, X 7 * = 8 Variables artificiales: X 5 * = 0, X 6 * = 0 87

6 Ejemplo 3 Aquí, se muestra el método simplex aplicado al ejemplo 3 del capítulo de método algebraico. Minimizar Z = 10X X X X X 7 = Con las siguientes restricciones: 3X 1 + 2X 2 + X 6 + X 7 = X 4 + X 5 + X 6 = X 2 +3X 3 + 2X 5 + X 6 + 2X 7 = Xj > 0 ; j = 1,2,3,4,5,6,7 Adicionando las variables artificiales necesarias para obtener una solución básica factible, el problema queda expresado de la siguiente forma: Min Z = 10X X X X X 7 + MX 8 + MX 9 + MX 10 3X 1 + 2X 2 + X 6 + X 7 + X 8 = X 4 + X 5 + X 6 + X 9 = X 2 + 3X 3 + 2X 5 + X 6 + 2X 7 + X 10 = Xj > 0 ; j = 1,2,3,4,5,6,7,8,9,10 Variables básicas X 8, X 9 y X 10 Cj M M M V.B. b X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 M X (1/3) M X M X Zj - Cj M 3M 3M-10 3M-30 2M-40 3M-10 3M 3M Cj M M M V.B. b X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 0 X /3 1 2/ /3 1/3 1/3 0 0 NO M X M X (1/2) Zj - Cj M 0 M-10 3M-30 2M-40 3M-10 2M 2M-20 -M

7 Cj M M M V.B. b X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 0 X /3 1 2/ /3 1/3 1/3 0 0 NO M X /2-3/ / / X /2 3/ / /2 NO Zj - Cj M /2M-5-3/2M-15 2M /2M+5 -M-10 -M 0-3/2M+5 Cj M M M V.B. b X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 0 X /3 1 2/ /3 1/3 1/ X /4-3/ /4-1/2 0 1/2-1/ X /2 3/ / / Zj - Cj M -M+20 -M-5 Cj M M M V.B. b X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 0 X X /4-3/4-3/ /4-1/4 1/2-1/4 10 X 5 0-3/2-1/2 3/ /2-1/2 0 1/2 Zj - Cj M-15 -M+20 -M-5 Solución: Variables de Decisión: X 1 * = X 2 * = X 3 * = X 5 * = X 7 * = 0 ; X 4 * = X 6 * = ; Z* = Variables Artificiales: X 8 * = X 9 * = X 10 * = 0 Interpretación: Para que halla un mínimo de desperdicio de cm de lámina y cumplir exactamente con los pedidos, hay que cortar láminas de la forma 4 y láminas de la forma 6 Ejemplo 4 En este ejemplo se muestra como resolver un problema en donde no todas las variables deben cumplir la condición de no negatividad, dicho de otra manera, con variables irrestrictas. Aquí el secreto consiste en reemplazar cada una de las variables irrestrictas por la diferencia de dos variables que si deban cumplir la condición de no negatividad. 89

8 Maximizar Z = 4X 1 + 5X 2 + 2X 3 X 4 X 1 + X 2 + 2X 3 X 4 > 1 2X 1 + 2X 2-3X 3 + X 4 < 3 X 1 + 4X 2 + 3X 3 + 2X 4 < 5 Xj > 0 ; j = 1, 2, 4 Aquí X 3 tiene libertad en el signo, esto es puede tomar valores positivos ó negativos. Hacemos X 3 = K W, en donde K y W deben ser positivas, K > 0 y W > 0 Fíjese que si K > W => X 3 será positiva, si K = W => X 3 será igual a cero (0) y si K < W => X 3 será negativa. Lo que hemos conseguido es convertir un problema que es irrestricto en su variable X 3 en uno que es restringido en todas sus variables, el problema queda así: Maximizar Z = 4X 1 + 5X 2 + 2K 2W X 4 X 1 + X 2 + 2K 2W X 4 > 1 2X 1 + 2X 2-3K + 3W + X 4 < 3 X 1 + 4X 2 + 3K 3W + 2X 4 < 5 Xj > 0 ; j = 1, 2, 4 ; K > 0 ; W > 0 Fíjese que este problema, es uno clásico de programación lineal y procedemos a resolverlo empleando el método simplex, para lo que adicionamos las variables de holgura y artificiales que sean necesarias para conseguir la solución básica factible. Maximizar Z = 4X 1 + 5X 2 + 2K 2W X 4 MX 6 X 1 + X 2 + 2K 2W X 4 X 5 + X 6 = 1 2X 1 + 2X 2-3K + 3W + X 4 X 7 = 3 X 1 + 4X 2 + 3K 3W + 2X 4 +X 8 < 5 Xj > 0 ; j = 1, 2, 4 ; K > 0 ; W > 0 Aquí las variables básicas son: X 6, X 7, y X 8 Cj M 0 0 V.B. b X 1 X 2 K W X 4 X 5 X 6 X 7 X 8 -M X /2 (1/2) 0 X NO 0 X /3 = 1,66 Zj - Cj -M -M-4 -M-5-2M-2 2M+2 M+1 M Cj M 0 0 V.B. b X 1 X 2 K W X 4 X 5 X 6 X 7 X 8 2 K 1/2 1/2 1/ /2-1/2 1/ (3) (-3) (2) 0 X 7 9/2 7/2 7/ /2-3/2 3/ /7 = 1,28 0 X 8 7/2-1/2 5/ /2 3/2-3/ /5 = 1,40 Zj - Cj M

9 Cj M 0 0 V.B. b X 1 X 2 K W X 4 X 5 X 6 X 7 X 8 5 X NO (-7/2) (-5/2) 0 X /7 = 0,14 (1/7) 0 X /5 = 0,20 Zj - Cj M Cj M 0 0 V.B. b X 1 X 2 K W X 4 X 5 X 6 X 7 X 8 5 X 2 9/ /7-3/7 3/7 2/7 0 NO -2 W 1/ /7 2/7-2/7 1/7 0 1/2 = 0,5 (2) (-5) 0 X 8 2/ /7 18/7-18/7-5/7 1 1/9 = 0,1 (7/18) Zj - Cj 43/ /7-19/7 M+19/7 8/7 0 Cj M 0 0 V.B. b X 1 X 2 K W X 4 X 5 X 6 X 7 X 8 5 X 2 4/3 1/ / /6 1/6 8/3 = 2,6-2 W 1/9 1/ /9-1/9 1/3 = 0,3 (3) 0 X 5 1/9-7/ / /18 7/18 NO (-2/7) (3/7) Zj - Cj 58/9-13/ /2 0 M 7/18 19/18 Cj M 0 0 V.B. b X 1 X 2 K W X 4 X 5 X 6 X 7 X 8 5 X 2 7/ /2-3/2 1/ /6-1/3 7/9 = 0,7 (2/3) 4 X 1 1/ /3-1/3 N0 (-1/2) (7/6) 0 X 5 1/ /2 7/2 3/ /2 0 N0 Zj - Cj 43/ /2 13/2 7/2 0 M 11/6 1/3 Cj M 0 0 V.B. b X 1 X 2 K W X 4 X 5 X 6 X 7 X 8 2 K 7/9 0 2/ / /9 2/9 (3) (7/2) 4 X 1 8/ /3 1/3 0 X 5 29/9 0 7/ / /9 7/9 Zj - Cj 110/9 0 13/ /3 0 M 10/9 16/9 Aquí todos los Zj Cj son > 0, entonces estamos en la solución óptima. La solución, mostrando las variables clasificadas es: 91

10 Variables de decisión Variables de holgura Variables artificiales X 1 * = 8/3 X 2 * = 0 X 3 * = K* - W* = 7/9 0 = 7/9 X 4 * = 0 Z * = 110/9 = 12,22 X 5 * = 29/9 X 7 * = 0 X 8 * = 0 X 6 * = 0 Ejemplo 5 En este ejemplo observaremos que a pesar de que el sistema tiene 4 variables, el número de iteraciones es apenas de 2 Minimizar Z = 3X 1-9X 2-5X 3 4X 4 Minimizar Z = 3X 1-9X 2-5X 3 4X 4 X 1 + 4X 2 + 5X 3 + 8X 4 < 8 X 1 + 4X 2 + 5X 3 + 8X 4 + X 5 = 8 X 1 + 2X 2 + 6X 3 + 4X 4 < 4 X 1 + 2X 2 + 6X 3 + 4X 4 + X 6 = 4 Xj > 0 ; j = 1, 2, 3, 4 Xj > 0 ; j = 1, 2, 3, 4, 5, 6 Cj V.B. b X 1 X 2 X 3 X 4 X 5 X 6 0 X (1/4) 0 X Zj - Cj Cj V.B. b X 1 X 2 X 3 X 4 X 5 X 6-9 X 2 2 1/4 1 5/4 2 1/4 0 0 X 6 0 1/2 0 7/2 0-1/2 1 Zj - Cj /4 0-25/ /4 0 Solución: X 1 * = 0 X 2 * = 2 X 3 * = 0 X 4 * = 0 Z * = -18 X 5 * = 0 X 6 * = 0 Ejemplo 6 Solución al problema número 4) El problema de los paquetes de tuercas, del capítulo 2, formulación. 92

11 Minimizar Z = 0,1X 1 + 0,04X 2 + 0,06X 3 Min Z = 1/10X 1 + 1/25X 2 + 3/50X 3 X 1 - X 2 + X 3 > 0 X 1 - X 2 + X 3 > 0 X 1 + X 2 < 1,6 X 1 + X 2 < 8/5 0,9X 1 0,1X 2 0,1X 3 > 0 9/10X 1 1/10X 2 1/10X 3 > 0-0,1X 1 + 0,9X 2 0,1X 3 > 0-1/10X 1 + 9/10X 2 1/10X 3 > 0-0,1X 1 0,1X 2 + 0,9X 3 > 0-1/10X 1 1/10X 2 + 9/10X 3 > 0 X 1 + X 2 + X 3 > 2 X 1 + X 2 + X 3 > 2 Xj > 0 ; j = 1, 2, 3 Xj > 0 ; j = 1, 2, 3 Min Z = 1/10X 1 + 1/25X 2 + 3/50X 3 +MX 10 - X 1 + X 2 - X 3 + X 4 = 0 X 1 + X 2 + X 5 = 8/5-9/10X 1 + 1/10X 2 + 1/10X 3 + X 6 = 0 1/10X 1-9/10X 2 + 1/10X 3 + X 7 = 0 1/10X 1 + 1/10X 2-9/10X 3 + X 8 = 0 X 1 + X 2 + X 3 - X 9 + X 10 = 2 Xj > 0 ; j = 1, 2, 3 Las variables básicas son: X 4, X 5, X 6, X 7, X 8, X 10 Cj 1/10 1/25 3/ M V.B. b X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 0 X (1) 0 X 5 8/ /5 0 X 6 0-9/10 1/10 1/ X 7 0 1/10-9/10 1/ NO 0 X 8 0 1/10 1/10-9/ M X Zj - Cj 2M M-1/10 M-1/25 M-3/ Cj 1/10 1/25 3/ M V.B. b X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 1/25 X NO (-1)(-1/10)(9/10) (-1/10)(-1) 0 X 5 8/ /5 0 X 6 0-4/5 0 1/5-1/ (5) 0 X 7 0-4/5 0-4/5 9/ NO 0 X 8 0 1/5 0-4/5-1/ NO M X Zj - Cj 2M 2M-7/50 0 2M-1/10 -M+1/ M 0 93

12 Cj 1/10 1/25 3/ M V.B. b X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 1/25 X / NO 0 X 5 8/ / /30 3/50 X / NO (1)(-1) (4/5)(-2) 0 X / NO 0 X / NO M X /5 (1/10) Zj - Cj 2M 10M-27/ / M+1/ M 0 Cj 1/10 1/25 3/ M V.B. b X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 1/25 X / /2 1/2 0 X 5 2/ / /5-3/5 3/50 X 3 4/ / /5 2/5 0 X 7 4/ / /5 2/5 0 X 8 3/ / /10 3/10 1/10 X 1 1/ /10 1/10 (5)(-2)(4) (4)(3) Zj - Cj 27/ / / /500 -M+27/500 Variables de decisión Variables de holgura Variables artificiales X 1 * = 1/5 X 2 * = 1 X 3 * = 4/5 = 0,8 Z * = 27/250 = 0,108 X 4 * = 0 X 5 * = 2/5 = 0,4 X 6 * = 0 X 7 * = 4/5 = 0,8 X 8 * = 3/5 = 0,6 X 9 * = 0 X 10 * = 0 Conclusión El método simplex es más práctico que el método algebraico, pero para problemas de un gran número de variables y restricciones, fácilmente se vuelve dispendioso por el número de iteraciones y por supuesto demorado para obtener la solución óptima, es aquí donde el uso del computador se hace indispensable y útil en términos de eficiencia, para ello existe el software adecuado, los más conocidos son: Winqsb de Yih-Long Chang, distribuido por John Wiley & Sons. Inc N.Y. Solver de Frontline Systems Inc., que viene integrado con el Excel de Microsoft. Lindo de Lindo Systems Inc. Que viene integrado con Visicalc. El AD, Ayuda a la decisión de la Universidad Cienfuegos de Cuba. 94

13 Se sugiere consultar las siguientes páginas en Internet: De estos lugares se puede bajar software gratuito ó en demostración, y manuales, además se dispone de interesantes enlaces. El Winqsb es un software muy completo para resolver problemas de Métodos Cuantitativos, tiene los siguientes módulos: 1) Análisis de aceptación. 2) Planeación agregada. 3) Análisis de decisión. 4) Programación dinámica. 5) Localización y distribución. 6) Series de tiempo. 7) Programación meta. 8) Sistemas y teoría de inventarios. 9) Programación del trabajo. 10) Programación lineal y entera. 11) Procesos de Markov. 12) Planeación del requerimiento de materiales. 13) Modelos de redes. 14) Programación no lineal. 15) PERT CPM 16) Programación cuadrática. 17) Gráficas de control de calidad. 18) Análisis de colas. 19) Sistemas de simulación de colas. A continuación se presentan las principales ventanas del módulo de programación lineal y entera. 95

14 Fíjese que hay que darle un nombre al problema, los datos de entrada se pueden almacenar en un archivo que tendrá el nombre del problema, esto es útil cuando el problema es grande. El resto de la ventana se explica por si sola, debido a la claridad de las preguntas. Fíjese en la variedad en el tipo de variables. A continuación se muestra un ejemplo de cómo se introducen los datos de un pequeño problema. Fíjese que se puede cambiar el tipo de variable, de forma individual, al igual que el sentido de la desigualdad ó cambiarla por una igualdad. El software resuelve problemas de dos variables por el método gráfico, resuelve el problema mostrando todos los tableros (paso a paso) ó muestra la solución de inmediato; También efectúa análisis de sensibilidad, hace gráficas y trabaja con el problema de la dualidad. La solución final se muestra a continuación: El precio sombra es lo que se incrementa la función objetivo por unidad adicional de recurso, aquí si el recurso de la restricción uno, que es 180 unidades, se incrementara a 181 unidades, la función objetivo crece en 16 unidades monetarias. 96

15 Problemas propuestos 1. Suponga que una persona acaba de heredar $6.000 y desea invertirlos. Al oír ésta noticia, dos amigos distintos le ofrecen la oportunidad de participar como socio en dos negocios, cada negocio planteado por cada amigo. En ambos casos, la inversión significa dedicar un poco de tiempo el siguiente verano, al igual que invertir efectivo. Con el primer amigo, al convertirse en socio completo, tendría que invertir $5.000 y 400 horas, y la ganancia estimada (ignorando el valor del tiempo) sería de $ Las cifras correspondientes a la proposición del segundo amigo son $4.000 y 500 horas, con una ganancia estimada de $ Sin embargo, ambos amigos son flexibles y le permitirían entrar en el negocio con cualquier fracción de la sociedad; la participación en las utilidades sería proporcional a esa fracción. Como de todas maneras, ésta persona está buscando un trabajo interesante para el verano (600 horas a lo sumo), ha decidido participar en una ó ambas propuestas, con la combinación que maximice la ganancia total estimada. Formule y resuelva el problema. Solución: X 1 * = $3.333,3 X 2 * = $2.666,6 Z * = $6.000 X 3 * = X 4 * = 0 Precio sombra, para el capital: $0,50 Precio sombra, para el tiempo: $5,00 Máxima utilidad a lograr $6.000 Con el amigo 1, invertirá $3.333,33 y obtendrá una utilidad de $3.000 Con el amigo 2, invertirá $2.666,66 y obtendrá una utilidad de $3.000 Con el amigo 1, trabajará 266,6 horas Con el amigo 2, trabajará 333,3 horas Por cada peso ($) adicional que invierta, incrementará la utilidad en $0,50 Por cada hora adicional que trabaje, incrementará la utilidad en $5 2. Una compañía manufacturera descontinuó la producción de cierta línea de productos no redituable. Esto creó un exceso considerable en la capacidad de producción. La gerencia quiere dedicar ésta capacidad a uno o más de tres productos; llámense productos 1, 2 y 3. En la siguiente tabla se resume la capacidad disponible de cada máquina que puede limitar la producción: Tipo de máquina Tiempo disponible (Horas) Fresadora 500 Torno 350 Rectificadora 150 El número de horas-máquina que se requiere para cada producto es: 97

16 Tipo de máquina Producto 1 Producto 2 Producto 3 Fresadora Torno Rectificadora El departamento de ventas ha indicado que las ventas potenciales para los productos 1 y 2 exceden la tasa máxima de producción y que las ventas potenciales del producto 3 son 20 unidades por semana. La ganancia unitaria sería $50, $20 y $25, respectivamente, para los productos 1, 2 y3. El objetivo es determinar cuántos productos de cada tipo debe producir la compañía para maximizar la ganancia. Solución: X 1 * =26,1905 unidades del producto 1 X 2 * =54,7619 unidades del producto 2 X 3 * =20 unidades del producto 3 Máxima ganancia Z * = $2.904,7620 Contribución del producto 1 a la ganancia: $1.309,5240 Contribución del producto 2 a la ganancia: $1.095,2380 Contribución del producto 3 a la ganancia: $500 La fresadora será usada todo el tiempo disponible; 500 horas El torno será usado todo el tiempo disponible; 350 horas La rectificadora será usada 118,5714 horas y quedará ociosa durante 31,4286 horas Toda la demanda potencial del producto 3 será fabricada. Por cada hora adicional de la fresadora, la ganancia aumentará en $4,7619 Por cada hora adicional de torno, la ganancia aumentará en $1,4286 El aumento de 1 hora adicional en la rectificadora no aumentará la ganancia. Por cada unidad potencial de demanda del producto 3, la ganancia aumentará en $1,1905 para mantener la solución óptima actual, el beneficio por unidad de cada producto, debe estar entre: 25 < Ganancia por unidad del producto 1 < 51,25 19 < Ganancia por unidad del producto 2 < 40 25,8095 < Ganancia por unidad del producto 3 < infinito 3. Se ha concedido permiso a una empresa de turismo para realizar vuelos entre Ibagué y las islas de San Andrés e interinsulares. para ello, debe comprar turborreactores con los que cubrir los vuelos entre Ibagué y las islas, así como aviones de hélice y / o helicópteros con los que atender los vuelos interinsulares. El presupuesto de compra es de millones de pesos. Las características de los aparatos que puede comprar se resumen en la tabla. 98

17 Tipo de Avión Costo / unid. (X 10 6 $) Mant./Unid. ($/día) Tripulación Pilotos Copilotos Azafatas Capacidad (pas/mes) Turborre A. hélice Helicóptero Se pueden contratar hasta 20 pilotos y 16 azafatas. Se desea emplear al menos a 3 copilotos. El tráfico entre Ibagué y San Andrés se estima en pasajeros por mes y el interinsular en 500 pasajeros por mes. El permiso concedido requiere que el número mínimo de aparatos sea 15. La compañía desea operar con costo de mantenimiento mínimo. a) Formule un problema de programación lineal que proporcione al plan óptimo de compra. b) Resolverlo e interpretar la solución. Solución: Se deben comprar 2 turborreactores, 3 aviones de hélice y 10 helicópteros, siendo el costo de mantenimiento diario mínimo $ Un empresario pretende fabricar dos tipos de congeladores denominados A y B. Cada uno de ellos debe pasar por tres operaciones antes de su comercialización: Ensamblaje, pintado y control de calidad. Los congeladores requieren, respectivamente, 2,5 y 3 horas de ensamblaje, 3 y 6 Kg. De esmalte para su pintado y 14 y 10 horas de control de calidad. Los costos totales de fabricación por unidad son, respectivamente, 30 y 28, y los precios de venta 52 y 48, todos ellos en miles de pesos. El empresario dispone semanalmente de horas para ensamblaje, de Kg. De esmalte y horas para control de calidad. Los estudios de mercado muestran que la demanda semanal de congeladores no supera las unidades y que, en particular, la de tipo A es de, al menos, 600 unidades. Se desea: a) Formular un modelo de programación lineal que indique cuántos congeladores deben fabricarse de cada tipo para que el beneficio sea máximo, teniendo en cuenta el estudio de demanda. b) Resolverlo mediante el método simplex. Interpretar la solución óptima incluyendo las variables de holgura. c) Determinar los precios sombra de las horas de ensamblaje y control de calidad. Al fabricante le ofrecen disponer de 200 horas más para ensamblaje con un costo adicional total de $ pesos. Debería aceptar la oferta? 99

18 Solución: Debe producir 882 congeladores tipo A y 764 congeladores tipo B con un beneficio óptimo de $ En el departamento de ensamblaje sobran 3 horas, no se consumirán 295,6 Kg. De esmalte, sobrarán 12 horas de control de calidad, se dejarán de producir 54 congeladores, se fabricarán 282 congeladores tipo A por encima del límite de 600 Por cada hora de ensamble adicional (dentro del intervalo 4.268,5 ; 4.725) el beneficio aumentará en $ En un laboratorio se fabrican 4 productos P 1, P 2, P 3, P 4 que consumen un día por unidad en su proceso completo de producción, aunque se pueden producir varias unidades simultáneamente. El espacio (m 2 ) en el almacén y la mano de obra (número de trabajadores) disponibles limitan la producción. La siguiente tabla contiene los datos relevantes del proceso de producción, así como los costos de fabricación y precios de venta (en miles de pesos). Producto P 1 P 2 P 3 P 4 Disponibilidad Área (m 2 /und.) Trabajadores /und Costos /unidad Precio de venta /und a) Encontrar el plan de producción de beneficio máximo b) Interpretar los valores de los precios sombra c) Cuál es el rango de los recursos del programa construido para el que se mantiene la optimalidad de tales valores? d) La firma podría alquilar 150 m 2 más de superficie de almacén a un costo de $ por día. Debería alquilar éste espacio? Si es así, Cuál es el nuevo plan de producción? Solución De producto 1 debe producir 10 unidades y de producto 4, 20 unidades; de los productos 2 y 3 no debe producir. Por cada m 2 adicional de bodega el beneficio aumenta en $680 Por cada trabajador adicional el beneficio aumenta en $