• Author / Uploaded
• Jesús Alfredo Escalona

Citation preview

UNIVERSIDAD NACIONAL EXPERIMENTAL POLITECNICA ANTONIO JOSE DE SUCRE VICERRECTORADO BARQUISIMETO

DIRECCION DE INVESTIGACION Y POSTGRADO MAESTRIA EN INGENIERIA INDUSTRIAL METODOS DE OPTIMIZACION

Prof. Víctor Bernal P.

Contenido

Capítulo 1.

Introducción

7

1.

La Investigación de Operaciones: El concepto

7

2.

La Investigación de Operaciones: El desarrollo

8

3.

Clasificación de los problemas de Investigación Operativa

8

3.1.

Clasificación según el objetivo del problema

9

3.2.

Clasificación según la certidumbre de los datos

9

4.

Metodología de la Investigación Operativa

10

Paso 1. Definición del problema

11

Paso 2. Modelado matemático

11

Paso 3. Resolución del modelo

12

Paso 4. Presentación/Implementación de los resultados

13

Capítulo 2. 1.

La programación lineal

15

Formulación de problemas

15

1.1.

El problema del transporte

16

1.2.

Ejemplo: El problema del transporte

17

1.3.

El problema del transporte: La solución computacional

19

1.4.

El problema de la dieta

19

1.5.

Ejemplo: El problema de la dieta

20

1.6.

El problema de la dieta: La solución computacional

21

1.6.1.

El paquete LPSOLVE

21

1.6.2.

El paquete LINGO

22

1.7.

El problema de la planificación de la producción

23

1.8.

Ejemplo: El problema de la planificación de la producción

24

1.9.

Planificación de la producción: La solución computacional

25

El paquete MAPLE

26

1.10.

26

El problema de flujo en una red 3

1.11.

Ejemplo: El problema de flujo en redes

27

1.12.

El problema de la cartera de valores

32

1.13.

Ejemplo del problema de la cartera

33

1.14.

El problema de las ocho damas

34

2.

Formulación matemática del problema

37

2.1.

La forma general del problema

38

2.2.

La forma estándar del problema

38

2.3.

Transformación en la forma estándar

39

2.4.

Ejemplos de conversión

39

2.5.

Soluciones básicas

40

3.

Ejercicios

Capítulo 3. 1. 1.1. 2.

41

El método SIMPLEX

47

Introducción

47

Ejemplo ilustrativo

49

Descripción del método

51

2.1.

Los pasos del método Simplex

53

2.2.

Ejemplo

54

2.3.

El significado de zk − ck

55

2.4.

La forma matricial del método Simplex

56

2.5.

La tabla del simplex

56

3.

El problema dual

57

3.1.

Origen del problema dual

57

3.2.

La definición del problema dual

59

3.3.

Obtención del dual en la forma estándar

60

3.4.

Construcción del problema dual

60

3.5.

Ejemplo de conversión al dual

61

3.6.

Ejemplo de interpretación del problema dual

61

3.7.

El dual y el programa LINGO

63

4.

Análisis de sensibilidad

64

4.1.

Cambios en los costos de las variables básicas

64

4.2.

Cambios en los costos de las variables no básicas

65

4.3.

Cambios en los términos independientes

66

5.

El método SIMPLEX REVISADO

67

5.1.

Actualización de la fila de la función objetivo

67

5.2.

Determinación de la variable que sale de la base

67

5.3.

Actualización de la base

67

5.4.

Eficiencia en el almacenamiento

68

Prof. Victor Bernal

OPTIMIZACION

Pág. 4 de 131

6.

Ejercicios

Capítulo 4. 1.

68

Aplicaciones: Programación lineal

71

El problema de transporte

71

1.1.

Ejemplo de Formulación

72

1.2.

Formulación General

73

1.3.

El problema no balanceado

74

1.4.

Solución del problema de transporte

75

1.4.1.

La solución inicial

75

1.4.2.

Método de la Esquina Noroeste

77

1.4.3.

Método de Vogel.

78

1.4.4.

El método de costo mínimo.

79

1.5.

El Método Simplex del Problema de Transporte

79

1.6.

Otras aplicaciones del modelo de transporte

80

2.

El problema de asignación

81

2.1.

El algoritmo húngaro

81

2.2.

Casos especiales del modelo de asignación

82

2.2.1.

Oferta y demanda desiguales.

82

2.2.2.

Problemas de maximización.

82

2.2.3. 2.3.

Problemas con asignación inaceptable. Ejercicios

Capítulo 5.

82 82

La programación no lineal

85

1.

Formulación de problemas

85

2.

Condiciones de Karush, Kuhn y Tucker

89

2.1.

Casos Especiales

91

2.2.

Ejemplo

91

2.3.

Ejemplo

93

3.

Interpretación económica de los multiplicadores

96

3.1.

Ejemplo

97

3.2.

Ejemplo

98

Ejercicios

99

4.

Capítulo 6. 1.

Aplicaciones: Programación no lineal

Programación cuadrática

105 105

1.1.

Planteamiento del problema

105

1.2.

Ejemplo de función objetivo

106

1.3.

Las condiciones de optimalidad

106

1.4.

Las condiciones de Karush–Kuhn–Tucker

107

Prof. Victor Bernal

OPTIMIZACION

Pág. 5 de 131

1.5.

La solución óptima

108

1.6.

Ejemplo

108

Ejercicios

109

2.

Capítulo A.

El programa LINGO

111

1.

El lenguaje de modelado: LINGO

111

2.

La formulación del modelo en LINGO

115

3.

Formulación en conjuntos y formulación escalar

119

4.

Importación y exportación de datos con la hoja de cálculo

120

5.

Importación y exportación desde bases de datos en LINGO

122

6.

Cálculos adicionales en modelos LINGO

124

7.

El modelo básico de Markowitz

125

8.

Frontera eficiente de un portafolio

127

Prof. Victor Bernal

OPTIMIZACION

Pág. 6 de 131

Cap´ıtulo

1

Introducción 1.

La Investigación de Operaciones: El concepto

Existen varias definiciones diferentes de lo que es la Investigación Operativa (IO). Por ejemplo: Un método científico para dotar a los departamentos ejecutivos de una base cuantitativa para las decisiones que tengan que ver con las operaciones bajo su control (Methods of Operations Research, McCord y Kimball, 1951 (2007)). El uso de la lógica y de la matemática de forma que no interfieran con el sentido común (Operations research for immediate application: a quick & dirty manual, Woolsey y Swanson, 1980). La ciencia que estudia el modelado de sistemas probabilísticos y determinísticos que se originan en la vida real desde un punto de vista de toma de decisiones óptimas (Introduction To Operations Research, Hillier and Lieberman, 1990). El estudio de cómo formular modelos matemáticos para problemas complejos de administración e ingeniería y cómo analizarlos para tener una visión de las posibles soluciones (Optimization in Operations Research, Rardin, 1998). Quizás la definición de intencionalidad más general pero a la vez más completa en cuanto a lo descriptiva es la que aparece en el texto Applied Management Science: Modeling, Spreadsheet Analysis, and Communication for Decision Making (Lawrence y Pasternack, 1998 (2002)): Un enfoque científico para la toma de decisiones ejecutivas, que consiste en: 1. El arte de modelar situaciones complejas. 2. La ciencia de desarrollar técnicas de solución para resolver dichos modelos y 3. La capacidad de comunicar efectivamente los resultados. A la que tal vez sólo le faltaría incluir el objetivo general de la IO: Estudiar la asignación óptima de recursos escasos a determinada actividad. 7

A menudo la Investigación Operativa es denominada Ciencia de la Administración. Esta ciencia, tal como la conocemos hoy, se desarrolló a partir de los grandes éxitos obtenidos mediante su aplicación a la resolución de problemas de organización militar en la Segunda Guerra Mundial. Por ello recibió el nombre de Investigación Operativa (Operations Research). Cuando estas técnicas fueron introduciéndose en el mundo de los negocios como ayuda a la toma de decisiones, se acuñó el término Ciencia de la Administración o Ciencias de la Gestión (Management Science). En la actualidad hay muy poca distinción entre ambos términos, y ambos se usan indistintamente en la literatura. 2.

La Investigación de Operaciones: El desarrollo

Una de las áreas más importantes y activas de la Investigación Operativa es la Programación Lineal. Los problemas de Programación Lineal se basan en la optimización de una función lineal, la función objetivo, sujeta a una serie de restricciones lineales de igualdad o desigualdad de las variables. El reconocimiento de la importancia de este tipo de problema coincidió con el desarrollo de un método eficiente, el Método Símplex (George Dantzing, 1941) y un medio, el computador, para aplicarlo. Una buena parte de los fundamentos de la Programación Lineal se descubrió en un período muy corto de tiempo de intensa labor de investigación y desarrollo, entre los años 1947 y 1949. En la actualidad, el Algoritmo Símplex es una herramienta estándar que ha ahorrado enormes cantidades de dinero a la mayoría de las empresas o compañías en los países industrializados, y su uso en otros sectores de la sociedad avanza rápidamente. Se han escrito docenas de libros sobre Programación Lineal y publicado centenares de artículos describiendo aplicaciones importantes. Recientemente, el Algoritmo Símplex ha sido elegido como uno de los diez algoritmos de mayor influencia en el desarrollo y la práctica de la ciencia y la ingeniería en el siglo XX (Nash, 2002). En los últimos años, la Programación Lineal ha vuelto a ser un foco de atención mayoritaria y un área de investigación muy activa. La causa de este auge ha sido el desarrollo de dos algoritmos que difieren radicalmente del Método Símplex: el primero es el Método del Elipsoide, desarrollado independientemente por Shor (1970) y Yudin y Nemiroviskii (1976) para Programación Convexa No Diferenciable, aunque fue Kachian quien demostró en 1979 que dicho método puede resolver problemas de Programación Lineal rápidamente, en un sentido teórico, y el segundo es el Algoritmo de Punto Interior Proyectivo de Karmarkar (1984) que constituye una potente y prometedora herramienta para resolver problemas grandes, pues es un algoritmo de tiempo polinomial, a diferencia del Símplex, que es un algoritmo de tiempo exponencial. 3.

Clasificación de los problemas de Investigación Operativa

Los problemas de IO se pueden clasificar de dos modos diferentes: Atendiendo al objetivo del problema. Prof. Victor Bernal

OPTIMIZACION

Pág. 8 de 131

Por el grado de certidumbre de los datos. 3.1.

Clasificación según el objetivo del problema. De acuerdo a este criterio, los proble-

mas de IO se clasifican en: Modelos de optimización, cuyo objetivo es maximizar cierta cantidad (beneficio, eficiencia) o minimizar cierta medida (coste, tiempo), quizás teniendo en cuenta una serie de limitaciones o requisitos que restringen la decisión (disponibilidad de capital, personal, material, requisitos para cumplir fechas límite, etc.). Ejemplos célebres de modelos de optimización son: - Problemas de secuenciación, que se ocupan de colocar objetos en cierto orden. Por ejemplo, supongamos que tenemos N trabajos que deben ser procesados en el mismo orden en M máquinas distintas en las que requieren tiempos de procesamiento diferentes. ¿De qué forma se deben ordenar los trabajos para que el tiempo total de procesamiento de éstos en cada una de las máquinas sea mínimo? - Problemas de localización, que consisten en realizar una asignación de recursos a actividades de manera que se optimice cierta medida de efectividad. Por ejemplo, si la medida de efectividad viene dada por una función lineal con varias variables que debe cumplir un conjunto de restricciones definidas por funciones lineales de dichas variables, el problema es de Programación Lineal. Si hay que asignar unívocamente objetos a tareas para optimizar alguna medida como puede ser un tiempo o un costo, el problema es de Asignación. Si tenemos que distribuir objetos desde ciertos orígenes a varios destinos de forma que cierta función lineal alcance su valor óptimo, estamos ante un problema de Transporte o Transbordo. Problemas de rutas, que tratan de encontrar la ruta óptima desde un origen a un destino cuando existen varias alternativas posibles. El ejemplo más característico es el clásico Problema del Viajante de Comercio. Un viajante de comercio tiene que visitar N ciudades una y sólo una vez antes de volver a su origen. ¿En qué orden debe visitarlas para minimizar la distancia total recorrida?. Este problema de formulación tan sencilla es, en muchos casos, muy difícil de resolver. 3.2.

Clasificación según la certidumbre de los datos. Problemas de búsqueda, que difieren de los otros tipos de problemas que hemos discutido en que hay que buscar cierta información que es necesaria para tomar una decisión. Algunos ejemplos son: buscar barcos enemigos en el océano, realizar auditorías en empresas en busca de trampas o errores, realizar exploraciones de la tierra para encontrar recursos naturales como petróleo, cobre, etc. En cada caso el objetivo es minimizar tanto los costos asociados con la recolección y análisis de datos para reducir los errores de decisión como los propios costos de decisión. La Teoría de la Decisión Estadística proporciona una base para resolver muchos problemas de búsqueda.

Prof. Victor Bernal

OPTIMIZACION

Pág. 9 de 131

Modelos de predicción, cuyo objetivo es describir o predecir sucesos (nivel de ventas, fechas de terminación de proyectos, número de clientes, etc.) dadas ciertas condiciones. Ejemplos de estos modelos son: Problemas de reemplazamiento, que se ocupan de decidir el tiempo adecuado para reemplazar los equipos que fallan o se deterioran. Uno de los problemas que se ajusta a este planteamiento nos es muy conocido: ¿Cuándo debemos cambiar un vehículo?. Como cada uno tiene su propia medida de efectividad, no hay una respuesta única aún suponiendo que los vehículos tuvieran exactamente el mismo rendimiento. Otros problemas bastante cotidianos que encajan en este marco son el problema de reemplazamiento de maquinaria industrial, de computadores en centros de cálculo, establecimiento de garantías, etc. Problemas de inventario, que consisten en determinar la cantidad ideal de productos que se deben tener disponibles en una tienda o almacén. Si un cliente quiere comprar una cierta cantidad de productos pero no están disponibles, esto supondría una venta perdida. Por otro lado, si hay un exceso de productos, el costo de almacenamiento puede ser demasiado grande. El objetivo de este problema es encontrar un punto de equilibrio. Problemas de colas, que son desgraciadamente muy cotidianos. Esperamos en colas para abordar un autobús, para efectuar un depósito bancario, etc. Cualquier problema en el que haya que esperar para obtener un servicio es un problema de colas. Estos problemas vienen definidos por la distribución de los tiempos entre dos llegadas consecutivas al sistema, la distribución de los tiempos de servicio de cada uno de los dependientes, el número de servidores presentes en el sistema, la disciplina de la cola y el tamaño de la sala de espera. El objetivo del problema es encontrar una forma de mejorar el rendimiento global del sistema, que se mide normalmente atendiendo al tamaño de la cola, o bien al tiempo que transcurre desde que un cliente llega al sistema hasta que lo abandona (tiempo de respuesta). En la gran variedad existente de libros de Teoría de Colas se proponen soluciones para muchos modelos de este tipo, pero los problemas reales son tan complejos y sus componentes están tan interconectadas que la simulación es un aspecto vital en este área. Problemas de competencia, que surgen cuando dos o más objetos compiten por un recurso. Muchas veces un problema de competencia consiste en una lucha para obtener un contrato para prestar cierto servicio o conseguir un privilegio. Resolver un problema de este tipo conlleva un proceso subyacente de Toma de Decisiones. 4.

Metodología de la Investigación Operativa

En su forma más simple, la Investigación Operativa puede considerarse como un procedimiento que consta de cuatro pasos o etapas: Prof. Victor Bernal

OPTIMIZACION

Pág. 10 de 131

Paso 1 Definición del problema. Paso 2 Modelado matemático. Paso 3 Solución del modelo. Paso 4 Presentación/Implementación resultados. Los proyectos raramente se ajustan totalmente a esta esquema en secuencia, sino que normalmente los modelos han de ser revisados, las soluciones han de ser modificadas o los informes han de ser reescritos a medida que se modifican y ajustan el conjunto inicial de datos e hipótesis. Por tanto, algunas partes del proceso deben repetirse hasta que se encuentra una solución adecuada.

Paso 1. Definición del problema. Quizás la parte más importante de todo el proceso sea la definición del problema. Una respuesta incorrecta a una pregunta correcta no suele tener consecuencias fatales, ya que se pueden hacer revisiones y explorar otras alternativas: sin embargo, la respuesta correcta a una pregunta incorrecta puede ser desastrosa. Es importante que el problema esté claramente definido antes de invertir una gran cantidad de trabajo y energía en resolverlo. A la hora de definir el problema, el analista debe enfrentarse a uno o más de los factores siguientes: datos incompletos, inconsistentes o difusos; diferencias de opinión; presupuestos o tiempos limitados; cuestiones políticas; el decisor no tiene una idea firme de qué quiere realmente. Para tratar con estos problemas, un buen plan de trabajo es el siguiente: 1. Observar. El analista debe realizar un esfuerzo para contemplar el problema desde diferentes puntos de vista, de modo que termine entendiendo el problema tan bien o mejor que las personas directamente implicadas. 2. Ser consciente de las realidades políticas. Casi siempre hay conflictos entre los jefes y los trabajadores, o entre varios jefes. Para el analista, esto significa que a menudo recibirá información distorsionada o incompleta de cada grupo. 3. Decidir qué se quiere realmente. El analista debe estar seguro de que la compañía tiene claros sus objetivos antes de desarrollar y resolver un modelo. 4. Identificar las restricciones. Es importante saber qué tipo de limitaciones pueden afectar la decisión final, para posteriormente incluirlas en el modelo. 5. Buscar información de modo continuo. A lo largo de todo el proceso, el analista no debería perder el contacto con el decisor. Esto permite que ambos modifiquen de forma continua sus observaciones iniciales y estén al día del desarrollo del proceso.

Paso 2. Modelado matemático. El modelado matemático es un procedimiento que reconoce y verbaliza un problema para posteriormente cuantificarlo transformando las expresiones verbales en expresiones matemáticas. El modelado matemático es un arte, que mejora con la práctica. El proceso del modelado matemático consta de los siguientes cuatro pasos: Prof. Victor Bernal

OPTIMIZACION

Pág. 11 de 131

1. Identificar las variables de decisión. Un paso crucial en la construcción de un modelo matemático es determinar aquellos factores sobre los que el decisor tiene control, que normalmente se llaman variables de decisión del problema. Hay que distinguir entre lo que está a nuestro alcance cambiar (por ejemplo, la cantidad de artículos a producir de cada producto o el material a utilizar) de aquello que no podemos modificar (como el número de horas de trabajo disponibles o fechas límite a cumplir), que normalmente denominaremos parámetros. Según el tipo de problema, lo que a veces es una variable de decisión en otros casos puede ser un parámetro o viceversa. En muchos casos, definir las variables de decisión es la etapa más difícil, pues una vez que están bien definidas, el resto del proceso fluye de modo natural. Sin embargo, una definición incorrecta de las variables de decisión bloquea totalmente el resto del problema. Para identificar las variables de decisión, puede ser útil hacerse las siguientes preguntas: ¿qué es lo que hay que decidir? o ¿sobre qué elementos tenemos control? o ¿cuál sería una respuesta válida para este caso?. 2. Identificar la función objetivo. El objetivo de la mayoría de los estudios de IO, y el de todos los modelos de optimización, es encontrar el modo de optimizar alguna medida respetando las restricciones existentes. Aunque una compañía quizás esté satisfecha con una mejora sustancial de la situación actual, normalmente el objetivo es buscar el valor óptimo para cierta función. A la hora de encontrar la función objetivo, la pregunta que podemos hacernos es ¿qué es lo que queremos conseguir? o Si yo fuera el jefe de esta empresa, ¿qué me interesaría más?. 3. Identificar las restricciones. En la búsqueda de la solución óptima, normalmente existen ciertas restricciones (limitaciones, requisitos) que limitan nuestra decisión. Ejemplos de restricciones frecuentes son: los recursos disponibles (trabajadores, máquinas, material, etc.) son limitados; fechas límite impuestas por los contratos; restricciones impuestas por la naturaleza del problema (por ejemplo: el flujo de entrada a un nodo debe ser igual al flujo de salida) 4. Traducir todos los elementos básicos a un modelo matemático. Una vez identificados los elementos básicos hay que expresarlos matemáticamente. Dependiendo de la naturaleza de las funciones matemáticas, el modelo será de un tipo u otro; por ejemplo, si todas ellas son lineales, el problema será de Programación Lineal; si existe más de una función objetivo, será de programación multicriterio, etc. Paso 3. Resolución del modelo. Aceptado ya el modelo matemático que mejor describe la situación en estudio, se aplican los algoritmos y métodos matemáticos diseñados para su resolución. Las etapas en la resolución del modelo son: 1. Elegir la técnica de resolución adecuada. Afortunadamente, muchos de los modelos de IO pueden resolverse utilizando técnicas eficientes ya existentes, que proporcionan una Prof. Victor Bernal

OPTIMIZACION

Pág. 12 de 131

solución óptima para el modelo. En otros casos, el problema es demasiado complejo o el algoritmo de resolución tiene una complejidad computacional inaceptable y hay que recurrir a métodos heurísticos de resolución. 2. Generar las soluciones del modelo. Una vez elegida la técnica de resolución, el siguiente paso es resolver el problema. Como normalmente la mayoría de los modelos conllevan la manipulación de una gran cantidad de datos, los problemas deben ser resueltos con ayuda del computador, utilizando alguno de los muchos programas de IO que existen o incluso hojas de cálculo (las versiones actuales de la mayoría de ellas incluyen operadores que realizan análisis de optimización). 3. Comprobar/validar los resultados. Dado que los modelos matemáticos no son más que simplificaciones de la realidad, las soluciones óptimas generadas para un modelo pueden no ser óptimas para el problema de la vida real. En el peor de los casos, puede que ni siquiera sean factibles. De este modo, comprobar la validez de dichas soluciones constituye un paso crucial, igual que comprobar que efectivamente proporcionan un mejor rendimiento que el plan de trabajo que actualmente sigue la empresa. 4. Si los resultados son inaceptables, revisar el modelo matemático. Como ningún modelo es totalmente exacto ni ninguna técnica de validación está exenta de errores, si los resultados de la validación son inaceptables puede ser necesario revisar el modelo. Las hipótesis deben ser estudiadas, la exactitud de los datos comprobada, las aproximaciones relajadas o endurecidas, las restricciones revisadas. 5. Realizar análisis de sensibilidad. Normalmente, la solución que nos proporciona el computador es una respuesta para el modelo. Pero el decisor suele querer no una solución, sino varias soluciones entre las que elegir. El analista debe estar preparado para estudiar los cambios posibles y su alcance. Para ello resulta muy útil realizar el llamado análisis de sensibilidad, que estudia los cambios que puede sufrir la solución si se alteran los parámetros del modelo, o bien en qué rango de variación de los parámetros la solución sigue siendo válida.

Paso 4. Presentación/Implementación de los resultados. Éste es el paso final dentro del proceso. Consta de sólo dos pasos: 1. Preparar informes y/o presentaciones. La comunicación efectiva de los resultados de un estudio es esencial para el éxito del mismo. La utilidad del análisis será nula si las personas que toman las decisiones no aprecian totalmente su valor. Los decisores deben comprender completamente el enfoque del analista, las hipótesis y simplificaciones que se han hecho, y la lógica subyacente en la recomendación. Las presentaciones orales (utilizando transparencias, videos o software especializado) y los informes son formas tradicionales para la comunicación. Prof. Victor Bernal

OPTIMIZACION

Pág. 13 de 131

2. Vigilar el proceso de implementación. Una vez que se ha emitido el informe o se ha hecho la presentación, debe implantarse la solución propuesta, que a veces puede suponer cambios que sean inconsistentes y encuentren resistencia en los miembros de la empresa. El apoyo del analista puede resultar crítico. Una vez implementada la solución, debe ser supervisada de forma continua. Dada la naturaleza dinámica y cambiante de la mayoría de las empresas, es casi inevitable que haya que realizar cambios en el modelo. El analista debe estar preparado para saber cuándo ha llegado el momento de cambiar y para realizar dichos cambios.

Prof. Victor Bernal

OPTIMIZACION

Pág. 14 de 131

Cap´ıtulo

2

La programación lineal Los problemas de programación lineal forman parte de la llamada programación matemática que trata problemas particulares a los que la ingeniería se enfrenta con relativa frecuencia. Actualmente es posible resolver la mayoría de ellos usando muchas de las herramientas disponibles, procedimientos o paquetes de software. De hecho, estos problemas se estudian en detalle en los estudios de pregrado y postgrado. Sin embargo, se debe estar preparado para resolver otros problemas muy frecuentes como: 1. Problemas de programación lineal con muchas variables y/o restricciones. 2. Problemas de programación no lineal. 3. Técnicas de descomposición para problemas a resolver con herramientas de programación matemática 4. Reglas para transformar otros problemas en problemas de programación matemática En estas notas se exponen algunos métodos que permiten resolver una amplia colección de problemas prácticos interesantes. El objetivo de estas notas no es el de tratar los métodos estándar de análisis, que están ya cubiertos en muchos otros libros. Al contrario, se trata de mostrar al lector la potencia de estos métodos para resolver problemas prácticos luego de introducir los principales conceptos y herramientas. Son pocos los requisitos para el lector, un conocimiento previo de álgebra lineal, cálculo elemental y una cierta familiaridad con matrices son muy convenientes. 1.

Formulación de problemas

La programación matemática es una potente técnica de modelado usada en el proceso de toma de decisiones. Cuando se trata de resolver un problema de este tipo, la primera etapa consiste en identificar las posibles decisiones que pueden tomarse; esto lleva a identificar las variables del problema concreto. Normalmente, las variables son de carácter cuantitativo y se buscan los valores que optimizan el objetivo. 15

La segunda etapa supone determinar qué decisiones resultan admisibles; esto conduce a un conjunto de restricciones que se determinan teniendo presente la naturaleza del problema en cuestión. En la tercera etapa, se calcula el costo/beneficio asociado a cada decisión admisible; esto supone determinar una función objetivo que asigna, a cada conjunto posible de valores para las variables que determinan una decisión, un valor de costo/beneficio. El conjunto de todos estos elementos define el problema de optimización. La programación lineal (PL), que trata exclusivamente con funciones objetivos y restricciones lineales, es una parte de la programación matemática, y una de las áreas más importantes de la matemática aplicada. Se utiliza en campos como la ingeniería, la economía, la gestión, y muchas otras áreas de la ciencia, la técnica y la industria. En este capítulo se introduce la programación lineal por medio de varios ejemplos seleccionados. Para empezar nuestra exposición se hace notar que cualquier problema de programación lineal requiere identificar cuatro componentes básicos: 1. El conjunto de datos. 2. El conjunto de variables involucradas en el problema, junto con sus dominios respectivos de definición. 3. El conjunto de restricciones lineales del problema que definen el conjunto de soluciones admisibles. 4. La función lineal que debe ser optimizada (minimizada o maximizada). En las secciones que siguen se da una lista de ejemplos, prestando especial atención en cada caso a estos cuatro elementos. 1.1.

El problema del transporte. Un cierto producto debe enviarse en determinadas can-

tidades u1 , . . . , um , desde cada uno de m orígenes, y recibirse en cantidades v1 , . . . , vn , en cada uno de n destinos. El problema consiste en determinar las cantidades xij , que deben enviarse desde el origen i al destino j, para conseguir minimizar el costo del envío. Los cuatro elementos principales de este problema son: 1. Datos: m: el número de orígenes n: el número de destinos ui : la cantidad que debe enviarse desde el origen i vj : la cantidad que debe ser recibida en el destino j cij : el costo de envío de una unidad de producto desde el origen i al destino j 2. Variables xij : la cantidad que se envía desde el origen i al destino j. Se supone que las variables deben ser no negativas: xij ≥ 0; i = 1, . . . , m; j = 1, . . . , n Prof. Victor Bernal

OPTIMIZACION

Pág. 16 de 131

Esto implica que la dirección de envío del producto está prefijada desde los distintos orígenes hasta los destinos. No obstante, otras hipótesis podrán tenerse en cuenta. Por ejemplo, podría no limitarse el signo de las variables xij si no se quiere predeterminar cuáles son los puntos de partida y llegada. 3. Restricciones. Las restricciones de este problema son:

n X

xij = ui ; i = 1, . . . , m,

m X

xij = vj ; j = 1, . . . , n

i=1

j=1

El primer conjunto de condiciones indica que la cantidad del producto que parte del origen i debe coincidir con la suma de las cantidades que parten de ese origen hasta los distintos destinos j = 1, . . . , n. El segundo conjunto de condiciones asegura que el total recibido en el destino j debe corresponder a la suma de todas las cantidades que llegan a ese destino y parten de los distintos orígenes i = 1, . . . , m. 4. Objetivo que debe optimizarse. En el problema del transporte normalmente interesa minimizar los costos de envío (suma de los costos de envío por unidad de producto multiplicado por las cantidades enviadas); es decir, se debe minimizar

z=

m X n X

cij xij

i=1 j=1

Una vez que se han identificado estos cuatro elementos, se está preparado para resolver el problema.

1.2.

Ejemplo: El problema del transporte. Considérese el problema del transporte del

diagrama, con m = 3 orígenes y n = 3 destinos, y

u1 = 2, u2 = 3, u3 = 4; v1 = 5, v2 = 2, v3 = 2 Prof. Victor Bernal

OPTIMIZACION

Pág. 17 de 131

u2 u1

u3

x21 x11

x31

x23 x13

x22 x12

x33

x32

v1

v3 v2

En este caso, el sistema es  

1  0   0 Cx =   1  0  0

1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0

x11



    x12     0  2    x13     0    3 x21       1  4   x22  =      0  5    x23       0  x31  2   1  2  x32    x33

xij ≥ 0; i, j = 1, 2, 3 Las tres primeras ecuaciones establecen la conservación del producto en los tres orígenes y las tres últimas igualdades, la conservación del producto en los tres destinos. Si se concretan valores particulares 

1 2 3



   c= 2 1 2  3 2 1

para los costos de envío, el problema consiste en minimizar z = x11 + 2x12 + 3x13 + 2x21 + x22 + 2x23 + 3x31 + 2x32 + x33 . Prof. Victor Bernal

OPTIMIZACION

Pág. 18 de 131

1.3.

El problema del transporte: La solución computacional. Actualmente existe una gran

cantidad de recursos computacionales para la solución de problemas de programación lineal, uno de ellos se denomina LPSOLVE hecho bajo la filosofía del software libre y utiliza el método simplex revisado. El programa se obtiene a traves de internet en la página http://sourceforge.net/projects/ lpsolve/, por otra parte, detalles más específicos sobre el uso del programa se encuentran en la página http://lpsolve.sourceforge.net/5.5/. Utilizando el paquete LPSOLVE se puede plantear el problema elaborando un archivo de texto con la función objetivo y las restricciones tal como, /* Problema de transporte */ /* Función objetivo */ min: x11 + 2 x12 + 3 x13 + 2 x21 + x22 + 2 x23 + 3 x31 + 2 x32 + x33 ; /* Restricciones */ /* Restricciones por los orígenes */ x11 + x12 + x13 = 2; x21 + x22 + x23 = 3; x31 + x32 + x33 = 4; /* Restricciones por los destinos */ x11 + x21 + x31 = 5; x12 + x22 + x32 = 2; x13 + x23 + x33 = 2; El programa produce el siguiente resultado: Variables Resultado z

14

x11

2

x12

0

x13

0

x21

3

x22

0

x23

0

x31

0

x32

2

x33

2

Es decir, el costo mínimo para cumplir los requisitos es 14. Es necesario anotar que este problema tiene otras soluciones con el mismo costo que no son advertidas al usuario. 1.4.

El problema de la dieta. El problema de la dieta consiste en determinar las cantida-

des de distintos nutrientes que deben ingerirse para asegurar ciertas condiciones de nutrición Prof. Victor Bernal

OPTIMIZACION

Pág. 19 de 131

y minimizar el costo de compra de los nutrientes. De modo más preciso, suponga que se conocen los contenidos nutritivos de ciertos alimentos, sus precios y la cantidad mínima diaria de nutrientes aconsejada. El problema consiste en determinar la cantidad de cada alimento que debe comprarse de suerte que se satisfagan los mínimos aconsejados y se alcance un precio total mínimo. Los cuatro elementos que intervienen en el problema de la dieta son: 1. Datos: m: el número de nutrientes. n: el número de alimentos. aij : la cantidad del nutriente i en una unidad del alimento j. bi : la cantidad mínima del nutriente i aconsejada. cj : el precio de una unidad del alimento j. 2. Variables. Las variables relevantes en este problema son: xj : la cantidad del alimento j que debe adquirirse. 3. Restricciones. Como la cantidad total de un nutriente dado i es la suma de las cantidades de los nutrientes en todos los alimentos y las cantidades de alimentos deben ser no negativas, se deben cumplir las siguientes restricciones: n X

aij xj ≥ bi ; i = 1, . . . , m

j=1

xj ≥ 0; j = 1, . . . , n 4. Función a minimizar. En el problema de la dieta se está interesado en minimizar el precio de la dieta: z=

n X

cj xj

j=1

donde cj es el precio unitario del alimento j.

1.5.

Ejemplo: El problema de la dieta. Considérese un caso con cuatro nutrientes y con

los mínimos aconsejados para los nutrientes digeribles (DN), proteínas digeribles (DP), calcio (Ca), y fósforo (Ph) dados en la siguiente tabla: Nutriente

Cantidad requerida

Maíz A

Avena

Maíz B

Salvado

Linaza

DN

74.2

78.6

70.1

80.1

67.2

77.0

DP

14.7

6.50

9.40

8.80

13.7

30.4

Ca

0.14

0.02

0.09

0.03

0.14

0.41

Ph

0.55

0.27

0.34

0.30

1.29

0.86

Prof. Victor Bernal

OPTIMIZACION

Pág. 20 de 131

Las restricciones entonces se convierten en  78.6  6.50   0.02  0.27

70.1 80.1 67.2 9.40 8.80 13.7 0.09 0.03 0.14 0.34 0.30 1.29

   x1    77.0  74.2    x2      30.4 14.7    ≥   x 3     0.41   0.14  x4  0.86   0.55 x5

con x1 , x2 , x3 , x4 , x5 ≥ 0 Suponga que los precios unitarios de los alimentos son: c1 = 1, c2 = 0.5, c3 = 2, c4 = 1.2, c5 = 3. De este modo, se tiene el problema siguiente; minimizar z = x1 + 0.5x2 + 2x3 + 1.2x4 + 3x5 sujeto a las restricciones antes enunciadas. Usando alguno de los paquetes existentes para resolver dicho problema, como por ejemplo LPSOLVE, se llega a la solución con un costo mínimo de z = 0.793, en el punto (0, 1.530, 0, 0.023, 0). Esto significa que sólo deben comprarse avena y salvado.

1.6. 1.6.1.

El problema de la dieta: La solución computacional. El paquete LPSOLVE. El planteamiento para LPSOLVE se escribe como sigue (lo en-

cerrado entre /* ... */ son comentarios del usuario): /* El problema de la dieta*/ /* Función objetivo */ min: x1 + 0.5 x2 + 2 x3 + 1.2 x4 + 3 x5; /* Restricciones */ 78.6 x1 + 70.1 x2

+ 80.1 x3 + 67.2 x4 + 77.0 x5 >= 74.2

;

6.50 x1 + 9.40 x2

+ 8.80 x3 + 13.7 x4 + 30.4 x5 >= 14.7

;

0.02 x1 + 0.09 x2

+ 0.03 x3 + 0.14 x4 + 0.41 x5 >= 0.14

;

0.27 x1 + 0.34 x2

+ 0.30 x3 + 1.29 x4 + 0.86 x5 >= 0.55

;

El resultado ofrecido por LPSOLVE se resume en la siguiente tabla: Prof. Victor Bernal

OPTIMIZACION

Pág. 21 de 131

1.6.2.

Variable

Resultado

z

0.792769148366363

x1

0

x2

1.53026245313337

x3

0

x4

0.0230316014997323

x5

0

El paquete LINGO. El paquete LINGO (ver Apéndice A) está alojado en la página

http://www.lindo.com/ en la que se puede obtener una versión de prueba para distintos sistemas operativos. Una vez instalado, para la formulación del problema el sistema LINGO requiere especificar todas las operaciones aritméticas, el modelo es entonces, min = x1 + 0.5 *x2 + 2 *x3 + 1.2 *x4 + 3 *x5; 78.6 *x1 + 70.1 *x2

+ 80.1 *x3 + 67.2 *x4 + 77.0 *x5 >= 74.2

;

6.50 *x1 + 9.40 *x2

+ 8.80 *x3 + 13.7 *x4 + 30.4 *x5 >= 14.7

;

0.02 *x1 + 0.09 *x2

+ 0.03 *x3 + 0.14 *x4 + 0.41 *x5 >= 0.14

;

0.27 *x1 + 0.34 *x2

+ 0.30 *x3 + 1.29 *x4 + 0.86 *x5 >= 0.55

;%

La respuesta obtenida es: Global optimal solution found. Objective value:

0.7927691

Total solver iterations:

3

Variable

Value

Reduced Cost

X1

0.000000

0.6335565

X2

1.530262

0.000000

X3

0.000000

1.542769

X4 X5 Row

0.000000 Slack or Surplus

0.000000 1.525094 Dual Price

1

0.7927691

-1.000000

2

34.61912

0.000000

3

0.000000

4 5

Prof. Victor Bernal

0.2303160E-01

0.9480450E-03 0.000000

OPTIMIZACION

-0.3173540E-01 0.000000 -0.5931976% Pág. 22 de 131

La interpretación de los valores identificados como Reduced Cost, Slack or Surplus y Dual Price se dará posteriormente. 1.7.

El problema de la planificación de la producción. Un productor fabrica una pieza,

cuya demanda varía en el tiempo, de acuerdo con el gráfico que se muestra a continuación. El productor debe siempre atender la demanda mensual.

600 b b

500 b

b

b b

Demanda

400

b

300 b b

200 b

b b

100 0 0

1

2

3

4

5

6 7 Tiempo

8

9

10

11

12

En general, cualquier problema de planificación admitirá diversas posibilidades que aseguren que la demanda es convenientemente atendida. Existen dos posibilidades: 1. Producción variable. El fabricante puede producir cada mes el número exacto de unidades que le solicitan. Sin embargo, como una producción que varía es costosa de mantener, por los costos de horarios más largos en los meses de producción alta y los costos asociados al paro del personal y la maquinaria en los meses de producción baja; este tipo de producción no es eficiente. 2. Producción constante. El fabricante que debe atender una demanda que cambia con el tiempo puede producir por encima de dicho nivel en periodos de baja demanda y almacenar la sobreproducción para los periodos de demanda mayor. Así, la producción puede mantenerse constante, compensando la demanda alta con la sobreproducción de periodos pasados. Sin embargo, debido a los costos de almacenamiento, tal opción puede no ser deseable si requiere costos altos de almacenamiento durante varios meses. Los problemas de esta naturaleza ilustran las dificultades que surgen cuando se presentan objetivos opuestos en un sistema dado. Nuestra meta es llevar a cabo una planificación de la producción que maximice los beneficios después de considerar los costos de las variaciones Prof. Victor Bernal

OPTIMIZACION

Pág. 23 de 131

en la producción y el almacenamiento. Los cuatro elementos principales que intervienen en el problema de la planificación de la producción son: 1. Datos. n: el número de meses a considerar s0 : la cantidad almacenada disponible al principio del periodo considerado dt : el número de unidades (demanda) que se solicita en el mes t smax : la capacidad máxima de almacenamiento at : el precio de venta en el mes t bt : el costo de producción en el mes t ct : el costo de almacenamiento en el mes t 2. Variables: xt : el número de unidades producidas en el mes t st : el número de unidades almacenadas en el mes t 3. Restricciones. Como la demanda dt en el mes t debe coincidir con el cambio en el almacenamiento, st−1 −st , más la producción xt en el mes t; la capacidad de almacenamiento no puede excederse; y la demanda dt , almacenamiento st , y producción xt deben ser no negativas; se tienen las siguientes restricciones: st−1 + xt − dt = st ; t = 1, 2, . . . , n st ≤ smax ; t = 1, 2, . . . , n st , xt ≥ 0 4. Función a optimizar. Una posibilidad en el problema de la planificación de la producción consiste en maximizar el ingreso después de descontar los costos de la variación de la producción y los inventarios; esto es, maximizar el beneficio

Z=

n X

(at dt − bt xt − ct st )

t=1

Si el periodo es corto, at , bt , y ct pueden considerarse constantes, esto es, at = a, bt = b y ct = c. Otra posibilidad consiste en minimizar los costos de almacenamiento: Z=

n X

ct st

t=1

1.8.

Ejemplo: El problema de la planificación de la producción. En este ejemplo se ilustra

el problema de la planificación de la producción sin límite en la capacidad de almacenamiento. Considérese la función de demanda en la tabla Prof. Victor Bernal

OPTIMIZACION

Pág. 24 de 131

Tiempo

Demanda

1

2

2

3

3

6

4

1

y suponga que la cantidad almacenada inicialmente es s0 = 2. Entonces, el sistema se plantea como 

 −1 0 0 0   1 −1 0 0  Cx =  0 1 −1 0  0 0 1 −1

1 0 0 0 1 0 0 0 1 0 0 0

s1



  s  2       0  s3  0         3 0  s 4      =   0 x1  6     1  1 x2    x3    x4

st , xt ≥ 0; t = 1, 2, 3, 4 donde el 0 en la matriz de la derecha procede de restar la demanda para t = 1 del almacenamiento inicial. Si se maximiza el beneficio después de descontar los costos debidos a las variaciones en la producción y los inventarios y se toma at = 3, bt = 1, ct = 1, nuestro problema de optimización se traduce en maximizar Z = 36 − x1 − x2 − x3 − x4 − s1 − s2 − s3 − s4 sujeto a las restricciones ya enunciadas. Mediante LPSOLVE puede resolverse este problema y obtener el valor máximo Z = 26 para x = (s1 , s2 , s3 , s4 , x1 , x2 , x3 , x4 ) = (0, 0, 0, 0, 0, 3, 6, 1) la solución implica que no hay almacenamiento. La formulación en LPSOLVE es tan sencilla como, /* Funcion objetivo */ min: -36 + x1 + x2 + x3 + x4 + s1 + s2 + s3 + s4 ; /* Restricciones */ x1 - s1

= 0 ;

s1 - s2 + x2 = 3 ; s2 - s3 + x3 = 6 ; s3 - s4 + x4 = 1 ; 1.9.

Planificación de la producción: La solución computacional.

Prof. Victor Bernal

OPTIMIZACION

Pág. 25 de 131

El paquete MAPLE. Si se escribe el problema general de programación lineal en términos de matrices, se hace mediante el sistema, m´ın f (x) sujeto a Ax ≤ b, x ≥ 0 En el programa MAPLE la forma más sencilla de plantear el problema utiliza el paquete interno Optimization. En el caso de la planificación de la producción la solución obtenida se presenta como: [>with(Optimization); [ImportMPS, Interactive, LPSolve, LSSolve,Maximize, Minimize, NLPSolve,QPSolve] [> Interactive();

En esta ventana se introducen los datos y al oprimir el botón Resolver el resultado es: [26., [s1 = 0., x1 = −4.44089209850062616 10−16 , x3 = 6., x4 = 1., s4 = 0., s3 = 0., s2 = 0., x2 = 3.00000000000000044]]

Luego de la instrucción Interactive(); se debe enunciar el problema en la ventana que abre el programa, allí se introducen los datos y luego de este procedimiento se pide la solución del problema. Obsérvese que x1 ≈ 0 y x2 ≈ 3, lo que en la práctica nos conduce a la respuesta ya enunciada (s1 , s2 , s3 , s4 , x1 , x2 , x3 , x4 ) = (0, 0, 0, 0, 0, 3, 6, 1). 1.10.

El problema de flujo en una red. Considérese una red de transporte (un sistema

de tuberías, ferrocarriles, autopistas, comunicaciones, etc.) a través de la que desea enviarse un producto homogéneo (combustibles, paquetes, mensajes, etc.) desde ciertos puntos de la red, llamados nodos fuente, hasta otros nudos de destino, llamados sumideros. Además de estas dos clases de nodos, la red puede contener nodos intermedios, donde no se genera ni se Prof. Victor Bernal

OPTIMIZACION

Pág. 26 de 131

consume el producto que está fluyendo por la red. Si se define xij como el flujo que va desde el nodo i al nodo j (positivo en la dirección i → j, y negativo en la dirección contraria). Los cuatro elementos presentes en los problemas de flujo son, 1. Datos. G: el grafo G = (N , A) que describe la red de transporte, donde N es el conjunto de nudos, y A es el conjunto de conexiones, dichas conexiones pueden ser, o no, de una única dirección. n: el número de nodos en la red fi : el flujo entrante (positivo) o saliente (negativo) en el nodo i mij : la capacidad máxima de flujo en la conexión entre el nodo i y el j cij : el costo de enviar una unidad del bien del nodo i al nodo j. 2. Variables. Las variables de decisión en este problema son: xij : el flujo que va desde el nodo i al nodo j. 3. Restricciones. Imponiendo la condición de conservación del flujo en todos los nodos, y las restricciones sobre la capacidad de las líneas o conexiones, se obtienen las siguientes restricciones. Las referidas a la conservación del flujo son X (xij − xji ) = fi ; i = 1, . . . , n j

y las relacionadas con la capacidad de las líneas o conexiones son 0 ≤ xij ≤ mij , i < j donde i < j evita la posible duplicación de restricciones y los valores lij no son necesariamente positivos. 4. Función a minimizar. El precio total es X Z= cij xij i,j

La condición para que el problema tenga solución es

Pn

i=1 fi

= 0, en este caso el pro-

blema se dice balanceado. Los problemas de flujo en redes son abundantes en ingeniería. De hecho, los sistemas de abastecimiento de agua, los sistemas de redes de comunicación, y otros, conducen a este tipo de problemas. Además de encontrar las soluciones de los problemas de optimización, se puede estar interesado en analizar el conjunto de soluciones, y en cómo cambia dicho conjunto cuando fallan algunos elementos en el sistema. El ejemplo siguiente se centra en una de tales situaciones. 1.11.

Ejemplo: El problema de flujo en redes. Considérese el problema de flujo en la red

del siguiente diagrama, donde las flechas indican los valores positivos de las variables del flujo. Prof. Victor Bernal

OPTIMIZACION

Pág. 27 de 131

Las ecuaciones para este ejemplo son,    x12    1 1 1 0 0  f1     x13   −1 0    f2  0 1 0        x14  =   0 −1 0   0 1  f    x24   3   0 0 −1 −1 −1  f4 x34 

xij ≤ mij ; i < j xij ≥ 0; i < j donde se supone que mij = 4, i < j, y (f1 , f2 , f3 , f4 ) = (7, −4, −1, −2).

f2 2 x12

x24

f1

x14

1 x13

4

f4

x34 3 f3

Supóngase además que cij = 1; para todo i, j. El problema de optimización es minimizar Z = x12 + x13 + x14 + x24 + x34 sujeto a las restricciones ya enunciadas: x12 + x13 + x14 =f1 = +7 −x12 + x24 =f2 = −4 −x13 + x34 =f3 = −1 −x14 − x24 − x34 =f4 = −2 0 ≤ xij ≤ 4; i < j

La formulación del problema mediante LPSOLVE es Prof. Victor Bernal

OPTIMIZACION

Pág. 28 de 131

/* Funcion objetivo */ min: x12+x13+x14+x24+x34; /* Restricciones */ x12+x13+x14=7; x24-x12=-4; x34-x13=-1; -x14-x24-x34=-2; /* Capacidades de los arcos */ x12