C A P T U L O1 La referencia seleccionada 2 proporciona una entretenida historia de la investigacin de operaciones que rastrea susraces hasta 1564 y describe una cantidad considerable de contribuciones cientfi cas desde ese ao hasta 1935 que infl uyeronen el desarrollo subsiguiente de la IO.2 CAPTULO 1 INTRODUCCINposterior a la guerra sigui su curso, los problemas provocados por el aumento de la complejidady la especializacin de las organizaciones pasaron de nuevo al primer plano. Entonces comenz aser evidente para un gran nmero de personas, entre ellas los consultores industriales que habantrabajado con o para los equipos de IO durante la guerra, que estos problemas eran en esencia losmismos que los que deban enfrentar los militares pero en un contexto diferente. Al inicio de ladcada de los aos cincuenta, estos visionarios introdujeron el uso de la investigacin de operacionesen una serie de organizaciones industriales, de negocios y del gobierno. Desde entonces, seha desarrollado con rapidez.Es posible identifi car por lo menos otros dos factores que tuvieron gran importancia en eldesarrollo de la IO durante este periodo. Uno es el progreso sustancial que se logr en el mejoramientode las tcnicas disponibles. Despus de la guerra, muchos de los cientfi cos que habanparticipado en equipos de IO o que tenan informacin sobre este trabajo, estaban motivados pararealizar investigacin relevante en el campo, de lo cual resultaron avances importantes; un ejemplosobresaliente es el mtodo smplex para resolver problemas de programacin lineal, desarrollado en1947 por George Dantzig. Muchas de las herramientas caractersticas de la IO, como programacinlineal, programacin dinmica, teora de colas y teora de inventarios haban sido desarrolladas casipor completo antes del trmino de la dcada de los aos cincuenta.Un segundo factor que dio gran impulso al desarrollo de este campo fue la revolucin delas computadoras. El manejo efi caz de los complejos problemas inherentes a la IO casi siemprerequiere un gran nmero de clculos. Realizarlos de forma manual puede resultar casi imposible,por lo cual el desarrollo de la computadora electrnica digital, con su capacidad para hacer clculosaritmticos, miles o tal vez millones de veces ms rpido que los seres humanos, fue una gran ayudapara esta disciplina. Otro avance tuvo lugar en la dcada de los aos ochenta, con el desarrollo decomputadoras personales cada vez ms rpidas y de buenos paquetes de software para resolverproblemas de IO. De esta forma, las tcnicas ms complejas estuvieron al alcance de un grannmero de personas, y este progreso se aceler an ms en la dcada de 1990 y al inicio del sigloxxi. Hoy en da, millones de individuos tienen acceso a estos paquetes y en forma cotidiana se utilizatoda una gama de computadoras, desde las grandes hasta las porttiles, para resolver problemasde investigacin de operaciones, algunos de ellos muy complejos. 1.2 NATURALEZA DE LA INVESTIGACIN DE OPERACIONESComo su nombre lo indica, el objetivo de esta disciplina implica investigar sobre las operaciones.En consecuencia, esta disciplina se aplica a la problemtica relacionada con la conduccin y lacoordinacin de actividades en una organizacin. En esencia, la naturaleza de la organizacin esirrelevante, por lo cual la IO ha sido aplicada de manera extensa en reas tan diversas como manufactura,transporte, construccin, telecomunicaciones, planeacin fi nanciera, cuidado de la salud,fuerzas armadas y servicios pblicos, por nombrar slo unas cuantas. As, la gama de aplicacioneses inusualmente amplia.La IO incluye el trmino investigacin en el nombre porque utiliza un enfoque similar al que seaplica en las reas cientfi cas establecidas. El mtodo cientfi co se utiliza para explorar los diversosproblemas que deben ser enfrentados, pero en ocasiones se usa el trmino management science ociencia de la administracin como sinnimo de investigacin de operaciones. El proceso comienzapor la observacin cuidadosa y la formulacin del problema, lo cual incluye la recoleccin de losdatos pertinentes. El siguiente paso es la construccin de un modelo cientfi co generalmente matemticocon el cual se intenta abstraer la esencia del problema real. En esta etapa se propone lahiptesis de que el modelo ser una representacin tan precisa de las caractersticas esenciales de lasituacin, que permitir que las conclusiones soluciones que se obtengan sean vlidas tambinpara el problema real. Despus se llevan a cabo los experimentos adecuados para probar esta hiptesis,para modifi carla si es necesario y para verifi carla en determinado momento, paso que se conocecomo validacin del modelo. En cierto sentido, la IO involucra la investigacin cientfi ca creativade las propiedades fundamentales de las operaciones. Sin embargo, es ms que esto. La IO se ocupatambin de la administracin prctica de la organizacin. Por lo tanto, para tener xito, tambin debeproporcionar conclusiones claras que el tomador de decisiones pueda usar cuando sea necesario.Otra caracterstica de la investigacin de operaciones es su amplio punto de vista. Como quedimplcito en la seccin anterior, la IO adopta una visin organizacional. Desde esta perspectivaintenta resolver los confl ictos de intereses entre los componentes de la organizacin de forma queel resultado sea el mejor para sta en su conjunto. Ello no signifi ca que el estudio de cada problemadeba considerar en forma explcita todos los aspectos de la organizacin, sino que los objetivos quese persiguen deben ser congruentes con los objetivos globales.Una caracterstica adicional de la investigacin de operaciones es que intenta encontrar unamejor solucin llamada solucin ptima para el problema en cuestin. (Se dice una mejorsolucin y no la mejor solucin porque es posible que existan muchas soluciones que puedan considerarsecomo las mejores.) En lugar de conformarse con mejorar el estado de las cosas, la metaes identifi car el mejor curso de accin posible. Aun cuando debe interpretarse con todo cuidado entrminos de las necesidades reales de la administracin, esta bsqueda del mejor camino es unaspecto importante de la IO.Estas caractersticas conducen de manera casi natural a otra. Es evidente que no puede esperarseque un solo individuo sea experto en los mltiples aspectos del trabajo de investigacin deoperaciones o de los problemas que se estudian, sino que se requiere un grupo de individuos condiversos antecedentes y aptitudes. Cuando se decide emprender un estudio de IO completo de unproblema nuevo, es necesario emplear el enfoque de equipo. Este grupo de expertos debe incluirindividuos con antecedentes slidos en matemticas, estadstica y teora de probabilidades, al igualque en economa, administracin de empresas, ciencias de la computacin, ingeniera, cienciasfsicas, ciencias del comportamiento y, por supuesto, en las tcnicas especiales de IO. El equipotambin necesita experiencia y aptitudes necesarias para considerar de manera adecuada todas lasramifi caciones del problema dentro de la organizacin. 1.3 EFECTO DE LA INVESTIGACIN DE OPERACIONESLa investigacin de operaciones ha tenido un efecto impresionante en el mejoramiento de la efi -ciencia de numerosas organizaciones de todo el mundo. En el proceso, la IO ha contribuido demanera signifi cativa al incremento de la productividad de la economa de varios pases. Hoy existenms de 30 pases miembros de la International Federation of Operational Research Societies(IFORS), cada uno de los cuales cuenta con una sociedad de investigacin de operaciones. Tantoen Europa como en Asia existen federaciones de sociedades de IO que dan conferencias y publicanrevistas internacionales en esos continentes. Adems, el Institute for Operations Research andthe Management Sciences (INFORMS) es una sociedad de IO internacional. Entre sus mltiplesrevistas existe una, llamada Interfaces, que publica artculos que presentan estudios importantesde IO y el efecto que stos tuvieron en sus organizaciones.Para dar una mejor idea de la amplia aplicabilidad de la IO, en la tabla 1.1 se enumeran algunasaplicaciones reales. Observe la diversidad de organizaciones y aplicaciones incluidas enlas primeras dos columnas. En la tercera columna se identifi ca la seccin donde un recuadro deaplicacin contiene varios prrafos en los que se describe la aplicacin y tambin hace referenciaa un artculo que proporciona detalles completos. (En esta seccin se puede ver el primero de estosrecuadros de aplicacin.) La ltima columna indica que estas aplicaciones signifi caron ahorrosanuales de muchos millones de dlares. An ms, algunos benefi cios adicionales no registradosen la tabla como un mejor servicio al cliente y mayor control administrativo fueron consideradosms importantes, en ciertos casos, que los benefi cios fi nancieros. (El lector tendr oportunidadde investigar estos benefi cios menos tangibles en los problemas 1.3-1, 1.3-2 y 1.3-3.) En nuestrositio web www.mhhe.com/hillier se incluye un vnculo con los artculos que describen estasaplicaciones a detalle.Aunque la mayora de los estudios rutinarios de IO proporciona benefi cios mucho ms modestosque estas aplicaciones reconocidas, las cifras que aparecen en la columna de la derecha dela tabla 1.1 refl ejan el gran efecto que pueden tener los estudios grandes y bien diseados de estadisciplina. 1.4 ALGORITMOS Y PAQUETES DE IOUna parte primordial de este libro es la presentacin de los algoritmos procedimientos sistemticosde solucin ms importantes de la IO para resolver cierto tipo de problemas. Algunos de estos1.4 ALGORITMOS Y PAQUETES DE IO 34 CAPTULO 1 INTRODUCCIN TABLA 1.1 Aplicaciones de la investigacin de operaciones que se describirn en los recuadros de aplicacinOrganizacin rea de aplicacin Seccin Ahorros anualesFederal Express Planeacin logstica de envos 1.3 No estimadosContinental Airlines Reasignacin de tripulaciones a vuelos cuando ocurreninterrupciones en el itinerario2.2 $40 millonesSwift & Company Mejora del desempeo en ventas y manufactura 3.1 $12 millonesMemorial Sloan-KetteringCancer CenterDiseo de terapia de radiacin 3.4 $459 millonesUnited Airlines Plan para los programas de trabajo de los empleados enaeropuertos y ofi cinas de reservacin3.4 $6 millonesWelchs Optimizacin del uso y movimiento de materias primas 3.6 $150 000Samsung Electronics Reduccin de tiempos de manufactura y niveles deinventario4.3 Ganancias adicionales de $200 millonesPacifi c Lumber Company Gestin de ecosistemas forestales a largo plazo 6.7 $398 millones VPNProcter & Gamble Rediseo del sistema de produccin y distribucin 8.1 $200 millonesCanadian Pacifi c Railway Plan de rutas para un tren de carga 9.3 $100 millonesUnited Airlines Reasignacin de aviones a vuelos cuando ocurreninterrupciones9.6 No estimadosEjrcito de Estados Unidos Planeacin logstica de la Operacin Tormenta del Desierto 10.3 No estimadosAir New Zealand Programacin de tripulaciones en una aerolnea 11.2 $6.7 millonesTaco Bell Planeacin de los programas de trabajo de los empleadosde restaurantes11.5 $13 millonesGestin de desperdicios Desarrollo de un sistema de administracin de rutas para larecoleccin y disposicin de basura11.7 $100 millonesBank Hapoalim Group Desarrollo de un sistema de apoyo a las decisiones deasesores en inversiones12.1 Ganancias adicionales de $31 millonesSears Rutas y programacin de vehculos para servicio y entregasa domicilio13.2 $42 millonesConoco-Phillips Evaluacin de proyectos de exploracin petrolera 15.2 No estimadosOfi cina de compensacionesa los trabajadoresGestin de solicitudes de incapacidad y rehabilitacin dealto riesgo15.3 $4 millonesWestinghouse Evaluacin de proyectos de investigacin y desarrollo 15.4 No estimadosMerrill Lynch Administracin del riesgo de liquidez de lneas de crditorevolventes16.2 Liquidez adicional de $4 mil millonesPSA Peugeot Citren Gua para el proceso de diseo de plantas de ensamble deautomviles efi cientes16.8 Utilidades adicionales de $130 millonesKeyCorp Mejora de la efi ciencia de los cajeros de banco 17.6 $20 millonesGeneral Motors Mejora de la efi ciencia de lneas de produccin 17.9 $90 millonesDeere & Company Administracin de inventarios a lo largo de una cadena desuministro18.5 Reduccin de $1 000 millones eninventarioTime Inc. Administracin de canales de distribucin de revistas 18.7 Utilidades adicionales de $3.5 millonesBank One Corporation Administracin de lneas de crdito y tasas de inters detarjetas de crdito19.2 Utilidades adicionales de $75 millonesMerrill Lynch Anlisis de precios de provisin de servicios fi nancieros 20.2 Ganancias adicionales de $50 millonesAT&T Diseo y operacin de centros de atencin telefnica 20.5 Utilidades adicionales de $750 millonesalgoritmos son muy efi cientes y casi siempre se utilizan para solucionar problemas que incluyencientos o miles de variables. Adems, se presenta una introduccin acerca de cmo funcionan yqu los hace tan efi cientes. Ms adelante, estos algoritmos se utilizarn para resolver diversos problemasen una computadora. El OR Courseware que contiene el sitio web del libro (www.mhhe.com/hillier) es la herramienta clave para hacerlo.Una caracterstica especial del OR Courseware es el programa llamado OR Tutor, cuyo objetivoes ser una gua personal para ayudar en el aprendizaje de los algoritmos. Este programacontiene muchos ejemplos de demostracin en los que se despliegan y explican los algoritmos enaccin. Estas demostraciones complementan los ejemplos del libro.T2 5Adems, el OR Courseware incluye un paquete especial llamado Interactive OperationsResearch Tutorial, o IOR Tutorial. Este paquete innovador fue implementado en Java y estdiseado para mejorar la experiencia de aprendizaje de los estudiantes que utilicen este libro. ElIOR Tutorial incluye muchas rutinas interactivas para ejecutar los algoritmos de manera dinmicay en un formato conveniente. La computadora realiza todos los clculos de rutina mientras el estudiantecentra su atencin en aprender y ejecutar la lgica del algoritmo. Estas rutinas interactivasson una manera efi ciente e ilustrativa de resolver muchos de los problemas de tarea. El IOR Tutorialtambin incluye otras herramientas tiles, como algunos procedimientos automticos para ejecutaralgoritmos y varios otros que ofrecen un despliegue grfi co de la forma en que la solucin queproporciona un algoritmo vara a medida que cambian los datos del problema.En la prctica, los algoritmos son ejecutados en paquetes de software comercial; por ello, esimportante familiarizar al estudiante con la naturaleza de los programas que utilizar en la vidaprofesional. El OR Courseware incluye una gran cantidad de material para introducir los tres paquetesde mayor uso, descritos a continuacin. Juntos, estos paquetes permiten resolver con granefi ciencia casi todos los modelos de IO que se presentan en este libro. Adems, se agregan ciertasrutinas automticas propias del OR Courseware slo para algunos casos en los que estos paquetesno son aplicables.En la actualidad, es comn el uso del paquete de hojas de clculo lder, Microsoft Excel, paraelaborar pequeos modelos de IO en este formato. Despus, se utiliza el Excel Solver para resolverlos modelos, en ocasiones, en una versin mejorada, como el Premium Solver for Education incluidoen el OR Courseware. ste incluye archivos individuales de Excel, basados en el relativamentenuevo Excel 2007, para casi cada captulo del libro. Cada vez que se presenta un ejemplo que puedaser resuelto con Excel, se proporciona la formulacin completa en una hoja de clculo y se da lasolucin en el archivo de Excel del captulo. En el caso de muchos modelos que aparecen en el librose dispone de una plantilla de Excel que incluye las ecuaciones necesarias para resolver el modelo.Algunos complementos de Excel tambin se encuentran en el sitio web de este libro.Despus de muchos aos, LINDO y su lenguaje de modelado LINGO an es uno delos programas de software ms populares para resolver modelos de investigacin de operaciones.En la actualidad es posible bajar gratis de internet las versiones para estudiante, pero tambin fueincluido en el OR Courseware. En cuanto a Excel, cada vez que un ejemplo pueda ser resuelto coneste paquete, se darn todos los detalles en un archivo de LINGO/LINDO para ese captulo en elOR Courseware.CPLEX es un software muy usado para resolver problemas grandes que son un reto en investigacinde operaciones. Cuando se los debe enfrentar, tambin es comn usar un sistema de modeladopara elaborar el modelo matemtico de manera efi ciente e introducirlo en la computadora. MPL esRecuadro de aplicacinFederal Express (FedEx) es la compaa de transporte depaquetes ms grande del mundo. Cada da de trabajo entregams de 6.5 millones de documentos, paquetes y otros artculosa travs de Estados Unidos y ms de 220 pases y territorios alrededordel mundo. En algunos casos, la entrega de estos embarquesest garantizada para el da siguiente a las 10:30 a.m.Los desafos logsticos que implica proporcionar este servicioson extraordinarios. Los millones de embarques diariosdeben ordenarse y ponerse en ruta de manera individual haciala ubicacin general correcta (por lo general por avin) paradespus ser entregados en el destino exacto (normalmente conun vehculo motorizado) en un tiempo sorprendentementebreve. Cmo es esto posible?La investigacin de operaciones (IO) es el motor tecnolgicoque impulsa a esta compaa. Desde su fundacin en1973, la IO le ha ayudado a tomar sus decisiones de negociosms importantes, entre ellas inversiones en equipo, estructurade rutas, programacin, fi nanzas y ubicacin de instalaciones.Despus de que la IO recibi el crdito por salvar a la compaadurante sus primeros aos, se volvi una costumbre teneruna representacin de IO en las reuniones de la alta direcciny, en realidad, algunos de los vicepresidentes corporativos hansurgido del destacable grupo de IO de FedEx.FedEx ha sido reconocida como una compaa de clasemundial. De manera rutinaria se encuentra entre las mejorescompaas de la lista anual de Fortune Magazine de LasCompaas ms Admiradas del Mundo. Tambin fue la primeraganadora del prestigioso premio que ahora se conocecomo INFORMS, el cual se otorga todos los aos por la efi cazy repetida integracin de la IO en la toma de decisiones dela organizacin en formas originales, variadas, novedosas yduraderas.Fuente: R. O. Mason, J. L. McKenney, W. Carlson y D. Copeland,Absolutely, Positively Operations Research: The Federal ExpressStory, Interfaces, 27(2): 17-36, marzo-abril de 1997. (En nuestrositio web www.mhhe.com/hillier se proporciona un vnculo coneste artculo.)6 CAPTULO 1 INTRODUCCINun sistema de modelado amigable que utiliza principalmente CPLEX para resolver los modelos.Tambin utiliza otros paquetes que incluyen LINDO, CoinMP (que se explica en la seccin 4.8),CONOPT (que se presenta en la seccin 12.9), LGO (que se introduce en la seccin 12.10) y BendX(til para resolver algunos modelos estocsticos). Una versin para el estudiante de MPL, junto conlas versiones para el estudiante ms recientes de CPLEX y sus restantes paquetes de solucin puedenobtenerse de manera gratuita en internet. Para conveniencia del lector, en el OR Courseware tambinse puede encontrar esta versin para el estudiante (que incluye todos los paquetes de solucin mencionados).De nuevo, todos los ejemplos que puedan resolverse con estos paquetes se detallan en losarchivos MPL/CPLEX de los captulos correspondientes en el OR Courseware.Estos tres paquetes y la manera de usarlos son descritos con ms detalle en especial cerca delfi nal de los captulos 3 y 4. El apndice 1 tambin proporciona documentacin del OR Coursewarey se incluye el OR Tutor y el IOR Tutorial.Como una indicacin acerca del material relevante que se incluye en el OR Courseware, al fi nalde cada captulo a partir del tercero aparecer una lista de ayuda para el aprendizaje de este captuloen nuestro sitio web. Como se explica al principio de la seccin de problemas de cada captulo,fueron colocados algunos smbolos a la izquierda del nmero del problema o del inciso cuando estematerial sea til, y se incluyeron los ejemplos de demostracin y las rutinas interactivas.Otra ayuda para el aprendizaje en nuestro sitio web es un conjunto de ejemplos desarrollados(Worked Examples) para cada captulo (del 3 en adelante). Estos ejemplos resueltos sirven decomplemento a los del libro para que se utilicen cuando sea conveniente, sin interrumpir el fl ujode material en las mltiples ocasiones en las que no es necesario un ejemplo adicional. Estos ejemploscomplementarios tambin pueden ser tiles durante la preparacin de un examen. Siempre queun ejemplo complementario de un tema en particular est incluido en la seccin de Worked Examplesdel sitio web, se lo mencionar en el texto del libro. Para asegurar que esta mencin no sea pasadapor alto, cada vez se marcarn las palabras ejemplo adicional (o algo similar) en negritas.El sitio web tambin incluye un glosario de cada captulo. REFERENCIAS SELECCIONADAS1. Bell, P. C., C. K. Anderson y S. P. Kaiser, Strategic Operations Research and the Edelman Prize FinalistApplications 1989-1998, en Operations Research, 51(1): 17-31, enero-febrero de 2003.2. Gass, S. I. y A. A. Assad: An Annotated Timeline of Operations Research: An Informal History, KluwerAcademic Publishers (ahora Springer), Boston, 2005.3. Gass, S. I. y C. M. Harris (eds.), Encyclopedia of Operations Research and Management Science, 2a.ed., Kluwer Academic Publishers, Boston, 2001.4. Horner, P.: History in the Making, en OR/MS Today, 29(5): 30-39, octubre de 2002.5. Horner, P. (ed.), Special Issue: Executives Guide to Operations Research, en OR/MS Today, Institutefor Operations Research and the Management Sciences, 27(3), junio de 2000.6. Kirby, M. W.: Operations Research Trajectories: The Anglo-American Experience from the 1940s tothe 1990s, en Operations Research, 48(5): 661-670, septiembre-octubre de 2000.7. Miser, H. J., The Easy Chair: What OR/MS Workers Should know About the Early Formative Years ofTheir Profession, en Interfaces, 30(2): 99-111, marzo-abril de 2000.8. Wein, L.M. (ed.), 50th Anniversary Issue, en Operations Research (un estudio especial que describeexplicaciones personales de algunos desarrollos tericos y prcticos clave recientes), 50(1), enero-febrerode 2002. PROBLEMAS1.3-1. Seleccione una de las aplicaciones de investigacin de operacionesque se mencionan en la tabla 1.1. Lea el artculo al que se hacereferencia en el Recuadro de aplicacin que se presenta en la seccinque se muestra en la tercera columna. (En nuestro sitio web www.mhhe.com/hillier se proporciona un vnculo a todos estos artculos.)Escriba un resumen de dos pginas acerca de la aplicacin y los beneficios que proporcion; incluya los benefi cios no fi nancieros.1.3-2. Seleccione tres de las aplicaciones de investigacin de operacionesque se mencionan en la tabla 1.1. Para cada una, lea el artculoal que se hace referencia en el Recuadro de aplicacin que se presentaen la seccin que se muestra en la tercera columna. (En nuestro sitioweb www.mhhe.com/hillier se proporciona un vnculo a todos estosartculos.) En cada caso, escriba un resumen de una pgina acerca dela aplicacin y sus benefi cios; incluya los no fi nancieros.1.3-3. Lea el artculo de referencia que describe todo el estudio de IOque se resume en el Recuadro de aplicacin de la seccin 1.3. Enlistelos diferentes benefi cios fi nancieros y no fi nancieros que resultaronde este estudio.