Fundamentos de La Programacion Lineal

Fundamentos de la Investigacin de Operaciones I

Hillier Frederick, Lieberman Gerald, Introduccin a la investigacin de operaciones, Mxico, 5 edicin, ed. Mc Graw Hill, 1995. Taha Hamdy, Investigacin de Operaciones una introduccin, Mxico, Editorial Alfaomega, 1989.

INSTITUTO TECNOLGICO DE DURANGO EDUCACIN A DISTANCIA

Gua Didctica de Investigacin de Operaciones I 2

Definicin de la Investigacin de Operaciones La investigacin de operaciones (IO) aspira a determinar el mejor curso de

accin (ptimo) de un problema de decisin con la restriccin de recursos limitados. El termino investigacin de operaciones muy a menudo est asociado casi en exclusiva con la aplicacin de tcnicas matemticas para representar por medio de un modelo y analizar problemas de decisin. Aunque las matemticas y los modelos matemticos representan una piedra angular de IO, la labor consiste ms en resolver un problema que en construir y resolver modelos matemticos. Un estudio de investigacin de operaciones consiste en construir un modelo de la

situacin fsica. Un modelo de investigacin de operaciones se define como una representacin idealizada (simplificada) de un sistema de la vida real, el sistema puede ya estar en existencia o puede todava ser una idea en espera de ejecucin.

Modelo

Un objetivo del modelo es analizar el comportamiento del sistema a fin de mejorar su funcionamiento, otro objetivo es diversificar la mejor estructura del sistema futuro. La complejidad de un sistema real resulta del gran nmero de elementos (variables) que controlan el comportamiento del sistema. El tipo ms importante de modelo en investigacin de operaciones es el modelo simblico o matemtico. Al formular este tipo de modelo suponemos que todas las variables son (cuantificables.La mayora de los analistas de Investigacin de operaciones se identifican principalmente con modelos matemticos ya que estos modelos son adecua-dos para el anlisis de una problemtica determinada, lo cual usualmente crea la posibilidad de encontrar la mejor solucin por medio de herramientas de tipo matemtico.



Tipos de modelos de Investigacin de Operaciones

El tipo ms importante de modelo de investigacin de operaciones es el modelo simblico o matemtico. Al formular este tipo uno supone que todas las variables relevantes son cuantificables. Por consiguiente, los smbolos mate-mticos se utilizan para representar variables, las cuales entonces estn rela-cionadas con las funciones matemticas apropiadas para describir el compor-tamiento del sistema.

La mayora de los analistas de I0 identifican el nombre investigacin de

operaciones principalmente con modelos matemticos. La razn puede ser que tales modelos son adecuados para el anlisis matemtico, lo cual usualmente crea la posibilidad de encontrar la "mejor" solucin por medio de herramientas matemticas convenientes. No es sorprendente entonces que la mayor parte de la atencin en investigacin de operaciones se haya concentrado hacia el desarrollo de modelos matemticos.

Adems de los modelos matemticos, se emplean los modelos heursticos y de

simulacin. Los modelos de simulacin "imitan" el comportamiento del sistema sobre un perodo. Esto se logra especificando ciertos eventos, los cuales son puntos en el tiempo, cuya ocurrencia significa que puede recolectarse la informacin importante perteneciente al comportamiento del sistema. Una vez que se definen tales eventos es necesario prestar atencin al sistema nica-mente cuando ocurre un evento. La informacin que mide el funcionamiento del sistema se acumula en observaciones estadsticas, las cuales se actualizan en cuanto cada evento tiene lugar.

Dado que los modelos de simulacin no necesitan funciones matemticas

explcitas para relacionar las variables, usualmente es posible simular sistemas complejos que no pueden modelarse o resolverse matemticamente. Adems, tal flexibilidad permite una representacin ms aproximada del sistema. La principal falla de la simulacin consiste en que el anlisis es equivalente a realizar experimentos y por consiguiente est sujeto al error experimental. Esto lleva a las dificultades usuales de disear (estadsticamente) el experimento, recolectar observaciones y entonces ejecutar las pruebas estadsticas necesarias de inferencia. Naturalmente el modelo de simulacin no es tan conveniente como los modelos matemticos (exitosos), los cuales proporcionan una solucin general al problema.

Mientras que los modelos matemticos buscan la determinacin de la mejor

solucin (ptima) algunas veces la formulacin matemtica puede ser demasiado compleja para permitir una solucin exacta. Aun si la solucin ptima puede obtenerse eventualmente, el cmputo requerido puede ser imprctica-mente grande. En este caso la heurstica puede utilizarse para desarrollar buenas soluciones (aproximadas). El mtodo heurstica de solucin descansa en las



reglas empricas o intuitivas que, dada una solucin actual al modelo, permiten la determinacin de una solucin mejorada. Actualmente los mtodos heursticos son procedimientos de bsqueda que pasan inteligentemente de un punto de solucin a otro, con el objetivo de mejorar el valor del criterio del modelo. Cuando ninguna mejora adicional puede lograrse la mejor solucin que se haya tenido es la solucin aproximada al modelo.

La figura 1.1 muestra los niveles de abstraccin que llevan a la construccin de un modelo de una situacin de la vida real. El sistema real supuesto se abstrae de la situacin de la vida real. El sistema real supuesto se abstrae de la situacin real concentrando las variables dominantes que controlan el comportamiento del sistema real. El modelo que es una abstraccin del mundo real supuesto identifica y simplifica las relaciones entre estas variables en una forma accesible al anlisis. Figura 1.1

Ejemplo 1: Estructura de los modelos matemticos

Un modelo matemtico incluye 3 conjuntos bsicos de elementos:

1. Variables de decisin y parmetros: las variables de decisin son las interrogantes que deben ser determinadas por medio de la solucin del modelo, los parmetros representan las variables controlables del sistema. Tal caso es el del ejemplo1, el nivel de produccin representa una variable de decisin. Los parmetros en este caso son las tasas de con-sumo y produccin de artculos almacenados.

2. Restricciones: para tomar en cuenta las limitaciones fsicas del sistema el modelo debe incluir restricciones que limitan las variables de decisin a los valores factibles (posibles). Esto usualmente se expresa en la forma de

Sistema real

Sistema real supuesto

Modelo



funciones matemticas restrictivas. Por ejemplo, x1 y x2 el nmero de unidades que van a producirse de dos productos (variables de decisin) y a1 y a2 sus respectivos requerimientos por unidad de materia prima (parmetros). Si la cantidad total disponible de esta materia prima es A la funcin correspondiente de restriccin se da como a1 x1+a2x2 A.

3. Funcin objetivo: define la medida de efectividad del sistema como una funcin matemtica de sus variables de decisin. En general la solucin ptima al modelo se obtiene cuando los valores correspondientes a las variables de decisin proporcionan el mejor valor de la funcin objetivo satisfaciendo todas las restricciones. Esto significa que la funcin objetivo acta como un indicador para el logro de la solucin ptima. Los modelos matemticos en investigacin de operaciones pueden ver-se generalmente como sigue: determinar los valores de las variables de decisin x1, x2n los cuales optimizarn x0 =f(x1,. x n)Donde f es la funcin objetivo

Un modelo matemtico de investigacin de operaciones busca optimizar una funcin objetivo sujeta a un conjunto de restricciones. En general no existen reglas fijas para efectuar los niveles de abstraccin

citados en la figura 1.1. La reduccin de las variables que controlan al sistema a un nmero relativamente pequeo de variables dominantes y la abstraccin de un modelo del mundo real supuesto, constituyen ms un arte que una ciencia. La validez del modelo al representar el sistema real depende principal-mente de la creatividad e imaginacin del analista de investigacin de operaciones y del equipo que trabaja en el proyecto. Tales cualidades individuales o personales no pueden ser reguladas por el establecimiento de reglas fijas sobre cmo deber construirse un modelo; puede ser til presentar ideas sobre tipos de modelos.

Simplificacin de un modelo matemtico Despus que se construye un modelo matemtico puede ser necesario simplificar el modelo de tal manera que sea analticamente tratable. Algunas de las simplificaciones comunes incluyen:

1. Convertir las variables discretas en continuas 2. Linealizar funciones no lineales. 3. Eliminar algunas de estas restricciones

La matemtica continua generalmente es ms fcil de tratar tanto desde el punto de vista analtico como de cmputo. La mayora de las tcnicas desarrolladas en 10 tratan con variables continuas. Adems, aun unas pocas variables discretas usualmente producen un problema computacional muy difcil.



Las funciones no lineales en un modelo, frecuentemente requieren un mtodo complejo de solucin. Las tcnicas de cmputo ms poderosas estn aso-ciadas a modelos en los que todas las funciones son lineales. Decididamente muchas tcnicas para modelos no lineales estn basadas en aproximaciones con modelos lineales.

Una regla general en la que se considera el cmputo en la mayora de los

modelos es que cuanto mayor es el nmero de restricciones, menos eficiente es el modelo. Consecuentemente, es ventajoso eliminar por completo las restricciones que uno piensa no tendrn un efecto serio en la solucin ptima. En el caso extremo donde no puedan quitarse restricciones, es posible establecer colateralmente estas restricciones que se sospecha no son obligatorias en lo ptimo. Naturalmente no se puede tener siempre la seguridad sobre el estado de cada restriccin. Pero si todas las restricciones desechadas se satisfacen por la solucin ptima del modelo reducido, entonces no debe hacerse nada ms, ya que tales restricciones son redundantes. De otra manera se agregan las restricciones infringidas al modelo reducido y se resuelve el nuevo modelo. El procedimiento contina hasta que se satisfagan todas las restricciones desechadas.

Las tres ideas anteriores cuando se implantan pueden resultar en un modelo

matemtico "menos aproximado". En otras palabras, resultan en un tercer nivel de abstraccin (los dos primeros se introdujeron en la figura 1.1) lo cual ampla adicionalmente la distancia entre el sistema real y el modelo resuelto. Como un resultado de las tres recomendaciones para el sistema original, uno debe estudiar el efecto de esta simplificacin adicional sobre la calidad de la solucin obtenida.



Fases de un estudio de Investigacin de Operaciones

1. Definicin del problema: la primera actividad que se debe desarrollar es el estudio y la interpretacin de la problemtica o de la situacin que se representa, esto es:

a) Una descripcin de la meta o el objetivo de estudio. b) Una identificacin de las alternativas de decisin, los cursos de accin para

una situacin determinada. c) Un reconocimiento de las limitaciones, restricciones y requisitos del

sistema.

el proceso de definicin del problema es fundamental ya que afectar significativamente las conclusiones del estudio

2. Construccin del modelo: esta etapa consiste en reformular el problema de manera conveniente para el anlisis. El modelo deber especificar expresiones cuantitativas para el objetivo y las restricciones del problema en funcin de sus variables de decisin.

1. Definicin del problema

2. Construccin del problema

3. Solucin del modelo problema

5. Implantacin de los

resultados

4. Validacin del modelo

Nota!



La forma convencional como la investigacin de operaciones realiza esto es construyendo un modelo matemtico que represente la esencia del problema. Antes de analizar cmo formular los modelos de este tipo, se explorar la naturaleza general de los modelos y, en particular, la de los modelos matemticos.

Recordemos que los modelos, o representaciones idealizadas, son una parte

integral de la vida diaria. Entre los ejemplos ms comunes pueden citarse los aeromodelos, retratos, globos terrqueos, etc. De igual manera, los modelos juegan un papel muy importante en la ciencia y los negocios, como lo hacen patente los modelos de tomos y de estructuras genticas, las ecuaciones matemticas que describen las leyes fsicas del movimiento o las reacciones qumicas, las grficas, los organigramas y los sistemas contables en la industria. Esos modelos son invaluables, ya que extraen la esencia de la materia de estudio, muestran sus interrelaciones y facilitan el anlisis.

Los modelos matemticos tambin son representaciones idealizadas, pero

estn expresadas en trminos de smbolos y expresiones matemticas las leyes de la fsica como F = ma y E = mc2 son ejemplos familiares. En forma parecida el modelo matemtico de un problema industrial es el sistema de ecuaciones y expresiones matemticas relacionadas que describen la esencia del problema. As se pueden tomar n decisiones cuantificables relacionadas unas con otras, se representan como variables de decisin (como x1, x2, ..., x3) para las que se deben determinar los valores respectivos. La medida de efectividad compuesta (por ejemplo, la ganancia) se expresa entonces como una funcin matemtica de estas variables de decisin (por ejemplo, P = 3x1 + 2x2 + . . . + 5xn). Esta funcin se llama funcin objetivo. Tambin se expresan matemticamente todas las limitaciones que se puedan imponer sobre los va-lores de las variables de decisin, casi siempre en forma de ecuaciones o de-sigualdades (como, xl + 3x1 x2+ 2x2 10). Tales expresiones matemticas de las limitaciones, con frecuencia reciben el nombre de restricciones.

Las constantes (los coeficientes o el lado derecho de las ecuaciones) en las

restricciones y en la funcin objetivo se llaman parmetros del modelo. El mo-delo matemtico puede expresarse entonces como el problema de elegir los valores de las variables de decisin de manera que se maximice la funcin objetivo, sujeta a las restricciones dadas. Un modelo de este tipo, y algunas variaciones menores sobre l, tipifican los modelos analizados en investigacin de operaciones.

Una clase de modelos especialmente importante, que se estudiar poste-

riormente, es el modelo de programacin lineal, en el que las funciones matemticas que aparecen tanto en la funcin objetivo como en las restricciones, son funciones lineales. 3. Solucin del modelo: una vez que se ha formulado el modelo matemtico

para el problema plantado, la siguiente etapa consiste en derivar una solucin



a partir de este modelo. En modelos matemticos esto se logra usando tcnicas de optimizacin bien definidas y se dice que el modelo proporciona una solucin optima, un tema comn en la investigacin de operaciones es el de la bsqueda de una solucin optima, es decir la mejor solucin.

4. La cuarta fase busca la validacin del modelo: un modelo es vlido si,

independiente de sus inexactitudes al representar el sistema, puede dar una prediccin confiable del funcionamiento del sistema. Un mtodo comn para probar la validez de un modelo es comparar su funcionamiento con algunos datos pasados disponibles del sistema actual. El modelo ser vlido si bajo condiciones similares de entradas puede reproducir el funcionamiento pasado del sistema. El problema aqu es que no existe seguridad de que el funcionamiento futuro del sistema continuar duplicando su historia. Tambin, ya que el modelo est basado en el examen cuidadoso de datos anteriores, esta comparacin deber siempre revelar resultados favorables. En algunos ejemplos este problema debe resolverse utilizando datos de corridas de ensayo del sistema. Debe notarse que tal mtodo de validacin no es apropiado para sistemas que no

existen, ya que no habr datos disponibles para comparacin. En algunos casos, si el sistema original se investiga por un modelo matemtico, puede ser factible construir un modelo de simulaciones del cual se obtienen los datos para llevar a cabo la comparacin indicada. 5. La fase final del estudio trata sobre la implantacin: de los resultados

probados del modelo. La tarea de aplicar estos resultados recae principalmente en los investigadores de operaciones. Esto bsicamente implicara la traduccin de estos resultados en instrucciones de operacin detallada, emitidas en una forma comprensible a los individuos que administrarn y operaran el sistema despus. La interaccin del equipo de investigacin de operaciones y el personal de operacin llegara a su mximo en esta fase. La comunicacin entre los dos grupos puede mejorarse buscando la participacin del personal de operacin al desarrollar el plan de implantacin. En efecto esta participacin deber hacerse a travs de todas las fases del estudio. En esta forma ninguna consideracin prctica, que de otra manera puede llevar al fracaso del sistema, se dejar de analizar. Es importante que la fase de implantacin se ejecute mediante la cooperacin del equipo de investigacin de operaciones y de aquellos que sern responsables de tomar las decisiones en la administracin y operacin del sistema.



Un tema comn en investigacin de operaciones es la bsqueda de la solucin ptima, es decir, la mejor. Sin duda, como aqu se presenta, se han desarrollado muchos procedimientos para encontrarlas en cierto tipo de problemas, pero es necesario reconocer que estas soluciones son ptimas slo respecto al modelo que se est utilizando. Como el modelo necesariamente es una idealizacin y no una representacin del problema real, no puede existir una garanta utpica de que la solucin ptima del modelo resulte ser la mejor solucin posible que pueda llevarse a la prctica para el problema real. Esto, por supuesto, es de esperarse si se toman en cuenta los muchos imponderables e incertidumbres asociados a casi todos los problemas reales, pero si el modelo est bien formulado y verificado, la solucin que resulta debe tender a una buena aproximacin del curso de accin ideal para el problema real. Por todo esto, ms que enfrascarse en pedir lo imposible, la prueba del xito de un estudio de investigacin de operaciones debe ser el hecho de si proporciona o no una mejor gua en las decisiones, que la que se puede obtener por otros medios.

El eminente cientfico de la administracin y premio Nobel de Economa, Herbert Simon, introdujo el concepto de que en la prctica es mucho ms fre-cuente satisfizar que optimizar.

Al inventar el trmino satisfizar como una combinacin de satisfacer y optimizar, Simon describe la tendencia de los administradores a buscar una solucin que sea "lo suficientemente buena" para el problema que se tiene. En lugar de intentar desarrollar una medida global de eficiencia para conciliar de manera ptima los conflictos entre los diferentes objetivos deseables (incluyendo los criterios bien establecidos para juzgar el desempeo de los distintos segmentos de la organizacin), se puede usar un enfoque ms pragmtico. Las metas se pueden establecer de manera que marquen los niveles mnimos satisfactorios de eficiencia en las diferentes reas, Jasndose quiz en niveles de desempeo anteriores o en los logros de la competencia. Si se encuentra una solucin que permita que todas estas metas se cumplan, es posible que se adopten ms requisitos. sta es la naturaleza de satisfizar. La distincin entre optimizar y satisfizar refleja la diferencia entre la teora y la realidad, diferencia que con frecuencia se enfrenta al tratar de implantar esa teora en la prctica. En palabras de uno de los lderes ingleses de la investigacin de operaciones, Samuel Eilon, "optimizar es la ciencia de lo esencial; satisfizar es el arte de lo factible



Trminos clave:

1. Investigacin de operaciones 2. Modelo

3. Variable 4. Cuantificable 5. Modelo simblico matemtico

6. Modelo de simulacin

7. Heurstica

8. Variables de decisin

9. Restricciones

10. Funcin objetivo

11. Optimizar

12. Definicin del problema

13. Construccin del modelo

14. Satisfizar

Documents

Fundamentos de La Programacion Lineal