5 ejercicios clásicos de programación lineal y sus resultados

 A continuación se presentan cinco ejercicios clásicos de programación lineal y sus resultados:

    Maximización de la ganancia en una empresa:

Un fabricante quiere maximizar su ganancia produciendo dos tipos de productos, A y B. Para producir una unidad del producto A, se necesitan 2 horas de trabajo y se obtiene una ganancia de $3. Para producir una unidad del producto B, se necesitan 3 horas de trabajo y se obtiene una ganancia de $2. La empresa solo tiene 400 horas disponibles para producir. ¿Cuántas unidades de cada producto deben producirse para maximizar la ganancia?

Solución:

La función a maximizar es: 3x + 2y, donde x es el número de unidades del producto A y y el número de unidades del producto B.

Los límites son: 2x + 3y ≤ 400 (por las horas disponibles) y x, y ≥ 0 (porque no se pueden producir unidades negativas).

El problema se puede resolver mediante el método gráfico, obteniendo los siguientes resultados:

x = 100 unidades

y = 133.3 unidades

La ganancia máxima es de $533.

    Problema de asignación: dado un conjunto de tareas y un conjunto de trabajadores, asignar cada tarea a un trabajador de tal manera que se minimice el costo total.

Ejemplo:

Tareas: T1, T2, T3, T4

Trabajadores: W1, W2, W3

Costos:

| T1 | T2 | T3 | T4 |

W1| 2 | 6 | 7 | 5 |

W2| 3 | 4 | 8 | 6 |

W3| 5 | 7 | 3 | 2 |

Solución: asignar T1 a W1, T2 a W2, T3 a W3 y T4 a W1. El costo total sería 17

    Problema del viajero de comercio: dado un conjunto de ciudades y las distancias entre ellas, encontrar el camino más corto para visitar todas las ciudades y regresar a la ciudad de origen.

Ejemplo:

Ciudades: C1, C2, C3, C4

Distancias (en millas):

| C1 | C2 | C3 | C4 |

C1| 0 | 2 | 5 | 7 |

C2| 2 | 0 | 4 | 1 |

C3| 5 | 4 | 0 | 6 |

C4| 7 | 1 | 6 | 0 |

Solución: visitar las ciudades en el siguiente orden: C1, C2, C4, C3, C1. La distancia total sería 14 millas.

    Problema de transporte: dado un conjunto de fábricas y un conjunto de tiendas, determinar la cantidad de productos que deben ser enviados de cada fábrica a cada tienda para satisfacer la demanda de productos de cada tienda y minimizar el costo total.

Ejemplo:

Fábricas: F1, F2

Tiendas: T1, T2, T3

Demanda de productos:

| T1 | T2 | T3 |

F1| 2 | 3 | 1 |

F2| 1 | 2 | 3 |

Costos (por unidad):

| T1 | T2 | T3 |

F1| 3 | 4 | 5 |

F2| 4 | 3 | 6 |

Solución: enviar 2 unidades de F1 a T1, 3 unidades de F1 a T2, 1 unidad de F1 a T3, 1 unidad de F2 a T1 y 2 unidades de F2 a T2. El costo total sería 27.

Asignación de trabajos a trabajadores:

Una empresa quiere asignar trabajos a sus trabajadores de manera que maximice su productividad. Cada trabajador tiene una habilidad diferente para realizar cada tipo de trabajo, y se sabe cuánto tiempo se tarda en realizar cada trabajo. ¿Cuántos trabajos de cada tipo deben asignarse a cada trabajador para maximizar la productividad?

Solución:

La función a maximizar es: 2x + 3y + 4z, donde x, y y z representan el número de trabajos de cada tipo que se asignan a cada trabajador.

Los límites son: x + y + z ≤ 10 (por el número total de trabajos disponibles) y x, y, z ≥ 0 (porque no se pueden asignar trabajos negativos).

El problema se puede resolver mediante el método gráfico, obteniendo los siguientes resultados:

x = 2 trabajos

y = 4 trabajos

z = 4 trabajos

La productividad máxima es de 26

¿Qué es la Programación Lineal?

 La programación lineal es una técnica matemática utilizada para encontrar la solución óptima a problemas que involucran la maximización o minimización de una función lineal sujeta a un conjunto de restricciones lineales.

Un problema de programación lineal se puede escribir en la forma siguiente:

Maximizar o minimizar:

z = cx

sujeto a:

ax ≤ b

donde "z" es la función objetivo que se quiere maximizar o minimizar, "c" y "x" son vectores de coeficientes y variables, respectivamente, y "a" y "b" son vectores de coeficientes que representan las restricciones.

¿Qué es la investigación de operaciones?

 La investigación de operaciones es una disciplina que se ocupa del estudio y la aplicación de técnicas y herramientas matemáticas y computacionales para la toma de decisiones en situaciones que involucran la optimización de procesos y sistemas. Esta disciplina se aplica en diversos campos, como la ingeniería, la economía, la psicología, la biología y la administración de empresas, entre otros.

La investigación de operaciones se utiliza para resolver problemas que involucran la optimización de recursos y la toma de decisiones en situaciones de incertidumbre. Por ejemplo, puede ser utilizada para determinar la mejor forma de producir un producto de manera más eficiente, o para diseñar una red de distribución que minimice los costos de transporte. También puede ser utilizada para modelar sistemas complejos y predecir su comportamiento en el futuro.

En resumen, la investigación de operaciones es una disciplina que utiliza técnicas matemáticas y computacionales para ayudar a tomar decisiones en situaciones de incertidumbre y optimizar la utilización de recursos.

Panorama del enfoque de modelado - PROBLEMA 19

 Lea la referencia seleccionada 7. Resuma el punto de vista del autor sobre el papel de la observación y la experimentación en el proceso de validación del modelo.

Panorama del enfoque de modelado - PROBLEMA 18

 Consulte las páginas 18-20 del artículo al que se hace referencia en el pie de página de la sección 2.2 que describe un estudio de IO realizado para el Rijkswaterstaat, de Holanda. Describa una lección importante aprendida con la validación del modelo en este estudio.

Panorama del enfoque de modelado - PROBLEMA 17

2.3-1. Lea la referencia seleccionada 5.

a) Describa el punto de vista del autor sobre el hecho de que la única meta al usar un modelo debe ser encontrar su solución óptima.

b) Resuma el punto de vista del autor sobre los papeles complementarios del modelado, la evaluación de la información obtenida y la aplicación del juicio del tomador de decisiones para determinar un curso de acción.

Panorama del enfoque de modelado - PROBLEMA 16

 Lea la referencia seleccionada 5.

a) Identifique el ejemplo del autor sobre un modelo de las ciencias naturales y uno de IO.

b) Describa el punto de vista del autor sobre la manera en que los principios básicos del uso de modelos para realizar investigación en ciencias naturales puede usarse para guiar la investigación sobre las operaciones (IO).

Panorama del enfoque de modelado - PROBLEMA 15

 Lea el artículo al que se hace referencia en el pie de página de la sección 2.5 que describe un estudio de IO realizado para Texaco.

a) Resuma los antecedentes que llevaron a emprender este estudio.

b) Describa brevemente la interfaz del usuario con el sistema de apoyo a las decisiones OMEGA desarrollado como resultado de este estudio.

c) OMEGA se actualiza y amplía en forma constante para reflejar los cambios en el ambiente de las operaciones. Describa los distintos tipos de cambios realizados.

d) Resuma cómo se usa el sistema OMEGA.

e) Enumere los distintos beneficios tangibles e intangibles que resultaron de este estudio.

Panorama del enfoque de modelado - PROBLEMA 14

 Lea las páginas 603-617 de la referencia seleccionada 3.

a) ¿Qué dice el autor sobre el hecho de que un modelo se puede validar por completo?

b) Resuma la diferencia entre validación del modelo, de los datos, validación lógica/matemática, predictiva, operativa y dinámica.

c) Describa el papel del análisis de sensibilidad en la validación operativa de un modelo.

d) ¿Qué dice el autor sobre la existencia de una metodología de validación adecuada para todos los modelos?

e) Cite la página del artículo que enumera los pasos básicos para la validación.

Panorama del enfoque de modelado - PROBLEMA 13

 2.4-2. Lea la referencia seleccionada 7. Resuma el punto de vista del autor sobre el papel de la observación y la experimentación en el proceso de validación del modelo.

Panorama del enfoque de modelado - PROBLEMA 12

 Consulte las páginas 18-20 del artículo al que se hace referencia en el pie de página de la sección 2.2 que describe un estudio de IO realizado para el Rijkswaterstaat, de Holanda. Describa una lección importante aprendida con la validación del modelo en este estudio.

Panorama del enfoque de modelado - PROBLEMA 11

 2.3-1. Lea la referencia seleccionada 5.

a) Describa el punto de vista del autor sobre el hecho de que la única meta al usar un modelo debe ser encontrar su solución óptima.

b) Resuma el punto de vista del autor sobre los papeles complementarios del modelado, la evaluación de la información obtenida y la aplicación del juicio del tomador de decisiones para determinar un curso de acción.

Panorama del enfoque de modelado - PROBLEMA 10

 Lea la referencia seleccionada 5.

a) Identifique el ejemplo del autor sobre un modelo de las ciencias naturales y uno de IO.

b) Describa el punto de vista del autor sobre la manera en que los principios básicos del uso de modelos para realizar investigación en ciencias naturales puede usarse para guiar la investigación sobre las operaciones (IO).

Panorama del enfoque de modelado - PROBLEMA 9

Lea el artículo al que se hace referencia en el pie de página de la sección 2.5 que describe un estudio de IO realizado para Texaco.

a) Resuma los antecedentes que llevaron a emprender este estudio.

b) Describa brevemente la interfaz del usuario con el sistema de apoyo a las decisiones OMEGA desarrollado como resultado de este estudio.

c) OMEGA se actualiza y amplía en forma constante para reflejar los cambios en el ambiente de las operaciones. Describa los distintos tipos de cambios realizados.

d) Resuma cómo se usa el sistema OMEGA.

e) Enumere los distintos beneficios tangibles e intangibles que resultaron de este estudio.

Panorama del enfoque de modelado - PROBLEMA 8

 Lea las páginas 603-617 de la referencia seleccionada 3.

a) ¿Qué dice el autor sobre el hecho de que un modelo se puede validar por completo?

b) Resuma la diferencia entre validación del modelo, de los datos, validación lógica/matemática, predictiva, operativa y dinámica.

c) Describa el papel del análisis de sensibilidad en la validación operativa de un modelo.

d) ¿Qué dice el autor sobre la existencia de una metodología de validación adecuada para todos los modelos?

e) Cite la página del artículo que enumera los pasos básicos para la validación.

Panorama del enfoque de modelado - PROBLEMA 7

 Lea la referencia seleccionada 7. Resuma el punto de vista del autor sobre el papel de la observación y la experimentación en el proceso de validación del modelo.

Panorama del enfoque de modelado - PROBLEMA 6

Consulte las páginas 18-20 del artículo al que se hace referencia en el pie de página de la sección 2.2 que describe un estudio de IO realizado para el Rijkswaterstaat, de Holanda. Describa una lección importante aprendida con la validación del modelo en este estudio.

Panorama del enfoque de modelado - PROBLEMA 5

 Lea la referencia seleccionada 5.

a) Describa el punto de vista del autor sobre el hecho de que la única meta al usar un modelo debe ser encontrar su solución óptima.

b) Resuma el punto de vista del autor sobre los papeles complementarios del modelado, la evaluación de la información obtenida y la aplicación del juicio del tomador de decisiones para determinar un curso de acción.

Panorama del enfoque de modelado - PROBLEMA 4

 Lea la referencia seleccionada 5.

a) Identifique el ejemplo del autor sobre un modelo de las ciencias naturales y uno de IO.

b) Describa el punto de vista del autor sobre la manera en que los principios básicos del uso de modelos para realizar investigación en ciencias naturales puede usarse para guiar la investigación sobre las operaciones (IO).

Panorama del enfoque de modelado - PROBLEMA 3

 Lea el artículo al que se hace referencia en el pie de página de la sección 2.2 que describe un estudio de IO realizado para el Rijkswaterstaat de Holanda. (Preste atención especial en las páginas 3-20 y 30-32.)

a) Resuma los antecedentes que llevaron a emprender este estudio.

b) Resuma el objetivo de cada uno de los cinco modelos matemáticos descritos en las páginas 10-18.

c) Resuma las “medidas de efecto” (medidas de desempeño) para comparar las políticas descritas en las páginas 6-7 de este artículo.

d) Enumere los distintos beneficios tangibles e intangibles que resultaron de este estudio.

Panorama del enfoque de modelado - PROBLEMA 2

 Lea el artículo al que se hace referencia en el pie de página de la sección 2.1 que describe un estudio de IO realizado para el Departamento de Salud de New Haven, Connecticut.

a) Resuma los antecedentes que llevaron a emprender este estudio.

b) Describa el sistema desarrollado para rastrear y probar cada aguja y cada jeringa con el fin de reunir los datos necesarios.

c) Resuma los resultados iniciales de este sistema de rastreo y pruebas.

d) Describa el efecto real y potencial de este estudio en las políticas gubernamentales.

Panorama del enfoque de modelado - PROBLEMA 1

 2.1-1. Lea el artículo al que hace referencia el pie de página de la sección 2.1 que describe un estudio de IO realizado para el Departamento de Policía de San Francisco.

a) Resuma los antecedentes que llevaron a emprender este estudio.

b) Defina parte del problema a que se refieren las seis metas del sistema de programación a desarrollar.

c) Describa cómo fueron recolectados los datos necesarios.

d) Enumere los distintos beneficios tangibles e intangibles resultado del estudio.

Panorama del enfoque de modelado - REFERENCIAS SELECCIONADAS

 1. Bradley P. S., U. M. Fayyad y O. L. Mangasarian, “Mathematical Programming for Data Mining: Formulations and Challenges”, en INFORMS Journal of Computing, 11(3): 217-238, verano de 1999.

2. Fortuin, L., P. van Beek y L. van Wassenhove (eds.), OR at wORk: Practical Experiences of Operational Research, Taylor & Francis, Bristol, PA, 1996.

3. Gass, S. I., “Decision-Aiding Models: Validation, Assessment, and Related Issues for Policy Analysis”, en Operations Research, 31: 603-631, 1983.

4. Gass, S. I., “Model World: Danger, Beware the User as Modeler”, en Interfaces, 20(3): 60-64, mayo-junio de 1990.

5. Hall, R.W., “What's So Scientific about MS/OR?”, en Interfaces, 15(2): 40-45, marzo-abril de 1985.

6. Howard, R. A., “The Ethical OR/MS Professional”, en Interfaces, 31(6): 69-82, noviembre-diciembre de 2001.

7. Miser, H. J., “The Easy Chair: Observation and Experimentation”, en Interfaces. 19(5): 23-30, septiembre-octubre de 1989.

8. Morris, W. T., “On the Art of Modeling”, en Management Science, 13: B707-717, 1967.

9. Murphy, F. H., “The Occasional Observer: Some Simple Precepts for Project Success”, en Interfaces, 28(5): 25-28, septiembre-octubre de 1998.

10. Pidd, M., “Just Modeling Through: A Rough Guide to Modeling”, en Interfaces, 29(2): 118-132, marzo-abril de 1999.

11. Simon, H. A., “Prediction and Prescription in Systems Modeling”, en Operations Research, 38:7-14, 1990.

12. Williams, H. P., Model Building in Mathematical Programming, 4a. ed., Wiley, Nueva York, 1999.

Panorama del enfoque de modelado - CONCLUSIONES

 Aunque el resto de este libro se enfoca principalmente en la construcción y solución de modelos matemáticos, en este capítulo se intentó hacer hincapié en que esos elementos sólo son una porción del proceso completo necesario para llevar a cabo un estudio de IO representativo. Las otras etapas que se describieron son también muy importantes para el éxito del estudio. Se pide al lector que en los capítulos subsecuentes no pierda de vista el papel que tienen el modelo y el procedimiento de solución dentro del proceso completo. Después, cuando haya adquirido una comprensión más profunda de los modelos matemáticos, se sugiere que planee regresar y revisar este capítulo con el fin de profundizar en esta perspectiva.

La investigación de operaciones está ligada en forma íntima al empleo de computadoras. Hasta hace poco, se usaban casi exclusivamente computadoras grandes, pero cada vez es mayor el uso de las computadoras personales y estaciones de trabajo para resolver modelos de IO.

Para concluir la presentación de las etapas más importantes de un estudio de IO, debe observarse que existen muchas excepciones a las “reglas” prescritas en este capítulo. Por su naturaleza, la investigación de operaciones requiere una gran dosis de ingenio e innovación, por lo que es imposible prescribir un procedimiento estándar que los equipos de IO deban seguir siempre. En su lugar, la descripción anterior debe verse como un modelo que representa, a grandes rasgos, cómo llevar a cabo un estudio exitoso de investigación de operaciones.

FORMULACIÓN DE UN MODELO MATEMÁTICO - IMPLEMENTACIÓN - Ejemplo 4

El último ejemplo se refiere al sistema SYSNET de Yellow Freight, descrito al final de la sección anterior, cuyo objetivo era establecer rutas de envíos en una red nacional. En este caso, hubo cuatro elementos importantes. El primero fue “vender” el concepto a la alta administración. Este paso se realizó con éxito cuando se validó la exactitud del modelo de costos y se realizaron sesiones interactivas para la alta administración que demostraron la eficacia del sistema. El segundo fue el desarrollo de una estrategia de implementación por etapas graduales, a la vez que se identificaban y eliminaban las fallas. El tercero fue el trabajo conjunto con los administradores operativos para instalar el sistema en forma adecuada, proporcionar las herramientas de apoyo necesarias, capacitar al personal que lo usaría y convencerlos de su utilidad. El último elemento fue proporcionar a la administración los incentivos y el refuerzo para la implementación efectiva del sistema.

FORMULACIÓN DE UN MODELO MATEMÁTICO - IMPLEMENTACIÓN - Ejemplo 3

 El siguiente ejemplo ilustra cómo, en ocasiones, una fase de implementación exitosa requiere el involucramiento de miles de empleados antes de poner en marcha los nuevos procedimientos. Samsung Electronics Corp.1 inició un importante estudio de IO en marzo de 1996 para desarrollar nuevas metodologías y programar el calendario de aplicaciones que pudieran incrementar el nivel de eficiencia de todo el proceso de manufactura de semiconductores y reducir el nivel de inventarios de productos en proceso. El estudio continuó por más de cinco años y llegó a su fin en junio de 2001, debido, principalmente, al gran esfuerzo que requirió la etapa de implementación. El equipo de IO debió obtener el apoyo de muchos integrantes de las áreas de administración, manufactura e ingeniería; dicho apoyo lo obtuvo mediante la capacitación del personal en los principios y la lógica de los nuevos procedimientos de manufactura. Al final del proceso, más de 3 000 personas habían asistido a las sesiones de capacitación. Después, los nuevos procedimientos fueron incorporados de manera gradual para construir la confianza en ellos. Este paciente proceso de implementación pagó grandes dividendos. Los nuevos procedimientos hicieron que la compañía se convirtiera de la manufacturera menos eficiente de la industria de los semiconductores en la más eficiente. Este logro incrementó las ganancias en más de 1 000 millones de dólares en el momento en que se completó el estudio de IO.

FORMULACIÓN DE UN MODELO MATEMÁTICO - IMPLEMENTACIÓN - Ejemplo 2

 El siguiente ejemplo se refiere al estudio para IBM expuesto al final de las secciones 2.4 y 2.5. En este caso se requirió una planeación cuidadosa para poner en marcha el complejo sistema Optimizer para controlar la red nacional de inventarios de refacciones. Fueron considerados tres factores especialmente importantes para lograr una implementación exitosa. Como se estudió en la sección 2.4, el primero era la inclusión de un equipo de usuarios —formado por administradores operativos— como consejeros del equipo de IO durante el estudio. Cuando llegó la etapa de implementación, estos administradores operativos sentían que el estudio también era de ellos, por lo que se convirtieron en un fuerte apoyo para la instalación de Optimizer en sus áreas funcionales. El segundo factor de éxito fue una extensa prueba de aceptación del usuario mediante la cual pudieron identificar áreas problemáticas que necesitaban modificaciones antes de la implementación total. El tercer factor fue que el nuevo sistema se puso en marcha por etapas, en cada una de las cuales se realizaron pruebas cuidadosas, con lo que las fallas más importantes fueron eliminadas antes de la implementación nacional del sistema.

FORMULACIÓN DE UN MODELO MATEMÁTICO - IMPLEMENTACIÓN - Ejemplo 1

 Este último punto sobre la documentación de un estudio de IO se ilustra con el caso de la política nacional de administración del agua del Rijkswaterstaat, en Holanda (véase las secciones 2.2, 2.3 y 2.4). La administración deseaba documentación más extensa que lo normal, tanto para apoyar la nueva política como para utilizarla en la capacitación de nuevos analistas o para realizar nuevos estudios. La integración de esta documentación requirió varios años y ¡quedó contenida en 4 000 páginas a espacio sencillo encuadernadas en 21 volúmenes!