Investigación de operaciones 0000 MMuunnoozz UUNNIIDDAADD PPRREELLIIMMIINNAARREESS..iinndddd II 0022//0033//1111 0011::5533 PPMM 0000 MMuunnoozz UUNNIIDDAADD PPRREELLIIMMIINNAARREESS..iinndddd IIII 0022//0033//1111 0011::5533 PPMM Investigación de operaciones Rodolfo Valentín Muñoz Castorena Centro Universitario de Ciencias Económico y Administrativas Universidad de Guadalajara María Bernardett Ochoa Hernández Centro Universitario de Ciencias Económico y Administrativas Universidad de Guadalajara Manuel Morales García Centro Universitario de Ciencias Económico y Administrativas Universidad de Guadalajara MÉXICO • BOGOTÁ • BUENOS AIRES • CARACAS • GUATEMALA • MADRID • NUEVA YORK SAN JUAN • SANTIAGO • SÃO PAULO • AUCKLAND • LONDRES • MILÁN • MONTREAL NUEVA DELHI • SAN FRANCISCO • SINGAPUR • ST. LOUIS • SIDNEY • TORONTO 0000 MMuunnoozz UUNNIIDDAADD PPRREELLIIMMIINNAARREESS..iinndddd IIIIII 0022//0033//1111 0011::5533 PPMM Director Higher Education: Miguel Ángel Toledo Castellanos Editor sponsor: Jesús Mares Chacón Coordinadora editorial: Marcela Rocha Martínez Editora de desarrollo: Karen Estrada Arriaga Supervisor de producción: Zeferino García García INVESTIGACIÓN DE OPERACIONES Primera edición Prohibida la reproducción total o parcial de esta obra, por cualquier medio, sin la autorización escrita del editor. DERECHOS RESERVADOS © 2011, respecto de la primera edición por: McGRAW-HILL/INTERAMERICANA EDITORES, S.A. DE C.V. A Subsidiary of The McGraw-Hill Companies, Inc. Prolongación Paseo de la Reforma 1015, Torre A, Pisos 16 y 17, Colonia Desarrollo Santa Fe, Delegación Álvaro Obregón C.P. 01376, México, D.F. Miembro de la Cámara Nacional de la Industria Editorial Mexicana, Reg. Núm. 736 ISBN: 978-607-15-0598-9 All rights reserved 1098765432 1098765432101 Impreso en México Printed in Mexico 0000 MMuunnoozz UUNNIIDDAADD PPRREELLIIMMIINNAARREESS..iinndddd IIVV 0022//0033//1111 0011::5533 PPMM COntEnidO Acerca de los autores ........................................................................................ VII Introducción ............................................................................................... VIII UNIDAD 1 ¿Qué es la investigación de operaciones? ......................... 1 1.1 Origen de la investigación de operaciones ................................................... 2 1.2 Modelo ............................................................................................................ 2 Clasificación de los modelos ........................................................................ 3 Ventajas y desventajas del empleo de modelos matemáticos ................... 4 1.3 Optimización .................................................................................................. 4 Problemas de optimización .......................................................................... 5 Unidad II Programación lineal ..................................................................... 7 2.1 Concepto de programación lineal ................................................................ 7 2.2 Planteamiento de problemas en términos de programación lineal ........... 7 2.3 Estructura general de un modelo de programación lineal .......................... 9 2.4 Método gráfico............................................................................................... 13 2.5 Teoría del método símplex ............................................................................ 19 2.6 Dualidad ......................................................................................................... 32 Unidad III Transporte y asignación ............................................................ 35 3.1 Modelos de transporte .................................................................................. 35 3.1.1 Método de la esquina noroeste ......................................................... 38 3.1.2 Método del costo menor ..................................................................... 42 3.1.3 Método Vogel ...................................................................................... 46 3.2 Método de cruce de arroyo o de piedra rodante .......................................... 53 Pasos para resolver el método de arroyo .................................................... 54 3.3 Modelo de asignación ................................................................................... 61 Pasos para aplicar el método húngaro ......................................................... 62 V 0000 MMuunnoozz UUNNIIDDAADD PPRREELLIIMMIINNAARREESS..iinndddd VV 0022//0033//1111 0011::5544 PPMM VI Contenido Unidad IV Modelos de optimización de redes .......................................... 67 4.1 Modelos de redes ........................................................................................... 67 Ruta ................................................................................................................ 68 Lazo dirigido .................................................................................................. 68 4.2 Algoritmo de la ruta más corta ..................................................................... 70 Algoritmo de Dijkstra ..................................................................................... 70 Algoritmo de Floyd ......................................................................................... 70 4.3 Modelo de flujo máximo ................................................................................ 71 4.3.1 Características del modelo de flujo máximo ..................................... 71 Algoritmo de la trayectoria de aumento en el caso del problema de flujo máximo ............................................................................................. 71 4.4 CPM y PERT .................................................................................................... 71 Representación de las redes PERT y CPM .................................................... 72 Cálculo de la ruta crítica (CPM) .................................................................... 74 Ejercicios ............................................................................................................... 77 Problema 1 ............................................................................................................. 77 Problema 2 ............................................................................................................. 77 Problema 3 ............................................................................................................. 78 Problema 4 ............................................................................................................. 79 Problema 5 ............................................................................................................. 79 Problema 6 ............................................................................................................. 80 Glosario ...................................................................................................... 81 Bibliografía ................................................................................................ 82 Índice ......................................................................................................... 83 0000 MMuunnoozz UUNNIIDDAADD PPRREELLIIMMIINNAARREESS..iinndddd VVII 0022//0033//1111 0011::5544 PPMM AcErcA dE lOs AutOrEs Mtro. Rodolfo Valentín Muñoz Castorena Es maestro en Tecnologías de Información por la Universidad de Guadalajara; actual- mente cursa el Doctorado en Educación en la misma institución. Es profesor de asignatura A en el Centro Universitario de Ciencias Económico Administrativas (CUCEA), así como del Departamento de Métodos Cuantitativos y asis- tente del Programa de Formación Docente en el CUCEA. Además, desde el 2005 se desempeña como Secretario y Presidente de la Academia de Optimización. Mtra. María Bernardett Ochoa Hernández Es licenciada en Economía por la Universidad de Guadalajara, maestra en Investiga- ción Educativa por el Centro de Estudios Pedagógicos y Sociales de la Secretaría de Educación Jalisco y actualmente cursa estudios de Doctorado en Educación en dicha universidad. Se desempeña como profesor investigador titular B de tiempo completo en el Cen- tro Universitario de Ciencias Económico Administrativas (CUCEA). Ha sido Presidente de la Academia de Investigación y Desarrollo del Departamento de Administración por ocho años consecutivos (desde el 2003 hasta el 2010). Actual- mente es profesora de los Departamentos de Administración y Métodos Cuantitativos y Responsable del Programa de Formación Docente en el CUCEA. En tres ocasiones ha contado con el perfil PROMEP y es autora de diversos libros y artículos en revistas internacionales, además ha dirigido tesis a nivel licenciatura y maestría. Mtro. Manuel Morales García Es licenciado en Economía por la Universidad de Guadalajara y maestro en Economía y Administración de Empresas por el ESADE en Barcelona, España. Hasta mayo del 2010 se desempeñó como Jefe del Departamento de Métodos Cuan- titativos de la División de Economía y Sociedad del CUCEA. Actualmente es profesor Titular B del Centro Universitario de Ciencias Económico Administrativas. De 2001 a 2007 se desempeñó como Secretario de la Dirección de Finanzas de la Universidad de Guadalajara. Además participó como miembro del Gabinete Econó- mico Universitario, del Consejo Técnico de Planeación Universitario y del Comité de Calidad de la Dirección de Finanzas. Actualmente funge como titular del Órgano Técnico de Hacienda Pública de la Comisión de Hacienda y Presupuestos en la LIX Legislatura del Congreso de Jalisco. VII 0000 MMuunnoozz UUNNIIDDAADD PPRREELLIIMMIINNAARREESS..iinndddd VVIIII 0022//0033//1111 0011::5544 PPMM INtrOducciÓN El objetivo principal de este trabajo es servir como libro de consulta para el curso de Investigación de operaciones, el cual se orienta a estudiantes de licenciatura y, funda- mentalmente, a las áreas de estudio como Negocios internacionales, Administración y Marketing. Los prerrequisitos son álgebra lineal, matemáticas y estadística. El texto proporciona suficiente material para el curso, tratando de desarrollar en cada unidad numerosos ejemplos basados en la realidad para una mejor comprensión de los contenidos de esta disciplina. Si se analizan los ejemplos, el lector adquirirá capacidad para resolver problemas matemáticos y conocerá las principales áreas que componen la Investigación de opera- ciones (desde el análisis del problema, la recopilación de la información, la formula- ción del modelo y el análisis de resultados). Esta última etapa se destaca por su importancia, por lo que se expondrán en forma amplia temas como el de análisis de sensibilidad. VIII 0000 MMuunnoozz UUNNIIDDAADD PPRREELLIIMMIINNAARREESS..iinndddd VVIIIIII 0022//0033//1111 0011::5544 PPMM II UUnniiddaadd ¿Qué es la investigación de operaciones? Al finalizar el estudio de esta unidad, se espera que el lector sea capaz de: explicar qué se entiende por investigación de operaciones. describir qué es un modelo. mencionar algunas aplicaciones de la investigación de operaciones. explicar los diferentes tipos de modelos. diseñar modelos para casos específicos. La investigación de operaciones (IO) es la disciplina que enfrenta un problema concreto, lo divide en pequeñas partes, lo cual facilita el análisis de cada una de Investigación de operaciones (IO). Disciplina que divide un problema con- ellas, para obtener un problema abstracto o, mejor aún, un modelo, todo ello creto en pequeñas partes que analiza mediante una investigación del sistema donde ocurre el problema, con el fin de para obtener un problema abstracto ofrecer acciones o alternativas de solución. o un modelo y así ofrecer acciones o […]La investigación de operaciones es la aplicación, por grupos interdisciplinarios, alternativas de solución. del método científico a problemas relacionados con el control de las organizaciones o sistemas (hombre-máquina), a fin de producir soluciones que sirvan mejor a los objetivos de la organización…1 Algunos autores utilizan el término ciencias de la administración como sinónimo de inves- tigación de operaciones.2 La IO se define como un conjunto de modelos matemáticos aplicables a la solución de ciertos proble- mas orientados a la toma de decisiones, en los que se involucran variables de decisión en los cuales se desea optimizar: 1. El uso de los recursos para lograr un determinado fin cuantificable. 2. Los problemas más o menos complejos que se presentan en una organización social cuya solución empírica resulta demasiado costosa e inadecuada. 1 Francisco J., González Hernández, Breve introducción a la investigación de operaciones, pp. 7 y 8. 2 Hillier y Lieberman, Investigación de operaciones, pp. 2 y 3. 1 0011 MMuunnoozz UUNNIIDDAADD 11..iinndddd 11 0022//0033//1111 0011::5555 PPMM