Ejercicios De Programación Dinámica

1221 palabras 5 páginas
1.- Un Ingeniero Forestal, requiere saber: I) Cuál es el costo mínimo, y II)Cuál es la ruta con ese costo mínimo, para ir desde su oficina hasta el lugar donde está la cosecha. En su camino debe pasar por 3 sectores o ciudades antes de llegar a su destino, y lugares posibles en esos sectores o ciudades. Las posibles rutas, y el costo asociado por Kms. de distancia y otros en $, se ven en el siguiente esquema:

Cálculos | | n = 4 | S \ X4 | 13 | F4* | X4* | | | | 9 | 12 | 12 | 13 | | | | 10 | 16 | 16 | 13 | | | | 11 | 15 | 15 | 13 | | | | 12 | 14 | 14 | 13 |

n = 3 | S \ X3 | 9 | 10 | 11 | 12 | F3* | X3* | | 6 | 3+12=15 | 2+16=18 | 1+15=16 | 3+14=17 | 15 | 9 | | 7 | 4+12=16 | 1+16=17 | 4+15=19 | 6+14=20 |
…ver más…
cargamentos \ destinos | 1 | 2 | 3 | 4 | 0 | 0 | 0 | 0 | 0 | 1 | 5 | 6 | 4 | 7 | 2 | 11 | 10 | 12 | 10 | 3 | 15 | 16 | 17 | 14 | 4 | 21 | - | 22 | 23 |

Los cálculos:

n = 4 | S \X3 | 0 | 1 | 2 | 3 | 4 | F4* | X4* | | 0 | 0 | - | - | - | - | 0 | 0 | | 1 | 0 | 7+0=7 | - | - | - | 7 | 1 | | 2 | 0 | 7+0=7 | 10 | - | - | 10 | 2 | | 3 | 0 | 7+0=7 | 10 | 14 | - | 14 | 3 | | 4 | 0 | 7+0=7 | 10 | 14 | 23 | 23 | 4 |

n =3 | S \ X3 | 1 | F3* | X3* | | 1 | 4+ 0 = 4 | 4 | 1 | | 2 | 4+ 7 =11 | 11 | 1 | | 3 | 4+10=14 | 14 | 1 | | 4 | 4+14=18 | 18 | 1 | | 5 | 4+23=27 | 27 | 1 |

n = 2 | S\X2 | 0 | 1 | 2 | 3 | F2* | X2* | | 1 | 0 + 4 = 4 | - | - | - | 4 | 0 | | 2 | 0+11=11 | 6+4=10 | - | - | 11 | 0 | | 3 | 0+14=14 | 6+11=17 | 10+4=14 | - | 14 | 1 | | 4 | 0+18=18 | 6+14=20 | 10+11=21 | 16+ 4=20 | 21 | 2 | | 5 | 0+27=27 | 6+18=24 | 10+14=24 | 16+11=27 | 27 | 0 - 3 |

n = 1 | S \ X1 | 0 | 1 | 2 | 3 | 4 | F1* | X1* | | 4 | 0+21=21 | 5+14=19 | 11+11=22 | 15+4=19 | --- | 22 | 2 | | 5 | 0+27=27 | 5+21=26 | 11+17=28 | 15+11=26 | 21+4=25 | 28 | 2 |

Respuesta:
A) Si envía 4 cargamentos, el óptimo es: MM$ 22, y la solución óptima es: X1 = 3 ; X2 = 0 ; X3= 1; X4= 0; | | X1 = 2 | | X2 = 0 | | X3= 1 | | X4= 1 | | La ruta óptima es: | 4 | | 2 | | 2 | | 1 | | 0 | | | 11 | | 0 | | 4 | | 7 | |
Es decir: Al destino-1 debe enviar 2 cargamentos, al destino-2 debe enviar 0

Documentos relacionados

  • Programacion Dinamica Deterministica
    3658 palabras | 15 páginas
  • Programacion Dinamica Deterministica
    3642 palabras | 15 páginas
  • Taller Analisis y Diseño de Algoritmos
    788 palabras | 4 páginas
  • Apuntes de php
    1589 palabras | 7 páginas
  • Ensayo Entrenamiento Deportivo
    1723 palabras | 7 páginas
  • Historia De La Planeacion En Mexico
    1301 palabras | 6 páginas
  • Localizacion
    1818 palabras | 8 páginas
  • guia de programacion basica conalep
    18679 palabras | 75 páginas
  • 1.3. Antecedentes y Clasificación de los métodos cuantitativos en la producción
    677 palabras | 3 páginas
  • Informe sobre programación neurolingûistica
    3643 palabras | 15 páginas