UNIVERSIDAD LIBRE SECCIONAL BARRANQUILLA
FACULTAD DE INGENIERIA
INGENIERIA INDUSTRIAL
CADENAS DE MÁRKOV
ORIGEN
El análisis de Markov, llamado así por los estudios realizados por el ruso Andréi Andréyevich Márkov entre 1906 y 1907, sobre la secuencia de los experimentos conectados en cadena y la necesidad de descubrir matemáticamente los fenómenos físicos. La teoría de Markov se desarrollo en las décadas de 1930 y 1940 por A.N.Kolmagoron, W.Feller, W.Doeblin, P.Levy, J.L.Doob y otros.
BIOGRAFIA: ANDREI MÁRKOV
Matemático ruso nació el 14 de junio de 1856 en Riazán, Rusia y murió el 20 de julio de 1922. Antes de los 10 años su padre, un funcionario estatal, fue trasladado a San Petersburgo donde Andréi entró a estudiar en un instituto de la ciudad. Desde el principio mostró cierto talento para las matemáticas y cuando se graduó en 1874 ya conocía a varios matemáticos de la universidad de San Petersburgo ingresó tras su graduación.
En la Universidad fue discípulo de Chebyshov tras realizar sus tesis de maestría y doctorado, en 1886 accedió como adjunto a la Academia de Ciencias de San Petersburgo a propuesta del propio Chebyshov. Diez años después Márkov había ganado el puesto de académico regular. Desde 1880, tras defender su tesis de maestría, Márkov impartió clases en la universidad y, cuando el propio Chebyshov dejó la Universidad tres años después, fue Márkov quien le sustituyó en los cursos de teoría de la probabilidad. En 1905, tras 25 años de actividad académica, Márkov se retiró definitivamente de la Universidad, aunque siguió impartiendo algunos cursos sobre teoría de la probabilidad.
A parte de su perfil académico, Andréi Márkov fue un convencido activista político. Se opuso a los privilegios de la nobleza zarista y llegó a rechazar las condecoraciones del propio zar en protesta por algunas decisiones políticas relacionadas con la Academia de Ciencias. Hasta tal punto llegó su implicación en la política que llegó a ser conocido con el sobrenombre de "el académico militante".
Márkov arrastró durante toda su vida problemas relacionados con una malformación congénita en la rodilla que le llevaría varias veces al quirófano y que, con el tiempo, fue la causa de su muerte cuando el 20 de julio del año 1922 una de las muchas operaciones a las que se sometió le produjo una infección generalizada de la que no pudo recuperarse.
Aunque Márkov influyó sobre diversos campos de las matemáticas, por ejemplo en sus trabajos sobre fracciones continuas, la historia le recordará principalmente por sus resultados relacionados con la teoría de la probabilidad. En 1887 completó la prueba que permitía generalizar el teorema central del límite y que ya había avanzado Chebyshov.
Su trabajo teórico en el campo de los procesos en los que están involucrados componentes aleatorios (procesos estocásticos) darían fruto en un instrumento matemático que actualmente se conoce como cadena de Márkov: secuencias de valores de una variable aleatoria en las que el valor de la variable en el futuro depende del valor de la variable en el presente, pero es independiente de la historia de dicha variable. Las cadenas de Márkov, hoy en día, se consideran una herramienta esencial en disciplinas como la economía, la ingeniería, la investigación y muchas otras.
Fuente: AZNAR, Enríque R. Departamento de álgebra de la facultad de ciencias. Unión internacional de matemáticas.
Fuente: AZNAR, Enríque R. Departamento de álgebra de la facultad de ciencias. Unión internacional de matemáticas.
Procedimiento
¿QUÉ SON CADENAS DE MÁRKOV?
Es una serie de eventos, en la cual la probabilidad de que ocurra un evento depende del evento inmediato anterior, es decir que un estado anterior determina un estado futuro.
PROCEDIMIENTO DE CADENA DE MÁRKOV
Un proceso de Markov esta caracterizado por una función de probabilidad de transición representada por T, llamada matriz de transición, que representa la probabilidades de transito de un estado a otro y un vector de probabilidad de estado inicial que representa el estado inicial del mercado. El procedimiento de la cadena de Markov se detallara a continuación con el ejemplo planteado.
Ejemplo:
Telefonía móvil de telecomunicación en Colombia: Existen tres operadores: Movistar, Tigo y Comcel.
Vector de estado inicial:
Po = [ 0,6522 ; 0,1304 ; 0,2174]
¿Cómo será la participación en el futuro dentro de 6 meses?
Para estimar la participación de cada uno de los operadores de telefonía dentro de 6 meses lo primero que hay que hacer es multiplicar el vector de estado inicial por la matriz de transición:
Para hallar el valor de T en el periodo 1 se hace lo siguiente:
(0,6522 * 0,6) + (0,1304 * 0,35) + (0,2174 * 0,3) = 0,5015
Para hallar el valor de M en el periodo 1 se hace lo siguiente:
(0,6522 * 0,1) + (0,1304 * 0,4) + (0,2174 * 0,2) = 0,161
Para hallar el valor de C en el periodo 1 se hace lo siguiente:
(0,6522 * 0,3) + (0,1304 * 0,25) + (0,2174 * 0,5) = 0,3275
Entonces se tiene que P1 (Vector de estado en el periodo 1)
P1 = [ 0,5015 ; 0,161 ; 0,3275]
Esta secuencia se hace hasta el P6 cambiando el valor de Po, ya que el estado posterior depende del inmediatamente anterior.
Tenemos P5:
P5= [0,4423; 0,1941; 0,3626]
Valor de T en el periodo 6:
Valor de T en el periodo 6:
(0,4423 * 0,6) + (0,1941 * 0,35) + (0,3626 * 0,3) = 0,4420
Valor de M en el periodo 6:
(0,4423 * 0,1) + (0,1941 * 0,4) + (0,3626 * 0,2) = 0,1943
Valor de C en el periodo 6:
(0,4423 * 0,3) + (0,1941 * 0,25) + (0,3626 * 0,5) = 0,36252
P6 = [ 0,4420 ; 0,1943 ; 0,36252]
La participación en el mercado dentro de 6 meses para Tigo es de 0,4420, para Movistar de 0,1943 y para Comcel de 0,3652. Se puede observar que la participación de Tigo disminuyó, aumentó la de Movistar y Comcel.
Cadena Absorbente
Una cadena de Márkov que consta solamente de estados transitorios y absorbentes, se denomina CADENA DE MÁRKOV ABSORBENTE.
Pasos que se deben seguir para la construcción de una matriz de cadena absorbente:
1. Determinar si la cadena es absorbente. Esto ocurre:
· Si la cadena tiene por lo menos un estado absorbente (es decir que hay 1 y 0 en la matriz).
· Si es posible pasar de un estado no absorbente a un estado absorbente.
2. Forma la matriz de transición T. Ponga el estado absorbente al final. asegúrese de que los renglones y las columnas se encuentran en el mismo orden.
3. Descarte los renglones que corresponden a los estados absorbentes. Esta información no se requerirá más.
4. Forme la matriz N a partir de las columnas no absorbentes de la matriz del paso 3 y forme la matriz A partir de las columnas absorbentes.
5. Calcule la matriz fundamental (I – N) -1. Esta matriz proporciona la cantidad esperada de periodos que se empleara en los estados no absorbentes antes de quedar absorbidos. La matriz (I – N) -1. Se obtiene de la información de un estado no absorbente, así que se denota con estados no absorbentes.
6. Calcule y nombre a (I – N) -1 A. Esta matriz proporciona la probabilidad de ser absorbidos en cada uno de los estados no absorbentes. Los renglones de (I – N) -1 A se encuentran rotulados con los estados no absorbentes y las columnas, con los estados absorbentes.
Ejemplo :
La universidad libre ha estudiado la trayectoria de sus estudiantes y ha descubierto que:
- 70% de los estudiantes de nuevo ingreso, regresarán el año siguiente como estudiantes de segundo año, el 15% volverán como estudiantes de nuevo ingreso, y el resto no regresarán.
- 75% de los estudiantes de segundo año volverán el año siguiente como estudiantes de tercer año, 15% volverán como estudiantes de segundo año y el resto no regresará.
- 80% de los estudiantes de tercer año regresarán el año siguiente, como estudiantes de último año, 10% volverán como estudiantes de tercer año y el resto no regresará.
- 85% de los estudiantes de último año se graduarán, 10% volverán como estudiantes de último año y el resto no regresará.
Hallar lo siguiente por medio de un sistema de ecuaciones o utilizando la herramienta Excel:
a) ¿Cuántos años pasará un estudiante de nuevo ingreso como estudiantes de nuevo ingreso?
b) ¿Cuál es la probabilidad de que se gradué un estudiante de nuevo ingreso?
Respuesta:
EJERCICIOS RESUELTOS CADENA DE MARKOV UTILIZANDO EXCEL
Aplicaciones
Se aplica en el posicionamiento de marcas para describir la probabilidad de que un cliente que adquiere la marca A en un periodo, adquiere en su lugar la marca B en el siguiente y analizar la penetración en el mercado.
Se aplica para describir la probabilidad de que una maquina que funciona en un periodo determinado, continúe o falle en el siguiente.
Se aplica en la meteorología si considera el clima de una región a través de distintos días, es claro que el estado actual solo depende del último estado y no de toda la historia en sí, de modo que se pueden usar cadenas de Markov para formular modelos climatológicos básicos.
Otra aplicación son los juegos de azar, un ejemplo es de ruina del jugador, que establece la probabilidad de que una persona que apuesta en un juego de azar termine sin dinero.
Fuente: MARTÍNEZ, Eliseo. Cadenas de Márkov y aplicaciones. Pág 2-5.
Ejercicios Propuestos
1) Supóngase que la probabilidad de que llueva mañana es de 0.7, si está lloviendo hoy, y que la probabilidad de tener un día despejado mañana es de 0.9, si está despejado hoy.
a) Determínese la matriz de transición en un paso de la cadena de Markov.
b) Hállense las probabilidades de estado estacionario.
2) El centro de cómputo en Rockbottom University sufre paros de las computadoras. Supongamos que los ensayos de un proceso de Markov asociado se definen como periodos de una hora y la probabilidad de que el sistema esté en un estado de operación o un estado de paro se base en el estado del sistema durante el periodo anterior. Los datos históricos muestran las siguientes probabilidades de transición:
a) Si el sistema inicialmente opera, ¿Cuál es la probabilidad de que el sistema esté detenido en la siguiente hora de operación?
b) ¿Cuáles son las probabilidades de un estado estable del sistema en el estado de operación y en el detenido?
3) Los datos reunidos acerca de importantes áreas metropolitanas seleccionadas de la parte este de Estados Unidos muestran que 2% de los individuos que viven dentro de los límites de la ciudad se mudan a los suburbios en un periodo de un año, en tanto que 1% de los individuos que viven en los suburbios se mudan a la ciudad en un periodo de un año. Responda las siguientes preguntas, suponiendo que este proceso queda modelado por un proceso de Markov con dos estados: ciudad y suburbios.
a) Prepare la matriz de probabilidad de transición.
b) Calcule las probabilidades de estado estable.
c) En un área metropolitana especifica, 40% de la población vive en la ciudad y 60% vive en los suburbios ¿Qué cambios en la población resultan de las probabilidades de estado estable para esta área metropolitana?.
Fuente: HILLIER F.S. Y LIEBERMAN G.J. Introducción a la investigación de operaciones. Sexta edición. Mc Graw Hill. 1997.
Preguntas
Dada la información suministrada en este blog sobre cadenas de Markov, es necesario que usted resuelva las siguientes preguntas con el propósito de hacerse una autoevaluación:
1) ¿En qué año se creó la teoría de cadenas de Markov?
2) ¿Quién creo las cadenas de Markov?
3) ¿A qué se debe el descubrimiento de las cadenas de Markov?
4) ¿Cuándo una matriz es absorbente?
5) ¿Cuándo una matriz se considera no absorbente?
6) ¿De qué sirve plantear una matriz identidad?
7) ¿Qué datos se deben tener para hallar la probabilidad de que un estado cambie a otro?
8) ¿Qué procedimiento se debe seguir para hallar la participación de un estado en un futuro?
9) ¿Para qué sirven las cadenas de Markov?
10) ¿Por qué es indispensable saber la participación de un estado en un futuro?
TEORIA DE JUEGOS
ORIGEN
La teoría de juegos fue inventada por el germano-estadunidense John Von Neumann en 1926, su teoría sorprendió a la comunidad científica porque proporcionaba un análisis estratégico de un tema que parecía escapar del análisis: los juegos de habilidad, pero fue cuando Von Neumann publicó junto a Oscar Morgenstern, en 1944, el clásico libro Theory of games and economic behavior ('Teoría de juegos y comportamiento económico') que la teoría fue comprendía como una gran herramienta.
Fuente: AGUADO FRANCO, Juan Carlos. Teoría de la decisión y de los juegos. Delta publicaciones. Pág 55-61.
BIOGRAFIA DE JOHN VON NEUMANN
Budapest, 1903 - Washington, 1957. Matemático húngaro, nacionalizado estadounidense. Nacido en el seno de una familia de banqueros judíos, dio muestras desde niño de unas extraordinarias dotes para las matemáticas. En 1921 se matriculó en la Universidad de Budapest, donde se doctoró en matemáticas cinco años después, aunque pasó la mayor parte de ese tiempo en otros centros académicos. En la Universidad de Berlín asistió a los cursos de Albert Einstein. Estudió también en la Escuela Técnica Superior de Zúrich, donde en 1925 se graduó en ingeniería química, y frecuentó así mismo la Universidad de Gotinga.
Allí conoció al matemático David Hilbert –cuya obra ejerció sobre él considerable influencia– y contribuyó de manera importante al desarrollo de lo que Hilbert llamó la teoría de la demostración y aportó diversas mejoras a la fundamentación de la teoría de conjuntos elaborada por E. Zermelo. En Gotinga asistió también al nacimiento de la teoría cuántica de Werner Heisenberg y se interesó por la aplicación del programa formalista de Hilbert a la formulación matemática de esa nueva rama de la física.
Ello le llevó a convertirse en el autor de la primera teoría axiomática abstracta de los llamados –precisamente por él– espacios de Hilbert y de sus operadores, que a partir de 1923 habían empezado a demostrar su condición de instrumento matemático por excelencia de la mecánica cuántica; la estructura lógica interna de esta última se puso de manifiesto merced a los trabajos de Von Neumann, quien contribuyó a proporcionarle una base rigurosa para su exposición.
También es notable su apertura de nuevas vías al desarrollo de la matemática estadística a partir de su estudio de 1928 sobre los juegos de estrategia, posteriormente desarrollado en la famosa obra Theory of games and economic behavior, publicada en 1944 y escrita en colaboración con O. Morgenstern.
En 1943, el ejército estadounidense reclamó su participación en el Proyecto Manhattan para la fabricación de las primeras bombas atómicas; a partir de entonces, Von Neumann colaboró permanentemente con los militares, y sus convicciones anticomunistas propiciaron que interviniera luego activamente en la fabricación de la bomba de hidrógeno y en el desarrollo de los misiles balísticos.
Entre 1944 y 1946 colaboró en la elaboración de un informe para el ejército sobre las posibilidades que ofrecía el desarrollo de las primeras computadoras electrónicas; de su contribución a dicho desarrollo destaca la concepción de una memoria que actuase secuencialmente y no sólo registrara los datos numéricos de un problema sino que además almacenase un programa con las instrucciones para la resolución del mismo.
Se interesó también por la robótica y en 1952 propuso dos modelos de máquinas autorreproductoras, uno de ellos con una modalidad de reproducción parecida a la de los cristales, mientras que el otro era más próximo a la forma en que se reproducen los animales. En 1955, tras solicitar la excedencia de Princeton, fue nombrado miembro de la Comisión de Energía Atómica del gobierno estadounidense; ese mismo año un cáncer en estado muy avanzado lo apartó de toda actividad hasta su muerte.
Fuente: MARTÍNEZ HERRERA, David. Artículo de biografía de John Von Neumman.2005.
Fuente: MARTÍNEZ HERRERA, David. Artículo de biografía de John Von Neumman.2005.
BIOGRAFÍA DE OSKAR MORGENSTERN
(24 de enero, 1902 - 26 de Julio de 1977) era Alemán llevado Economista austriaco. Él junto con Juan Von Neumann, ayudado encontrado el campo matemático de teoría de juego. Morgenstern fue llevado adentro de Gorlitz, Alemania. Su madre era una hija ilegitima de Frederick II, emperador alemán. Adentro lo educaba Viena, y era un recipiente de una beca de tres años financiada por Fundación Rockefeller. Cuando Adolfo Hitler asumió el control Viena con Anschluss, Morgenstern estaba en Estados Unidos y le parece una buena idea permanecer allí.
Él hizo un miembro de la facultad en Universidad de Princeton, pero gravitado hacia instituto. Su primer libro era “predicción económica”. En 1944, él y von Neumann co-escribieron Teoría de Juegos y del comportamiento económico, reconocido como el primer libro en teoría de juego. Morgenstern también escribió el libro “en la exactitud de observaciones económicas”. Él aplicó teoría de juego a negocio. Él murió adentro Princeton, New Jersey, en los Estados Unidos.
Fuente: MARTÍNEZ HERRERA, David. Artículo de biografía de Oskar Morgenstern.2005.
Fuente: MARTÍNEZ HERRERA, David. Artículo de biografía de Oskar Morgenstern.2005.
¿Qué es teoria de juego? Objetivos
En todo momento la vida ha estado llena de conflictos y de competencia. Algunos ejemplos en donde se presentan distintos conflictos son los siguientes: Batallas militares, campañas políticas, campañas publicitarias, mercadeo de empresas competidoras, entre otras. La combinación de estrategias que los adversarios utilicen influirá en el resultado final.
Entonces, nos preguntamos ¿Cómo poder determinar las estrategias a utilizar?, la respuesta a esta pregunta es la teoría de juegos. Esta teoría matemática que trata de las características generales de las situaciones de competencia de una manera formal, abstracta. Siendo esta un proceso de toma de decisiones por los adversarios, con el propósito de utilizar la mejor estrategia en el momento adecuado para no poner alerta al adversario de que estrategia deba utilizar para ganar el juego.
Gran parte de la investigación sobre la teoría de juegos ha sido en relación con los juegos de dos personas y suma cero. Como el nombre indica, estos juegos comprenden únicamente a dos adversarios o jugadores. Se conocen como de su ma cero porque uno de los jugadores gana en tanto que el otro pierde, de modo que la suma de sus ganancias netas es cero.
OBJETIVO DE LA TEORÍA DE JUEGOS
Su objetivo principal es la desarrollar criterios racionales para seleccionar una estrategia. Siendo una estrategia una acción definida por un tomador de decisiones con el fin de neutralizar o contrarrestar otra acción de su adversario. Una estrategia puede comprender solo una acción simple para juegos simples. Por otra parte, en juegos más complicados que comprenden una serie de movimientos, una estrategia es una regla predeterminada que especifica completamente cómo se piensa responder a cada una de las circunstancias posibles en cada etapa del juego. Antes de que se inicie el juego, cada jugador conoce sus propias estrategias, las de su oponente y la tabla de resultados. El desarrollo real del juego consiste en que los jugadores eligen simultáneamente una estrategia sin conocer la elección de su oponente.
El problema general de cómo tomar decisiones en un medio de competencia es muy común e importante. La contribución fundamental de la teoría de juegos es que suministra una estructura conceptual para plantear y analizar tales problemas en situaciones simples. Sin embargo, existe una brecha considerable entre lo que la teoría de juegos puede manejar y la complejidad de la mayor parte de las situaciones de competencia que surgen en la práctica. Por lo tanto, las herramientas conceptuales de la teoría de juegos por lo común desempeñan solo un papel suplementario al tratar con estas situaciones.
Debido a la importancia del problema general, se está continuando la investigación con cierto éxito para extender la teoría hacia situaciones más complejas.
Fuente: WINSTON WAYNE, L. (1994). Investigación de operaciones, aplicaciones y algoritmos. Segunda edición. Grupo editorial Iberoamérica. Teoría de juegos.
Fuente: WINSTON WAYNE, L. (1994). Investigación de operaciones, aplicaciones y algoritmos. Segunda edición. Grupo editorial Iberoamérica. Teoría de juegos.
Aplicaciones
La Teoría de Juegos actualmente tiene muchas aplicaciones, sin embargo, la economía es el principal cliente para las ideas producidas por los especialistas en Teoría de Juego. Entre las disciplinas donde hay aplicación de la Teoría de Juegos tenemos:
La ciencia -política
En la biología
En la filosofía
En general la teoría de juegos se aplica en todo campo en el cual se tiene un adversario y por lo cual de debe de tener estrategias que ayuden a ganar.
Fuente: GONZÁLEZ CONDE, Medardo. Clase de modelos matemáticos de producción. Universidad libre seccional Barranquilla. 08/09/10.
Fuente: GONZÁLEZ CONDE, Medardo. Clase de modelos matemáticos de producción. Universidad libre seccional Barranquilla. 08/09/10.
Ejemplo Ilustrativo
Para formar las características básicas de la teoría de juegos, consideremos una versión simplificada del juego de los dos dedos.
Este juego incluye a dos jugadores, los cuales muestran simultáneamente uno o dos dedos de una mano.
Luis y Andrea están practicando este clásico juego, si ambos muestran un dedo, Andrea la paga a Luis $6, si Luis muestra un dedo y Andrea dos, Luis paga a Andrea $11, si Luis saca dos dedos y Andrea uno, Andrea paga a Luis $3, si Luis saca dos dedos y Andrea dos dedos, Luis paga a Andrea $2.
Teniendo en cuenta que Luis es el jugador renglón y Andrea el jugador columna, el arreglo matemático de apuestas se resume en la siguiente matriz, llamada Matriz de recompensa:
JUGADOR COLUMNA
| |||
muestra un dedo
|
muestra dos dedos
| ||
JUGADOR RENGLON
|
muestra un dedo
|
6
|
-11
|
muestra dos dedos
|
3
|
2
| |
Para el renglón 1 columna 1, indica que Andrea le paga a Luis $6, en este caso el premio de Luis es $6 y el de Andrea es $-6 por lo tanto para el resultado de este caso y el de los demás la suma de los premios es 0, por lo tanto el juego se denomina suma cero.
Esto significa que la ganancia de Luis y Andrea promedian entre $0 por cada juego, si este lo realizan una gran cantidad de veces, pero Luis sospecha que él lleva más ventaja porque tiene más maneras de ganar a Andrea, y esta sospecha que ella lleva ventaja porque cuando gana, sus éxitos son mayores que los de Luis.
ESTRATEGIAS PURAS
De las estrategias la más simple de todas es aquella en la que el jugador constantemente elige siempre el mismo renglón o columna, a dichas estrategias se les denomina estrategias puras.
Usando la matriz de recompensa del juego de Luis y Andrea donde I es sacar un dedo y II es sacar dos dedos encontremos cuales son las estrategias puras que usa cada uno de ellos y determinar si alguno debería desviarse de su mejor estrategia pura:
I
|
II
| |
I
|
6
|
-11
|
II
|
3
|
2
|
La mayor ganancia de Luis ocurre cuando él y Andrea muestran un dedo, sin embargo si el muestra constantemente un dedo, Andrea descubrirá pronto la estrategia de Luis y de igual forma ella mostrara siempre dos dedos, lo cual daría como resultado que sea Luis quien pague a Andrea $11 por juego. Por otra parte si Luis siempre muestra dos dedos, Andrea del mismo modo mostrara dos dedos con lo cual solo pagara a Luis $2 por juego. Para Luis es mejor recibir $2 que paga $11, así su mejor estrategia pura consiste en mostrar siempre dos dedos.
Si Andrea muestra constantemente un dedo tendría que pagar $6 o $3 a Luis. Este respondería ante esta estrategia para mostrarle un dedo con los cual ganaría $6 por juego. Si Andrea muestra siempre dos dedos, pagara $2 a Luis o éste pagara $11. A su vez Luis respondería mostrando dos dedos y ganaría $2 por juego. Andrea estaría mejor si pagara $2 en vez de $6, asi su mejor estrategia pura es mostrar siempre dos dedos.
Andrea no deberá desviarse de su mejor estrategia pura porque si lo hace deberá pagar a Luis $3 por juego. De la misma forma Luis no deberá desviarse de su mejor estrategia pura, porque de lo contrario deberá pagar $11 a Andrea por juego.
VALOR DEL JUEGO
Si Luis y Andrea se consolidan con sabiduría a sus mejores estrategias puras, cada uno elegirá siempre dos dedos lo cual favorecería siempre a Luis, incluso seria aun más sabio si Andrea se retira del juego, ya que Andrea siempre pagara $2 a Luis, a este $2 se le denomina valor del juego.
Una forma más sencilla de determinar el valor del juego y la estrategia más pura de un jugador es de la matriz de recompensa elegir el mínimo de cada renglón y de esos el máximo y el máximo de cada columna y de esos el menor, también se le conoce como criterio mini Max para los renglones y criterio MAXI mini para la columna, lo cual se realiza así:
I
|
II
|
miniMAX
| |
I
|
6
|
-11
|
-11
|
II
|
3
|
2
|
2
|
MAXImini
|
6
|
2
|
Como se observa los menores de cada renglón son -11 y 2 y de estos el mayor es 2, de igual forma en las columnas los mayores de cada una son 6 y 2 y de estos el menor es dos, si pasamos una línea en la intercepción de estos dos valores así:
I
|
II
|
miniMAX
| |
I
|
6
|
-11
|
-11
|
II
|
3
|
2
|
2
|
MAXImini
|
6
|
2
|
Esa intersección es la que denominamos valor del juego lo cual nos indica también que el juego está estrictamente determinado y que las estrategia a usar por Luis es la II, es decir, mostrar siempre dos dedos y la de Andrea es la II, es decir mostrar siempre dos dedos.
Miremos otro ejemplo, con la siguiente matriz de recompensa determinar el valor del juego, las estrategias de cada jugador y si es un juego determinado:
I
|
II
|
mínimax
| |
I
|
2
|
3
|
2
|
II
|
-2
|
2
|
-2
|
MAXImini
|
2
|
3
|
Como se observa el máximo de los mínimos es 2 y el minino de los máximos es 2, por tal motivo el valor del juego es 2, la estrategia usada por el jugador renglón es la estrategia I y la del jugador columna es la estrategia I.
Pero ¿qué pasa cuando el juego es indeterminado y no podemos encontrar el valor del juego?
CUANDO EL JUEGO NO ESTA ESTRICTAMENTE DETERMINADO
· Método algebraico:
Tomemos como ejemplo si dos personas juegan el juego de los dedos, en esta versión llamaremos a uno de los jugadores impar, el cual gana si la suma de los dedos que saca él y el otro jugador es impar, al otro jugador lo llamaremos par y el cual gana si la suma de los dedos que saque él y el jugador impar es par, la ganancia es la suma de los dedos, miremos la matriz de recompensa:
PAR
| |||
I
|
II
| ||
IMPAR
|
I
|
-2
|
3
|
II
|
3
|
-4
| |
Ahora determinemos los criterios mini Max y MAXI mini:
PAR
| ||||
I
|
II
|
miniMAX
| ||
IMPAR
|
I
|
-2
|
3
|
-2
|
II
|
3
|
-4
|
-4
| |
MAXImini
|
3
|
3
| ||
Como se observa no hay un elemento que sea simultáneamente el máximo de los mínimos y el mínimo de los máximos por lo tanto no podemos encontrar el valor del juego, las estrategias, lo que indican que el juego no está estrictamente determinado.
En este caso los jugadores deberán adoptar estrategias mixtas las cuales consisten en una combinación de varias estrategias escogidas al azar, una cada vez, según determinadas probabilidades.
Una forma de hallar esas probabilidades es a través del método algebraico, donde la probabilidades de hallar el renglón I o II es respectivamente p1 y p2 y suponiendo que el jugador columna adopta una estrategia pura. Entonces para hallarlas seria de este modo:
p1 p2
|
-2
|
3
| |
3
|
-4
|
[p1*-2 + 3p2 ; p1*3 + p2*-4]
Si remplazamos p2 por 1-p1, recordemos que la suma de las proporciones p1 y p2 debe dar 1, tendríamos:
[p1*-2 + (1-p1)*3 ; p1*3 + (1-p1)*-4]
[ -2 p1 +3 - 3p1 ; 3p1 -4 + 4p1]
[ -5 p1 + 3 ; 7p1 - 4]
Luego de obtener estas dos ecuaciones las igualamos y encontramos el valor de la proporción de p1:
-5 p1 + 3 = 7p1 – 4
-5 p1 -7p1= – 4 - 3
-12p1= -7
p1= 7/12
Reemplazamos en 1- p1 para hallar el valor de p2:
p2 = 1 – p1
p2 = 1 – 7/12
p2= 5/12
Esto nos indica que 7/12 de las veces el jugador impar usara la estrategia 1 y que las 5/12 usara la estrategia 2.
· Método gráfico:
El método grafico es otro procedimiento que se sigue para resolver un ejercicio cuyo juego no se encuentra estrictamente determinado, tal y como se muestra en el siguiente ejemplo:
1. Para la tabla siguiente, utilícese el procedimiento grafico para determinar el valor del juego y la estrategia mixta óptima para cada jugador, de acuerdo con el criterio mínimax:
A continuación se muestra la explicación de la solución de este ejercicio por medio del procedimiento gráfico, con el propósito de determinar lo establecido en el ejercicio. En la hoja siguiente esta solución:
Ahora veamos como soluciones un juego que no está estrictamente determinado a través de la programación lineal usando Excel y la herramienta solver.
ELIMINACIÓN DE ESTRATEGIAS DOMINADAS MATRIZ DE RECOMPESA REDUCIDA
Cuando en un juego existe más de dos estrategias es posible eliminar aquellas estrategias que resulten no ser tan efectivas, a las estrategias que puede eliminarse se les llama estrategias dominadas y la matriz que queda como resultado de esa eliminación se llama matriz de recompensa reducida.
De la siguiente matriz de recompensa determine que estrategias se puede eliminar y halle la matriz de pago reducida:
C1
|
C2
|
C3
|
C4
| |
R1
|
1
|
2
|
-2
|
-2
|
R2
|
-1
|
-2
|
3
|
3
|
R3
|
-1
|
-3
|
-3
|
-3
|
Lo elementos positivos indican que son ganancia del jugador renglón y los elementos negativos ganancia del jugador columna, tomemos primero el renglón 1 y el renglón 2, aquí no hay posibilidad de eliminar alguno ya que no todos los elementos del renglón 1 domina a los del renglón 2 ya que si miramos para el e mejor ganar 1 que perder -1, mejor ganar 2 que perder -2, pero no le es mejor perder -2 que ganar 3.
Si tomamos el renglón 1 y el renglón 3 se observa que cada elemento del renglón 1 es mayor o igual que del 3 (1>= -1, 2 >= -3, -2 >= -3 y -2>= -3), lo que indica que el renglón 1 domina al renglón 3
Hagamos ahora con el renglón 2 donde cada elemento del renglón es mayor o igual que los del renglón 3, (-1>= -1, -2 >= -3, 3 >=3 y 3>=-3), el jugador renglón no debería jugar con la estrategia 3 y por tal motivo se elimina.
En el caso de las columnas la estrategia 3 domina a la 4, ya que en ambas tiene el mismo resultado, con las otras dos no existe un dominancia constante, por tal motivo se elimina la columna 4, y la matriz de recompensa reducida seria:
C1
|
C2
|
C3
| |
R1
|
1
|
2
|
-2
|
R2
|
-1
|
-2
|
3
|
EJEMPLO DE EJERCICIOS RESUELTOS EN EXCEL
https://spreadsheets.google.com/ccc?key=tqHNxfgTCxCtS8FuK7t_Phg&hl=en#gid=2
Fuente: MOWRY, Tomas. JOHNSON, David. Matemáticas finitas. Aplicaciones prácticas. Pág 361.
Suscribirse a:
Entradas (Atom)