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.


domingo, 20 de abril de 2008

MÉTODO DUAL


A cualquier problema que llamamos primal tiene mas restricciones que variables, esto simplifica la solución porque el problema se representa como un problema dual y se maneja con menos restricciones.

Esto es:

1.- si el primal se refiere a maximizar, el problema dual sera minimizar.

2.- los coeficientes de la funcion objetivo del primal seran los coeficientes del vector de disponibilidad de recursos en el dual.

3.- asi, los coeficientes del vector disponibilidsd de recursos del problema primal seran los coeficientes de la funcion objetivo (vector costos, precios o utilidad) en el programa dual.

4.- los coeficientes d e las restricciones en el primal ( transpuesta de la matriz), sera la matriz de los coeficientes tecnológicos en el dual.

5.- los signos de desigualdad del problema dual son contrarios a los del primal.

6.- las variables “x” del primal, se convierten en nuevas variables “y” en el dual.




1.- considerando el siguiente problema primario, calcular su modelo dual.

Sea máx. = Z= 3x + 5y


Ponemos los coeficientes disponibilidad en forma de vector columna ( matriz) primal




y estos se convierten en vector, horizontal o vertical ( matriz fila ) transpuesta; esto es

Hacemos las restricciones del primal en forma de matriz





Por lo tanto su transpuesta Dual Sera:




Y al maximizar: