optimizacion de redes

INVESTIGACION DE OPERACIONES

Optimización de Redes

http://www.ingenieriaindustrialonline.com/herramientas-para-el-ingeniero-industrial/investigaci

%C3%B3n-de-operaciones/

TERMINOLOGIA Arco Dirigido, Es el flujo a través de un

arco que permite sólo una sola dirección. La dirección se indica agregando una cabeza de flecha al final de la línea que representa el arco.

Arco No Dirigido, Es el flujo a través de un arco que permite el sentido en ambas direcciones.

TERMINOLOGIA

Ligadura, para ayudar a distinguir entre los dos tipos de arcos, con frecuencia se hará referencia a los arcos no dirigidos con el sugestivo nombre de ligadura.

Red Dirigida, una red que tiene sólo arcos dirigidos. Red No Dirigida, son todos los arcos no

dirigidos

TERMINOLOGIA Trayectoria, es una sucesión de arcos

conectados por una serie de arcos entre dos nodos.

Trayectoria dirigida, Cuando algunos o todos los arcos de una red son arcos dirigidos, se hace la distinción entre trayectorias dirigidas trayectorias no dirigidas. Una Trayectoria dirigida del nodo i al nodo j es una sucesión de arcos (si la tienen ) cuya dirección es hacia el nodo j , de

TERMINOLOGIA manera que el flujo del nodo i al nodo j a

través de esta trayectoria sea factible.

Una trayectoria no dirigida del nodo i al nodo j es una sucesión de arcos cuya dirección (si la tienen) puede ser hacia o desde el nodo j .

TERMINOLOGIA Una Gráfica consiste en un conjunto de

puntos y un conjunto de líneas que unen ciertos pares de puntos.

Los puntos se llaman nodos (o vértices).

Las Líneas se llaman Arcos ó ligaduras, aristas o ramas.

TERMINOLOGIA

7 5

2 2 4

5 1 3 7 4 1 4 SISTEMAS DE CAMINOS PARA EJEMPLO

0

A

C

B

D

E

T

Red Dirigida Común La sucesión de arcos AB-BC-CE (A B C D) es una trayectoria dirigida

del nodo A al nodo E ya que el flujo hacia el nodo E a lo largo de toda esta trayectoria es factible.

A

B

C

D

E

Red Dirigida Común También vemos que, BC-AC-AD (B C A D) no es una trayectoria

dirigida del nodo B al nodo D, porque la dirección del arco AC es desde el nodo D.

(sobre esta trayectoria).

A

B

C

D

E

Red Dirigida Común No obstante, (B C A D) es una

trayectoria no dirigida del nodo B al nodo D.

A

B

C

D

E

Red Dirigida Común Un ciclo es una trayectoria que comienza

y termina en el mismos nodo. En una red dirigida, un ciclo puede ser dirigido o no dirigido según si la trayectoria en cuestión es dirigida o no dirigida. Y lo observamos en la figura con los nodos DE.

TERMINOLOGIA Se dice que dos nodos están conectados

si la red contiene al menos una trayectoria no dirigida entre ellos.

Una red conexa es una red en la que cada par de nodos está conectado, por lo tanto las dos redes mostradas anteriormente con redes conexas.

Componentes de Redes Representativas

Nodos Arcos Flujo

Cruceros Caminos Vehículos Aeropuertos Líneas Aéreas Aviones

Puntos de conmutación Cables, canales Mensajes

Estaciones de Bombeo Tuberías Fluidos

Centros de Trabajo Rutas de manejo Trabajos de Materiales

TERMINOLOGIA Se puede hacer crecer un árbol,

agregando un arco o rama a la vez de cierta manera. Cada nuevo arco crea un árbol más grande, que es una red conexa, para algún subconjunto de n nodos que no contiene ciclos no dirigidos.

Esté árbol se llama árbol en expansión, y es una red conexa para los nodos que no contienen ciclos no dirigidos.

TERMINOLOGIA Todo árbol de expansión tiene exactamente

(n – 1) arcos, ya que esté es el mínimo número de arcos necesario para tener una red conexa y el máximo número posible para que no haya ciclos no dirigidos.

Los nodos sin arcos:

A D

C

B E

Ejemplo para hacer crecer un Árbol un árbol con un arco :

un árbol con dos arcos :

un árbol con tres arcos :

A D

A D

E

A D

E

C

Ejemplo para hacer crecer un Árbol un árbol de expansión:

A D

E

C

B

Ejemplo para hacer crecer un Árbol

La figuras anteriores muestran los cinco nodos y algunos de los arcos para ilustrar el proceso de hacer crecer un árbol poniendo un arco a la vez, hasta que se obtiene un árbol de expansión.

Importancia de los Árboles de expansión. Los árboles de expansión juegan un papel

clave en el análisis de problemas de árbol de mínima expansión, en soluciones de básicas factibles en el método simplex de redes.

TERMINOLOGIA Terminología adicional sobre flujos en

redes: La cantidad máxima de flujo (quizá

infinito) que puede circular en un arco dirigido se conoce como capacidad de arco.

Un nodo fuente (o nodo origen) tiene la propiedad de que el flujo que sale del nodo excede el flujo que entra a él.

TERMINOLOGIA El caso inverso es un nodo demanda (o

nodo destino), en el que el flujo que llega excede al que sale del nodo.

El nodo de trasbordo (o no nodo intermedio) satisface la conservación del flujo, así el flujo que entra es igual al que sale.

PROBLEMA DE LA RUTA MAS CORTA

Algoritmo.

7 5

2 2 4

5 1 7 4 1 3 4 Encontrar la Ruta más Corta del diagrama anterior.

0

A

C

B

D

E

T

Aplicación del algoritmo del problema de la Ruta más Corta:

Nodos resueltos Nodo no resuelto Distancia n-ésimo

n conectados directamente más cercano total nodo más Distancia Ultima a nodos no resueltos conectado involucrada cercano mínima Conexión

1 O A 2 A 2 OA




1 O A 2 A 2 OA

2,3 O C 4 C 4 OC




1 O A 2 A 2 OA

2,3 O C 4 C 4 OC A B 2+2= 4 B 4 AB




1 O A 2 A 2 OA

2,3 O C 4 C 4 OC A B 2+2= 4 B 4 AB

A D 2+7= 9 4




1 O A 2 A 2 OA

2,3 O C 4 C 4 OC A B 2+2= 4 B 4 AB

A D 2+7= 9 4 B E 4+3= 7




1 O A 2 A 2 OA

2,3 O C 4 C 4 OC A B 2+2= 4 B 4 AB

A D 2+7= 9 4 B E 4+3= 7 E 7 BE C E 4+4= 8




1 O A 2 A 2 OA

2,3 O C 4 C 4 OC A B 2+2= 4 B 4 AB

A D 2+7= 9 4 B E 4+3= 7 E 7 BE C E 4+4= 8 A D 2+7= 9 5




1 O A 2 A 2 OA

2,3 O C 4 C 4 OC A B 2+2= 4 B 4 AB

A D 2+7= 9 4 B E 4+3= 7 E 7 BE C E 4+4= 8 A D 2+7= 9 5 B D 4+4= 8




1 O A 2 A 2 OA

2,3 O C 4 C 4 OC A B 2+2= 4 B 4 AB

A D 2+7= 9 4 B E 4+3= 7 E 7 BE C E 4+4= 8 A D 2+7= 9 5 B D 4+4= 8 D 8 BD E D 7+1= 8 D 8 ED




1 O A 2 A 2 OA

2,3 O C 4 C 4 OC A B 2+2= 4 B 4 AB


6 D T 8+5= 13




1 O A 2 A 2 OA

2,3 O C 4 C 4 OC A B 2+2= 4 B 4 AB


6 D T 8+5= 13 T 13 DT E T 7+7= 14


Algoritmo.

5

2 2

1 3 Encontrar la Ruta más Corta del diagrama anterior.

0

A

C

B

D

E

T


Algoritmo.

5

2 2

1 3 La Ruta más Corta del diagrama : O-A-B-E-D-T

0

A

B

D

E

T


Algoritmo.

5

2 2 4

Encontrar la Ruta más Corta del diagrama anterior.

0

A

B

D T


Algoritmo.

7 5

2 2 4

5 1 7 4 1 3 4 Encontrar la Ruta más Corta del diagrama anterior.

0

A

C

B

D

E

T

winqsb ruta mas corta Ruta mas corta WINQSB.ppt

Ejemplo no. 2 7

4 1 6

6 5 1

4 8 5 2

5

ENCONTRAR LA RUTA MAS CORTA SEGÚN EL ALGORITMO.

O

A

B

C

D

E

T




1 O A 4 A 4 OA

2 O C 5 C 5 OC 3 A B 4+1= 5 B 5 AB 4 B C 5+2= 7 C 7 BC A D 4+7= 11 5 B D 5+5= 10 D 10 BD E D 5+4+1= 10 D 10 ED

B E 5+4= 9 E 9 BE 6 C E 7+5= 12

7 D T 10+6= 16 T 16 DT E T 9+8= 17

Ejemplo No. 3Encontrar la Ruta más Corta

3 4 4 5 2 2 2 1 7 6 2 5 8

3 4 5 1 2 3 4 6 5

O

A

B

C

D

E

F

G

H

I

T


Nodos resueltos Nodo no resuelto Distancia n-ésimo n conectados directamente más cercano total nodo más Distancia Ultima a nodos no resueltos conectado involucrada cercano mínima Conexión 1 O A 4 A 4 OA

2 O B 3 B 3 OB3 A C 4+5= 9 C4 B C 3+4= 7 C

A D 4+3= 7 D 7 AD C D 9+2= 11 D

B E 3+6= 9 E 9 BE 6 C E 9+5= 14 E

7 D F 7+2= 9 DF C F 6+2=9 F 9 CF E F 9+1= 10 8 D G 7+4= 11 G 11 DG F G 9+2= 11 G 11 FG

9 F H 9+5= 14 E H 9+2= 11 H 11 EH E I 9+5= 14 10 G T 11+7= 18 GT H T 11+8= 19 T 18 I T 14+4= 18 IT

PROBLEMA DE ÁRBOL EXPANSIÓN MÍNIMA. Consiste en encontrar la Ruta más Corta a

través de una red completamente definida, el problema elige las ligaduras en la red que tenga la longitud total más corta al mismo tiempo que proporciona una trayectoria entre cada par de nodos.

Es necesario que las ligaduras se elijan de tal manera que la red resultante forme un árbol que se expande todos los nodos dados. El problema, encontrar el árbol de expansión con la longitud total mínima de sus ligaduras.

PROBLEMA DE ÁRBOL EXPANSIÓN MÍNIMA. Ejemplo No.1

7 5

2 2 4

5 1 7 4 1 3 4

0

A

C

B

D

E

T

PROBLEMA DE ÁRBOL EXPANSIÓN MÍNIMA.

figura No. 1

0

A

C

B

D

E

T

PROBLEMA DE ÁRBOL EXPANSIÓN MÍNIMA. De la figura No. 1 : No es un árbol de

expansión, pues los nodos (O, A, B, C) no están conectados con los nodos (D, T, E ). Se necesitan una rama más para hacer conexión.


figura No. 2

0

A

C

B

D

E

T

PROBLEMA DE ÁRBOL EXPANSIÓN MÍNIMA. De la figura No. 2 : Las ligaduras de está

red sise expanden por toda la red, es una gráfica conexa, pero no es un árbol por que tiene dos ciclos : (O-A-B-C-D) y

( D-T-E-D ). Tienen demasiadas ligaduras, ya que como el problema tiene 7 nodos y una red debe tener justo (n-1=6) ligaduras y no tener ciclos para calificar como un árbol de expansión.


figura No. 3

0

A

C

B

D

E

T

PROBLEMA DE ÁRBOL EXPANSIÓN MÍNIMA. La figura No. 3 , está red cumple la

condición de (n-1=6) por lo tanto esta tiene una solución factible para el problema de mínima expansión. Con una longitud total de 24 millas en las ramas.

PROBLEMA DE ÁRBOL EXPANSIÓN MÍNIMA. Ejemplo No.1

5

2 2 4

7 4

0

A

C

B

D

E

T

PROBLEMA DE ÁRBOL EXPANSIÓN MÍNIMA. Este problema tiene muchas aplicaciones

prácticas importantes, tales como en redes de transportes, costos, redes de comunicación y redes de distribución de gran escala.

El problema de árbol de mínima expansión se puede resolver directamente, pues en cada etapa del procedimiento de solución, conduce al final a una solución óptima.

ALGORITMO PARA EL PROBLEMA DE ÁRBOL EXPANSIÓN MÍNIMA.

1. Se selecciona de manera arbitraria, cualquier nodo y se conecta al nodo más cercano distinto de esté.

2. Se identifica el nodo no conectado más cercano a un nodo conectado, y se conectan estos dos nodos a través de una ligadura. Este paso se repite hasta que se hayan conectado todos los nodos.

ALGORITMO PARA EL PROBLEMA DE ÁRBOL EXPANSIÓN MÍNIMA. Empates: los empates para el nodo mas

cercano (paso 1) o para el nodo no conectado más cercano (paso 2), se puede romper arbitrariamente y el algoritmo todavía puede tener una solución óptima. No obstante estos empates son señal de que pueden existir soluciones óptimas múltiples (no necesariamente) Todas esas soluciones se pueden identificar si se buscan las demás formas de romper los empates hasta el final.

PROBLEMA DE ÁRBOL EXPANSIÓN MÍNIMA. Enfoque Gráfico.

7 5

2 2 4

5 1 7 4 1 3 4 En forma arbitraria, se selecciona el nodo O para comenzar. El

nodo más cercano a O es el nodo A. Se conecta

0

A

C

B

D

E

T


7 5

2 2 4

5 1 7 4 1 3 4 El nodo no conectado más cercano a cualquiera de los nodos O ó

A es el nodo B (más cercano a A). Se conectan

0

A

C

B

D

E

T


7 5

2 2 4

5 1 7 4 1 3 4 El nodo no conectado más cercano a O, A ó B es el nodo C (más

cercano a B). Se conectan

0

A

C

B

D

E

T


7 5

2 2 4

5 1 7 4 1 3 4 El nodo no conectado mas cercano a O, A, B o C es el nodo E (más

cercano a B). Se conectan

0

A

C

B

D

E

T


7 5

2 2 4

5 1 7 4 1 3 4 El nodo no conectado más cercano a los nodos O, A, B, C, ó E es el

nodo D (más cercano a E), se conectan

0

A

C

B

D

E

T


7 5

2 2 4

5 1 7 4 1 3 4 El único nodo sin conectar, es el nodo T. Esta más cerca del nodo D.

por lo que se conectan. Dando como resultado el total 14 millas

0

A

C

B

D

E

T

Encontrar la solución por medio del Árbol de Mínima Expansión 7

4 1 6

6 5 1

4 8 5 2

5

O

A

B

C

D

E

T


4 1 6

6 5 1

4 8 5 2

5

se selecciona el nodo O para comenzar. El nodo más cercano a O es el nodo A. Se conecta

O

A

B

C

D

E

T


4 1 6

6 5 1

4 8 5 2

5

El nodo no conectado más cercano a cualquiera de los nodos O ó A es el nodo B (más cercano a A). Se conectan

O

A

B

C

D

E

T


4 1 6

6 5 1

4 8 5 2

5

El nodo no conectado más cercano a O, A ó B es el nodo C (más cercano a B). Se conectan

O

A

B

C

D

E

T


4 1 6

6 5 1

4 8 5 2

5

El nodo no conectado mas cercano a O, A, B o C es el nodo E (más cercano a B). Se conectan

O

A

B

C

D

E

T


4 1 6

6 5 1

4 8 5 2

5

El nodo no conectado más cercano a los nodos O, A, B, C, ó E es el nodo D (más cercano a E), se conectan

O

A

B

C

D

E

T


4 1 6

6 5 1

4 8 5 2

5

El único nodo sin conectar, es el nodo T. Esta más cerca del nodo D. por lo que se conectan. Dando como resultado el total : 18 millas

O

A

B

C

D

E

T

Encontrar la solución por medio WIN QSB del Árbol de Mínima Expansión

7

4 1 6

6 5 1

4 8 5 2

5

O

A

B

C

D

E

T

Encontrar la solución por medio WIN QSB del Árbol de Mínima ExpansiónINGRESANDO A WINQSB El primer paso para resolver un problema de transporte mediante WinQSB es ingresar al módulo Network Modeling.


Luego debemos seleccionar la opción Minimal Spanning Tree (Árbol de Expansión Mínima). Además en este submenú debemos de especificar el nombre del problema y el número de nodos. En

nuestro caso el número de nodos es igual a 7, luego click en OK.


Una vez se realiza el paso anterior se abrirá una ventana en la cual aparecerá la siguiente matriz:


En esta matriz se deben de consignar los valores de los ramales que unen las conexiones entre los nodos correspondientes, según el contexto de nuestro problema se deben de consignar las distancias entre los nodos si es que dichas conexiones existen de lo contrario en caso que la conexión no exista se debe dejar la celda en blanco. Hay que tener en cuenta que las distancias entre los nodos en este caso son exactamente conmutativas, es decir que si el nodo fuente es 2 y el destino es 4 la distancia existente entre estos es exactamente igual a la distancia existente entre un nodo fuente 4 y un nodo destino 2, sin embargo esta propiedad debe de especificarse en la matriz consignando los valores correspondientes a una conexión dos veces, es decir en la celda [From 1 - To 4] se debe de consignar la distancia 6, además debe de consignarse la misma distancia en la celda [From 4 - To 1].


http://www.ingenieriaindustrialonline.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/teor%C3%ADa-de-redes/

Encontrar la solución por medio del Árbol de Mínima Expansión (WINQSB)

3 4 4 5 2 2 2 1 7 6 2 5 8

3 4 5 1 2 3 4 6 5

O

A

B

C

D

E

F

G

H

I

T

Encontrar la solución por medio WIN QSB del Árbol de Mínima ExpansiónINGRESANDO A WINQSB El primer paso para resolver un problema de transporte mediante WinQSB es ingresar al módulo Network Modeling.


Luego debemos seleccionar la opción Minimal Spanning Tree (Árbol de Expansión Mínima). Además en este submenú debemos de especificar el nombre del problema y el número de nodos. En nuestro caso el número de nodos es igual a 11, luego click en OK.


Una vez se realiza el paso anterior se abrirá una ventana en la cual aparecerá la siguiente matriz:


En esta matriz se deben de consignar los valores de los ramales que unen las conexiones entre los nodos correspondientes, según el contexto de nuestro problema se deben de consignar las distancias entre los nodos si es que dichas conexiones existen de lo contrario en caso que la conexión no exista se debe dejar la celda en blanco. Hay que tener en cuenta que las distancias entre los nodos en este caso son exactamente conmutativas, es decir que si el nodo fuente es 2 y el destino es 4 la distancia existente entre estos es exactamente igual a la distancia existente entre un nodo fuente 4 y un nodo destino 2, sin embargo esta propiedad debe de especificarse en la matriz consignando los valores correspondientes a una conexión dos veces, es decir en la celda [From 1 - To 4] se debe de consignar la distancia 6, además debe de consignarse la misma distancia en la celda [From 4 - To 1].

Encontrar la solución por medio del Árbol de Mínima Expansión

3 4 4 5 2 2 2 1 7 6 2 5 8

3 4 5 1 2 3 4 6 5 Existe un empate en los nodos C-D y C-F Resultado : 22 millas

O

A

B

C

D

E

F

G

H

I

T

EJERCICIO

La ciudad de Cali cuenta con un nuevo plan parcial de vivienda el cual contará con la urbanización de más de 7 proyectos habitacionales que se ubicarán a las afueras de la ciudad. Dado que el terreno en el que se construirá no se encontraba hasta ahora dentro de las zonas urbanizables de la ciudad, el acueducto municipal no cuenta con la infraestructura necesaria para satisfacer las necesidades de servicios públicos en materia de suministro de agua. Cada uno de los proyectos de vivienda inició la construcción de un nodo de acueducto madre, el cual cuenta con las conexiones

EJERCICIO … continua

de las unidades de vivienda propias de cada proyecto (es decir que cada nodo madre solo necesita estar conectado con un ducto madre del acueducto municipal para contar con su suministro). El acueducto municipal al ver la situación del plan parcial debe de realizar las obras correspondientes a la instalación de ductos madres que enlacen todos los nodos del plan con el nodo Meléndez (nodo que se encuentra con suministro de agua y que no pertenece al plan parcial de vivienda, además es el más cercano al mismo), la

EJERCICIO … continua

instalación de los ductos implica obras de excavación, mano de obra y costos de los ductos mismos, por lo cual optimizar la longitud total de los enlaces es fundamental. Las distancias existentes (dadas en kilómetros) correspondientes a las rutas factibles capaces de enlazar los nodos del plan parcial se presentan a continuación. Además la capacidad de bombeo del nodo Meléndez es más que suficiente para satisfacer las necesidades de presión que necesita la red madre.

Luego damos click en Solve and Analize y tendremos la siguiente ventana solución inmediatamente.

PROBLEMA DEL FLUJO MÁXIMO

Terminología: Considérese una red dirigida y conexa que tiene un solo nodo fuente un solo nodo destino, y el resto son nodos de trasbordo. Dada la capacidad en los arcos, el objetivo es determinar el patrón factible que fluye a través de la red que maximiza el flujo total, desde el nodo fuente al nodo destino.

PROBLEMA DEL FLUJO MÁXIMO Para la solución de este problema se

cuenta con un Algoritmo de Trayectorias Aumentadas mucho mas eficiente. Este algoritmo se basa en dos conceptos intuitivos, el de la red residual y el de una trayectoria aumentada

PROBLEMA DEL FLUJO MÁXIMOAlgoritmo para el Problema del Flujo Máximo.

1. Se identifica una trayectoria aumentada encontrando alguna trayectoria dirigida del nodo de origen al nodo destino en la red residual tal que cada arco sobre está trayectoria tiene capacidad residual estrictamente positiva. Si no existe una, los flujos netos ya asignados constituyen un patrón de flujo óptimo.


2. Se identifica la capacidad residual c* de está trayectoria aumentada encontrando el mínimo de las capacidades residuales de los arcos sobre la trayectoria. Se aumenta en c* el flujo de esta trayectoria.


3. Se disminuye en c* la capacidad residual de cada arco en esta trayectoria aumentada. Se aumenta en c* la capacidad residual de cada arco en la dirección opuesta en está trayectoria. Se regresa al punto 1.

Problema de Flujo Máximo

3

0 1 0 9 0 0 5 7 0 1 4 1 0 4 2 5

0 1 0 6 0 4 0

0

A

C

B

D

E

T

Problema de Flujo Máximo Iteración I: si se hace referencia a la figura

anterior, una de las trayectorias aumentadas es O-B-E-T que tiene la capacidad residual igual al min {7, 5, 6}=5. Si se asigna un flujo de 5 a esta trayectoria, la red residual que resulta es:


3

0 1 0 9 0 0 5 2 5 1 4 1 5 4 2 0

5 1 0 1 0 4 0

0

A

C

B

D

E

T

5

5


Iteración 2 : se asigna un flujo de 3 a O A D T la red resultante es la red

residual


0

3 1 3 6 3 0 2 2 5 1 4 1 5 4 2 0

5 1 0 1 0 4 0

0

A

C

B

D

E

T

8

8


Iteración 3: se asigna un flujo de 1 a la trayectoria aumentada O A B D T .

Iteración 4: se asigna un flujo de 2 a la trayectoria aumentada O B D T .


0

4 0 3 3 6 3 1 0 7 2 1 1 5 4 2 0

5 1 0 1 0 4 0

0

A

C

B

D

E

T

11

11

Problema de Flujo Máximo Iteración 5: se asigna un flujo de 1 a la

trayectoria aumentada O C E D T

Iteración 6 : se asigna un flujo de 1 a la trayectoria aumentada O C E T


0

4 0 3 2 7 3 1 0 7 2 1 2 5 3 2 0

5 0 0 1 1 3 1

0

A

C

B

D

E

T

12

12


0

4 0 3 2 7 3 1 0 7 2 1 2 6 2 2 0

5 0 0 0 2 2 2

0

A

C

B

D

E

T

13

13


Iteración 7: se asigna un flujo de 1 a la trayectoria aumentada O C E B D T


0

4 0 3 1 8 4 1 0 7 2 0 2 6 1 2 1

4 0 0 0 3 1 3

0

A

C

B

D

E

T

14

14


La solución Óptima para esté problema de flujo máximo es el siguiente:


3 4 1 8 4 7 1 6

3 4 3

0

A

C

B

D

E

T

14

14

Encontrar la solución por medio de : Flujo Máximo 7

4 1 6

6 5 1

4 8 5 2

5

O

A

B

C

D

E

T

Encontrar la solución por medio de : Flujo Máximo

3 4 4 5 2 2 2 1 7 6 2 5 8

3 4 5 1 2 3 4 6 5

O

A

B

C

D

E

F

G

H

I

T

Encontrar la solución por medio de : Flujo Máximo

O

A

B

C

D

E

F

G

H

I

T

Problema de Flujo de Costo Mínimo Este problema tiene una posición medular

entre los modelos de optimización de redes; primero, porque abarca una clase muy amplia de aplicaciones y segundo, porque su solución es en extremo eficiente.

Al igual que en el flujo máximo. Toma en cuenta un flujo a través de una red con capacidades limitadas en sus arcos.

Problema de Flujo de Costo Mínimo Al igual que los problemas de ruta mas

corta, considera un costo o o distancia para el flujo a través de un arco.

Al igual que el problema de transporte o el problema de asignación, puede manejar varios orígenes y varios destinos para el flujo , también con costos asociados.

Por lo tanto se puede resolver mediante una versión simplificada del método símplex de redes.

Problema de Flujo de Costo Mínimo Formulación: Considere una red conexa

dirigida en la que los n nodos incluyen al menos un nodo origen y al menos un nodo destino. Las variables de decisión son:

Xij = flujo a través del arco i j y la información dada incluye : Cij = costo por unidad de flujo a través del

arco arco i j Uij = capacidad del arco i j bi = flujo neto generado en el nodo i

Problema de Flujo de Costo Mínimo El valor de bi depende de la naturaleza del

nodo i, en donde

bi> 0, si i es un nodo fuente, bi< 0, si i es un nodo demanda, bi= 0, si i es un nodo transbordo El objetivo es minimizar el costo total de

mandar los recursos disponibles a través de la red puede satisfacer la demanda dada.

Problema de Flujo de Costo Mínimo Usando la convención de que las sumas se toman

sólo sobre arcos existentes, la formulación de programación lineal de este problema es:

Minimizar Z = ∑ ∑ Cij Xj Sujeta a

∑Xij - ∑ Xji = bi , para cada nodo i

Y 0 ≤ Xij ≤ Uij , para cada arco i j

n

i=1

n

J=1

n n

J=1 J=1

Problema de Flujo de Costo Mínimo La primera suma en las restricciones

representa el flijo total que sale del nodo i, mientras que la segunda suma representa el flujo total que entra al nodo i así, la diferencia es el flujo neto generado en este nodo.

Con el fin de ajustar el modelo al formato anterior con restricciones de no negatividad.

No se garantiza que el problema posea soluciones factibles, esto depende en parte

Problema de Flujo de Costo Mínimo de qué arcos se tienen en la red y de sus

capacidades. De cualquier manera, para una red diseñada razonablemente, la condición mas importante es la siguiente:

∑ bi= 0; para que un problema de flujo de costo mínimo

tenga soluciones factibles, el flujo total generado en los nodos de origen es igual al flujo total absorbido por los nodos destino.

n

i=1

Problema de Flujo de Costo Mínimo Al igual que en los problemas de transporte la

solución está garantizada sin tener que establecer restricciones enteras en forma explicita sobre las variables. Esto debido a la siguiente Propiedad:

Propiedad de soluciones enteras: para los problemas de flujo de costo mínimo en donde toda bi y uij tienen un valor entero, todas las variables básicas en cada solución básica factible tendrán también valores enteros.

Problema de Flujo de Costo Mínimo La siguiente Red del problema del flujo de

costo mínimo, se agregan los valores de bi Cij y Uij

CA = [50] [-30]

CAD = 9

2 4 [0] 2 3 3 1 (UCE = 80)

[40] [-60]

A

B

C

D

E

Para Examen Final :

Fecha : 26 de noviembre del 2008 Hora : 15:20 como máximo Grupo de 2 personas 2 Aplicaciones con problemas resueltos de

los siguientes Temas: 1.Ruta mas Corta.2.Árbol de mínima expansión.3.Flujo Máximo.4.Flujo Costo Mínimo.5.Teoría de Redes. Investigar

procedimiento, solución y aplicaciones.

optimizacion de redes

Documents