Unidad 3 by xJuan Carlosxx on Scribd
viernes, 21 de junio de 2019
Preguntas diagrama de arbol
¿Qué es un Diagrama de Árbol?
Un diagrama de árbol o árbol de probabilidad es una herramienta que se utiliza para determinar si en realidad en el cálculo de muchas opciones se requiere conocer el número de objetos que forman parte del espacio muestral, estos se pueden determinar con la construcción de un diagrama de planta.
¿Para que se usa un Diagrama de Árbol?
Los diagramas en árbol son especialmente útiles para resolver problemas con experimentos compuestos, es decir, aquellos donde realizamos más de un experimento aleatorio.
Menciona experimentos donde se pueda usar el diagrama de Árbol.
Algunos ejemplos de experimentos compuestos son: tirar dos monedas al aire, y mirar si salen dos caras, contar si hay dos mujeres de entre tres hijos, sacar dos bolas de una urna, y mirar si hay una roja y una azul.
¿Cómo se construye un Diagrama de Árbol?
Para la construcción de un diagrama en árbol se partirá poniendo una rama para cada una de las posibilidades, acompañada de su probabilidad. Cada una de estas ramas se conoce como rama de primera generación.
¿Cuál es el principio que se usa en un Diagrama de Árbol?
Existe un principio sencillo de los diagramas de árbol que hace que éstos sean mucho más útiles para los cálculos rápidos de probabilidad: multiplicamos las probabilidades si se trata de ramas adyacentes (contiguas)
Menciona las características de un Diagrama de Árbol.
Un diagrama de árbol parte de lo general y va hacia lo específico, es decir, la base es el problema y las ramificaciones son los niveles subsecuentes o causas.
Un diagrama de árbol es útil en la construcción de agrupación, bien sean combinaciones, variaciones o permutaciones.
¿Cómo crear un Diagrama de Árbol experimental?
En la construcción de un diagrama en árbol se comienza colocando una rama para cada una de las posibilidades y se acompaña de su respectiva probabilidad, estas ramas son conocidas como ramas de primera generación.
Al final de cada ramificación de primera generación, a la vez se constituye un nudo, del cual salen nuevas ramas, estas se conocen a modo de ramas de segunda generación
¿Cómo se caracteriza un Diagrama de Árbol de decisión?
Un diagrama de árbol de decisión se caracteriza por no tener demasiados elementos, los elementos clave se llaman nodos y se representan con un círculo o un cuadrado, las ramas son líneas que conectan los nodos y otras ramas hasta alcanzar el resultado deseado.
¿Que utilidad tiene esta herramienta para las empresas?
Las empresas utilizan este método en diferentes procesos y procedimientos, en virtud de que permiten identificar las acciones, tareas y decisiones que son necesarias para desarrollar soluciones y mejoras en el rendimiento y eficiencia de la misma.
¿Qué utilidad tiene esta herramienta en la vida cotidiana?
En la vida misma se pueden aplicar los diagramas de árbol, como una herramienta a la hora de elegir, combinar o desechar algunas opciones que se nos presentan ante sucesos, eventualidades o problemas.
Un diagrama de árbol o árbol de probabilidad es una herramienta que se utiliza para determinar si en realidad en el cálculo de muchas opciones se requiere conocer el número de objetos que forman parte del espacio muestral, estos se pueden determinar con la construcción de un diagrama de planta.
¿Para que se usa un Diagrama de Árbol?
Los diagramas en árbol son especialmente útiles para resolver problemas con experimentos compuestos, es decir, aquellos donde realizamos más de un experimento aleatorio.
Menciona experimentos donde se pueda usar el diagrama de Árbol.
Algunos ejemplos de experimentos compuestos son: tirar dos monedas al aire, y mirar si salen dos caras, contar si hay dos mujeres de entre tres hijos, sacar dos bolas de una urna, y mirar si hay una roja y una azul.
¿Cómo se construye un Diagrama de Árbol?
Para la construcción de un diagrama en árbol se partirá poniendo una rama para cada una de las posibilidades, acompañada de su probabilidad. Cada una de estas ramas se conoce como rama de primera generación.
¿Cuál es el principio que se usa en un Diagrama de Árbol?
Existe un principio sencillo de los diagramas de árbol que hace que éstos sean mucho más útiles para los cálculos rápidos de probabilidad: multiplicamos las probabilidades si se trata de ramas adyacentes (contiguas)
Menciona las características de un Diagrama de Árbol.
Un diagrama de árbol parte de lo general y va hacia lo específico, es decir, la base es el problema y las ramificaciones son los niveles subsecuentes o causas.
Un diagrama de árbol es útil en la construcción de agrupación, bien sean combinaciones, variaciones o permutaciones.
¿Cómo crear un Diagrama de Árbol experimental?
En la construcción de un diagrama en árbol se comienza colocando una rama para cada una de las posibilidades y se acompaña de su respectiva probabilidad, estas ramas son conocidas como ramas de primera generación.
Al final de cada ramificación de primera generación, a la vez se constituye un nudo, del cual salen nuevas ramas, estas se conocen a modo de ramas de segunda generación
¿Cómo se caracteriza un Diagrama de Árbol de decisión?
Un diagrama de árbol de decisión se caracteriza por no tener demasiados elementos, los elementos clave se llaman nodos y se representan con un círculo o un cuadrado, las ramas son líneas que conectan los nodos y otras ramas hasta alcanzar el resultado deseado.
¿Que utilidad tiene esta herramienta para las empresas?
Las empresas utilizan este método en diferentes procesos y procedimientos, en virtud de que permiten identificar las acciones, tareas y decisiones que son necesarias para desarrollar soluciones y mejoras en el rendimiento y eficiencia de la misma.
¿Qué utilidad tiene esta herramienta en la vida cotidiana?
En la vida misma se pueden aplicar los diagramas de árbol, como una herramienta a la hora de elegir, combinar o desechar algunas opciones que se nos presentan ante sucesos, eventualidades o problemas.
martes, 11 de junio de 2019
Problema del agente viajero
En el Problema del Agente Viajero - TSP (Travelling Salesman Problem), el objetivo es encontrar un recorrido completo que conecte todos los nodos de una red, visitándolos tan solo una vez y volviendo al punto de partida, y que además minimice la distancia total de la ruta, o el tiempo total del recorrido.
Este tipo de problemas tiene gran aplicación en el ámbito de la logística y distribución, así como en la programación de curvas de producción.
El problema del agente viajero tiene una variación importante, y esta depende de que las distancias entre un nodo y otro sean simétricas o no, es decir, que la distancia entre A y B sea igual a la distancia entre B y A, puesto que en la práctica es muy poco probable que así sea.
La cantidad de rutas posibles en una red está determinada por la ecuación:
(n-1)!
Es decir que en una red de 5 nodos la cantidad de rutas probables es igual a (5-1)! = 24, y a medida que el número de nodos aumente la cantidad de rutas posibles crece factorialmente. En el caso de que el problema sea simétrico la cantidad de rutas posibles se reduce a la mitad, ( (n-1)! ) / 2 Lo cual significa un ahorro significativo en el tiempo de procesamiento de rutas de gran tamaño.
MÉTODOS DE SOLUCIÓN:
La complejidad del cálculo del problema del agente viajero ha despertado múltiples iniciativas por mejorar la eficiencia en el cálculo de rutas. El método más básico es el conocido con el nombre de fuerza bruta, que consiste en el cálculo de todos los posibles recorridos, lo cual se hace extremadamente ineficiente y casi que se imposibilita en redes de gran tamaño. También existen heurísticos que se han desarrollado por la complejidad en el cálculo de soluciones óptimas en redes robustas, es por ello que existen métodos como el vecino más cercano, la inserción más barata y el doble sentido. Por último se encuentran los algoritmos que proporcionan soluciones óptimas, como el método de branch and bound (ramificación y poda), que trabaja el problema como un algoritmo de asignación y lo resuelve por
MÉTODO DE FUERZA BRUTA
El método de la fuerza bruta no implica la aplicación de ningún algoritmo sistemático, tan solo consiste en explorar todos los recorridos posibles. Considerando la siguiente red simétrica, los caminos posibles se reducen a la mitad:
Posibles rutas
A - B - D - C - A = 9 + 15 + 4 + 7 = 35 km
A - B - C - D - A = 9 + 10 + 4 + 8 = 31 km
A - C - B - D - A = 7 + 10 + 15 + 8 = 40 km
Rutas simétricas
A - D - C - B - A = 8 + 4 + 10 + 9 = 31 km
A - C - D - B - A = 7 + 4 + 15 + 9 = 35 km
A - D - B - C - A = 8 + 15 + 10 +7 = 40 km
MÉTODO DEL VECINO MÁS CERCANO
El método del vecino más cercano es un algoritmo heurístico diseñado para solucionar el problema del agente viajero, no asegura una solución óptima, sin embargo suele proporcionar buenas soluciones, y tiene un tiempo de cálculo muy eficiente. El método de desarrollo es muy similar al utilizado para resolver problemas de árbol de expansión mínima.
El método consiste en una vez establecido el nodo de partida, evaluar y seleccionar su vecino más cercano. En este caso:
En la siguiente iteración habrá que considerar los vecinos más cercanos al nodo C (se excluye A por ser el nodo de origen):
En la siguiente iteración los vecinos más cercanos de D serán C, con quien ya tiene conexión, A quién es el nodo de origen y B, por esta razón B se debe seleccionar por descarte. Al estar en B todos los nodos se encuentran visitados, por lo que corresponde a cerrar la red uniendo el nodo B con el nodo A, así entonces la ruta solución por medio del vecino más próximo sería A, C, D, B, A = 7, 4, 15, 9 = 35 km.
Este es un caso en el que a pesar de tener una red compuesta por pocos nodos, el método del vecino más cercano no proporciona la solución óptima, la cual calculamos con el método de fuerza bruta como 31 km.
Preguntas:
1°-¿Cual es el objetivo del Problema del gente Viajero?
El objetivo es encontrar un recorrido completo que conecte todos los nodos de una red, visitándolos tan solo una vez y volviendo al punto de partida.
2°-¿Este tipo de problemas en que ámbito se aplica?
Este tipo de problemas tiene gran aplicación en el ámbito de la logística y distribución, así como en la programación de curvas de producción.
3°-Menciona los métodos que conoces para solucionar el problema.
-Método de Fuerza Bruta
-Método del vecino mas cercano
-Método de Branch and Bound
4°-¿En que consiste el método de Fuerza Bruta?
El método de la fuerza bruta no implica la aplicación de ningún algoritmo sistemático, tan solo consiste en explorar todos los recorridos posibles.
5°-¿En que consiste el método del vecino mas cercano?
El método de desarrollo es muy similar al utilizado para resolver problemas de árbol de expansión mínima.
6°-¿Como es el origen del Agente Viajero?
El origen de los problemas del agente viajero no esta claro.Una guía para agentes viajeros de 1832 menciona el problema e incluye ejemplos de viajes a traves de Alemania y Suiza.
7°-¿Qué es el método del vecino mas cercano?
El método del vecino más cercano es un algoritmo heurístico diseñado para solucionar el problema del agente viajero, no asegura una solución óptima, sin embargo suele proporcionar buenas soluciones, y tiene un tiempo de cálculo muy eficiente.
8°-¿En que consiste el método del vecino mas cercano?
El método consiste en una vez establecido el nodo de partida, evaluar y seleccionar su vecino más cercano.
9°-Descripción el Agente Viajero.
En el problema se presentan N! rutas posibles, aunque se puede simplificar ya que dada una ruta nos da igual el punto de partida.
10°-¿Que nos proporciona el método de Branch and Bound?
El método de branch and bound(ramificación y poda), nos proporciona una solución óptima del problema del agente viajero, calculando mediante el algoritmo simplex la solución del modelo.
El problema del agente viajero tiene una variación importante, y esta depende de que las distancias entre un nodo y otro sean simétricas o no, es decir, que la distancia entre A y B sea igual a la distancia entre B y A, puesto que en la práctica es muy poco probable que así sea.
La cantidad de rutas posibles en una red está determinada por la ecuación:
(n-1)!
Es decir que en una red de 5 nodos la cantidad de rutas probables es igual a (5-1)! = 24, y a medida que el número de nodos aumente la cantidad de rutas posibles crece factorialmente. En el caso de que el problema sea simétrico la cantidad de rutas posibles se reduce a la mitad, ( (n-1)! ) / 2 Lo cual significa un ahorro significativo en el tiempo de procesamiento de rutas de gran tamaño.
MÉTODOS DE SOLUCIÓN:
La complejidad del cálculo del problema del agente viajero ha despertado múltiples iniciativas por mejorar la eficiencia en el cálculo de rutas. El método más básico es el conocido con el nombre de fuerza bruta, que consiste en el cálculo de todos los posibles recorridos, lo cual se hace extremadamente ineficiente y casi que se imposibilita en redes de gran tamaño. También existen heurísticos que se han desarrollado por la complejidad en el cálculo de soluciones óptimas en redes robustas, es por ello que existen métodos como el vecino más cercano, la inserción más barata y el doble sentido. Por último se encuentran los algoritmos que proporcionan soluciones óptimas, como el método de branch and bound (ramificación y poda), que trabaja el problema como un algoritmo de asignación y lo resuelve por
MÉTODO DE FUERZA BRUTA
El método de la fuerza bruta no implica la aplicación de ningún algoritmo sistemático, tan solo consiste en explorar todos los recorridos posibles. Considerando la siguiente red simétrica, los caminos posibles se reducen a la mitad:
Posibles rutas
A - B - D - C - A = 9 + 15 + 4 + 7 = 35 km
A - B - C - D - A = 9 + 10 + 4 + 8 = 31 km
A - C - B - D - A = 7 + 10 + 15 + 8 = 40 km
Rutas simétricas
A - D - C - B - A = 8 + 4 + 10 + 9 = 31 km
A - C - D - B - A = 7 + 4 + 15 + 9 = 35 km
A - D - B - C - A = 8 + 15 + 10 +7 = 40 km
MÉTODO DEL VECINO MÁS CERCANO
El método del vecino más cercano es un algoritmo heurístico diseñado para solucionar el problema del agente viajero, no asegura una solución óptima, sin embargo suele proporcionar buenas soluciones, y tiene un tiempo de cálculo muy eficiente. El método de desarrollo es muy similar al utilizado para resolver problemas de árbol de expansión mínima.
El método consiste en una vez establecido el nodo de partida, evaluar y seleccionar su vecino más cercano. En este caso:
En la siguiente iteración habrá que considerar los vecinos más cercanos al nodo C (se excluye A por ser el nodo de origen):
En la siguiente iteración los vecinos más cercanos de D serán C, con quien ya tiene conexión, A quién es el nodo de origen y B, por esta razón B se debe seleccionar por descarte. Al estar en B todos los nodos se encuentran visitados, por lo que corresponde a cerrar la red uniendo el nodo B con el nodo A, así entonces la ruta solución por medio del vecino más próximo sería A, C, D, B, A = 7, 4, 15, 9 = 35 km.
Este es un caso en el que a pesar de tener una red compuesta por pocos nodos, el método del vecino más cercano no proporciona la solución óptima, la cual calculamos con el método de fuerza bruta como 31 km.
Preguntas:
1°-¿Cual es el objetivo del Problema del gente Viajero?
El objetivo es encontrar un recorrido completo que conecte todos los nodos de una red, visitándolos tan solo una vez y volviendo al punto de partida.
2°-¿Este tipo de problemas en que ámbito se aplica?
Este tipo de problemas tiene gran aplicación en el ámbito de la logística y distribución, así como en la programación de curvas de producción.
3°-Menciona los métodos que conoces para solucionar el problema.
-Método de Fuerza Bruta
-Método del vecino mas cercano
-Método de Branch and Bound
4°-¿En que consiste el método de Fuerza Bruta?
El método de la fuerza bruta no implica la aplicación de ningún algoritmo sistemático, tan solo consiste en explorar todos los recorridos posibles.
5°-¿En que consiste el método del vecino mas cercano?
El método de desarrollo es muy similar al utilizado para resolver problemas de árbol de expansión mínima.
6°-¿Como es el origen del Agente Viajero?
El origen de los problemas del agente viajero no esta claro.Una guía para agentes viajeros de 1832 menciona el problema e incluye ejemplos de viajes a traves de Alemania y Suiza.
7°-¿Qué es el método del vecino mas cercano?
El método del vecino más cercano es un algoritmo heurístico diseñado para solucionar el problema del agente viajero, no asegura una solución óptima, sin embargo suele proporcionar buenas soluciones, y tiene un tiempo de cálculo muy eficiente.
8°-¿En que consiste el método del vecino mas cercano?
El método consiste en una vez establecido el nodo de partida, evaluar y seleccionar su vecino más cercano.
9°-Descripción el Agente Viajero.
En el problema se presentan N! rutas posibles, aunque se puede simplificar ya que dada una ruta nos da igual el punto de partida.
10°-¿Que nos proporciona el método de Branch and Bound?
El método de branch and bound(ramificación y poda), nos proporciona una solución óptima del problema del agente viajero, calculando mediante el algoritmo simplex la solución del modelo.
Suscribirse a:
Entradas (Atom)