Modelo De Optimizacion- Problema De La Diligencia

La Familia Vargas decide hacer un viaje con vehículo particular desde su ciudad (A) hacia la ciudad (I), para aquel viaje dispone de rutas en las cuales se encontrará con la posibilidad de visitar algunas ciudades, las cuales pueden ser B,C,D,E,F,G,H, por lo que deciden realizar aquellas visitas, tomando en cuenta el menor gasto en combustible( en litros), las ramificaciones de las rutas juntocon el gasto que implica cada recorrido entre las ciudades se muestran en el siguiente gráfico. ¿Cuál es la ruta que minimiza el costo total del viaje?, tomando en cuenta que la satisfacción de la visita son iguales en todas las ciudades, al igual que la estadía no afecta en la decisión de la ruta.











Cuando la familia tiene solo una etapa por recorrer n=4se tiene f4*(S)=fn (s,I)=Cx ,I la solución al problema para n=4 es


S f4*(S) X4*
G 41 I
H 53 I








En n=3
a) b) c)









Cuando la familia tiene dos etapas por recorrer (n=3), el procedimiento de resolución requiere de los siguientes cálculos. Si seencuentra en D como se describe en el primer diagrama (a) debe ir al estado G o H a un costo inmediato de CD,G=21 o costo CD,H=51 respectivamente. Si elige el estado G el costo adicional mínimo al llegar esta dado en la anterior como f4*(G)=41de modo que el costo total de esta decisión seria 21+41=62, de igual manera se elige el estado H, el costo total es 51+53=104 que es mayor, por lo tanto sedebería escoger el estado G, X3*=G, ya que da el costo mínimo f3*(D)=62; para obtener los resultado mostrados en la tabla se debe hacer un procedimiento similar al ya nombrado en los nodos E y F:



X3
S f3 *(S3, X3)= C SX3+ f3+1 *( Xn3) f3*(S) X3*
G H
D 62 104 62 G
E 114 95 95 I
F 81 93 81 G






En n=2
Para la resolución de n=2 se obtiene de lasiguiente forma. En este caso f2 *(S2, X2)= C SX2+ f2+1 *( X2). Por ejemplo, suponga que la familia se encuentra en el estado B como se muestra en el diagrama (d) ahora debe ir al estado D, E o F con un costo inmediato de CBD=84, CBE=52, CBF=75. Al llegar ahí, el costo adicional mínimo hasta llegar al destino esta dado en la tabla anterior (n=3), como f3*(D)=62, f3*(E)=95 o f3*(F)=81, como semuestra en d y e:
d) e)










Por ejemplo para las tres alternativas que dispone B se puede observar en las ecuaciones:
X2=D: f2 (B, D)= C B,D+ f2+1 *( D)=84+62=146
X2=E: f2(B, E)= C B,E+ f3*( E)=52+95=147
X2=F: f2 (B, F )= C B,F+ f3 *( F)=75+81=168
El mínimo de estos números es 146, por lo que el costo total mínimo desde el estado Bal final es f2*(B)=146 y el destino inmediato debe ser D. Al hacer un cálculo similar cuando se comienza desde el estado C se obtienen los siguientes resultados:

X2
S f2 *(S2, X2)= C SX2+ f2+1 *( X2) f2*(S) X2*
D E F
B 146 147 168 146 D
C 105 146 145 105 F
En n=1
de la misma manera que en los casos anteriores se debe de realizar los cálculos, pero con ladiferencia que solo hay un inicio posible s=A, como se muestra en el siguiente diagrama.










f1*(A, B)= C A,B+ f2 *( B)=146+33=179
f1*(A, C)= C A,C+ f2 *( C)=105+52=157

Como el mínimo es 157 f1*(A)=157 y X1*=C como se muestra en la siguiente tabla:



X1
S f1*(S1, X1)= C SX1+ f1+1 *( X1) f1*(S) X1*
B C
A 179 157 157 C


En este punto se puedeidentificar la solución óptima a partir de las cuatro tablas. Los resultados del problema para n=1 indican que la familia debe elegir como primer destino el estado C. con n=2 el resultado para s=C es X2*=F, este resultado conduce para el problema n=3, que da X3*=G para s=F y el problema con n=4 indica que X4*=I para s=G. así la ruta optima es A-C-F-G-I como lo muestra el siguiente gráfico:...