Investigación de Operaciones - Rodolfo Valentín Muñoz Castorena

Investigación de operaciones 00 Munoz UNIDAD PRELIMINARES.indd I 02/03/11 01:53 PM 00 Munoz UNIDAD PRELIMINARES.indd II 02/03/11 01:53 PM LOUIS • SIDNEY • TORONTO 00 Munoz UNIDAD PRELIMINARES.indd III 02/03/11 01:53 PM .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. Núm. por cualquier medio. Inc.indd IV 02/03/11 01:53 PM . Pisos 16 y 17. 736 ISBN: 978-607-15-0598-9 All rights reserved 1098765432 1098765432101 Impreso en México Printed in Mexico 00 Munoz UNIDAD PRELIMINARES. Torre A. Reg. S. México. A Subsidiary of The McGraw-Hill Companies. DERECHOS RESERVADOS © 2011.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.F. Delegación Álvaro Obregón C. respecto de la primera edición por: McGRAW-HILL/INTERAMERICANA EDITORES. sin la autorización escrita del editor.P. DE C. 01376. Prolongación Paseo de la Reforma 1015. Colonia Desarrollo Santa Fe.V. Miembro de la Cámara Nacional de la Industria Editorial Mexicana. D.A. .........................................................................................................................................................4 2......................................................................................................... 7 Planteamiento de problemas en términos de programación lineal .... VIII UNIDAD 1 ¿Qué es la investigación de operaciones? .............1............... Pasos para resolver el método de arroyo .........indd V 02/03/11 01:54 PM ...3 Método Vogel .......................................................... 7 Estructura general de un modelo de programación lineal .................................................................................................................. 1.....................2 Método del costo menor.................... Problemas de optimización .................... 1 1....................................1.................1 Modelos de transporte ........................................ 3.... 35 38 42 46 53 54 61 62 V 00 Munoz UNIDAD PRELIMINARES.......................................3 Optimización.3 Modelo de asignación .............3 2........................................................................................... 32 Unidad III Transporte y asignación ........................1 Método de la esquina noroeste .............................................................................1 2.......................1 Origen de la investigación de operaciones .............1.......................... Ventajas y desventajas del empleo de modelos matemáticos .................. 3.............. 7 Concepto de programación lineal ............................ 3........................................... 19 Dualidad ..........................2 2...................................... 35 3................6 Programación lineal ......................... 3...................................................................................................... Clasificación de los modelos ...................................................................................... VII Introducción .... 9 Método gráfico.................................................................................................................................COntEnidO Acerca de los autores............................... 3..............2 Modelo ..................................2 Método de cruce de arroyo o de piedra rodante ............. 13 Teoría del método símplex ............ 1............................................................... 2 2 3 4 4 5 Unidad II 2.....................5 2........................... Pasos para aplicar el método húngaro. ..................................................................... 4.. Problema 5......................... Problema 6.................................................................................................... 81 Bibliografía ............................. 83 00 Munoz UNIDAD PRELIMINARES................. 4.......................................................................................................................... Lazo dirigido .................................................................................................2 Algoritmo de la ruta más corta ....................................................................................................................................................................................................... Problema 1..................................................................... Algoritmo de la trayectoria de aumento en el caso del problema de flujo máximo ........... 67 68 68 70 70 70 71 71 71 71 72 74 77 77 77 78 79 79 80 Glosario ..................................................................................................................................................................4 CPM y PERT ..................................................................... Problema 3............................. Ruta ....indd VI 02/03/11 01:54 PM ..........1 Características del modelo de flujo máximo ............................................................................................................................................................................................................................................................................ Problema 4.....................................................................................VI Contenido Unidad IV Modelos de optimización de redes ........3........................................................ Problema 2............... 4.......................... Algoritmo de Dijkstra.................. Representación de las redes PERT y CPM ................................................................1 Modelos de redes ............... Ejercicios ....................................... Cálculo de la ruta crítica (CPM) .....................................................................3 Modelo de flujo máximo .................................................................... 67 4.................................... 4........................................................................................................................................................................ 82 Índice .................................................................................... Algoritmo de Floyd........................................................... AcErcA dE lOs AutOrEs Mtro. Rodolfo Valentín Muñoz Castorena Es maestro en Tecnologías de Información por la Universidad de Guadalajara; actualmente 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 asistente 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 Investigació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 Centro 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). Actualmente 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 Cuantitativos 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 00 Munoz UNIDAD PRELIMINARES.indd VII 02/03/11 01:54 PM 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, fundamentalmente, 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 operaciones (desde el análisis del problema, la recopilación de la información, la formulació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 00 Munoz UNIDAD PRELIMINARES.indd VIII 02/03/11 01:54 PM Unidad I ¿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 ellas, para obtener un problema abstracto o, mejor aún, un modelo, todo ello mediante una investigación del sistema donde ocurre el problema, con el fin de ofrecer acciones o alternativas de solución. […]La investigación de operaciones es la aplicación, por grupos interdisciplinarios, 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 Investigación de operaciones (IO). Disciplina que divide un problema concreto en pequeñas partes que analiza para obtener un problema abstracto o un modelo y así ofrecer acciones o alternativas de solución. Algunos autores utilizan el término ciencias de la administración como sinónimo de investigación de operaciones.2 La IO se define como un conjunto de modelos matemáticos aplicables a la solución de ciertos problemas 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 2 Francisco J., González Hernández, Breve introducción a la investigación de operaciones, pp. 7 y 8. Hillier y Lieberman, Investigación de operaciones, pp. 2 y 3. 1 01 Munoz UNIDAD 1.indd 1 02/03/11 01:55 PM algunos administradores industriales comenzaron a aplicar esta herramienta para resolver los problemas que originaban el tamaño y la complejidad de las industrias. que se elabora para facilitar su comprensión y el estudio de su comportamiento[…]. http://buscon. quienes lograron resultados tan sorprendentes que obligaron a concentrar la atención en este nuevo enfoque científico. De no haber sido por la computadora digital.1 Origen de la investigación de operaciones Los primeros esfuerzos por estructurar esta disciplina se realizaron durante la Segunda Guerra Mundial en Gran Bretaña. Diccionario de la lengua española. que con sus enormes capacidades de velocidad de cómputo. esta disciplina que plantea grandes problemas de computación no hubiera crecido hasta el nivel en el que se encuentra hoy en día.2 UNIDAD I ¿Qué es la investigación de operaciones? 1. 3. Un modelo se define como una representación simplificada o idealizada de una parte de la realidad. 02/03/11 01:55 PM . En sus estudios se incluyeron problemas logísticos complejos. instituciones financieras. desarrollado en 1947 por el matemático estaMétodo símplex de programación dounidense George B. o. tales como la planeación de minas en el mar y la eficaz utilización de equipo electrónico. minante el desarrollo de la computadora digital.1). Un grupo importante de administradores militares de Estados Unidos inició algunas investigaciones similares. la investigación de operaciones (IO) fue bautizada así debido a que el equipo realizaba una investigación de operaciones militares. tigación de operaciones. como la evolución económica de un país.2 Modelo Modelo. Al término de la guerra y atraídos por los éxitos que consiguieron los estrategas militares. basado en la En el progreso impresionante de la investigación de operaciones fue deteriteración para ir mejorando la solución a cada paso. sistemas de transporte y sistemas de comercialización.indd 2 Op. vigésima segunda edición.es/draeI/SrvltConsulta?TIPO_ BUS=3&LEMA=modelo. que se definen como una función objetivo y restricciones que se expresan en términos de las variables alternativas de decisión del problema (véase figura 1. La primera técnica matemática ampliamente aceptada en el medio fue el método símplex de programación lineal. cit. En un principio se acreditó a Gran Bretaña el mérito de haber utilizado la IO como una nueva disciplina. motivados por los resultados alentadores que obtuvieron los equipos británicos. Para llevarlas a cabo. bibliotecas. Desde entonces. Aparentemente. generalmente en forma matemática. consultado el 4 de octubre de 2010. reunieron a varios especialistas. según el Diccionario de la lengua española es: […]un esquema teórico. planeación urbana. En la actualidad. pero Estados Unidos tomó pronto el liderazgo en este campo creciente. Primer procedimiento matemátinicas y otras se han perfeccionado gracias al esfuerzo y cooperación de expertos co ampliamente aceptado en la invesinteresados tanto en el área académica como en la industrial. Representación simplificada o idealizada de una parte de la realidad. Dantzig. 1. que trascienden los ámbitos militares e industriales. Real Academia Española. la IO se aplica a distintas actividades. donde la administración militar convocó a un grupo de científicos de distintas áreas del conocimiento para que estudiaran y ofrecieran soluciones viables a problemas tácticos y estratégicos asociados con la defensa del país.rae. deben contener los siguientes tres elementos: 3 4 01 Munoz UNIDAD 1. de un sistema o de una realidad compleja..3 Cabe mencionar que la IO ha sido un factor de primera importancia en el mejoramiento de la eficiencia de numerosas organizaciones alrededor del mundo. p. permitió a los tomadores de decisiones actuar con rapidez y precisión. para incluir actividades tales como la salud pública. y su aplicación ha contribuido en gran medida al incremento de la productividad de la economía de algunos países. almacenamiento y recuperación de información.4 Los modelos. se han incorporado nuevas téclineal. Universidad Politécnica de Valencia. este tipo no indica ninguna evolución durante el transcurso del tiempo ni los cursos de acción que se deben seguir. por ejemplo. además de describir la realidad. sin embargo. su ingreso total (y) sería de Ingreso total del promotor = 200 (3) = $600 Ahora bien. Al resolver el problema simplificado o modelo. de las cuales se hace una selección. 2. 3. la cual puede tomarse del problema original o modificar nuestro modelo hasta que nos arroje los resultados deseados. Ello genera una función relación ventas-ingreso: y = 200x donde. Clasificación de los modelos Los modelos pueden clasificarse según el siguiente criterio: • Modelos mentales. para excluir alternativas no factibles. p. • Modelos matemáticos. Se construyen mediante símbolos matemáticos que representan diferentes comportamientos del problema. debe establecerse una relación función entre el número de ventas y el ingreso total del promotor.2 Modelo 3 1. • Modelos a escala. Para crear este modelo. prescriptivo): Además de ser descriptivo y predictivo nos induce a elegir un curso de acción para obtener un objetivo establecido.indd 3 02/03/11 01:55 PM .5 Abstracto Problema concreto Figura 1. 01 Munoz UNIDAD 1. señala el curso de acción que debe seguirse para lograr un objetivo definido (este tipo de modelos también se denomina de optimización). 3. es decir. una función exponencial nos puede indicar cuál será la población en México en el año 2015. Por ejemplo. 2. los modelos matemáticos se clasifican en tres tipos generales: 1. si el promotor llevara a cabo 3 ventas (x = 3). se obtiene una solución. señala cuál será la situación futura. Alternativas de decisión.1 Analiza Problema simplificado Llega Modelo Proceso de construcción del modelo. podemos elaborar un modelo matemático simple para determinar el ingreso por comisión que reciben Z promotores de ventas que obtienen $200 por cada operación que efectúen. Sea x = número de ventas que realiza cada promotor y = ingreso total del promotor Modelo matemático. Investigación operativa para ingenieros.1. Modelo normativo (decisión. 5 Juan Pilar Tormos. Ed. España. por ejemplo. Modelo predictivo: Tiene mayor alcance que el modelo anterior. Modelo descriptivo: Es el que representa la realidad mediante una relación funcional. pues. Criterios para evaluar y clasificar las alternativas factibles. no todos son complejos. Restricciones. un organigrama es un modelo descriptivo. No todos son complejos. 33. Los modelos matemáticos son aquellos que se construyen mediante símbolos matemáticos que sirven para representar los diferentes comportamientos del problema. Tabla 1. es factible predecir su comportamiento con un cierto margen de error aceptable o tolerable. Su implementación puede ser demasiado costosa o compleja. Modelos aleatorios Describen un fenómeno que se comporta regularmente en intervalos diferentes. a pesar de la existencia de otras importantes clases de modelos. 1. Logro de mayores beneficios con una mínima inversión de recursos. explica que la …también denominada programación matemática. mayor producción o felicidad o la que logra el menor costo.4 UNIDAD I ¿Qué es la investigación de operaciones? Además de la clasificación anterior. etc. Ayudan a operacionalizar las variables con base en ciertos patrones o indicaciones.1. maquinaria. por consiguiente.3 Optimización Optimizar. Se considera que optimizar es la función de lograr mayores beneficios con la mínima cantidad de recursos invertidos. sirve para encontrar la respuesta que proporciona el mejor resultado.2 Ventajas y desventajas de los modelos matemáticos Ventajas Desventajas Permiten apreciar cuáles son las variables importantes del problema y cómo se relacionan entre sí. Modelos abstractos Se les denomina así debido a que es impredecible usar expresiones simbólicas para representar el comportamiento del sistema. predecir su comportamiento es muy difícil. Los 01 Munoz UNIDAD 1. tiempo. Suministran una base cuantitativa para la toma de decisiones. Arsham Hosseim. Modelos dinámicos Interpretan la evolución de una parte de la realidad en un tiempo determinado. Modelos determinísticos Representan un fenómeno que se comporta regularmente a intervalos iguales y. la que obtiene mayores ganancias. tales como dinero.2. existencias. Modelos estáticos Representan la realidad en una determinada unidad de tiempo. Pueden llevar a simplificaciones exageradas o excesivas si se pretende que el modelo se aplique a situaciones muy diversas. es decir. Es necesario destacar que.indd 4 02/03/11 01:55 PM . buscar la mejor manera de realizar una actividad. experto en el tema. existen otras que son independientes de los modelos matemáticos que se mencionaron y que pueden agruparse bajo la perspectiva de uno o varios de los términos que aparecen en la tabla 1. es decir. el objetivo principal de esta sección es el estudio de los modelos matemáticos. Con frecuencia. personal. se presentan las ventajas y desventajas de la tabla 1. estos problemas implican utilizar de la manera más eficiente los recursos. lo que puede provocar la omisión de variables que puedan ser importantes. desperdicio o malestar. se construyen mediante el empleo de gran cantidad de símbolos.1 Términos de los modelos matemáticos Término Definición Modelos físicos Se representan a escala y se construyen con base en problemas concretos. Tabla 1. Ventajas y desventajas del empleo de modelos matemáticos Cuando se utilizan modelos matemáticos para representar el comportamiento de una situación en particular. por lo tanto. http://home. sujetos a las limitaciones impuestas por las restricciones. 2. en el que las variables de entrada son x1 y x2. 2 Maximizar Z = 4x1 + 5x2 Sujeto a: 3x1 + 2x2 ≤ 15 2x1 + 3x2 ≤ 4 x1. Un programa matemático como el del ejemplo anterior es lineal si f(x1. de no negatividad. 2. x2.indd 5 02/03/11 01:55 PM .edu/ntsbarsh/opre640S/spanishD.Actividades de la unidad I 5 problemas de optimización generalmente se clasifican en lineales y no lineales. 01 Munoz UNIDAD 1. según las relaciones del problema sean lineales con respecto a las variables…6 Problemas de optimización En un problema se trata de maximizar o minimizar una cantidad específica llamada objetivo. Conteste: a) ¿Cómo se relaciona? b) ¿Para qué sirve? 6 Arsham Hosseim. por ejemplo. xn) donde (i = 1. indica que las variables que se utilizaron en el modelo deben ser positivas o ceros puesto que. dulces. si se deseara producir. 1 El problema: Minimizar: Z = x1 + x2 Sujeto a: x1 – x2 = 3 x2 ≥ 2 Éste es un problema de optimización del objetivo z. xn) y cada gi(x1. la cual depende de un número finito de variables de entrada. no se podrían producir –4 dulces. Modelos deterministas: optimización lineal. 1. Se desean obtener valores de las variables de entrada que minimicen el objetivo principal. m) se dan como funciones matemáticas y como ilaciones funcionales (como sucede en el primer ejemplo). x2. consultado el 4 de octubre de 2010. x2 ≥ 0 Cabe señalar que la última restricción. Construya su propia definición de investigación de operaciones.htm#rop. …. …. Relacione la investigación de operaciones con las materias del contenido curricular de su carrera o nivel educativo. …. Éstas pueden ser independientes entre sí o relacionarse a través de una o más restricciones.ubalt. 01 Munoz UNIDAD 1.indd 6 02/03/11 01:55 PM . mencionar la estructura general de un modelo de programación lineal. 7a. el transporte.indd 7 02/03/11 01:56 PM . un conjunto de restricciones y una restricción de no negatividad.1 Concepto de programación lineal La programación lineal. Procedimiento matemático con una o más funciones objetivo. la agricultura. 2. resolver e interpretar problemas mediante el empleo del concepto de método símplex. se espera que el lector sea capaz de: explicar qué entiende por programación lineal. un conjunto de restricciones y una restricción de no negatividad para determinar la asignación óptima de recursos escasos. Taha. Se aplica con éxito en el ejército. p. exponer los pasos para plantear un problema dado. la industria. la economía.Unidad II Programación lineal Al finalizar el estudio de esta unidad. consta de una o más funciones objetivo. Investigación de operaciones. resolver e interpretar problemas mediante el empleo del concepto de método gráfico. en las ciencias conductuales y sociales. los sistemas de salud e. 2. Esta herramienta es una técnica de modelado matemático diseñada para optimizar el empleo de los recursos limitados. 11. incluso.2 Planteamiento de problemas en términos de programación lineal Los modelos de programación lineal son normativos y poseen tres conjuntos básicos de elementos.1 Programación lineal. explicar cómo se forman las restricciones y la función objetivo.. 7 02 Munoz UNIDAD 2. ed. que es un procedimiento matemático que ayuda a asignar de manera óptima los recursos escasos. a saber: • Variables de decisión y parámetros • Conjunto de restricciones • Una o más funciones objetivos 1 Hamdy A. Valores que especifican problemas distintos. 02/03/11 01:56 PM .8 UNIDAD II Programación lineal Variables de decisión. Cantidades que se desconocen y que deben determinarse en la solución de un problema cuyo modelo se plantea. entonces. de cada mesa se emplean 6 horas y en la de cada escritorio.1 Distribución de mano de obra. a partir de un recurso básico. Escritorios Recurso básico Mano de obra Mesas Figura 2. ésta tendría la forma y los contenidos siguientes: Tabla 2. Define la eficacia del modelo en función de las variables de decisión. Por ejemplo. la restricción correspondiente a esta limitante sería: 6x1 + 8x2 ≤ 80 horas Si reunimos toda la información descrita en una tabla. éste debe contener cualquiera de las restricciones que limiten las variables de decisión que consumirán valores permisibles. Los parámetros son los valores que describen la relación entre las variables de decisión y que permanecen constantes en cada problema.indd 8 Producto Horas laboradas Operación Total de horas a la semana Mesa 6 6x1 + 8x2 ≤ 80 Escritorio 8 La función objetivo define la eficacia del modelo en función de las variables de decisión.1). Conjunto de restricciones. Supongamos que en la producción decisión. supongamos que el departamento de fabricación de mesas y escritorios trabaja 80 horas por semana. En la figura 2. Son las limitaciones que restringen las variables de decisión que consumirán valores permisibles en el modelo. Para incluir las limitaciones que se presentan en el problema cuyo modelo se plantea. que en este ejemplo es la mano de obra. la relación función de mano de obra es la siguiente: Mano de obra para fabricar los productos 6x1 + 8x2 lo cual nos da el tiempo total que se consume en el proceso de fabricación. pero varían en Parámetros. 8 horas.1 se indica que. pueden fabricarse diversos productos (escritorios y mesas).1 Reunión de datos importantes de una restricción Función objetivo. 02 Munoz UNIDAD 2. las horas de mano de obra que se requieren la relación entre las variables de para elaborar cada uno de estos productos. en consecuencia. Por ejemplo. Un ejemplo para definir una variable de decisión podría ser la cantidad de un determinado producto que debe fabricarse en una operación de producción que involucra diversos productos a partir de un mismo recurso básico (véase figura 2. Conjunto de restricciones. Por ejemplo. si el objetivo debe definir éstas en términos de las variables de decisión en forma matemática indica que se obtiene una utilidad de 210 unidades monetarias por cada mesa y una utilidad de 360 por cada escritorio que se fabrique y se venda. Las variables de decisión son las cantidades desconocidas que deben determinarse en la solución de un problema cuyo modelo se plantea. La compañía logra una utilidad de $2 000 por cada comedor tipo 1 y $2 400 por cada comedor tipo 2.3 Entonces se genera la función objetivo Estructura general de un modelo de programación lineal 9 210x1 + 360x2 = Z. =. =. por lo que es importante especificar cuáles son las cantidades que se deben producir. . .3 Estructura general de un modelo de programación lineal A continuación se muestra la estructura que debe presentar un modelo de programación lineal para su mejor comprensión y aplicación: Función objetivo Optimizar z = c1x1 + c2x2 +…+ cnxn Sujeta a las siguientes restricciones: a11x1 + a12x2 +…+ a1nxn a x + a x +…+ a x 21 1 22 2 2n n . Sea x1 = número de comedores tipo 1 que se deben producir Sea x2 = número de comedores tipo 2 que se deben producir Cuando se definen las variables debe tomarse en cuenta que. 02 Munoz UNIDAD 2. plantear cada una de las restricciones. cuyo propósito principal es maximizar las utilidades que genera la fabricación de mesas y escritorios. Solución: Primero deben definirse las variables de decisión que se emplearán. xn > 0 <. El departamento de construcción cuenta con 120 horas diarias disponibles mientras que el de pintura sólo dispone de 64 horas.indd 9 02/03/11 01:56 PM . 4. La compañía desea determinar el número de unidades de cada tipo de comedor que debe producir por día. Plantee el modelo de programación lineal (MPL) correspondiente. . de esta manera.…. . es indispensable precisar cuántas variables se van a utilizar en el problema. > bm (restricción de no negatividad) Los pasos básicos que se deben dar para plantear un problema en términos de un modelo de programación lineal (MPL) son los siguientes: 1. Identificar los recursos limitantes para. =. 1 Una fábrica de muebles se especializa en la producción de dos tipos de comedores. 3. en la construcción de un comedor tipo 2 se emplean 12 horas y 4 horas para la pintura. > b2 >. son numéricas. cada uno requiere de un tiempo de construcción y otro diferente de pintura. 2. x2. > b1 <. en la mayoría de los casos. Identificar las variables importantes del problema (variables de decisión) y seleccionar una notación adecuada para ellas. Plantear la función objetivo en términos de las variables de decisión. de tal manera que las utilidades totales sean máximas. Un comedor tipo 1 demanda 6 horas de producción y 8 horas de pintura.2. En el momento en que nos indican costos o utilidades. Formular el modelo de acuerdo con la estructura general. am1x1 + am2x2 +…+ amnxn x1. . 2. 2. Según las fluctuaciones de los costos de la materia prima la empresa ha observado que el costo de producción varía de un mes a otro. Los administradores han pronosticado la demanda y los costos de producción de los siguientes 8 meses.indd 10 Mes Costo proyectado por par Demanda pronosticada 1 360 150 000 2 420 110 000 3 380 180 000 4 400 100 000 5 350 200 000 6 390 180 000 7 370 110 000 8 410 170 000 02/03/11 01:56 PM . Otro aspecto que debe definirse con claridad es el objetivo del problema que se va a resolver. se obtiene lo siguiente: Maximizar z = 2 000x1 + 2 400x2 Sujeto a: 6x1 + 12x2 ≤ 120 8x1+ 4x2 ≤ 64 x1. la restricción es: 8x1 + 4x2 ≤ 64 Luego de reunir todos los datos y de acuerdo con la estructura general de un MPL. como se muestra en la tabla 2. Además. las utilidades totales se obtienen mediante la siguiente ecuación: 2 000x1 + 2 400x2 sujeta a las restricciones de tiempo disponible para construcción y pintura. especialista en la fabricación de botas. la compañía considera que resulta conveniente fabricar pares de botas demás en algunos meses para venderlos en meses posteriores. sino que lo hace a través de tiendas al menudeo. x2 ≥ 0 2 Una compañía de zapatos. desean programar la producción de este periodo para minimizar los costos totales de producción y almacenamiento. se tiene: Objetivo = maximizar utilidades Por lo tanto. cuál será la función objetivo. en este caso. Debido a esas variaciones y a que el costo unitario del manejo y almacenamiento es de $11. no vende en forma directa al público.2 Costos proyectados por mes 02 Munoz UNIDAD 2. a su vez.00 por mes.10 UNIDAD II Programación lineal La frase “La compañía obtiene una utilidad de $2 000 por cada comedor tipo 1 y $2 400 por cada comedor tipo 2” refleja con claridad cuántas variables de decisión se usarán y. Tabla 2. En el caso de la construcción de comedores existe la siguiente restricción: 6x1 + 12x2 ≤ 120 Para la pintura. 1+371x1.6 + x5.indd 11 02/03/11 01:56 PM .8+370x7.4+402x3. las tendrán que vender en el mes 2 con un costo adicional de $11.2+382x1. deben definirse las variables de decisión.3 ≥ 180 000 x1.1 donde i = 1 y j = 1.2 + x2.6+475x2.2 ≥ 110 000 Esta restricción indica que las botas que no se vendieron en el mes 1 y se guardaron para venderse en el mes 2 (x1.6+426x1. se obtiene la restricción de ese mes: x1. Objetivo: Minimizar costos de fabricación y almacenamiento.8 ≥ 170 000 xi.7 + x3. si en el mes 2 la demanda pronosticada es de 110 000 pares. lo que da como resultado la variable “371x1. Después.5+415x1.8 + x2.2) se suman a las que se fabricaron en el mes 2 (x2.6 + x3.6+401x6.7+444x4.4 + x2.7+435x3. en el mes 2.8 En este caso.7 + x5.8 + x3.7 + x6.2 ≥ 110 000 Es así como se obtuvieron las restricciones de este problema. esto es.7+412x6.7 + x2.4 + x4.5 + x5.8 +400x4.2 + x2.8+380x3. con lo cual tenemos: x1.5+422x4.2 + x2.4+411x4.2).3+391x3.8+350x5.4 ≥ 100 000 x1.3+393x1. Sujeta a: x1.2+431x2.7 + x4. Una vez que hayamos determinado la función objetivo.8 +410x8.00 Bajo el supuesto de que en ese mes no se vendan todas las botas.7+383x5.7 + x7. el 360x1.2 + x2. la restricción es: x1. $360 + $11.6 + x6. Min z = 360x1.3 Estructura general de un modelo de programación lineal 11 Plantee el modelo de programación lineal correspondiente.2 Ahora.4 + x3. 2”.3 + x2.6+433x4.5 + x2.6 + x4.8+ x8.6 +372x5.7 +486x2. Sea: xij = pares de botas que se fabrican en el mes i y se venden en el mes j. tendremos que definir las restricciones a las cuales se encuentra sujeta. j ≥ 0 Para obtener dichas restricciones se tomaron en cuenta las siguientes consideraciones: Por ejemplo.8+390x6.00 por almacenamiento.8 + x5.2.5+464x2.3 + x3.5 + x4.4+404x1. es decir.1 ≥ 150 000 x1.5 + x3. 02 Munoz UNIDAD 2.8 + x6.2 ≥ 110 000 x1. Solución: En primer término .3+442x2. debe tenerse bien delimitado el objetivo del problema.7+381x7.6 + x2. el costo de las botas fabricadas en el mes 1 y vendidas en el mes 1 es de $360. lo cual significa que las botas fabricadas en el mes 1 y vendidas en el mes 2 tendrán un costo total de $371.6+424x3.5+361x5.6 ≥ 180 000 x1. por ejemplo.5+413x3.8 + x4. tomemos.7 ≥ 110 000 x1.8 + x7.8+420x2.7 +437x1.5 ≥200 000 x1.4+453x2. cualquier materia prima que no se use para la producción actual debe desecharse. se extraen los datos del problema para tener la información de una forma clara y concisa. El aditivo se vende a empresas petroleras y se emplea en la producción de diesel y otros combustibles similares.indd 12 02/03/11 01:56 PM .00 por cada tonelada de aditivo y a $3 000. la administración de la empresa ha concluido que cuenta con las siguientes cantidades de materia prima: Tabla 2. La utilidad asciende a $4 000. un aditivo y un disolvente.3 muestra que una tonelada de aditivo se obtiene mezclando 37 de 1 000 kg de la materia prima 1.4 se deben definir las variables de decisión que se utilizarán: Sea: x1 = 1 000 kg de aditivo que se producirán x2 = 1 000 kg de disolvente que se producirán Proceso de restricciones: En el caso de la materia prima 1. Debido al deterioro y a la naturaleza del proceso de producción.4. y 47 de 1 000 kg de la materia prima 3.12 UNIDAD II Programación lineal 3 En su proceso de producción.00 kg Materia prima 2 5 000. con la cual se puede generar la tabla 2. una pequeña empresa que elabora diversos productos químicos utiliza 3 materiales para elaborar 2 productos.00 por cada tonelada de disolvente. 25 de 1 000 kg de la materia prima 2 y 20 de 1 000 kg de la materia prima 3. la restricción es: 3 x + 1 x ≤ 20 000 kilogramos 7 1 4 2 En el de la materia prima 2 existe la siguiente restricción: 2 x ≤ 5 000 kilogramos 5 2 02 Munoz UNIDAD 2.00 kg Plantee el modelo de programación lineal correspondiente. El disolvente se vende a empresas químicas para elaborar productos de limpieza industrial y para el hogar. una tonelada de disolvente se logra con la mezcla de 14 de 7 1 000 kg de la materia prima 1. Tabla 2. Solución: Antes que nada. Después de un análisis de la demanda potencial. Para formar el aditivo y el disolvente se mezclan las tres materias primas en forma específica.4 Extracción de información importante del problema Producto Materia prima 1 Materia prima 2 Materia prima 3 Aditivo 3 7 0 4 7 Disolvente 1 4 2 5 7 20 Una vez elaborada la tabla 2. La tabla 2.00 kg Materia prima 3 21 000.3 Cantidad de kilogramos disponibles de cada materia prima Materia prima Cantidades disponibles para la producción Materia prima 1 20 000. sin embargo. el método se Método gráfico en actividad. 02 Munoz UNIDAD 2. Cuando los ejes se relacionan con las variables del problema.4 Método gráfico 13 La materia prima 3. esto es. Puede decirse que una solución factible con más de m componentes positivos es no básica. propósito que se logra mediante la graficación de cada una en el plano cartesiano R2. Al conjunto de todas las soluciones factibles se le denomina espacio de soluEspacio de soluciones factibles o ciones factibles. Por último. Por ello. es necesario conocer los siguientes conceptos: Solución factible. y objetivos. padece la siguiente restricción: 4 x + 7 x ≤ 21 000 kilogramos 7 1 20 2 El propósito de la empresa es maximizar las utilidades. en el de restricciones. Se recomienda el empleo del método gráfico sólo en el caso de modelos Método gráfico en recursos. resulta impráctico o imposible de aplicar. pues la mayoría de éstos incluyen un gran número de variables. se dice que es no degenerada. mediante la representación geométrica El modelo puede resolverse en forma gráfica si sólo posee dos variables. Conjunto de todas las Cabe señalar que existe la posibilidad de que un problema no tenga solusoluciones factibles.4 Método gráfico El método gráfico se utiliza para solucionar problemas de programación lineal Método gráfico. 3. ciones factibles. región factible. condiciones técnicas caso de modelos con tres o más variables. la intersección del conjunto solución de cada una de las restricciones. Se utiliza que incluyan dos variables de decisión. pero también es conocido como región factible. Cuando lo hacen con las restricciocuando los ejes se relacionan con las nes tecnológicas se denomina método gráfico en recursos. Después de elaborar el modelo correspondiente. El propósito del método gráfico no es proporcionar un método práctico para resolver problemas lineales. agregamos la restricción de no negatividad: x1.indd 13 02/03/11 01:56 PM . conceptos fundamentales que se emplean para desarrollar las técnicas algebraicas necesarias para resolver modelos de programación lineal. Marcar los puntos que intersecan en la frontera de la región factible.2. Es la que m es el rango o número de restricciones. Es aquella con más de m componentes positivos donde Solución factible degenerada. 2. si tiene menos de m componentes positivos. es una solución factible ro de restricciones. este método muestra los cuando los ejes se vinculan con las restricciones tecnológicas. Identificar la región factible. Si una solución básica factible tiecuenta con más de m componentes ne exactamente m componentes positivos. x2 ≥ 0 2. Se aplica conoce como método gráfico en actividad. Los pasos básicos que se deben seguir para resolver un problema lineal por medio del método gráfico son los siguientes: 1. Se emplea para resolmediante la representación geométrica de las restricciones. variables del problema. condiciones técniver problemas de programación lineal cas y objetivos. por el positivos donde m es el rango o númecontrario. Para entender la forma de operar de los modelos de programación lineal en su forma general. degenerada. el siguiente paso consiste en determinar el conjunto de soluciones de cada una de las restricciones. obtiene la función objetivo siguiente: Max Z = 4 000x1 + 3 000x2 La expresión anterior significa que va a ganar $4 000 por cada tonelada de aditivo y $3 000 por cada tonelada de disolvente. Sea el modelo lineal: Max Z = 4x1 + 3x2 Sujeto a: – – 2x1 + 3x2 ≤ 6 –3x1 + 2x2 ≤ 3 2x1 + x2 ≤ 4 2x1. A este punto se le conoce como punto óptimo. 02/03/11 01:56 PM .14 UNIDAD II Programación lineal 4. x2 ≥ 0 Como primer paso. primero debemos considerarlo como una ecuación con objeto de graficar la recta que limitará al semiplano correspondiente a la solución de la desigualdad. Punto óptimo. despejamos x2 sin tomar en cuenta el valor de x1: 6 . es necesario determinar el conjunto de soluciones de cada una de las restricciones. Para obtener el conjunto de soluciones de una desigualdad en el plano cartesiano (R2). Ubicar el o los puntos factibles que den el mejor valor de la función objetivo. Para la primera restricción 2x1 + 3x2 ≤ 6 2x1 + 3x2 = 6 Al quitar la desigualdad Despejamos a x1 sin tomar en cuenta el valor de x2: 2x1 = 6 x1 = 6 2 expresión de la cual se obtiene que x1 = 3 Ahora.indd 14 2 3 4 5 x1 Primera restricción. Suponga que x1 es el número de sillas tipo 1 que se van a producir y que x2 es el número de sillas tipo 2 que se elaborarán. que significa que x2 = 2 3 3x2 = 6 Se puede observar que x1 = 3 y x2 = 2.2. Punto factible que brinda el mejor valor de la función objetivo. x2 5 4 Va hacia la izquierda 3 Región factible 2 1 1 Figura 2. La gráfica de la restricción quedaría como se muestra en la figura 2.2 02 Munoz UNIDAD 2. la región factible de esa restricción se encuentra hacia la izquierda y se desecha la siguiente suposición de que x1 tome el valor de 4. podemos tomar x2. x2 3 2. se toma el valor de 2 y 4.4 Método gráfico 15 Para saber dónde se ubica la región factible debe tomarse un valor antes y uno después del de x1. Restricción 1 2x1 + 3x2 ≤ 6 Si x1 toma el valor de 2. despejamos x2 sin tomar en cuenta el valor de x1: 3 2 2x2 = 3 de lo que obtenemos x2 = 1. En el caso de la restricción 2 se tiene lo siguiente: Restricción 2 –3x1 + 2x2 ≤ 3 –3x1 + 2x2 = 3 Al quitar la desigualdad Luego. pero. si en este caso el valor de x1 es de 3. y se sustituyen en la restricción 2. y se sustituyen en la restricción 1. La gráfica de la restricción quedaría como se muestra en la figura 2. si en este caso el valor de x1 es de –1.5 2 1. es decir. si no se tiene x1 podemos tomar x2. Para saber hacia dónde se encuentra la región factible debe tomarse un valor antes y uno después del valor de x1.2.5 1 –5 –4 –3 –2 –1 Figura 2. que es 2. se toma el valor de –2 y 0. olvide el valor de x2 o supóngalo cero al sustituir los valores anteriormente descritos. Restricción 2 02 Munoz UNIDAD 2. si es que existe. Nota: Si se utiliza el valor de x1. es decir.5 Observe que x1 = –1 y x2 = 1.3. respectivamente. al sustituirlo debemos cuestionarnos lo siguiente: ¿2 por el valor de x1. si es negativa. la región factible se localiza hacia la derecha.5. si es que existe x1. respectivamente. En este punto terminamos la restricción 1.3 1 2 3 4 5 x1 Segunda restricción. de no ser así. despejamos x1 sin tomar en cuenta el valor de x2: –3x1 = 3 x1 = 3 y se obtiene x1 = –1 –3 A continuación. es menor que 6? Si la respuesta es afirmativa.indd 15 –3x1 + 2x2 ≤ 3 02/03/11 01:56 PM . indd 16 02/03/11 01:56 PM . despejamos x2 sin tomar en cuenta el valor de x1: x2 = 4 de lo cual resulta que x2 = 4 Observe que x1 = 2 y x2 = 4. es decir. se toma el valor de 1 y 3. si no es así podemos tomar x2. al sustituirlo surge la pregunta siguiente: ¿2 por el valor de x1. El siguiente paso es unir las tres gráficas en una sola e identificar la región factible que es la intersección entre las tres áreas. si es negativa. como se observa en la figura 2. y se sustituyen en la restricción 3. En este punto terminamos con la restricción 3. para lo cual será necesario evaluar los puntos de intersección existentes dentro del cuadrante uno. que es 1.16 UNIDAD II Programación lineal Si x1 toma el valor de –2. Restricción 3 2x1 + x2 ≤ 4 Si x1 adopta el valor de 1. olvide el valor de x2 o supóngalo cero al sustituir los valores descritos. la región factible de esa restricción se encuentra hacia la izquierda y se desecha la siguiente suposición de que x1 tome el valor de 3. x2 5 4 3 2 1 1 Figura 2. Por lo tanto. Para saber hacia dónde se localiza la región factible. debe tomarse un valor antes y uno después del valor de x1. al sustituirlo surge la siguiente pregunta: ¿–3 por el valor de x1.4. Para determinar en qué punto factible se alcanza el mejor valor de la función objetivo. Nota: Si se utiliza el valor de x1. pero. es menor que 3? Si la respuesta es positiva. si es negativa. que es –2. respectivamente. es menor que 4? Si la respuesta es afirmativa. En este punto terminamos con la restricción 2. nos apoyaremos en las curvas de nivel o frontera de la región factible óptima. si en este caso el valor de x1 es 2. En el caso de la restricción 3 se tiene lo siguiente: Restricción 3 2x1 + x2 ≤ 4 2x1 + x2 = 4 Eliminamos la desigualdad Luego despejamos x1 sin tomar en cuenta el valor de x2: 2x1 = 4 x1= 4 y obtenemos que x1 = 2 2 Ahora. la región factible se localiza hacia la derecha. pero.5.4 2 3 4 5 x1 Tercera restricción. Nota: Si se emplea el valor de x1. la gráfica de la restricción quedaría como muestra la figura 2. la región factible de esa restricción se encuentra hacia la izquierda y se desecha la siguiente suposición de que x1 tome el valor de 0. si es que existe x1. 02 Munoz UNIDAD 2. entonces la región factible se localiza hacia la derecha. olvide el valor de x2 o supóngalo cero al sustituir los valores descritos. el punto queda así: 02 Munoz UNIDAD 2.5 Región factible B A C 1 D 1 1. mientras que el segundo interseca las restricciones 1 y 3. los valores de los puntos B y C los tenemos que obtener por medio de un método de resolución de ecuaciones. El punto B tiene el siguiente sistema de ecuaciones. determinaremos el valor del punto B.4 Método gráfico 17 x2 3 5 2 4 1 3 2 1. En nuestro ejemplo utilizaremos el método de suma y resta para obtener los valores de los puntos B y C. a partir de lo cual se obtiene: 6x1 + 9x2 = 18 (se multiplica por 3) –6x1 + 4x2 = 6 (se multiplica por 2) Note que no es necesario multiplicar por un valor negativo puesto que ya lo tiene Después de multiplicar la restricción 1 por 3 y la restricción 2 por 2. por otra parte. En la gráfica pueden observarse cuatro puntos óptimos posibles: A. despejaremos la variable x1 y. B.5 2 3 –1 Figura 2. 2x1 + 3x2 = 6 2x1 + 3 ( 2413 ) = 6 2x1 = 6 – Luego. El primero de ellos interseca con las restricciones 1 y 2. 2413 ) 02/03/11 01:56 PM . En este caso sustituiremos el valor en la restricción 1. de los cuales sólo se deducen A y D.2. ya que intersecan el eje x1 y el x2. el cual resolveremos por el método de suma y resta: 2x1 + 3x2 = 6 restricción 1 –3x1 + 2x2 = 3 restricción 2 Como se puede observar sólo se tiene que multiplicar por 3 la restricción 1 y por 2 la restricción 2 para poder eliminar una variable. por último. se tiene lo siguiente: 6x1 + 9x2 = 18 –6x1 + 4x2 = 6 13x2 = 24 De este resultado. si despejamos el valor de x2: x2 = 24 13 Para encontrar el valor de x1 se sustituye x2 en cualquiera de las dos ecuaciones iniciales.5 4 5 x1 Unión de las 3 restricciones. C y D.indd 17 B 2x1 = 6 13 x1 = 3 13 72 13 ( 133 . indd 18 3 2 de sillas del tipo 1 y 1 del 02/03/11 01:56 PM . se logra lo siguiente: 2x1 + 3x2 = 6 –2x1 – x2 = 4 2x2 = 2 De este resultado. procederemos a obtener la Z final que satisfaga nuestras expectativas de maximizar utilidades.5 84 3 24 = 6. obtendremos el valor del punto C. el punto queda así: C ( 32 ) ( 32 . 2x1 + 3x2 = 6 2x1 + 3 (1) = 6 2x1 = 6 – 3 2x1 = 3 x1 = Luego. ( 32 ) = 92 ) = 4. C y D obtenemos: Z = 4x1 + 3x2 Entonces. sustituiremos el valor en la ecuación 1. Sustituyendo en la función objetivo los valores de los puntos A. para encontrar el valor de x1 se sustituye x2 en cualquiera de las dos ecuaciones iniciales. puesto que los dos valores de x1 son iguales. cualquier restricción debe multiplicarse por –1. despejamos el valor de x2 para obtener: x2 = 2 2 x2 = 1 Ahora. En este caso. despejaremos la variable x1 y.4615 Z = 4( ) + 3( ) = 13 ) 13 13 3 Z = 4( ) + 3(1) = 9 2 ZA = 4(0) + 3 B C ZD = 4(2) + 3(0) = 8 ⬖ Z Max = 9 Punto óptimo lo cual indica que se va a lograr una utilidad máxima de 9 si la fábrica produce tipo 2. 2x1 + 3x2 = 6 2x1 + x2 = 4 (–1) Luego de multiplicar la restricción 3 por –1.18 UNIDAD II Programación lineal El punto C tiene el siguiente sistema de ecuaciones. 02 Munoz UNIDAD 2. finalmente. el cual resolveremos por el método de suma y resta: 2x1 + 3x2 = 6 restricción 1 2x1 + x2 = 4 restricción 3 Como se puede observar. 1) Como ya determinamos los valores de los cuatro posibles puntos óptimos. B. tarea que se debe repetir con cada restricción. Por lo tanto. Así.indd 19 02/03/11 01:56 PM . cuya teoría veremos en seguida: Considerando el modelo lineal en la forma conocida. George Dantzig. el “padre de la programación lineal”.5 Teoría del método símplex En los ejemplos anteriores puede apreciarse que. Por fortuna. tenemos: Max Z = –6x1 – 5x2 Note el cambio de signo de positivo a negativo Continuemos ahora con las restricciones. si son valores negativos. a profundidad. La primera restricción x1 + x2 ≤ 9 debe convertirse a la forma estándar. deben analizarse todos los puntos posibles extremos.5 Teoría del método símplex 19 2. Max Z = Cxi + Cxj Sujeto a: xi + xj ≥ b1 xi + xj ≤ b2 xi. s1. según sea el caso. el valor de x1 y x2 no cambia. elaboró un método a finales de la década de 1940 que permite resolver un problema lineal sin necesidad de analizar de manera explícita el valor de la función objetivo en cada punto extremo. la función asumirá valores negativos. el cual después de añadir variables de holgura puede llevarse a la forma estándar. la variable de holgura tomará un signo positivo. x2 ≥ 0 Para resolver este problema.00 por cada galleta cuadrada y $5. si la desigualdad de la restricción es ≤. xj. se suma a la restricción y queda de la siguiente forma: x1 + x2 + s1 = 9 02 Munoz UNIDAD 2. el valor de la función objetivo en cada punto extremo. lo cual puede resultar una tarea bastante laboriosa. deben ponerse tantas variables de holgura como restricciones existan en cada problema. en primer lugar debemos convertir la función objetivo a la forma estándar. y se asigna una variable de holgura denominada Sn en cada restricción: Método símplex. es decir. la cual llamaremos s1. Max Z = 6x1 = + 5x2 Sujeto a: x1 + x2 ≤ 9 x1 – x2 ≥ 1 x1.2. xj ≥ 0 Max Z = – Cxi – Cxj Variable de holgura Sujeto a: xi + xj – s1 = b1 xi + xj + s2 = b2 xi. Método que permite resolver un problema lineal sin necesidad de analizar. s2 ≥ 0 Suponga que usted produce galletas y que gana $6. ¿Cómo se lleva a cabo esta tarea? La función objetivo Max Z = 6x1 + 5x2 deberá cambiar de signo. Esta herramienta se conoce como método símplex. El modelo del problema se resume a continuación: Observe que x1 es el número de galletas cuadradas y x2 de galletas redondas unido a la ganancia de cada galleta.00 por cada galleta redonda. para encontrar la solución óptima de un modelo lineal con la herramienta que se tiene hasta el momento. la función tomará valores positivos. y si son valores positivos. pero tenemos que quitar la desigualdad agregando una variable de holgura. es decir. queda x1 + x2 = 9. en el caso de la segunda restricción. la variable de holgura asumirá un valor negativo ya que la desigualdad es ≥ y queda de la siguiente forma: x1 – x2 – s2 = 1 En la figura 2. Forma original Forma estándar Max Z = 6x1 + 5x2 Genera Max Z = –6x1 – 5x2 Sujeto a: x1 + x2 ≤ 9 x1 – x2 ≥ 1 x1. s1. El valor de Z que se elija indicará la columna que se debe y se llamará columna pivote o columna de entrada. x2 ≥ 0 Figura 2. s2 ≥ 0 Conversión del modelo a la forma estándar.20 UNIDAD II Programación lineal Ahora. Paso 2. Recuerde que este procedimiento sólo se aplica a las restricciones. El siguiente paso es introducir los valores del modelo de la forma estándar a la tabla símplex.indd 20 02/03/11 01:56 PM . 02 Munoz UNIDAD 2. x2. Columna de entrada o pivote x1 x2 s1 s2 Solución s1 1 1 1 0 9 s2 1 –1 0 –1 1 Z –6 –5 0 0 0 Más negativo En la tabla anterior puede observarse que x1 es la variable de entrada. Nombre que se les da: Restricción 1 Restricción 2 x1 x2 s1 s2 Solución s1 1 1 1 0 9 s2 1 –1 0 –1 1 Z –6 –5 0 0 0 Ya con los valores en la tabla se debe resolver este problema de acuerdo con los siguientes pasos: Paso 1. Elegir el valor de Z más negativo. En la siguiente tabla símplex se muestra cómo se llevó a cabo este paso. Se determina la variable de salida mediante la división de la columna solución de las restricciones entre la columna pivote o de entrada.6 se muestra la conversión final del modelo a la forma estándar.6 Sujeto a: x1 + x2 + s1 = 9 x1 – x2 – s2 = 1 x1. no a la función objetivo Z. A la intersección entre la columna de entrada y el renglón de salida se le llama pivote. x1 s2 1 Pivote 1 –1 0 –1 1 –6 Paso 4.indd 21 x1 x2 s1 s2 Solución s1 1 s1 1 1 1 0 9 x1 Pivote x1 1 –1 0 –1 1 Z –6 Z –6 –5 0 0 0 Pivote Convertirlos en ceros 02/03/11 01:56 PM . Paso 5. ÷ s1 x1 x2 s1 s2 Solución 1 1 1 0 9 9 entre 1 = 9 ÷ s2 x1 x2 s1 s2 Solución 1 –1 0 –1 1 1 entre 1 = 1 Observe que los resultados son 9 y 1. Es muy importante que el pivote tome el valor 1. x1 x2 s1 s2 Solución s1 1 1 1 0 9 9/1 = 9 s2 1 –1 0 –1 1 1/1 = 1 Z –6 –5 0 0 0 Aquí se observa que s2 es la variable que debe salir y la que entra es x1. conviértalo a 1 dividiendo todo el renglón entre el valor del pivote. Hacer ceros los demás valores de la columna de entrada o pivote cambiado sólo el nombre de la restricción de s2 a x1. En este caso. Paso 3. Columna de entrada o pivote Note el cambio del nombre de la variable 02 Munoz UNIDAD 2. el renglón queda igual. por lo tanto. el pivote ya es 1. por lo que se elige el valor positivo más pequeño sin tomar en cuenta valores negativos o ceros.5 Teoría del método símplex 21 A continuación se muestra cómo se realiza este paso.2. si éste no tiene dicho valor. x1 x2 s1 s2 Solución x1 1 –1 0 –1 1 Z –6 –5 0 0 0 Inverso de –6 6* 1 6* –1 6* 0 6*–1 6* 1 Multiplicar por 6 y sumar a Z = 6 + (–6) = 0 = –6 + (–5) = –11 =0+0=0 = –6 + 0 = –6 =6+0=6 lo cual genera: x1 x2 s1 s2 Solución x1 1 –1 0 –1 1 Z 0 –11 0 –6 6 Si se resume la información se obtiene lo siguiente: Note que ya son ceros 02 Munoz UNIDAD 2. x1 x2 s1 s2 Solución s1 1 1 1 0 9 x1 1 –1 0 –1 1 (–1)(pivote) (–1)(1) = –1 + 1 = 0 Valor buscado Ingreso del valor a hacer cero Ahora. Además. es decir.22 UNIDAD II Programación lineal En primer término. si queremos hacer cero al 1. que es el inverso de 1 y el resultado se lo sumamos a s1. el renglón x1 es el que tiene el pivote. multiplicamos al renglón x1 por –1. continuamos con el renglón Z multiplicando al renglón x1 por 6 ya que es el inverso de –6. en el caso de los demás valores: x1 x2 s1 s2 Solución s1 0 2 1 1 8 x1 1 –1 0 –1 1 Ya es cero (–1)(–1) = 1 + 1 = 2 (–1)(0) = 0 + 1 = 1 (–1)(–1) = 1 + 0 = 1 (–1)(1) = –1 + 9 = 8 Una vez terminado el renglón s1.indd 22 x1 x2 s1 s2 Solución s1 0 2 1 1 0 x1 1 –1 0 –1 1 Z 0 –11 0 –6 6 02/03/11 01:56 PM . se tiene que multiplicar el renglón x1 por el inverso del valor que se hará cero y sumárselo al renglón que desea convertirse. debemos realizar nuevamente las operaciones correspondientes y hacer que el renglón pivote tenga un valor de 1 y los demás valores de la columna de entrada o pivote tengan valores de 0.indd 23 02/03/11 01:56 PM . debemos multiplicar el renglón x1 por 1 y sumárselo al renglón x1. Si en el renglón de Z aún existen valores negativos.5 Teoría del método símplex 23 Paso 6. debe convertirse el renglón pivote en 1. Se divide todo el renglón entre 2. se debe multiplicar al renglón x2 por el inverso de cada valor que se convertirá en cero y sumárselo al renglón que se desea convertir. regrese al paso 1. En este caso. 02 Munoz UNIDAD 2. En primer lugar. lo que genera: x2 x1 x2 s1 s2 Solución 0 1 1 2 1 2 4 Note que ya cambió a 1 Para convertir en ceros los valores de la columna de entrada o pivote. –11 y –6. se tienen 2 valores. y el valor que elegimos es –11. La nueva columna entrante es: Nueva columna de entrada o pivote x1 x2 s1 s2 Solución s1 0 2 1 1 8 x2 1 –1 0 –1 1 Z 0 –11 0 –6 6 8 =4 2 1 = –1 –1 Renglón elegido No se toma en cuenta ya que es negativo Pivote En este punto ya se han definido todas las variables. es decir. si queremos hacer cero al –1. Ahora. regresamos al paso 1. Como el renglón Z todavía tiene valores negativos. el cual indica que se tiene que elegir el mayor valor negativo. se debe emplear el pivote: x2 Pivote x1 –1 Z –11 Valores a convertir en ceros En seguida. hasta que el renglón Z no tenga valores negativos. Cambió de s1 a x2 x2 x1 x2 s1 s2 Solución 0 2 1 1 8 0/2 = 0 2/2 = 1 1 2 1 2 8 2 = = 1 2 1 2 0 =0 2 2 =1 2 1 1 = 2 2 1 1 = 2 2 8 =4 2 =4 A continuación se introducen los valores que obtuvimos para ubicarlos en el renglón pivote.2. la variable que entra es x2 y la que sale es s1. indd 24 x1 x2 s1 s2 Solución x2 0 1 1 2 1 2 4 x1 1 0 1 2 – 1 2 5 Z 0 0 11 2 – 1 2 50 02/03/11 01:56 PM . continuamos con el renglón Z multiplicando al renglón x2 por 11 ya que es el inverso de –11.24 UNIDAD II Programación lineal x1 x2 s1 s2 Solución x2 0 1 1 2 1 2 4 x1 1 –1 0 –1 1 1* 0 1* 1 1* 1* =0+1=1 = 1 + (–1) = 0 1 2 1 2 1 2 = 1 2 +0= 1 1 = – 2 + (–1) = – 2 1* 4 =4+1=5 lo que queda como sigue: x1 x2 s1 s2 Solución x2 0 1 1 2 1 2 4 x1 1 0 1 2 – 1 2 5 Una vez terminado el renglón x1. x1 x2 s1 s2 Solución x2 0 1 1 2 1 2 4 Z 0 –11 0 –6 6 11* 0 11* 1 11* 11* Multiplicar por 11 y sumárselo a Z =0+0=0 = 11+ (–11) = 0 1 2 1 2 = = 11* 4 11 2 11 2 +0= 11 2 1 + –6 = – 2 = 44 + 6 = 50 operación que genera: x1 x2 s1 s2 Solución x2 0 1 1 2 1 2 4 Z 0 0 11 2 – 1 2 50 Resumiendo la información se obtiene la tabla siguiente: Note que ya son ceros 02 Munoz UNIDAD 2. debemos hacer que el pivote tenga el valor 1 y los demás valores que componen la columna de entrada o pivote obtengan valores de 0. por lo tanto. debemos ubicar las variables de entrada que. x2 x1 x2 s1 s2 Solución 0 2 1 1 8 Pivote Note que ya cambió a 1 El siguiente paso implica convertir a ceros los valores de la columna de entrada o pivote utilizando el pivote para hacerlo: x2 x1 Z 02 Munoz UNIDAD 2. éste es el único valor negativo que queda en el renglón Z.2. Columna de entrada o pivote x1 x2 s1 s2 Solución x2 0 1 1 2 1 2 4 4/ x1 1 0 1 2 – 1 2 5 5/– Z 0 0 11 2 – 1 2 50 Renglón elegido 1 =8 2 1 = –10 2 No se toma en cuenta puesto que es negativo Pivote 1 En principio. tenemos que realizar de nueva cuenta las operaciones correspondientes hasta lograr que el renglón Z no tenga ningún valor negativo. en este caso. aún tenemos valores negativos en el renglón Z. es s2. 1 Para convertir el renglón pivote en 1 es necesario dividir el renglón pivote entre 2 . Con base en el reglón pivote. 1 El renglón de salida es x2 y el pivote es 2 . que tiene el valor de – 2 .5 Teoría del método símplex 25 Como podemos observar.indd 25 Pivote 1 2 1 – 2 – Valores a convertir en ceros 02/03/11 01:56 PM . Queda como sigue: x2 0/ 1 2 =0 1/ 1 2 =2 1 2 / 1 2 1 2 / 1 2 4/ 1 2 x1 x2 s1 s2 Solución 0 1 1 2 1 2 4 =1 0 1 2 =1 1 =0 1 2 1 2 1 2 =2 1 2 1 2 =1 =1 4 1 2 =8 =8 Después introducimos los valores que obtuvimos en el renglón pivote. debe multiplicarse al renglón x2 por el inverso de los valores que se harán cero y sumárselos 1 al renglón que se convertirá. 1 2 1 2 1 2 1 2 1 2 x1 x2 s1 s2 Solución s2 0 2 1 1 8 Z 0 0 11 2 – 1 2 Multiplicar por y sumar a Z 1 2 ya que es el 1 2 50 *0=0+0=0 *2=1+0=1 *1 = *1 = 1 2 1 2 + 11 2 + (– =6 1 2 )=0 *8 = 4 + 50 = 54 Aquí se genera: 02 Munoz UNIDAD 2. continuamos con el renglón Z multiplicando el renglón x2 por 1 inverso de – 2 . si queremos hacer cero al 2 . 1 2 1 2 1 2 1 2 1 2 x1 x2 s1 s2 Solución s2 0 2 1 1 8 x1 1 0 1 2 – 1 2 Multiplicar por y sumar a x1 1 2 5 *0=0+1=1 *2=1+0=1 *1= *1= 1 2 1 2 + 1 2 + (– =1 1 2 )= 0 *8=4+5=9 Luego del paso anterior queda como sigue: x1 x2 s1 s2 Solución s2 0 2 1 1 8 x1 1 1 1 0 9 Ya terminado el renglón x1.26 UNIDAD II Programación lineal En seguida. es decir. entonces debemos multiplicar el renglón 1 x2 por 2 y sumarlo a x1.indd 26 x1 x2 s1 s2 Solución s2 0 2 1 1 8 Z 0 1 6 0 54 02/03/11 01:56 PM . pues esas cantidades generan una utilidad máxima de $54.indd 27 x1 x2 s1 s2 Solución s1 6 10 1 0 30 s2 10 4 0 1 20 Z –5 –2 0 0 0 30 = 5 6 20 =2 10 Renglón elegido 02/03/11 01:56 PM . Columna de entrada o pivote Pivote 02 Munoz UNIDAD 2.00. s2 ≥ 0 Los valores debemos ubicarlos en una tabla símplex. Cuando no aparece una de las variables básicas (x1 y x2) en la tabla símplex final. puede hacerse una comprobación en cualquiera de las ecuaciones del problema. x2. sólo nos queda resumir los resultados que obtuvimos y dar una conclusión: x1 = 9 x2 = 0 Z = 54 Como conclusión. por lo cual ésa será la columna entrante. x2 ≥0 Sujeto a: 6x1 + 10x2 + s1 = 30 10x1 + 4x2 + s2 = 20 x1. 2 Max Z = 5x1 + 2x2 Forma estándar Max Z = –5x1 – 2x2 Sujeto a: 6x1+10x2 ≤ 30 10x1 + 4x2 ≤ 20 x1. s1.2. Ahora. lo cual indica que el problema ha sido resuelto. Para asegurarnos de que realizamos las operaciones adecuadas. Vamos a llevarla a cabo en la función objetivo original para verificar. Max Z = 6x1 + 5x2 54 = 6 * 9 + 5 * 0 54 = 54 Hemos finalizado todo el procedimiento por el método símplex. de esta manera: x1 x2 s1 s2 Solución s1 6 10 1 0 30 s2 10 4 0 1 20 Z –5 –2 0 0 El valor más negativo del renglón Z es –5. se supone que es igual a cero. puede decirse que deben fabricarse 9 galletas de tipo cuadrada y 0 de tipo redonda.5 Teoría del método símplex 27 Luego de reunir toda la información se obtiene la siguiente tabla símplex: x1 x2 s1 s2 Solución s2 0 2 1 1 8 x1 1 1 1 0 9 Z 0 1 6 0 54 Como se puede observar esta tabla símplex no incluye valores negativos en Z. x1 10 10 4 10 0 10 1 10 20 10 x1 x2 s1 s2 Solución 10 4 0 1 20 =1 Cambió de s2 a x1 = 2 5 =0 = 1 10 =2 A continuación.28 UNIDAD II Programación lineal Hasta este momento hemos definido todas las variables. que es el mismo valor del pivote. x1 x2 s1 s2 Solución s1 6 10 1 0 30 x1 1 2 5 0 1 10 2 Multiplicar por –6 y sumar a s1 –6 * 1 = –6 + 6 = 0 –6 * 2 = – 12 + 10 = 38 5 5 5 –6 * 0 = 0 + 1 =1 –6 * 1 3 3 =– +0=– 10 5 5 –6 * 2 = –12 + 30 = 18 02 Munoz UNIDAD 2.indd 28 02/03/11 01:56 PM . Para empezar. Ahora tenemos que realizar de nueva cuenta las operaciones correspondientes y hacer que el renglón pivote tenga un valor de 1 y los demás valores de la columna de entrada o pivote posean valores de 0. introducimos los valores que obtuvimos para ubicarlos en el renglón pivote. con lo cual la tabla queda así: Note que ya cambió a 1 x1 x1 x2 s1 s2 Solución 1 2 5 0 1 10 2 Luego convertimos a ceros los valores de la columna de entrada o pivote usando el pivote para hacerlo: s1 6 x1 Pivote Z –5 Valores a convertir en ceros A continuación debe multiplicarse el renglón x1 por el inverso de cada valor que se transformará en cero y sumarlo al renglón que se convertirá. debemos convertir el renglón pivote en 1 mediante la división de todo el renglón entre 10. la que entra es x1 y la que sale es s2. 5 Teoría del método símplex 29 El resultado es el siguiente: x1 s1 0 x1 1 x2 38 5 2 5 s1 1 0 Solución s2 3 – 5 1 10 18 2 Una vez que hemos resuelto el renglón x1.2. 02 Munoz UNIDAD 2. Ahora sólo nos queda resumir los resultados que obtuvimos: s1 = 18. Ahora debemos multiplicar el renglón x2 por 11 ya que es la inversa de –11. x2 = 0 y Z = 10. lo cual nos indica que hemos terminado. Para llevarla a cabo vamos a verificar la función objetivo original. A continuación. continuamos con el renglón Z. podemos hacer una comprobación en cualquiera de las ecuaciones del problema para asegurarnos de que efectuamos las operaciones adecuadas. esta tabla símplex no tiene valores negativos en el renglón Z. Max Z = 5x1 + 2x2 10 = 5(2) + 2(0) 10 = 10 Hemos finalizado todo el procedimiento por el método símplex. x1 = 2. s2 = 0.indd 29 02/03/11 01:56 PM . x1 x2 s1 s2 Solución x1 1 2 5 0 1 10 2 Z –5 –2 0 0 0 s2 Solución Multiplicar por 5 y sumarlo a Z 5 * 1 = 5 + (–5) = 0 5* 2 = 2+ (–2) = 0 5 5*0=0+0=0 5* 1 1 1 = +0= 10 2 2 5 * 2 = 10 + 0 = 10 Esta operación genera: x1 x2 s1 s1 1 2 5 0 Z 0 0 0 1 10 1 2 2 10 Resumiendo la información se obtiene lo siguiente: x1 Note que ya son ceros x2 0 x1 1 Z 0 x2 38 5 2 5 0 s1 1 0 0 s2 3 – 5 1 10 1 2 Solución 18 2 10 Como se puede ver. Para empezar debemos convertir el renglón pivote en 1 mediante la división de todo el renglón entre 2. x2 ≥ 0 Sujeto a: 2x1 + x2 + s1 = 8 2x1 + 3x2 + s2 = 12 x1. que es el mismo valor del pivote.30 UNIDAD II Programación lineal 3 Max Z = 3x1 + x2 Forma estándar Max Z = –3x1 – x2 Sujeto a: 2x1+ x2 ≤ 8 2x1 + 3x2 ≤ 12 x1. s1. por lo cual ésa será la columna entrante. de esta manera: x1 x2 s1 s2 Solución s1 2 1 1 0 8 s2 2 3 0 1 12 Z –3 –1 0 0 0 El valor más negativo del renglón Z es –3. Cambió de s1 a x1 2 2 1 2 1 2 0 2 8 2 x1 x1 x2 s1 s2 Solución 2 1 1 0 8 =1 1 2 1 = 2 = =0 =4 Luego de la división. Columna de entrada o pivote Pivote x1 x2 s1 s2 Solución s1 2 1 1 0 8 s2 2 3 0 1 12 Z –3 –1 0 0 0 8 =4 2 12 =6 2 Renglón elegido Hasta este punto hemos definido todas las variables: la que entra es x1 y la que sale es s1. actividad que genera la siguiente tabla: x1 x1 x2 s1 s2 Solución 1 1 2 1 2 0 4 Note que ya cambió a 1 02 Munoz UNIDAD 2. x2. ahora debemos efectuar de nuevo las operaciones correspondientes y hacer que el renglón pivote tenga un valor de 1 y los demás valores de la columna de entrada o pivote tengan valores de 0. s2 ≥ 0 Debemos ubicar los valores en una tabla símplex.indd 30 02/03/11 01:56 PM . introducimos los valores que obtuvimos para ubicarlos en el renglón pivote. ya que es el inverso de –3. x1 x2 s1 s2 Solución x1 1 1 2 1 2 0 4 s2 2 3 0 1 12 Multiplicar por –2 y sumar a s2 –2 * 1 = –2 + 2 = 0 1 = –1 + 3 = 2 2 1 –2 * = –1 + 0 = –1 2 –2 * –2 * 0 = 0 + 1 = 1 –2 * 4 = –8 + 12 = 4 La tabla que se obtiene será: x1 x2 s1 s2 Solución x1 1 1 2 1 2 0 4 s2 0 2 –1 1 4 Una vez resuelto el renglón x1 continuamos con el renglón Z multiplicando al renglón x1 por 3.5 Teoría del método símplex 31 Para convertir a ceros los valores de la columna de entrada o pivote. x1 x2 s1 s2 Solución x1 1 1 2 1 2 0 4 Z –3 –1 0 0 0 Multiplicar por 3 y sumar a Z 3 * 1 = 3 + (–3) = 0 1 3 1 = + (–1) = 2 2 2 1 3 3 3* = +0= 2 2 2 3* 3*0=0+0=0 3 * 4 = 12 + 0 = 12 02 Munoz UNIDAD 2.2. utilizamos el pivote: x1 Pivote s2 2 Z –3 Valores a convertir en ceros A continuación debe multiplicarse el renglón x1 por el inverso de cada valor que se transformará en cero y sumarlo al renglón que se convertirá.indd 31 02/03/11 01:56 PM . 32 UNIDAD II Programación lineal Esta operación genera: x1 x2 s1 s2 Solución x1 1 1 2 1 2 0 4 Z 0 1 2 3 2 0 12 Si resumimos la información podemos ordenarla en la siguiente tabla: x1 x2 s1 s2 Solución x1 1 1 2 1 2 0 4 s2 0 2 –1 1 4 Z 0 1 2 3 2 0 12 Como podemos observar, en esta tabla símplex no hay ningún valor negativo en el renglón Z, lo cual nos indica que hemos concluido. Ahora, sólo nos queda resumir los resultados que obtuvimos, a saber: s1 = 0; x1 = 4; s2 = 4; x2 = 0 y Z = 12. Ahora podemos hacer una comprobación en cualquiera de las ecuaciones del problema para asegurarnos de que efectuamos las operaciones adecuadas; para verificar, nos enfocaremos en la función objetivo original. Max Z = 3x1 + x2 12 = 3(4) + 0 12 = 12 Hemos finalizado todo el procedimiento que señala el método símplex. 2.6 Dualidad El término dualidad señala la existencia de dos fenómenos o caracteres diferentes en un mismo estado. En este sentido, las nociones del bien y el mal son un ejemplo de dualidad; la filosofía china también cuenta con los conceptos del yin y el yang para resumir la dualidad de todo lo que existe en el universo. Dentro de la investigación de operaciones, el concepto de dualidad desempeña un papel importante tanto en la teoría como en la práctica. Todo modelo de programación lineal está asociado a otro modelo llamado modelo dual; al modelo de programación inicial también se le conoce como modelo primal. Entre otras cosas, las estructuras duales permiten: • Resolver problemas lineales que tienen más restricciones que actividades. Por ejemplo, el grado de dificultad para resolver un programa lineal por medio de una computadora que está en función del número de filas de la matriz A y no en el número de columnas, al aplicar la dualidad a un problema primario donde m > n, se obtiene otro problema lineal donde el número de columnas m < n. Una vez que se resuelve el problema primario, de manera automática se soluciona su correspondiente dual o viceversa. • Hacer interpretaciones económicas de las soluciones óptimas de los problemas de programación lineal. 02 Munoz UNIDAD 2.indd 32 02/03/11 01:56 PM 2.6 Dualidad 33 • Concebir nuevos algoritmos para solucionar problemas de redes de optimización. • Generar métodos como el dual símplex para realizar análisis de sensibilidad de los programas de programación lineal. Para poder entender el concepto de dualidad debemos referirnos al tema de matriz transpuesta. Podemos decir que la matriz A transpuesta, que se conoce con la simbología AT, es aquella en donde las columnas se transforman en filas o viceversa. Ejemplo: Si tenemos la siguiente matriz: A= 1 2 a b c 15 20 25 10 30 40 Genera AT = a b 1 15 10 2 20 30 3 25 40 Cuestiones importantes que se deben tomar en cuenta: Cuestión 1. Si el primal es un problema de maximización, su dual será un problema de minimización o viceversa. Max Min Cuestión 2. Los coeficientes de la función objetivo del problema primal se convierten en los coeficientes del vector de disponibilidad del problema dual. Cuestión 3. Los coeficientes del vector de disponibilidad del problema original se convierten en los coeficientes de la función objetivo (vector de costo o precio) del problema dual. Cuestión 4. Los coeficientes de las restricciones del problema primal serán la matriz de coeficientes del dual. Cuestión 5. Los signos de desigualdad del problema dual son contrarios a los del primal. Cuestión 6. Si el primal tiene m restricciones y n variables, el dual tendrá n restricciones y m variables. Así, las variables xn del primal se convierten en nuevas variables ym del dual. Primal Max Z = Cx Sujeto a: Ax ≤ B x≥0 Dual Min G = BT y Sujeto a : AT y > CT y>0 Donde: C = constante x = variable Cx = función objetivo En la figura 2.7 se ilustra quién es A; B; C para, posteriormente, convertirse en su dual. Primal Max Z = C 5x1 + 12x2 + 4x3 Sujeto a: 1x1 + 2x2 + 1x3 ≤ 10 1x1 – 1x2 + 3x3 ≥ 8 B A x1 ≥ 0 Figura 2.7 02 Munoz UNIDAD 2.indd 33 Estructura de un problema dual. 02/03/11 01:56 PM 34 UNIDAD II Programación lineal Primal Dual Min Z = 15x1 + 12x2 Max G = 3y1 + 5y2 Sujeto a: x1 + 2x2 ≥ 3 2x1 – 4x2 ≤ 5 xi ≥ 0 Sujeto a: y1 + 2y2 ≤ 15 2y1 – 4y2 ≥ 12 yi ≥ 0 Note que xi = x1, x2, …, xn según las variables utilizadas 2 Dual Primal Min Z = x1 + 3x2 + 2x3 Sujeto a: 3x1 – x2 + 2x3 ≤ 7 2x1 – 4x2 ≥ 12 –2x1 + 3/2 x2 + 4x3 ≤ 5 xi ≥ 0 Max J = 7y1 + 12y2 + 5y3 Sujeto a: 3y1 + 2y2 – 2y3 ≥ 1 –y1 – 4y2 + 3/2y3 ≤ 3 2y1 + 4y3 ≥ 2 yi ≥ 0 Cabe destacar que, una vez solucionados el dual como el primal por medio del método símplex, la solución es la misma. 1. Resuelva los siguientes ejercicios con el empleo del método gráfico: a) Max Z = 3x1 + 2x2 b) Max Z = 2x1 + 3x2 c) Max Z = 20x1 + 30x2 Sujeto a: 7x1 + 3x2 ≤ 15 3x1 + x2 ≤ 20 x1 + x2 ≤ 5 x1, x2 ≥ 0 Sujeto a: x1 + 3x2 ≤ 9 3x1 + 2x2 ≤ 12 x1, x2 ≥ 0 Sujeto a: 2x1 + 2x2 ≤ 150 x1 + 2x2 ≤ 120 x1, x2 ≥ 0 2. Resuelva los siguientes ejercicios por medio del método símplex: a) Max Z = 3x1 + 2x2 + 5x3 b) Max Z = 6x1 – 2x2 + 3x3 Sujeto a: 7x1 + 3x2 – x3 ≤ 15 2x1 – 2x2 + 3x3 ≤ 20 x1 + x2 + x3 ≤ 5 x1, x2, x3 ≥ 0 Sujeto a: 2x1 – x2 + 2x3 ≤ 2 x1 + 4x3 ≤ 4 x1, x2, x3 ≥ 0 c) Max Z = 2x1 + x2 + 2x3 Sujeto a: 4x1 + 3x2 + 8x2 ≤ 12 4x1 + x2 + 12x3 ≤ 8 4x1 – x2 + 3x3 ≤ 8 x1, x2, x3 ≥ 0 3. Convierta a su forma dual los siguientes modelos primales: a) Min Z = 3x1 + 2x2 Sujeto a: 3x1 + 2x2 ≤ 30 x1 + 2x2 ≥ 20 x1, x2 ≥ 0 02 Munoz UNIDAD 2.indd 34 b) Min Z = 6x1 + 7x2 Sujeto a: x1 + x2 ≥ 2 5x1 + x2 ≥ 4 x1, x2 ≥ 0 02/03/11 01:56 PM resolver problemas por medio del método Vogel. fábricas) hasta los puntos de destino (bodegas). al mismo tiempo. solucionar problemas de asignación por medio del método húngaro. 3. resolver problemas por el método de la esquina noroeste. Clase especial de programación por medio del cual se minimizan los costos del transporte de personas o productos desde los puntos de origen hasta los puntos de destino.1 Modelos de transporte Figura 3. se espera que el lector sea capaz de: explicar qué entiende por modelos de transporte. Forma de enviar un bien de un origen a un destino. El objetivo es determinar las cantidades que se deben enviar desde cada punto de origen hasta cada punto de destino que minimicen el costo total del envío y que.1).Unidad III Transporte y asignación Al finalizar el estudio de esta unidad.1 a1 1 a2 2 am m c11 x11 cmn xmn Modelo de transporte. desarrollar los pasos para resolver problemas de transporte. satisfagan tanto los límites de la oferta como los requisitos de la demanda (figura 3. solucionar problemas por medio del método de costo menor. exponer el modelo de asignación. 1 b1 2 b2 n bn Demanda Oferta El modelo de transporte es una clase especial de programación lineal que aborda la situación en la cual se envía un bien desde los puntos de origen (por ejemplo.indd 35 02/03/11 01:57 PM . 35 03 Munoz UNIDAD 3. mientras que la demanda durante el mismo periodo de los 2 centros de distribución será de 4 600 y 2 800 automóviles. Para obtener el costo de envío por cada ruta. en este caso.8 Michoacán 400 432 Nayarit 408 272 Dado que la tabla de costos puede resolverse por medio del método símplex. Las capacidades de producción de las 3 plantas durante el próximo trimestre son de 2 000.1 Distancia entre plantas y centros de distribución Origen Destino México (en kilómetros) Guadalajara (en kilómetros) Guanajuato 2 000 5 380 Michoacán 2 500 2 700 Nayarit 2 550 1 700 La compañía encargada del transporte de los automóviles cobra 16 centavos por kilómetro por auto.indd 36 02/03/11 01:57 PM . de la tabla anterior se obtienen los siguientes costos: Origen Destino México Guadalajara Guanajuato 320 860. En general.16 En resumen. el modelo de transporte puede ampliarse a otras áreas. A partir de la figura 3. Origen Destino México Guadalajara Guanajuato 2 000  0.1 se deduce que: xij = Cantidad enviada cij = Constante. elabore el modelo de programación lineal correspondiente al problema (véase figura 3.1 proporciona la distancia en kilómetros que existe entre las plantas y los centros de distribución. horarios de empleo y asignación de personal. La función objetivo se obtiene de la siguiente forma: Min Z = c11 x11 + c12 x12 +…+ cij xij Una fábrica de autos cuenta con 3 plantas fabriles. una en Guanajuato. La tabla 3. También posee 2 centros de distribución principales.2).16 2 700  0. será de 16 centavos por kilómetro.36 UNIDAD III Transporte y asignación El modelo supone que el costo de envío por una ruta específica es directamente proporcional al número de unidades enviadas (por esa ruta).16 Michoacán 2 500  0. entre ellas el control de inventarios. 2 400 y 3 000 automóviles. 03 Munoz UNIDAD 3. debe multiplicarse la distancia por el costo de transporte que. Tabla 3.16 5 380  0. otra en Michoacán y otra en Nayarit. uno en México y otro en Guadalajara.16 Nayarit 2 550  0.16 1 700  0. 8 2 000 Michoacán 400 432 3 000 Nayarit 408 272 2 400 4 600 2 800 7 400 Demanda 03 Munoz UNIDAD 3.indd 37 México 02/03/11 01:57 PM .2 272x32 3 Nayarit Formas de enviar automóviles desde la fábrica hasta los puntos de venta. Michoacán.8 x12 2 000 2 000 + Michoacán 400 x21 432 x22 3 000 3 000 + Nayarit 408 x31 272 x32 2 400 2 400 = Demanda 4 600 2 800 7 400 7 400 4 600 + 2 800 = 7 400 Nótese que la demanda es igual a la oferta Min Z = 320 x11 + 860.1 Guanajuato 320x11 1 860. sin embargo.8x12 + 400x21 + 432x22 + 408x31 + 272x32 Sujeto a: x11 + x12 ≤ 2 000 x21 + x22 ≤ 3 000 Oferta x31 + x32 ≤ 2 400 x11 + x21 + x31 = 4 600 x12 + x22 + x32 = 2 800 Demanda xij ≥ 0 El modelo de programación lineal puede resolverse con el método símplex.3. Nayarit) j = Destino (México. Donde: i = Origen (Guanajuato. la estructura especial de las restricciones nos permite solucionarlo de una manera más conveniente con ayuda de la tabla símplex de transporte que se muestra a continuación: Origen Destino Guadalajara Oferta Guanajuato 320 860. Sea xij = Número de automóviles enviados del origen (i) al destino (j). Guadalajara) Origen Destino México Guadalajara Oferta Guanajuato 320 x11 860.8x12 1 México 2 Guadalajara Modelos de transporte 37 400x21 Michoacán 432x22 2 408x31 Figura 3. de manera simultánea. no obstante. Si queda sin tachar un renglón o una columna. B. C) con una oferta de 120. 3) que es de 150. tache sólo uno de ellos y deje una oferta o demanda de 0 en el renglón o columna no tachado.38 UNIDAD III Transporte y asignación Determinación de la solución inicial Un modelo de transporte general con m puntos de origen y n puntos de destino posee m + n ecuaciones de restricción.1. 11 y 9 pesos. Pasos para aplicar el método de la esquina noroeste A continuación desglosaremos los pasos para aplicar este método: Paso 1. Regrese al paso 1. el modelo tiene m + n – 1 variables básicas.indd 38 02/03/11 01:57 PM . avance al siguiente cuadro a la derecha si acaba de tachar una columna o al inferior si ha tachado un renglón. Paso 2. 3). Los costos de envío de la granja A a las rosticerías 1. respectivamente. La estructura especial del modelo de transporte admite una solución básica inicial no artificial empleando uno de los tres métodos: • Método de la esquina noroeste • Método del costo menor • Método de aproximación de Vogel La diferencia entre los tres métodos es la calidad de la solución básica inicial. 2. de lo contrario.3 Esquina noroeste de la tabla símplex. deténgase. Desde este punto de vista general. Así. reste la cantidad asignada. 2. dan 0. 2 y 3 son de 10. 03 Munoz UNIDAD 3. B.1 Método de la esquina noroeste El método de la esquina noroeste empieza en el cuadro (ruta) de la esquina noroeste de la tabla símplex (variable x11) (véase figura 3. la peor.3). Asigne tanto como sea posible al cuadro seleccionado y ajuste las cantidades asociadas de oferta y demanda. 2 Tenemos 3 granjas de pollos (A. 5 y 3 pesos y los de la granja C son de 7. C) a las rosticerías (1. debido a que el modelo de transporte siempre está equilibrado. pues cuando ésta es más precisa da un valor objetivo más pequeño. por pollo. 130 y 250 pollos cada una. La ventaja es que el método de la esquina noroeste implica menor cálculo. Paso 3. 15 y 18 pesos por pollo. 3. que deben cubrir la demanda de 3 rosticerías (1. Tache el renglón o la columna con 0 oferta o demanda para indicar que no pueden hacerse asignaciones adicionales en ese renglón o columna. 130 y 220 pollos. Elabore el modelo de programación lineal correspondiente y determine cuántos pollos se deben enviar desde las granjas (A. Esquina noroeste Figura 3. una para cada punto de origen y destino. luego. los de la granja B son de 1. Si tanto el renglón como la columna. el método de Vogel aporta la mejor solución básica inicial y el método de la esquina noroeste. una de estas ecuaciones debe ser redundante. Para resolver este problema. Tache el renglón o la columna con 0 oferta o demanda para indicar que no pueden hacerse asignaciones adicionales en ese renglón o columna. de manera simultánea. tache sólo uno de ellos y deje una oferta o demanda de 0 en el renglón o columna no tachados. como la oferta es igual a la demanda. la granja A ya no puede vender más. Paso 1. Paso 2. dan 0. se dice que la tabla está en equilibrio. en primer lugar se debe asignar tanto como sea posible al cuadro de la esquina noroeste seleccionado (en este caso sería A. con lo cual sólo quedan por satisfacer 30 pollos. Por lo tanto. Si tanto el renglón como la columna.1 Rosticería 1 2 3 A 10 15 18 120 B 1 5 3 130 C 7 11 9 250 150 130 220 500 Granjas Demanda (pollos) Modelos de transporte 39 Oferta (pollos) Nota: La oferta no puede ser mayor que lo que se tiene en la demanda. 1) y ajustar las cantidades asociadas de oferta y demanda mediante la resta de la cantidad asignada. por lo que se cancelan los demás espacios. 03 Munoz UNIDAD 3. Rosticería Granjas A 1 10 120 2 3 Oferta (pollos) 15 18 120 – 120 = 0 B 1 5 3 130 C 7 11 9 250 Demanda (pollos) 150 – 120 = 30 130 220 380 Observe que. Rosticería 1 2 3 A 10 15 18 120 B 1 5 3 130 C 7 11 9 250 150 130 220 500 Granjas Demanda (pollos) Oferta (pollos) Los recuadros representan las siguientes referencias: Cuadro seleccionado (esquina noroeste) Oferta de la granja A: 120 pollos Demanda de la rosticería 1: 150 pollos Enviamos 120 pollos a la rosticería 1 que pide 150.3.indd 39 02/03/11 01:57 PM . al entregar 120 pollos. Se tacha porque se agota la oferta de la granja A Rosticería Granjas 1 A 10 120 2 3 Oferta (pollos) 15 18 120 – 120 = 0 B 1 5 3 130 C 7 11 9 250 Demanda (pollos) 150 – 120 = 30 130 220 380 Cuadro seleccionado (esquina noroeste) Se le asignan 30 ya que la rosticería 1 sólo pide 30 y la granja B tiene 30 disponibles Se tacha porque satisface la demanda de la rosticería 1 Rosticería Granjas 1 2 3 Oferta (pollos) A 10 120 15 18 0 B 11 30 5 3 130 – 30 = 100 C 7 11 9 250 Demanda (pollos) 30 – 30 = 0 130 220 350 100 pollos disponibles que oferta la granja B Ahora. Rosticería Granjas 03 Munoz UNIDAD 3. la granja A no tiene pollos para vender y la rosticería 1 cubrió su demanda.40 UNIDAD III Se tacha porque se agota la oferta de la granja A Transporte y asignación Rosticería Granjas 1 A 10 120 2 3 Oferta (pollos) 15 18 120 – 120 = 0 B 1 5 3 130 C 7 11 9 250 Demanda (pollos) 150 – 120 = 30 130 220 380 Paso 3. avanzamos a la siguiente esquina noroeste para satisfacer los 30 pollos que solicita la rosticería 1. Regrese al paso 1.indd 40 1 2 3 Oferta (pollos) 18 0 3 100 – 100 = 0 A 10 120 15 B 11 30 5 100 C 7 11 9 250 Demanda (pollos) 0 130 – 100 = 30 220 250 Se tacha porque se agota la oferta de la granja B 02/03/11 01:57 PM . deténgase. Como se tachó el renglón de la granja A. Si queda sin tachar un renglón o una columna. avance al siguiente cuadro a la derecha si acaba de tachar una columna o al inferior si ha tachado un renglón. Se avanza a la siguiente rosticería (2) y se le asigna lo más que se pueda a la granja B. de lo contrario. la granja C. la granja B. 30 pollos a la rosticería 1 y 100 al 2.3. la solución óptima es: La granja A debe enviar 120 pollos a la rosticería 1. 120 A Granjas de pollos 30 B C Figura 3. que deben ser proporcionados por la granja C ya que la B agotó su oferta. Rosticería Granjas 1 A 10 120 B 11 30 C 7 Demanda (pollos) 0 2 3 Oferta (pollos) 15 18 0 3 0 5 100 11 30 0 9 220 220 – 220 = 0 220 – 220 = 0 Este punto es donde se satisface por completo la demanda con la oferta En este ejemplo. Rosticería Granjas 1 A 10 120 B 11 30 2 3 Oferta (pollos) 15 18 0 3 0 9 250 – 30 = 220 220 220 5 100 C 7 11 Demanda (pollos) 0 30 – 30 = 0 Siguiente esquina noroeste No tiene demanda Rosticería Granjas 30 Se tacha porque se satisface la demanda de la rosticería 2 1 A 10 120 B 11 30 C 7 Demanda (pollos) 0 No tienen oferta 2 3 Oferta (pollos) 15 18 0 Oferta satisfecha 5 100 3 0 11 30 9 250 – 30 = 220 220 220 0 Siguiente esquina noroeste Demanda satisfecha Debido a que la demanda de la rosticería 2 ya fue satisfecha. se tacha y se avanza a la siguiente rosticería.4).indd 41 100 30 220 1 2 Rosticerías 3 Diagrama de distribución de pollos.4 03 Munoz UNIDAD 3. Los costos de envío de pollos de las granjas son: Min Z = 10 (120) + 1 (30) + 5 (100) + 11 (30) + 9 (220) = 4 040 pesos ⬖ El costo de envío será de 4 040 pesos.1 Modelos de transporte 41 La rosticería 2 aún necesita 30 pollos. 02/03/11 01:57 PM . 30 pollos al 2 y 220 al 3 (figura 3. después. tache sólo uno de ellos y deje una oferta o demanda de 0 en el renglón o columna no tachado.2 Método del costo menor El método del costo menor permite encontrar una mejor solución inicial pues se concentra en las rutas más económicas.indd 42 500 – 130 = 370 02/03/11 01:57 PM . 130 y 220 pollos. respectivamente. avance al siguiente cuadro con el costo más bajo por unidad de la tabla no tachada. 3). 3 Para este tema. deténgase. Paso 3. Paso 2. Si tanto un renglón como una columna se satisfacen de manera simultánea. que deben cubrir la demanda de 3 rosticerías (1. Asígnele tanto como sea posible al cuadro con el costo más bajo por unidad de toda la tabla. Rosticería 1 2 3 Oferta (pollos) A 10 15 18 120 B 1 5 3 130 C 7 11 9 250 150 130 220 Granjas Demanda (pollos) 03 Munoz UNIDAD 3. retomaremos el ejercicio que se trabajó en la sección anterior (método de la esquina noroeste). de lo contrario. Si tanto el renglón como la columna dan 0 de manera simultánea. Pasos para aplicar el método del costo menor A continuación desglosaremos los pasos para aplicar este método: Paso 1. con una oferta de 120. comienza por asignarle tanto como sea posible al cuadro con el costo más bajo por unidad de toda la tabla. se busca el cuadro no tachado con el menor costo unitario y se repite el proceso hasta que. el costo de envío por pollo es de 5 pesos Rosticería 1 2 3 Oferta (pollos) A 10 15 18 120 B 1 5 3 130 C 7 11 9 250 150 130 220 500 Granjas Demanda (pollos) Nota: La oferta no puede ser mayor que la demanda Paso 1. Costos de envío de pollos de las granjas a las rosticerías Ejemplo: de la granja B a la rosticería 2. Tenemos 3 granjas (A. se tacha el renglón o la columna satisfechos y se ajusta la cantidad de la oferta y de la demanda conforme a ello. al final. 130 y 250 pollos. que es de 150. sólo se tacha uno de ellos. Asígnele tanto como sea posible al cuadro con el menor costo unitario de toda la tabla y ajuste las cantidades asociadas de oferta y demanda mediante la resta de la cantidad asignada. C). Se concentra en las rutas económicas. Método del costo menor.1. Asigna el costo más bajo a cada unidad y después se ajusta la cantidad de la oferta y la demanda. 2. Regrese al paso 1.42 UNIDAD III Transporte y asignación 3. Si queda sin tachar un renglón o una columna. En vez de empezar con el cuadro noroeste. B. Tache el renglón o la columna con 0 oferta o demanda para indicar que no pueden hacerse asignaciones adicionales en ellos. luego. queda exactamente un renglón o una columna no tachados. Rosticería Granjas A B 1 2 3 Oferta (pollos) 10 15 18 120 5 3 130 – 130 = 0 250 1 130 C 7 11 9 Demanda (pollos) 150 – 130 = 20 130 220 500 – 130 = 370 1 2 3 Oferta (pollos) 10 15 18 120 Rosticería Granjas A B 1 130 5 3 0 C 7 20 11 9 250 – 20 = 230 130 220 370 – 20 = 350 Demanda (pollos) 20 – 20 = 0 Siguiente costo más bajo Se tacha porque se satisface la demanda de la rosticería 1 Tomar en cuenta que la rosticería pide aún 20 pollos que va a satisfacer la granja C Rosticería Granjas A 1 2 3 Oferta (pollos) 10 15 18 120 3 0 B 1 130 5 C 7 20 11 Demanda (pollos) 0 9 130 Rosticería A 230 – 220 = 10 350 – 220 = 130 Se tacha porque satisface la demanda de la rosticería 3 1 2 3 Oferta (pollos) 10 15 18 120 5 3 0 B 1 130 C 7 20 Demanda (pollos) 220 220 – 220 = 0 Siguiente costo más bajo.3.1 Modelos de transporte 43 Paso 2. se le asigna lo que pide la rosticería 3 (220) quedando aún 10 pollos por colocar de la granja C Granjas Se tacha porque se agota la oferta de la granja B 0 11 10 130 – 10 = 120 9 220 0 10 – 10 = 0 Se tacha porque se agota la oferta de la granja B 130 – 10 = 120 Siguiente costo más bajo sólo se le asigna 10 pollos ya que la granja C sólo dispone de 10 y la rosticería 2 aún requiere 10 pollos 03 Munoz UNIDAD 3. Si tanto el renglón como la columna dan 0 de manera simultánea. Tache el renglón o la columna con 0 oferta o demanda para indicar que no pueden hacerse asignaciones adicionales en ellos.indd 43 02/03/11 01:57 PM . tache sólo uno de ellos y deje una oferta o demanda de 0 en el renglón o columna no tachados. D). lo cual demuestra que no siempre este método es mejor.indd 44 02/03/11 01:57 PM . D). 15 y 15 mil pares de zapatos cada una. B. 2. de lo contrario. 03 Munoz UNIDAD 3. 15. C. Regrese al paso 1. C. Rosticería Granjas 1 A 2 10 15 B 11 130 C 7 20 Demanda (pollos) 120 5 11 0 10 9 120 – 120 = 0 Último costo más bajo se le asigna el total de pollos disponibles de la granja A 3 Oferta (pollos) 18 120 – 120 = 0 3 0 0 220 0 120 – 120 = 0 Note que tanto la demanda como la oferta quedaron satisfechas El costo total por el envío de los pollos es: Min Z = 1 (130) + 7 (20) + 9 (220) + 11 (10) + 15 (120) = 4 160 Observe que el costo es mayor que en caso del método de la esquina noroeste. avance al siguiente cuadro con el costo más bajo por unidad de la tabla no tachada. Tienda Fábrica A B D Oferta (miles) 20 11 15 – 15 = 0 1 10 2 12 7 9 20 25 3 4 14 16 18 10 Demanda 5 15 15 15 50 – 15 = 35 C D Oferta (miles) 20 11 0 Tienda Fábrica 2 C 15 A B 1 10 2 12 7 9 20 25 5 14 16 18 10 – 5 = 5 0 15 15 35 – 5 = 30 3 Demanda 4 5–5=0 2 15 La oferta de la fila 1 llega al límite Se elimina porque se abastece la demanda de la columna A. B.44 UNIDAD III Transporte y asignación Paso 3. deténgase. Si queda sin tachar un renglón o una columna. Elabore el modelo de programación lineal correspondiente y determine cuántos pares de zapatos se van a enviar desde las fábricas (1. cuyas demandas ascienden a 5. 3) con una oferta de 15. respectivamente. 2. 4 Tres fábricas de calzado (1. 3) a cada una de las tiendas (A. 25 y 10 mil pares de zapatos. deben cubrir los pedidos de 4 tiendas (A. 1 Tienda Fábrica A B C D Oferta (miles) 1 10 2 15 20 11 15 – 15 = 0 2 12 7 0 9 20 25 14 16 18 10 15 – 15 = 0 15 15 30 3 4 Demanda 5 0 Modelos de transporte 45 Se elimina porque se abastece la demanda de la columna B Cabe que recordar que no se puede eliminar al mismo tiempo una fila y una columna.indd 45 02/03/11 01:57 PM .3. lo que da como resultado: 03 Munoz UNIDAD 3. por eso se otorga 0 a B2 (note que no se eliminó desde la primera tabla) Tienda Fábrica A B 1 10 2 15 2 12 7 0 3 4 Demanda 5 C D Oferta (miles) 20 11 0 20 25 – 15 = 10 9 15 14 16 18 10 – 5 = 5 0 15 – 15 = 0 15 30 – 15 = 15 0 Se elimina porque se abastece la demanda de la fila C Tienda Fábrica A 1 10 2 12 3 4 Demanda B 2 C 5 20 15 7 D 9 16 0 0 0 11 10 20 15 14 Oferta (miles) 18 15 – 15 = 0 25 – 15 = 10 5 15 – 5 = 10 5–5=0 15 – 5 = 10 La oferta de la fila 3 llega al límite Tienda Fábrica A B C 1 10 2 15 2 12 7 0 3 Demanda 4 5 0 D 20 9 15 14 16 0 0 11 Oferta (miles) 10 20 18 0 10 – 10 = 0 5 10 – 10 = 0 Llega al límite La oferta de la fila 3 0 10 – 10 = 0 Se abastece la demanda de la columna D Nota: En este punto se llega al abastecimiento de la demanda y se agota la oferta. B. Los costos de envío son: Min Z = 2(15) + 4(5) + 7(0) + 9(15) + 5(18) + 20(10) = $ 475 000 ⬖ El costo de envío será de $ 475 000. regrese al paso 1.3 Método Vogel Este método es una versión mejorada del de costo menor que.46 UNIDAD III Transporte y asignación Tienda Fábrica A B C 1 10 2 15 2 12 7 0 3 4 Demanda 5 0 D 20 9 11 16 0 0 0 10 20 15 14 Oferta (miles) 18 0 0 5 0 0 En este ejemplo la solución óptima es: En este caso. Rosticería 1 2 3 Oferta pollos A 10 15 18 120 B 1 5 3 130 C 7 11 9 250 150 130 220 500 Granjas Demanda (pollos) 03 Munoz UNIDAD 3. 130 y 220 pollos. deben cubrir la demanda de 3 rosticerías (1. 5 000 pares de la fábrica 3 a la tienda A y 5 000 a la tienda D.indd 46 Costos de envío de pollos de las granjas a las rosticerías 02/03/11 01:57 PM . Tres granjas de pollos (A. C). por último. 130 y 250. Si queda sin tachar un renglón o una columna con una oferta o demanda positiva. Pasos para aplicar el método de Vogel A continuación detallamos los pasos a seguir para aplicar este método: Paso 1. respectivamente.1. si se satisfacen de manera simultánea un renglón y una columna. Paso 2. Paso 3. de la fábrica 1 se deben enviar 15 000 pares de zapatos a la tienda B y 10 000 pares a la tienda D. En el caso de cada renglón o columna con una oferta o una demanda estrictamente positiva. Identifique el renglón o columna con penalidad más grande y asígnele tanto como sea posible a la variable con el costo más bajo. al final. ajuste la oferta y demanda y tache el renglón o columna satisfechos. de lo contrario. deténgase. 5 Para explicar este tema se retomarán los ejercicios que se trabajaron en las dos secciones anteriores (método de la esquina noroeste y método del costo menor) para. sólo se tacha uno de ellos. 15 000 pares a la tienda C y. de la fábrica 2. 3. determine una medida de penalidad restando el elemento del costo por unidad más bajo del renglón o columna del siguiente elemento de menor costo. con una oferta de 120. 2. precise las variables básicas del renglón o columna por el método del costo menor. Si queda un renglón o una columna sin tachar con 0 oferta y 0 demanda. poder hacer una comparación entre los métodos que se utilizaron. para optimizar los costos de envío. 3) que es de 150. por lo regular. produce mejores soluciones iniciales. En esta tabla se puede observar que la mayor penalidad es 6 en 3 diferentes lugares. se le asigna lo más que se pueda al renglón elegido (B). Se elige esta columna pues el costo menor elegido es 1. Ajuste la oferta y demanda y tache el renglón o columna satisfechos. si se satisfacen de manera simultánea un renglón y una columna. 130 de los 150 pollos que se piden. debemos elegir sólo una de las tres posibilidades y buscar el costo menor de estas tres. Rosticería Granjas A B 03 Munoz UNIDAD 3. en este caso. En el caso de cada renglón o columna con una oferta o una demanda estrictamente positiva.indd 47 1 1 2 3 Oferta (pollos) Penalidad 1 10 15 18 120 15 – 10 = 5 5 3 130 3–1=2 9–7=2 130 C 7 11 9 250 Demanda (pollos) 150 130 220 380 Penalidad 1 7–1=6 11 – 5 = 6 9–3=6 02/03/11 01:57 PM . Rosticería 1 2 3 Oferta (pollos) Penalidad 1 A 10 15 18 120 15 – 10 = 5 B 1 5 3 130 3–1=2 C 7 11 9 250 9–7=2 Demanda (pollos) 150 130 220 380 Penalidad 1 7–1=6 11 – 5 = 6 9–3=6 Granjas Costos más bajos por renglón y columna Paso 2.1 Modelos de transporte 47 Paso 1. aunque las penalidades sean 6 Rosticería 1 2 3 Oferta (pollos) Penalidad 1 A 10 15 18 120 15 – 10 = 5 B 1 5 3 130 3–1=2 C 7 11 9 250 9–7=2 Demanda (pollos) 150 130 220 380 Penalidad 1 7–1=6 11 – 5 = 6 9–3=6 Granjas Después de elegir el costo menor (1). establezca una medida de penalidad mediante la resta del elemento de menor costo unitario del renglón o columna del siguiente elemento de costo más bajo. por ello. Identifique el renglón o columna con penalidad más grande y asígnele tanto como sea posible a la variable con el costo más bajo. sólo se tacha uno de ellos. mientras que los demás son 5 y 3.3. Rosticería Granjas A B 1 1 2 3 Oferta (pollos) Penalidad 2 10 15 18 120 15 – 10 = 5 5 3 130 – 130 = 0 130 C 7 11 9 250 Demanda (pollos) 150 – 130 = 20 130 220 380 Penalidad 2 10 – 7 = 3 15 – 11 = 4 18 – 9 = 9 9–7=2 Ahora se elige esta columna puesto que es la penalidad más grande 03 Munoz UNIDAD 3.48 UNIDAD III Transporte y asignación Ya asignada la cantidad de 130. se tachan los renglones o columnas satisfechos con cero oferta o cero demanda. se ajustan las cantidades de oferta y demanda como se muestra a continuación. Rosticería Granjas A B 1 1 2 3 Oferta (pollos) Penalidad 1 10 15 18 120 15 – 10 = 5 5 3 130 – 130 = 0 3–1=2 9–7=2 130 C 7 11 9 250 Demanda (pollos) 150 – 130 = 20 130 220 380 Penalidad 1 7–1=6 11 – 5 = 6 9–3=6 La siguiente etapa implica regresar al paso 1 y encontrar otra penalidad (penalidad 2) mediante la resta de los dos valores más pequeños por renglón y por columna. Rosticería Granjas A B 1 1 2 3 Oferta (pollos) Penalidad 1 10 15 18 120 15 – 10 = 5 5 3 130 – 130 = 0 3–1=2 9–7=2 130 C 7 11 9 250 Demanda (pollos) 150 – 130 = 20 130 220 380 Penalidad 1 7–1=6 11 – 5 = 6 9–3=6 Luego.indd 48 02/03/11 01:57 PM . se ajustan las cantidades de oferta y demanda como se muestra a continuación.3.1 Modelos de transporte 49 Una vez que se eligió la columna. Valor más pequeño de la columna no tachado Rosticería Granjas A B 1 2 3 Oferta (pollos) Penalidad 2 10 15 18 120 15 – 10 = 5 5 3 130 – 130 = 0 1 130 C 7 11 9 250 Demanda (pollos) 150 – 130 = 20 130 220 380 Penalidad 2 10 – 7 = 3 15 – 11 = 4 18 – 9 = 9 9–7=2 Al cuadro elegido se le asignan 220 pues la oferta es de 250. Rosticería Granjas A B 03 Munoz UNIDAD 3. Rosticería Granjas A B 1 2 3 Oferta (pollos) Penalidad 2 10 15 18 120 15 – 10 = 5 5 3 130 – 130 = 0 220 250 1 130 C 7 11 9 Demanda (pollos) 150 – 130 = 20 130 220 Penalidad 2 10 – 7 = 3 15 – 11 = 4 18 – 9 = 9 9–7=2 380 Luego de asignar la cantidad de 220.indd 49 1 1 2 3 Oferta (pollos) Penalidad 2 10 15 18 120 15 – 10 = 5 5 3 130 – 130 = 0 220 250 – 220 = 30 130 C 7 11 9 Demanda (pollos) 150 – 130 = 20 130 220 – 220 = 0 Penalidad 2 10 – 7 = 3 15 – 11 = 4 18 – 9 = 9 9–7=2 380 02/03/11 01:57 PM . se asigna al valor más pequeño lo más que se pueda. 50 UNIDAD III Transporte y asignación Luego. se tachan los renglones o columnas satisfechos con cero oferta o cero demanda. se asigna al valor más pequeño lo más que se pueda. puesto que es la penalidad más grande 03 Munoz UNIDAD 3. Rosticería Granjas A B 1 1 2 3 Oferta (pollos) Penalidad 2 10 15 18 120 15 – 10 = 5 5 3 130 – 130 = 0 220 250 – 220 = 30 130 C 7 11 9 Demanda (pollos) 150 – 130 = 20 130 220 – 220 = 0 Penalidad 2 10 – 7 = 3 15 – 11 = 4 18 – 9 = 9 9–7=2 380 La siguiente etapa exige regresar al paso 1 y encontrar otra penalidad (penalidad 3) mediante la resta de los dos valores más pequeños por renglón y por columna. Rosticería Granjas A B 1 2 3 Oferta (pollos) Penalidad 3 10 15 18 120 15 – 10 = 5 5 3 130 – 130 = 0 1 13 C 7 11 Demanda (pollos) 150 – 130 = 20 130 Penalidad 3 10 – 7 = 3 15 – 11 = 4 9 220 250 – 220 = 30 220 – 220 = 0 9–7=2 380 Si se eligió la columna.indd 50 02/03/11 01:57 PM . Rosticería Granjas A B 1 1 2 3 Oferta (pollos) Penalidad 3 10 15 18 120 15 – 10 = 5 5 3 130 – 130 = 0 130 C 7 11 Demanda (pollos) 150 – 130 = 20 130 Penalidad 3 10 – 7 = 3 15 – 11 = 4 9 220 220 – 220 = 0 250 – 220 = 30 11 – 7 = 4 380 Ahora se elige este renglón. indd 51 1 1 2 3 Oferta (pollos) Penalidad 3 10 15 18 120 – 20 = 100 15 – 10 = 5 5 3 130 – 130 = 0 130 C 7 11 Demanda (pollos) 150 – 130 = 20 20 – 20 = 0 130 Penalidad 3 10 – 7 = 3 15 – 11 = 4 9 220 220 – 220 = 0 250 – 220 = 30 11 – 7 = 4 380 02/03/11 01:57 PM . Rosticería Granjas A B 03 Munoz UNIDAD 3. se asigna al valor más pequeño lo más que se pueda.1 Modelos de transporte 51 Si se eligió el renglón.3. se tachan los renglones o columnas satisfechos con cero oferta o cero demanda. Rosticería Granjas 1 2 3 Oferta (pollos) Penalidad 3 15 – 10 = 5 A 10 20 15 18 120 B 1 130 5 3 130 – 130 = 0 C 7 11 Demanda (pollos) 150 – 130 = 20 130 Penalidad 3 10 – 7 = 3 15 – 11 = 4 9 220 220 – 220 = 0 250 – 220 = 30 11 – 7 = 4 380 Luego. Valor más pequeño del renglón no tachado Rosticería Granjas A B 1 1 2 3 Oferta (pollos) Penalidad 3 10 15 18 120 15 – 10 = 5 5 3 130 – 130 = 0 130 C 7 11 Demanda (pollos) 150 – 130 = 20 130 Penalidad 3 10 – 7 = 3 15 – 11 = 4 9 220 220 – 220 = 0 250 – 220 = 30 11 – 7 = 4 380 Al cuadro elegido se le asignan 20 pollos pues es lo último que se pide aunque A ofrezca aún 120 pollos. con lo cual el cuadro queda de la siguiente forma. En este caso se elige el costo menor de la columna no tachada.52 UNIDAD III Transporte y asignación De inmediato se regresa al paso 1. Rosticería Granjas A B 1 1 2 3 Oferta (pollos) 10 15 18 120 – 20 = 100 5 3 130 – 130 = 0 130 C 7 11 Demanda (pollos) 150 – 130 = 20 20 – 20 = 0 130 9 220 220 – 220 = 0 250 – 220 = 30 380 Se elige este cuadro Se le asigna lo más que se pueda al cuadro elegido. pero como ya sólo queda una columna no tachada se continúa el proceso por medio del método del costo menor.indd 52 1 1 2 3 Oferta (pollos) 10 15 18 120 – 20 = 100 5 3 130 – 130 = 0 130 C 7 11 Demanda (pollos) 150 – 130 = 20 20 – 20 = 0 130 9 220 220 – 220 = 0 250 – 220 = 30 380 02/03/11 01:57 PM . Rosticería Granjas A B 1 1 2 3 Oferta (pollos) 10 15 18 120 – 20 = 100 5 3 130 – 130 = 0 130 C 7 11 Demanda (pollos) 150 – 130 = 20 20 – 20 = 0 130 9 220 220 – 220 = 0 250 – 220 = 30 380 Columna no tachada que se resuelve por medio del método de costo menor El método de costo menor establece que se debe elegir el costo más pequeño de entre todos los elementos. Rosticería Granjas A B 03 Munoz UNIDAD 3. en este caso. 30 pollos. 2 Método de cruce de arroyo o de piedra rodante El método de cruce de arroyo o de piedra rodante recibe su nombre debido a que los primeros en utilizarlo le denominaban “celda de piedra” a las celdas con asignación a las cuales se desea hacer una asignación.indd 53 Método de cruce de arroyo.3. 02/03/11 01:57 PM . es decir. pisar sólo donde es posible apoyarse. se asignan 100 pollos al cuadro final no tachado y se ajustan las ofertas y demandas correspondientes. en este método es necesario encontrar un procedimiento de reasignación. 3. pues se debe pisar sólo en las celdas de piedra. respectivamente) se manejó el mismo ejemplo para poder hacer una comparación entre estos tres métodos y. en estas últimas. no es posible apoyarse. no en las de agua.2 Método de cruce de arroyo o de piedra rodante 53 En seguida se tachan los renglones o columnas satisfechos con cero oferta o cero demanda. Método a través del cual debe encontrarse un procedimiento de reasignación en el que sólo se pisen las celdas de piedra y ninguna de agua pues. 03 Munoz UNIDAD 3. Rosticería Granjas 1 2 A 10 20 B 1 130 C 7 Demanda (pollos) 150 – 130 = 20 20 – 20 = 0 15 100 5 11 30 130 – 30 = 100 100 – 100 = 0 9 3 Oferta (pollos) 18 120 – 20 = 100 100 – 100 = 0 3 130 – 130 = 0 220 250 – 220 = 30 30 – 30 = 0 220 – 220 = 0 380 Como ya todo está asignado. la solución lineal a este problema es: Min Z = 10 (20) + 1 (130) + 15 (100) + 11 (30) + 9 (220) = 4 140 En el problema de los modelos anteriores (modelos de la esquina noroeste. del costo menor y modelo de Vogel. como puede observarse. Rosticería Granjas 1 2 3 Oferta (pollos) A 10 20 15 18 120 – 20 = 100 B 1 130 5 3 130 – 130 = 0 C 7 11 Demanda (pollos) 150 – 130 = 20 20 – 20 = 0 30 130 – 30 = 100 9 220 250 – 220 = 30 20 – 20 = 0 220 – 220 = 0 380 Por último. ninguno de ellos es cien por ciento seguro ya que tendría que hacerse una comprobación previa antes de poder tomar una decisión. con valor asignado. D1. D2) y. asigne la cantidad que tiene la celda a la variable de entrada y. donde exista algún valor negativo. el procedimiento finaliza y se dice que la solución actual es la óptima. después continuar en (S3. de forma horizontal y/o vertical. es decir. que puede ser: pasar primero por (S1.indd 54 02/03/11 01:57 PM . Origen 1 2 3 Oferta A 5 10 10 55 B 20 30 20 80 C 10 20 30 75 Demanda 70 100 40 En este caso aplicaremos el método del costo mínimo para asignar los valores a la tabla. en caso contrario. Si todos los IMij calculados son mayores o iguales a cero. D1). 1 Con los datos del problema que se incluyen en la tabla siguiente. después ir hasta la siguiente celda llena que nos dé dirección diferente. Cabe destacar que no importa el orden en que hayamos encontrado la trayectoria. El IMij se calcula mediante la suma y resta de manera alternativa de los costos de las celdas sobre la trayectoria. reasigne los valores de manera que queden con los totales que la tabla exige. Elija la variable de entrada correspondiente al menor (IMij) y la variable de salida que corresponda a la casilla de menor valor asignado en la trayectoria y que se reste y sume de los demás según sea el caso en el cálculo de IMij. D1). de lo cual resulta: Origen s1 s2 s3 Demanda D1 5 55 20 10 D2 D3 Oferta 10 10 55 30 20 40 20 15 70 60 100 40 30 80 75 40 Z = (5)(55) + (30)(40) + (20)(40) + (10)(15) + (20)(60) = 3 625 Paso 1. D2). por último. La siguiente celda llena es (S3. Paso 3. determine la solución óptima. Calcule el índice de mejoramiento (IMij). D1) y terminar en S1. De acuerdo con el costo más bajo que eligió en el paso anterior. indicará que hay una mejor solución a la que aquí se presenta. Para hallar la trayectoria que debe seguir la celda vacía S1. por lo tanto. Regrese al paso 1. D2. es decir (S3. la celda para cerrar la trayectoria es (S2. Sea k el valor de dicha casilla. de cada celda vacía hasta que encuentre una trayectoria cerrada que comience en dicha celda y continúe alternativamente sobre las celdas llenas. pues bien podríamos haber iniciado en (S2. debe buscarse la opción que permita pasar por celdas llenas. 03 Munoz UNIDAD 3. Asigne a la casilla de entrada k unidades y recalcule de nueva cuenta los valores de las casillas sobre la trayectoria. Sea k el valor de dicha casilla. Paso 2.54 UNIDAD III Transporte y asignación Pasos para resolver el método de arroyo A continuación explicaremos cuáles son los pasos que se deben seguir para aplicar este método: Paso 1. Paso 4. Elija la variable de entrada correspondiente a la menor (IMij) y la variable de salida que corresponda a la casilla de menor valor asignado y que se reste en el cálculo del IMij. D2). D1). (S3.3. D3 es (S1. a veces.indd 55 D1 5 55 D2 D3 Oferta 10 10 55 20 Inicio 30 10 20 15 70 20 40 60 100 40 30 80 Note la trayectoria de la celda (S2. D1) y (S1. no en las cantidades que hemos asignado a cada una de las celdas. D1). El índice de mejoramiento (IM) de las celdas S1 y D2. D2). se encuentran con esta ruta. D2) y (S3. (S2. D2) 80 75 40 Nota: Las flechas indican la trayectoria que debe seguirse para asignar nuevos valores. D1). la trayectoria tuvo que pasar por todas las celdas llenas que. D3). el IM quedaría como sigue: IM13 = 10 – 20 + 30 – 20 + 10 – 5 = 5 La trayectoria para la próxima celda vacía (S2. La flecha roja especifica dónde comienza la trayectoria. (S3. D1) 75 40 02/03/11 01:57 PM . Origen s1 D1 5 55 s2 s3 20 10 D2 D3 Oferta 10 Inicio 10 55 30 40 20 15 Demanda 20 70 60 100 40 30 Note la trayectoria de la celda (S1. (S2. Origen s1 s2 s3 Demanda 03 Munoz UNIDAD 3. D1) sería:(S2. para conocer los índices de mejoramiento nos debemos enfocar en los costos.2 Método de cruce de arroyo o de piedra rodante 55 Recuerde que. D3). D2). (S3. IM12 = 10 – 5 + 10 – 20 = – 5 La trayectoria que debe seguirse para la celda vacía S1. Como podemos observar. Origen s1 s2 s3 Demanda D1 5 55 20 10 D2 D3 Oferta 10 10 Inicio 55 30 20 40 20 15 70 60 100 40 30 Note la trayectoria de la celda (S1. D3) 80 75 40 En consecuencia. D2). (S2. en esta ocasión. Sea k el valor de dicha casilla. 10 y 20. Como corresponde. 5.56 UNIDAD III Transporte y asignación Por lo tanto. la variable de entrada es donde está la celda (S1. ningún valor sea negativo. 5. Origen s1 s2 s3 Demanda D1 5 55 20 10 D2 D3 Oferta 10 10 55 30 20 40 40 60 30 Inicio 20 15 70 100 80 75 40 Con ello. el IM sería: IM33 = 30 – 20 + 30 – 20 = 20 Reuniendo todos los IMij se tiene lo siguiente: note que el valor es negativo IM12 = 10 – 5 + 10 – 20 = –5 IM13 = 10 – 20 + 30 – 20 + 10 – 5 = 5 IM21 = 20 – 30 + 20 – 10 = 0 IM33 = 30 – 20 + 30 – 20 = 20 Paso 2. D2) que elegimos debido a que ahí se encuentra el índice negativo. D3). el índice de mejoramiento es: IM21 = 20 – 30 + 20 – 10 = 0 La trayectoria para la siguiente celda vacía y última (S3. Celda vacía a la cual reasignaremos un nuevo valor por tener un índice de mejoramiento negativo Costo más bajo que sigue la trayectoria Origen s1 D1 55 s2 D2 Oferta D1 5 Inicio 10 20 40 30 10 60 20 40 10 55 20 80 30 75 15 s3 70 100 40 Los costos de la trayectoria de esta celda son: 10. (S3. Como en este caso IM12 es negativo. es decir. D2) y (S2. tomaremos el costo más bajo de la trayectoria. Paso 3. en el siguiente cálculo. Elija la variable de entrada que es la correspondiente a la menor (IMij) y la variable de salida que corresponda a la casilla de menor valor asignado y que se reste en el cálculo del IMij. Recordemos la trayectoria que seguía esta celda vacía. 03 Munoz UNIDAD 3. D3).indd 56 02/03/11 01:57 PM . En este caso. (S2. D3) quedaría así: (S3. tendremos que reasignar valores a las celdas con el objetivo de conseguir que. D2). quedan satisfechos. al reasignarle el valor de 55 para satisfacer la columna.2 Método de cruce de arroyo o de piedra rodante 57 Paso 4. debemos restar los 55 que reubicamos. Es por eso que a la celda (S3.3. La nueva tabla queda como se presenta a continuación: Origen D1 s1 5 s2 20 s3 D2 10 0 + 55 30 Oferta 10 55 20 40 10 40 20 15 Demanda D3 30 60 70 100 80 75 Observemos cómo el valor que tenía la celda de menor costo cambió a la celda donde teníamos un índice de mejoramiento negativo sumándolo 40 Nota: Recordemos que reasignamos el 55 a la celda vacía porque ésta tenía un valor negativo en su índice de mejoramiento y que reacomodamos los valores de la tabla de tal modo que cada columna y fila quedaran satisfechas con el valor asignado. tanto de la oferta como de la demanda. Origen s1 s2 s3 D1 D2 5 10 55 – 55 30 20 Oferta 10 55 20 40 10 Demanda 0 + 55 D3 40 20 15 + 55 60 – 55 70 100 30 80 75 40 Observe que los valores de la tabla. reasignar los valores de manera que queden con los totales que la tabla exige. sólo debemos mover los valores sobre los cuales se movió la trayectoria y todos los demás por los que no pasaba permanecerán iguales. que al inicio tenía un valor de 15. la nueva tabla quedaría de la siguiente forma: Origen s1 s2 s3 Demanda D1 D2 5 10 0 55 30 20 55 20 20 70 70 10 40 10 Oferta D3 5 100 40 30 80 75 40 Para obtener de nueva cuenta el costo total del problema se debe realizar la siguiente operación: Z = (55)(10) + (40)(30) + (5)(20) + (70)(10) + (40)(20) = 3 350 03 Munoz UNIDAD 3. Ahora. D2) también debe ser reasignada y. Para reasignar los valores con los que quedará la tabla para satisfacer los requisitos de la tabla total. La celda (S3. por lo tanto. debemos sumarle 15 + 55 = 70.indd 57 02/03/11 01:57 PM . de lo cual resulta: 60 – 55 = 5. por lo cual debemos asignar la cantidad que tiene esta celda (55) a la variable de entrada y. En este caso. por esa razón. el costo más bajo es 5. D1). 2 Con los datos relativos al problema de transporte elaboramos la siguiente tabla: Origen s1 s2 s3 Demanda Oferta D1 D2 D3 $8.indd 58 D1 D2 8 6 10 Inicio 4 85 9 40 8 110 7 Oferta D3 40 6 5 95 110 85 125 150 95 175 02/03/11 01:57 PM . que quedará así: Origen s1 s2 s3 D1 D2 8 6 10 85 4 9 125 40 8 110 7 Oferta D3 150 40 6 5 95 95 Demanda 110 85 175 Z = (85)(6) + (40)(10) + (110)(4) + (40)(8) + (95)(5) = 2 145 Origen s1 s2 s3 Demanda 03 Munoz UNIDAD 3.00 $8.00 110 85 175 125 150 95 En este caso utilizaremos el método de costo mínimo para asignar valores a la tabla. el resultado final nos indica que el valor de Z es 3 350.00 $5.58 UNIDAD III Transporte y asignación Luego. eso indica que hay otra solución factible Como en este caso no obtuvimos ningún valor negativo.00 $10.00 $9.00 $7.00 $4. de regreso al paso 1.00 $6. calculamos nuevamente los índices de las variables: IM11 = 5 – 10 + 20 – 10 = 5 IM13 = 10 – 10 + 30 – 20 = 10 IM21 = 20 – 30 + 20 – 10 = 0 IM33 = 30 – 20 + 30 – 20 = 20 Cuando existe un 0 en los índices de mejoramiento.00 $6. 3.2 Método de cruce de arroyo o de piedra rodante 59 El índice de mejoramiento de la celda vacía S1. 03 Munoz UNIDAD 3. D1: IM11 = 8 – 10 + 8 – 4 = 2 Origen s1 s2 s3 D1 D2 8 6 10 85 4 9 110 7 Oferta D3 40 8 Inicio 6 40 5 95 Demanda 110 85 175 D2 D3 125 150 95 IM22 = 9 – 8 + 10 – 6 = 4 Origen s1 s2 s3 D1 8 6 10 85 4 9 40 8 110 7 40 6 5 Inicio Demanda Oferta 95 110 85 175 D2 D3 125 150 95 IM31= 7 – 4 + 8 – 5 = 6 Origen s1 s2 s3 Demanda D1 8 6 10 85 4 9 40 8 110 7 40 6 5 Inicio 110 Oferta 85 95 125 150 95 175 IM32 = 6 – 6 + 10 – 5 = 5 En este caso.indd 59 02/03/11 01:57 PM . por lo tanto. la solución óptima indica que Z tiene un valor de 2 145. ninguno de los índices de mejora muestra valores negativos. Bodega Planta 1 2 3 4 5 Capacidad mensual 1 $20.60 UNIDAD III Transporte y asignación 3 Una cervecería cuenta con 3 plantas de embotellamiento de marcas genéricas.00 $36. La siguiente tabla sintetiza los costos de distribución.00 $35. Agregando la bodega ficticia. queda de la siguiente forma: Bodega Ficticia Capacidad mensual Planta 1 2 3 4 5 1 20 35 30 40 42 400 2 45 30 42 36 38 350 3 38 40 36 35 50 450 Necesidad mensual 150 300 200 250 175 125 Después de resolver el problema se tiene la siguiente solución inicial: Bodega Planta 1 2 3 Necesidad mensual 1 20 2 35 3 30 150 45 4 40 5 42 200 30 42 40 36 38 36 35 300 0 50 350 200 250 0 75 175 Capacidad mensual 400 50 250 150 0 50 300 38 Ficticia 125 450 125 Z = (150)(20) + (300)(30) + (200)(30) + (50)(42) + (50)(38) + (75)(50) + (250)(35) = 34 500 03 Munoz UNIDAD 3.00 $50.00 $42.00 $30.00 $40.00 $38. añadiremos otra columna antes de los valores finales con la cantidad que hace falta.indd 60 02/03/11 01:57 PM . por lo tanto.00 400 2 $45. las capacidades mensuales de las plantas y las necesidades de cada bodega expresadas todas ellas en cientos de cajas.00 350 3 $38. en este ejercicio.00 450 Necesidad mensual 150 300 200 250 175 Se puede observar que.00 $42. Para hacerlo. desde las cuales se distribuye el producto a 5 bodegas. debemos igualarlas. que en este caso es 125.00 $35.00 $36.00 $40. las cantidades de la demanda y la oferta no son iguales.00 $30. pero la solución que acabamos de hallar también satisface todos los lineamientos que se requerían. es necesario reasignar valores a la tabla mediante el método de asignación. Bodega Planta 1 2 3 Necesidad mensual 1 20 2 3 35 30 150 45 4 40 5 42 200 30 42 40 0 400 36 38 0 350 125 36 75 150 Capacidad mensual 50 225 38 Ficticia 300 35 50 250 200 250 0 125 175 450 125 Z = (150)(20) + (200)(30) + (50)(42) + (225)(30) + (125)(38) + (75)(40) + (250)(35) = 34 350 A continuación debemos calcular los índices de mejoramiento de cada celda vacía.3 Modelo de asignación El modelo de asignación es un caso especial del de transporte en donde cada fuente (origen) tiene una oferta de uno. y cada destino. 03 Munoz UNIDAD 3. Son problemas en donde a m elementos (por ejemplo. procederemos a asignar valores a la tabla. vendedores) se les debe asignar a n destinos. insertaremos la columna de la bodega ficticia para equilibrar la tabla. Modelo en el que cada fuente y cada destino poseen una demanda unitaria. que son: IM12 = 35 – 42 + 38 – 30 = 1 IM14 = 40 – 35 + 40 – 30 + 38 – 42 = 11 IM21 = 45 – 20 + 42 – 38 = 29 IM23 = 42 – 30 + 42 – 38 = 16 IM24 = 36 – 35 + 40 – 30 = 11 IM31 = 38 – 20 + 42 – 38 + 30 – 40 = 12 IM33 = 36 – 40 + 30 – 38 + 42 – 30 = 0 IM35 = 50 – 38 + 30 – 40 = 2 Observe que existe otra opción óptima para resolver este problema.indd 61 Modelo de asignación. Al final.3 Modelo de asignación 61 Luego de equilibrar los valores. 02/03/11 01:57 PM . una demanda unitaria. A continuación debemos calcular los índices de mejoramiento de cada una de las celdas vacías que son: IM12 = 35 – 42 + 38 – 30 = 1 IM14 = 40 – 42 + 50 – 35 = 13 IM21 = 45 – 20 + 42 – 38 = 29 IM23 = 42 – 30 + 42 – 38 = 16 IM24 = 36 – 38 + 50 – 35 = 13 IM31 = 38 – 20 + 42 – 50 = 10 IM32 = 40 – 30 + 38 – 50 = –2 IM33 = 36 – 30 + 42 – 50 = –2 Como aparecieron valores negativos. 3.3. Si el número de líneas que trazó en este paso es menor que m. 2. se vuelve al inicio de este paso. C. Paso 2. deben asignarse a cuatro destinos (1. existe uno más eficiente. réstele el menor elemento no cubierto por una línea a todos los elementos que no fueron eliminados por una línea. que cubran todos los ceros. B. sea igual a m. Los costos de la asignación aparecen en la tabla que a continuación se presenta: Destinos 1 Vendedores 2 3 4 A 16 7 10 9 B 4 14 8 7 C 9 10 5 11 D 4 6 8 12 Paso 1. 3 1 Cuatro vendedores (A. súmeselo a todos los elementos que se encuentran en una intersección de dos líneas. Haga la resta del menor costo por fila. Paso 3. El proceso concluye cuando el menor número de líneas que trazó.62 UNIDAD III Transporte y asignación Aunque este tipo de problemas podría resolverse con el método de transporte. el problema queda resuelto y se procede a la asignación. Con la tabla así formada. luego. restándole el menor elemento. Pasos para aplicar el método húngaro A continuación presentamos los pasos para aplicar este método: Paso 1. Destinos 1 Vendedores 2 3 4 A 16 7 10 9 B 4 14 8 7 C 9 10 5 11 D 4 6 8 12 Nota: Los valores menores de cada fila aparecen en gris. 03 Munoz UNIDAD 3.indd 62 02/03/11 01:57 PM . desarrolle otra tabla para reducir cada fila restándole el menor valor de ésta. De la tabla que encontró en el paso anterior. Con base en la tabla original de costos. 4). Los demás elementos quedan igual. D). al que se conoce como método húngaro. elimine todos los ceros cruzándolos con el menor número de líneas horizontales o verticales. Si el menor número de líneas que trazó es igual a m. De la tabla que desarrolló en el paso 2. que debe hacerse empleando sólo celdas en cero. 3. reduzca ahora cada columna. indd 63 2 3 4 A 9 0 3 0 B 0 10 4 1 C 4 5 0 4 D 0 2 4 6 02/03/11 01:57 PM . Destinos 1 Vendedores 2 3 4 A 9 0 3 2 B 0 10 4 3 C 4 5 0 6 D 0 2 4 8 Nota: Como el costo menor en cada columna es 0. sería la 4: Destinos 1 Vendedores 03 Munoz UNIDAD 3.3 Destinos 1 Vendedores 2 3 Modelo de asignación 63 4 A 16 – 7 = 9 7–7=0 10 – 7 = 3 9–7=2 B 4–4=0 14 – 4 = 10 8–4=4 7–4=3 C 9–5=4 10 – 5 = 5 5–5=0 11 – 5 = 6 D 4–4=0 6–4=2 8–4=4 12 – 4 = 8 El resultado es el siguiente: Destinos 1 Vendedores 2 3 4 A 9 0 3 2 B 0 10 4 3 C 4 5 0 6 D 0 2 4 8 Paso 2. en este caso. sólo se procederá a restar donde no tenga cero dicha columna. Reste el menor costo por columna.3. se suma dicho número en donde hay intersección y a los números que no fueron cubiertos por las líneas se les restará el costo menor. Elimine todos los ceros de la tabla que desarrolló cruzándolos con el menor número de líneas horizontales o verticales. como el número de filas es igual a m (4). Destinos 1 Vendedores 2 3 4 A 9 0 3 0 B 0 10 4 1 C 4 5 0 4 D 0 2 4 6 Como el número de líneas no es igual a m (4 vendedores).64 UNIDAD III Transporte y asignación Paso 3. debe hacerse la asignación: Destinos 1 Vendedores 03 Munoz UNIDAD 3. Destinos 1 Vendedores 2 3 4 A 10 0 4 0 B 0 9 4 0 C 4 4 0 3 D 0 1 4 5 En este caso. El resultado es el siguiente. luego de lo cual el cuadro queda como sigue: Destinos 1 Vendedores 2 3 4 A 9 + 1 = 10 0 3+1=4 0 B 0 10 – 1 = 9 4 1–1=0 C 4 5–1=4 0 4–1=3 D 0 2–1=1 4 6–1=5 Nota: En este caso. debe restarse el menor costo no cubierto por una línea y luego sumarlo a las intersecciones de las líneas. el costo menor no cubierto por ninguna línea es el número 1 ubicado en B. Cabe recordar que debe procederse a trazar las líneas en donde hay ceros.4.indd 64 2 3 4 A 10 0 4 0 B 0 9 4 0 C 4 4 0 3 D 0 1 4 5 02/03/11 01:57 PM . como se mencionó. otra en Coahuila y otra en San Luis Potosí. El diagrama de la distancia que existe entre las plantas y los centros de distribución es el siguiente: Ciudad de México a) b) c) d) Monterrey Toluca 75 km 875 km Coahuila 993 km 348 km San Luis Potosí 407 km 501. Una empresa que fabrica automóviles cuenta con 3 plantas de producción. W X A 10 1 B 12 C Demanda 03 Munoz UNIDAD 3.indd 65 Y Z Oferta 9 11 600 14 20 20 100 2 7 16 18 140 120 80 100 540 02/03/11 01:57 PM . el C al 3 con un costo de 5 y el vendedor D va al destino 1 con un costo de 4. El envío de automóviles se realiza por vía férrea con un costo aproximado de 8 centavos por cada 2 000 km. 4 500 y 3 200 automóviles. 2. Destinos 1 Vendedores 2 3 4 A 16 7 10 9 B 4 14 8 7 C 9 10 5 11 D 4 6 8 12 Luego de sumar los costos de cada vendedor en relación con cada uno de los destinos se obtiene: 7 + 7 + 5 + 4 = 23 1. una en Toluca. respectivamente.2 km Elabore la tabla de costos Formule el modelo de acuerdo a la estructura general de la programación lineal.Actividades de la unidad III 65 La asignación quedaría así: el vendedor A se dirige al destino 2 con un costo de 7 (que es el valor inicial de la primera tabla). Sus centros de distribución principales están ubicados en las ciudades de México y Monterrey. Las capacidades de las tres plantas durante el trimestre próximo son de 5 000. Explique cuál de los dos métodos es mejor. Encuentre la solución inicial mediante cualquiera de los métodos que se expusieron en el capítulo (esquina noroeste. costo menor y Vogel) y utilice el método de cruce del arroyo para encontrar la solución óptima del siguiente problema. el B al punto de arribo 4 con un costo de 7. Las demandas trimestrales en los dos centros de distribución son de 7 300 y 5 400 vehículos. Encuentre la solución mediante los métodos de costo menor y de Vogel. 66 UNIDAD III Transporte y asignación 3.indd 66 Máquina A B C 1 5 7 9 2 14 10 12 3 15 13 16 02/03/11 01:57 PM . 03 Munoz UNIDAD 3. Utilizando el método húngaro encuentre la asignación óptima asociada de cada uno de los trabajos a cada una de las máquinas y calcule el costo final. resolver problemas mediante el algoritmo de flujo máximo. 4) 4 2 Nodo Figura 4.Unidad IV Modelos de optimización de redes Al finalizar el estudio de esta unidad. 5 A = (1. se espera que el lector sea capaz de: explicar qué entiende por red.1 Arco o rama Representación de una red.indd 67 02/03/11 01:58 PM . resolver problemas mediante los métodos PERT y CPM 4. nodo. resolver problemas mediante el algoritmo de Dijkstra. A) en donde N es el conjunto de nodos y A es el conjunto de arcos. explicar qué es una ruta. 5) (2.1). 3) (1.1 Modelos de redes Una red consta de un conjunto de nodos unidos por arcos o ramas (véase figura 4. 4) (4. árbol. resolver problemas mediante el algoritmo de Floyd. La notación para describir una red es (N. 5) (3. 3. 5 3 1 N = 1. 2. 3) (2. arco. lazo. 4. 67 04 Munoz UNIDAD 4. 2) (3. Árboles Por su parte. Red conectada que puede contener sólo un subconjunto de todos los nodos de la red. Es aquella en la cual dos nodos se encuentran unidos. Red conectada Una red conectada es aquella en la cual dos nodos se encuentran unidos.3): Figura 1 1 2 2 4 3 Árbol Figura 4.3 04 Munoz UNIDAD 4. Se dice que un arco está dirigido u orientado si permite un flujo positivo en una dirección y un flujo 0 en la dirección opuesta. 3) sí existe. Círculo en el que todas las ramas se orientan en la misma dirección. El que une todos los nodos sin permitir ningún lazo. 3) (3. 2) forman un ciclo. Un lazo dirigido o circuito es un círculo en el cual todas las ramas están orientadas en la misma dirección. un árbol es una red conectada que puede incluir sólo un subconjunto de todos los nodos de la red. mientras que un árbol de expansión une todos los nodos sin permitir ningún lazo entre ellos.1.2 5 3 1 Lazo o ciclo. En la figura anterior (2. Árbol de expansión. Si se observa la figura 4. 4 2 Figura 4. por lo menos. 4) (4. una red dirigida tiene todas las ramas orientadas. se obtiene lo siguiente (véase figura 4.2. En general. Una ruta forma un lazo o ciclo si conecta un nodo consigo mismo. por lo menos. el flujo de una red está limitado por la capacidad de sus arcos.indd 68 6 3 5 Árbol de expansión Representación de un árbol y de un árbol de expansión. Ruta.68 UNIDAD IV Modelos de optimización de redes ¿Por qué el arco (3. 1) no está en el conjunto A? Porque se repetiría el arco puesto que el (1. Árbol. Lazo dirigido Lazo dirigido (circuito). los cuales pueden ser finitos e infinitos. como muestra la figura 4. por una ruta. por una ruta. Ruta Una ruta es una secuencia de ramas distintas que unen a dos nodos sin que importe la dirección del flujo de cada rama. Secuencia de ramas diferentes que enlazan dos nodos sin que importe la dirección del flujo de cada rama. Red conectada. 02/03/11 01:58 PM . 5) (4. A y determine una ruta. 2 1. 1 1. determine el conjunto de N.1 Modelos de redes 69 En el caso de la siguiente figura. las actividades que se desarrollan en ella se simbolizan mediante círculos (nodos). 3. 3.4. 3. 1) 3 4 Ciclos: 1. 2. Representación gráfica de un proyecto. 1 Rutas: 1. 2 N = 1. mientras que las relaciones de secuencia entre actividades con segmentos dirigidos (aristas). 3. 2) (1. Una ruta es una secuencia entre actividades en una red. 3) (3. 4. 04 Munoz UNIDAD 4. 2. 3. 5 1. un árbol de expansión. 5. Secuencia entre actividades que se desarrollan en una red. 3. 1 1. 2. Ruta. 5. 2. Ruta Red. 5 3 3 4 5 2 5 Incluye todos los nodos de la red evitando ciclos Red Una red es la representación gráfica de un proyecto. 5 1 5 A = (1. 5) (2. 5.indd 69 02/03/11 01:58 PM . 4. 5) (5. 5 1. 4) (3. 5. 5 2 1 5 1 5 1 3 3 Ejemplo: Representación de una ruta 5 4 Ejemplo: Representación de uno de los ciclos 1 1 Árbol: 1. un árbol y un lazo o circuito. 4. por medio de un procedimiento especial de clasificación. Este algoritmo representa una red de N nodos como una matriz cuadrada con N renglones y N columnas. Paso 2. Algoritmo de Dijkstra Los cálculos del algoritmo de Dijkstra avanzan de un nodo i a un nodo siguiente j. 3 dij = 30 15 2 100 Ruta: 1. entonces se reemplaza con el nuevo. Paso 3. el algoritmo de Floyd es más general porque permite determinar la ruta más corta entre cualquier par de nodos de la red. Si todos tienen clasificaciones permanentes. 1 Permanente = 15 Permanente = 10 i=1 j = 2. deténgase. Calcule las clasificaciones temporales de cada nodo j al que puede llegarse desde el nodo i. siempre y cuando j no esté clasificado como permanente. En una red de transporte. La entrada (i. dicho modelo también puede utilizarse para modelar diferentes situaciones.indd 70 02/03/11 01:58 PM . De lo contrario. Clasifique el nodo del punto de origen (nodo 1) en la clasificación permanente. Por otra parte. existen dos algoritmos que se utilizan para resolver las redes críticas y las acríticas: • Dijkstra • Floyd El algoritmo de Dijkstra es útil para determinar la ruta más corta entre el nodo del punto de origen y cada uno de los otros nodos de la red. Si se llega al punto en el cual es evidente que no existe una ruta mejor. Si el nodo j es temporal y el nuevo valor es menor que el que tenía. el estado temporal cambia a permanente. Pasos para resolver el algoritmo de Dijkstra Paso 1. j) de la matriz de la distancia 04 Munoz UNIDAD 4. seleccione la clasificación con la distancia más corta de entre todas las temporales.70 UNIDAD IV Modelos de optimización de redes 4. 2 Costo: 55 1 i j 20 4 10 30 3 j 50 60 j 5 j Permanente = 30 Algoritmo de Floyd El algoritmo de Floyd es más general que el de Dijkstra ya que determina la ruta más corta entre cualesquiera dos nodos de la red. La clasificación de nodos de acuerdo con el algoritmo de Dijkstra se representa en dos formas: • Temporales • Permanentes Una clasificación temporal puede ser remplazada por otra si se puede encontrar una ruta más corta al mismo nodo. 3.2 Algoritmo de la ruta más corta El problema de la ruta más corta determina la distancia menor entre un punto de origen y un punto de destino. Por ejemplo. 04 Munoz UNIDAD 4. Métodos basados en redes que ayudan a planificar. Se disminuye en c* la capacidad residual de cada arco en esta trayectoria de aumento. Ocurre cuando los arcos que hay en una red residual del origen al destino no tienen capacidad residual positiva. Se da cuando en la red residual hay una trayectoria del origen al destino en la que cada arco sobre ella tiene una capacidad residual positiva. 4. (Si no existe ninguna. se dispone de un algoritmo de trayectorias aumentadas mucho más eficiente que se basa en dos conceptos intuitivos: el de red residual y el de trayectoria aumentada. Cada arco tiene una capacidad máxima de flujo admisible. Se aumenta en c* el flujo de esta trayectoria. Investigación de operaciones. En la fuente. Sin embargo. definimos las actividades del proyecto. 4. programar y controlar proyectos. sus 1 CPM y PERT. 4. Algoritmo de la trayectoria de aumento en el caso del problema de flujo máximo Se identifica una trayectoria de aumento si en la red residual se encuentra alguna trayectoria dirigida del origen al destino. que es finito. El problema de flujo máximo puede formularse como uno de programación lineal. Proyecto. • El objetivo es maximizar la cantidad total de flujo de la fuente al destino.4 CPM y PERT 71 dij del nodo i al nodo j. los flujos netos asignados constituyen un patrón del flujo óptimo). resolverse con el método símplex y por medio de cualquier software.indd 71 02/03/11 01:58 PM . En el destino. • Se permite el flujo a través de un arco sólo en la dirección que indica la flecha.1 Características del modelo de flujo máximo A continuación presentamos las características del modelo de flujo máximo: • Todo flujo a través de una red conexa dirigida se origina en un nodo llamado fuente y termina en otro denominado destino. Se regresa al paso 1. Un proyecto se define como un conjunto de actividades interrelacionadas en la cual cada una requiere tiempo y recursos. Nodo en el cual todos los Tal cantidad se mide en cualquiera de dos maneras equivalentes: la cantidad arcos señalan hacia el nodo. Se identifica la capacidad residual c* de esta trayectoria de aumento mediante la determinación del mínimo de las capacidades residuales de los arcos sobre esta trayectoria. apuntan hacia el exterior. El objetivo es obtener la máxima capacidad de flujo entre la fuente y el destino. Destino. Por su parte.3.4 CPM y PERT El CPM (Critical Path Method) o método de la ruta crítica y el PERT (Program Evaluation and Review Technique) también conocido como técnica de evaluación y revisión de programas. Hillier y Lieberman. p. es infinito. todos los arcos apuntan hacia el exterior. Nodo en el que todos los arcos el nodo. tal que cada arco sobre ella tenga capacidad residual estrictamente positiva. son métodos que se basan en redes diseñadas para ayudar en la planificación. de lo contrario. Los nodos restantes son nodos de trasbordo.1 Trayectoria de aumento. programación y control de proyectos. Primero. El objetivo del CPM y del PERT es proporcionar medios analíticos para programar las actividades. que sale de la fuente o la que entra al destino.4. todos señalan hacia Fuente.3 Modelo de flujo máximo En este caso se trata de enlazar un nodo fuente y un nodo destino a través de una red de arcos dirigidos. Conjunto de actividades interrelacionadas en la que cada una implica tiempo y recursos. i está elaborado directamente con j. donde la cantidad máxima de flujo está dada por la capacidad del arco. Se aumenta en c* la capacidad residual de cada arco en la dirección opuesta en esta trayectoria. 423. Patrón del flujo óptimo. Los nodos de la red establecen las relaciones de procedencia entre las diferentes actividades del proyecto. Existen tres reglas para construir una red. Las técnicas CPM y PERT difieren en que la primera supone duraciones deterministas de la actividad. Por definición. se deben responder las siguientes preguntas a medida de que se añade cada actividad en la red.4 Proceso para elaborar un proyecto. Al insertar una actividad simulada en una de las tres reglas anteriores. mantenemos la concurrencia de A y B. proporcionamos los nodos finales únicos para las dos actividades concurrentes.4). Cada actividad debe identificarse por medio de dos nodos finales distintos. la segunda supone duraciones probabilísticas. Por último.indd 72 02/03/11 01:58 PM . Representación de las redes PERT y CPM Cada actividad del proyecto se representa por medio de un arco direccional (flecha que apunta en dirección del proyecto). Cada actividad se representa con una y sólo una flecha en la red. es decir. Para mantener las relaciones de precedencia correctas.5 B 2 A 3 2 B 1 3 B Representación de varias actividades concurrentes. en cambio. ¿Cuál actividad debe preceder inmediatamente a la actual? ¿Cuál actividad debe seguir a la actual? ¿Cuáles actividades deben ocurrir de forma concurrente a la actual? 04 Munoz UNIDAD 4. 1 1 A A 3 2 Figura 4. 3. La figura 4.72 UNIDAD IV Modelos de optimización de redes relaciones de procedencia y sus requerimientos de tiempo.5 muestra cómo debe utilizarse una actividad simulada para representar dos actividades concurrentes (A y B). la cual no consume tiempo ni recursos. a saber: 1. una actividad simulada normalmente se representa por medio de una flecha de líneas punteadas. 2. Actividades de proceso Cálculos de la red Programas de tiempos tiempo Figura 4. el proyecto se traduce a una red que muestra las relaciones de procedencia entre las actividades. se hacen cálculos específicos de red que faciliten el desarrollo del programa de tiempo del proyecto (figura 4. después. 4. B 2 F Composición tipográfica del libro E 4 G El autor verifica la composición de las páginas F 2 H El autor verifica las ilustraciones D 1 I Producción de las placas para la impresión G.6). las cuales. primero debe asignarse el punto de origen (nodo 1). principia al concluir con la actividadd D. La actividad C puede comenzar inmediatamente después de que se hayan completado las actividades A y B. se inicia cuando acaban las tareas G y H. H 2 J Producción y encuadernación del libro C. La actividad D puede empezar inmediatamente después de haberse completado sólo la actividad B (véase figura 4. supongamos que debe satisfacerse la siguiente precedencia.6 A C B D Representación de una red. serían A. a su vez. se inicia cuando termina la actividad E. 02/03/11 01:58 PM .4 CPM y PERT 73 Las respuestas a estas preguntas pueden requerir el empleo de actividades simuladas para asegurar la presencia empleada entre las actividades. empieza al finalizar las actividades C e I. Actividades Predecesoras Duración en semanas A El editor corrige el manuscrito – 3 B El tipógrafo prepara las páginas de muestra – 2 C Diseño de la portada – 4 D Preparación de las ilustraciones – 3 E El autor aprueba el texto editado A. Al finalizar estas actividades. deben tomarse las actividades que no tengan ninguna actividad precedente. Desarrolle la red que represente el proyecto. Las flechas indican la trayectoria de las actividades. 1 Un editor tiene un contrato con un autor para publicar un libro de texto. D. I 4 Para poder elaborar la red. en este caso. comienzan a ubicarse las siguientes como: E F G H I J 04 Munoz UNIDAD 4. Las actividades simplificadas que se asocian con la producción del libro de texto se desarrollan y proporcionan a continuación. comienza al cumplir con la tarea F. B. Después. Por ejemplo. Figura 4. C.indd 73 empieza al finalizar las actividades A y B. se representan con círculos. Para efectuar los cálculos. en términos de la concluyen determinadas actividades y red. 3. de modo que el tiempo de iniciarla puede adelantarse o retrasarse dentro de ciertos límites sin que ello afecte la fecha de terminación del proyecto. • Categorización de las actividades del proyecto como críticas y no críticas. Cada actividad crítica debe iniciarse y terminarse a tiempo. se concluye la trayectoria de la red de dicho proyecto (véase figura 4. Actividad crítica.indd 74 2 2 02/03/11 01:58 PM .74 UNIDAD IV Modelos de optimización de redes Con ello. Punto en el tiempo en el que se en el cual se terminan ciertas actividades y se inician otras. Cálculo de la ruta crítica (CPM) Para lograr el resultado final con la construcción del programa de tiempo del proyecto de una manera conveniente. mientras que el paso hacia atrás calcula las últimas fechas de ocurrencia. hacemos cálculos especiales que nos proporcionan la siguiente información: • Duración total necesaria para completar el proyecto.7). Los cálculos de la ruta crítica implican dos pasos: el paso hacia adelante y el paso hacia atrás. se empiezan otras. 3 2 5 3 5 7 1 6 3 6 7 3 2 2 4 Respuesta: Ruta: 1. 2 Calcule la ruta crítica dada la siguiente red. definimos un evento como un punto en el tiempo Evento. 4. Se dice que cualquier actividad es crítica cuando no hay libertad para determinar los tiempos de inicio y terminación como tales para completar el proyecto sin demora. el evento corresponde a un nodo. 7 = 19 04 Munoz UNIDAD 4. 6.7 7 Representación de la red del problema 3. Una actividad no crítica permite cierta holgura en la programación. El que se dirige hacia adelante determina los primeros tiempos de ocurrencia de los eventos. 5. E 2 F 4 5 A 3 B 1 9 J C G 8 D I H 6 Figura 4. Ocurre cuando no hay libertad para determinar los tiempos de inicio y terminación en un proyecto. Determine la ruta más corta entre los nodos 1 y 5: 9 800 7 100 5 000 1 4 000 2 4 300 4 800 3 4 900 4 5 6 200 8 700 3. La figura siguiente representa los enlaces posibles de televisión entre las cinco áreas.Actividades de la unidad IV 75 1. La extensión de los cables se muestra en cada uno de los arcos. que comienza el 1 de enero de 2006 y termina el 31 de diciembre de 2010. Al iniciar cada año se decide si un auto se debe mantener en operación o se debe sustituir. Una compañía de televisión por cable está en proceso de proporcionar servicio a cinco nuevas áreas habitacionales. El problema se formula como una red. Una compañía que renta automóviles desea desarrollar un plan de reposición de su flotilla para un horizonte de planeación de 4 años. Considere la siguiente figura. 6 8 10 4 12 2 14 1 15 3 13 11 5 7 04 Munoz UNIDAD 4. La figura siguiente muestra el costo de reposición en función del año de compra del vehículo y los años que tiene en funcionamiento. encuentre la ruta más corta del nodo 1 al 15. Luego. Cada vehículo debe estar en servicio durante 1 año como mínimo y 3 años como máximo.indd 75 9 02/03/11 01:58 PM . en la cual se representan por los nodos del 1 al 5 los años de 2006 a 2010. Determine la red de cable más económica en las conexiones de cable de la compañía: 3 2 1 5 6 4 6 9 1 5 10 3 5 7 6 8 3 4 2. indd 76 02/03/11 01:58 PM . E 10 8 7 2 B A 1 5 1 10 D F 3 4 7 4 3 C G 5. Los números sobre las ramas representan los costos de incluir estas ramas en la red final. B 3 5 2 E 1 4 2 1 A 7 C G 1 6 5 F 10 3 D 04 Munoz UNIDAD 4. En la figura siguiente. Resuelva el problema de recorrido mínimo en la red que se muestra en la figura siguiente.76 UNIDAD IV Modelos de optimización de redes 4. identifique una ruta del origen A al destino G que permita un flujo positivo. Egresos (miles p) Proyecto 1 2 3 Fondos disponibles 1 25 18 16 120 2 27 22 27 140 3 28 21 21 120 4 30 28 34 150 5 28 31 24 110 Utilidad 215 320 270 x1 = proyecto 1 x2 = proyecto 2 x3 = proyecto 3 Objetivo: maximizar Max Z = 215x1 + 320x2 + 270x3 S. A continuación se muestra una tabla de estimación de las utilidades que proporcionará cada proyecto y los egresos que se relacionan con cada uno de ellos y que se consideran anuales. se nos proporcionan las utilidades esperadas de cada producto. 25x1 + 18x2 + 16x3 ≥ 120 27x1 + 22x2 + 27x3 ≥ 140 28x1 + 21x2 + 21x3 ≥ 120 30x1 + 28x2 + 34x3 ≥ 150 28x1 + 31x2 + 24x3 ≥ 110 xi ≥ 0 Problema 2 La compañía Higiene y Limpieza Institucional (HLI) desea evaluar y proyectar las utilidades de cada uno de sus productos Fabuloso. así como su proceso de elaboración durante 5 años. además. elaboró una planificación de 5 años para acrecentar su rentabilidad.Ejercicios Problema 1 Afianzadora Insurgentes evalúa 3 proyectos de crecimiento.A. Plantee el modelo de programación lineal entero. Plantee el modelo de programación lineal.indd 77 02/03/11 01:59 PM . Tipo de Fabuloso Año 1 Año 2 Año 3 Año 4 Año 5 Utilidades Mar fresco 1 2 3 1 1 10 000 Lavanda 1 1 4 1 1 9 500 Frutas 1 1 1 1 1 7 000 Canela 2 5 3 2 1 14 000 11 500 Naranja 2 2 2 2 2 Fondos disponibles 20 28 26 30 37 77 05 Munoz EJERCICIOS. mes Alcance del medio 1 TV 35 000 22 000 16 000 3 425 000 2 Radio 16 000 10 000 5 000 275 000 3 TV por cable 18 000 14 000 9 000 49 000 4 Periódico 15 000 9 000 7 000 781 550 Total costos ⫻ mes presupuestados 84 000 55 000 37 000 Sea: x1 = medio 1 x2 = medio 2 x3 = medio 3 x4 = medio 4 Max Z = 3 425 000x1 + 275 000x2 + 49 000x3 + 781 550x4 S. mes 3er.78 Ejercicios Sea: x1 = Fabuloso mar fresco x2 = Fabuloso lavanda x3 = Fabuloso frutas x4 = Fabuloso canela x5 = Fabuloso naranja Objetivo: maximizar Max Z = 10 000x1 + 9 500x2 + 7 000x3 + 14 000x4 + 11 500x5 1x1 + 1x2 + 1x3 + 2x4 + 2x5 ≤ 20 2x1 + 1x2 + 1x3 + 5x4 + 2x5 ≤ 28 3x1 + 4x2 + 1x3 + 3x4 + 2x5 ≤ 26 1x1 + 1x2 + 1x3 + 2x4 + 2x5 ≤ 30 1x1 + 1x2 + 1x3 + 1x4 + 2x5 ≤ 37 xi ≥ 0 Problema 3 Se analizan cuatro medios electrónicos de comunicación para lanzar la nueva campaña publicitaria de Desechables Jaguar. La siguiente tabla proporciona los alcances totales y los costos mensuales presupuestados de cada medio.indd 78 02/03/11 01:59 PM . La campaña tendrá una duración de 3 meses. Número Medio de comunicación Costos 1er.A. Elabore el modelo de programación lineal entero. mes 2do. 35 000x1 + 16 000x2 + 18 000x3 + 15 000x4 ≤ 84 000 22 000x1 + 10 000x2 + 14 000x3 + 9 000x4 ≤ 55 000 16 000x1 + 5 000x2 + 9 000x3 + 7 000x4 ≤ 37 000 xi ≥ 0 05 Munoz EJERCICIOS. Los datos se muestran en la siguiente tabla: Requerimiento de capital (meses)(en pesos) Mezcla de promoción Valor actual ⫻ 3 meses (en pesos) 3 6 9 12 TV y prensa 8 000 16 000 15 000 18 000 25 000 Radio y prensa 6 000 7 000 12 000 10 000 4 000 Radio y TV 10 000 10 000 13 000 18 000 25 000 30 000 40 000 35 000 50 000 Fondo disponible Sea: x1 = TV y prensa x2 = Radio y prensa x3 = Radio y TV Min Z = 8 000x1 + 6 000x2 + 10 000x3 Sujeto a: 16 000x1 + 7 000x2 + 10 000x3 ≤ 30 000 15 000x1 + 12 000x2 + 13 000x3 ≤ 40 000 18 000x1 + 10 000x2 + 18 000x3 ≤ 35 000 25 000x1 + 4 000x2 + 25 000x3 ≤ 50 000 xi ≥ 0 Problema 5 La empresa Sueño desea importar colchones de Tailandia. Agencia aduanal 05 Munoz EJERCICIOS. por lo cual debe elegir la opción que más se adapte a sus necesidades. los cuales se llevarán a cabo en los siguientes 12 meses y.indd 79 Tiempo de entrega Costo total (en pesos) Ganancia Tipo 1 4 días 24 000 10 000 Tipo 2 5 días 20 000 13 000 Tipo 3 5 días 19 500 12 000 02/03/11 01:59 PM . para lo cual debe evaluar las posibles agencias aduanales a las que acudirá para ello. La tabla ilustra las características de cada agencia aduanal. sin olvidar el costo y la utilidad. para ello.Ejercicios 79 Problema 4 Una compañía aérea debe evaluar tres proyectos promocionales. así que uno de los factores más importantes para elegir agencia es el tiempo en que llega el pedido al almacén de la tienda. cuenta con un capital limitado para cada mes. La empresa está comprometida a entregar sus pedidos en no más de una semana y no puede gastar más de 25 000 pesos por pedido. A la compañía le interesa cumplir con los pedidos que tiene. 5x2 + 2.00 AT&T 400 300 1. 4x1 + 5x2 + 5x3 ≥ 7 días 24 000x1 + 20 000x2 + 19 500x3 ≤ 25 000 x1 ≥ 0 Problema 6 La empresa de telemarketing Atel trata de reducir sus costos.A. pero. debe hacer un promedio de 400 llamadas al mes por empleado. pero sus costos extras no deben exceder de 2 000 pesos.A. aunque sin poner en riesgo la buena promoción de los productos. tiene que ofrecerles planes muy atractivos. que cobra 360 pesos por mes. la estrategia es escoger la compañía telefónica que le ofrezca más llamadas a un costo reducido. 350x1 + 300x2 + 300x3 ≥ 400 2x1 + 1.20 ¿Cómo debe repartir las llamadas la empresa para minimizar los costos? Sea: x1= contratar línea telefónica con Telmex x2= contratar línea telefónica con AT&T x3= contratar línea telefónica con Avantel Min Z = 350x1 + 400x2 + 280x3 S. cuya tarifa fija es de 280 pesos mensuales. Son tres las compañías telefónicas: Telmex. Ello significa un precio considerable para la promoción o ventas de los productos de sus clientes.indd 80 02/03/11 01:59 PM . y Avantel. Para que la empresa cumpla con sus clientes. La compañía debe cumplir con sus clientes. debido a que la competencia ha aumentado. En la siguiente tabla se presentan los beneficios que se obtienen con cada una de las compañías telefónicas. de llamadas al mes Costo por llamada extra Telmex 350 350 2. Compañía Renta mensual Núm. AT&T.2x3 ≤ 2 000 x1 ≥ 0 05 Munoz EJERCICIOS. 450 pesos fijos al mes.80 Ejercicios ¿Qué agencia aduanal debe elegir la empresa de acuerdo con la ganancia obtenida? Sea: x1 = contratar agencia aduanal tipo 1 x2 = contratar agencia aduanal tipo 2 x3 = contratar agencia aduanal tipo 3 Max Z = 10 000x1 + 13 000x2 + 12 000x3 S.50 Avantel 280 300 2. Modelos abstractos. Método del costo menor. en principio. Patrón del flujo óptimo. C Cola. Asigna el costo más bajo a cada unidad y después se ajusta la cantidad de la oferta y la demanda.indd 81 02/03/11 01:59 PM . Se emplea para solucionar problemas de programación lineal mediante la representación geométrica de restricciones. Se concentra en las rutas económicas. Logro de mayores beneficios con una mínima inversión de recursos. Modelos dinámicos. Modelo matemático. Nodo en el que todos los arcos apuntan hacia el exterior. F Fuente. Métodos basados en redes que ayudan a planificar. Modelos aleatorios. Describen un fenómeno que se comporta regularmente en intervalos diferentes. Programación lineal. en estas últimas. CPM y PERT. Clase especial de programación por medio del cual se minimizan los costos del transporte de personas o productos desde los puntos de origen hasta los puntos de destino. Modelos determinísticos. por una ruta. Conjunto de modelos matemáticos que describen sistemas de 81 06 Munoz GLOSARIO-BIBLIO. Modelo normativo. Paradigma que señala el curso de acción que debe seguirse para lograr un objetivo. I Investigación. Ruta. El que une todos los nodos sin permitir ningún lazo. Representación de la realidad mediante una relación funcional. Ocurre cuando no hay libertad para determinar los tiempos de inicio y terminación en un proyecto. Investigación de operaciones (IO). Representación simplificada o idealizada de una parte de la realidad. Actividad que tiene por fin ampliar el conocimiento científico sin perseguir. por lo tanto. Representación de un fenómeno que se comporta regularmente a intervalos iguales y. Optimizar. ninguna aplicación práctica. no es posible apoyarse. Modelo de transporte. Modelo de asignación. Modelo descriptivo. Primer procedimiento matemático ampliamente aceptado en la investigación de operaciones. Red conectada. Método símplex de programación lineal. Modelo en el que cada fuente y cada destino poseen una demanda unitaria. Disciplina que divide un problema concreto en pequeñas partes a las que analiza para obtener un problema abstracto o un modelo y así ofrecer acciones o alternativas de solución. Nodo en el cual todos los arcos señalan hacia el nodo. Red conectada que puede contener sólo un subconjunto de todos los nodos de la red.A Actividad crítica. Representan la realidad en una determinada unidad de tiempo. Árbol de expansión. un conjunto de restricciones y una restricción de no negatividad para determinar la asignación óptima de recursos escasos. Valores que especifican la relación entre las variables de decisión. Secuencia de ramas diferentes que enlazan dos nodos sin que importe la dirección del flujo de cada rama. condiciones técnicas y objetivos. Conjunto de reglas que permiten. O Operación. llamadas datos. a partir de una o varias cantidades o expresiones. Paradigma que no sólo describe la realidad sino que señala las situaciones futuras. Círculo en el que todas las ramas se orientan en la misma dirección. Procedimiento matemático con una o más funciones objetivo. Secuencia entre actividades que se desarrollan en una red T Teoría de colas. M Método de cruce de arroyo. Representación gráfica de un proyecto. Método gráfico. Proyecto. por consiguiente. no todos son complejos. Es aquella en la cual dos nodos se encuentran unidos. basado en la iteración para ir mejorando la solución a cada paso. Se construyen mediante símbolos matemáticos que representan diferentes comportamientos del problema. por lo menos. Modelo predictivo. Paradigmas que representan la realidad a escala y se construyen con base en problemas concretos. Herramientas de investigación que utilizan expresiones simbólicas para representar el comportamiento de un sistema. Ocurre cuando los arcos que hay en una red residual del origen al destino no tienen capacidad residual positiva. E Evento. P Parámetros. Conjunto de actividades interrelacionadas en la que cada una implica tiempo y recursos. Punto en el tiempo en el que se concluyen determinadas actividades y empiezan otras. Árbol. Modelo. D Destino. es factible predecir su compor- tamiento con un cierto margen de error aceptable o tolerable. Modelos estáticos. L Lazo dirigido (circuito). Método a través del cual debe encontrarse un procedi- miento de reasignación en el que sólo se pisen las celdas de piedra y ninguna de agua pues. Modelos físicos. Línea de espera. Interpretan la evolución de una parte de la realidad en un tiempo determinado. programar y controlar proyectos. obtener otras cantidades o expresiones denominadas resultados. R Red. predecir su comportamiento es muy difícil. A. Investigación de operaciones una introducción. http:// home.htm TAHA HAMDY. Los modelos sirven para encontrar una relación óptima entre los costos del sistema y los tiempos promedio de la línea de espera de un sistema dado. séptima edición.investigacionoperaciones.indd 82 V Variables de decisión. 02/03/11 01:59 PM .com/Introduccion_IO. sexta edición. Cantidades que se desconocen y que deben determinarse en la solución de un problema cuyo modelo se plantea. 1998.htm#rop 06 Munoz GLOSARIO-BIBLIO. Introducción a la investigación de operaciones. 2002. HILLIER–LIEBERMAN. Investigación de operaciones. Trayectoria de aumento.82 Bibliografía líneas de espera particulares o de sistemas de colas. www. Se da cuando en la red residual hay una trayectoria del origen al destino en la que cada arco sobre ella tiene una capacidad residual positiva.. McGraw-Hill.ubalt. México. HOSSEIN ARSHAM. Modelos deterministas: optimización lineal.edu/ntsbarsh/opre640S/SpanishD. Prentice Hall. 68. 19. 81 a escala. 13 Problemas no lineales. 71. 13-16 Restricciones. 7. 81 Organigrama. 68. 1 Circuito. 14. 5. 70 06 Munoz GLOSARIO-BIBLIO. 4 Solución factible. 69. 54. 5. 38 Eficacia. 68. 62. 2 aleatorios. 67 de la ruta más cercana. 3. 81 Conjunto de restricciones. 4. 35. 2 Función exponencial. 3 Función objetivo. 9. 42. 4 Proyecto. 8 Espacio de soluciones factibles. 12. 17. Dantzig. 81 predictivo. 13. 32 E Ecuaciones de restricción. 81 de holgura. 81 Programación matemática. 53. 2. 24. 70 de Floyd. 78 descriptivo. 9-13. 13 húngaro. 13 Solución factible degenerada. 35. 71 de programación lineal (MPL). 4. 81 físicos. 44. 32 estáticos. 81 Arco. 81 de flujo máximo. 81 de la esquina noroeste. 9. 61. 9. 81 Función. 67-72 permanentes. 65. 74. 20. 68. 76 Rango. 71. 4 determinísticos. 42. 67. 7. 37. 3 normativos. 23. 52. 14. 74. 67. 70 No negatividad. 81 N Nodo. 71. 61 Investigación de operaciones (IO). 71. 29. 18 R Ramas. 81 de cruce de arroyo. 57. 81 dual. 44. 81 primales. 5. 65. 13 O Objetivo. 67. 59. 34. 13 de decisión. 68. 4 C Cálculo de la ruta crítica (CPM). 46. 71. 19. 4. 58. 38. 36. 20 Ruta. 53 de suma y resta. 66 PERT (Program Evaluation and Review Technique). 3 mentales. 5. 34 ventajas. 71 de piedra rodante. 69 Arsham Hossein. 69 Lazo dirigido. 13 gráfico en recursos. 71 Arista. 81 residual. 56. 67. 8 D Destino. 61. 35. 2. 81 lineal. 81 Trayectoria aumentada. 81 Punto óptimo. 28. 81 F Fuente. 67. 13 Número de restricciones. 65. 15. 38. 70 Árbol. 69. 27. 81 símplex. 32. 32. 4. 82 V Variables. 1. 4. 68 Ciencias de la administración. 9. 81 Iteración. 54. 19 I Índice de mejoramiento (IM). 19. 76. 65 de la ruta crítica. 46. 81 desventajas. 33 Optimizar. 81 conectada. 72. 71. 67. 34. 7-11. 46. 68. 21. 13. 67. 27. 70 de flujo máximo. 7. 35. 77. 4. 20 numéricas. 3. 65 Modelos. 71 Región factible. 36. 81 de asignación. 71 Teoría de colas. 4. 53 CPM (Critical Path Method). 11 Operación. 29. 35. 81 Vogel. 81 de asignación. 71. 20. 81 Cola. 5. 33 gráfico. 32. 81 de transporte. 72. 1-6. 8. 2 L M Método celda de piedra. 81 Dualidad. 2 normativo. 81 Pivote. 14 Problemas lineales. 81 de expansión. 7. 13 T Tabla símplex. 55. 30. 68. 67. 81 Patrón de flujo óptimo. 5. 9.indd 83 temporales. 71. 36 G George B. 13. 33. 61 de costo menor. 81 descriptivos. 68. 13. 20. 7. 13 Solución factible no degenerada. 74 Ciclo. 7. 19 matemáticos. 69. 69. 10. 81 Algoritmo de Dijkstra. 38. 32. 81 S Sistema. 7 Programación lineal. 7-13. 3 predictivos. 67-74. 31 Plano cartesiano. 4 Lazo. 67. 30. 36-38. 18 de transporte. 81 dinámicos. 33. 29. 38 Técnica de evaluación y revisión de programas. 2.Índice A Actividad crítica. 14. 13 Evento. 62 dual símplex. 13 Red. 3 P Parámetros. 1. 9 02/03/11 01:59 PM . 35. 4. 5. 81 Optimización. 35. 37. 68. 81 abstractos. 81 gráfico en actividad. indd 84 02/03/11 01:59 PM .06 Munoz GLOSARIO-BIBLIO.