Home > Operation Research calculators > Game Theory >> LPP method example

9. Linear programming method example ( Enter your problem )
  1. Method & Example-1
  2. Example-2
Other related methods
  1. Saddle point
  2. Dominance method
  3. Algebraic method
  4. Calculus method
  5. Arithmetic method
  6. Matrix method
  7. 2Xn Games
  8. Graphical method
  9. Linear programming method
  10. Bimatrix method

1. Method & Example-1



Method
linear programming method Steps (Rule)
Step-1: The linear programming technique is used for solving mixed strategy games of dimensions greater than (2`xx`2) size.
Step-2: The example is used to explain the procedure.

Example-1
1. Find Solution of game theory problem using linear programming method
Player A\Player BB1B2B3
A13-42
A21-7-3
A3-247


Solution:
1. Saddle point testing
Players
Player `B`
`B_1``B_2``B_3`
Player `A``A_1` 3  -4  2 
`A_2` 1  -7  -3 
`A_3` -2  4  7 


We apply the maximin (minimax) principle to analyze the game.

Player `B`
`B_1``B_2``B_3`Row
Minimum
Player `A``A_1` (3)  -4  2 `-4`
`A_2` 1  -7  -3 `-7`
`A_3` [-2]  4  7 `[-2]`
Column
Maximum
`(3)``4``7`


Select minimum from the maximum of columns
Column MaxiMin = (3)

Select maximum from the minimum of rows
Row MiniMax = [-2]

Here, Column MaxiMin `!=` Row MiniMax

`:.` This game has no saddle point.



So the value of the game lies between -2 and 3
It is possible that the value of game may be negative or zero.
Thus, a constant k is added to all the elements of pay-off matrix.
Let k = 3, then the given pay-off matrix becomes:
Player `B`
`B_1``B_2``B_3`
Player `A``A_1` 6  -1  5 
`A_2` 4  -4  0 
`A_3` 1  7  10 



Let V = value of the game
`p_1,p_2,p_3` = probabilities of selecting strategies `A_1,A_2,A_3` respectively.

`q_1,q_2,q_3` = probabilities of selecting strategies `B_1,B_2,B_3` respectively.

Player `B`
`B_1``B_2``B_3`Probability
Player `A``A_1` 6  -1  5 `p_1`
`A_2` 4  -4  0 `p_2`
`A_3` 1  7  10 `p_3`
Probability`q_1``q_2``q_3`





player A's objective is to maximize the expected gains, which can be achieved by maximizing V, i.e., it might gain more than V if company B adopts a poor strategy.
The expected gain for player A will be as follows
`6p_1+4p_2+p_3>=V`

`-p_1-4p_2+7p_3>=V`

`5p_1+0p_2+10p_3>=V`


Dividing the above constraints by V, we get
`6(p_1/V)+4(p_2/V)+(p_3/V)>=1`

`-(p_1/V)-4(p_2/V)+7(p_3/V)>=1`

`5(p_1/V)+0(p_2/V)+10(p_3/V)>=1`


To simplify the problem, we put
`p_1/V=x_1,p_2/V=x_2,p_3/V=x_3`


In order to maximize V, player A can
Minimize `Z_p=1/V = x_1+x_2+x_3`

subject to
`6x_1+4x_2+x_3>=1`

`-x_1-4x_2+7x_3>=1`

`5x_1+0x_2+10x_3>=1`

and `x_1,x_2,x_3>=0`


player B's objective is to minimize its expected losses, which can be reduced by minimizing V, i.e., player A adopts a poor strategy.
The expected loss for player B will be as follows
`6q_1-q_2+5q_3<=V`

`4q_1-4q_2+0q_3<=V`

`q_1+7q_2+10q_3<=V`


Dividing the above constraints by V, we get
`6(q_1/V)-(q_2/V)+5(q_3/V)<=1`

`4(q_1/V)-4(q_2/V)+0(q_3/V)<=1`

`(q_1/V)+7(q_2/V)+10(q_3/V)<=1`


To simplify the problem, we put
`q_1/V=y_1,q_2/V=y_2,q_3/V=y_3`


In order to minimize V, player B can
Maximize `Z_q=1/V = y_1+y_2+y_3`

subject to
`6y_1-y_2+5y_3<=1`

`4y_1-4y_2+0y_3<=1`

`y_1+7y_2+10y_3<=1`

and `y_1,y_2,y_3>=0`


Now, solve this problem using simplex method.


Problem is
Max `Z_q``=``````y_1`` + ````y_2`` + ````y_3`
subject to
```6``y_1`` - ````y_2`` + ``5``y_3``1`
```4``y_1`` - ``4``y_2``1`
`````y_1`` + ``7``y_2`` + ``10``y_3``1`
and `y_1,y_2,y_3 >= 0; `


The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate

1. As the constraint 1 is of type '`<=`' we should add slack variable `S_1`

2. As the constraint 2 is of type '`<=`' we should add slack variable `S_2`

3. As the constraint 3 is of type '`<=`' we should add slack variable `S_3`

After introducing slack variables
Max `Z_q``=``````y_1`` + ````y_2`` + ````y_3`` + ``0``S_1`` + ``0``S_2`` + ``0``S_3`
subject to
```6``y_1`` - ````y_2`` + ``5``y_3`` + ````S_1`=`1`
```4``y_1`` - ``4``y_2`` + ````S_2`=`1`
`````y_1`` + ``7``y_2`` + ``10``y_3`` + ````S_3`=`1`
and `y_1,y_2,y_3,S_1,S_2,S_3 >= 0`


Iteration-1 `C_j``1``1``1``0``0``0`
`B``C_B``X_B` `y_1` Entering variable`y_2``y_3``S_1``S_2``S_3`MinRatio
`(X_B)/(y_1)`
 `S_1` Leaving variable`0``1` `(6)`  (pivot element)`-1``5``1``0``0``(1)/(6)=1/6``->`
`S_2``0``1``4``-4``0``0``1``0``(1)/(4)=1/4`
`S_3``0``1``1``7``10``0``0``1``(1)/(1)=1`
 `Z_q=0` `0=`
`Z_j=sum C_B X_B`
 `Z_j` `Z_j=sum C_B x_j` `0` `0=0xx6+0xx4+0xx1`
`Z_j=sum C_B y_1`
 `0` `0=0xx(-1)+0xx(-4)+0xx7`
`Z_j=sum C_B y_2`
 `0` `0=0xx5+0xx0+0xx10`
`Z_j=sum C_B y_3`
 `0` `0=0xx1+0xx0+0xx0`
`Z_j=sum C_B S_1`
 `0` `0=0xx0+0xx1+0xx0`
`Z_j=sum C_B S_2`
 `0` `0=0xx0+0xx0+0xx1`
`Z_j=sum C_B S_3`
`C_j-Z_j` `1` `1=1-0``uarr` `1` `1=1-0` `1` `1=1-0` `0` `0=0-0` `0` `0=0-0` `0` `0=0-0`


Positive maximum `C_j-Z_j` is `1` and its column index is `1`. So, the entering variable is `y_1`.

Minimum ratio is `1/6` and its row index is `1`. So, the leaving basis variable is `S_1`.

`:.` The pivot element is `6`.

Entering `=y_1`, Departing `=S_1`, Key Element `=6`

`R_1`(new)`= R_1`(old)`-: 6`

`R_2`(new)`= R_2`(old)`- 4 R_1`(new)

`R_3`(new)`= R_3`(old)`- R_1`(new)

Iteration-2 `C_j``1``1``1``0``0``0`
`B``C_B``X_B``y_1` `y_2` Entering variable`y_3``S_1``S_2``S_3`MinRatio
`(X_B)/(y_2)`
`y_1``1` `1/6` `1/6=1-:6`
`R_1`(new)`= R_1`(old)`-: 6`
 `1` `1=6-:6`
`R_1`(new)`= R_1`(old)`-: 6`
 `-1/6` `-1/6=(-1)-:6`
`R_1`(new)`= R_1`(old)`-: 6`
 `5/6` `5/6=5-:6`
`R_1`(new)`= R_1`(old)`-: 6`
 `1/6` `1/6=1-:6`
`R_1`(new)`= R_1`(old)`-: 6`
 `0` `0=0-:6`
`R_1`(new)`= R_1`(old)`-: 6`
 `0` `0=0-:6`
`R_1`(new)`= R_1`(old)`-: 6`
---
`S_2``0` `1/3` `1/3=1-4xx1/6`
`R_2`(new)`= R_2`(old)`- 4 R_1`(new)
 `0` `0=4-4xx1`
`R_2`(new)`= R_2`(old)`- 4 R_1`(new)
 `-10/3` `-10/3=(-4)-4xx(-1/6)`
`R_2`(new)`= R_2`(old)`- 4 R_1`(new)
 `-10/3` `-10/3=0-4xx5/6`
`R_2`(new)`= R_2`(old)`- 4 R_1`(new)
 `-2/3` `-2/3=0-4xx1/6`
`R_2`(new)`= R_2`(old)`- 4 R_1`(new)
 `1` `1=1-4xx0`
`R_2`(new)`= R_2`(old)`- 4 R_1`(new)
 `0` `0=0-4xx0`
`R_2`(new)`= R_2`(old)`- 4 R_1`(new)
---
 `S_3` Leaving variable`0` `5/6` `5/6=1-1/6`
`R_3`(new)`= R_3`(old)`- R_1`(new)
 `0` `0=1-1`
`R_3`(new)`= R_3`(old)`- R_1`(new)
 `(43/6)` `43/6=7-(-1/6)` (pivot element)
`R_3`(new)`= R_3`(old)`- R_1`(new)
 `55/6` `55/6=10-5/6`
`R_3`(new)`= R_3`(old)`- R_1`(new)
 `-1/6` `-1/6=0-1/6`
`R_3`(new)`= R_3`(old)`- R_1`(new)
 `0` `0=0-0`
`R_3`(new)`= R_3`(old)`- R_1`(new)
 `1` `1=1-0`
`R_3`(new)`= R_3`(old)`- R_1`(new)
`(5/6)/(43/6)=5/43``->`
 `Z_q=1/6` `1/6=1xx1/6`
`Z_j=sum C_B X_B`
 `Z_j` `Z_j=sum C_B x_j` `1` `1=1xx1+0xx0+0xx0`
`Z_j=sum C_B y_1`
 `-1/6` `-1/6=1xx(-1/6)+0xx(-10/3)+0xx43/6`
`Z_j=sum C_B y_2`
 `5/6` `5/6=1xx5/6+0xx(-10/3)+0xx55/6`
`Z_j=sum C_B y_3`
 `1/6` `1/6=1xx1/6+0xx(-2/3)+0xx(-1/6)`
`Z_j=sum C_B S_1`
 `0` `0=1xx0+0xx1+0xx0`
`Z_j=sum C_B S_2`
 `0` `0=1xx0+0xx0+0xx1`
`Z_j=sum C_B S_3`
`C_j-Z_j` `0` `0=1-1` `7/6` `7/6=1-(-1/6)``uarr` `1/6` `1/6=1-5/6` `-1/6` `-1/6=0-1/6` `0` `0=0-0` `0` `0=0-0`


Positive maximum `C_j-Z_j` is `7/6` and its column index is `2`. So, the entering variable is `y_2`.

Minimum ratio is `5/43` and its row index is `3`. So, the leaving basis variable is `S_3`.

`:.` The pivot element is `43/6`.

Entering `=y_2`, Departing `=S_3`, Key Element `=43/6`

`R_3`(new)`= R_3`(old)`xx6/43`

`R_1`(new)`= R_1`(old)`+ 1/6 R_3`(new)

`R_2`(new)`= R_2`(old)`+ 10/3 R_3`(new)

Iteration-3 `C_j``1``1``1``0``0``0`
`B``C_B``X_B``y_1``y_2``y_3``S_1``S_2``S_3`MinRatio
`y_1``1` `8/43` `8/43=1/6+1/6xx5/43`
`R_1`(new)`= R_1`(old)`+ 1/6 R_3`(new)
 `1` `1=1+1/6xx0`
`R_1`(new)`= R_1`(old)`+ 1/6 R_3`(new)
 `0` `0=(-1/6)+1/6xx1`
`R_1`(new)`= R_1`(old)`+ 1/6 R_3`(new)
 `45/43` `45/43=5/6+1/6xx55/43`
`R_1`(new)`= R_1`(old)`+ 1/6 R_3`(new)
 `7/43` `7/43=1/6+1/6xx(-1/43)`
`R_1`(new)`= R_1`(old)`+ 1/6 R_3`(new)
 `0` `0=0+1/6xx0`
`R_1`(new)`= R_1`(old)`+ 1/6 R_3`(new)
 `1/43` `1/43=0+1/6xx6/43`
`R_1`(new)`= R_1`(old)`+ 1/6 R_3`(new)
`S_2``0` `31/43` `31/43=1/3+10/3xx5/43`
`R_2`(new)`= R_2`(old)`+ 10/3 R_3`(new)
 `0` `0=0+10/3xx0`
`R_2`(new)`= R_2`(old)`+ 10/3 R_3`(new)
 `0` `0=(-10/3)+10/3xx1`
`R_2`(new)`= R_2`(old)`+ 10/3 R_3`(new)
 `40/43` `40/43=(-10/3)+10/3xx55/43`
`R_2`(new)`= R_2`(old)`+ 10/3 R_3`(new)
 `-32/43` `-32/43=(-2/3)+10/3xx(-1/43)`
`R_2`(new)`= R_2`(old)`+ 10/3 R_3`(new)
 `1` `1=1+10/3xx0`
`R_2`(new)`= R_2`(old)`+ 10/3 R_3`(new)
 `20/43` `20/43=0+10/3xx6/43`
`R_2`(new)`= R_2`(old)`+ 10/3 R_3`(new)
`y_2``1` `5/43` `5/43=5/6xx6/43`
`R_3`(new)`= R_3`(old)`xx6/43`
 `0` `0=0xx6/43`
`R_3`(new)`= R_3`(old)`xx6/43`
 `1` `1=43/6xx6/43`
`R_3`(new)`= R_3`(old)`xx6/43`
 `55/43` `55/43=55/6xx6/43`
`R_3`(new)`= R_3`(old)`xx6/43`
 `-1/43` `-1/43=(-1/6)xx6/43`
`R_3`(new)`= R_3`(old)`xx6/43`
 `0` `0=0xx6/43`
`R_3`(new)`= R_3`(old)`xx6/43`
 `6/43` `6/43=1xx6/43`
`R_3`(new)`= R_3`(old)`xx6/43`
 `Z_q=13/43` `13/43=1xx8/43+1xx5/43`
`Z_j=sum C_B X_B`
 `Z_j` `Z_j=sum C_B x_j` `1` `1=1xx1+0xx0+1xx0`
`Z_j=sum C_B y_1`
 `1` `1=1xx0+0xx0+1xx1`
`Z_j=sum C_B y_2`
 `100/43` `100/43=1xx45/43+0xx40/43+1xx55/43`
`Z_j=sum C_B y_3`
 `6/43` `6/43=1xx7/43+0xx(-32/43)+1xx(-1/43)`
`Z_j=sum C_B S_1`
 `0` `0=1xx0+0xx1+1xx0`
`Z_j=sum C_B S_2`
 `7/43` `7/43=1xx1/43+0xx20/43+1xx6/43`
`Z_j=sum C_B S_3`
`C_j-Z_j` `0` `0=1-1` `0` `0=1-1` `-57/43` `-57/43=1-100/43` `-6/43` `-6/43=0-6/43` `0` `0=0-0` `-7/43` `-7/43=0-7/43`


Since all `C_j - Z_j <= 0`

Hence, optimal solution is arrived with value of variables as :
`y_1=8/43,y_2=5/43,y_3=0`

Max `Z_q = 13/43`



`:. Z_q=1/V=13/43`

`:. V=43/13`

player B's optimal strategy
`q_1=V xx y_1=43/13 xx 8/43=8/13`

`q_2=V xx y_2=43/13 xx 5/43=5/13`

`q_3=V xx y_3=43/13 xx 0=0`

Hence, player B's optimal strategy is `(8/13,5/13,0)`.

player A's optimal strategy
The values for `x_1,x_2,x_3` can be obtained from the `z_j-c_j` row of final simplex table

`x_1=6/43,x_2=0,x_3=7/43`

`p_1=V xx x_1=43/13 xx 6/43=6/13`

`p_2=V xx x_2=43/13 xx 0=0`

`p_3=V xx x_3=43/13 xx 7/43=7/13`

Hence, player A's optimal strategy is `(6/13,0,7/13)`.


This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then Submit Here









 
Copyright © 2020. All rights reserved. Terms, Privacy





Adblocker detected!

Dear user,

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add atozmath.com to your ad blocking whitelist or disable your adblocking software.

Thanks for your support

×