1 Modelos CuantitativosCapítulo 7 Primera Parte Programación Lineal Método Gráfico

2 7.1 Un problema simple de maximización

3 Características de los problemas de Programación LinealEl objetivo es la maximización o minimización de alguna cantidad. Todos los problemas presentan restricciones.

4 Problema de las bolsas de golf 1..Departamentos: Corte y teñido. Costura. Terminado. Inspección y Embalaje. Se producirán dos tipos de bolsas: Estándar con utilidad de 10 dólares y de Lujo con utilidad de 9 dólares.

5 Problema de las bolsas de golf ..2..Tiempo de producción (horas) Producto Corte y teñido Costura Terminado Inspección Embalaje Bolsa Estándar 7/10 1/2 1 1/10 Bolsa de Lujo 5/6 2/3 1/4 Hrs. disponibles en los prox. 3 meses 603 600 708 135

6 Problema de las bolsas de golf ..3El problema de la compañía Par es determinar cuántas bolsas estándares y cuántas bolsas de lujo deben fabricar con objeto de maximizar la contribución a las utilidades.

7 7.2 Función Objetivo

8 Función Objetivo Variables de decisiónx1 = número de bolsas estándares fabricadas x2 = número de bolsas de lujo fabricadas Función Objetivo Contribución a las utilidades totales z = 10 x1 + 9 x2 Utilizando max como abreviatura de maximizar, el objetivo de Par se plantea de la siguiente manera max z = max 10 x1 + 9 x2

9 7.3 Restricciones

10 Restricciones Corte y Teñido Costura Terminado Inspección y embalajeNo negatividad

11 7.4 Planteamiento matemático

12 Planteamiento matemático del problema como un modelo de Programación Lineal

13 Problema Ahora se requiere encontrar la combinación de productos (x1 y x2) que satisfaga todas las restricciones y, al mismo tiempo, dé un valor de la función objetivo que sea mayor o igual a un valor dado por cualquiera otra solución factible.

14 Semántica de la Programación LinealProgramación: elegir curso de acción Lineal: en el modelo matemático están presentes sólo funciones lineales.

15 7.5 Solución gráfica

16 Gráfica de los puntos de soluciónX2 1200 Un punto solución con x1=200 x2=800 1000 (200, 800) 800 Un punto solución con x1=400 x2=300 600 400 Cantidad de bolsas de lujo (400, 300) 200 X1 -200 200 400 600 800 1000 1200 Cantidad de bolsas estándares -200

17 Restricciones de no negatividadX2 1200 1000 800 600 400 Cantidad de bolsas de lujo 200 X1 -200 200 400 600 800 1000 1200 Cantidad de bolsas estándares -200

18 La recta de restricción de corte y teñidoX2 1200 1000 800 (0, 630) Cantidad de bolsas de lujo 600 (600, 500) 400 7/10x1 + 1x2 = 630 200 (200, 200) (900,0) C. y T. X1 -200 200 400 600 800 1000 1200 Cantidad de bolsas estándares -200

19 Criterio para determinar los puntos factibles de solución.Si un punto de solución determinado no es factible, entonces todos los demás puntos de solución que se encuentran al mismo lado de la recta de restricción tampoco son factibles. Si un punto de restricción específico es factible, entonces son factibles todos los demás puntos de solución que están al mismo lado de la recta de restricción. Por ello es necesario evaluar la función restrictiva sólo para un punto solución y determinar en cuál de los dos lados de la recta de restricción se encuentra la región factible (región de todos los puntos factibles de solución).

20 Cantidad de bolsas de lujo Cantidad de bolsas estándaresSoluciones factibles para la restricción de corte y teñido (C. y T.) representadas mediante la región sombreada X2 1200 1000 800 Cantidad de bolsas de lujo 600 7/10x1 + 1x2 = 630 400 200 C. y T. X1 -200 200 400 600 800 1000 1200 Cantidad de bolsas estándares -200

21 Cantidad de bolsas de lujo Cantidad de bolsas estándaresSoluciones factibles para la restricción de costura (C.) representadas mediante la región sombreada X2 1200 1000 (0, 720) 800 Cantidad de bolsas de lujo 600 400 1/2x1 + 5/6x2 = 600 200 (1200,0) C. X1 -200 200 400 600 800 1000 1200 Cantidad de bolsas estándares -200

22 Cantidad de bolsas de lujo Cantidad de bolsas estándaresSoluciones factibles para la restricción de terminado (T.) representadas mediante la región sombreada X2 1200 (0, 1062) 1000 800 Cantidad de bolsas de lujo 600 1x1 + 2/3x2 = 708 400 T. 200 (708,0) X1 -200 200 400 600 800 1000 1200 Cantidad de bolsas estándares -200

23 Cantidad de bolsas de lujo Cantidad de bolsas estándaresSoluciones factibles para la restricción de inspección y embalaje (I. y E.) representadas mediante la región sombreada X2 1200 1000 800 (0, 540) Cantidad de bolsas de lujo 600 400 1/10x1 + 1/4x2 = 135 200 I. Y E. (1350,0) X1 -200 200 400 600 800 1000 1200 1400 Cantidad de bolsas estándares -200

24 Cantidad de bolsas de lujo Cantidad de bolsas estándaresGráfica con la combinación de las restricciones y que muestra la región de soluciones factibles para el problema de Par Inc. X2 1200 1000 T. 800 C. Cantidad de bolsas de lujo 600 400 200 Región Factible I. Y E. C. y T. X1 -200 200 400 600 800 1000 1200 1400 Cantidad de bolsas estándares -200

25 Región de soluciones factibles para el problema de Par Inc.X2 1200 1000 800 Cantidad de bolsas de lujo 600 400 200 Región Factible X1 -200 200 400 600 800 1000 1200 1400 Cantidad de bolsas estándares -200

26 Recta de utilidades de $1 800 para el problema de Par Inc.X2 600 500 400 Cantidad de bolsas de lujo 300 Recta de utilidades (0, 200) 10x1 + 9x2 = 1800 200 100 (180,0) X1 100 200 300 400 500 600 700 Cantidad de bolsas estándares

27 Rectas de utilidades seleccionadas para el problema de Par Inc.X2 600 500 400 Cantidad de bolsas de lujo 300 10x1 + 9x2 = 5400 200 10x1 + 9x2 = 3600 100 10x1 + 9x2 = 1800 X1 100 200 300 400 500 600 700 Cantidad de bolsas estándares

28 Rectas de utilidades seleccionadas para el problema de Par Inc.X2 600 10x1 + 9x2 = 7668 500 Línea de utilidad máxima 400 Solución óptima Cantidad de bolsas de lujo 300 (540,252) 200 100 X1 100 200 300 400 500 600 700 Cantidad de bolsas estándares

29 Rectas de utilidades seleccionadas para el problema de Par Inc.X2 600 10x1 + 9x2 = 7668 500 Línea de utilidad máxima 400 Solución óptima Cantidad de bolsas de lujo 300 (540,252) 200 100 X1 100 200 300 400 500 600 700 Cantidad de bolsas estándares

30 Resumen del procedimiento gráfico de solución para problemas de maximizaciónElaborar una gráfica de los puntos solución factible para cada una de las restricciones. Determinar la región factible identificando los puntos solución que satisfacen en forma simultánea todas las restricciones. Trazar una recta de la función objetivo para un caso concreto. Desplazar rectas de función objetivo paralelas en dirección de los valores más altos de la función objetivo hasta que llegue el momento en el que un mayor alejamiento haga que la recta, menos un punto, quede por completo fuera de la región factible Un punto solución factible que se encuentre sobre la recta de la función objetivo y que tenga el mayor valor, es una solución óptima.

31 Variables de Holgura Requisitos de los tiempos de producción según solución óptima

32 Variables de Holgura Cualquier capacidad no utilizada, u ociosa, para una restricción de < o igual se la denomina holgura. Los resultados anteriores muestran a los administradores que la producción de 540 estándares y 252 bolsas de lujo requeriría de todo el tiempo disponible de acabado (708 horas), y que dejarán de utilizarse 120 horas del tiempo de costura, ( ) y 18 horas de tiempo de inspección y embalaje ( ). Estas horas de tiempo no utilizado serían la holgura de los dos departamentos.

33 Variables de Holgura Las variables que se añaden para representar la capacidad de holgura se llaman variables de holgura. Cómo la capacidad no utilizada no contribuye a las utilidades, tienen coeficiente cero en la función objetivo.

34 Programa Lineal en Forma EstándarEn los casos en que los programas lineales están formulados de manera que todas las restricciones se expresan como igualdades, se dice que está escrito de forma estándar.

35 Valores de las variables de holgura para el problema de Par Inc.Restricción Valor de la variable de holgura Corte y teñido Costura Terminado Inspección y embalaje s1 = 0 s2 =120 s3 = 0 s4 = 18 La restricción “Costura” es una restricción redundante porque no afecta la región factible y por tanto tampoco afecta la solución óptima.

36 7.6 Puntos extremos y la solución óptima

37 Replanteamiento del problema 1..Supóngase que se reduce la contribución a las utilidades de las bolsas estándares de Par Inc. de $10 a $5 por bolsa, al mismo tiempo que la contribución a las utilidades de las bolsas de lujo y todas las restricciones permanecen constantes.

38 Replanteamiento del problema ..2

39 Cantidad de bolsas de lujo Cantidad de bolsas estándaresSolución óptima para el problema Par Inc., con una función objetivo de 5x1+9x2 X2 Solución óptima (x1 = 300, x2 = 420) 600 500 400 Cantidad de bolsas de lujo Línea de utilidad máxima 300 200 5x1 + 9x2 = 5280 5x1 + 9x2 = 2700 100 X1 100 200 300 400 500 600 700 Cantidad de bolsas estándares

40 Cantidad de bolsas de lujo Cantidad de bolsas estándaresLos cinco puntos extremos de la región factible (o de factibilidad) para el problema de Par, Inc. X2 600  500  400 Cantidad de bolsas de lujo 300  Región Factible 200 100   X1 100 200 300 400 500 600 700 Cantidad de bolsas estándares

41 7.7 Un problema sencillo de minimización

42 Problema de M&D ChemicalsDos productos 1 y 2 cuya producción total debe ser cuando menos 350. Se debe satisfacer también un pedido de un cliente importante de 125 galones del producto 1. El producto 1 requiere de 2 horas de tiempo de procesamiento por galón, en tanto que el producto 2 requiere de una hora de procesamiento por galón y existen disponibles 600 horas de tiempo de procesamiento para el siguiente mes. El objetivo de M&D es satisfacer los requicitos anteriores incurriendo en un costo de producción mínimo. Los costos de producción son de $2 por galón de producto 1 y de $3 por galón del producto 2.

43 Planteamiento del problemax1 = número de galones del prod. 1 fabricados x2 = número de galones del prod. 2 fabricados

44 Región factible para el problema de M&DX2 600 Mínimo x1=125 500 Tiempo de Procesamiento 400 Galones del Producto 2 300 Producción 200 2x1 + 1x2 = 600 100 1x1 + 1x2 = 350 X1 -100 100 200 300 400 500 600 Galones del Producto 1 -100

45 Resolución gráfica para el problema de M&DX2 600 500 400 Galones del Producto 2 300 200 2x1 + 3x2 = 1200 100 Solución óptima (x1 = 250, x2 = 100) 2x1 + 3x2 = 800 X1 -100 100 200 300 400 500 600 Galones del Producto 1 -100

46 Resumen del procedimiento gráfico de solución para problemas de minimizaciónElaborar una gráfica de los puntos solución factible para cada una de las restricciones. Determinar la región factible identificando los puntos solución que satisfacen en forma simultánea todas las restricciones. Trazar una recta de la función objetivo para un caso concreto. Desplazar rectas de función objetivo paralelas en dirección de los valores más bajos de la función objetivo hasta que llegue el momento en el que un mayor alejamiento haga que la recta, menos un punto, quede por completo fuera de la región factible Un punto solución factible que se encuentre sobre la recta de la función objetivo y que tenga el menor valor, es una solución óptima.

47 Variables excedentes Cualquier cantidad en exceso que corresponda a una restricción de > o igual se la denomina excedente. En el problema de M&D obsérvese que se satisface la restricción que exige satisfacer la demanda del producto 1, con x1 = 250 galones. De hecho, la elaboración del productor excede su nivel mínimo en 125 galones

48 Programa Lineal en Forma Estándar del problema de M&D

49 Valor de la variable de holguraValores de las variables de holgura para el problema de M&D Chemicals con la solución óptima encontrada Restricción Valor de la variable de holgura Demanda del producto 1 Producción total Tiempo de Procesamiento s1 = 125 s2 =0 s3 = 0

50 Programa Lineal con los tres tipos de restricciones

51 7.8 Casos Especiales

52 Casos Especiales Soluciones óptimas alternativas No factibilidad No acotamiento

53 Soluciones óptimas alternas 1..Supongamos que la utilidad proveniente de la bolsa estándar ha disminuido a $6.30. La función objetivo modificada se convierte en 6.3 x1 + 9 x2

54 Soluciones óptimas alternas ..2X2 600  500  (x1 = 300, x2 = 420) 400 Cantidad de bolsas de lujo 300  (x1 = 540, x2 = 252) 6.3x1 + 9x2 = 3780 200 6.3x1 + 9x2 = 5670 100   X1 100 200 300 400 500 600 700 Cantidad de bolsas estándares

55 Cantidad de bolsas de lujo Cantidad de bolsas estándaresNo factibilidad para las restricciones de producción de 360 bolsas de lujo y 500 estándares como mínimo. X2 600 Puntos que satisfacen los requisitos mínimos de solución 500 x1 mínimo 400 x2 mínimo Cantidad de bolsas de lujo 300 Puntos que satisfacen las restricciones de los departamentos 200 100 X1 100 200 300 400 500 600 700 Cantidad de bolsas estándares

56 Recursos que se requieren para fabricar 500 bolsas estándares y 360 bolsas de lujo.Operación Recursos mínimos que se requieren (horas) Recursos disponibles (horas) Recursos adicionales que se necesitan (horas) Corte y T. 7/10(500) + 1(360) = 710 630 80 Costura 1/2(500) + 5/6(360) = 550 600 Ninguno Terminado 708 32 Inspección y embalaje 135 5

57 No acotamiento La solución de un problema de programación lineal es no acotada si el valor de la solución puede ser infinitamente grande, sin violar ninguna de las restricciones. A esta condición se la podría denominar “utopía gerencial”. Si ocurriera tal condición en un problema de maximización de utilidades, sería un hecho que los administradores pudieran lograr utilidades ilimitadas. Significa el problema ha sido mal planteado y se ha omitido alguna restricción importante.

58 Ejemplo de No Acotamiento

59 Cantidad de bolsas de lujo Cantidad de bolsas estándaresNo acotamiento X2 30 25 20 Cantidad de bolsas de lujo 15 10 5 X1 5 10 15 20 25 30 35 Cantidad de bolsas estándares