Presentación1 (1) by on Scribd
viernes, 21 de junio de 2019
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. 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, es decir:
( (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 medio del método simplex.
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.
MÉTODO DE BRANCH AND BOUND - WINQSB
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. A medida que aumente el tamaño de la red el método puede tardar gran cantidad de tiempo en resolverse, sin embargo para redes de mediano tamaño es una excelente alternativa. En este caso y
considerando la red que hemos desarrollado mediante los métodos anteriores, utilizaremos el módulo Network Modeling del software WinQSB para encontrar la solución óptima.
viernes, 7 de junio de 2019
sucecion de fibonacci
La sucesión de Fibonacci, en ocasiones también conocida como secuencia de Fibonacci o incorrectamente como serie de Fibonacci, es en sí una sucesión matemática infinita. Consta de una serie de números naturales que se suman de a 2, a partir de 0 y 1. Básicamente, la sucesión de Fibonacci se realiza sumando siempre los últimos 2 números (Todos los números presentes en la sucesión se llaman números de Fibonacci).
¿Como es?
La sucesión de Fibonacci es la sucesión de números:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Cada número se calcula sumando los dos anteriores a él.
- El 2 se calcula sumando (1+1)
- Análogamente, el 3 es sólo (1+2),
- Y el 5 es (2+3),
- ¡y sigue!
Ejemplo: el siguiente número en la sucesión de arriba sería (21+34) = 55
¡Así de simple!
Aquí tienes una lista más larga:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, ...
TEORIA DE SUBCONJUNTOS
1:Conjunto de elementos que tienen las mismas características y que está incluido dentro de otro conjunto más
2:Un conjunto A es subconjunto de otro B si todos los elementos del primer conjunto son también elementos del segundo conjunto. Esto es;
A⊂B ⇔ ∀x∈A,x∈B
Ejemplos.
- El «conjunto de todos los hombres» es un subconjunto del «conjunto de todas las personas».
- {1, 3} ⊆ {1, 2, 3, 4}
- {2, 4, 6, ...} ⊆ {1, 2, 3, ..} = N ( {Números pares} ⊆ {Números naturales} )
- 3:
relacion entre teoria de conjuntos logica matematica y algebra booleana
Entre logica matematica y teoria de conjuntos comparten leyes logicas tanto para conjuntos como para logica proposicional. El álgebra de Boole fue un intento de utilizar las técnicas algebraicas para tratar expresiones de la lógica proposicional.En la actualidad, el álgebra de Boole se aplica de forma generalizada en el ámbito del diseño electrónico
PERMUTACIONES
- Son de n elementos a los diferentes grupos que se pueden formar con esos elementos siguiendo las siguientes reglas:
- Entran todos los elementos
- Si importa el orden
- No se repiten los elementos
Si el ejercicio que se plantea sigue esas tres reglas, la formula a aplicar es:
Pn=n!
Donde "n" es el numero de elementos que vana participar en las agrupaciones.
Ejercicios
1: ¿Cuantos numeros de 3 cifras diferentes se pueden formar con los digitos 1,2 y 3?
Pn=3! P3=3! 123
P3=3*2*1=6 132
213
231
312
321
2:¿Cuantos grupos diferentes de 3 vocales se pueden formar sin que se repitan los elementos usando las siguientes vocales?
P3=3! P3=3*2*1
P3=6
A,E,O
A,O,E
A,E,O
A,O,E
E,A,O
E,O,A
O,A,E
O,E,A
3:¿Cuantos grupos de 4 elementos se pueden formar con los digitos si no se repiten los elementos?
P4=4! 3579 3597
P4=4*3*2*1 3759 3795
P4=24 3957 3975
5379 5397
5739 5793
5937 5973
7359 7395
7539 7593
7935 7953
9357 9375
9537 9573
9735 9753
4:Antiguamente los barcos se comunicaban entre si utilizando banderas de diferentes colores colocandolas de manera ordenada en diferenes posiciones. ¿Cuantos mensajes distintos se podran enviar con las banderas en los colores azul, rojo, verde y negro? Indique cuantos mensajes serian si se le añade otra bandera cafe.
-En este caso no deberan mostrarselas agrupaciones-
P4=4! P5=5!
P4=4*3*2*1 P5=5*4*3*2*1
P4=24 mensajes P5=120 mensajes
PERMUTACIONES CON REPETICION
*Se llama permutaciones con repeticion a los diferentes grupos de elementos que se forman usando "n" elementos donde el primer elemento se repite n veces, el segundo tambien se repite n veces y asi consecutivamente hasta llegar al final de la lista. Estas agrupaciones deben seguir las siguientes reglas:
1:Entran todos los elementos.
2:Si importa el orden.
3:Si se repiten los elementos.
*La formula para realizar el calculo de las permutaciones con repeticion es la siguiente:
PRnabc = Pn
a!b!c!
1:Con las cifras 2,2,2,3,3,3,3,4 y 4 ¿Cuantos numeros de nueve cifras se pueden formar? n=9, a=3, b=4, c=2
PR93,4,2 = P9!
3! 4! 2!
PR93,4,2 = 9*8*7*6*5*4*3*2*1
3*2*1 4*3*2*1 2*1
PR93,4,2 = 362,880
6*24*2
PR93,4,2 = 362,880
288
PR93,4,2 = 1260 Numeros de nueve cifras o permutaciones
PERMUTACIONES CIRCULARES
PERMUTACIONES CIRCULARES
*Se utiliza cuando los elementos se van a ordenar en circulo, por ejemplo los comenzales en una mesa de modo que el primer elemento que se sitúa en la mesa, determina el principio y el fin de la lista.
La formula es:
La formula es:
PCn*1 = n!
1:¿De cuantas formas distintas pueden sentarse 8 personas al rededor de una mesa redonda?
PC8-1 = 7!
PC7 = 7*6*5*4*3*2*1
PC7 = 5,040 Formas de sentarse en la mesa
Actividades de permutaciones
1:¿Cuantas palabras se pueden formar de 4 letras con la palabra AXEL?
Escriba el listado de las palabras que se pueden formar.
P4 = 4! A X E L
P4 = 4*3*2*1 axel xale exal lexa
P4 = 24 alxe xael exla leax
aelx xeal elax laxe
alex xela elxa laex
axle xlea eaxl lxea
aexl xlae ealx lxae
2:¿Cuantas palabras diferentes de 5 letras se pueden formar con la palabra libro?
P5 = 5!
P5 = 5*4*3*2*1
P5 = 120 Palabras
3:¿Cuantas palabras diferentes de 6 letras se pueden formar con la palabra tratar?
PRtra = 6! PRtra = 720
2! 2! 2! 8
PRtra = 6*5*4*3*2*1 PRtra = 90
2*1 2*1 2*1
4:¿Cuantas palabras de 10 letras se pueden formar usando la palabra termometro?
P10222 = 10!
2! 2! 2! 2! 2!
P10222 = 10*9*8*7*6*5*4*3*2*1
2*1 2*1 2*1 2*1 2*1
P10222 = 1,814,400
16
P10222 = 113,400
Escriba el listado de las palabras que se pueden formar.
P4 = 4! A X E L
P4 = 4*3*2*1 axel xale exal lexa
P4 = 24 alxe xael exla leax
aelx xeal elax laxe
alex xela elxa laex
axle xlea eaxl lxea
aexl xlae ealx lxae
2:¿Cuantas palabras diferentes de 5 letras se pueden formar con la palabra libro?
P5 = 5!
P5 = 5*4*3*2*1
P5 = 120 Palabras
3:¿Cuantas palabras diferentes de 6 letras se pueden formar con la palabra tratar?
PRtra = 6! PRtra = 720
2! 2! 2! 8
PRtra = 6*5*4*3*2*1 PRtra = 90
2*1 2*1 2*1
4:¿Cuantas palabras de 10 letras se pueden formar usando la palabra termometro?
P10222 = 10!
2! 2! 2! 2! 2!
P10222 = 10*9*8*7*6*5*4*3*2*1
2*1 2*1 2*1 2*1 2*1
P10222 = 1,814,400
16
P10222 = 113,400
Principios fundamentales del conteo
Principios fundamentales del conteo
*La enumeración o conteo puede parecer un proceso obvio que u estudiante aprende a estudiar aritmética por primera vez. Pero luego según parece se presta poca atención en lo que se refiere a un desarrollo más amplio del conteo con forme al estudiante pasa áreas mas difícil de las matemáticas, como el álgebra, geometría, trigonometría y el calculo. En consecuencia deberá servir como advertencia acerca del conteo.
*La enumeración no termina con la aritmética:
también en aplicaciones en áreas como la teoría de códigos como la contabilidad y estadísticas.
*La enumeración no termina con la aritmética:
también en aplicaciones en áreas como la teoría de códigos como la contabilidad y estadísticas.
REGLAS DE A SUMA EL PRODUCTO
Reglas de la suma y el producto
1:Si una primera tarea puede realizarse de "m" formas mientras que una tarea puede realizarse de "n" formas y no es posible realizar ambas tareas de manera simultanea, entonces para llevar a cabo cualquiera de ellas puede utilizarse cualquiera de ellas.
2:Si un procedimiento se puede descomponer en las etapas primera y segunda y si existen "m" resultados posibles de la primera etapa, para cada uno de estos resultados existen "n" resultados posibles para la segunda etapa, entonces el procedimiento total que se puede realizar en el orden dado.
2:Si un procedimiento se puede descomponer en las etapas primera y segunda y si existen "m" resultados posibles de la primera etapa, para cada uno de estos resultados existen "n" resultados posibles para la segunda etapa, entonces el procedimiento total que se puede realizar en el orden dado.
TECNCAS DE CONTEO
TENICAS DE CONTEO
Las tecnicas de conteo se utilizan para calcular, el numero de veces o la canridad de veces en que un suceso o accion se presenta.
Las tecnicas utilizadas para el conteo son:
Un arbol se dibuja de la siguiente manera.
Ejercicio:
Luis fernando decea conocer de cuantas formas distintas puede vestirce si tiene las siguientes prendas: un pantalon negro, azul y beige, una playera azul, blanca,roja, y negra, Unos zapatos negros y unos tenis.
A
N B
R
A
A B
R
B B
R
Las tecnicas utilizadas para el conteo son:
- Permutacion
- Convinacion
- Arbol
Un arbol se dibuja de la siguiente manera.
Ejercicio:
Luis fernando decea conocer de cuantas formas distintas puede vestirce si tiene las siguientes prendas: un pantalon negro, azul y beige, una playera azul, blanca,roja, y negra, Unos zapatos negros y unos tenis.
A
N B R
N
A
A B R
N
A
B B R
N
Un matrimobio tiene 3 hijos, basandoce en el siguiente diagrama de arbol ¿cual es la probabilidad de que los dos sean del mismo sexo?
Se determina la variable que se van a utilizar en el diagrama "sea c" cara "sea s" sello
Se tiene una tienda de pantalones,2 camisas y 2 zapatos de color azul y negro. Calcula el numero de combinaciones posibles .
PERMUTACIONES
Se llama permutaciones de N elementos a los diferentes grupos que se pueden formar con esos elementos siguiendo las siguientes reglas.
- Entran todos los elemntos
- Si importa el orden
- Nos se repiten los elementos
Si el ejercicio que se plantea sigue esas tres reglas la formula a aplicar es permutacion.
PN=N1
Donde N es el numero de elementos que van a participar en las agrupaciones.
cuantos numeros de 3 cifras diferentes se pueden frmar on los digitos 1,2,3
PN=N! PN=N!
P3=3
3*2*1=6
P4=4! 4*3*2*1=24
4. Antiguamente los barcos se comunicaban entre si usando banderas de diferentes colores de manera ordenada.
Ejercicios Permutaciones
- ¿Cuantos números de 3 cifras diferentes se puede formar con los dígitos 1,2,3?
3*2*1=6 1,2,3
1,3,2
2,3,1
2,1,3
3,1,2
3,2,1
2.¿Cuantos grupos diferentes de tres vocales se puede formar sin que se repitan los elementos, usando 3 vocales: A,E,O?
3*2*1=6 A,E,O
A,O,E
E,A,O
E,O,A
O,A,E
O,E,A
3.¿Cuantos grupos de 4 elementos se puede formar con los digitos 3,5,7,9?
P4=4! 4*3*2*1=24
3,5,7,9 5,3,7,9 7,5,9,3 9,3,5,7
3,5,9,7 5,3,9,7 7,5,3,9 9,3,7,5
3,9,7,5 5,9,3,7 7,3,5,9 9,7,3,5
3,9,5,7 5,9,7,3 7,3,9,5 9,7,5,3
3,7,9,5 5,7,3,9 7,9,3,5 9,5,3,7
3,7,5,9 5,7,9,3 7,9,5,3 9,5,7,3
4. Antiguamente los barcos se comunicaban entre si usando banderas de diferentes colores de manera ordenada.
P4=4!
4*3*2*1= 24 mensajes
P5=5!
5*4*3*2*1=120 mensajes
Permutaciones con repetición
Se llama permutaciones con repetición a los grupos de elementos que se forman cuando "n" elementos,donde e primer elemento se repite n veces, el segundo también se repite n veces y así se repiten hasta llegar al final de la lista. Estas agrupaciones deben seguir las siguientes reglas;
- Entran todos los elementos.
- Si importa el orden.
- Si se repiten los elementos.
La formula para realizar el calculo de las permutaciones con repetición es la siguiente.
PRn=____Pn_____
a! b! c!
Con las cifras 2,2,2,3,3,3,3,4,4 ¿Cuantos números de 9 cifras se pueden formar? Si los datos son n=9 a=3 b=4 c=2
abc
PRn =____Pn______
a! b! c!
3,4,2
PRn =______Pa______= 9*8*7*6*5*4*3*2*1= 9*8*7*6 = 15120 = 1260
3! 4! 2! 3*2*1.4*3+2 *1 6*2 12
Permutaciones Circulares
Las permutaciones circulares se utilizan cuando os elementos se van a ordenar en circulo
Por ejemplo
Los comensales en una mesa se van a sentar de modo que el primer elemento que se situe en la mesa determina el principio y el fin de la lista.
La formula para la permutacion circular es PC n-1=n!
Ejercicio
- De cuantas formas distintas pueden sentarse 8 personas alrededor de una mesa redonda.
PC n-1= n!
PC 8-1= 71 =7*6*5*4*3*2*1= 5040
PERMUTACIONES FORMULA REGLAS
1. Entran todos los elementos.
Permutaciones P4= 4! 2. Si importa el orden.
3. No se repiten los elementos.
Con repetición PRn=__Pn__ 222 3333 44 a! b! c! a b c
Circulares PCn-1 = n! Tienen que ser un problema relacionado a un circulo.
Ejercicios de Permutaciones
- ¿Cuantas palabras distintas de cuatro letras se pueden formar? Escriba el listado que se forma.
Pn = 4!
Pn = n! = 4! = 4*3*2*1= 24 palabras
ALEX LAEX ELAX XAEL
AELX LAXE ELXA XALE
AEXL LXAE EXAL XLAE
AXLE LXEA EXLA XLEA
AXEL LEAX EALX XELA
ALXE LAEX EAXL XEAL
2.¿Cuantas palabras diferentes de 5 letras se puede fomar con la palabra LIBRO?
Pn = n! =5! = 5*4*3*2*1= 120 palabras
3.¿Cuantas palabras diferentes de 6 letras se puede formar la palabra TRATAR?
PRn = ____Pn_____
a! b! c!
2,2,2
PR =____P6_____ = 6*5*4*3*2*1 =___360___ = 90 palabras
2! 2! 2! 2*1 * 2*1 * 2*1 4
4.¿Cuantas palabras de 10 letras se puede formar usando la palabra TERMÓMETRO?
PR =____P10____ = 10*9*8*7*6*5*4*3*2*1 = 1814400 = 113400 palabras
2! 2! 2! 2! 2! 2*1 x 2*1 x 2*1 x 2*1 x 2*1 16
Principios Fundamentales del Conteo
La enumeración o conteo puede parecer un proceso obvio que un estudiante aprende al estudio aritmética por primera vez. Pero luego según parece se presta poca atención en lo que se refiere a un desarrollo mas amplio del conteo, conforme el estudiante pasa áreas mas difíciles de las matemáticas como el álgebra, la geometría, la trigonometria y el calculo. En consecuencia deberá servir como advertencia acerca del conteo.
La enumeración no termina con la aritmética, también tiene aplicaciones como: la teoría de códigos, la probabilidad y la estadística.
Reglas de la Suma y Producto
- Si una primera tarea puede realizarse de "m" formas mientras que una segunda tarea puede realizarse de "n" formas, y no es posible realizar ambas tareas de manera simultanea entonces para llevar a cabo cualquiera de ellas.
- Si un procedimiento se puede descomponer en las etapas primera y segunda, si existe "m" resultados posibles de la primera etapa, para cada uno de estos resultados existen "n" resultados posibles para la segunda etapa, entonces el procedimiento total se puede realizar en el orden dado.
Suscribirse a:
Comentarios (Atom)