CADENAS DE MARKOV

 CADENAS DE MARKOV

Una cadena de Markov es un proceso evolutivo que consiste en un numero finito de estados en el cual la probabilidad de que ocurra un evento depende solamente del evento inmediatamente anterior con probabilidades que están fijas. 

 También conocida como modelo de Markov o proceso de Markov, es un concepto desarrollado dentro de la teoría de la probabilidad y la estadística que establece una fuerte dependencia entre un evento y otro suceso anterior. Su principal utilidad es el análisis del comportamiento de procesos estocásticos. 

 La explicación de estas cadenas la desarrollo el matemático de origen ruso Andréi Márkov. Se ha podido emplear dicha metodología en numerosos casos prácticos de la vida cotidiana. 

 También es llamado como cadena simple biestable de Márkov

DISTRIBUCION DE PROBABILIDADES

 DISTRIBUCION DE PROBABILIDADES

En teoría de la probabilidad y estadística, la distribución de probabilidad de una variable aleatoria es una función que asigna a cada suceso definido sobre la variable de probabilidad de que dicho suceso ocurra. La distribución de probabilidad esta definida sobre el conjunto de todos los sucesos y cada uno de los sucesos es el rango de valores de la variable aleatoria. 

 

ANALISIS INSUMO PRODUCCION

 ANALISIS COMBINATORIO

Es la rama de la matemática que estudia los diversos arreglos o agrupaciones que podemos formar con los elementos de un conjunto dado, formándolas y calculando su numero permitiéndonos resolver problemas de la vida real. Por ejemplo, podemos calcular cuantos números diferentes de teléfonos se puede formar a partir de un conjunto de números. Además, estudia las ordenaciones o agrupaciones de un determinado numero de elementos. 

En resumen, El objeto del Análisis combinatorio o Combinatoria es el estudio de las distintas ordenaciones que pueden formularse con los elementes de un conjunto, de los distintos grupos que pueden formarse con aquellos elementos y de las relaciones entre unos y otros grupos. 

 

PRINCIPIO FUNDAMENTAL DEL ANALISIS COMBINATORIO:  

El análisis combinatorio  se define como una manera practica y abreviada de contar; las operaciones o actividades que se presentan son designadas como eventos o sucesos. 

ejemplos: 

El 35% de los estudiantes de un centro docente practica el futbol. El 70% de los que practican el futbol estudian Matemáticas, así como el 25% de los que no practican el futbol. 

Que es una función Factorial? 

Es una formula matemática representada por el signo de exclamación !. En la formula factorial se debe multiplicar toso los números enteros y positivos que hay entre el numero que aparece en la formula y el numero 1. 

Ejemplo: 

n	n!
1	1	1	1
2	2 × 1	= 2 × 1!	= 2
3	3 × 2 × 1	= 3 × 2!	= 6
4	4 × 3 × 2 × 1	= 4 × 3!	= 24
5	5 × 4 × 3 × 2 × 1	= 5 × 4!	= 120

 

Métodos de análisis combinatorio 

 1. PERMUTACIONES (IMPORTA EL ORDEN) 

Las permutaciones o, también llamadas, ordenaciones son aquellas foras de agrupar los elementos de un conjunto teniendo en cuenta que: 

• Influye el orden en que se colocan.
• Tomamos todos los elementos de que se disponen. 

a) PERMUTACIONES SIN REPETICION 

Las permutaciones sin repetición de n elementos se definen como las distintas formas de ordenar todos esos elementos distintos, por lo que la única diferencia entre ellas es el orden de colocación de sus elementos. El numero de estas permutaciones será: 

 

                                                         

P= Permutación

n= numero tota de elementos del conjunto a permutar

r= numero de veces o de elementos que serán permutados.  

Ejemplo de permutaciones sin repetición:

Con las letras de la palabra Carlos, Cuantas permutaciones distintas se pueden formar?  

P:?

n=6

r=6                                 

 

                       6!     =    6!       

                            (6 - 6)!     0!  = 720 formas

 La palabra carlos tiene 720 formas de ordenarse o permutarse. 

 

PERMUTACION CON REPETICION

El numero de permutaciones (P) distintas de "n" elementos tomados de "n" en "n" en donde hay un primer grupo n1 objetos iguales entre si; n2 objetos iguales entre de un ultimo tipo, entonces:  

 

P= permutación 

n= número total de elementos del conjunto a permutar

r= numero de veces o de elementos que serán permutados 

 

Ejemplo de permutación con repetición 

En una urna, hay 5 bolas del mismo tamaño y peso, de los cuales, 3 son rojas y 2 son azules, ¿ De cuantas maneras se pueden extraer una a una las bolas de la urna?

 Coloquemos algunas formas de extraer las bolas: 

Roja-Roja-Azul-Roja-Azul

Azul-Roja-Roja-Azul-Roja

Roja-Azul-Roja-azul-Roja 

En cada forma de extraer las bolas, importa el orden, hay elementos repetidos y participan todos los elementos (bolas), por ello, usaremos la formula de permutación con elementos repetidos. 

Numero de bolas rojas: 3

Numero de bolas azules: 2

Numero total de elementos: n=3+2 ➜ n= 5

En total, se pueden extraer las bolas de 10 formas diferentes.  

Permutación circular

Son agrupaciones donde no hay primero ni ultimo elemento, por hallarse todos en una linea cerrada. Para hallar el numero de permutaciones circulares que se pueden formar con "n" objetos distintos de un conjunto, hay que considerar fija la posición de un elemento, ¡los n-1 restantes podrán cambiar de lugar de (n-1)! Formas diferentes tomando todas las posiciones sobre la circunferencia. 

 Formula: 

                        PCn = (n – 1)!

 Ejemplo: 

De cuantas maneras se pueden sentar 5 amigos alrededor de una mesa circular?  

Numero de elementos: n=5

Ahora calculamos el numero de permutaciones circulares:  

Los 5 amigos, se pueden sentar de 24 formas diferentes.  

METODOS DE TRANSPORTE

     

METODOS DE TRANSPORTE

 El método de transporte busca determinar la distracción de mercaderías desde una fuente o planta de producción, hacia un destino o almacén. El objetivo es buscar una combinación de traslado que permita minimizar los costos de transportación.

Existen varios métodos de solución a problemas de transporte, veremos tres de ellos.  

1. Esquina Noroeste 

               2. Costo Mínimo

               3. Aproximación de Voguel  

ESQUINA NOROESTE

Es un método que funciona encontrando soluciones a los  problemas de transporte o distribución. Este método, tiene como ventaja, frente a sus similares, la rapidez de su ejecución. '

 ¿De que trata el método de la esquina Noroeste?

 Este método, comienza por plantear, en forma de matriz, el problema que buscamos resolver. Las filas representaran las fuentes y las columnas los destinos, luego el algoritmo debe iniciar en la celda, ruta o esquina Noroeste de la tabla

Ejemplo 

La empresa químicos del Caribe, S.A posee 4 depósitos de azufre que deben ser usados para fabricar 4 tipos de productos diferentes ( A,B,C,D), además por cala litro que se haga de los productos A, B, C, y D se utilizan un litro de azufre. SE sabe que  las capacidades de cada deposito  son de 100, 120, 80, 95 respectivamente. Le empresa tiene un pedido de 125L de la sustancia A, 50L de la sustancia B, 130L de la sustancia C y 90L de la sustancia D. 

Paso 1: Verificar la existencia de una matriz de costos. 

		A		B	C		D		DISPONIBILIDAD
DEPOSITO 1		2		3	4		6		100
DEPOSITO 2		1		5	8		3		120
DEPOSITO 3		8		5	1		4		80
DEPOSITO 4		4		5	6		3		95
REQUERIMIENTO	125		50		130	90

 

 

 

   

Paso 2: Confirmar que la suma de las disponibilidades sea igual a la suma de los requerimientos  

		A		B	C		D		DISPONIBILIDAD
DEPOSITO 1		2		3	4		6		100
DEPOSITO 2		1		5	8		3		120
DEPOSITO 3		8		5	1		4		80
DEPOSITO 4		4		5	6		3		95
REQUERIMIENTO	125		50		130	90

 

Suma de disponibilidades 395

                               Suma de requerimientos:  395

Paso 3 Asignar la mayor cantidad posible de las disponibilidades y de los requerimientos para ir satisfaciendo cada fila y columna utilizando la esquina superior izquierda que este vacía (Esquena noroeste. El procedimiento termina hasta que se concluye toda la matriz 

		A		B	C		D		DISPONIBILIDAD
DEPOSITO 1		2   100		3   x	4                  x		6 x		100-100=0
DEPOSITO 2		1   25		5 50	8   45		3 x		120-25=95-50=45-45=0
DEPOSITO 3		8   x		5 x	1   80		4 x		80-80=0
DEPOSITO 4		4   x		5 x	6   5		3 90		95-5=90-90=0
REQUERIMIENTO	125-100=25-25=0		50-50=0		130-45=85-80=5-5=0	90-90=0

Paso 4

Seleccionar las casillas que tengan una asignación y vamos a multiplicarlas por el costro de transporte correspondiente.   

Costo total de transporte= (100x2)+(25x1)+(50x5)+(45x8)+(80x1)+(5x6)+(90x3)=Q1215.00 

COSTO MINIMO

El método del costo mínimo o método de los mínimos costos es un algoritmo desarrollado con el objetivo de resolver problemas de transporte o distribución, arrojando mejores resultados que métodos como el de la esquina noroeste, dado que se enfoca en las rutas que presentan menores costos.  

 Se asigna el valor mas grande posible a la variable con menor costo unitario de la tabla. Se tacha el renglón o columna satisfecho, repitiéndose este ultimo procedimiento hasta tachar todas las columnas y/o renglones. 

EJEMPLO  

La empresa químicos del Caribe, S.A posee 4 depósitos de azufre que deben ser usados para fabricar 4 tipos de productos diferentes ( A,B,C,D), además por cala litro que se haga de los productos A, B, C, y D se utilizan un litro de azufre. SE sabe que  las capacidades de cada deposito  son de 100, 120, 80, 95 respectivamente. Le empresa tiene un pedido de 125L de la sustancia A, 50L de la sustancia B, 130L de la sustancia C y 90L de la sustancia D. 

Paso 1: Verificar la existencia de una matriz de costos.  

Paso 2: Confirmar la suma de las disponibilidades sea igual a la suma de los requerimientos. 

		A		B	C		D		DISPONIBILIDAD
DEPOSITO 1		2		3	4		6		100
DEPOSITO 2		1		5	8		3		120
DEPOSITO 3		8		5	1		4		80
DEPOSITO 4		4		5	6		3		95
REQUERIMIENTO	125		50		130	90

 

Suma disponibilidades 
Q 395
                                                                                                                        Suma requerimientos                                                                                                                                                                                                                 Q 395 

Paso 3. Buscar el valor del costo mínimo renglón por renglón y anotarlo al finalizar la fila.

		A		B	C		D		DISPONIBILIDAD
DEPOSITO 1		2		3	4		6		100 (2)
DEPOSITO 2		1		5	8		3		120 (1)
DEPOSITO 3		8		5	1		4		80 (1)
DEPOSITO 4		4		5	6		3		95 (3)
REQUERIMIENTO	125		50		130	90

Paso 4: Buscar el valor del costo mínimo columna por columna y anotarlo al finalizar la

columna. 

		A		B	C		D		DISPONIBILIDAD
DEPOSITO 1		2		3	4		6		100 (2)
DEPOSITO 2		1		5	8		3		120 (1)
DEPOSITO 3		8		5	1		4		80 (1)
DEPOSITO 4		4		5	6		3		95 (3)
REQUERIMIENTO	125 (1)		50 (3)		130 (1)	90 (3)

Paso 5: Seleccionar el menor de todos los valores anotados al final de cada fila y columna

• Asignar la oferta (disponibilidad / origen), la cantidad máxima posible al costo mínimo 
• Anular las casillas del renglón o columna, que hubiesen sido satisfechas; lo que primero suceda. O todas las casillas del renglón y todas las columnas, si la oferta y la demanda hubiesen sido agotadas totalmente. 

	A		B	C		D		DISPONIBILIDAD
DEPOSITO 1	2    5		3    45	4    50		6 x		100-5=95-45=50-50=0 (4)
DEPOSITO 2	1    120		5     x	8    x		3 x		120-120=0 (1)
DEPOSITO 3	8    x		5 x	1    80		4 x		80-80=0 (1)
DEPOSITO 4	4    x		5 5	6    x		3 90		95-5=90-90=0 (3)
REQUERIMIENTO	125-5=120-120=0 (1)	50-45=5-5=0 (3)		130-50=80-80=0 (1)	90-90=0 (3)

Paso 6: Repetir los pasos 3,4 y 5 hasta completar de satisfacer toda la matriz(disponibilidad

y requerimiento) 

	A		B	C		D		DISPONIBILIDAD
DEPOSITO 1	2    5		3    45	4    50		6 x		100-5=95-45=50-50=0 (4)
DEPOSITO 2	1    120		5     x	8    x		3 x		120-120=0 (1)
DEPOSITO 3	8    x		5 x	1    80		4 x		80-80=0 (1)
DEPOSITO 4	4    x		5 5	6    x		3 90		95-5=90-90=0 (3)
REQUERIMIENTO	125-5=120-120=0 (1)	50-45=5-5=0 (3)		130-50=80-80=0 (1)	90-90=0 (3)

Paso 7: Seleccionar las casillas que tengan una asignación y vamos a multiplicarlas por el costo de transporte correspondiente, para con la sumatoria total encontrar el costo Total del transporte.

Costo Total de Transporte= (5x2) + (45x3) + (50x4) + (120x1) + (80x1) + (5x5) + (90x3)= Q840

METODO DE VOGUEL

Este procedimiento permite obtener otro costo mínimo y muchas veces mas optimo que los dos

métodos anteriores. 

Ejemplo 

La empresa químicos del Caribe, S.A posee 4 depósitos de azufre que deben ser usados para fabricar 4 tipos de productos diferentes ( A,B,C,D), además por cala litro que se haga de los productos A, B, C, y D se utilizan un litro de azufre. SE sabe que  las capacidades de cada deposito  son de 100, 120, 80, 95 respectivamente. Le empresa tiene un pedido de 125L de la sustancia A, 50L de la sustancia B, 130L de la sustancia C y 90L de la sustancia D. 

paso 1: Verificar la existencia de una matriz de costos.

		A		B	C		D		DISPONIBILIDAD
DEPOSITO 1		2		3	4		6		100
DEPOSITO 2		1		5	8		3		120
DEPOSITO 3		8		5	1		4		80
DEPOSITO 4		4		5	6		3		95
REQUERIMIENTO	125		50		130	90

paso 2: Confirmar que la suma de las disponibilidades sea igual a la suma de los requerimientos

		A		B	C		D		DISPONIBILIDAD
DEPOSITO 1		2		3	4		6		100
DEPOSITO 2		1		5	8		3		120
DEPOSITO 3		8		5	1		4		80
DEPOSITO 4		4		5	6		3		95
REQUERIMIENTO	125		50		130	90		Suma de disponibilidades 395

                                  Suma de requerimientos= 395

Paso 3= Buscar los dos costos mínimo renglón por renglón, restarlos y anotarlo

al finalizar la fila 

		A		B	C		D		DISPONIBILIDAD
DEPOSITO 1		2		3	4		6		100 (1)
DEPOSITO 2		1		5	8		3		120 (2)
DEPOSITO 3		8		5	1		4		80 (3)
DEPOSITO 4		4		5	6		3		95 (1)
REQUERIMIENTO	125		50		130	90

Paso 4: Buscar los dos costos mínimo columna por columna, restarlos y anotarlos

al final de cada columna. 

		A		B	C		D		DISPONIBILIDAD
DEPOSITO 1		2		3	4		6		100 (1)
DEPOSITO 2		1		5	8		3		120 (2)
DEPOSITO 3		8		5	1		4		80 (3)
DEPOSITO 4		4		5	6		3		95 (1)
REQUERIMIENTO	125 (1)		50 (2)		130 (3)	90 (1)

Paso 5: Identificar la fila o columna con la penalización (diferencia) mas alta. 

		A		B	C		D		DISPONIBILIDAD
DEPOSITO 1		2   X		3    50	4 50		6 x		100-50=50-50=0 (1)
DEPOSITO 2		1 120		5 x	8 x		3 x		120-120=0 (2)
DEPOSITO 3		8 x		5 x	1 80		4 x		80-80=0 (0)
DEPOSITO 4		4 5		5 x	6 x		3 90		95-5=90-90=0 (1)
REQUERIMIENTO	125-120=5-5=0 (1)		50-50=0 (2)		130-50=80-80=0 (2)	90-90=0 (0)

Paso 6: Repetir los pasos 3,4 y5 hasta completar de satisfacer toda la matriz

		A		B	C		D		DISPONIBILIDAD
DEPOSITO 1		2   X		3    50	4 50		6 x		100-50=50-50=0 (1)
DEPOSITO 2		1 120		5 x	8 x		3 x		120-120=0 (2)
DEPOSITO 3		8 x		5 x	1 80		4 x		80-80=0 (0)
DEPOSITO 4		4 5		5 x	6 x		3 90		95-5=90-90=0 (1)
REQUERIMIENTO	125-120=5-5=0 (1)		50-50=0 (2)		130-50=80-80=0 (2)	90-90=0 (0)

Paso 7: Seleccionar las casillas que tengan una asignación y vamos a multiplicarlas por el costro de transporte correspondiente, para con la sumatoria total 

Costo total de transporte: (50x3)+(50x4)+(120x1)+(80x1)+(5x4)+(90x3)= Q840.00

METODO DE ASIGNACION

Es un caso especial del modelo de transporte, en el que los recursos se asignan a las actividades en términos de uno a uno, haciendo notar que la matriz correspondiente debe ser cuadrada. 

Se pretende optimizar la relación de costos e insumos o factores productivos asignados a determinada actividad económica. 

Usualmente en asignar "n" recursos a "n" receptores o actividades, conociendo los costos de cada actividad u opción con el fin de minimizar el mismo. 

EJEMPLO 

Hay cuatro constructoras que presentan una oferta de construcción de nuevos edificios a la Universidad. En la matriz siguiente, las filas muestran el numero de edificios a construir y las columnas los constructores que ofertan. Las casillas poseen un valor (en millones) que representa cada oferta. Obtener la mejor alternativa, minimizando los costos de construcción. 

Paso 1 

Verificar que todas las casillas tengan un costo unitario. Si hay alguna casilla vacía, agregar costo cero. 

Paso 2 

La tabla debe estar balanceada. Numero de filas = numero de columnas. Si no tuviera balanceada se agrega una fila o columna con costo cero para balancearla.  

                                       No de filas = No de columnas 4   Son iguales

 

 Paso 3

Elegir el valor mas pequeño de cada fila y restarlo de toda la fila

 

 Resultado del paso 3

 

Paso 4

Elegir de la tabla anterior (paso 3) el menor valor de cada columna y restarlo a los demás de la misma columna

 

 Resultado del paso 4

 

 Paso 5

Se procede a trazar el menor numero de líneas posibles, de modo que todos los ceros queden tachados. Las líneas se trazan donde hay mas ceros y solo pueden trazarse líneas horizontales y verticales. 

Paso 6

Responder la pregunta: ¿El numero de líneas es igual al orden (tamaño) de la matriz? No

Orden de la matriz= 4 (4 filas y 4 columnas) 

El Numero de líneas = 3 

El orden de la matriz no es igual al numero de líneas  

Paso 7

Si la respuesta anterior fue NO, se selecciona el menor valor no tachado de toda la matriz. Este valor restarlo de todo elemento no tachado y sumarlo a los elementos de la intersección de las líneas. 

 

 Resultado el paso 7

 

Volvamos a repetir el paso No 5 (copiando la tabla que viene del paso 7)  

Se procede a trazar el menor numero de líneas posibles, de modo que todos los ceros queden tachados. Las líneas se trazan donde hay mas ceros y solo pueden trazarse líneas horizontales y verticales. 

 No. 6 utilizando la tabla anterior. 

Responder la pregunta: ¿El numero de líneas es igual al orden de la matriz? 

Orden de nuestra matriz (numero de filas y columnas= 4

El numero de líneas= 4 

Orden de la matriz = el numero de líneas. 

Como tienen el mismo numero, llegamos a la solución del problema.

Para dar solución al problema copiamos la ultima tabla.  

Para iniciar dando la solución tomamos como referencia la fila y columnas que tiene un único cero:  

 Matriz original de costos