Antología Io

Parte 1: Conceptos Generales Por lo general se debe iniciar un curso con algunos conceptos básicos para el mejor entendimiento del mismo, por lo tanto empezaremos con las definiciones que involucran a la Investigación de Operaciones.

1.1 La Investigación de Operaciones La Investigación de Operaciones o Investigación Operativa, es una rama de las Matemáticas consistente en el uso de modelos matemáticos, estadística y algoritmos con objeto de realizar un proceso de toma de decisiones. Frecuentemente, trata del estudio de complejos sistemas reales, con la finalidad de mejorar (u optimizar) el funcionamiento de los mismos. La investigación de operaciones permite el análisis de la toma de decisiones teniendo en cuenta la escasez de recursos, para determinar cómo se puede optimizar un objetivo definido, como la maximización de los beneficios o la minimización de costes.

1.1 Los orígenes de la IO El origen de la IO se remonta a los inicios de la Segunda Guerra Mundial, había un pequeño grupo de investigadores militares, encabezados por A.P. Rowe, interesados en el uso militar de una técnica conocida como radió ubicación (o radio-localización), que desarrollaron científicos civiles. Algunos historiadores consideran que esta investigación es el punto inicial de la investigación de operaciones. Otros creen que los estudios que tienen las características del trabajo de investigación de operaciones aparecen posteriormente. Algunos consideran que su comienzo está en el análisis y solución del bloqueo naval de Siracusa que Arquímedes presentara al tirano de esa ciudad, en el siglo III A.C. F. W. Lanchester, en Inglaterra, justo antes de la primera guerra mundial, desarrolló relaciones matemáticas sobre la potencia balística de las fuerzas opositoras, que si se resolvían tomando en cuenta el tiempo, podían determinar el resultado de un encuentro militar. Tomás Edison también realizó estudios de guerra antisubmarina. Ni los estudios de Lanchester ni los de Edison tuvieron un impacto inmediato; junto con los de Arquímedes, constituyen viejos ejemplos del empleo de científicos para determinar la decisión óptima en la guerra. No mucho después de que estallara la Segunda Guerra Mundial, la Badswey Research Station, bajo la dirección de Rowe, participó en el diseño de utilización óptima de un nuevo sistema de detección y advertencia prematura, denominado radar (Radio Detection And Ranging – Detección y medición de distancias mediante radio). Poco después este avance sirvió para el análisis de todas las fases de las

1

operaciones nocturnas, y el estudio se constituyó en un modelo de los estudios de investigación de operaciones que siguieron. En agosto de 1940 se organizó un grupo de investigación, bajo la dirección de P. M. S. Blackett, de la Universidad de Manchester, para estudiar el uso de un nuevo sistema antiaéreo controlado por radar. Se conoció al grupo de investigación como el “Circo de Blackett”, nombre que no parece desatinado a la luz de sus antecedentes y orígenes diversos. El grupo estaba formado por tres fisiólogos, dos fisicomatemáticos, un astrofísico, un oficial del ejército, un topógrafo, un físico general y dos matemáticos. Parece aceptarse comúnmente que la formación de este grupo constituye el inicio de la investigación de operaciones. Blackett y parte de su grupo, participaron en 1941 en problemas de detección de barcos y submarinos mediante un radar autotransportado. Este estudio condujo a que Blackett fuera nombrado director de Investigación de Operación Naval del Almirantazgo Británico. Posteriormente, la parte restante de su equipo pasó a ser el grupo de Investigación de Operaciones de la Plana de Investigación y Desarrollo de la Defensa Aérea, y luego se dividió de nuevo para formar el Grupo de Investigación de Operaciones del Ejército. Después de la guerra, los tres servicios tenían grupos de investigación de operaciones. Como ejemplo de esos primeros estudios está el que planteó la Comandancia Costera que no lograba hundir submarinos enemigos con una nueva bomba antisubmarina. Las bombas se preparaban para explotar a profundidades de no menos de 30 m. Después de estudios detallados, un profesor apellidado Williams llegó a la conclusión de que la máxima probabilidad de muerte ocurriría con ajustes para profundidades entre 6 y 7 m. Entonces se prepararon las bombas para mínima profundidad posible de 10 m, y los aumentos en las tasas de muertes, según distintas estimaciones, se incrementaron entre un 400 y un 700%. De inmediato se inició el desarrollo de un mecanismo de disparo que se pudiera ajustar a la profundidad óptima de 6 a 7m. Otro problema que consideró el Almirantazgo fueron las ventajas de los convoyes grandes frente a los pequeños. Los resultados fueron a favor de los convoyes grandes. A pocos meses de que Estados Unidos entrara en la guerra, en la fuerza aérea del ejército y en la marina se iniciaron actividades de investigación de operaciones. Para el Día D (invasión aliada de Normandía), en la fuerza aérea se habían formado veintiséis grupos de investigación de operaciones, cada uno con aproximadamente diez científicos. En la marina se dio un proceso semejante. En 1942, Philip M. Morris, del Instituto Tecnológico de Massachussets, encabezó un grupo para analizar los datos de ataque marino y aéreo en contra de los submarinos alemanes. Luego se emprendió otro estudio para determinar la mejor política de maniobrabilidad de los barcos en convoyes a fin de evadir aeroplanos enemigos, e incluso los efectos de la exactitud antiaérea. Los resultados del estudio demostraron que los barcos pequeños deberían cambiar su dirección gradualmente.

2

Al principio, la investigación de operaciones se refería a sistemas existentes de armas y a través del análisis, típicamente matemático, se buscaban las políticas óptimas para la utilización de esos sistemas. Hoy día, la investigación de operaciones todavía realiza esta función dentro de la esfera militar; sin embargo, lo que es mucho más importante, ahora se analizan las necesidades del sistema de operación con modelos matemáticos, y se diseña un sistema (o sistemas) de operación que ofrezca la capacidad óptima. El éxito de la investigación de operaciones en la esfera de lo militar quedó bastante bien documentado hacia finales de la Segunda Guerra Mundial. El general Arnold encargó a Donald Douglas, de la Douglas Aircraft Corporation, en 1946, la dirección de un proyecto Research And Development (RAND – Investigación y Desarrollo) para la Fuerza Aérea. La corporación RAND desempeña hoy día un papel importante en la investigación que se lleva a cabo en la Fuerza Aérea.

1.3 Características de la IO A partir del inicio de la investigación de operaciones como disciplina, sus características más comunes son:

¾

Enfoque de sistemas.

¾

Modelado matemático.

¾

Enfoque de equipo.

Estas características prevalecieron a ambos lados del Atlántico, a partir del desarrollo de la investigación de operaciones durante la Segunda Guerra Mundial. Para maximizar la capacidad militar de entonces, fue necesario un enfoque de sistemas. Ya no era tiempo de tomar decisiones de alto nivel sobre la dirección de una guerra que exigía sistemas complicados frente a la estrategia de guerras anteriores o como si se tratara de un juego de ajedrez. La computadora digital y el enfoque de sistemas fueron preludios necesarios del procedimiento matemático de los sistemas militares de operaciones. Las matemáticas aplicadas habían demostrado su utilidad en el análisis de sistemas económicos, y el uso de la investigación de operaciones en el análisis de sistemas demostró igualmente su utilidad. Para que un análisis de un sistema militar de operaciones fuera tecnológicamente factible, era necesario tener una comprensión técnica adecuada, que tomara en cuenta todas las subcomponentes del sistema. En consecuencia, el trabajo de equipo resultó ser tan necesario como efectivo.

3

Actualmente la Investigación Operativa es una moderna disciplina científica que se caracteriza por la aplicación de teoría, métodos y técnicas especiales, para buscar la solución de problemas de administración, organización y control que se producen en los diversos sistemas que existen en la naturaleza y los creados por el ser humano, tales como las organizaciones a las que identifica como sistemas organizados, sistemas físicos, económicos, ecológicos, educacionales, de servicio social, etc. El objetivo más importante de la aplicación de la Investigación Operativa es apoyar en la “toma óptima de decisiones” en los sistemas y en la planificación de sus actividades. El enfoque fundamental de la Investigación Operativa es el enfoque de sistemas, por el cual, a diferencia del enfoque tradicional, se estudia el comportamiento de todo un conjunto de partes o subsistemas que interaccionan entre sí, se identifica el problema y se analizan sus repercusiones, buscándose soluciones integrales que beneficien al sistema como un todo. Para hallar la solución, la Investigación Operativa generalmente representa el problema como un modelo matemático, que es analizado y evaluado previamente.

1.4 La Investigación de Operaciones como una ciencia interdisciplinaria Algunas personas se verían tentadas a aplicar métodos matemáticos a cuanto problema se presentase, pero es que ¿acaso siempre es necesario llegar al óptimo? Podría ser más caro el modelar y el llegar al óptimo que a la larga no nos dé un margen de ganancias muy superior al que ya tenemos. Tómese el siguiente ejemplo: La empresa EMX aplica I.O. y gasta por el estudio y el desarrollo de la aplicación $100 pero luego de aplicar el modelo observa que la mejora no es muy diferente a la que actualmente tenía. Podríamos pues indicar que la investigación de operaciones sólo se aplicará a los problemas para los cuales el buen sentido se revela impotente: En el dominio combinatorio, muchas veces la enumeración es imposible. Por ejemplo, si tenemos 200 trabajos por realizar, que toman tiempos distintos y solo cuatro personas que pueden hacerlos, enumerar cada una de las combinaciones podría ser ineficiente (aparte de desanimante). Luego los métodos de secuenciación serán los más apropiados para este tipo de problemas. De igual manera, la I.O. es útil cuando en los fenómenos estudiados interviene el azar. La noción de esperanza matemática y la teoría de procesos estocásticos suministran la herramienta necesaria para construir el cuadro en el cual se optimizará la función económica. Dentro de este tipo de fenómenos se encuentran las líneas de espera y los inventarios con demanda probabilística.

4

Con mayor motivo, la investigación de operaciones se muestra como un conjunto de instrumentos precioso cuando se presentan situaciones de concurrencia. La teoría de juegos no permite siempre resolverlos formalmente, pero aporta un marco de reflexión que ayude a la toma de decisiones. Cuando observamos que los métodos científicos resultan engorrosos para nuestro conjunto de datos, tenemos otra opción, simular tanto el comportamiento actual así como las propuestas y ver si hay mejoras sustanciales. Las simulaciones son experiencias artificiales. Finalmente debe ponerse la máxima atención en no considerar la investigación de operaciones como una colección de recetas heterogéneas y aplicables sistemáticamente en unas situaciones determinadas. Si se cae en este error, será muy difícil captar en condiciones reales los problemas que puedan deducirse de los múltiples aspectos de esta disciplina. En la ciencia de la administración, que también es conocida como investigación de operaciones, los administradores utilizan las matemáticas y las computadoras para tomar decisiones racionales en la resolución de problemas. Aunque estos administradores pueden resolver algunos problemas con su experiencia, ocurre que en el complejo mundo en que vivimos muchos problemas no pueden ser resueltos basándose en la experiencia. Las técnicas de la administración se aplican a dos categorías básicas de problemas:

¾

Problemas Deterministicos: son aquellos en que la información necesaria para obtener una solución se conoce con certeza

¾

Problemas Estocásticos: son aquellos en los que parte de la información necesaria no se conoce con certeza, como es el caso de los deterministicos, sino que más bien se comporta de una manera probabilística.

El objetivo y finalidad de la “investigación operacional” (conocida también como “teoría de la toma de decisiones”, o ”programación matemática”) es encontrar la solución óptima para un determinado problema (militar, económico, de infraestructura, logístico, etc.) Está constituida por un acercamiento científico a la solución de problemas complejos, tiene características intrínsecamente multidisciplinares y utiliza un conjunto diversificado de instrumentos, prevalentemente matemáticos, para la modelización, la optimización y el control de sistemas estructurales. En el caso particular de problemas de carácter económico, la función objetivo puede ser obtener el máximo rendimiento o el menor costo. La investigación operacional tiene un rol importante en los problemas de toma de decisiones porque permite tomar las mejores decisiones para alcanzar un determinado objetivo respetando los vínculos externos, no controlables por quien debe tomar la decisión.

5

La investigación operacional consiste en la aplicación del método científico, por parte de grupos interdisciplinares, a problemas de control de sistemas organizativos con la finalidad de encontrar soluciones que atiendan de la mejor manera posible a los objetivos de la organización en su conjunto. No se sustituye a los responsables de la toma de decisiones, pero dándoles soluciones al problema obtenidas con métodos científicos, les permite tomar decisiones racionales. Puede ser utilizada en la programación lineal(planificación del problema); en la programación dinámica (planificación de las ventas); en la teoría de las colas(para controlar problemas de tránsito).

1.5 La metodología de IO Como toda disciplina, la IO debe seguir un método, el cual consta de las siguientes fases:

¾

Definición del problema y recolección de datos: La mayor parte de los problemas prácticos con los que se enfrenta el equipo IO están descritos inicialmente de una manera vaga. Por consiguiente, la primera actividad que se debe realizar es el estudio del sistema relevante y el desarrollo de un resumen bien definido del problema que se va a analizar. Esto incluye determinar los objetivos apropiados, las restricciones sobre lo que se puede hacer, las interrelaciones del área bajo estudio con otras áreas de la organización, los diferentes cursos de acción posibles, los límites de tiempo para tomar una decisión, etc. Este proceso de definir el problema es crucial ya que afectará en forma significativa la relevancia de las conclusiones del estudio. ¡Es difícil extraer una respuesta "correcta" a partir de un problema "equivocado"! Por su naturaleza, la investigación de operaciones se encarga del bienestar de toda la organización, no sólo de algunos de sus componentes. Un estudio de IO busca soluciones óptimas globales y no soluciones subóptimas aunque sean lo mejor para uno de los componente. Entonces, idealmente, los objetivos que se formulan debe coincidir con los de toda la organización. Sin embargo, esto no siempre es conveniente. Muchos problemas interesan nada más a una parte de la organización, de manera que el análisis sería innecesariamente besado si los objetivos fueran muy generales y si se prestara atención especial a todos los efectos secundarios sobre el resto de la organización. En lugar de ello, los objetivos usados en un estudio deben ser tan específicos como sea posible, siempre y cuando contemplen las metas principales del tomador de decisiones y mantengan un nivel razonable de consistencia con los objetivos de los altos niveles.

¾

Formulación de un modelo matemático: Una vez definido el problema del tomador de decisiones, la siguiente etapa consiste en reformularlo de manera conveniente para su análisis. La forma convencional en que la investigación de operaciones realiza esto es construyendo un modelo

6

matemático que represente la esencia del problema. Antes de analizar como formular los modelos de este tipo, se explorará la naturaleza general de los modelos y, en particular, la de los modelos matemáticos. El modelo matemático está constituido por relaciones matemáticas (ecuaciones y desigualdades) establecidas en términos de variables, que representa la esencia el problema que se pretende solucionar. Para construir un modelo es necesario primero definir las variables en función de las cuales será establecido. Luego, se procede a determinar matemáticamente cada una de las dos partes que constituyen un modelo: a) la medida de efectividad que permite conocer el nivel de logro de los objetivos y generalmente es una función (ecuación) llamada función objetivo; b) las limitantes del problema llamadas restricciones que son un conjunto de igualdades o desigualdades que constituyen las barreras y obstáculos para la consecución del objetivo. Un modelo siempre debe ser menos complejo que el problema real, es una aproximación abstracta de la realidad con consideraciones y simplificaciones que hacen más manejable el problema y permiten evaluar eficientemente las alternativas de solución. Los modelos matemáticos tienen muchas ventajas sobre una descripción verbal del problema. Una ventaja obvia es que el modelo matemático describe un problema en forma mucho más concisa. Esto tiende a hacer que toda la estructura del problema sea más comprensible y ayude a revelar las relaciones importantes entre causa y efecto. De esta manera, indica con más claridad que datos adicionales son importantes para el análisis. También facilita simultáneamente el manejo del problema en su totalidad y el estudio de todas sus interpelaciones. Por último, un modelo matemático forma un puente para poder emplear técnicas matemáticas y computadoras de alto poder, para analizar el problema. Sin duda, existe una amplia disponibilidad de paquetes de software para muchos tipos de modelos matemáticos, para micro y minicomputadoras. Por otro lado, existen obstáculos que deben evitarse al usar modelos matemáticos. Un modelo es, necesariamente, una idealización abstracta del problema, por lo que casi siempre se requieren aproximaciones y suposiciones de simplificación si se quiere que el modelo sea manejable (susceptible de ser resuelto). Por lo tanto, debe tenerse cuidado de que el modelo sea siempre una representación válida del problema. El criterio apropiado para juzgar la validez de un modelo es el hecho de si predice o no con suficiente exactitud los efectos relativos de los diferentes cursos de acción, para poder tomar una decisión que tenga sentido. En consecuencia, no es necesario incluir detalles sin importancia o factores que tienen aproximadamente el mismo efecto sobre todas las opciones. Ni siquiera es necesario que la magnitud absoluta de la medida de efectividad sea aproximadamente correcta para las diferentes alternativas, siempre que sus valores relativos (es 7

decir, las diferencias entre sus valores) sean bastante preciso. Entonces, todo lo que se requiere es que exista una alta correlación entre la predicción del modelo y lo que ocurre en la vida real. Para asegurar que este requisito se cumpla, es importante hacer un número considerable de pruebas del modelo y las modificaciones consecuentes. Aunque esta fase de pruebas se haya colocado después en el orden del libro, gran parte del trabajo de validación del modelo se lleva a cabo durante la etapa de construcción para que sirva de guía en la obtención del modelo matemático.

¾

Obtener una solución a partir de un modelo: Resolver un modelo consiste en encontrar los valores de las variables dependientes, asociadas a las componentes controlables del sistema con el propósito de optimizar, si es posible, o cuando menos mejorar la eficiencia o la efectividad del sistema dentro del marco de referencia que fijan los objetivos y las restricciones del problema. La selección del método de solución depende de las características del modelo. Los procedimientos de solución pueden ser clasificados en tres tipos: a) analíticos, que utilizan procesos de deducción matemática; b) numéricos, que son de carácter inductivo y funcionan en base a operaciones de prueba y error; c) simulación, que utiliza métodos que imitan o, emulan al sistema real, en base a un modelo. Muchos de los procedimientos de solución tienen la característica de ser iterativos, es decir buscan la solución en base a la repetición de la misma regla analítica hasta llegar a ella, si la hay, o cuando menos a una aproximación.

¾

Prueba del modelo: El desarrollo de un modelo matemático grande es análogo en algunos aspectos al desarrollo de un programa de computadora grande. Cuando se completa la primera versión, es inevitable que contenga muchas fallas. El programa debe probarse de manera exhaustiva para tratar de encontrar y corregir tantos problemas como sea posible. Eventualmente, después de una larga serie de programas mejorados, el programador (o equipo de programación) concluye que el actual da, en general, resultados razonablemente válidos. Aunque sin duda quedarán algunas fallas ocultas en el programa (y quizá nunca se detecten, se habrán eliminado suficientes problemas importantes como para que sea confiable utilizarlo. De manera similar, es inevitable que la primera versión de un modelo matemático grande tenga muchas fallas. Sin duda, algunos factores o interpelaciones relevantes no se incorporaron al modelo y algunos parámetros no se estimaron correctamente. Esto no se puede eludir dada la dificultad de la comunicación y la compresión de todos los aspectos y sutilezas de un problema operacional complejo, así como la dificultad de recolectar datos confiables. Por lo tanto, antes de usar el modelo debe probarse exhaustivamente para intentar identificar y corregir todas las fallas que se pueda. 8

Con el tiempo, después de una larga serie de modelos mejorados, el equipo de IO concluye que el modelo actual produce resultados razonablemente válidos. Aunque sin duda quedarán algunos problemas menores ocultos en el modelo (y quizá nunca se detecten), las fallas importantes se habrán eliminado de manera que ahora es confiable usar el modelo. Este proceso de prueba y mejoramiento de un modelo para incrementar su validez se conoce como validación del modelo. Debido a que el equipo de IO puede pasar meses desarrollando todas las piezas detalladas del modelo, es sencillo "no ver el bosque por buscar los árboles". Entonces, después de completar los detalles ("los árboles") de la versión inicial del modelo, una buena manera de comenzar las pruebas es observarlo en forma global ("el bosque") para verificar los errores u omisiones obvias. El grupo que hace esta revisión debe, de preferencia, incluir por lo menos a una persona que no haya participado en la formulación. Al examinar de nuevo la formulación del problema y comprarla con el modelo pueden descubrirse este tipo de errores. También es útil asegurarse de que todas las expresiones matemáticas sean consistentes en las dimensiones de las unidades que emplean. Además, puede obtenerse un mejor conocimiento de la validez del modelo variando los valores de los parámetros de entrada y/o de las variables de decisión, y comprobando que los resultados del modelo se comporten de una manera factible. Con frecuencia, esto es especialmente revelador cuando se asignan a los parámetros o a las variables valores extremos cercanos a su máximo o a su mínimo. Un enfoque más sistemático para la prueba del modelo es emplear una prueba retrospectiva. Cuando es aplicable, esta prueba utiliza datos históricos y reconstruye el pasado para determinar si el modelo y la solución resultante hubieran tenido un buen desempeño, de haberse usado. La comparación de la efectividad de este desempeño hipotético con lo que en realidad ocurrió, indica si el uso del modelo tiende a dar mejoras significativas sobre la práctica actual. Puede también indicar áreas en las que el modelo tiene fallas y requiere modificaciones. Lo que es más, el emplear las alternativas de solución y estimar sus desempeños históricos hipotéticos, se pueden reunir evidencias en cuanto a lo bien que el modelo predice los efectos relativos de los diferentes cursos de acción. Cuando se determina que el modelo y la solución no son válidos, es necesario iniciar nuevamente el proceso revisando cada una de las fases de la metodología de la investigación de operaciones.

¾

Establecimiento de controles sobre la solución: Una solución establecida como válida para un problema, permanece como tal siempre y cuando las condiciones del problema tales como: las variables no controlables, los parámetros, las relaciones, etc., no cambien significativamente. Esta situación

9

¾

se vuelve más factible cuando algunos de los parámetros fueron estimados aproximadamente. Por lo anterior, es necesario generar información adicional sobre el comportamiento de la solución debido a cambios en los parámetros del modelo. Usualmente esto se conoce como análisis de sensibilidad. En pocas palabras, esta fase consiste en determinar los rangos de variación de los parámetros dentro de los cuales no cambia la solución del problema.

¾

Implantación de la solución: El paso final se inicia con el proceso de "vender" los hallazgos que se hicieron a lo largo del proceso a los ejecutivos o tomadores de decisiones. Una vez superado éste obstáculo, se debe traducir la solución encontrada a instrucciones y operaciones comprensibles para los individuos que intervienen en la operación y administración del sistema. La etapa de implantación de una solución se simplifica en gran medida cuando se ha propiciado la participación de todos los involucrados en el problema en cada fase de la metodología. Preparación para la aplicación del modelo Esta etapa es crítica, ya que es aquí, y sólo aquí, donde se cosecharán los beneficios del estudio. Por lo tanto, es importante que el equipo de IO participe, tanto para asegurar que las soluciones del modelo se traduzcan con exactitud a un procedimiento operativo, como para corregir cualquier defecto en la solución que salga a la luz en este momento. El éxito de la puesta en práctica depende en gran parte del apoyo que proporcionen tanto la alta administración como la gerencia operativa. Es más probable que el equipo de IO obtenga este apoyo si ha mantenido a la administración bien informada y ha fomentado la guía de la gerencia durante el estudio. La buena comunicación ayuda a asegurar que el estudio logre lo que la administración quiere y por lo tanto merezca llevarse a la práctica. También proporciona a la administración el sentimiento de que el estudio es suyo y esto facilita el apoyo para la implantación. La etapa de implantación incluye varios pasos. Primero, el equipo de investigación de operaciones de una cuidadosa explicación a la gerencia operativa sobre el nuevo sistema que se va a adoptar y su relación con la realidad operativa. En seguida, estos dos grupos comparten la responsabilidad de desarrollar los procedimientos requeridos para poner este sistema en operación. La gerencia operativa se encarga después de dar una capacitación detallada al personal que participa, y se inicia entonces el nuevo curso de acción. Si tiene éxito, el nuevo sistema se podrá emplear durante algunos años. Con esto en mente, el equipo de IO supervisa la experiencia inicial con la acción tomada para identificar cualquier modificación que tenga que hacerse en el futuro. A la culminación del estudio, es apropiado que el equipo de investigación de operaciones documento su metodología con suficiente claridad y detalle para que el trabajo sea reproducible. Poder obtener una réplica debe ser parte del código de ética profesional del investigador de

10

operaciones. Esta condición es crucial especialmente cuando se estudian políticas gubernamentales en controversia.

1.6 Limitaciones de la IO ¾

Frecuentemente es necesario hacer simplificaciones del problema original para poder manipularlo y detener una solución.

¾

La mayoría de los modelos sólo considera un solo objetivo y frecuentemente en las organizaciones se tienen objetivos múltiples.

¾

Existe la tendencia a no considerar la totalidad de las restricciones en un problema práctico, debido a que los métodos de enseñanza y entrenamiento dan la aplicación de esta ciencia centralmente se basan en problemas pequeños para razones de índole práctico, por lo que se desarrolla en los alumnos una opinión muy simplista e ingenua sobre la aplicación de estas técnicas a problemas reales.

¾

Casi nunca se realizan análisis costo-beneficio de la implantación de soluciones definidas por medio de la I de O, en ocasiones los beneficios potenciales se van superados por los costos ocasionados por el desarrollo e implantación de un modelo.

11

Parte 2: Programación lineal En este apartado se verán conceptos sobre programación lineal y algunos métodos de solución

2.1 La Programación lineal (PL) Es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función objetivo, también lineal. La programación lineal consiste en optimizar (minimizar o maximizar) una función lineal, que denominaremos función objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales El problema de la resolución de un sistema lineal de inecuaciones se remonta, al menos, a Fourier, después de quien nace el método de eliminación de Fourier-Motzkin. La programación lineal se plantea como un modelo matemático desarrollado durante la segunda guerra mundial para planificar los gastos y los retornos, a fin de reducir los costos al ejército y aumentar las pérdidas del enemigo. Se mantuvo en secreto hasta 1947. En la posguerra, muchas industrias lo usaron en su planificación diaria. Los fundadores de la técnica son George Dantzig, quien publicó el algoritmo simplex, en 1947, John von Neumann, que desarrolló la teoría de la dualidad en el mismo año, y Leonid Kantorovich, un matemático ruso, que utiliza técnicas similares en la economía antes de Dantzig y ganó el premio Nobel en economía en 1975. Leonid Khachiyan en 1979 fue el primero en demostrar que el problema de la programación lineal se solucionaba en tiempo polinomial, sin embargo, el mejor avance en los principios teóricos y prácticos en el campo se produjo en 1984, cuando Narendra Karmarkar introduce un nuevo método del punto interior para resolver problemas de programación lineal. El ejemplo original de Dantzig de la búsqueda de la mejor asignación de 70 personas a 70 puestos de trabajo es un ejemplo de la utilidad de la programación lineal. La potencia de computación necesaria para examinar todas las permutaciones a fin de seleccionar la mejor asignación es inmensa; el número de posibles configuraciones excede al número de partículas en el universo. Sin embargo, toma sólo un momento encontrar la solución óptima mediante el planteamiento del problema como una programación lineal y la aplicación del algoritmo simplex. La teoría de la programación lineal reduce drásticamente el número de posibles soluciones óptimas que deberán ser revisadas.

12

2.1.1 Variables Las variables son números reales mayores o iguales a cero. En caso que se requiera que el valor resultante de las variables sea un número entero, el procedimiento de resolución se denomina Programación entera. Restricciones Las restricciones pueden ser de la forma:

Tipo 1:

Tipo 2:

Tipo 3: Donde: A = valor conocido a ser respetado estrictamente; B = valor conocido que debe ser respetado o puede ser superado; C = valor conocido que no debe ser superado; j = número de la ecuación, variable de 1 a M (número total de restricciones); a; b; y, c = coeficientes técnicos conocidos; X = Incógnitas, de 1 a N; i = número de la incógnita, variable de 1 a N. En general no hay restricciones en cuanto a los valores de N y M. Puede ser N = M; N > M; ó, N < M. Sin embargo si las restricciones del Tipo 1 son N, el problema puede ser determinado, y puede no tener sentido una optimización. Los tres tipos de restricciones pueden darse simultáneamente en el mismo problema

13

2.2 Aplicaciones de la Programación lineal (PL) La programación lineal constituye un importante campo de la optimización por varias razones, muchos problemas prácticos de la investigación de operaciones pueden plantearse como problemas de programación lineal. Algunos casos especiales de programación lineal, tales como los problemas de flujo de redes y problemas de flujo de mercancías se consideraron en el desarrollo de las matemáticas lo suficientemente importantes como para generar por si mismos mucha investigación sobre algoritmos especializados en su solución. Una serie de algoritmos diseñados para resolver otros tipos de problemas de optimización constituyen casos particulares de la más amplia técnica de la programación lineal. Históricamente, las ideas de programación lineal han inspirado muchos de los conceptos centrales de la teoría de optimización tales como la dualidad, la descomposición y la importancia de la convexidad y sus generalizaciones. Del mismo modo, la programación lineal es muy usada en la microeconomía y la administración de empresas, ya sea para aumentar al máximo los ingresos o reducir al mínimo los costos de un sistema de producción. Algunos ejemplos son la mezcla de alimentos, la gestión de inventarios, la cartera y la gestión de las finanzas, la asignación de recursos humanos y recursos de máquinas, la planificación de campañas de publicidad, etc. Otros son:

¾

Optimización de la combinación de diámetros comerciales en una red ramificada de distribución de agua.

¾

Aprovechamiento óptimo de los recursos de una cuenca hidrográfica, para un año con afluencias caracterizadas por corresponder a una determinada frecuencia.

¾

Soporte para toma de decisión en tiempo real, para operación de un sistema de obras hidráulicas;

¾

Solución de problemas de transporte.

2.3 Maximización y minimización Muchos problemas de administración y economía están relacionados con la optimización (maximización o minimización) de una función sujeta a un sistema de igualdades o desigualdades. La función por optimizar es la función objetivo. Las funciones de ganancia y de costo son ejemplos

de funciones

objetivo. El sistema de igualdades o desigualdades a las que está sujeta la función objetivo reflejan las restricciones (por ejemplo, las limitaciones sobre recursos como materiales y mano de obra) impuestas a la solución (o soluciones) del problema. Los problemas de esta naturaleza se llaman problemas de programación matemática. En particular, aquellas

donde la función objetivo y las restricciones se

expresan como ecuaciones o desigualdades lineales se llaman problemas de programación lineal.

14

2.4 Métodos de solución de problemas de PL Existen muchos métodos para solucionar problemas de programación lineal (PL), entre los cuales se pueden mencionar los siguientes:

¾

El método gráfico

¾

El método analítico

¾

El método simplex

2.5 El método gráfico Para poder solucionar un problema de PL mediante el método gráfico se realiza el siguiente procedimiento: 1.- Se establece la función objetivo, la cual se denominará con el identificador Z 2.- Se establecen las ecuaciones a las cuales estará sujeto el modelo, también se le conoce como funciones de restricción 3.- Una vez que se tienen las ecuaciones establecidas, para cada una de ellas se establecen valores de X=0 y Y=0, con el fin de obtener puntos que permitan establecer una recta en el plano. Dependiendo del número de ecuaciones será el número de líneas que se generarán. 4.- se grafican los puntos obtenidos para obtener las líneas que representen cada gráfica 5.- verificar los puntos X,Y donde se intersecan las líneas para poder establecer valores a evaluar 6.- una vez obtenidos los puntos X,Y se sustituyen en la función objetivo Z para establecer una solución óptima Ejemplo:

Un granjero tiene 480 hectáreas en la que se puede sembrar ya sea Maiz: trigo o maíz. El calcula que tiene 800 horas de trabajo disponible Utilidad: $40 por hrs. durante la estación crucial del verano. Dados márgenes de utilidad Trabajo: 2hs por hrs. y los requerimientos laborales mostrados a la derecha, ¿Cuántas Trigo: hectáreas

de

cada

uno

debe

plantar

utilidad?¿Cuál es ésta utilidad máxima?

para

maximizar

su Utilidad: $30 por hrs. Trabajo: 1hs por hrs.

Solución:

15

Como primer paso para la formulación matemática de este problema, se tabula la información dada. Si llamamos x a las hectáreas de maíz e y a las hectáreas de trigo. Entonces la ganancia total Z, en pesos, está dada por: Z=40x+30y Que es la función objetivo por maximizar.

Maíz

Trigo

Elementos disponibles

Horas

2

1

800

Hectáreas

1

1

480

La cantidad total de tiempo par hectáreas para sembrar maíz y trigo está dada por 2x+y horas que no debe exceder las 800 horas disponibles para el trabajo. Así se tiene la ecuación: 2X+Y=800 En forma análoga, la cantidad de hectáreas disponibles está dada por x+y, y ésta no puede exceder las hectáreas disponibles para el trabajo, lo que conduce a la desigualdad. X+Y=480 Por lo tanto, el problema en cuestión consiste en maximizar la función objetivo Z=40x+30y Sujeta a las siguientes restricciones: 2x+y=800 x+y=480 A continuación se establecen valores de X=0 y Y=0 para las ecuaciones, por lo tanto: Para la ecuación 2x+y=800: Si X=0 por despeje se obtiene para Y un valor de 800, obteniendo el punto (0,800) Si Y=0 por despeje se obtiene para X un valor de 400, obteniendo el punto (400,0) Para la ecuación x+y=480: Si X=0 por despeje se obtiene para Y un valor de 480, obteniendo el punto (0,480) Si Y=0 por despeje se obtiene para X un valor de 480, obteniendo el punto (480,0)

16

Estos datos se grafican en un plano X,Y, resultando lo siguiente:

Como es un problema de maximización, la región factible de presentar una solución es la que aparece en color amarillo. Y dentro de esta región, el punto donde se cruzan las líneas es el punto (320,160), Por lo que se puede responder a la primera pregunta de la siguiente manera: El granjero necesita sembrar 320 hectáreas de maíz y 160 de trigo Por lo que se asume que este es el punto óptimo del problema. Con estos datos, se sustituyen en la función objetivo Z, para obtener la utilidad máxima del granjero. Z=40x+30y Sustituyendo: Z=40(320)+30(160) Z=12800+4800 Z=17600 Por lo tanto, la utilidad máxima que puede lograr el granjero son $17,600.00

17

2.6 El método analítico Para poder solucionar un problema de PL mediante el método analìtico se realiza el siguiente procedimiento: 1.- Se establece la función objetivo, la cual se denominará con el identificador Z 2.- Se establecen las ecuaciones a las cuales estará sujeto el modelo, también se le conoce como funciones de restricción 3.- Una vez que se tienen las ecuaciones establecidas, se elige una de las variables y mediante el método de adición se elimina temporalmente una de ellas para poder obtener por despeje el valor de la variable restante. 4.- se sustituye el valor de la variable conocida en cualquiera de las ecuaciones para obtener el valor que todavía no se conoce 5.- una vez obtenidos los puntos X,Y se sustituyen en la función objetivo Z para establecer una solución óptima Ejemplo: Tomando el mismo ejemplo del granjero se tienen los siguientes datos: Maximizar la función objetivo Z=40x+30y Sujeta a las siguientes restricciones: 2x+y=800 x+y=480 Se elimina temporalmente una de las variables

18

Una vez conocido el valor de una de las variables (en este caso Y), se sustituye en cualquiera de las ecuaciones para obtener el valor de la otra variable(X). X+Y=480 Sustituyendo: X+160=480 Despejando: X=480-160 X=320 Por lo tanto, los valores encontrados son X=320 Y=160

2.7 El método simplex

En la teoría de optimización, el algoritmo símplex, descubierto por el matemático norteamericano George Bernard Dantzig en 1947, es una técnica popular para dar soluciones numéricas del problema de la programación lineal. Un método sin relación, pero llamado de manera similar, es el método Nelder-Mead o método símplex cuesta abajo, debido a Nelder y Mead, que es un método numérico para optimización de problemas libres multidimensionales, perteneciente a la clase más general de algoritmos de búsqueda. El que permite encontrar una solución óptima en un problema de maximización o minimización. El método del simplex se utiliza, sobre todo, para resolver problemas de programación lineal en los que intervienen tres o más variables. El álgebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de ecuaciones lineales constituyen la base del método simplex Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución. Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.

19

El método del simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta. Ejemplo:

Vamos a resolver mediante el método del simplex el siguiente problema:

Se consideran las siguientes fases: 1. Convertir las desigualdades en igualdades Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:

2. Igualar la función objetivo a cero

3. Escribir la tabla inicial simplex En las columnas aparecerán todas las variables del problema y, en las filas, los coeficientes de las igualdades obtenidas, una fila para cada restricción y la última fila con los coeficientes de la función objetivo:

20

4. Encontrar la variable de decisión que entra en la base y la variable de holgura que sale de la base ¾

Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor (en valor absoluto). En nuestro caso, la variable x de coeficiente - 3. Si existiesen dos o más coeficientes iguales que cumplan la condición anterior, entonces se elige uno cualquiera de ellos. Si en la última fila no existiese ningún coeficiente negativo, significa que se ha alcanzado la solución óptima. Por tanto, lo que va a determinar el final del proceso de aplicación del método del simplex, es que en la última fila no haya elementos negativos. La columna de la variable que entra en la base se llama columna pivote (En color verde).

¾

Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre

que

estos

últimos

sean

mayores

que

cero.

En

nuestro

caso:

18/2 [=9] , 42/2 [=21] y 24/3 [=8] Si hubiese algún elemento menor o igual que cero no se hace dicho cociente. En el caso de que todos los elementos fuesen menores o iguales a cero, entonces tendríamos una solución no acotada y no se puede seguir. El término de la columna pivote que en la división anterior dé lugar al menor cociente positivo, el 3, ya 8 es el menor, indica la fila de la variable de holgura que sale de la base, d. Esta fila se llama fila pivote (En color verde). Si al calcular los cocientes, dos o más son iguales, indica que cualquiera de las variables correspondientes pueden salir de la base.

21

¾

En la intersección de la fila pivote y columna pivote tenemos el elemento pivote operacional, 3.

5. Encontrar los coeficientes de la nueva tabla. Los nuevos coeficientes de x se obtienen dividiendo todos los coeficientes de la fila d por el pivote operacional, 3, que es el que hay que convertir en 1. A continuación mediante la reducción gaussiana hacemos ceros los restantes términos de su columna, con lo que obtenemos los nuevos coeficientes de las otras filas incluyendo los de la función objetivo Z. También se puede hacer utilizando el siguiente esquema:

Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso: ¾

La variable que entra en la base es y, por ser la variable que corresponde al coeficiente -1

¾

Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote: 2:1/3 [=6] , 26:7/3 [=78/7] y 8:1/3 [=8] y como el menor cociente positivo es 6, tenemos que la variable de holgura que sale es h.

22

¾

El elemento pivote, que ahora hay que hacer 1, es 1/3.

Operando de forma análoga a la anterior obtenemos la tabla:

Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:

¾

La variable que entra en la base es d, por ser la variable que corresponde al coeficiente -1

¾

Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote: 6/(-2) [=-3] , 12/4 [=3], y 6:1 [=6] y como el menor cociente positivo es 3, tenemos que la variable de holgura que sale es s.

¾

El elemento pivote, que ahora hay que hacer 1, es 4.

Obtenemos la tabla:

Como todos los coeficientes de la fila de la función objetivo son positivos, hemos llegado a la solución óptima.

23

Los solución óptima viene dada por el valor de Z en la columna de los valores solución, en nuestro caso: 33. En la misma columna se puede observar el vértice donde se alcanza, observando las filas correspondientes a las variables de decisión que han entrado en la base: D(3,12) Nota:

¾

Si en el problema de maximizar apareciesen como restricciones inecuaciones de la forma: ax + by by

¾

c; multiplicándolas por - 1 se transforman en inecuaciones de la forma - ax -

- c y estamos en el caso anterior

Si en lugar de maximizar se trata de un problema de minimizar se sigue el mismo proceso, pero cambiando el sentido del criterio, es decir, para entrar en la base se elige la variable cuyo valor, en la fila de la función objetivo, sea el mayor de los positivos y se finalizan las iteraciones cuando todos los coeficientes de la fila de la función objetivo son negativos

24

Parte 3: PERT y CPM La problemática de la planeación de proyectos no ha sido una problemática reciente, si no que desde tiempos pasados nuestros antepasados han enfrentado emprendimientos de gran envergadura que significaron una problemática desde el punto de la planificación, es por ello que han surgido métodos de planificación como el PERT y el CPM.

3.1 Antecedentes del PERT y CPM Actualmente se han logrado perfeccionar herramientas que permiten a los administradores de dichos proyectos, realizar una labor más eficiente permitiendo una óptima aplicación de los recursos en las mismas y logrando una maximización de los mismos. Admitiendo que la ejecución de un proyecto o elaboración se puede subdividir en planear, programar y controlar, y hablando de manera clásica, podemos considerar las técnicas PERT (Program Evaluation aand review Technique) y el CPM (Critical Path Method,) que son los mas usuales para un primer cometido. Dos son los orígenes del método del camino crítico: el método PERT (Program Evaluation and Review Technique) desarrollo por la Armada de los Estados Unidos de América, en 1957, para controlar los tiempos de ejecución de las diversas actividades integrantes de los proyectos espaciales, por la necesidad de terminar cada una de ellas dentro de los intervalos de tiempo disponibles. Fue utilizado originalmente por el control de tiempos del proyecto Polaris y actualmente se utiliza en todo el programa espacial. El método CPM (Crítical Path Method), el segundo origen del método actual, fue desarrollado también en 1957 en los Estados Unidos de América, por un centro de investigación de operaciones para la firma Dupont y Remington Rand, buscando el control y la optimización de los costos de operación mediante la planeación adecuada de las actividades componentes del proyecto. Ambos métodos aportaron los elementos administrativos necesarios para formar el método del camino crítico actual, utilizando el control de los tiempos de ejecución y los costos de operación, para buscar que el proyecto total sea ejecutado en el menor tiempo y al menor costo posible. En general estas técnicas resultan útiles para una gran variedad de proyectos que contemplen:

¾

Investigación y desarrollo de nuevos productos y procesos.

25

¾

Construcción de plantas, edificios, y carreteras.

¾

Diseño de equipo grande y complejo.

¾

Diseño e instalación de sistemas nuevos.

¾

Diseño y control de epidemias,

¾

y otras múltiples aplicaciones en las cuales se requiera una planificación adecuada.

En los proyectos como estos, los administradores deben programas, coordinar las diversas tareas o actividades a desarrollar un proyecto, las cuales no necesariamente son secuenciales, y aun en este caso estas actividades son interdependientes. Si bien es cierto que, algunas actividades en paralelo que originan una tercera. Las preguntas esenciales de la elaboración de un proyecto comprenden: ¾

Cual es el tiempo que se requiere para terminar el proyecto.

¾

Cuales son las fechas programadas de inicio y finalización del proyecto.

¾

Que actividades son críticas y deben terminarse exactamente según lo programado para poder mantener el proyecto según el cronograma.

¾

Cuales actividades pueden ser demoradas sin afectar el tiempo de terminación del proyecto.

3.2 La terminología usada en PERT y CPM Para lograr una adecuada comprensión del tema a desarrollar se consideró prioritario desarrollar un glosario que sirva como guía para comprender la terminología empleada.

¾

PERT. Las traducción de las siglas en inglés significan: técnica de revisión y evaluación de programas, es una técnica de redes desarrollado en la década de los 50, utilizada para programar y controlar programas a realizar. Cuando hay un grado extremo de incertidumbre y cuando el control sobre el tiempo es más importante sobre el control del costo, PERT es mejor opción que CPM.

¾

CPM. La traducción de las siglas en inglés significan: método del camino crítico, es uno de los sistemas que siguen los principios de redes, que fue desarrollado en 1957 y es utilizado para planear y controlar proyectos, añadiendo el concepto de costo al formato PERT. Cuando los tiempos y costos se pueden estimar relativamente bien, el CPM puede ser superior a PERT.

¾

Actividad. Es un trabajo que se debe llevar a cabo como parte de un proyecto, es simbolizado mediante una rama de la red de PERT.

¾

Lista de actividades. Es una lista cuidadosa y ordenada donde se recopilan todas las diferentes actividades que intervienen en la realización de un proyecto.

¾

Evento. Se dice que se realiza un evento, cuando todas las actividades que llegan a un mismo nodo han sido terminadas. Son los círculos numerados que forman parte del diagrama de red y representan el principio y el fin de las actividades que intervienen en el proyecto. 26

¾

Rama. Son las flechas que forman Parte del diagrama de red y significan las actividades en el proyecto.

¾

Ruta crítica o camino crítico. Camino es una secuencia de actividades conectadas, que conduce del principio del proyecto al final del mismo, por lo que aquel camino que requiera el mayor trabajo, es decir, el camino más largo dentro de la red, viene siendo la ruta crítica o el camino crítico de la red del proyecto.

¾

Predecesor Inmediato. Es una actividad que debe Preceder (estar antes) inmediatamente a una actividad dada en un proyecto, también nombradas prioridades inmediatas.

¾

Diagrama de red. Es una red de círculos numerados y conectados con flechas, donde se muestran todas las actividades que intervienen en un determinado proyecto y la relación de prioridad entre las actividades en la red.

¾

Actividad ficticia. Actividades imaginarias que existen dentro del diagrama de red, sólo con el Propósito de establecer las relaciones de precedencia y no se les asigna tiempo alguno, es decir, que la actividad ficticia Permite dibujar redes con las relaciones de Precedencia apropiadas, se representa por medio de una línea punteada.

¾

Holgura. Es el tiempo libre en la red, es decir, la cantidad de tiempo que puede demorar una actividad sin afectar la fecha de terminación del, proyecto total.

¾

Distribución beta. Distribución utilizada para la estimación del tiempo de actividad esperado en el PERT, esta estimación se basa en el supuesto de que el tiempo de la actividad es una variable aleatoria cuya Probabilidad tiene una distribución beta unimodal.

¾

Tiempo optimista. Es el tiempo mínimo o más corto posible en el cual es probable que sea terminada una actividad si todo marcha a la Perfección, utilizado en el PERT y simbolizado con a.

¾

Tiempo más probable. Es el tiempo que esta actividad sea más probable que tome sí se repitiera una y otra vez, en otras palabras, es el tiempo normal que se necesita en circunstancias ordinarias, utilizado en el PERT y simbolizado con m.

¾

Tiempo pesimista. Es el tiempo máximo o más largo posible en el cual es probable sea terminada una actividad bajo las condiciones más desfavorables, utilizado en el PERT y simbolizado con b.

¾

Tiempo esperado para una actividad. Es el tiempo calculado en el PERT usando el promedio ponderado (a+4m+b)/6.

¾

Tiempo normal. Es el tiempo en el CPM requerido para terminar una actividad si esta se realiza en forma normal. Es el tiempo máximo para terminar una actividad con el uso mínimo de recurso, el tiempo normal se aproxima al tiempo estimado probable en PERT.

¾

Tiempo acelerado. Tiempo en el CPM que sería requerido si no se evita costo alguno con tal de reducir el tiempo del proyecto. Tiempo mínimo posible para terminar una actividad con la concentración máxima de recursos.

27

3.3 Metodología para el trazo de la red Para aplicar CPM o PERT se requiere conocer la lista de actividades que incluye un proyecto. Se considera que el proyecto esta terminado cuando todas las actividades han sido completadas. Para cada actividad, puede existir un conjunto de actividades predecesoras que deben ser completadas antes de que comience la nueva actividad. Se construye una malla o red del proyecto para graficar las relaciones de precedencia entre las actividades. En dicha representación grafica, cada actividad es representada como un arco y cada nodo ilustra la culminación de una o varias actividades. Consideremos un proyecto que consta de solo dos actividades A y B. Supongamos que la actividad A es predecesora de la actividad B. La representación grafica de este proyecto se muestra en la figura. Así, el nodo 2 representa la culminación de la actividad A y el comienzo de la actividad B.

A 1

B 2

3

FIg.1.1 Si suponemos ahora que las actividades A y B deben ser terminadas antes que una actividad C pueda comenzar, la malla del proyecto queda como se muestra en la figura2. En este caso, el nodo representa que las actividades A y B se han terminado, además del inicio de la actividad C. Si la actividad A fuera predecesora de las actividades B y C, la red quedara como se muestra en la figura 3.

Dado un conjunto de actividades y sus relaciones de predecisión, se puede construir una representación grafica de acuerdo a las siguientes reglas:

¾

El nodo 1 representa el inicio del proyecto. Por lo tanto, las actividades que parten del nodo 1 no pueden tener predecesoras.

¾

El nodo Terminal o final del proyecto debe representar el término de todas las actividades incluidas en la red.

28

¾

Una actividad no puede ser representada por más de un arco en la red.

¾

Dos nodos deben estar conectados por a lo mas un arco.

Para no violar las reglas 3 y 4, a veces es necesario introducir una actividad artificial o dummy que posee tiempo de duración nulo. Por ejemplo, supongamos que las actividades A y B son predecesoras de la actividad C y además comienzan al mismo tiempo. En este caso, una primera representación podría ser la indicada en la figura 2.4. Sin embargo, la red de la figura 3 viola la regla 4. Para corregir este problema, se introduce una actividad artificial indicada con un arco segmentado en la figura La red de la figura 4 refleja el hecho de que la actividad C tiene como predecesoras a A y B, pero sin violar la regla 4. En otros casos, se deben agregar actividades artificiales para no violar la regla 3. A C 1

2

B Fig. 3 A y B predecesoras de C A

C 2

1

C

Dummy 3

Fig. 4 Incorporación de una actividad artificial.

29

• Fig. 5

Ejemplo: 1 Actividad A B C D E F

2 Antecedente A,B A,B D C,E

3 T. Optimo (o)

4 T. Normal (m) 2 5 3 1 8 9

6 9 8 7 10 12

5 T. Pesimo (p)

7 K. Normal 10 13 13 13 12 15

8 K. Acelerado 10 20 15 20 20 50

50 100 30 200 100 200

Primeramente se prepara la grafica de actividades siguiendo la secuencia lógica ya explicada, respetando las actividades antecedentes.

30

Como segundo paso se procede a determinar el tiempo esperado Te mediante la fórmula:

Te = 1 Actividad A B C D E F

2 Antecedente A,B A,B D C,E

3 T. Optimo (o)

o + 4m + p 6

4 T. Normal (m) 2 5 3 1 8 9

6 9 8 7 10 12

5 T. Pesimo (p)

6 T. Esperado(Te) 10 13 13 13 12 15

7 K. Normal

8 K. Acelerado 10 20 15 20 20 50

50 100 30 200 100 200

El tercer paso consiste en calcular el costo de acelerar la actividad un día, esto se determina mediante la formula:

K= 1 Actividad A B C D E F

2 Antecedente A,B A,B D C,E

(K .acelerado − K .normal ) (o − m )

3 4 5 7 8 9 T. Optimo (o) T. Normal (m) T. Pesimo (p) K. Normal K. Acelerado K 2 6 10 10 50 10 5 9 13 20 100 20 3 8 13 15 30 3 1 7 13 20 200 30 8 10 12 20 100 40 9 12 15 50 200 50

Como tercer paso para de la ruta crítica se calcula los tiempos mas tempranos para cada actividad se comienza dejando el tiempo como cero en el nodo inicial. Luego, se calcula el intervalo de tiempo que transcurre entre el inicio y las actividades inmediatas al comienzo del proyecto. Debido a que la actividad artificial no tiene duración, el tiempo acumulado al nodo 3 para que sean terminadas todas las actividades predecesoras a dicho nodo corresponde a 9 días. En otras palabras, el tiempo más temprano para el nodo 3 es 9 días. Luego, las actividades que comienzan en el nodo 3 no pueden comenzar antes de 9.

31

A continuación, es posible completar el intervalo de tiempo de desarrollo para la actividad Finalmente, el tiempo mas temprano para el nodo 5 es de 26 días, por lo que la actividad F solo puede comenzar en dicho instante. Los intervalos de tiempo más temprano para todas las actividades del proyecto. A partir de esta figura, se puede concluir que la duración mínima del proyecto es de 38 días, cantidad que corresponde al camino mas largo para llegar del nodo inicial 1 al nodo al 6.

Como segunda etapa se procede a calcular los tiempos mas tarde para cada nodo. La idea consiste en determinar cuanto es posible retardar el inicio de cada actividad sin afectar la duración total del proyecto. Para ello se comienza desde el nodo final. En este caso, dado que existe una única actividad que llega a dicho nodo no es posible retardarla sin afectar la duración del proyecto. La figura muestra el intervalo de tiempo mas tarde para la última actividad en paréntesis cuadrado. Las actividades que llegan al nodo 5 terminan a mas tardar en el día 26, por lo tanto, es posible retardar la actividad C en 26 -17 = 9 días. Se incorpora los intervalos de duración de tiempo mas tarde a la malla en la figura. El nodo 4 tiene como tiempo mas tarde 26, por lo que no es factible retardar la actividad D. De esta forma, el nodo 3 tiene como tiempo mas tarde 9 días, por lo tanto las actividades deben llegar a más tardar el día 9. Como la actividad artificial no tiene duración, La actividad B no puede ser retardada. La actividad A puede ser retardada en 9-6= 3 días.

32

Una actividad crítica es una actividad que no puede ser retardada sin afectar la duración total del proyecto. En otras palabras, en el tiempo más temprano y el tiempo mas tarde de inicio de la actividad son idénticos. Un camino desde el nodo inicial al final constituido solo por actividades críticas se denomina ruta crítica. Es decir, constituye el camino que no puede ser retrasado sin afectar la duración del proyecto, o bien, la ruta mas larga entre los nodos inicial y final. De acuerdo a la definiciones anteriores, la ruta critica del proyecto corresponde a las actividades Bdummy- D-E-F, las cuales han sido marcadas con una línea mas oscura

Se continúa copiando los tiempos determinados en la matriz siguiendo el siguiente criterio: ¾

Los valores entre paréntesis corresponden a (EF. LF)

¾

Los valores entre corchetes corresponden a [ES ,LS]

1 Actividad A B C D E F

2 3 4 5 7 8 9 10 11 12 13 Antecedente T. Optimo (o) T. Normal (m) T. Pesimo (p) K. Normal K. Acelerado K ES LS EF LF 2 6 10 10 50 10 0 6 3 9 5 9 13 20 100 20 0 9 0 9 A,B 3 8 13 15 30 3 9 17 18 26 A,B 1 7 13 20 200 30 9 16 9 16 D 8 10 12 20 100 40 16 26 16 26 C,E 9 12 15 50 200 50 26 38 26 38

El cuarto paso se determina las holguras (s) que nos determinan el tiempo que puede retrasarse o adelantarse una actividad que esta fuera de la ruta critica, mediante la formula:

s = LF − LS y s = EF − ES

33

1 Actividad A B C D E F

2 3 4 5 7 8 9 10 11 12 13 14 Antecedente T. Optimo (o) T. Normal (m) T. Pesimo (p) K. Normal K. Acelerado K ES LS EF LF s 2 6 10 10 50 10 0 6 3 9 3 5 9 13 20 100 20 0 9 0 9 0 A,B 3 8 13 15 30 3 9 17 18 26 9 A,B 1 7 13 20 200 30 9 16 9 16 0 D 8 10 12 20 100 40 16 26 16 26 0 C,E 9 12 15 50 200 50 26 38 26 38 0

Como quinto paso se determinan los días a comprimir el proyecto, este valor nos indica la posibilidad de acelerar las actividades, en función de los tiempos óptimos y tiempos medios mediante la formula:

DC = o − m 1 Actividad A B C D E F

2 3 4 5 7 8 9 10 11 12 13 14 15 Antecedente T. Optimo (o) T. Normal (m) T. Pesimo (p) K. Normal K. Acelerado K ES LS EF LF s Dc 2 6 10 10 50 10 0 6 3 9 3 4 5 9 13 20 100 20 0 9 0 9 0 4 A,B 3 8 13 15 30 3 9 17 18 26 9 5 A,B 1 7 13 20 200 30 9 16 9 16 0 6 D 8 10 12 20 100 40 16 26 16 26 0 2 C,E 9 12 15 50 200 50 26 38 26 38 0 3

La desviación estándar (columna 16) que representa la probabilidad de retraso o adelanto en promedio, es igual al tiempo pésimo menos el tiempo óptimo dividido entre 6

1

2

Activ idad Antecedente A B C D E F

A,B A,B D C,E

3

4

5

7

T. Optimo (o) T. Normal (m) T. Pesimo (p) 2 5 3 1 8 9

6 9 8 7 10 12

10 13 13 13 12 15

Te 6 9 8 7 10 12

8

9

K. Normal K. Acelerado K 10 20 15 20 20 50

50 100 30 200 100 200

10 ES

10 20 3 30 40 50

0 0 9 9 16 26

11 LS 6 9 17 16 26 38

12 EF 3 0 18 9 16 26

13 LF 9 9 26 16 26 38

14

15

s

16

DS

Dc 3 0 9 0 0 0

4 4 5 6 2 3

1,3 1,3 1,7 2,0 0,7 1,0

Por definición representa el 68% de seguridad. Si se desea una seguridad mayor en el resultado, de 95% se tomará el equivalente a dos desviaciones estándar y si se desea una seguridad del 99% en el tiempo de duración de la actividad se tomarán tres desviaciones estándar. De esta manera, podemos observar que la actividad F tiene un tiempo estándar de 12 y una desviación estándar de 1 días. Esto significa que se podrá ejecutar entre 13 y 11 días con el 68% de seguridad; entre 14y 10 días con el 95% de seguridad; y entre 15 y 9 días con el 99% de seguridad. Mientras mayor sea el intervalo que se mencione para la ejecución, mayor será la seguridad de acertar. La desviación estándar del proyecto es igual a la suma de las desviaciones estándar del camino crítico: Esta desviación será la probabilidad de retraso de todo el proyecto. Por supuesto es la misma probabilidad de adelanto del mismo. 34

En el caso anterior el camino critico esta dado por: 9

7

10

12

1.3

2

0.7

1

Esto significa que el proyecto se va a ejecutar entre

38 ± 5 O sea entre 38 y 33 días, con el 68% de seguridad. La desviación estándar puede señalarse como tolerancia en el desarrollo del proyecto.

3.4 Crashing En muchas ocasiones es necesario completar un proyecto en un periodo determinado que puede ser inferior a la duración de la ruta crítica. En este caso se puede asignar recursos adicionales a algunas actividades para acelerarlas y se habla de un proyecto con crashing. El hecho de incorporar recursos adicionales a la ejecución de una actividad involucra un aumento de los costos y por ende el problema de aplicar crashing a un proyecto se puede asociar a un problema de minimización de costos para terminar un proyecto en un determinado periodo La idea es ir acelerando las actividades de la ruta crítica de tal forma de minimizar costos poniendo atención a los márgenes en que cada actividad se mantiene como critica. En el ejemplo, la actividad de menor costo de aceleración es la C. Sin embargo dado que C no pertenece a la ruta crítica no se consigue disminuir la duración del proyecto acelerándola. Lo mismo ocurre con la actividad A, que es la que le sigue en costos. La próxima actividad de menor costo de aceleración es la B, con kB = 20. En este caso, como la actividad es crítica conviene acelerarla dentro de los rangos permitidos y cuidando que siga siendo critica. El límite de aceleración por enunciado es 4, mientras que el límite para que siga siendo crítica viene dado por la duración de la actividad A. Luego, B puede ser acelerada en 9- 6 = 3 < 4 a un costo de 20 x 3 = 60. La nueva red se muestra en la figura, con una duración total de

38 - 3 = 35 días

35

Como se observa en la figura, la actividad A forma parte también de una ruta crítica. Luego, cualquier nueva aceleración de la actividad B debe involucrar también a la actividad A para no retardar la duración del proyecto, de forma que se obtiene un costo unitario conjunto de 10 + 20 = 30. Dicho costo coincide con el costo de la otra actividad factible de acelerar (D), luego se puede escoger en acelerar D o A y B simultáneamente. La diferencia entre el tiempo más temprano y más tarde de la actividad C es 9 días, por lo tanto el valor máximo de aceleración para D queda controlado por la restricción de 6 días. Como la actividad B ya ha sido acelerada en 3 días, solo es posible acelerarla 1 días más. Como interesa llegar lo mas pronto posible a los 25 días requeridos de duración del proyecto se escoge D, obteniendo como nueva duración del proyecto 35- 5 = 30 días. El costo adicional es de 5 x 30 = 150, luego el costo total acumulado es de 60 + 150 = 210. La nueva condición de la malla se muestra en la figura. Como las rutas criticas no se ven alteradas, ahora tiene sentido acelerar las actividades E, F o

36

A y B simultáneamente. En este caso tiene el menor costo intervenir las actividades A y B, a un valor unitario de 10 + 20 = 30. Como B ya fue reducida en 3 días, solo se puede disminuir 1 día más de acuerdo a las restricciones. Con ello, la duración del proyecto queda en 30-1 = 29, días con un costo total acumulado de 60+150+30. Imponiendo el cambio, se obtiene

Se concluye que el costo de acelerar el proyecto a 29 días es de 135+60+150+30=375

[9,17] (5,13) [0,5] (0,5)

[17,29] (17,29)

C

F

3

5

A [0,5] (0,5)

Dummy

1

B 2

[5,7] (5,7)

6

[7,17] (7,17)

D

E

4

37

Parte 4: Ejercicios Con la finalidad de que el alumno aplique las técnicas vistas en clase, se sugieren los siguientes ejercicios:

4.1 Programación lineal Realice los siguientes ejercicios aplicando el método gráfico, y compruebe utilizando el método analítico 1.- Un herrero con 80 kgs. de acero y 120 kgs. de aluminio quiere hacer bicicletas de paseo y de montaña que quiere vender, respectivamente a 20.000 y 15.000 pesos cada una para sacar el máximo beneficio. Para la de paseo empleará 1 kg. De acero y 3 kgs de aluminio, y para la de montaña 2 kgs. de ambos metales. ¿Cuántas bicicletas de paseo y de montaña venderá? Sean las variables de decisión: x= n: de bicicletas de paseo vendidas. y= n: de bicicletas de montaña vendidas. Tabla de material empleado:

Paseo Montaña

Acero 1 2

Aluminio 3 2

2.- Un autobús México-Cancún ofrece plazas para fumadores al precio de 10.000 pesos y a no fumadores al precio de 6.000 pesos. Al no fumador se le deja llevar 5 kgs. de peso y al fumador 2 kgs. Si el autobús tiene 90 plazas y admite un equipaje de hasta 300 kg. ¿Cuál ha de ser la oferta de plazas de la compañía para cada tipo de pasajeros, con la finalidad de optimizara el beneficio? Sean las variables de decisión: x= n: de plazas de fumadores. y= n: de plazas de no fumadores. 3.- Un comerciante acude al mercado popular a comprar naranjas con 50,000 pesos. Le ofrecen dos tipos de naranjas: las de tipo A a 50 pesos el kg. y las de tipo B a 80 pesos el kg. Sabiendo que sólo dispone de su camioneta con espacio para transportar 700 kg. de naranjas como máximo y que piensa vender el kg. de naranjas tipo A a 58 pesos. y el kg. de tipo B a 90 pesos, contestar justificando las respuestas:

38

¿Cuántos kg. de naranjas de cada tipo deberá comprar para obtener máximo beneficio? ¿Cuál será ese beneficio máximo? Sean las variables de decisión: x= kg. de naranjas tipo A comprados. y= kg. de naranjas tipo B comprados.

4.2 Método simplex Obtenga los valores óptimos de los siguientes sistemas de ecuaciones utilizando el método simplex 1.-

2.-

SOLUCIONES A LOS PROBLEMAS DE PROGRAMACION LINEAL 1.- Solución al problema del herrero Función objetivo: f(x, y)= 20.000x+15.000y

máxima.

Restricciones: 3X+2Y=120 X+2Y=80

39

Zona de soluciones factibles:

Ha de vender 20 bicicletas de paseo y 30 de montaña para obtener un beneficio máximo de 850.000 pesos. 2.- Solución al problema del camión La Función objetivo: f(x, y)=10.000x+6.000y máxima Restricciones: X+Y=90 2X+5Y=300 Zona de soluciones factibles:

40

Vértices:

Ha de vender 50 plazas para fumadores y 40 para no fumadores y así obtener un beneficio máximo de 740000 pesos. 3.- Solución al problema de las naranjas Sean las variables de decisión: x= kg. de naranjas tipo A comprados. y= kg. de naranjas tipo B comprados. La función objetivo que da el beneficio es: Z=8x+10y Sujeto a: 5x+8y=5000 X+y=700 La zona de soluciones factibles es:

41

Ha de comprar 200 kgs. de naranjas A y 500 kgs. de naranjas B para obtener un beneficio máximo de 6.600 pesos

42

UNIVERSIDAD PRIVADA DEL SUR DE MEXICO

ANTOLOGIA Investigación De Operaciones I

Ing. Juan Mendoza Díaz

Mayo de 2009

43