Edicin Especial

Flujo mximo

rbol

rbol de peso mnimo

Mtodo PRIM

RU

TA

M

S C

OR

TA

Cir

cuit

os

neg

ativ

os

Mtodo Dijkstra Generalizado

Ruta m

s corta como problema de Transporte

Mtodo Ford y Fulkerson

Red marginalPERT

CPM

Modelo de Programacin Lineal de Redes de Actividad

Mtodo de eliminacin de circuitos negativos

Mtodo basado en rutas ms cortas

Mtodo Simplex para redes

Costos indirectos

Diagrama de GANTT

Red dirigida

Capacidad y Requerimiento en la redCapacidad y Requerimiento en la redCapacidad y Requerimiento en la redCapacidad y Requerimiento en la red

3

En las siguientes pginas, se conocer y aplicaralos mtodos de solucin y modelos paraproblemas de redes de optimizacin.

Se darn a conocer cuatro tiposimportantes de problemas de Redes, y algunasideas bsicas sobre cmo resolverlos (Sinprofundizar en los aspectos de estructuras debases de datos, tan vitales para la aplicacinexitosa en los problemas de gran escala).

Los cuatro primeros tipos de problemas: El problema de la ruta ms corta, El problema del flujo mximo: Tienen una

estructura especfica que surge confrecuencia en la prctica.

El problema del flujo de costo mnimo:Proporciona un enfoque unificador de muchasotras aplicaciones por su estructura muchoms general.

Y por ltimo el mtodo del CPM.

4

Tema Tema Tema Tema PginaPginaPginaPgina

Presentacin..4Contenido...5Introduccin...7

Terminologa de Redes...11Componentes de Redes.....13Esquema de algunos mtodos..14

Ruta ms corta.15Algoritmo de la Ruta ms corta.....16Ejemplo...17

Flujo Mximo.19Algunas aplicaciones20Ejemplo...21

Flujo a Costo Mnimo......23Descripcin del problema....24Aplicaciones comunes..26Ejemplo28

5

6Redes de actividad..30

Aplicaciones31Planeacin......................32Programacin.34Ejemplo...36Control.39

Clasifica los problemas....44Si de Mtodos Hablamos....46Conocer ms a los creadores.49

Edsger Wybe Dijkstra......49Lester Randolph Ford JR.51Delbert Ray Fulkerson..52

Referencias53

Los problemas de redes surgen en una granvariedad de situaciones. Son aplicables a unaextensa variedad de problemas de decisin, loscuales pueden ser modelados como problemas deoptimizacin de redes que pueden ser eficiente yefectivamente resueltos.

Algunos de estos problemas de decisinson realmente problemas fsicos, tales como eltransporte o flujo de bienes materiales. Las redesde transporte, elctricas y de comunicacionespredominan en la vida diaria.

Sin embargo, muchos problemas de redesson ms que una representacin abstracta deprocesos o actividades, tales como el caminocrtico en las actividades entre las redes de unproyecto gerencial. Se utiliza ampliamente en reastan diversas como produccin, distribucin,planeacin de proyectos, localizacin deinstalaciones, administracin de recursos yplaneacin financiera, para nombrar slo unosejemplos.

7

La familia de redes de los problemas deoptimizacin incluye los siguientes prototiposde modelos: Problemas de asignacin,camino crtico, flujo mximo, camino mscorto, transporte y costo mnimo de flujos.

Los problemas son establecidosfcilmente mediante el uso de arcos de redesy de los nodos.

8

Qu es un Nodo? Es usualmente llamadovrtice, o punto. Es usualmente representado por uncrculo. En las redes de transporte, estos deberanser las localidades o las ciudades en un mapa.Qu es un Arco? Es usualmente llamado bordeo flecha. Este podra ser directo o indirecto. Lacabeza es el destino, y la cola el origen. La cabezay la cola son nodos que pueden estar tanto al origencomo al final. En las redes de transporte, los arcospodran ser los caminos, los canales de navegacinen un ro, o los patrones de vuelo de un avin. Losarcos proporcionan la conectividad entre los nodos.Una calle de una sola direccin podra serrepresentada por un arco, mientras que una calle dedos direcciones podra representada por un arco sindireccin o por dos arcos que apuntan a direccionesopuestas.

De hecho, una representacin de redesproporciona un panorama general tanpoderoso y una ayuda conceptual paravisualizar las relaciones entre loscomponentes del sistema, que se usa casi entodas las reas cientficas, sociales yeconmicas.

9

Uno de los mayores desarrollos recientes eninvestigacin de operaciones (IO) ha sido el rpidoavance tanto en la metodologa como en laaplicacin de los modelos de optimizacin de redes.

La aparicin de algunos algoritmos ha tenidoun impacto importante, al igual que las ideas deciencias de la computacin acerca de estructuras dedatos y la manipulacin eficiente de los mismos.En consecuencia, ahora se dispone de algoritmos ypaquetes de computadora y se usan en formarutinaria para resolver problemas muy grandes queno se habran podido manejar hace dos o tresdcadas.

10

SABAS QUE.....El peso de un rbol es la suma de los costos de lasaristas que lo forman.Y para los rboles de peso mnimo se tienen 2mtodos:PRIMKRUSKAL

Red: conjunto de puntos y lneas que unenciertos pares de puntos.Nodos: Puntos (o vrtices).

11

Arcos: Lneas, ligaduras, aristas o ramas. Seetiquetan para dar nombre a los nodos en sus puntosterminales.Arco dirigido: Si el flujo a travs de un arco sepermite slo en una direccin. La direccin se indicaagregando una cabeza de flecha al final de la lneaque representa el arco.Arco no dirigido: Si el flujo a travs de un arco sepermite en ambas direcciones.Red dirigida: Red que tiene slo arcos dirigidos.Red no dirigida: Todos sus arcos son no dirigidos.Trayectoria: Sucesin de arcos distintos queconectan nodos.Ciclo: Trayectoria que comienza y termina en elmismo nodo.Red conexa: Red en la que cada par de nodos estconectado.

rbol: Red conexa (para algn subconjuntode n nodos) que no contiene ciclos nodirigidos.rbol de expansin: Red conexa para los nnodos que contiene ciclos no dirigidos.

12

Capacidad del arco: Cantidad mxima de flujo(quiz infinito) que puede circular en un arco dirigido.Nodo fuente: Nodo origen, tiene la propiedad deque el flujo que sale del nodo excede el flujo queentra a l.Nodo de demanda: Nodo de destino, donde el flujoque llega excede al que sale de l.Nodo de trasbordo: Intermedio, satisface laconservacin del flujo, es decir, el flujo que entra esigual al que sale.

13

Nodos Arcos Flujos

Cruceros Caminos Vehculos

Aeropuertos Lneas areas Aviones

Puntos de

conmutacin

Cables, canales Mensajes

Estaciones de

bombeo

Tuberas Fluidos

Centros de trabajo Rutas de manejo

de materiales

Trabajos

14

15Considere una red conexa y no dirigida condos nodos especiales llamados origen ydestino. A cada ligadura (arco no dirigido) seasocia una distancia no negativa.

El objetivo es encontrar la ruta ms corta(la trayectoria con la mnima distancia total) delorigen al destino. Se dispone de un algoritmobastante sencillo para este problema.La esencia del procedimiento es que analiza todala red a partir del origen; identifica de manerasucesiva la ruta ms corta a cada uno de los nodosen orden ascendente de sus distancias (mscortas), desde el origen; el problema quedaresuelto en el momento de llegar al nodo destino.

16

1. Objetivo de la n-sima iteracin: encontrar el n-simo nodo ms cercano al origen. (Este paso serepetir para n=1,2, hasta que el n-simo nodoms cercano sea el nodo destino.)2. Datos para la n-sima iteracin: n-1 nodos mscercanos al origen (encontrados en las iteracionesprevias), incluida su ruta ms corta y la distancia desdeel origen. (Estos nodos y el origen se llaman nodosresueltos, el resto son nodos no resueltos.)3. Candidatos para el n-simo nodo ms cercano: Cadanodo resuelto que tiene conexin directa por unaligadura con uno o ms nodos no resueltos proporcionaun candidato, y ste es el nodo no resuelto que tiene laligadura ms corta. (Los empates proporcionancandidatos adicionales.)4. Clculo del n-simo nodo ms cercano: para cadanodo resuelto y sus candidatos, se suma la distanciaentre ellos y la distancia de la ruta ms corta desde elorigen a este nodo resuelto. El candidato con la distanciatotal ms pequea es el n-simo nodo ms cercano (losempates proporcionan nodos resueltos adicionales), y suruta ms corta es la que genera esta distancia.

17Ruta ms segura: Un egresado de MACconduce diariamente hacia su trabajo. Comoacaba de terminar un curso de OptimizacinEntera puede determinar la ruta ms corta.Desafortunadamente, la ruta seleccionada estmuy patrullada por la polica y a las multas pormanejar a alta velocidad podra ser que la ruta mscorta no sea la mejor eleccin. El chico decideentonces elegir una ruta que maximice laprobabilidad de no ser detenido por la polica. En lasiguiente tabla se colocan las probabilidades de noser detenido en ese segmento.Plantear la red y encontrar solucin.

18

SABAS QUE

El algoritmo de Dijkstra (que esuno de los mtodos utilizadospara obtener la ruta ms corta)se puede modificar paraencontrar el camino ms largo,as como en el problema de rutams segura donde se haya lamayor probabilidad.

19En trminos generales, el problema de flujomximo se puede describir de la siguientemanera:

1. Todo flujo a travs de una red conexa dirigida seorigina en un nodo, llamado fuente, y termina en otronodo llamado destino.2. Los nodos restantes son los nodos de trasbordo.3. Se permite el flujo a travs de un arco solo en ladireccin indicada por la flecha, donde la cantidadmxima de flujo est dada por la capacidad del arco.En la fuente, todos los arcos sealan hacia afuera. Enel destino, todos sealan hacia el nodo.4. El objetivo es maximizar la cantidad total de flujode la fuente al destino. Esta cantidad se mide encualquiera de las dos maneras equivalentes, esto es,la cantidad que sale de la fuente o la cantidad queentra al destino.

20A continuacin se menciona algunos tipos deaplicaciones comunes del problema del flujomximo.1. Maximizar el flujo a travs de la red de

distribucin de una compaa desde susfbricas hasta sus clientes.

2. Maximizar el flujo a travs de la red desuministros de una compaa deproveedores a las fbricas.

3. Maximizar el flujo de petrleo por unsistema de tuberas.

4. Maximizar el flujo de agua a travs de unsistema de acueductos

5. Maximizar el flujo de vehculos por unared de transporte.

En algunas de estas aplicaciones, el flujo a travsde la red se puede originar en ms de un nodo ytambin puede terminar en ms de uno, aunque elproblema de flujo mximo puede tener solo unorigen y un destino.

21

La aerolnea Aeromxico debe determinarcuntos vuelos de conexin diarios puedenconcretar entre Tijuana y Cancn.Los vuelos de conexin deben detenerse enGuadalajara y despus parar en el DF o en Toluca.Debido al espacio de aterrizaje limitado, la empresaest limitada a hacer el nmero de vuelos diariosentre los pares de ciudades que se muestran en lasiguiente tabla. Establezca un problema de flujomximo cuya solucin permite saber cmomaximizar el nmero de vuelos de conexin diariosentre Tijuana y Cancn.Plantear red y modelo de programacin lineal.

22

23Qu es?El problema del flujo de costo mnimo tieneuna posicin medular entre los modelos deoptimizacin de redes; primero, abarca unaclase amplia de aplicaciones y segundo, susolucin es muy eficiente.Toma en cuenta un flujo en una red con capacidadeslimitadas en sus arcos. Considera un costo (odistancia) para el flujo a travs de un arco. Puedemanejar varios orgenes (nodo fuente) y variosdestinos (nodos demanda) para el flujo, de nuevo concostos asociados.La razn por la que el problema de flujo de costomnimo se puede resolver de modo tan eficiente esque se puede formular como un problema deprogramacin lineal y es posible resolverlo con unaversin simplificada del mtodo Smplex llamadamtodo Smplex de redes.

24A continuacin se describe el

problema del flujo de costo mnimo:1. La red es una red dirigida y conexa.2. Al menos uno de los nodos es un nodofuente.3. Al menos uno de los nodos es un nodo dedemanda.4. El resto de los nodos son nodos de trasbordo.5. Se permite el flujo a travs de un arco slo en ladireccin indicada por la flecha, donde la cantidadmxima de flujo est dada por la capacidad delarco.

6. La red tiene suficientes arcos con suficientecapacidad para permitir que todos los flujosgenerados por los nodos fuente lleguen a los nodosde demanda.7. El costo del flujo a travs del arco es proporcionala la cantidad de ese flujo, donde se conoce el costopor unidad.8. El objetivo es minimizar el costo total de enviar elsuministro disponible a travs de la red parasatisfacer la demanda dada. (Un objetivo alternativoes maximizar la ganancia total del envo.)

25

Objetivo:

Tal vez el tipo ms importante de aplicacindel problema del flujo de costo mnimo es enla operacin de la red de distribucin de unacompaa.Este tipo de aplicacin siempre incluye determinarun plan para enviar bienes desde las fuentes(fbricas, etc.) a las instalaciones dealmacenamiento intermedias (segn se necesite) ydespus a los consumidores.Siendo as, el objetivo es minimizar el costo total demandar los recursos a travs de la red parasatisfacer la demanda dada.Por ejemplo, considere la red de distribucin de laInternational Paper Company (descrita en elnmero de marzo-abril de 1988 de Interfaces). Estacompaa es el mayor fabricante en el mundo depulpa, papel y productos de papel, lo mismo que unimportante productor de madera y triplay. Los nodosfuente en su red de distribucin son esos bosquesen los distintos lugares. Sin embargo, antes de quelos bienes de la compaa puedan llegar a losnodos de demanda (clientes), la madera debepasar por una larga secuencia de nodos detrasbordo.

26

Una trayectoria tpica por la red dedistribucin es:Bosques Maderera Aserradero Fbrica de papel Plantas Transformadoras Almacenes Consumidores

Aplicaciones comunes del problema del

flujo de costo mnimo:

Tipo de

aplicacin

Nodos

fuente

Nodos de

trasbordo

Nodos de

demanda

Operacin de

una red de

distribucin

Fuentes de

bienes

Almacenes

intermedios

Consumidores

Administracin

de desechos

slidos

Fuentes de

desechos

slidos

Instalaciones

de

procesamiento

Rellenos

Operacin de

una red de

suministros

Agentes de

ventas

Almacenes

intermedios

Instalaciones de

procesamiento

27Coordinacin

de mezclas de

productos en

plantas

Plantas Produccin

de un artculo

especifico

Mercado del

producto

especifico

Administracin

de flujo de

efectivo

Fuentes de

efectivo en

tiempos

especficos

Opciones de

inversin a

corto plazo

Necesidad

de efectivo

en tiempos

especficos

SABAS QUE.....

En el problema de flujo mximotodo que entra debe sexexactamente igual al que sale, nadase queda en los nodos detransbordo.

28Asignacin de empleados: La agencia deempleo tena un contrato para proporcionartrabajadores durante los 4 meses siguientesde acuerdo.Plantear la red.

Debido al cambio en la demanda podra ser mseconmico conservar ms trabajadores de losnecesarios durante determinado mes. El costo dereclutar y mantener a un trabajador est en funcinde su periodo de empleo.

29

SABAS QUE.....El flujo a costo mnimo es el caso ms general

de las redes de optimizacin.

30Pert (Programa Evolution and Review

Technique) Tcnica de Evaluacin y

Revisin de Programas.

.PERT fue desarrollado por cientficos de la oficinanaval de proyectos especficos en 1958, siendo losautores: Booz Allen y Hamilton y la divisin desistemas y armamentos de la empresa Lockheedpara el desarrollo del misil Polans.Al mismo tiempo la empresa Dupant desarrollaba elmtodo de la Ruta Critica (CPM) para controlar elmantenimiento de proyectos de plantas qumicas.Una diferencia principal entre PERT y CPM es quePERT es la metodologa y CPM es uno de los pasesdentro de PERT. Otra diferencia es que PERT utilizatiempos probabilsticos y CPM deterministas.

SABAS QUE.....En las redes de actividad los nodos representan momentos en el tiempo.

31Aplicaciones: Ingeniera de Software Construccin de inmuebles Desarrollo de procedimientos en una

empresa.Esta tcnica se utiliza para administrar proyectos.Un proyecto se define como la combinacin deactividades interrelacionadas que deben ejecutarseen cierto orden, antes de que el proyecto termine.Una actividad es un trabajo que requiere tiempo yrecursos.

PERT/CPM proporciona diversos elementos tilespara la administracin de proyectos: Duracin de un proyecto Actividades criticas del proyecto Tiempos de holgura de las actividades Herramientas para controlar y monitorear el

proceso del proyectoEsta tcnica apoya de los proyectos: Planeacin Programacin Control

32

En esta primera etapa se contempla:o Identificar las tareas (actividades)

individualmente que contrapone el proyectoo Obtener la estimulacin de tiempo de

conclusin de cada actividado Identificar las relaciones entre las

actividadeso Dibujar la red

Identificacin de las tareas:

Se deben enlistar considerando los siguientespuntos:1. Cada actividad tiene un inicio y final clases en el

contexto del proyecto2. La terminacin de cada actividad es necesaria

para la conclusin de un proyecto3. Se debe hacer responsable a una persona en

cada actividad

PlaneacinPlaneacinPlaneacinPlaneacin::::

33

Obtener los tiempos:En PERT se requieren tres valores paraobtener un valor esperado:a) Tiempo optimista (Si todo sale bien)b) Tiempo pesimista (Si todo sale mal)c) Tiempo ms probable (Si todo sale de

manera normal)Estos se combinan para obtener una frmulade aproximacin utilizando la distribucin Beta:

34Consiste en llevar el mtodo CPM (CriticalPath Method) Mtodo de la Ruta Crtica.Este mtodo se realiza directamente en la red y losresultados son: Clasificacin de actividades crticas y no crticas:

Una actividad es crtica si una demora en suinicio o en su fin causa una demora en lafinalizacin del proyecto (estas actividades sutiempo de holgura vale 0).

Ruta crtica: Cadena de actividades crticas lascuales conectan el nodo inicial y el nodoterminal. La duracin de esta cadena (la sumade las actividades criticas) define la duracin delproyecto. Puede haber ms de una cadenacrtica.

ProgramacinProgramacinProgramacinProgramacin::::

SABAS QUE.....

En las redes de los arcos representan la duracin de laactividad que va acompaado de la clave de dichaactividad.

35

El mtodo de la ruta crtica se basa en llevara cabo dos revisiones: Revisin hacia adelante: Con esta secalcula la duracin de un proyecto:

Tiempo prximo de iniciacin

Tiempo prximo de terminacin

Revisin hacia atrs: Calcula los tiempos deholgura y clasifica las actividades:

Tiempo ms lejano de iniciacin

Tiempo ms lejano de terminacin

36Proyecto: Construir una casa en semanas

RED:

Actividad Descripcin Predecesor b a m t Desviacin

estndar

A Cimientos --- 6 3 4 4.2 0.5

B Plomera y

electricidad

A 5 1 2 2.3 0.7

C Techos A 7 2 3 3.5 0.8

D Pintura externa A 3 5 1 1.3 0.4

E Pintura interna B, C 10 4 5 5.7 1.0

37

RUTA CRTICA:

38REVISIN HACIA ADELANTE:

REVISIN HACIA ATRS:

39El tiempo determinacin de un proyecto es untiempo esperado y este valor puede variar.

La distribucin de la duracin de un proyectose supone se distribuye normalmente.

Cmo se obtiene la desviacin estndar en unproyecto?- Se debe sumar las desviaciones estndar de cadaactividad crtica

ControlControlControlControl::::

El rango para la duracin del proyecto:

[13.4 2.3, 13.4 + 2.3]

[11.10, 15.70]

40

a) Cul es la probabilidad de cumplircon una fecha especfica de terminacin?

Por ejemplo Cul es la probabilidad enconstruir la casa en 15 semanas?

Primero se estandariza nuestra normal:

P (z 0.70) = 0.75 Probabilidad de terminar lacasa en 15 semanas

41

Cul es la probabilidad de construir la casaen 13 semanas?

Cul es la probabilidad de construir la casa en 19semanas?

P (z - 0.17) = 0.43

P (z 2.43) = 0.99

SABAS QUE.....

El anlisis de la ruta crtica se establecioficialmente en 1957 por la Seccin deInvestigacin Operativa de la Central ElectricityGenerating Board en Inglaterra que se utilizanpara gestionar un gran proyecto que requieretodo el rediseo de una planta de fabricacin.

42

b) Qu fecha de terminacin se puedecumplir con un nivel dado de confianza?

Por ejemplo Cul es la fecha de terminacincon una confianza de 95%?

z = 1.65

x = 17.20 Se construir la casa en 17.20semanas

43

Con una confianza del 85% cuando seterminara de construir la casa?

z = 1.04

Con una confianza del 20% cuando se terminarade construir la casa?

z = -0.81

x = 15.79 semanas

x = 11.54 semanas

44

Tipo de

problema

Caractersticas Planteamiento Mtodos

Reemplazo -Variable binaria

-Los nodos

representan

perodos en el

tiempo

-Los arcos

representan los

tiempos de

cambio

Xij=

min z= x12+ x13+ +x1n++ xm1+ xm2++

xmn

s.a

x12+ x13++ x1n=>1

x21+ x22++ x2n=>1

:

:

Xm1+ xm2++ xmn=>1

-Dijkstra

-Dijkstra

generalizado

Ruta ms

segura

-En lugar de costos

hay probabilidades

en los arcos

-Se multiplican las

probabilidades

Xij=

max z= x12+ x13+ +x1n++ xm1+ xm2++

xmn

s.a

x12+ x13++ x1n=>1

x21+ x22++ x2n=>1

:

:

Xm1+ xm2++ xmn=>1

-Dijkstra

-Dijkstra

generalizado

45

Mochila -Variable binaria

-En el arco se

coloca el valor del

articulo

-En el nodo se

coloca el artculo y

la capacidad

restante

Xij=

max z= x11+ x21+ +x2n++ xm1+

xm2++ xmns.a

x12+ x13++ x1n=>1

x21+ x22++ x2n=>1

:

:

Xm1+ xm2++ xmn=>1

-Dijkstra

-Dijkstra

generalizado

Planeacin de

produccin

-Variable binaria

-El costo total se

pone en el arco

-Los nodos

representan

momentos en el

tiempo

-Capacidad en

funcin a ofertas y

demandas

Xij=

min z= x12+ x13+ +x1n++ xm1+

xm2++ xmn

s.a

x12+ x13++ x1n=>1

x21+ x22++ x2n=>1

:

:

Xm1+ xm2++ xmn=>1

-Dijkstra

-Eliminacin de

circuitos negativo

-Mtodo simplex

Asignacin de

empleados

-Se manejan costos

y penalizaciones

-Las ofertas y

demandas se

manejan en funcin

a cada mes

Xij=

min z= x12+ x13+ +x1n++ xm1+

xm2++ xmn

s.a

x12+ x13++ x1n=>1

x21+ x22++ x2n=>1

:

:

Xm1+ xm2++ xmn=>1

-Eliminacin de

circuitos negativo

-Mtodo simplex

SABAS QUE.....

En el problema de flujo mximo todo que entra debe ser

exactamente igual al que sale, nada se queda en los nodos

de transbordo.

46

Mtodo Tipo de problema Caracterstica Ventajas y

Desventajas

Prim -Ruta ms corta -Empieza con un

nodo y analiza

arcos adyacentes

-Se tienen

exactamente n-1

iteraciones

-Encuentra arboles

de peso mnimo

-Fcil de aplicar

-Solo para

problemas

pequeos

-Se tiene n-1

iteraciones

Kruskal -Ruta ms corta -Enlista arcos y

selecciona los de

menor peso sin

hacer bucles

-Para redes sin

direccin

-se realizan ms

de n-1 iteraciones

-Resuelve

problemas

grandes

-Es ms preciso

que PRIM

-Se tiene que

programar

-Se pueden tener

muchas

iteraciones

Dijkstra -Ruta ms corta -Se obtiene la

arborescencia de

ruta ms corta

-Es para redes

dirigidas

-Solo para costos

positivos

-Etiqueta a

destiempo

-Fcil de

implementar

47

Dijkstra

generalizado

-Ruta ms corta -Equivalente a

simplex para ruta

ms corta

-No importa el

costo

-Arborescencia

de ruta ms corta

-Es ms preciso

-Acepta costos

negativos

-Muchas

iteraciones

Floyd -Ruta ms corta -Redes dirigidas

con cualquier

costo

-Ruta ms corta

entre todo par de

nodos

-Se tiene n

iteraciones

-Encuentra

cualquier ruta

ms corta

-Muchas

posibilidades

Ford-Fulkerson -Flujo mximo -Inicia saturando

arcos

-Etiqueta los

arcos con el flujo

-Equidad en el

flujo

-Se utiliza la

capacidad

mxima de los

arcos del nodo

inicial y el nodo

final

-Resulta un poco

difcil aplicar a

redes grandes

Flujo mnimo -Flujo a costo

mnimo

-Etiqueta arcos

saturando arcos

sobrepasando el

requerimiento

mnimo

-Satisface los

requerimientos

mnimos de todos

los arcos

-Similar a Ford-

Fulkerson

-Fcil de aplicar

a redes

pequeas

-Complicado

para redes

grandes

48

Eliminacin de

circuitos negativos

-Flujo a costo

mnimo

-Se aplica a una

red marginal

-Solo se aplica a

redes marginales

Ruta ms corta -Flujo a costo

mnimo

-Se aplica a una

red marginal

-Solo se aplica a

redes marginales

CPM -Redes de

actividad

-Se utiliza solo para

redes de actividad

-sirve para la

planeacin de

proyectos

-Revisa hacia atrs

y hacia adelante

-Muestra inicio y fin

de las actividades

-Fcil de

implementar

-Muestra tiempos

de holgura

-Indica tiempo ms

prximo y lejano de

inicio y fin de

actividades

SABAS QUE.....

En un inicio las redes de actividad como casi todos los

mtodos se implement inicialmente en el campo

militar

Algunos de los personajes ms importantes enlas redes de optimizacin son:

49

Edsger Wybe Dijkstra(1930-2002)

En su capacidad como herramienta, los computadores sern

slo un rizo sobre la superficie de nuestra cultura. En su

capacidad de desafo intelectual, no tienen precedente en la

historia de la humanidad.

Dijkstra en su discurso de recepcin del premio Turing, 1972.

El premio Turing otorgado por laACM (Association for ComputingMachinery, EEUU) es considerado elequivalente al premio Nobel de lacomputacin. El primero de ellos fueentregado en 1966 y hasta la fechadiez de nuestros prceres ya no nosacompaan. .Casualmente, cuatro de ellosfallecieron en un lapso menor a 45das:El 29 de Junio, Ole-Johan Dahl; el 16 de Julio, John Cocke; el 6 deAgosto, Dijkstra; y el 10 de Agosto, Kristen Nygaard. John Cocke fue unode los principales diseadores de las arquitecturas RISC. Ole-Johan yKristen fueron los desarrolladores de Simula, el precursor de los lenguajesde programacin orientados a objetos, tema del prximo mes. Hoydedicaremos estas lneas a Dijkstra, quin contribuy al desarrollo de lacomputacin en muchas reas distintas.

50

ContribucionesContribucionesContribucionesContribuciones::::Dijkstra escribi ms de 1300 artculos, peroindudablemente hay tres contribuciones cuyo impactoest presente en numerosos mbitos de la computacinmoderna:

Algoritmo para encontrar el camino ms corto en un grafo:este fue el primer problema de grafos que resolvi Dijkstra en1956 y publicado en 1959 por que en esa poca un algoritmoera difcilmente considerado un logro cientfico. Hoy en da,este algoritmo ha sido usado como la base para protocolosde enrutamiento en Internet, sistemas de posicionamientoglobal o simplemente para itinerarios de viaje.

Su aporte a la programacin estructurada. Dijkstra participen el comit que diseo Algol 60, el primer lenguaje deprogramacin estructurado, y lo promovi intensamentefomentando la verificacin formal de programas y laeliminacin del goto. En este tema fue autor y coautor devarios libros, adems de su artculo corto "Go To statementconsidered harmful" (La instruccin go to es consideradadaina) publicado en Communications of ACM en 1968, quees legendario.

51Algoritmo de Ford y Fulkerson:Algoritmo de Ford y Fulkerson:Algoritmo de Ford y Fulkerson:Algoritmo de Ford y Fulkerson:

LESTER RANDOLPH FORD, JR.

Naci el 23 de septiembre 1927, Houston.Es un americano matemtico especializado en redes deflujo problemas. l es el hijo del matemtico Lester R.Ford, padre.Papel de Ford con DR Fulkerson en el problema de flujomximo y el algoritmo de Ford-Fulkerson para resolverlo,publicado como un informe tcnico en 1954 y en undiario en 1956, estableci el mximo de flujo mnimo decorte teorema. Con Richard Bellman, Ford tambin hadesarrollado el algoritmo de Bellman-Ford paraencontrar los caminos ms cortos en grafos que tienenbordes negativamente ponderados.

52

DELBERT RAY FULKERSON

Naci el 14 de agosto de 1924.Fue un matemtico estadounidense que desarroll comoco-autor, y junto con Lester Randolph Ford, Jr., el Algoritmode Ford-Fulkerson, uno de los algoritmos ms utilizadospara computar el flujo mximo en una red de flujo.Fulkerson recibi su Ph.D. en la Universidad de Wisconsin-Madison en 1951. En 1956, su importante artculocientfico fue publicado.Desde 1979, la Sociedad de ProgramacinMatemtica (MPS) y la American MathematicalSociety (AMS) otorgan cada tres aos el Premio Fulkerson,para aquellos matemticos que hayancreado artculos importantes en el rea de la matemticadiscreta.Fulkerson muri el 10 de enero de 1976.

53

INFORMACIN: Optimizacin de Enteros y Modelos de Redes, Modelos de Redes,

Recuperado (06/Octubre/2014) dehttp://home.ubalt.edu/ntsbarsh/opre640S/SpanishIN.htm

Optimizacin de Redes, Instituto Tecnolgico de Tijuana, Recuperado(13/Octubre/2014) de:http://es.slideshare.net/herovalrey/optimizacion-de-redes

Biografa de Edsger Wybe Dijkstra, Universidad de Chile(13/Septiembre/2014), Recuperado de:http://users.dcc.uchile.cl/~rbaeza/inf/dijkstra.html

Lester Randolph Ford, Jr., Biografa, Recuperado(27/Septiembre/2014) de http://en.wikipedia.org/wiki/L._R._Ford,_Jr.

Delbert Ray Fulkerson, Biografa, Recuperado (27/Septiembre/2014)de http://es.wikipedia.org/wiki/D._R._Fulkerson

IMGENES: Modelos de Redes, Mtodos de solucin, Recuperado

(06/Octubre/2014) dehttp://arodriguez.blogs.upv.es/files/2008/12/redes_grafos.jpg

Lester Randolph Ford, Jr., Recuperado (27/Septiembre/2014)de http://www.tangrammit.com/images/INFORMS01web.jpg

Delbert Ray Fulkerson, Recuperado (27/Septiembre/2014) dehttp://arodrigu.webs.upv.es/grafos/lib/exe/fetch.php?media=delbertrayfulkerson_foto.jpg

Optimizacin de Redes, Instituto Tecnolgico de Tijuana, Recuperado(13/Octubre/2014) de:http://es.slideshare.net/herovalrey/optimizacion-de-redes

Universidad Nacional Autnoma de Mxico

Facultad de Estudios Superiores Acatln

Matemticas Aplicadas y Computacin

Elaborado (18/Octubre/2014) por: Ramrez Gonzlez Juan Francisco

Villeda Lira Dalia Itzel