Solución de problemas de programación dinámica y análisis de decisión
Enviado por Luis Avellaneda • 29 de Mayo de 2020 • Documentos de Investigación • 2.850 Palabras (12 Páginas) • 140 Visitas
Solución de problemas de programación dinámica y análisis de decisión.
Faiber Alberto Suárez Rodríguez
Eduard Jose Mendoza Garcia
Luis Alejandro Avellaneda Vasquez
Héctor Alberto Gómez Rocha
Fundación Universitaria Área Andina
Ingeniería de Sistemas
Investigación de operaciones II.
Bogotá
Mayo 2020
Introducción 3
Problemas a resolver 4
Problema 1: Faiber Suárez 4
Problema 2: Luis Alejandro Avellaneda 12
Problema 3: Eduard Mendoza 15
Problema 4: Héctor Gómez 18
Introducción
Cuando hablamos de investigación de operaciones, sabemos que en gran parte hacemos referencia a la toma de decisiones ya que este es un tema fundamental en el entorno organizacional como en la vida cotidiana, estas tomas de decisiones siempre están ligada a múltiples variables como; costos, tiempos, personas, entre otros; la cual si no analizamos bien, pueden convertirse en una tarea más compleja, en muchas circunstancias de la vida profesional se deja al azar, a la intuición o en manos de otros estas tomas de decisiones, quedando con la incertidumbre si la decisión tomada fue la mejor. lo que nos brinda la Investigación de operaciones apoyada de las matemáticas y la programación contribuye a que, nosotros como tomadores de decisiones podamos hacerlo de una manera técnica donde nada queda al azar y donde los podemos poner en práctica el mejor escenario y de esta manera apoyar la continuidad y crecimiento profesional como el de las organizaciones.
Problemas a resolver
Problema 1: Faiber Suárez
[pic 2]
Grafo del problema de la diligencia.
[pic 3]
Tabla resumen de los cálculos de la etapa 3 o segunda iteración del problema de
la diligencia.
[pic 4]
Tabla resumen de los cálculos de la etapa 2 o tercera iteración del problema de la
diligencia
[pic 5]
Tabla resumen de los cálculos de la etapa 1 o cuarta iteración del problema de la
diligencia.
Refiriéndonos al problema de la diligencia, abordado en el referente de pensamiento del presente eje, el grafo anterior muestra los puntos origen, destino, puntos intermedios y costos de las pólizas por etapas. Como resultado del análisis se llegó a las anteriores tablas de resumen correspondiente a diferentes etapas (o iteraciones). Con base en esto y la información correspondiente a programación dinámica, consignada en el referente 1, se pide al equipo de estudiantes lo siguiente:
- Verificar y mostrar los cálculos que se resumen en la tabla teniendo en cuenta el grafo y definiciones propias de la programación dinámica.
- Verificar y mostrar los resultados que se resumen en la tabla de tercera iteración
- Verificar y mostrar los resultados de la Tabla correspondientes a la primera etapa o cuarta iteración.
Desarrollo:
Según lo analizado en el documento referente, para solucionar este tipo de problemas se podría tomar cada una de las rutas y sumar sus costos y de esta manera determinar la ruta más óptima, esto se podría analizar como una tarea fácil para el ejercicio tomando un pequeño grupo de variables, pero si este ejercicio aplica como un caso real en nuestra profesión donde se pueden tener miles de variables, sería muy tardado y quizás algo imposible realizarlo de esta manera, pero con la programación dinámica y haciendo uso de algoritmos y posiblemente automatizando estas tareas en un programa, estos desarrollos pueden realizar en menos tiempo.
De acuerdo a lo establecido el grafo lo debemos fragmentar en subproblemas más pequeños, encontrando la ruta más corta para este y hallando los resultados podremos calcular las rutas más cortas para los siguientes subprogramas y así sucesivamente hasta llegar a la(s) rutas(s) óptimas.
Variables:
De acuerdo al referente las variables que se utilizan en el desarrollo de este tipo de problemas son:
n= el número de etapas para este caso son 4 = 1, 2, 3, 4,
= nodo origen[pic 6]
nodo destino partiendo de S[pic 7]
= costo global de la mejor decisión[pic 8]
= valor de que hace mínimo al valor de [pic 9][pic 10][pic 11]
= valor mínimo de [pic 12][pic 13]
El objetivo del ejercicio con este método es partiendo de la última etapa hallar la mejor opción, luego la etapa , la etapa y finalmente la etapa , como se observa el problema va desde el final, hasta el principio.[pic 14][pic 15][pic 16][pic 17]
Primera iteración - cuarta etapa
[pic 18]
En esta etapa el viajero sólo tiene 1 opción de llegada dos nodos de origen S = H, I con valores respectivamente, representado en la siguiente tabla:[pic 19][pic 20]
S | [pic 21] | [pic 22] |
H | 3 | J |
I | 4 | J |
Tabla #1
Segunda Iteración - Tercera Etapa
[pic 23]
En esta etapa el viajero tiene los anteriores escenarios y de estos puede llegar a los nodos H o I, sobre las flechas se observa los diferentes costos, y sobre H e I están los costos de llegar al nodo final J.[pic 24]
[pic 25] | [pic 26] | [pic 27][pic 28][pic 29] | [pic 30] | [pic 31] | ||
H | I | H | I | |||
E | 1 | 4 | 4 | 8 | 4 | H |
F | 6 | 3 | 9 | 7 | 7 | I |
G | 3 | 3 | 6 | 7 | 6 | H |
Tabla #2
A manera de ilustración y para mostrar de donde salen los datos se explica los resultados de S= E
- E.H=1 ,corresponde al valor de la ruta.[pic 32]
- E.I=4 ,corresponde al valor de la ruta.[pic 33]
- E,H =4 corresponde a la suma de E,H=1 + (dato que se trae de la tabla 1); 3+1=4[pic 34][pic 35][pic 36][pic 37]
- E,I= 8 E,I= 8 corresponde a la suma de E.I=4 +(dato que se trae de la tabla 1; 4+4=8[pic 38][pic 39][pic 40][pic 41]
- =4, este valor corresponde a la ruta de menor valor correspondiente para el nodo y que será utilizado en la siguiente etapa.[pic 42]
- =H, corresponde al nodo con menor valor y que será utilizado en la siguiente etapa.[pic 43]
Estos pasos anteriores se realizan para cada nodo (S).
...