Programacion lineal

ALEJANDRA OSORIO ARVISU

INVESTIGACION DE OPERACIONES

EJEMPLOS DE PROBLEMA DE LA RUTA MAS CORTA EJEMPLO 1
Supongamos que se desea determinar la ruta que toma menos tiempo entre dos puntos dela ciudad (Pe. Casa y Oficina), es decir la trayectoria o conjunto de ramas que minimice el tiempo. (incluso combustible y otros desgastes). No siempre la ruta más corta es la más directa. Para estohacemos una lista de los posibles caminos o rutas a tomar y de ser posible dibujamos un grafo equivalente, anotando el tiempo en minutos de cada lado de la red. Si el número de ruta a evaluar es muygrande, el procedimiento es muy ineficiente. Lo que se necesita es un procedimiento sistemático que nos permita determinar la ruta más corta (de menor tiempo) entre dos puntos dados sin tener queenumerar todas las rutas posibles entre esos dos puntos.

Existen dos algoritmos básicos que solucionan este problema, en redes cíclicas y aciclicas, el algoritmo cíclico es más general, porque incluyeel caso aciclico, sin embargo el algoritmo aciclico es más eficiente porque necesita menos cálculos.

ISC

ALEJANDRA OSORIO ARVISU EJEMPLO 2

INVESTIGACION DE OPERACIONES

Considere elsiguiente grafo de red, calcule la distancia más corta desde el punto A al G.

La siguiente tabla muestra la secuencia de cálculos que contienen la solución final, las columnas son los nodos y lasfilas las distancias calculadas y el rótulo.
A A B C D E F G Rot [A] [A,B] [B,C] [A,D] [C,E] [C,F] 0 B 0+4=4 0 5+1=6 C 0+6=6 4+1=5 0 5+2=7 10+5=15 5+2=7 0 0 9+1=10 D 0+5=5 4+7=11 5+5=10 5+4=9 5+5=1010+1=11 0 10+6=16 9+8=17 0 [E,G] E F G

Nota: si el gráfo es dirigido, se describen en la tabla sólo aquellos flujos factibles. Para encontrar la ruta óptima se procede hacia atrás desde los nodosutilizando la información de los rótulos. [E,G], [C,E], [B,C], [A,B] Para el ejemplo la ruta óptima es: [A,B], [B,C], [C,E], [E,G], note que [A,B], [B,C], [C,F], [F,E], [E,G] también es óptima.

ISC...