jueves, 22 de mayo de 2008

introduccion




CPM COSTOS.

















PERT PROBABILISTICO









RUTA CRITICA:










PROBLEMA DEL CAMINO MÍNIMO.





REDES DE TRANSPORTE. (problema de ruta corta)

Algoritmo de DANTZIG para el problema de la ruta mas corta de una red.
Paso 1.
Construyase una lista muestra, tabulando bajo cada nodo en un orden ascendente según la distancia, las ramas o arcos que llegan a el. Cada arco bajo un nodo dado se escribe con ese nodo como su primer nodo. Omitase de la lista cualquier arco que tenga la fuente como un segundo nodo o que tenga al destino como su primer nodo.
Paso 2.
Marquese con un asterisco a la fuente y asignesele el valor cero.localicese el arco mas corto que coincida con la fuente y encierrese en un circulo. Márquese con un asterisco al segundo nodo de este arco y asignese a este nodo un valor igual a la distancia del arco. Eliminandose de la lista muestra todos aquellos otros arcos que tengan como segundo nodo al que se acaba de marcar con asterisco.
Paso 3.
Si el nodo se acaba es el destino, continuese en el paso 5, en el caso contrario continúese en el paso 4.
Paso 4.
Considerese en la lista muestra actual, todos los nodos marcados con asterisco que tenga bajo ellos arcos encerrados en circulo. Para cada uno de ellos agreguese el valor asignado al nodo, a la distancia del arco sin circulo mas corta bajo él. Denotese a la menor de estas sumas y encierrese en un circulo al arco cuya distancia contribuyo a M. Marquese con un asterisco con un asterisco al segundo nodo de este arco y signesele el valor M. Eliminense de la lista muestra todos los otros arcos que tengan al nodo que acaba de marcarse con asterisco, como segundo nodo. Continuese en el caso 3.
Paso 5.
Una ruta mas corta se obtiene recursivamente, iniciando con el destino incluyendo en la ruta cada arco encerrado en circulo, cuyo nodo pertenezca a la ruta.

Problema:
La dirección del parque nacional ha reservado a este para pasear y acampar. No se permite la entrada de los automóviles al parque, pero existe un sistema de caminos angostos para tranvías y jeeps conducidos por los guardabosques en la figura se muestra este sistema de caminos sin (curvas), en donde 0 es la localización de la entrada al parque, los otros nodos designan la localización de estaciones de guardabosques (y otras instalaciones). Los números en los arcos dan las distancias en estos caminos sinuosos en Km.

El parque contiene un paisaje maravilloso en la estación T; se usa en numero pequeño de tranvías para transportar visitantes de la entrada del parque a la estación T, y de regreso, para quienes deseen contemplar este paisaje sin tener que caminar.
El administrador del parque desea determinar cual ruta de entrada a la estación T, tiene la distancia total menor, para la operación de los tranvías.












La ruta mas corta es 0-->A->B->E->D->T con 13 Km.Ó 0->A->B->D->T CON 13 Km . Soluciones múltiples.