Investigaciones de Operaciones PDF

Preview

Summary

UNIVERSITARIA SERIE interactivo en esta edición PATRIA “Si la gente no piensa que las matemáticas son simples, es solo porque no se dan cuenta de lo complicada que es la vida”. John Von Neumann En el presente texto se presenta con detalle los principales temas de un primer curso de investigación de ...

Description

SERIE UNIVERSITARIA

PATRIA

interactivo en esta edición

“Si la gente no piensa que las matemáticas son simples, es solo porque no se dan cuenta de lo complicada que es la vida”. John Von Neumann

Entre sus principales características destacan las siguientes: C

M

Y

CM

MY

CY

CMY

La obra consta de cinco unidades y un apéndice (uso detallado del Solver de Excel). Cuenta con breves, pero claras, explicaciones de los fundamentos de la investigación de operaciones. Es un libro flexible, el estudiante lo puede utilizar según sus inquietudes y necesidades. Explica con minuciosidad los pasos necesarios para resolver los problemas propuestos planteados a lo largo de las cinco unidades temáticas. Esto con el objetivo de que sepa resolver diferentes tipos de problemas.

K

Cuenta con más de 300 problemas para resolver, presentados en diferentes categorías; según sus características, algunos deben ser resueltos con el apoyo de la tecnología, por ejemplo con el uso de Solver. Algunos de los problemas propuestos están acompañados de breves textos destacados con el nombre de Alerta, cuyo propósito es preparar al lector para que esté al pendiente de detalles importantes del contenido, que le serán útiles para resolver los problemas. Con el propósito de motivar al estudiante para resolver problemas con un grado de dificultad mayor, al final de cada unidad se incluye una selección de Problemas reto. El libro viene acompañado de un CD-ROM de apoyo, donde alumno y profesor podrán encontrar, entre otras cosas: respuestas a los problemas propuestos, documentos extras, simulación y ejemplos anotados.

EMPRESA DEL GRUPO

www.editorialpatria.com.mx

Investigación de operaciones

En el presente texto se presenta con detalle los principales temas de un primer curso de investigación de operaciones. El atractivo y funcional diseño de este libro, así como su novedosa metodología, ofrecen una invitación a los alumnos de ingeniería para que se acerquen acompañados de lápiz, papel y una computadora, a fin de aprovechar al máximo la oportunidad de ejercitarse con la gran variedad de problemas propuestos que se incluyen en las unidades, los cuales le ayudarán a preparar sus exámenes.

Iris A. Martínez Salazar / Gastón Vértiz Camarón / Jesús F. López Pérez Guillermo Jiménez Lozano / Luis A. Moncayo Martínez

INVESTIGACIÓN DE OPERACIONES Iris Abril Martínez Salazar Universidad Autónoma de Nuevo León

Gastón Vértiz Camarón Universidad Autónoma del Estado de México

Jesús Fabián López Pérez Universidad Autónoma de Nuevo León

Guillermo Jiménez Lozano Universidad Nacional de Colombia

Luis Antonio Moncayo Martínez Instituto Tecnológico Autónomo de México

Colaboración especial Marco Antonio Montufar Benítez Eva Selene Hernández Gress Universidad Autónoma del Estado de Hidalgo

PRIMERA EDICIÓN EBOOK MÉXICO, 2014

INVESTIGACIÓN DE OPERACIONES Iris Abril Martínez Salazar Universidad Autónoma de Nuevo León

Gastón Vértiz Camarón Universidad Autónoma del Estado de México

Jesús Fabián López Pérez Universidad Autónoma de Nuevo León

Guillermo Jiménez Lozano Universidad Nacional de Colombia

Luis Antonio Moncayo Martínez Instituto Tecnológico Autónomo de México

Colaboración especial Marco Antonio Montufar Benítez Eva Selene Hernández Gress Universidad Autónoma del Estado de Hidalgo

PRIMERA EDICIÓN EBOOK MÉXICO, 2014

GRUPO EDITORIAL PATRIA

info

editorialpatria.com.mx

www.editorialpatria.com.mx

Dirección editorial: Javier Enrique Callejas Coordinación editorial: Estela Delfín Ramírez Supervisor de preprensa: Gerardo Briones González Diseño de interiores y portada: Juan Bernardo Rosado Solís Ilustraciones: Adrian Zamorategui Berber Fotografías: © Thinkstockphoto Diagramación: Gustavo Vargas M. y Jorge Martínez J. Colaboración especial: Marco Antonio Montufar Benítez Eva Selene Hernández Gress Universidad Autónoma del Estado de Hidalgo Revisión técnica: Alejandra Gómez Padilla Universidad de Guadalajara-CUCEI Manuel Álvarez Madrigal Instituto Tecnológico y de Estudios Superiores de Monterrey-CCM Investigación de Operaciones Derechos reservados: © 2014, Iris Abril Martínez Salazar, Gastón Vértiz Camarón, Jesús Fabián López Pérez, Guillermo Jiménez Lozano, Luis Antonio Moncayo Martínez. © 2014, GRUPO EDITORIAL PATRIA, S.A. DE C.V. Renacimiento 180, Colonia San Juan Tlihuaca Delegación Azcapotzalco, Código Postal 02400, México, D.F. Miembro de la Cámara Nacional de la Industria Editorial Mexicana Registro Núm. 43 ISBN ebook: 978-607-438-923-4 Queda prohibida la reproducción o transmisión total o parcial del contenido de la presente obra en cualesquiera formas, sean electrónicas o mecánicas, sin el consentimiento previo y por escrito del editor. Impreso en México Printed in Mexico Primera edición ebook: 2014

Agradecimientos A mi familia, por su apoyo incondicional. A cada una de las personas quienes contribuyeron en el desarrollo de este libro. Iris Abril Martínez Una vez concretado el libro, quiero agradecer de todo corazón a Grupo Editorial Patria por haberme permitido participar como autor. Mi mejor deseo es que mi participación en la obra en realidad contribuya a la formación de las futuras generaciones de estudiantes de las licenciaturas en Ingeniería y Administración y a la mejor comprensión de los temas de programación lineal que se abordan. Gastón Vértiz Camarón En primer lugar a Dios. A mi madre y a mi hermano. A mi esposa Albanery, con quien he compartido los mejores momentos, y espero al máximo los que vienen; “TE QUIERO MUCHO”. A mi hija Xiomara Alexandra, quien recién comienza su vida laboral en Bogotá, la cual espero sea demasiado fructífera. A mi hija Angélica, quien en la actualidad estudia su maestría en la Universidad de Guadalajara; aspiro a que construya una magnífica profesión. A mis hijas les he permitido hacer todo lo que han querido en materia de estudio. Todas ellas y ellos son los motores de mi vida. Gracias a todos… Guillermo Jiménez Lozano A Eleonora y Emilio, quienes son mi amores. A la Asociación Mexicana de Cultura, A.C. Luis Moncayo Martínez Agradezco a las siguientes instituciones académicas por su apoyo al escribir esta obra: Instituto Tecnológico y de Estudios Superiores de Monterrey (ITESM), Campus Toluca, Universidad de Lleida, Secretaría de Educación Pública, Universidad Autónoma del Estado de Hidalgo (UAEH). Al apoyo editorial encabezado por la Ingeniera Estela Delfín Ramírez. Marco A. Montufar B. A la Universidad Autónoma del Estado de Hidalgo (UAEH), por permitirme desarrollarme profesionalmente haciendo lo que más me gusta: impartir clases. Al maestro Marco Montufar, por invitarme a participar en este libro. A mis alumnos por dejarme ver con claridad cuáles son los requerimientos para que un libro de texto cumpla su función. A mis padres, por haberme inspirado a ser docente. A mi esposo, por todo su apoyo y a mis hijos quienes son el motor de mi vida. Eva Hernández

Presentación Investigación de operaciones. Serie Universitaria Patria, destacada obra desarrollada por especialistas e investigadores de importantes universidades de México y Colombia, consta de cinco unidades y un apéndice, cada una de las cuales está estructurada con breves explicaciones teóricas, problemas resueltos paso a paso, algunos de estos resueltos con el apoyo de software especializado, alertas (notas de atención para resolver los problemas) y problemas para resolver. La unidad 1 está dedicada a la formulación de modelos matemáticos utilizados en investigación de operaciones. A lo largo de esta se listan los principales elementos de los modelos matemáticos y se describen algunos de los modelos clásicos, a través de la presentación de ejemplos en los que se explica, paso a paso, la construcción de estos. Además, también se analizan diversos tipos de funciones objetivo y de restricciones. Conocer y comprender la forma en que se modelan distintas situaciones facilita al lector la formulación de modelos matemáticos que representen (y apoyen en la solución) del problema bajo estudio. La segunda unidad, Programación lineal, tiene como objetivo presentar la programación lineal continua (PLC) y sus métodos de solución; en esta, se analiza qué es la PLC, además de que también se estudian y describen sus prerrequisitos, las formas de representación de un modelo de PLC, así como los conceptos de variable de holgura, variable de excedencia, variable artificial y variable irrestricta. Asimismo, en esta parte se describe el concepto de solución básica y solución básica factible. En general, existen varios tipos de modelos de programación lineal que presentan estructuras especiales, las cuales pueden ser aprovechadas y explotadas para la construcción de algoritmos más eficientes, con el fin de obtener cotas de búsqueda en el espacio solución y, al mismo tiempo, para obtener soluciones factibles de alta calidad. Inherentemente, la mayor parte de este beneficio tiene que ver con tomar ventaja de este tipo de estrategias para atender y resolver problemas de alta dimensionalidad y escala, y poder lograr soluciones hasta la optimalidad. Lo anterior no es trivial, pues en la práctica habitualmente se tienen limitaciones de tecnología computacional, lo que ha motivado la investigación y el desarrollo para atender problemas de gran escala. Esto, sin duda, es en particular aplicable para los modelos de redes que se exponen en la unidad 3, Aplicación de modelos de redes en la solución de problemas para la toma de decisiones. Pues, para el caso de los modelos de redes es posible referenciar históricamente el problema de transporte. El desarrollo de procedimientos de solución eficientes para este tipo de problemas resultó en la primera aplicación de amplia utilización de la programación lineal en el ámbito industrial. En esta unidad se presentan y analizan las diversas propiedades y variantes que habitualmente se utilizan en los modelos de redes. Asimismo, aquí se formulan y plantean diversos ejemplos para estos modelos, al tiempo que también se presenta su enfoque de solución. De manera muy particular, en esta obra se exponen y desarrollan variantes de los modelos de redes, en los cuales se introduce el uso de variables binarias y enteras, dando lugar al desarrollo de modelos de programación mixta entera. La solución de todos los problemas concernientes al problema de transporte de la unidad 3 se resuelven con la aplicación del algoritmo simplex, desarrollado en la unidad 2. La unidad 4, Programación lineal discreta, se divide en seis partes bien identificadas. En la primera se realiza una introducción a la programación lineal entera, algoritmo de Gomory, algoritmo de rami­ficación y acotamiento (branch and bound ), método de enumeración exhaustiva (enumeración explícita), cada uno acompañado con ejemplos de aplicación. La segunda parte comienza con una introducción a la programación lineal entera binaria y continúa con la explicación de los métodos de enumeración implícita cero-uno y aditivo (enumeración) de Egon Balas, con diversas aplicaciones a través de ejemplos. En la tercera parte se hace una introducción a la programación lineal entera mixta, VII

Presentación acompañada de ejemplos de aplicación. En la cuarta sección se realiza una introducción al problema del transporte (distribución), se muestran los principales métodos de solución, ejemplos de aplicación, problemas de transporte de maximización, soluciones degeneradas y problemas del transporte generalizado. La quinta parte comienza con una introducción al problema de la asignación, se muestran los principales métodos de solución, ejemplos de aplicación, problemas de asignación de maximización y problemas de la asignación generalizada. En la última parte se plantean problemas de programación lineal entera, programación lineal entera binaria, programación lineal entera mixta, problema del transporte y problema de la asignación. Por último, en la unidad 5, Algoritmos especiales: el problema del transporte, se presenta con detalle el problema del transporte, donde cada una de sus variantes es un caso especial en la programación lineal. El problema tiene como objetivo minimizar los costos de distribución de cierto número de unidades de las fuentes u orígenes a los destinos. En el modelo más elemental, las fuentes son entidades que ofertan cierto número de unidades, mientras que los orígenes reciben cierto número de unidades. Esto implica considerar que los orígenes son proveedores de unidades y los destinos las entidades que demandan las primeras. El problema es muy común en la práctica profesional. La presente obra también cuenta con un apéndice, cuyo objetivo principal es introducir al estudiante en la solución de varios tipos de problemas cotidianos de programación lineal mediante el uso del software Solver de Excel; por ejemplo: problemas de producción, de ruta más corta, de asignación, de transporte y de flujo máximo. La idea principal de usar Excel es que este programa constituye una herramienta fácil de entender y usar por la mayoría de los estudiantes de las diversas carreras de ingeniería y administración. Su capacidad para comunicar el modelo y su solución a los interesados es otra de sus cualidades. Sin duda, con las bases que ofrece Investigación de operaciones. Serie Universitaria Patria, el alumno será capaz de poner en práctica otras herramientas computacionales, con el fin de desarrollar modelos y encontrar su solución, sobre todo en modelos de gran escala.

VIII

Contenido Unidad 1 Modelos matemáticos

1

1.1  ¿Qué es un modelo?

2

1.2  Metodología de la investigación de operaciones

2

1.3  Modelo matemático

3

1.4  Modelos matemáticos clásicos

8

1.5  Modelando con variables enteras

26

Problemas para resolver Problema reto Referencias bibliográficas

29 32 32

Unidad 2 Programación lineal

33

2.1  Introducción a la programación lineal continua

34

2.2  Método gráfico

40

2.3  Método simplex

44

2.4  Método de la gran M

57

2.5  Método de las dos fases

64

2.6  Método dual simplex

68

Problemas para resolver Problemas reto Referencias bibliográficas Referencias electrónicas

74 75 77 77 IX

Contenido

Unidad 3 Aplicación de modelos de redes en la solución de problemas para la toma de decisiones

79

3.1 Ejemplos de modelos de investigación de operaciones para redes 80 3.2  Modelo de redes para problemas de asignación

80

3.3 Modelo de redes aplicado al problema de programación óptima de horarios 86 3.4 Modelo de redes aplicado al problema de asignación óptima unidimensional y bidimensional 88 3.5  Modelos de redes para problemas de transporte

89

3.6  Modelo de redes para el problema de flujo máximo

93

3.7  Modelo de redes para el problema de costo mínimo

94

3.8 Modelo de redes para el problema de la ruta crítica aplicado en la planificación de proyectos 94 3.9  Modelo de redes aplicado a problemas de costo fijo

95

3.10 Modelo de redes para el problema de agrupamiento óptimo 96 Problemas para resolver Problema reto Referencias bibliográficas

Unidad 4 Programación lineal discreta

99 110 110

111

4.1  Introducción

112

4.2  Métodos de solución

112

4.3  Programación lineal entera binaria

125

4.4  Programación lineal entera mixta

129

4.5  Problema del transporte o distribución

129

4.6 Problema de asignación o afijación o de nombramientos 135 Problemas para resolver Problema reto Referencias bibliográficas Referencias electrónicas 

142 148 148 148

Grupo Editorial Patria©

Unidad 5 Algoritmos especiales: el problema de transporte

149

5.1  Introducción al problema de transporte

150

5.2 Modelo de programación lineal del problema de transporte 151 5.3  Tabla simplex del problema de transporte

154

5.4 Métodos de aproximación para obtener una solución básica inicial 156 5.5  Métodos para obtener la solución óptima

164

5.6  Problema de asignación

173

5.7 Método para obtener la solución óptima del problema de asignación 174 5.8  Método húngaro

179

Problemas para resolver Problemas reto Referencias bibliográficas Referencias electrónicas

185 187 188 188

Apéndice A Aplicaciones de la optimización lineal usando hojas de cálculo Introducción ❚ Solucionadores para hojas de cálculo Solución de problemas de programación lineal (PL) con una hoja de cálculo ❚ Pasos para implementar un modelo de PL en una hoja de cálculo Modelo en hoja de cálculo para el problema de Luisa Caoba

189 190 190 190 191 192

❚ Organización de los datos

192

❚ Representación de las variables de decisión

193

❚ Representación de la función objetivo

193

❚ Representación de las restricciones

193

❚ Representación de los límites sobre las variables de decisión

194 XI

Contenido ❚ ¿Cómo ve Solver el modelo?

194

❚ Usando Solver

195

❚ Definiendo la celda objetivo

196

❚ Definiendo las celdas variables

197

❚ Definiendo las celdas de restricción

197

❚ Definiendo las condiciones de no negatividad

197

❚ Resolviendo el modelo

198

Problema de flujo máximo ❚ El modelo en hoja de cálculo y su solución

XII

199 200

Problema de transporte

202

Problema de asignación

207

Problema de transbordo

212

Problema de ruta más corta

218

Problemas para resolver

223

UNIDAD

1

Modelos matemáticos Iris Abril Martínez Salazar

Objetivos

Entender el concepto de función objetivo, restricciones, parámetros y variables. Reconocer los diferentes tipos de variables. Entender el concepto de modelado. Entender la relación entre los elementos de un modelo matemático. Conocer aplicaciones de los modelos matemáticos. Formular modelos matemáticos.

¿Qué sabes?

¿Cuál es la diferencia entre parámetro, variable y coeficiente en una ecuación? ¿Qué es una solución factible? ¿Qué son las restricciones y cómo afectan? ¿Cómo usar notación matemática para expresar una situación? ¿Cómo usar álgebra para representar relaciones?

UNIDAD

1

Modelos matemáticos

1.1  ¿Qué es un modelo? Entre las variadas acepciones que hay de la palabra modelo, citamos la siguiente, de la Real Academia Española, que es la que más se adecua al objetivo de esta unidad: Esquema teórico, generalmente en forma matemática, de un sistema o de una realidad compleja, como la evolución económica de un país, que se elabora para facilitar su comprensión y el estudio de su comportamiento. Elaborar un modelo de un sistema o realidad compleja suele ser una tarea ardua y retadora. En la práctica, es usual encontrar modelos desarrollados para representar el comportamiento de alguna sección de...