Redes

Teoría de redes en I.O

La modelación de redes permite la resolución de múltiples problemas de programación matemática mediante la implementación de algoritmos especiales creados para tal fin, conocidos como Algoritmos de optimización de redes. 

Dentro de los problemas más comúnmente resueltos mediante la modelación de redes se encuentran los ya vistos modelos de transporte, transbordo además de los muy conocidos modelos de determinación de cronograma de actividades para proyectos como lo son el PERT y el CPM.

Para hacer mas flexible el tema, debemos recalcar los conceptos básicos que como tal se ven en dicho tema.

- Gráfica: Una gráfica es una serie de puntos llamados nodos que van unidos por unas líneas llamadas ramales o arcos.

- Red: Una red es una gráfica que presenta algún tipo de flujo en sus ramales. Por ejemplo una gráfica cuyo flujo en sus ramales sea la electricidad es una red eléctrica. En las redes se usa una simbología específica para denotar su tamaño y elementos que la constituyen, dicha notación es la (N, A) donde N representa el número de nodos que contiene la red y A representa el número de arcos o ramales.

- Cadena: Una cadena corresponde a una serie de elementos ramales que van de un nodo a otro. En el siguiente caso se resalta una cadena que va desde el nodo 1 hasta el nodo 7 y que se compone por los elementos [1-4, 4-7].

- Ruta: Una ruta corresponde a los nodos que constituyen una cadena, en el siguiente caso (1, 4, 7)

Ciclo: Un ciclo corresponde a la cadena que une a un nodo con sigo mismo, en el siguiente ejemplo el ciclo está compuesto por la cadena [4-2, 2-5, 5-7, 7-4].

- Ramal orientado: Un ramal o arco orientado es aquel que tiene un sentido determinado, es decir que posee un nodo fuente y un nodo destino.

- Gráfica orientada: Una gráfica orientada es aquella en la cual todos sus ramales se encuentran orientados.

- Árbol: Un árbol es una gráfica en la cual no existen ciclos, como el siguiente ejemplo.

- Árbol de expansión: Un árbol de expansión es aquel árbol que enlaza todos los nodos de la red, de igual manera no permite la existencia de ciclos.

- Nodo fuente: El nodo fuente es aquel nodo en el cual todos sus ramales se encuentran orientados hacia afuera.

- Nodo destino: El nodo destino es aquel nodo en el cual todos sus ramales se encuentran orientados hacia él.

Problemas fundamentales

• Problema del camino más corto
• Modelos del flujo máximo.
• Planeación, programación y control de proyecto de actividades.

En cada caso, una función es definida en los arcos de la red, pero el álgebra para la manipulación de estas medidas cuantitativas es diferente de modelo a modelo. Un concepto clave en los modelos de redes es que aunque la estructura de varias redes puede ser idéntica, el análisis de las relaciones funcionales definidas sobre la red pueden ser diferentes para modelos diferentes, de ahí que los resultados del análisis sean distintos.

Problema del camino más corto

El problema del camino más corto tiene como característica común el hecho de ser representado mediante una red en la cual se le asocia a cada arco o arista un determinado valor y la solución del problema planteado está dada por la búsqueda de un conjunto de secuencias o caminos de valor extremal, o sea, de valor mínimo o máximo.

Modelos del flujo máximo

Los modelos de flujo máximo en una red permiten determinar el flujo máximo posible entre dos nodos específicos de la red. El problema físico surge casi siempre que las mercancías, físicas o de otra clase, fluyen de una fuente u origen s a un terminal t.. Por tanto si en una red que describa tal situación existen puntos desde los cuales se envía el flujo (Ej. fábricas), puntos a los cuales se envía el flujo (ejemplo: almacenes, fábricas, etc.) y rutas por las cuales puede ser enviado el flujo que conecta los puntos de orígenes y puntos de destino pasando por puntos intermedios.

Planeación, programación y control de proyecto de actividades (redes)

Los modelos de redes de actividades sirve para planear, programar y controlar proyectos que constan de numerosos trabajos o tareas separadas que son llevadas a cabo por diversos departamentos, personas, etcétera. Con frecuencia, estos proyectos son tan grandes y/o tan complejos que no es posible que un administrador tenga en mente toda la información relativa al plan, al programa y al avance de su proyecto. En estas situaciones, las técnicas denominadas PERT (Program Evaluation and Review Technique) ( o sea, Técnica de evaluación y revisión de programa ) Y CPM ( Critical Path Method)(o sea, Método de la Ruta Crítica) han demostrado ser extremadamente valiosas para ayudar a los ejecutivos en la toma de decisiones relacionada con los proyectos.

Árbol de Decisión 

Es un método analítico que a través de una representación esquemática de las alternativas disponible facilita la toma de mejores decisiones, especialmente cuando existen riesgos, costos, beneficios y múltiples opciones. El nombre se deriva de la apariencia del modelo parecido a un árbol y su uso es amplio en el ámbito de la toma de decisiones bajo incertidumbre (Teoría de Decisiones) junto a otras herramientas como el Análisis del Punto de Equilibrio.

Los árboles de decisión son especialmente útiles cuando:

• Las alternativas o cursos de acción están bien definidas (por ejemplo: aceptar o rechazar una propuesta, aumentar o no la capacidad de producción, construir o no una nueva bodega, etc.)
• Las incertidumbres pueden ser cuantificadas (por ejemplo: probabilidad de éxito de una campaña publicitaria, probable efecto en ventas, probabilidad de pasar de etapas, etc.)
• Los objetivos están claros (por ejemplo: aumentar las ventas, maximizar utilidades, minimizar costos, etc.)

Método Esquina Noroeste

El método de la esquina es un método de programación lineal hecho a mano para encontrar una solución inicial factible del modelo, muy conocido por ser el método mas fácil al determinar una solución básica factible inicial, pero al mismo tiempo por ser el menos probable para dar una solución inicial acertada de bajo costo, debido a que ignora la magnitud relativa de los costos. es un proceso utilizado para resolver problemas de transporte o asignación, si bien es un método no exacto tiene la ventaja de poder resolver problemas manualmente y de una forma rápida, muy cercano al valor óptimo.

Paso 1. 

Seleccionar la celda de la esquina noroeste (esquina superior izquierda) para un envío.

Paso 2. 

Hacer el más grande envío como pueda en la celda de la esquina noroeste. Esta operación agotara completamente la disponibilidad de suministros en un origen a los requerimientos de demanda en un destino.

Paso 3. 

Corregir los números del suministro y requerimientos para reflejar lo que va quedando de suministro y requerimiento y regrese al paso 1.

Dando el resultado como en la imagen anterior.

Método de aproximación de Vogel

El método de aproximación de Vogel es un método heurístico de resolución de problemas de transporte capaz de alcanzar una solución básica no artificial de inicio, este modelo requiere de la realización de un número generalmente mayor de iteraciones que los demás métodos heurísticos existentes con este fin, sin embargo produce mejores resultados iniciales que los mismos.

Paso 1

Identificar en cada fila y columna los dos costos más bajos o menores, posteriormente se restan entre si dichos valores y a ese resultado lo llamamos “PENALIZACION”. (El valor de la penalización siempre es positivo dado que se resta el valor mayor menos el menor) .

Paso 2

Identificar la fila o columna con la mayor penalización, es decir que de la resta realizada en el "Paso 1" se debe escoger el número mayor de manera general. En caso de haber empate, se debe escoger arbitrariamente (a juicio personal).

Paso 3

La fila o columna de mayor penalización determinada en el paso anterior, debemos de identificar la celda con el menor costo, y en esta asignar la mayor cantidad posible que cumpla con las condiciones de demanda y disponibilidad. Una vez se realiza este paso una oferta o demanda quedará satisfecha por ende reducimos la tabla sombreando las columnas o filas satisfechas (en caso de haber empate solo se tachara 1, la restante o no satisfecha quedará con oferta o demanda igual a la diferencia.) en adelante repetir el proceso desde el paso 1.

Dado el resultado como en la imagen anterior.

Método de aproximación de Russell

Para cada renglón de origen i que queda bajo consideración, debe determinarse ui, su mayor costo unitario (cij) de lso que quedan en ese renglón. Para cada columna de destino que todavía está bajo consideración, se determina vj, su mayor costo unitario de los que hay en esa columna. Para cada variable xij que no haya sido seleccionada en estos renglones o columnas, se calcula: Δij = cij - ui - vj. Se elige la variable con el mayor valor negativo (en términos absolutos) de Δij. (Los empates se pueden romper arbitrariamente)

Paso 1

Determinar para cada fila y columna una medida de penalización restando los dos costos menores en filas y columnas.

Paso 2

Escoger la fila o columna con la mayor penalización, es decir que de la resta realizada en el "Paso 1" se debe escoger el número mayor. En caso de haber empate, se debe escoger arbitrariamente (a juicio personal).

Paso 3

De la fila o columna de mayor penalización determinada en el paso anterior debemos de escoger la celda con el menor costo, y en esta asignar la mayor cantidad posible de unidades. Una vez se realiza este paso una oferta o demanda quedará satisfecha por ende se tachará la fila o columna, en caso de empate solo se tachará 1, la restante quedará con oferta o demanda igual a cero (0).

PASO 4: DE CICLO Y EXCEPCIONES

- Si queda sin tachar exactamente una fila o columna con cero oferta o demanda, detenerse.

- Si queda sin tachar una fila o columna con oferta o demanda positiva, determine las variables básicas en la fila o columna con el método de costos mínimos, detenerse.

- Si todas las filas y columnas que no se tacharon tienen cero oferta y demanda, determine las variables básicas cero por el método del costo mínimo, detenerse.

- Si no se presenta ninguno de los casos anteriores vuelva al paso 1 hasta que las ofertas y las demandas se hayan agotado.

Para cada renglón de origen que queda bajo consideración, debe determinarse el mayor

costo unitario de los que quedan en ese renglón. Para cada columna de destino que

todavía está bajo consideración, se determina , el mayor costo unitario de los que hay en

esa columna. Para cada variable que no haya sido seleccionada en estos renglones o

columnas, se calcula se elige la variable con el mayor negativo

Para cada renglón de origen que queda bajo consideración, debe determinarse el mayor

costo unitario de los que quedan en ese renglón. Para cada columna de destino que

todavía está bajo consideración, se determina , el mayor costo unitario de los que hay en

esa columna. Para cada variable que no haya sido seleccionada en estos renglones o

columnas, se calcula se elige la variable con el mayor negativo.

Dando el resultado como en la imagen anterior.

Modelo de transporte

Modelo de transporte y sus variantes

Es un programa que básicamente trata sobre el transporte de artículos o mercancía desde su origen que en este caso es la fabrica hasta su destino que en este caso son a las bodegas o depósitos en los que se vende al cliente. 

El punto de este articulo es minimizar el costo de transporte y al mismo tiempo sea lo suficiente efectivo para tener buena demanda con el productor determinando la cantidad de unidades a vender o despachar. 

Así como puede ser aplicado para disminuir costo en el transporte también puede ser utilizado para el control de inventarios, programación de empleos y asignación de personal, es decir, tener control de recursos humanos.

Modelos no tradicionales de transporte

El programa  de modelo transporte no tiene limitación para las distintas áreas geográficas. Y en esta sección se explicaran 2 tipos de aplicaciones que se usan en el área control de producción e inventarios como también el mantenimiento de equipos. 

El algoritmo de transporte

Es algoritmo de transporte sigue exactamente los mismos pasos que el método símplex. Sin embargo, en lugar de usar la tabla símplex normal, se aprovecha la ventaja de la estructura especial del modelo de transporte para organizar los cálculos en una forma más cómoda. Se debe agregar que el algoritmo especial de transporte fue desarrollado por primera vez cuando la norma eran los cálculos a mano, y se necesitaba soluciones “con método abreviado”. Hoy contamos con poderosos programas de cómputo que pueden resolver un modelo de transporte de cualquier tamaño en forma de programación lineal.

Tipos de métodos:

• Método del costo mínimo: este método determina una mejor solución de inicio, porque se concentra en las rutas menos costosas. Se inicia asignando todo lo posible a la celda que tenga el mínimo costo unitario (los empates se rompen en forma arbitraria).

• Método de aproximación de Voge: Es una versión mejorada del método del costo mínimo, que en general produce mejores soluciones de inicio.

• Método de la esquina Noroeste: es un algoritmo heurístico capaz de solucionar problemas de transporte o distribución mediante la consecución de una solución básica inicial que satisfaga todas las restricciones existentes sin que esto implique que se alcance el costo óptimo total.

Investigación de operaciones

Es una herramienta metodológica cuantitativa que nos permite la asignación óptima de recursos escasos y en general apoyar de una forma eficiente el proceso de toma de decisiones. La Investigación de Operaciones hace uso de modelos matemáticos con el objetivo que las decisiones que éstos nos proveen sean significativamente mejores en comparación a aquellas decisiones que se toman con una base cualitativa.

Las aplicaciones de la Investigación de Operaciones crecen rápidamente, principalmente por un mejor conocimiento de estas metodología en las diferentes disciplinas, la creciente complejidad de los problemas que se desea resolver, la mayor disponibilidad de software y el desarrollo de nuevos y mejores algoritmos de solución.

Aunque para TAHA, La Investigación de Operaciones aspira a determinar el mejor curso de acción óptimo de un problema de decisión con la restricción de recursos limitados, aplicando técnicas matemáticas para representar por medio de un modelo y analizar problemas de decisión.

Como tambíen se puede mencionar el desarrolo de Frederick S Hillier el cual ha asumido muchas posiciones de liderazgo en las sociedades profesionales de su campo. Por ejemplo, fungió como tesorero de la Operations Research Society of America, como vicepresidente en juntas de The Institute of Management Science (TIMS) y como co-coordinador general de la 1989 TIMS International Meeting en Osaka, Japón. Ha dirigido comités como TIMS Publications Committee, el ORSA Search Committee como editor de investigación de operaciones, el ORSA Resource Planning Committee para INFORMS. En la actualidad es editor de la serie International Series in Operations Research and Management Science que publica Kluwer Academic Publishers. Y segun el la investigación de operaciones ha extendido a muchas áreas que incluyen programación entera, teoría de colas y sus aplicaciones, control estadístico de la calidad y la aplicación de investigación de operaciones al diseño de sistemas productivos y al presupuesto de capital. Es autor de diversas publicaciones y sus artículos se han seleccionado, al menos una decena de veces, para ser publicados en libros de lecturas recomendadas. Se le adjudicó el primer premio en un concurso de investigación sobre “Presupuesto de capital y temas relacionados” auspiciado por The Institute of Management Science y el U.S. Office of Naval Research. Junto con el Dr. Lieberman recibió una mención honorífica por el Lanchaster Prize de 1995 (mejor publicación en idioma inglés en el campo de investigación de operaciones), otorgado por el Institute of Operations Research and the Management Sciences (INFORMS) por la sexta edición de este libro.

Áreas funcionales

Una muestra de los problemas que la IO ha estudiado y resuelto con éxito en negocios e industria se tiene a continuación:

• Personal: La automatización y la disminución de costos, reclutamiento de personal, clasificación y asignación a tareas de mejor actuación e incentivos a la producción.
• Mercado y distribución:El desarrollo e introducción de producto, envasado, predicción de la demanda y actividad competidora, localización de bodegas y centros distribuidores.
• Compras y materiales: Las cantidades y fuentes de suministro, costos fijos y variables, sustitución de materiales, reemplazo de equipo, comprar o rentar.
• Manufactura: La planeación y control de la producción, mezclas óptimas de manufactura, ubicación y tamaño de planta, el tráfico de materiales y el control de calidad.
• Finanzas y contabilidad: Los análisis de flujo de efectivo, capital requerido de largo plazo, inversiones alternas, muestreo para la seguridad en auditorías y reclamaciones.
• Planeación: Con los métodos Pert para el control de avance de cualquier proyecto con múltiples actividades, tanto simultáneas como las que deben esperar para ejecutarse.

La lista de áreas funcionales de la organización que son de posible aplicación de la IO, es ilustrativa del potencial que tiene para resolver el problema de la empresa.

Problemas ejemplo de aplicación con éxito de la IO.

- En los siguientes problemas el gobierno o empresa, ahorraron millones de dólares en la aplicación de la IO:

1. Programación del horario de las rondas de policías de San Francisco.-En 1989 Taylor y Huxley diseñaron un método para programar el horario de las rondas de oficiales de la Policía de San Francisco, usando un modelo de programación lineal, la programación de metas y la programación entera. El ahorro sumó 11 millones de dólares anuales.
2. Reducción de gastos de combustible en la industria de la energía eléctrica.- En 1989 Chao y Cols ahorraron a 79 empresas de servicio de energía eléctrica más de 125 millones de dólares en costos de compras y de déficit, usando programación dinámica y simulación.
3. Diseño de una instalación para desmontar lingoteras en Bethlehem Steel.- En 1989 Vasko y Cols ayudaron a esta empresa siderúrgica con el diseño del sistema de quitar lingoteras a los lingotes de acero con un modelo de programación entera ahorrando 8 millones de dólares anuales.
4. Mezcla de gasolinas en Texaco.- Con programación lineal y no lineal Dewit y Cols diseñaron un modelo de mezcla para cuatro tipos de gasolina ahorrando 30 millones de dólares al año; aplicando análisis de sensibilidad calcularon el efecto de cambios al modelo.
5. Programación del horario de los camiones para North America Van Lines.-En 1989 Powell y Cols, con modelos de redes y programación dinámica, formularon la asignación de carga a chóferes, reduciendo costos en 2.5 millones de dólares, con mejor servicio.
6. Administración del inventario a Blue Bell.-En 1985 Edwars, Wagner y Wood con programación lineal y modelos probabilísticos de inventario redujeron el nivel medio de inventario de ropa deportiva y de oficina en un 31%.
7. Determinación de carteras de bonos.- Varias personas (Chandy y Kharabe, 1986) utilizaron la programación lineal para máxima ganancia con restricciones de riesgo y de la diversificación de la cartera.
8. Planeación de producción en lechería.-En 1985 Sullivan y Secrest, usaron programación lineal con utilidad de 48000 dólares, al determinar el proceso: del suero, la leche cruda, el suero dulce y la crema, para obtener: queso crema, requesón, crema agria y crema de suero.
9. Reemplazo de equipo en Phillips Petroleum.- Para el reemplazo de equipo usaron modelos (Waddell, 1983), que se estima ahorraron 90000 dólares por año.

Objetivos y métodos

El objetivo y finalidad de la investigación operacional 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 conocimiento a demás cosas.

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.