Transcript 9.4 Linear programming and m x n Games: Simplex Method and the

9.4 Linear programming and m x n Games:
Simplex Method and the Dual Problem
In this section, the process of solving 2 x 2 matrix
games will be generalized to solving m x n matrix
games. The procedure will be essentially the same as
the process for the 2 x 2 case, but the solution of the
linear programming problem will incorporate the
simplex method and the dual.
Procedure:

Given the non-strictly determined matrix game M, free of
recessive rows and columns,
 r1 r2 r3 

 q1 
*
to find P   p1 p2  Q *   q2 
 q3 
proceed as follows:

1.

s2
s3 
If M is not a positive matrix, add a suitable positive constant k
to each element of M to get a new matrix M1
 a1 a2
M1  
 b1 b2

and v
M 
 s1
a3 
b3 
If v1 is the value of game M1 , then the value of the original game
M is given by v = v1 – k
Procedure continued:



2. Set up the two linear programming problems ( maximization
problem is always the dual of the minimization problem) :
A) Minimize
subject to :
y  x1  x2
a1 x1  b1 x2  1
a2 x1  b2 x2  1
a3 x1  b3 x2  1
x1 , x2  0

B) Maximize:
y  z1  z2  z3
a1 z1  a2 z2  a3 b3  1

subject to:
b1 z1  b2 z2  b3 z 3  1
z1 , z2 , z3  0
Procedure continued:



Step 3. Solve the maximization problem, part (B) , the dual of
part (A), using the simplex method as modified in section 5.5.
[You will automatically obtain the solution of the minimization
problem, Part A, as well, by following this process. ]
Step 4. Use the solutions from the third step to find the value of
the game , v1 for game M1 and the optimal strategies and value
V
for the original game,
1
1
v1  
y z1  z2  z3
v  v1  k
M.
P*  v1 x1 v1 x2 
 v1 z1 
Q *   v 2 z2 
 v 3 z3 
An example







Suppose that an investor wishes to invest $10,000 in long
and short term bonds, as well as in gold, and he is
concerned about inflation. After some analysis he
estimates that the return (in thousands of dollars) at the
end of a year will be indicated in the following payoff
matrix:
Inflation rate
up 3% down 3%
 3 3 


long term bonds  3
2


short-term bonds   1
1 

gold
Example continued


Assume that fate is a very good player that will attempt to
reduce the investor’s return as much as possible. Find the
optimal strategies for both the investor and fate. What is
the value of the game?
1. We start with the payoff matrix and need to make all
entries positive so we choose to add a constant k = 4 to
each entry:
 3 3 
 3 2 


 1 1 
 7 1
2 6


 3 5 
Example continued
2. Write the corresponding linear programming problems:
min y  x1  x2  x3
subject to:
7 x1  2 x2  3 x3  1
1 x1  6 x2  5 x3  1
x1 , x2 , x3  0
Maximize:
y  z1  z2
subject to:
7 z1  z2  1
2 z1  6 z2  1
3 z1  5 z2  1
z1 , z2  0
Example continued:


3. Introduce slack variables and form the simplex tableau
and solve the second linear programming problem:
7 z1  z2  x1  1
2 z1  6 z2  x2  1
3 z1  5 z2  x3  1
 z1  z2  y  0
z1
 7
 2

 3

 1
z2
x1
x2
x3
y
1 1 0 0 0 1 
6 0 1 0 0 1 
5 0 0 1 0 1 

1 0 0 0 1 0 
Solution:

After performing the steps, the final solution is displayed
below: The value of the game is zero, which means it is a
fair game.
P *   0.25 0 0.75
0.5 
Q  
0.5 
v0
*