Introduccion a la Programacion Lineal PDF

3 C A P Í T U L O Introducción a la programación lineal E l desarrollo de la programación lineal ha sido clasificado como uno de los avances científicos más importantes de mediados del siglo xx, y estamos de acuer...

3 C A P Í T U L O Introducción a la programación lineal E l desarrollo de la programación lineal ha sido clasificado como uno de los avances científicos más importantes de mediados del siglo xx, y estamos de acuerdo con esta aseveración. Su efecto desde 1950 ha sido extraordinario. En la actualidad es una herramienta de uso normal que ha ahorrado miles o millones de dólares a muchas compañías o negocios, incluso empresas me- dianas, en los distintos países industrializados del mundo; su aplicación a otros sectores de la sociedad se ha ampliado con rapidez. Una proporción muy grande de los programas científicos en computadoras está dedicada al uso de la programación lineal. Se han escrito docenas de libros de texto sobre esta materia y se cuentan por cientos los artículos publicados que describen aplicacio- nes importantes. ¿Cuál es la naturaleza de esta notable herramienta y qué tipos de problemas puede manejar? El lector adquirirá una noción de este tema a medida que trabaje en los ejemplos que se presentarán más adelante. Sin embargo, un resumen verbal puede permitirle elaborar una idea. Expresado en forma breve, el tipo más común de aplicación abarca el problema general de asignar de la mejor manera posible —es decir, de forma óptima— recursos limitados a actividades que compiten entre sí por ellos. Con más precisión, este problema consiste en elegir el nivel de ciertas actividades que compiten por recursos escasos necesarios para realizarlas. Después, los niveles de actividad que se eligen dictan la cantidad de recursos que consumirá cada una de ellas. La variedad de situaciones a las que se puede aplicar esta descripción es sin duda muy grande, ya que abarca desde la asignación de instalaciones de producción a los productos hasta la asignación de los recursos nacionales a las necesidades de un país; desde la selección de una cartera de inversiones hasta la selección de los patrones de envío; desde la planeación agrícola hasta el diseño de una terapia de radiación, etc. No obstante, el ingrediente común de todas estas situaciones es la necesidad de asignar recursos a las actividades mediante la elección de los niveles de éstas. La programación lineal utiliza un modelo matemático para describir el problema. El adjetivo lineal significa que todas las funciones matemáticas del modelo deben ser funciones lineales. En este caso, la palabra programación no se refiere aquí a términos computacionales; en esencia es sinónimo de planeación. Por lo tanto, la programación lineal involucra la planeación de activida- des para obtener un resultado óptimo; esto es, el resultado que mejor alcance la meta especificada —de acuerdo con el modelo matemático— entre todas las alternativas factibles. Aunque la asignación de recursos a las actividades es la aplicación más frecuente, la progra- mación lineal tiene muchas otras posibilidades. En realidad, cualquier problema cuyo modelo matemático se ajuste al formato general del modelo de programación lineal, es un problema de programación lineal. (Por esta razón, un problema de programación lineal y su modelo se denomi- nan con frecuencia programa lineal, o incluso sólo PL.) Aún más, se dispone de un procedimiento de solución muy eficiente llamado método símplex para resolver estos problemas lineales, incluso los de gran tamaño. Éstas son algunas razones del tremendo efecto de la programación lineal en las décadas recientes. Debido a su gran importancia hemos dedicado a la programación lineal éste y los siguientes seis capítulos. Después de presentar aquí las características generales de programación lineal, los capítulos 4 y 5 se dedican al método símplex. El capítulo 6 analiza los problemas de programación www.elsolucionario.net 22 CAPÍTULO 3 INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL lineal después de la aplicación inicial del método símplex. El capítulo 7 examina varias extensiones muy empleadas de este método e introduce el algoritmo de punto interior que en ocasiones se usa para resolver problemas de programación lineal aún más grandes que los que maneja el método símplex. Los capítulos 8 y 9 consideran algunos problemas especiales de programación lineal cuya trascendencia justifica su estudio individual. Además, en varios de los capítulos posteriores se verán aplicaciones de programación lineal a otras áreas de la investigación de operaciones. Este capítulo comienza con el desarrollo de un ejemplo prototípico simplificado de un proble- ma de programación lineal. Este ejemplo es tan pequeño que puede resolverse de manera directa en una gráfica. En las secciones 3.2 y 3.3 se presentan el modelo general de programación lineal y sus supuestos básicos. La sección 3.4 proporciona algunos ejemplos adicionales de programación lineal. La sección 3.5 describe cómo pueden establecerse y resolverse problemas de programa- ción lineal de tamaño mediano en una hoja de cálculo. Sin embargo, algunos problemas reales requieren modelos en verdad masivos. La sección 3.6 ilustra cómo suelen surgir estos modelos de gran tamaño y cómo se pueden formular de manera correcta con la ayuda de lenguajes especiales de modelado como MPL —su formulación se describe en esta sección— o LINGO (la formulación de este modelo se presenta en el suplemento 2 de este capítulo en el sitio web del libro). 3.1 EJEMPLO PROTOTÍPICO La WYNDOR GLASS CO. produce artículos de vidrio de alta calidad, entre ellos ventanas y puertas de vidrio. Tiene tres plantas. Los marcos y molduras de aluminio se hacen en la planta 1, los de madera en la planta 2; la 3 produce el vidrio y ensambla los productos. Debido a una reducción de las ganancias, la alta administración ha decidido reorganizar la línea de producción de la compañía. Se discontinuarán varios productos no rentables y se dejará libre una parte de la capacidad de producción para emprender la fabricación de dos productos nuevos cuyas ventas potenciales son muy prometedoras: Producto 1: una puerta de vidrio de 8 pies con marco de aluminio Producto 2: una ventana corrediza con marco de madera de 4 por 6 pies El producto 1 requiere parte de la capacidad de producción en las plantas 1 y 3 y nada en la planta 2. El producto 2 sólo necesita trabajo en las plantas 2 y 3. La división de comercialización ha con- cluido que la compañía puede vender todos los productos que se puedan fabricar en las plantas. Sin embargo, como ambos productos competirían por la misma capacidad de producción en la planta 3, no está claro cuál mezcla de productos sería la más rentable. Por lo tanto, se ha formado un equipo de IO para estudiar este problema. El grupo comenzó por realizar juntas con la alta administración para identificar los objetivos del estudio. Como consecuencia de ellas se desarrolló la siguiente definición del problema: Determinar cuáles tasas de producción deben tener los dos productos con el fin de maximizar las utilidades totales, sujetas a las restricciones impuestas por las capacidades de producción limita- das disponibles en las tres plantas. (Cada producto se fabricará en lotes de 20 unidades, de manera que la tasa de producción está definida como el número de lotes que se producen a la semana.) Se permite cualquier combinación de tasas de producción que satisfaga estas restricciones, incluso no fabricar uno de los productos y elaborar todo lo que sea posible del otro. El equipo de IO también identificó los datos que necesitaba reunir: 1. Número de horas de producción disponibles por semana en cada planta para fabricar estos nuevos productos. (Casi todo el tiempo de estas plantas está comprometido con los productos actuales, lo que limita la capacidad para manufacturar nuevos productos.) 2. Número de horas de fabricación que se emplea para producir cada lote de cada artículo nuevo en cada una de las plantas. 3. La ganancia por lote de cada producto nuevo. (Se escogió la ganancia por lote producido como una medida adecuada una vez que el equipo llegó a la conclusión de que la ganancia incremental de cada lote adicional producido sería, en esencia, constante, sin que importase el número total de lotes producidos. Debido a que no se incurre en costos sustanciales para iniciar www.elsolucionario.net  Recuadro de aplicación T2 23 Swift & Company es una empresa diversificada productora disponibilidad de ganado y las restricciones impuestas por la de proteína con base en Greeley, Colorado. Con ventas anua- capacidad de la planta. les de más de 8 000 millones de dólares, la carne de res y sus Para enfrentar estos tres desafíos, un equipo de IO desa- productos derivados son, por mucho, la parte más grande del rrolló un sistema integrado de 45 modelos de programación negocio de la compañía. lineal basado en tres formulaciones de modelo para programar A fin de mejorar las ventas de la empresa y su desem- de manera dinámica sus operaciones de fabricación de carne peño en la manufactura, la alta administración concluyó que en cinco plantas en tiempo real cuando recibe los pedidos. Los necesitaba alcanzar tres objetivos importantes. Uno fue per- beneficios totales auditados que se observaron en el primer mitir a los representantes de servicio al cliente hablar a sus año de operación de este sistema fueron de 12.74 millones de más de 8 000 clientes para transmitirles información precisa dólares, de los cuales 12 millones correspondieron a la optimi- acerca de la disponibilidad de inventario actual y futuro, al zación de la mezcla de productos. Entre otros beneficios se des- mismo tiempo que consideraban fechas de entrega solicitadas tacan la disminución de las órdenes perdidas, la reducción de y edad máxima del producto en el momento de su entrega. los descuentos de precio y la mejora de las entregas a tiempo. Un segundo objetivo fue producir un programa eficiente de nivel de turno para cada planta en un horizonte de 28 días. El Fuente: A. Bixby, B. Downs y M. Self, “A Scheduling and Capa- tercer objetivo consistió en determinar de manera exacta si ble-to-Promise Application for Swift & Company”, en Interfaces, una planta podía embarcar una cantidad solicitada de pedi- 36(1): 39-50, enero-febrero de 2006. (En nuestro sitio web, www. dos-líneas-artículos en la fecha y a la hora requeridas dadas la mhhe.com/hillier, se proporciona un vínculo con este artículo.) la producción y la comercialización de estos nuevos productos, la ganancia total de cada uno es aproximadamente la ganancia por lote que se produce multiplicada por el número de lotes.) La obtención de estimaciones razonables de estas cantidades requirió del apoyo de personal clave en varias unidades de la compañía. El personal de la división de manufactura proporcionó los datos de la primera categoría mencionada. En la segunda categoría, el desarrollo de estimaciones requirió un análisis de los ingenieros de manufactura involucrados en el diseño de los procesos de producción para elaborar los nuevos artículos. Al analizar los datos de costos que se obtuvieron, junto con la decisión sobre los precios de la división de marketing, el departamento de contabilidad calculó las estimaciones para la tercera categoría. La tabla 3.1 resume los datos reunidos. De inmediato, el equipo de IO reconoció que se trataba de un problema de programación li- neal del tipo clásico de mezcla de productos y procedió a la formulación del modelo matemático correspondiente. Formulación como un problema de programación lineal La definición del problema planteado indica que las decisiones que deben tomarse son el número de lotes de los productos que se fabricarán semanalmente, de manera que se maximice su ganancia total. Para formular el modelo matemático de programación lineal de este problema se define x1 5 número de lotes del producto 1 que se fabrican por semana x2 5 número de lotes del producto 2 que se fabrican por semana Z 5 ganancia semanal total (en miles de dólares) que generan estos dos productos TABLA 3.1 Datos del problema de la Wyndor Glass Co. Tiempo de producción por lote, horas Producto Tiempo de producción Planta 1 2 disponible a la semana, horas 1 1 0 4 2 0 2 12 3 3 2 18 Ganancia por lote $3 000 $5 000 www.elsolucionario.net 24 CAPÍTULO 3 INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL Por lo tanto, x1 y x2 son las variables de decisión del modelo. Si se usa el último renglón de la tabla 3.1 se obtiene Z 5 3x1 1 5x2. El objetivo es elegir los valores de x1 y x2 que maximice Z 5 3x1 1 5x2, sujeta a las restricciones impuestas sobre sus valores por las capacidades de producción limitadas de las cuales se disponen en las tres plantas. La tabla 3.1 indica que cada lote del producto 1 que se produce por semana emplea una hora de producción en la planta 1, y sólo se dispone de 4 horas semanales. En términos matemáticos, esta restricción se expresa mediante la desigualdad x1 # 4. De igual manera, la plan- ta 2 impone la restricción 2x2 # 12. El número de horas de producción usadas a la semana en la planta 3 que se consume al elegir x1 y x2 como las tasas de producción de los nuevos productos sería 3x1 1 2x2. En consecuencia, la expresión matemática de la restricción de la planta 3 es 3x1 1 2x2 # 18. Por último, como las tasas de producción no pueden ser negativas, es necesario restringir las variables de decisión a valores no negativos: x1 $ 0 y x2 $ 0. Para resumir, en el lenguaje matemático de programación lineal, el problema consiste en seleccionar valores de x1 y x2 para Maximizar Z ⫽ 3x1 ⫹ 5x2 , sujeta a las restricciones x1 ⱕ 4 2x2 ⱕ 12 3x1 ⫹ 2x2 ⱕ 18 y x1 ⱖ 0, x2 ⱖ 0. (Observe cómo la información de la tabla 3.1 en esencia se duplica en la distribución de los coefi- cientes de x1 y x2 en el modelo de programación lineal.) Solución gráfica Este pequeño problema tiene sólo dos variables de decisión, esto es, sólo dos dimensiones, así que se puede usar un procedimiento gráfico para resolverlo. Este procedimiento incluye la construc- ción de una gráfica de dos dimensiones con x1 y x2 como los ejes. El primer paso es identificar los valores de (x1, x2) permitidos por las restricciones. Este objetivo se logra dibujando cada una de las rectas que limitan los valores permitidos por una restricción. Para comenzar, observe que las restricciones de no negatividad x1 $ 0 y x2 $ 0 exigen que el punto (x1, x2) se encuentre en el lado positivo de los ejes (incluso sobre cualquiera de los dos ejes), es decir, en el primer cuadrante. Des- pués, debe observarse que la restricción x1 # 4 significa que (x1, x2) no puede estar a la derecha de la recta x1 5 4. Estos resultados se muestran en la figura 3.1, en la que el área sombreada contiene los únicos valores de (x1, x2) permitidos. De manera parecida, la restricción 2x2 # 12 (o de modo equivalente, x2 # 6) implica que la recta 2x2 5 12 debe agregarse a la frontera de la región permisible. La última restricción, 3x1 1 2x2 # 18, se encuentra al graficar los puntos (x1, x2) tales que 3x1 1 2x2 5 18 (otra recta) para completar la frontera. (Observe que los puntos que cumplen 3x1 1 2x2 # 18 son aquellos que están sobre o por debajo de la recta 3x1 1 2x2 5 18, por lo que ésta es la recta que limita, y más allá de ella, la desigualdad no se satisface.) En la figura 3.2 se muestra la región de valores permisibles de (x1, x2), llamada región factible. (La demostración llamada Graphical Method —método gráfico— en el OR Tutor proporciona un ejemplo detallado de la construcción de la región factible.) El paso final es seleccionar, dentro de esta región factible, el punto que maximiza el valor de Z 5 3x1 1 5x2. Para descubrir cómo realizar este paso de manera eficiente se pueden intentar algunos valores por prueba y error. Por ejemplo, probar, Z 5 10 5 3x1 1 5x2 para ver si existe algún valor de (x1, x2) dentro de la región permisible que dé un valor de 10 para Z. Si se dibuja la recta 3x1 1 5x2 5 10 se puede ver que existen muchos puntos sobre esta recta que están dentro de la región (vea la figura 3.3). Después de intentar este valor arbitrario de Z 5 10 se tiene una mejor www.elsolucionario.net  3.1 EJEMPLO PROTOTÍPICO 25 x2 5 4 3 2 FIGURA 3.1 El área sombreada muestra 1 los valores de (x1, x2) per- mitidos por x1 $ 0, x2 $ 0, x1 # 4. 0 1 2 3 4 5 6 7 x1 perspectiva, debe intentarse ahora un valor arbitrario más grande, por ejemplo, Z 5 20 5 3x1 1 5x2. De nuevo, la figura 3.3 revela que un segmento de la recta 3x1 1 5x2 5 20 se encuentra dentro de la región, de manera que el máximo valor permisible de Z debe ser, por lo menos, 20. Observe ahora en la figura 3.3 que las dos rectas que se acaban de graficar son paralelas. Esto no es coincidencia, ya que cualquier recta construida de esta manera tiene la forma Z 5 3x1 1 5x2 para el valor seleccionado de Z, lo que implica que 5x2 5 23x1 1 Z o, en forma equivalente, 3 1 x2 x1 Z 5 5 Esta última ecuación, llamada forma de pendiente-ordenada al origen de la función objetivo, demuestra que la pendiente de las rectas es 25–3 (ya que cada incremento de una unidad en x1 hace que x2 cambie en – 5–3 ), mientras que la ordenada al origen de la recta —la intersección con el eje x2— FIGURA 3.2 x2 El área sombreada muestra los valores permitidos de 10 (x1, x2), llamada la región factible. 3x1 1 2x2 5 18 8 x1 5 4 6 2x2 5 12 4 Región factible 2 0 2 4 6 8 x1 www.elsolucionario.net 26 CAPÍTULO 3 INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL x2 8 Z 5 36 5 3x1 1 5x2 (2, 6) 6 Z 5 20 5 3x1 1 5x2 4 Z 5 10 5 3x1 1 5x2 2 FIGURA 3.3 El valor de (x1, x2) que maximiza 3x1 1 5x2 es 0 2 4 6 8 10 x1 (2, 6). es 5–1Z (puesto que x2 5 5–1Z cuando x15 0). El hecho de que la pendiente esté fija en 25–3 significa que todas las rectas construidas de esta manera son paralelas. De nuevo, si se comparan las rectas 10 5 3x1 1 5x2 y 20 5 3x1 1 5x2 en la figura 3.3, es posible observar que la recta que da el valor mayor de Z (Z 5 20) se encuentra más lejos del origen hacia arriba que la otra recta (Z 5 10). Este hecho también está implícito en la forma de pendiente-orde- nada al origen de la función objetivo, lo que indica que la intersección con el eje x1 (5–1Z) aumenta cuando crece el valor seleccionado de Z. Estas observaciones implican que el procedimiento de prueba y error para construir las rectas de la figura 3.3 involucra sólo dibujar una familia de rectas paralelas que contengan al menos un punto en la región factible y elegir la que corresponda al mayor valor de Z. La figura 3.3 muestra que esta recta pasa por el punto (2, 6), lo cual indica que la solución óptima es x1 5 2 y x2 5 6. La ecuación de esta recta es 3x1 1 5x2 5 3(2) 1 5(6) 5 36 5 Z, lo cual indica que el valor óptimo de Z es Z 5 36. El punto (2, 6) se encuentra en la intersección de las dos rectas 2x2 5 12 y 3x1 1 2x2 5 18, que se muestra en la figura 3.2, por lo que el punto se puede calcular de manera algebraica como la solución simultánea de estas dos ecuaciones. Una vez estudiado el procedimiento de prueba y error para encontrar el punto óptimo (2, 6) es posible seguir los pasos de este método en otros problemas. En lugar de dibujar varias rectas paralelas, es suficiente marcar una de ellas con una regla para establecer la pendiente y después mover la regla con pendiente fija sobre la región factible en la dirección en que Z mejora. (Cuando el objetivo sea minimizar Z la regla deberá moverse en la dirección en que Z decrece.) La regla se deja de mover en el momento en que todavía pasa por un punto de esta región. Este punto es la solución óptima deseada. Con frecuencia se hace referencia a este procedimiento como el método gráfico de progra- mación lineal. Se puede usar para resolver cualquier problema de programación lineal con dos variables de decisión. Con alguna dificultad es posible extender el método a tres variables de decisión, pero no más de tres. (En el siguiente capítulo se estudia el método símplex para resolver problemas más grandes.) Conclusiones El equipo de IO utilizó este procedimiento para encontrar que la solución óptima deseada es x1 5 2, x2 5 6, con Z 5 36. Esta solución indica que la Wyndor Glass Co. debe fabricar los produc- tos 1 y 2 a una tasa de 2 y 6 lotes por semana, respectivamente, con una ganancia total resultante de 36 000 dólares semanales. No existe otra mezcla de los dos productos que sea tan reditua- ble, de acuerdo con el modelo. www.elsolucionario.net  3.2 MODELO DE PROGRAMACIÓN LINEAL 27 No obstante, en el capítulo 2 se puso de manifiesto que un buen estudio de investigación de operaciones no sólo encuentra una solución para el modelo inicial formulado. Cada una de las seis etapas que se describieron es importante, incluso las pruebas exhaustivas del modelo (vea la sección 2.4) y el análisis posóptimo (sección 2.3). Si reconoce la totalidad de estas realidades prácticas, el equipo de IO está listo para evaluar la validez del modelo de una manera más crítica (esta explicación continuará en la sección 3.3), y para llevar a cabo un análisis de sensibilidad sobre el efecto que tendría el hecho de que las estimaciones dadas en la tabla 3.1 fueran diferentes debido a inexactitudes, cambios en las circunstancias, etc. (Este tema continuará en la sección 6.7.) Continuación del proceso de aprendizaje con OR Courseware Éste es el primero de muchos puntos en los cuales será útil emplear el OR Courseware que se en- cuentra en el CD que acompaña al libro. Un programa clave en este CD es el llamado OR Tutor que contiene un ejemplo de demostración completo del método gráfico que se estudia en esta sección. Esta demostración comienza por la introducción de un problema y la formulación de un modelo de programación lineal, antes de aplicar el método gráfico para resolverlo, con la intención de propor- cionar un ejemplo adicional de formulación de un modelo. Al igual que muchos otros ejemplos de demostración en otras secciones, éste resalta los conceptos que son difíciles de explicar en una página impresa. En el apéndice 1 se puede consultar la documentación sobre el software. Si el lector desea ver más ejemplos puede consultar la sección de problemas resueltos —Worked Examples— en el sitio web del libro. Esta sección incluye unos cuantos ejemplos con soluciones completas para casi todos los capítulos, así como un complemento de los ejemplos del libro y del OR Tutor. Los ejemplos de este capítulo comienzan con un problema relativamente directo que implica la formulación de un pequeño modelo de programación lineal y la aplicación del método gráfico. Los ejemplos siguientes implicarán de manera progresiva un reto mayor. Otra parte clave del OR Courseware es un programa llamado IOR Tutorial. Éste realiza mu- chos procedimientos interactivos para ejecutar los diferentes métodos de solución que se presentan en el libro, lo que permite que el lector se enfoque en el aprendizaje y la ejecución de la lógica del método en forma eficiente, mientras que la computadora realiza los cálculos numéricos. Se incluye un procedimiento interactivo para aplicar el método gráfico en la programación lineal. Una vez que se haya captado este primer procedimiento, un segundo enfoque permite aplicar con rapidez el método gráfico para desarrollar análisis de sensibilidad sobre el efecto de cambios en los datos del problema. Después, es posible imprimir los trabajos y resultados como una tarea. Como los otros procedimientos del IOR Tutorial, éstos están específicamente diseñados para proporcionar al lector una experiencia de aprendizaje eficiente, amena y enriquecedora mientras realiza sus tareas. Cuando se formule un modelo de programación lineal con más de dos variables de decisión, por lo que no puede usarse el método gráfico, el método símplex descrito en el capítulo 4 permi- tirá encontrar una solución óptima de inmediato. Obtenerla también es útil para la validación del modelo puesto que encontrar una solución sin sentido indica que se cometieron errores en la formulación del modelo. En la sección 1.4 se mencionó que el OR Courseware es una introducción a los tres paquetes de software comerciales que más se usan —Excel Solver, LINGO/LINDO y MPL/CPLEX— para resolver una variedad de modelos de IO. Los tres paquetes incluyen el método símplex para resol- ver problemas de programación lineal. En la sección 3.5 se describe cómo usar Excel para formular y resolver modelos de programación lineal en el formato de una hoja de cálculo. Las descripciones de los otros paquetes se proporcionan en la sección 3.6 —MPL y LINGO—, los suplementos 1 y 2 de este capítulo en el sitio web del libro —LINGO—, la sección 4.8 —CPLEX y LINDO— y el apéndice 4.1 —LINDO—. Además, el OR Courseware incluye un archivo para cada uno de los tres paquetes que muestra cómo se puede usar para resolver los ejemplos en este capítulo. 3.2 MODELO DE PROGRAMACIÓN LINEAL El problema de la Wyndor Glass Co. se diseñó para ilustrar un problema común de programación lineal, en versión simplificada. Sin embargo, esta técnica es muy versátil como para describirla mediante un solo ejemplo. En esta sección se presentarán las características generales de los pro- blemas de programación lineal y las distintas formas legítimas del modelo matemático. www.elsolucionario.net 28 CAPÍTULO 3 INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL TABLA 3.2 Terminología común de programación lineal Ejemplo modelo Problema general Capacidad de producción de las plantas Recursos 3 plantas m recursos Fabricación de productos Actividades 2 productos n actividades Tasa de producción del producto j, xj Nivel de actividad j, xj Ganancia Z Medida global de desempeño Z Comenzaremos por establecer la terminología y notación básicas. La primera columna de la tabla 3.2 resume los componentes del problema de la Wyndor Glass Co. La segunda introduce términos más generales de estos componentes, que se ajustarán a muchos problemas de programa- ción lineal. Los términos clave son recursos y actividades en los que m denota el número de tipos de recursos que se pueden usar y n el número de actividades que se consideran. Algunos ejem- plos de recursos son dinero y tipos especiales de maquinaria, equipo, vehículos y personal. Los ejemplos de actividades incluyen inversión en proyectos específicos, publicidad en un medio de- terminado y el envío de bienes de cierta fuente a cierto destino. En cualquier aplicación de pro- gramación lineal es posible que todas las actividades sean de un tipo general (como cualquiera de estos tres ejemplos), a consecuencia de lo cual cada una correspondería en forma individual a las alternativas específicas dentro de esta categoría general. Como se describió en la introducción del capítulo, el tipo más usual de aplicación de progra- mación lineal involucra la asignación de recursos a ciertas actividades. La cantidad disponible de cada recurso es limitada, de forma que debe asignarse con todo cuidado. La determinación de esta asignación implica elegir los niveles de las actividades que lograrán el mejor valor posible de la medida global de desempeño. Ciertos símbolos se usan de manera convencional para denotar los diversos componentes de un modelo de programación lineal. Estos símbolos se enumeran a continuación, junto con su interpretación para el problema general de asignación de recursos a actividades. Z 5 valor de la medida global de desempeño. xj 5 nivel de la actividad j (para j 5 1, 2,... , n). cj 5 incremento en Z que se obtiene al aumentar una unidad en el nivel de la actividad j. bi 5 cantidad de recurso i disponible para asignarse a las actividades (para i 5 1, 2,... , m). aij 5 cantidad del recurso i consumido por cada unidad de la actividad j. El modelo plantea el problema en términos de tomar decisiones sobre los niveles de las actividades, por lo que x1, x2,... , xn se llaman variables de decisión. Como se resume en la tabla 3.3, los valores TABLA 3.3 Datos necesarios para elaborar un modelo de programación lineal para manejar la asignación de recursos a actividades Consumo de recursos por unidad de actividad Actividad Cantidad de Recurso 1 2... n recursos disponibles 1 a11 a12... a1n b1 2 a21 a22... a2n b2.................. m a m1 am2... amn bm Contribución a Z por c1 c2... cn unidad de actividad www.elsolucionario.net 3.2 MODELO DE PROGRAMACIÓN LINEAL 29 de cj, bi y aij (para i 5 1, 2,... , m y j 5 1, 2,... , n) son las constantes de entrada al modelo. Las cj, bi y aij también se conocen como parámetros del modelo. Observe la correspondencia entre la tabla 3.3 y la tabla 3.1. Una forma estándar del modelo Para proceder con el problema de la Wyndor Glass Co., ahora se puede formular el modelo mate- mático del problema general de asignar recursos a actividades. En particular, este modelo consiste en elegir valores de x1, x2,... , xn para Maximizar Z ⫽ c1x1 ⫹ c2x2 ⫹... ⫹ cnxn , sujeta a las restricciones a11x1 ⫹ a12x2 ⫹... ⫹ a1nxn ⱕ b1 a21x1 ⫹ a22x2 ⫹... ⫹ a2nxn ⱕ b2 o am1x1 ⫹ am2x2 ⫹... ⫹ amnxn ⱕ bm , y x1 ⱖ 0, x2 ⱖ 0,... , xn ⱖ 0. Ésta es llamada nuestra forma estándar1 del problema de programación lineal. Cualquier situación cuya formulación matemática se ajuste a este modelo es un problema de programación lineal. Observe que el modelo del problema de la Wyndor Glass Co. se ajusta a la forma estándar con m 5 3 y n 5 2. En este momento se puede resumir la terminología común de los modelos de programación lineal. La función que se desea maximizar, c1x1 1 c2x2 1 · · · 1 cnxn, se llama función objetivo. Por lo general, se hace referencia a las limitaciones como restricciones. Las primeras m restricciones (aquellas con una función de todas las variables ai1x1 1 ai2x2 1 · · · 1 ainxn en el lado izquierdo) a veces reciben el nombre de restricciones funcionales (o restricciones estructurales). De manera parecida, las restricciones xj $ 0 se conocen como restricciones de no negatividad (o condiciones de no negatividad). Otras formas Debe hacerse notar que el modelo anterior no se ajusta a la forma natural de algunos problemas de programación lineal. Las otras formas legítimas son las siguientes: 1. Minimizar en lugar de maximizar la función objetivo: Minimizar Z ⫽ c1x1 ⫹ c2x2 ⫹... ⫹ cnxn. 2. Algunas restricciones funcionales con desigualdad en sentido mayor o igual que: ai1x1 ⫹ ai2x2 ⫹... ⫹ ainxn ⱖ bi para algunos valores de i. 3. Algunas restricciones funcionales en forma de ecuación: ai1x1 ⫹ ai2x2 ⫹... ⫹ ainxn ⫽ bi para algunos valores de i. 4. Algunas variables de decisión sin la restricción de no negatividad: xj no está restringida en su signo para algunos valores de j. Cualquier problema que incluye una, varias o todas estas formas con las otras partes del modelo anterior también se clasifica como un problema de programación lineal. La interpretación de las palabras asignación de recursos limitados entre actividades que compiten puede ya no aplicarse 1 Se llama nuestra forma estándar en lugar de la forma estándar porque otros libros adoptan formas distintas. www.elsolucionario.net 30 CAPÍTULO 3 INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL muy bien, si es que se aplica; pero sin importar cuál sea la interpretación o el contexto, lo único necesario es que la formulación matemática del problema se ajuste a las formas permitidas. Así, la definición concisa de un problema de programación lineal es que cada componente de su modelo se ajusta a la forma estándar o a una de las otras formas legítimas que ya se mencionaron. Terminología de las soluciones del modelo Puede ser que el lector esté acostumbrado a que el término solución signifique la respuesta final a un problema, pero en programación lineal (y sus extensiones) la convención es bastante distinta. Ahora, cualquier conjunto de valores específicos de las variables de decisión (x1, x2,... , xn) se llama una solución, aunque sea sólo una posibilidad deseable o ni siquiera permitida. Después se identifican los tipos de soluciones mediante el empleo de un adjetivo apropiado. Una solución factible es aquella para la que todas las restricciones se satisfacen. Una solución no factible es una solución para la que al menos una restricción se viola. En el ejemplo, los puntos (2, 3) y (4, 1) de la figura 3.2 son soluciones factibles, mientras que (21, 3) y (4, 4) son soluciones no factibles. La región factible es la reunión de todas las soluciones factibles. En el ejemplo, la región factible es toda el área sombreada de la figura 3.2. Es posible que un problema no tenga soluciones factibles. Esto habría ocurrido si se hubiera requerido que los nuevos productos tuvieran un rendimiento neto de 50 000 dólares semanales por lo menos, para justificar la interrupción de la fabricación de la línea actual. La restricción correspondiente, 3x1 1 5x2 $ 50, hubiera eliminado por completo la región factible, con lo que ninguna mezcla de nuevos productos sería superior a la situación actual. Este caso se ilustra en la figura 3.4. Dado que existen soluciones factibles, la meta de la programación lineal es encontrar una solución factible que sea la mejor, medida por el valor de la función objetivo en el modelo. Una solución óptima es una solución factible que proporciona el valor más favorable de la función objetivo. FIGURA 3.4 El problema de la Wyn- x2 dor Glass Co. no tendría soluciones óptimas si se le 10 Maximizar Z 5 3x1 1 5x2, sujeta a x1 #4 agregara la restricción 2x2 # 12 3x1 1 5x2 $ 50. 3x1 1 5x2 $ 50 3x1 1 2x2 # 18 3x1 1 5x2 $ 50 8 y x1 $ 0, x2 $ 0 6 2x2 # 12 4 3x1 1 2x2 # 18 x1 $ 0 2 x1 # 4 x2 $ 0 0 2 4 6 8 10 x1 www.elsolucionario.net  3.2 MODELO DE PROGRAMACIÓN LINEAL 31 El valor más favorable significa el valor más grande si la función objetivo debe maximizarse, o el valor más pequeño si la función objetivo debe minimizarse. La mayor parte de los problemas tendrá nada más una solución óptima. Sin embargo, también es posible tener más de una. Esto ocurriría en el ejemplo si la ganancia por lote producido del pro- ducto 2 se cambiara a 2 000 dólares. Este hecho cambiaría la función objetivo a Z 5 3x1 1 2x2, de manera que todos los puntos sobre el segmento de recta que va de (2, 6) a (4, 3) serían soluciones óptimas, situación que se ilustra en la figura 3.5. Igual que en este caso, cualquier problema que tenga soluciones óptimas múltiples tendrá un número infinito de ellas, todas con el mismo valor de la función objetivo. Otra posibilidad es que el problema no tenga soluciones óptimas, lo cual ocurre sólo si: 1) no tiene soluciones factibles, o 2) las restricciones no impiden que el valor de la función objetivo (Z) mejore indefinidamente en la dirección favorable (positiva o negativa). Este caso se conoce como un problema con Z no acotada u objetivo no acotado. El último caso sería cierto si, por error, en el ejemplo se omitieran las últimas dos restricciones funcionales del modelo, lo cual se ilustra en la figura 3.6. Ahora se introducirá un tipo especial de soluciones factibles que tiene un papel importante cuando el método símplex trata de encontrar una solución óptima. Una solución factible en un vértice (FEV) es una solución que se encuentra en una esquina de la región factible. (Las soluciones FEV también se conocen como puntos extremos o esquinas, pero preferimos la terminología más sugerente de vértice.) La figura 3.7 pone de relieve cinco soluciones factibles en los vértices del ejemplo. En las secciones 4.1 y 5.1 se analizarán varias propiedades útiles de las soluciones FEV para problemas de cualquier tamaño, incluso la siguiente relación con las soluciones óptimas. Relación entre las soluciones óptimas y las soluciones FEV: Considere cualquier pro- blema de programación lineal con soluciones factibles y una región factible acotada. El problema debe poseer soluciones FEV y al menos una solución óptima. Además, la mejor solución FEV debe ser una solución óptima. Entonces, si un problema tiene exactamente una solución óptima, ésta debe ser una solución FEV. Si el problema tiene múltiples so- luciones óptimas, al menos dos deben ser soluciones FEV. FIGURA 3.5 x2 El problema de la Wyndor Glass Co. tendría múltiples 10 Maximizar Z 5 3x1 1 2x2, soluciones óptimas si la Z 518 5 3x1 1 2x2 x1 #4 sujeta a función objetivo se cam- 2x2 # 12 biara a Z 5 3x1 1 2x2. 3x1 1 2x2 # 18 8 y x1 $ 0, x2 $ 0 6 Cada punto en este segmento de línea 4 oscura es óptimo, cada uno con Z 5 18. Región factible 2 0 2 4 6 8 10 x1 www.elsolucionario.net 32 CAPÍTULO 3 INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL (4, `), Z 5 ` x2 10 (4, 10), Z 5 62 Maximizar Z 5 3x1 1 5x2, 8 (4, 8), Z 5 52 sujeta a x1 # 4 y x1 $ 0, x2 $ 0 6 (4, 6), Z 5 42 Región factible FIGURA 3.6 4 (4, 4), Z 5 32 El problema de la Wyndor Glass Co. no tendría solu- ciones óptimas si la única restricción funcional fuera 2 (4, 2), Z 5 22 x1 # 4, puesto que x2 podría aumentar de modo indefinido en la región factible sin llegar a un valor máximo de Z 5 3x1 1 5x2. 0 2 4 6 8 10 x1 El ejemplo tiene exactamente una solución óptima, (x1, x2) 5 (2, 6), que es FEV. (Considérese la forma como el método gráfico que conduce a la solución óptima que es FEV.) Cuando se modifica el ejemplo para que tenga soluciones óptimas múltiples, como se muestra en la figura 3.5, dos de estas soluciones óptimas —(2, 6) y (4, 3)— son soluciones factibles en los vértices. 3.3 SUPUESTOS DE PROGRAMACIÓN LINEAL En realidad, todos los supuestos de programación lineal están implícitos en la formulación del modelo que se presentó en la sección 3.2. En particular, desde un punto de vista matemático, los supuestos simplemente son que el modelo debe tener una función objetivo lineal sujeta a restricciones lineales. Sin embargo, desde el punto de vista de modelación, estas propiedades FIGURA 3.7 x2 Los puntos indican las cinco soluciones FEV para (0, 6) (2, 6) el problema de la Wyndor Glass Co. Región factible (4, 3) (0, 0) (4, 0) x1 www.elsolucionario.net 3.3 SUPUESTOS DE PROGRAMACIÓN LINEAL 33 TABLA 3.4 Ejemplos de proporcionalidad satisfecha o violada Ganancia del producto 1 ($000 por semana) Proporcionalidad violada Proporcionalidad x1 satisfecha Caso 1 Caso 2 Caso 3 0 0 0 0 0 1 3 2 3 3 2 6 5 7 5 3 9 8 12 6 4 12 11 18 6 matemáticas de un modelo de programación lineal implican que se deben considerar ciertos su- puestos acerca de las actividades y datos del problema que será modelado, incluso algunos acerca del efecto de las variaciones en el nivel de las actividades. Vale la pena hacer hincapié en ellas para que sea más sencillo evaluar si esta técnica es adecuada para un problema dado. Aún más, es necesario analizar por qué el equipo de IO de la Wyndor Glass Co. concluyó que la formulación de programación lineal proporcionaba una representación satisfactoria del problema. Proporcionalidad La proporcionalidad es un supuesto sobre la función objetivo y sobre las restricciones funcionales, como se resume a continuación. Supuesto de proporcionalidad: La contribución de cada actividad al valor de la función objetivo Z es proporcional al nivel de la actividad xj, como lo representa el término cjxj en la función objetivo. De manera similar, la contribución de cada actividad al lado izquierdo de cada restricción funcional es proporcional al nivel de la actividad xj, como lo repre- senta en la restricción el término aijxj. En consecuencia, este supuesto elimina cualquier exponente diferente de 1 para las variables en cualquier término de las funciones —ya sea la función objetivo o la función en el lado izquierdo de las restricciones funcionales— en un modelo de programación lineal.2 Para ilustrar este supuesto, considere el primer término (3x1) en la función objetivo (Z 5 3x1 1 5x2) del problema de la Wyndor Glass Co. Este término representa la ganancia generada por semana (en miles de dólares) cuando se fabrica el producto 1 a una tasa de x1 lotes por semana. La columna de proporcionalidad satisfecha de la tabla 3.4 muestra el caso que se supuso en la sección 3.1, esto es, que la ganancia sin duda es proporcional a x1 de manera que 3x1 es el término apropiado de la función objetivo. Por el contrario, las siguientes tres columnas muestran casos hipotéticos diferentes en los que el supuesto de proporcionalidad no se cumple. Vea primero la columna del caso 1 en la tabla 3.4. Este caso surgiría si se tuvieran costos fijos asociados al arranque de la fabricación del producto 1. Por ejemplo, es posible que existan costos debidos a la preparación de las instalaciones de producción. También puede haber costos asociados con el arreglo de la distribución del nuevo producto. Como se trata de costos en los que se incurre una sola vez, deben amortizarse cada semana para que sean conmensurables con Z (ganancia en miles de dólares por semana). Suponga que se hace esta amortización y que los costos de prepa- ración o fijos totales significan una reducción de 1 en el valor de Z, la ganancia, sin considerar los costos fijos es de 3x1. Esto quiere decir que la contribución del producto 1 a Z es 3x1 2 1 para x1. 0, mientras que la contribución es 3x1 5 0 cuando x1 5 0 (no hay costo fijo). Esta función de ganancias,3 dada por la curva continua en la figura 3.8, sin duda no es proporcional a x1. 2 Cuando la función incluye algún término de producto cruzado, la proporcionalidad debe interpretarse en el sentido de que los cambios en el valor de la función son proporcionales a los cambios en cada variable (xj) en forma individual, dados cualesquiera valores fijos para las otras variables. Por lo tanto, un término de producto cruzado satisface la propor- cionalidad siempre que cada variable del término tenga un exponente de 1. (Sin embargo, cualquier término de producto cruzado viola el supuesto de aditividad que se estudiará en seguida.) 3 Si la contribución del producto 1 a la función Z fuera 3x1 2 1 para toda x1 $ 0, incluso x1 5 0, entonces la constante fija, 21, se podría eliminar de la función objetivo sin cambiar la solución óptima y se restablecería la proporcionalidad. Sin embargo, en este caso no es posible, ya que la constante 21 no se aplica si x1 5 0. www.elsolucionario.net 34 CAPÍTULO 3 INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL Contribución de x1 a Z 12 9 Satisface el supuesto de proporcionalidad 6 Viola el supuesto de proporcionalidad FIGURA 3.8 La curva continua viola el 3 supuesto de proporcionali- dad debido al costo fijo en que se incurre cuando x1 0 1 2 3 4 x1 aumenta desde cero. Los Costo de inicio valores de los puntos están dados en la columna del 23 caso 1 de la tabla 3.4. A primera vista, podría parecer que el caso 2 de la tabla 3.4 es bastante parecido al caso 1. Pero el hecho es que el caso 2 surge de forma muy diferente. No existe un costo fijo y la ganan- cia generada por la primera unidad del producto 1 por semana, por supuesto, es de 3 dólares, como se supuso en un principio. Pero ahora se tiene un rendimiento marginal creciente; es decir, la pendiente de la función de ganancia del producto 1 (vea la curva continua de la figura 3.9) crece a medida que x1 aumenta. Esta violación de la proporcionalidad puede ocurrir debido a economías de escala que en ocasiones se pueden lograr en niveles altos de producción, por ejemplo, a través del uso de maquinaria más eficiente para altos volúmenes, corridas de producción más grandes, descuentos por cantidad por compras grandes de materia prima y por el efecto de la curva de aprendizaje debido a la cual los trabajadores son cada vez más eficientes a medida que adquieren experiencia en un trabajo de producción dado. Cuando el costo incremental disminuye, la ganancia incremental aumenta si se supone un ingreso marginal constante. FIGURA 3.9 Contribución La curva continua viola el de x1 a Z 18 supuesto de proporciona- lidad porque su pendiente (el rendimiento marginal 15 del producto 1) sigue en crecimiento a medida que x1 aumenta. Los valores de Viola el 12 supuesto de los puntos están dados en proporcionalidad la columna del caso 2 de la tabla 3.4. 9 Satisface el supuesto de 6 proporcionalidad 3 0 1 2 3 4 x1 www.elsolucionario.net  3.3 SUPUESTOS DE PROGRAMACIÓN LINEAL 35 Contribución de x1 a Z 12 Satisface el FIGURA 3.10 supuesto de La curva continua viola el 9 proporcionalidad supuesto de proporciona- lidad porque su pendiente (el rendimiento marginal 6 del producto 1) sigue en decadencia a medida que Viola el 3 supuesto de x1 aumenta. Los valores de proporcionalidad los puntos están dados en la columna del caso 3 de la tabla 3.4. 0 1 2 3 4 x1 De nuevo, según los datos de la tabla 3.4, el caso contrario del 2 es el caso 3, en el que existe un rendimiento marginal decreciente. En este caso, la pendiente de la función de ganancia del produc- to 1 (dada por la curva continua de la figura 3.10) disminuye conforme x1 aumenta. Esta violación de la proporcionalidad puede ocurrir debido a que los costos de marketing tienen que elevarse más que proporcionalmente para lograr aumentos del nivel de ventas. Por ejemplo, tal vez el producto 1 se pueda vender a una tasa de 1 por semana (x1 5 1) sin publicidad, mientras que lograr ventas que sostengan una tasa de producción de x1 5 2 puede requerir una publicidad moderada, para x1 5 3 es posible que sea necesaria una extensa campaña publicitaria y para x1 5 4 puede requerirse también una disminución de precios. Los tres casos son ejemplos hipotéticos de la forma en que el supuesto de proporcionalidad puede no cumplirse. ¿Cuál es la situación real? La ganancia real al fabricar el producto 1 (o cual- quier otro) se deriva del ingreso por ventas menos los distintos costos directos e indirectos. Es inevitable que algunos de estos componentes de costos no sean estrictamente proporcionales a las tasas de producción, tal vez por alguna de las razones que se expusieron. Sin embargo, la pregunta importante es si después de acumular todos los componentes de ganancia, la proporcionalidad es una aproximación razonable del modelado. En el problema de la Wyndor Glass Co., el equipo de IO verificó tanto la función objetivo como las restricciones funcionales. La conclusión fue que sin duda podía suponerse la proporcionalidad sin distorsiones serias. ¿Qué ocurre cuando el supuesto no se cumple, ni siquiera como una aproximación razonable? En la mayor parte de los casos, esto significa que se debe emplear programación no lineal (vea el capítulo 12). Sin embargo, en la sección 12.8 se señala que cierta clase importante de falta de proporcionalidad se puede manejar mediante programación lineal a través de la reelaboración del problema de manera adecuada. Aún más, si se viola el supuesto nada más debido a los costos fijos, existe una extensión de la programación lineal (programación entera mixta) que se puede usar, presentada en la sección 11.3 (el problema de costos fijos). Aditividad Aunque el supuesto de proporcionalidad elimina los exponentes diferentes de uno, no prohíbe los términos de productos cruzados, términos que incluyen el producto de dos o más variables. El supuesto de aditividad elimina esta posibilidad, como se ve a continuación. Supuesto de aditividad: Cada función de un modelo de programación lineal (ya sea la función objetivo o el lado izquierdo de las restricciones funcionales) es la suma de las contribuciones individuales de las actividades respectivas. Para que esta definición sea más concreta y aclare por qué es necesario preocuparse por este supuesto se analizarán algunos ejemplos. En la tabla 3.5 se muestran algunos casos posibles de la función objetivo del problema de la Wyndor Glass Co. En cada caso, las contribuciones individua- les de los productos son las que se supusieron en la sección 3.1, es decir, 3x1 para el producto 1 y 5x2 para el producto 2. La diferencia estriba en el último renglón que da el valor de la función de www.elsolucionario.net 36 CAPÍTULO 3 INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL TABLA 3.5 Ejemplos que satisfacen o violan la aditividad de la función objetivo Valor de Z Aditividad violada (x1, x2) Aditividad satisfecha Caso 1 Caso 2 (1, 0) 3 3 3 (0, 1) 5 5 5 (1, 1) 8 9 7 Z cuando se fabrican los dos productos de manera conjunta. La columna de aditividad satisfecha muestra el caso en el que este valor de la función se obtiene simplemente mediante la suma de los dos primeros renglones (3 1 5 5 8), es decir, Z 5 3x1 1 5x2, como se supuso antes. Por el contra- rio, las columnas que siguen muestran casos hipotéticos en los que el supuesto de aditividad queda violado, pero no el de proporcionalidad. De acuerdo con la columna del caso 1 de la tabla 3.5, se tiene una función objetivo de Z 5 3x1 1 5x2 1 x1x2, de manera que Z 5 3 1 5 1 1 5 9 para (x1, x2) 5 (1, 1), lo que viola el supuesto de aditividad de que Z 5 3 1 5. (El supuesto de proporcionalidad todavía se satisface puesto que si se fija el valor de una variable, el incremento de Z debido a la otra variable es proporcional al valor de esa variable.) Este caso surge si los dos productos son complementarios de alguna forma en que la ganancia aumenta. Por ejemplo, suponga que es necesaria una campaña publicitaria importante para comercializar cualquiera de los dos productos por sí solos, pero que la misma campaña puede promover de manera eficaz ambos productos. Como se ahorra un costo alto del segundo producto, la ganancia conjunta será algo más que la suma de sus ganancias individuales si se producen por separado. El caso 2 de la tabla 3.5 también viola el supuesto de aditividad debido al término adicional en su función objetivo, Z 5 3x1 1 5x2 2 x1x2, de forma que Z 5 3 1 5 2 1 5 7 para (x1, x2) 5 (1, 1). Al contrario del primer caso, el caso 2 surge cuando los dos productos son competitivos de algún modo en que su ganancia conjunta disminuye. Por ejemplo, suponga que ambos productos deben usar la misma maquinaria y equipo. Si se produce cada uno por sí solo, maquinaria y equipo se dedican a este único uso. Sin embargo, cuando son fabricados ambos productos, se requiere cambiar los procesos de producción de uno a otro, con tiempo y costos involucrados en la inte- rrupción temporal de la producción de uno y la preparación del otro. Debido a este costo adicional importante, su ganancia conjunta será algo menor que la suma de sus ganancias individuales si se les produce por separado. El mismo tipo de interacción de actividades puede afectar la aditividad de las funciones de restricción. Por ejemplo, considere la tercera restricción del problema de la Wyndor Glass Co., 3x1 1 2x2 # 18. (Ésta es la única restricción que incluye ambos productos.) Esta restricción se refiere a la capacidad de producción de la planta 3, en la que se dispone de 18 horas semanales de producción para los dos nuevos productos, mientras que la función del lado izquierdo (3x1 1 2x2) representa el número de horas de producción semanales que se usarían en estos productos. La columna de aditividad satisfecha de la tabla 3.6 muestra este caso, mientras que las dos columnas siguientes exponen casos en los que la función tiene un término adicional de producto cruzado que TABLA 3.6 Ejemplos de aditividad satisfecha o violada de una restricción funcional Cantidad de recurso usado Aditividad satisfecha (x1, x2) Aditividad violada Caso 3 Caso 4 (2, 0) 6 6 6 (0, 3) 6 6 6 (2, 3) 12 15 10.8 www.elsolucionario.net 3.3 SUPUESTOS DE PROGRAMACIÓN LINEAL 37 viola la aditividad. En las tres columnas, las contribuciones individuales de los productos en cuanto al uso de la capacidad de la planta 3 son las que se supusieron, es decir, 3x1 para el producto 1 y 2x2 para el producto 2, o sea, 3(2) 5 6, para x1 5 2 y 2(3) 5 6 para x2 5 3. Igual que en la tabla 3.5, la diferencia estriba en el último renglón que ahora da el valor total de la función para el tiempo de producción que se utiliza cuando se fabrican los dos productos de manera conjunta. En el caso 3 (vea la tabla 3.6), el tiempo de producción para los dos productos está dado por la función 3x1 1 2x2 1 0.5x1x2, de manera que el valor total de la función es 6 1 6 1 3 5 15 cuando (x1, x2) 5 (2, 3), lo que viola el supuesto de aditividad de que el valor es sólo 6 1 6 5 12. Este caso puede surgir justo de la misma forma que se describió en el caso 2 (tabla 3.5): tiempo adi- cional desperdiciado en el cambio de procesos de producción entre los dos productos. El término adicional de producto cruzado (0.5x1x2) representa el tiempo de producción desperdiciado en esta forma. (Observe que el desperdicio de tiempo al cambiar de un producto a otro da por resultado, en este caso, un término positivo de producto cruzado en donde la función total mide el tiempo de producción utilizado, mientras que lleva a un término negativo de producto cruzado en el caso 2 puesto que esa función total mide la ganancia.) En el caso 4 de la tabla 3.6, la función de la capacidad que se usa es 3x1 1 2x2 2 0.1x12x2, por lo que el valor de la función para (x1, x2) 5 (2, 3) es 6 1 6 2 1.2 5 10.8. Este caso surge de la siguiente manera. Igual que en el caso 3, suponga que los dos productos requieren el mismo tipo de maquinaria y equipo, pero que ahora el tiempo para cambiar de un producto a otro es relativamente pequeño. Como cada producto pasa por una serie de operaciones, las instalaciones de producción individual, que por lo general se dedican a ese producto, tendrían algunos tiempos ociosos. Estas instalaciones podrían utilizarse durante estos tiempos en otros productos. En consecuencia, el tiempo total de producción usado cuando se fabrican en forma conjunta los dos productos, es menor que la suma de los tiempos de producción usados por los productos individuales cuando se fabrican por separado. Después de analizar los tipos posibles de interacción de los dos productos ilustrados en estos cuatro casos, el equipo de IO concluyó que ninguno tenía un papel importante en el problema real de la Wyndor Glass Co. Por lo tanto, el supuesto de aditividad se adoptó como una aproximación razonable. En otros problemas, si la aditividad no es un supuesto razonable, de forma que algunas o todas las funciones matemáticas del modelo necesariamente son no lineales (debido a términos de pro- ducto cruzado), resulta definitiva la entrada en el ámbito de la programación no lineal (capítulo 12). Divisibilidad El siguiente supuesto se refiere a los valores permitidos para las variables de decisión. Supuesto de divisibilidad: En un modelo de programación lineal, las variables de deci- sión pueden tomar cualquier valor, incluso valores no enteros, que satisfagan las restric- ciones funcionales y de no negatividad. En consecuencia, estas variables no están restrin- gidas a sólo valores enteros. Como cada variable de decisión representa el nivel de alguna actividad, se supondrá que las actividades se pueden realizar a niveles fraccionales. En el problema de la Wyndor Glass Co., las variables de decisión representan tasas de pro- ducción (número de lotes de un producto fabricados a la semana). Como estas tasas pueden tomar cualquier valor fraccional dentro de la región factible, el supuesto de divisibilidad se cumple. En ciertas situaciones, el supuesto de divisibilidad no se cumple porque algunas o todas las variables de decisión deben restringirse a valores enteros. Los modelos matemáticos con esta res- tricción, que se llaman modelos de programación entera, se estudiarán en el capítulo 11. Certidumbre El último supuesto se refiere a los parámetros del modelo, es decir, a los coeficientes cj, en la fun- ción objetivo, los coeficientes aij, en las restricciones funcionales y los bi en el lado derecho de las restricciones funcionales. Supuesto de certidumbre: Se supone que los valores asignados a cada parámetro de un modelo de programación lineal son constantes conocidas. www.elsolucionario.net 38 CAPÍTULO 3 INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL En los problemas reales, el supuesto de certidumbre casi nunca se satisface por completo. Por lo general se formula un modelo de programación lineal para elegir un curso de acción futuro. En este caso, los valores de los parámetros que se emplean están basados en una predicción de las condiciones futuras, lo que es inevitable que introduzca cierto grado de incertidumbre. Por esta razón, siempre es importante realizar un análisis de sensibilidad después de encon- trar una solución óptima de los valores supuestos de los parámetros. Como se presentó en la sección 2.3, el propósito general es identificar los parámetros sensibles (es decir, aquellos cuyo valor no puede cambiar mucho sin cambiar la solución óptima), debido a que un cambio mayor en el valor de un parámetro sensible de inmediato envía la señal de la necesidad de introducir un cambio en la solución usada. El análisis de sensibilidad tiene un papel importante en el problema de la Wyndor Glass Co., como se verá en la sección 6.7. De cualquier manera, es necesario adquirir algunos conocimientos adicionales antes de terminar esta historia. En algunos casos, el grado de incertidumbre en los parámetros es demasiado grande para que el análisis de sensibilidad lo pueda manejar. En estas situaciones es necesario establecer, en forma explícita, estos parámetros como variables aleatorias. Se han desarrollado formulaciones de este tipo, que se pueden consultar en las secciones 23.6 y 23.7 del sitio web del libro. Los supuestos en perspectiva En la sección 2.2 se hizo hincapié en que el modelo matemático intenta ser sólo una representación idealizada del problema real. Por lo general se requieren aproximaciones y los supuestos de sim- plificación para que el modelo se pueda manejar. Agregar demasiados detalles y precisión puede hacer que el modelo sea difícil de manipular para llevar a cabo un análisis útil del problema. En realidad, todo lo que se necesita es que exista una correlación relativamente alta entre la predicción del modelo y lo que de hecho pasaría en el problema real. Este consejo sin duda es aplicable a la programación lineal. Es muy frecuente en las aplica- ciones reales de esta técnica que casi ninguno de los cuatro supuestos se cumpla. Excepto, quizá, en el caso del supuesto de divisibilidad, deben esperarse pequeñas disparidades. Esto es cierto en especial para el supuesto de certidumbre, de manera que es normal que deba aplicarse el análisis de sensibilidad para compensar la violación de este supuesto. Sin embargo, es importante que el equipo de IO examine los cuatro supuestos en el problema que se estudia y analice el tamaño de las disparidades. Si cualquiera de los supuestos es violado de manera importante, es necesario disponer de varios modelos alternativos, como se verá en capí- tulos posteriores de este libro. Una desventaja de estos modelos es que los algoritmos disponibles para resolverlos no son tan poderosos como el de programación lineal, pero en algunos casos este inconveniente se ha solucionado. En algunas aplicaciones se utiliza el poderoso enfoque de programación lineal para el análisis inicial y después un modelo más complejo para perfeccionar el análisis. Al trabajar los ejemplos de la siguiente sección se demostrará que el análisis del grado en que se cumplen los cuatro supuestos de la programación lineal es una buena práctica. 3.4 EJEMPLOS ADICIONALES El problema de la Wyndor Glass Co. es un ejemplo prototípico de programación lineal en varios aspectos: comprende la asignación de recursos limitados entre actividades que compiten por ellos, su modelo se ajusta a la forma estándar y su contexto es el tradicional de planeación para mejorar la administración. Sin embargo, la aplicación de la programación lineal es mucho más extensa. Esta sección comienza por ampliar el horizonte. Al estudiar los siguientes ejemplos observe que se caracterizan como problemas de programación lineal por el modelo matemático, más que por su contexto. Luego, debe considerarse que el mismo modelo matemático surge en muchos otros contextos con sólo cambiar los nombres de las actividades. Estos ejemplos son versiones simplificadas de aplicaciones reales. Como el problema de Wyndor y el ejemplo de demostración del problema gráfico en el OR Tutor, el primero de estos ejemplos tiene sólo dos variables de decisión, de manera que puede ser resuelto mediante el mé- todo gráfico. Ahora se trata de un problema de minimización y tiene una mezcla de formas para www.elsolucionario.net  3.4 EJEMPLOS ADICIONALES 39 las restricciones funcionales. (Este ejemplo simplifica de manera considerable la situación real de diseñar una terapia de radiación, pero el primer Recuadro de aplicación en esta sección describe el emocionante impacto que en realidad está teniendo la IO en esta área.) Los ejemplos subsecuen- tes tienen muchas más de dos variables de decisión y por lo tanto son más difíciles de formular. Aunque se mencionarán las soluciones óptimas que se obtienen por medio del método símplex, en esta sección el enfoque se concentra en la manera de formular el modelo de programación lineal para estos problemas más grandes. En las secciones subsecuentes y en el capítulo siguiente se dará mayor importancia a las herramientas de software y al algoritmo (método símplex) que se utiliza para resolver dichos problemas. Si el lector considera que requiere ejemplos adicionales de formulación de modelos de pro- gramación lineal pequeños y relativamente directos antes de tratar con los ejemplos de formulación más grandes, se le sugiere regresar al caso de demostración del método gráfico en el OR Tutor y a los ejemplos en la sección de Worked Examples de este capítulo en el sitio web del libro. Diseño de terapia de radiación Acaban de diagnosticar que Mary padece cáncer en una etapa bastante avanzada. Específicamente, tiene un tumor grande en el área de la vejiga, una “lesión que afecta a toda la vejiga”. Mary recibirá los cuidados médicos más avanzados disponibles, para proporcionarle la mejor posibilidad de supervivencia. Estos cuidados incluyen una terapia de radiación extensa. La terapia implica el uso de una máquina de rayos externos que envía radiación ionizante a través del cuerpo de la paciente y daña tanto los tejidos cancerosos como los sanos. Es normal que se administren los rayos con precisión desde diferentes ángulos en un plano de dos dimensiones. Debido a la atenuación, cada rayo descarga más radiación sobre el tejido cercano al punto de entrada que sobre el cercano al punto de salida. La dispersión también provoca que parte de la radiación se descargue sobre tejidos que están fuera de la trayectoria directa del rayo. Debido a que las células del tumor casi siempre se encuentran diseminadas entre células sanas, la dosis de radiación a través de la región del tumor debe ser suficiente para matar las células malignas que son un poco más sensibles a ella, pero suficientemente pequeña para no matar a las células sanas. Al mismo tiempo, la dosis acumulada que reciben los tejidos críticos no debe exceder los niveles de tolerancia establecidos, con el objeto de prevenir complicaciones que puedan resultar más serias que la enfermedad misma. La dosis completa que recibe el cuerpo sano debe minimizarse. Debido a la necesidad de balancear con cuidado todos estos factores, el diseño de la terapia de radiación es un proceso muy delicado. La meta principal de este diseño es elegir la combinación de rayos que se utilizará y la intensidad de cada uno para generar la mejor distribución posible de la dosis. (La fuerza de la dosis en cualquier punto del cuerpo se mide en unidades llamadas kilorads.) Una vez diseñado el tratamiento, se administra en muchas sesiones durante varias semanas. En el caso de Mary, el tamaño y la localización del tumor hacen que el diseño de su tratamiento FIGURA 3.11 sea un proceso más delicado que lo usual. La figura 3.11 muestra un diagrama de un corte trans- Corte transversal del tumor versal del tumor visto desde arriba, al igual que los tejidos cercanos críticos que deben evitarse. de Mary (visto desde Estos tejidos incluyen órganos vitales —por ejemplo, el recto— y estructura ósea —el fémur y la arriba), cerca de tejidos pelvis— que atenuarán la radiación. Además, se muestra el punto de entrada y la dirección de los críticos y de los rayos de únicos dos rayos que se pueden usar en este caso con un grado relativamente moderado de segu- radiación usados. ridad. (El ejemplo se ha simplificado en este punto, pero en la realidad se consideran docenas de rayos posibles.) Rayo 2 En el caso de cualquier rayo propuesto de una cierta intensidad, el análisis para determinar 1 cuál sería la absorción de radiación resultante por distintas partes del cuerpo requiere desarrollar un 3 3 difícil proceso. En resumen, con base en un análisis anatómico cuidadoso, la distribución de energía 2 dentro de un corte transversal de dos dimensiones se puede graficar en un mapa de isodosis en el que las curvas representan la fuerza de la dosis como un porcentaje de la fuerza de ésta en el punto de entrada. Después, se coloca una red fina sobre dicho mapa. Si se suma la radiación absorbida Rayo 1 en los cuadros que contienen cada tipo de tejido, se puede calcular la dosis promedio que absorbe 1. Vejiga y tumor el tumor, los tejidos sanos y los tejidos críticos. La absorción de la radiación es aditiva cuando se 2. Recto, cóccix, etc. 3. Fémur, parte de administra más de un rayo (en forma secuencial). la pelvis, etc. Después de un análisis exhaustivo, el equipo médico estimó con detalle los datos necesarios para el diseño del tratamiento de Mary, cuyo resumen se presenta en la tabla 3.7. La primera co- lumna presenta una lista de las áreas del cuerpo que deben considerarse y las dos siguientes pro- www.elsolucionario.net  Recuadro de aplicación 40 CAPÍTULO 3 INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL El cáncer de próstata es la forma más común de cáncer diag- minutos mediante un sistema de planeación computarizado nosticada en hombres. Se estima que en 2007 hubo 220 000 que puede ser operado con facilidad por el personal médico nuevos casos sólo en Estados Unidos. Como muchas otras cuando comienza el procedimiento de insertar las semillas en formas de esta enfermedad, la terapia de radiación es un mé- la próstata del paciente. todo común de tratamiento para el cáncer de próstata, cuya Este procedimiento para optimizar la aplicación de la meta es tener una dosis de radiación suficientemente alta en radioterapia para el cáncer de próstata ha teniendo un efecto la región del tumor para matar las células malignas al mismo profundo tanto en los costos del cuidado de la salud como en tiempo que se minimiza la exposición a la radiación de estruc- la calidad de vida de los pacientes que reciben el tratamiento turas sanas críticas cercanas al tumor. Este tratamiento puede debido a su alta eficacia y a la reducción sustancial de los aplicarse a través de una terapia de radiación de rayo externo efectos colaterales. Se estima que cuando todas las clínicas (como se ilustra en el primer ejemplo en esta sección) o radio- de Estados Unidos adopten este procedimiento, los ahorros en terapia, la cual implica colocar alrededor de 100 “semillas” costos anuales serán de alrededor de 500 millones de dólares, radiactivas dentro de la región del tumor. El reto consiste en debido a la eliminación de la necesidad de una reunión para determinar el patrón geométrico tridimensional más eficaz planear el tratamiento y una exploración posterior a la ope- para colocarlas. ración, así como porque proporciona un procedimiento qui- El Memorial Sloan-Kettering Cancer Center (MS- rúrgico más eficiente y reduce la necesidad de tratar efectos KCC) en Nueva York es el centro para el tratamiento del cán- colaterales subsecuentes. También se anticipa que este enfo- cer más antiguo del mundo. Un equipo de IO del Centro para que puede extenderse a otras formas de radioterapia, como el la Investigación de Operaciones en Medicina y Cuidado de tratamiento del cáncer de seno, cérvix, esófago, tracto biliar, la Salud del Georgia Institute of Technology trabajó con mé- páncreas, cabeza y cuello, y ojo. dicos del MSKCC para desarrollar un método vanguardista Esta aplicación de la programación lineal y sus extensio- altamente complejo para optimizar la aplicación de radiotera- nes llevaron al equipo de IO a ganar en 2007 el primer lugar pia al cáncer de próstata. El modelo subyacente se ajusta a la en la competencia internacional por el Premio Franz Edelman estructura para programación lineal con una excepción. Ade- al desempeño en investigación de operaciones y ciencias de más de tener las variables continuas comunes que se ajustan la administración. a la programación lineal, el modelo también incluye algunas variables binarias (variables cuyos únicos valores posibles Fuente: E. K. Lee y M. Zaider, “Operations Research Advances son 0 y 1). (Este tipo de extensión de la programación lineal Cancer Therapeutics”, en Interfaces, 38(1): 5-25, enero-febrero, a la cual se le llama programación entera mixta se explicará 2008. (En nuestro sitio web, www.mhhe.com/hillier, se propor- en el capítulo 11.) La optimización se hace en cuestión de ciona un vínculo con este artículo.) porcionan la fracción de la dosis de radiación de cada rayo en el punto de entrada que se absorbe en promedio en las áreas respectivas. Por ejemplo, si el nivel de la dosis en el punto de entrada del rayo 1 es 1 kilorad, se absorberán 0.4 kilorad en toda la anatomía sana en el plano de dos dimensiones, un promedio de 0.3 kilorad en los tejidos críticos cercanos, un promedio de 0.5 kilorad en las distintas partes del tumor y 0.6 kilorad en el centro del tumor. La última columna presenta las restricciones sobre la dosis total de ambos rayos que se absorbe en promedio en las diferentes partes del cuerpo. En particular, la absorción promedio de la dosis por la anatomía sana debe ser tan pequeña como sea posible, los tejidos críticos no deben exceder 2.7 kilorads, el promedio sobre todo el tumor debe ser igual a 6 kilorads y en el centro del tumor debe ser por lo menos de 6 kilorads. TABLA 3.7 Datos para el diseño del tratamiento de radiación de Mary Fracción de la dosis de entrada absorbida por área (promedio) Área Rayo 1 Rayo 2 Restricción sobre la dosis promedio total, kilorads Anatomía sana 0.4 0.5 Minimizar Tejido crítico 0.3 0.1 ⱕ 2.7 Región del tumor 0.5 0.5 ⫽ 6 Centro del tumor 0.6 0.4 ⱖ 6 www.elsolucionario.net 3.4 EJEMPLOS ADICIONALES 41 Formulación como un problema de programación lineal. Las decisiones que de- ben hacerse son las dosis de radiación en los dos puntos de entrada. Por lo tanto, las dos variables de decisión x1 y x2 representan la dosis (en kilorads) en el punto de entrada de los rayos 1 y 2, res- pectivamente. Como debe minimizarse la dosis total que llega a la anatomía sana, se definirá como Z a esta cantidad. En este punto se pueden usar los datos de la tabla 3.7 para formular el siguiente modelo de programación lineal.4 Minimizar Z ⫽ 0.4x1 ⫹ 0.5x2 , sujeta a 0.3x1 ⫹ 0.1x2 ⱕ 2.7 0.5x1 ⫹ 0.5x2 ⫽ 6 0.6x1 ⫹ 0.4x2 ⱖ 6 y x1 ⱖ 0, x2 ⱖ 0. Observe las diferencias entre este modelo y el que se presentó en la sección 3.1 para la Wyndor Glass Co. Este último involucraba maximizar Z, y todas las restricciones funcionales tenían la for- ma #. El nuevo modelo incorpora otras tres formas legítimas descritas en la sección 3.2; a saber: minimizar Z, restricciones funcionales de la forma 5, y restricciones funcionales de la forma $. Sin embargo, ambos modelos tienen sólo dos variables, de manera que este nuevo problema también se puede resolver por el método gráfico que se ilustró en la sección 3.1. La figura 3.12 muestra la solución gráfica. La región factible consiste nada más en el segmento entre los puntos (6, 6) y (7.5, 4.5), ya que los puntos en este segmento son los únicos que satisfacen todas las restric- ciones al mismo tiempo. (Observe que la restricción de igualdad limita la región factible a la recta que contiene este segmento y las otras restricciones funcionales determinan los puntos extremos del segmento.) La línea punteada representa la función objetivo que pasa por la solución óptima (x1, x2) 5 (7.5, 4.5) con Z 5 5.25. Esta solución es óptima y no (6, 6) porque disminuir Z (para valores positivos de Z) empuja la función objetivo hacia el origen (donde Z 5 0). Y Z 5 5.25 pa- ra (7.5, 4.5) es menor que Z 5 5.4 para (6, 6). En consecuencia, el diseño óptimo implica utilizar una dosis total en el punto de entrada de 7.5 kilorads para el rayo 1 y 4.5 kilorads para el rayo 2. Planeación regional La CONFEDERACIÓN SUR DE KIBBUTZIM está formada por tres kibbutzim (comunidades agrícolas comunales) de Israel. La planeación global de este grupo se hace en su oficina de coordi- nación técnica. En la actualidad planean la producción agrícola para el año próximo. La producción agrícola está limitada tanto por la extensión de terreno disponible para irriga- ción como por la cantidad de agua que la Comisión de Aguas (una oficina del gobierno nacional) asigna para irrigarlo. La tabla 3.8 contiene los datos. Los tipos de cultivos adecuados para la región incluyen remolacha, algodón y sorgo, que son precisamente los tres que están en estudio para la estación venidera. Los cultivos difieren primordialmente en su rendimiento neto esperado por acre y en su consumo de agua. Además, el Ministerio de Agricultura ha establecido una cantidad máxima de acres que la Confederación puede dedicar a estos cultivos. La tabla 3.9 muestra estas cantidades. 4 Este modelo es mucho más pequeño del que normalmente se necesitaría para aplicaciones reales. Para obtener mejores resultados, un modelo realista podría incluso requerir muchas decenas de miles de variables de decisión y restricciones. Por ejemplo, vea H. E. Romeijn, R. K. Ahuja, J. F. Dempsey y A. Kumar, “A New Linear Programming Approach to Radiation Therapy Treatment Planning Problems”, en Operations Research, 54(2): 201-216, marzo-abril de 2006. Para enfoques alternativos que combinan programación lineal con otras técnicas de IO (como en el primer Recuadro de apli- cación de esta sección), también vea G. J. Lim, M. C. Ferris, S. J. Wright