Facultad de Ingeniería y Arquitectura Profesor Luis Antonio Durand Romero
Introducción a los
Modelos Estocásticos
Programación Lineal
en la Teoría de Juegos
Facultad de Ingeniería y Arquitectura Profesor Luis Antonio Durand Romero
Capacidades
Conocer cuando se debe aplicar
programación lineal a un Juego.
Conocer las partes de un MPL en la
teoría de juegos.
Aplicar modelos de programación
lineal e interpretarlos.
Facultad de Ingeniería y Arquitectura Profesor Luis Antonio Durand Romero
1. Programación Lineal en
la Teoría de Juegos
Consiste en resolver la MATRIZ de
RETRIBUCIONES de orden mxn mediante
Programación Lineal.
Facultad de Ingeniería y Arquitectura Profesor Luis Antonio Durand Romero
Facultad de Ingeniería y Arquitectura Profesor Luis Antonio Durand Romero
Maximin ≠ MiniMax
Es decir, no existe equilibrio.
Esto indica que los jugadores no pueden
elegir o jugar con una sola estrategia.
Sino que se debe aplicar una estrategia
mixta.
Facultad de Ingeniería y Arquitectura Profesor Luis Antonio Durand Romero
2. Componentes del
modelo de
Programación Lineal
Un MPL en la Teoría de Juegos tiene
los siguientes componentes para el
Jugador 1.
I. Variables de Decisión
Xi=Porcentaje de veces
que se usa la
estrategia i(1,…,m),
con 0≤ Xi ≤1
G=Retribución obtenida,
con G≥0.
X1 X2:
Xm
Facultad de Ingeniería y Arquitectura Profesor Luis Antonio Durand Romero
II. Función Objetivo
2. Componentes del
modelo de
Programación Lineal
Maximizar La Retribución Espera
Max G
Facultad de Ingeniería y Arquitectura Profesor Luis Antonio Durand Romero
Tenemos:
III. Restricciones
2. Componentes del
modelo de
Programación Lineal
a11x1+a
21x2+...+a
m1xm>=G
a12x1+a
22x2+...+a
m2xm>=G
⋮a1nx1+a
2nx2+...+a
mnxm>=G
x1
+ x2 + ⋯+ x
m= 1
X1 X2:
Xm
Facultad de Ingeniería y Arquitectura Profesor Luis Antonio Durand Romero
3. El Modelo de PL para
el Jugador 1El modelo de Programación Lineal para
una estrategia mixta es:
MAX G
ST
a11x1+a
21x2+...+a
m1xm– G >=0
a12x1+a
22x2+...+a
m2xm– G >=0
⋮a1nx1+a
2nx2+...+a
mnxm– G >=0
x1
+ x2 + ⋯+ x
m= 1
END
En
formato
LINDO
0≤ Xi ≤1 y G≥0
Facultad de Ingeniería y Arquitectura Profesor Luis Antonio Durand Romero
Nuestra empresa y otra de los
más grandes productores de
agendas electrónicas se
proponen sacar al mercado un
modelo nuevo con teléfono
móvil incorporado.
Pueden establecer un convenio
con cuatro de las compañías
telefónicas y uno de los dos
podría desarrollar una
compañía telefónica propia.
Caso de aplicación
Facultad de Ingeniería y Arquitectura Profesor Luis Antonio Durand Romero
La matriz de ganancias (en millones de
soles) se presenta a continuación
MoviSun EntFone UnderHill WindTel
MoviSun 10 -20 -5 -10
EntFone 15 10 5 6
UndeHill 30 25 -10 -5
WindTel 25 10 -30 -20
PhoneCasie 10 -20 15 -5
a. ¿Existe
equilibrio?
b. ¿Cuál es la
mejor
estrategia
para nuestra
compañía?
MOVI
MI-COM
Interprete
los
resultados
Facultad de Ingeniería y Arquitectura Profesor Luis Antonio Durand Romero
Solución
El modelo de Programación Lineal para
MI-COM es:
MAX G
ST
10x1+15x
2+30x
3+25x
4+10x
5-G >=0
-20x1+10x
2+25x
3+10x
4-20x
5-G >=0
-5x1+ 5x
2-10x
3-30x
4+15x
5-G >=0
-10x1+ 6x
2-5x
3-20x
4- 5x
5–G >=0
x1
+ x2 + x
3+ x
4 + x
5 = 1
ENDEn
formato
LINDO
0≤ Xi ≤1 y G≥0
Facultad de Ingeniería y Arquitectura Profesor Luis Antonio Durand Romero
Cuya solución con el software LINDO es
Se debe hacer convenios con EntFone en
un 95.2% y se puede crear PhoneCasie
4.8% obteniéndose un beneficio de
5.476191 millones.
LP OPTIMUM FOUND AT STEP 6
OBJECTIVE FUNCTION VALUE
1) 5.476191
VARIABLE VALUE REDUCED COST
G 5.476191 0.000000
X1 0.000000 12.857142
X2 0.952381 0.000000
X3 0.000000 13.095238
X4 0.000000 30.714285
X5 0.047619 0.000000
¿Cuál es la
mejor
estrategia
para MOVI
Facultad de Ingeniería y Arquitectura Profesor Luis Antonio Durand Romero
4. El Modelo de PL para
el Jugador 2El modelo de Programación Lineal para
una estrategia mixta es:
MIN G
ST
a11Y1+a
12Y2+...+a
1nYn– G <=0
a21Y1+a
22Y2+...+a
2nYn– G <=0
⋮am1Y1+a
m2Y2+...+a
mnYn– G <=0
Y1
+ Y2 + ⋯+ Y
n= 1
END
En
formato
LINDO
0≤ Yi ≤1 y G≥0
Facultad de Ingeniería y Arquitectura Profesor Luis Antonio Durand Romero
Dos empresas de Catering van a ofrecer
sus servicios durante la Cumbre del FMI y
Banco Mundial asistirán 3000 personas.
Han de ofrecer los alimentos y la
publicidad simultáneamente y con
antelación a la celebración del congreso.
La empresa CATA (jugador 1) podría optar
por tres modalidades distintas, mientras
que la empresa MABRYS tiene dos
posibilidades
Caso de aplicación
Facultad de Ingeniería y Arquitectura Profesor Luis Antonio Durand Romero
La matriz de beneficios esta formada por
una estimación del número de comensales
en CATA según las diversas estrategias
Modalidad A Modalidad B
Modalidad 1 1500 2400
Modalidad 2 1400 2500
Modalidad 3 1800 1700
CATA
MABRYS
a. ¿Existe
equilibrio?
b. Que
modalidades
debe ofrecer
CATA.
c. Que
modalidades
puede aplicar
MABRYS.
Interprete
los
resultados
Facultad de Ingeniería y Arquitectura Profesor Luis Antonio Durand Romero
Solución
El modelo de Programación Lineal para
MABRIS es:
MIN G
ST
1500Y1+2400Y2-G<=0
1400Y1+2500Y2-G<=0
1800Y1+1700Y2-G<=0
Y1+Y2=1
END
En
formato
LINDO
0≤ Yi ≤1 y G≥0
Facultad de Ingeniería y Arquitectura Profesor Luis Antonio Durand Romero
Cuya solución con el software LINDO es
¿Cuál es la interpretación de los
resultados?
LP OPTIMUM FOUND AT STEP 6
OBJECTIVE FUNCTION VALUE
1) 1770.000
VARIABLE VALUE REDUCED COST
G 1770.000000 0.000000
Y1 0.700000 0.000000
Y2 0.300000 0.000000
Facultad de Ingeniería y Arquitectura Profesor Luis Antonio Durand Romero
Bibliografía
[1] Frederick S. Hillier y Gerald J.
Lieberman. (2002). Investigación de
operaciones. (7a ed.). - México:
McGraw-Hill.
[2] Wayne L. Winston. (2005).
Investigación de operaciones:
Aplicaciones y Algoritmos. (4a ed.).-
México: Thomson.
Top Related