• Author / Uploaded
• Karily Mendez Mendoza

Citation preview

Instituto Tecnológico de Lázaro Cárdenas 1 Modelos de Investigación de Operaciones

ISC Grupo 31T

nidad 2 Analisis de Redes Desarrollo de toda la unidad: Archivos .html\Investigacion de UNIDAD 2 ANALISIS DE REDES.htm

Operaciones

Análisis de Redes. Presentación.

El estudio de las propiedades estructurales y su optimización así como su dinámica son objeto del análisis de redes. El análisis de redes es el área encargada de analizar las redes mediante la teoría de redes (conocida más genéricamente como teoría de grafos). Las redes pueden ser de diversos tipos: social, transporte, eléctrica, biológica, internet, información, epidemiología, etc. Los estudios realizados sobre las redes abarcan sus estructuras tales como en las redes de mundo pequeño, las redes libres de escala, los círculos sociales, medidas de centralidad. Puede ser objeto de estudio la optimización como en el caso de método de la ruta crítica, el PERT (del inglés Program Evaluation & Review Technique). Así como la dinámica de las redes como pede ser el estudio de sistema dinámico secuencial (SDS del inglés Sequential Dynamical System), o de propiedades como la asignación dinámica de flujos. 2.1 Conceptos Basicos Un

problema

de

redes

Silva Soto Rosa Lizbeth

es

aquel

que

puede

representarse

por:

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Instituto Tecnológico de Lázaro Cárdenas 2 Modelos de Investigación de Operaciones

LA IMPORTANCIA DE LOS MODELOS DE REDES: Muchos problemas comerciales pueden ser resueltos a través de modelos redes El resultado de un problema de redes garantiza una solución entera, dada su estructura matemática. No se necesitan restricciones adicionales para obtener este tipo de solución. Problemas de redes pueden ser resueltos por pequeños algoritmos , no importando el tamaño del problema, dada su estructura matemática. Terminología de Redes 1. Flujo: Corresponde a la cantidad que debe transportarse desde un nodo i a un nodo j a través de un arco que los conecta. La siguiente notación es usada: Xij= cantidad de flujo Uij= cota mínima de flujo que se debe transportar Lij= cota maxíma de flujo que se puede transportar. 2. Arcos dirigidos /no dirigidos: Cuando el flujo puede transportarse en una sola dirección se tiene un arco dirigido (la flecha indica la dirección). Si el flujo puede transportarse en ambas direcciones existe un arco no dirigido (sin flecha). 3. Nodos adyacentes: Un nodo j es adyacente con un nodo i si existe un arco que une el nodo j con el nodo i. Rutas/Conexión entre nodos Ruta: Una colección de arcos formados por una serie de nodos adyacentes Los nodos están conectados si existe una ruta entre ellos. 4 Ciclos / Arboles /Arboles expandidos Ciclos : Un ciclo se produce cuando al partir de un nodo por un cierto camino se vuelve al mismo nodo por otra ruta. Arbol : Una serie de nodos que no contienen ciclos. Arbol expandido: Es un árbol que conecta todos los nodos de la red (contiene n-1 arcos).

Silva Soto Rosa Lizbeth

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Silva Soto Rosa Lizbeth

Instituto Tecnológico de Lázaro Cárdenas 3 Modelos de Investigación de Operaciones

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Silva Soto Rosa Lizbeth

Instituto Tecnológico de Lázaro Cárdenas 4 Modelos de Investigación de Operaciones

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Instituto Tecnológico de Lázaro Cárdenas 5 Modelos de Investigación de Operaciones

2.2 Problema de transporte Un problema de transporte surge cuando se necesita un modelo costo-efectividad que permita transportar ciertos bienes desde un lugar de origen a un destino que necesita aquellos bienes, con ciertas restricciones en la cantidad que se puede transportar.

El PT es un caso particular de la PL Se debe determinar un esquema óptimo de transporte que se origina en los lugares de oferta donde la existencia de cierta mercancía es conocida, y llega a los lugares de donde se conoce la cantidad requerida. El costo de cada envió es proporcional a la cantidad transportada y, el costo total es la suma de los costos individuales.

Silva Soto Rosa Lizbeth

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Instituto Tecnológico de Lázaro Cárdenas 6 Modelos de Investigación de Operaciones

Una solución al PT queda definido por un conjunto de mxn número Xij, donde: Xij : Número de unidades a enviar desde el origen i al destino j Siendo Xij ≥ 0

El programa lineal del Problema del transporte queda expresado de la siguiente manera:

Sujeto:

DEFINICIÓN DEL PROBLEMA

Silva Soto Rosa Lizbeth

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Instituto Tecnológico de Lázaro Cárdenas 7 Modelos de Investigación de Operaciones

Se tienen m lugares de origen. Cada lugar de origen tiene una capacidad de producción Si Se tienen n destinos. Cada destino j demanda Dj Objetivo: Minimizar el costo de transporte de la carga al lugar de destino cumpliendo con las restricciones de los lugares de origen. El modelo de transporte tiene notable interés por sus importantes aplicaciones que, como se verá en varios ejercicios, no se restringe únicamente a la distribución de mercancías. Su procedimiento especifico de solución, llamado algoritmo de transporte consta de dos fases y es rápido y eficiente. La primera fase consiste en obtener una solución factible inicial. Se pasa después a la segunda fase, en la que se comprueba si la solución obtenida en la primera fase es óptima, y si no lo es, como mejorarla. EL PROBLEMA DE TRANSPORTE Corresponde a un problema de flujo de mínimo costo Supongamos que deseamos enviar productos desde las bodegas a los lugares de venta Ejemplo: 3 bodegas 4 puntos de venta ai: oferta en bodega i bj: demanda de vendedor j cij: costo de envio de i a j Sea xij la cantidad enviada de i a j Formule el LP

Silva Soto Rosa Lizbeth

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Instituto Tecnológico de Lázaro Cárdenas 8 Modelos de Investigación de Operaciones

EL PROBLEMA DE TRANSPORTE En general, la formulación es Min FARMACÉUTICA CARLTON La farmacéutica Carlton abastece de drogas y otros suministros médicos. Esta tiene tres plantas en: Claveland, Detroit, Greensboro. Tiene cuatro centros de distribución en: Boston, Atlanta, St Louis. La gerencia de Carlton desea realizar el trnsporte de sus productos de la manera más económica posible. DATOS Costo de transporte por unidad, oferta y demanda.

Silva Soto Rosa Lizbeth

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Instituto Tecnológico de Lázaro Cárdenas 9 Modelos de Investigación de Operaciones

SUPUESTOS * El costo de transporte por unidad es constante * Todos los transportes ocurren simultáneamente. * Solo se considera el costo de transporte entre el lugar de origen y el de destino * La oferta total es igual a la demanda total. RED QUE REPRESENTA EL PROBLEMA

SOLUCION DEL PROBLEMA DE TRANSPORTE. En esta sección presentamos los detalles para resolver el modelo de transporte. TECNICA DE TRANSPORTE. Los pasos básicos de la técnica de transporte son: Paso 1: determínese una solución factible.

Silva Soto Rosa Lizbeth

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Instituto Tecnológico de Lázaro Cárdenas 10 Modelos de Investigación de Operaciones

Paso 2: determínese la variable que entra, que se elige entre las variables no básicas. Si todas estas variables satisfacen la condición de optimidad (del método simplex), deténgase; de lo contrario, diríjase al paso 3. Paso 3: determínese la variable que sale (mediante el uso de la condición de factibilidad) de entre las variables de la solución básica actual; después obténgase la nueva solución básica. Regrese al paso 2. OBTENCIÓN DE SOLUCIONES BÁSICAS FACTIBLES PARA PROBLEMAS DE TRANSPORTES Podemos obtener una solución básica factible (sbf) para un problema de transporte balanceado mediante el método de la esquina Noroeste, el método de costo mínimo, o el método de Vogel. Para obtener una sbf mediante el método de la esquina noroeste, empiece en la esquina superior izquierda del cuadro del transporte y haga a X11 lo más grande posible. Naturalmente, X11 no puede ser mayor que el menor valor Si y así X11 S1 tache el primer renglón del cuadro de transporte; Esto indica que si habrá más variables básicas del renglón 1 del cuadro. También d1-S1 . Si X11=d1, tache la primera la columna del cuadro de transporte y cambie S1 – d1. Si X11= S1 = d1, tache o el renglón 1, o la columna 1 (pero no ambos), del cuadro de transporte. Si tacha el renglón 1, cambie d1 por cero; si tacha columna 1, cambie S 1 por 0. Continúe aplicando este procedimiento a la celda mas noroeste del cuadro que no cae en un renglón eliminado o en una columna eliminada. Finalmente, llegara un momento en el cual solo queda una celda a la cual se puede asignar un valor. Asigne a esta celda un valor igual a la oferta de su renglón o a la demanda de su columna, y tache el renglón y la columna de la celda. Se obtiene de esta manera una solución básica factible. OBTENER LA SOLUCIÓN ÓPTIMA PARA UN PROBLEMA DE TRANSPORTE Paso 1: Si el problema no está balanceado, balancéelo. Paso 2: Utilice uno de los métodos descritos anteriormente para obtener una solución básica factible.

Silva Soto Rosa Lizbeth

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Instituto Tecnológico de Lázaro Cárdenas 11 Modelos de Investigación de Operaciones

Paso 3: Utilice el hecho de que U1=0, y Ui+Vj=Cij en todas las variables básicas para encontrar (U1,U2…Um V1,V2…Vn) para la sbf actual. Paso 4: Si Ui + Vj – Cij es menor o igual a cero, para todas las variables no básicas, entonces la sbf actual es óptima. Si no es así se introduce la variable con valor más positivo de Ui + Vj –Cij en la base. Para hacer esto, encuentre un circuito cerrado (se puede demostrar que solamente existe un circuito cerrado) que contiene la variable que entra y algunas de las variables básicas. Después, tomando en cuenta solamente las celdas en el circuito cerrado marque las que se encuentren alejadas en número par (0,2,4,6,…) de celdas de la variable que entra como celdas pares. También marque las celdas en el circuito cerrado, que se encuentra un número impar de celdas de la variable que entra como celdas impares. Ahora encuentre la celda impar cuya variable toma el menor valor. Llame este valor teta. La variable correspondiente a esta celda impar saldrá de la base. Para realizar el pivoteo, disminuye el valor de cada celda impar en teta y aumenta el valor de cada celda par en teta. Los valores de las variables que no se encuentran en el circuito cerrado permanecen sin cambio. Ahora se completó el bloqueo. Sí teta es igual a cero, la variable que entra será igual a cero, y una variable impar que tiene un valor actual de cero, saldrá de la base. En este caso, existía un sbf degenerada antes del pivoteo y resultará después del pivoteo. Si más de una celda impar en el circuito cerrado es igual a teta. Puede escoger arbitrariamente una de estas celdas impares para que salga de la base; se obtendrá una vez más una sbf degenerada. El pivoteo produce una nueva sbf. Paso 5: Regrese a los pasos 3 y 4, utilizando la nueva sbf. Para un problema de maximización, proceda como se especificó, pero cambie el paso 4 por el paso 4’. Paso 6: Si Ui + Vj –Cij es mayor o igual a cero, para todas las variables no básicas, entonces, la sbf actual es óptima. De otra manera, coloque la variable con el valor más negativo de Ui + Vj – Cij en la base mediante el procedimiento de pivoteo.

2.3 Problema de asignación El problema de asignación es una variación del problema original de transporte, variación en la cual las variables de decisión X(i,j) solo pueden tomar valores binarios, es decir ser cero (0) o uno (1) en la solución óptima, lo que supone que la

Silva Soto Rosa Lizbeth

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Instituto Tecnológico de Lázaro Cárdenas 12 Modelos de Investigación de Operaciones

oferta y la demanda están perfectamente alineadas, de hecho ambas son iguales a uno (1). Múltiples son los casos en los que como ingenieros industriales podemos hacer uso del problema de asignación para resolver diversas situaciones, entre los que cabe mencionar se encuentran la asignación de personal a maquinas, herramientas a puestos de trabajos, horarios a maestros, candidatos a vacantes, huéspedes a habitaciones, comensales a mesas, vendedores a zonas territoriales etc En el modelo de asignación la idea fundamental de resolución es ¿qué fuente satisface mejor el destino?, y dado que hemos asociado el modelo a una gran diversidad de circunstancias esta pregunta puede plantearse en múltiples contextos, como ¿qué candidato es el idóneo para la vacante?, o ¿qué personal es el indicado para la línea productiva?, o ¿qué personal es el mejor para ejecutar determinada tarea?. Una característica particular del modelo de asignación es que para su resolución no se hace necesario que el número de fuentes sea igual al número de destinos, lo cual es muy común en la vida real teniendo en cuenta su aplicación, pues generalmente la cantidad de aspirantes es exageradamente superior al número de vacantes (lógicamente haciendo referencia a la aplicación del modelo al contexto de oferta y demanda laboral).

2.4 Problema de la ruta más corta El problema de la ruta más corta incluye un juego de nodos conectados donde sólo un nodo es considerado como el origen y sólo un nodo es considerado como el nodo destino. El objetivo es determinar un camino de conexiones que minimizan la distancia total del origen al destino. El problema se resuelve por el “algoritmo de etiquetado”. Se trata de encontrar la ruta de menor distancia, o costo ,a entre el punto de partida o nodo inicial y el destino o nodo terminal. DEFINICIÓN DEL PROBLEMA -Se tienen n nodos, partiendo del nodo inicial 1 y terminando en el nodo final n. -Arcos bi-direccionales conectan los nodos i y j con distancias mayores que cero, dij

Silva Soto Rosa Lizbeth

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Instituto Tecnológico de Lázaro Cárdenas 13 Modelos de Investigación de Operaciones

-Se desea encontrar la ruta de mínima distancia que conecta el nodo 1 con el nodo n. Por medio de la aplicación del algoritmo de este problema podemos conocer la menor distancia entre un nodo origen y un nodo destino. Pasos a seguir: Primer paso: Elaborar un cuadro con todos los nodosy los ramales que salen de él. Segundo paso: Partiendo del origen, debemos encontrar el nodo más cercano a él. Tercer paso: Anular todos los ramales que entren al nodo más cercano elegido. Cuarto paso: Comenzando en el origen se debe encontrar el nodo más cercano a él, por intermedio del(los) nodo(s) ya elegido(s) y volver al tercer paso hasta llegar al destino. PROBLEMA DE LA RUTA MÁS CORTA ¿Cuál es el camino más corto desde la origen (s de “source”) hasta el destino (t) ? Supuestos: Existe un camino de la fuente a todos los demás nodos Todos los largos de los arcos son no negativos • ¿Cuál es el camino más corto del nodo 1 al 6 ?

PROBLEMA DE LA RUTA MÁS CORTA • En general la formulación con LP de este problema, desde una origen s a un destino t está dada por Silva Soto Rosa Lizbeth

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Instituto Tecnológico de Lázaro Cárdenas 14 Modelos de Investigación de Operaciones

PROBLEMA DE LA RUTA MÁS CORTA • Otra formulación, para determinar la ruta más corta a n nodos es enviar “un” paquete a desde s a cada n-1 nodos.

EJEMPLO 1. Ruta más Corta. Líneas Fairway Van Determine la ruta más corta entre Seattle y El Paso para la siguiente red de carreteras. Solución- Analogía de un problema de programación lineal. - Variables de Decisión

Silva Soto Rosa Lizbeth

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Instituto Tecnológico de Lázaro Cárdenas 15 Modelos de Investigación de Operaciones

Solución- Analogía de un problema de programación lineal. - Variables de Decisión

Silva Soto Rosa Lizbeth

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Instituto Tecnológico de Lázaro Cárdenas 16 Modelos de Investigación de Operaciones

EJEMPLO 2. Ruta más Corta.

Silva Soto Rosa Lizbeth

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Instituto Tecnológico de Lázaro Cárdenas 17 Modelos de Investigación de Operaciones

Solución:

Silva Soto Rosa Lizbeth

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Instituto Tecnológico de Lázaro Cárdenas 18 Modelos de Investigación de Operaciones

2.5 Programacion de proyectos (PERT-CPM). Un proyecto es cualquier empresa humana con un claro principio y un claro final (Gallagher) Poseen algunas características comunes: Combinación de actividades Relación secuencial entre actividades Preocupación por el tiempo Preocupación por los recursos PLANEACIÓN, PROGRAMACIÓN Y CONTROL La Planeación requiere desglosar el proyecto en actividades, estimar recursos, tiempo e interrelaciones entre actividades. La Programación requiere detallar fechas de inicio y terminación. El Control requiere información sobre el estado actual y analiza posibles trueques cuando surgen dificultades. HERRAMIENTAS DE PLANEACIÓN, PROGRAMACIÓN Y CONTROL Gráficas de Gantt Modelos de redes: Redes deterministas (CPM = Método de la ruta crítica) Redes probabilistas (PERT = Técnica de evaluación y revisión de programas) También existen otras técnicas PLANEACIÓN Y CONTROL DE PROYECTOS PERT – CPM. La buena administración de proyectos a gran requiereplaneación, programación y coordinación de muchas actividades.

escala

Programas de construcción Preparación de propuestas y presupuestos Programación de computadoras

Silva Soto Rosa Lizbeth

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Instituto Tecnológico de Lázaro Cárdenas 19 Modelos de Investigación de Operaciones

Planeación de mantenimiento e instalación de sistemas de cómputo. PERT (Técnica de evaluación y revisión de programas- Program evaluationand Review technique). Se utiliza más comúnmente para: Determinar la probabilidad de cumplir con fechas de entrega específicas. Identificar cuellos de botella. Evaluar el efecto de los cambios en el programa.

Silva Soto Rosa Lizbeth

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Silva Soto Rosa Lizbeth

Instituto Tecnológico de Lázaro Cárdenas 20 Modelos de Investigación de Operaciones

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Silva Soto Rosa Lizbeth

Instituto Tecnológico de Lázaro Cárdenas 21 Modelos de Investigación de Operaciones

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Silva Soto Rosa Lizbeth

Instituto Tecnológico de Lázaro Cárdenas 22 Modelos de Investigación de Operaciones

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Silva Soto Rosa Lizbeth

Instituto Tecnológico de Lázaro Cárdenas 23 Modelos de Investigación de Operaciones

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Silva Soto Rosa Lizbeth

Instituto Tecnológico de Lázaro Cárdenas 24 Modelos de Investigación de Operaciones

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Silva Soto Rosa Lizbeth

Instituto Tecnológico de Lázaro Cárdenas 25 Modelos de Investigación de Operaciones

Profesor: ME. José Antonio López Tello

ISC Grupo 31T

Silva Soto Rosa Lizbeth

Instituto Tecnológico de Lázaro Cárdenas 26 Modelos de Investigación de Operaciones

Profesor: ME. José Antonio López Tello