Deakin University SIT718 Task 4: Linear Programming and Game Theory

This document presents a comprehensive solution to a homework assignment (Task 4) for the SIT718 Real World Analytics course. The assignment focuses on applying linear programming (LP) and game theory to solve real-world problems. The solution begins with an LP problem, formulating the objective function and constraints for a beverage production scenario, which is then graphically solved. The second part of the solution involves a more complex LP problem with multiple constraints, solved using R-studio code to maximize profit in a production scenario. The third question delves into game theory, analyzing a two-player zero-sum game, determining saddle points, and formulating LP models for both players. The final section applies game theory to a pricing strategy problem, determining the Nash equilibrium using elimination of dominated strategies. The solution includes detailed explanations, equations, and R code for the linear programming problems, along with the payoff matrices and analysis of the game theory scenarios.

Task 4: Problem Solving
Question 1
(a) The problem obeys proportionality assumption of LP because a change in the cost of
any product (A or B) will have a proportional change in the total cost. The total cost
of production of the beverage is the sum of the cost contributed by product A and B
(additive assumption). The implication is that there is no interaction between the
decision variables. Next, the decision variables (liters of orange, lime and mango) are
continuous they can take both decimal and integers. [1] Cost per unit of product A and
B are known thus satisfying the certainty assumption of LP. Finally, the factory
cannot produce less than zero units of beverages implying that the assumption of
finite choices is satisfied.
(b) The LP is formulated as follows:
Let n = volume in liters of product A and,
m = volume in liters of product B.
The objective function is to minimize the total cost function
f (n, m) = 5n + 7m (1)
The constraints are:
Liters of orange not less than 4.5 liters per 100liters of beverage
6 n+4 m
100 ≥ 4.5 (2)
Liters of mango not less than 5 liters per 100liters of beverage
4 n+6 m
100 ≥5 (3)
Liters of Lime no more than 6 liters per 100liters of beverage
3 n+8 m
100 ≤ 6 (4)

Customer Needs
n+ m≥ 80 (5)
Certainty constraints
n ≥ 0 (6)
m ≥0 (7)
Equation (1) represents the objective function while equation (2) to (7) represent
constraints.
(c) In order to plot the equations, we make m the subject in the constraints as follows:
Equation (2) becomes
m ≥− 3
2 n+ 225
2
Equation (3) becomes
m ≥− 2
3 n+ 250
3
Equation (4) becomes
m ≤− 3
8 n+75
Equation (5) becomes
m ≥−n+80 . Now we can use these equations to plot the graph in desmons.com
calculator [9].

From the plot n = x and y = m. The extreem points within the solution region are
(33.33, 62.5), (35, 60), (125, 0) and (200, 0). We noe substitute these values in
equation (1) to obtain total costs at these points.
For (m = 33.33, n = 62.5) the total cost is TC=5 ( 33.33 ) +7 ( 62.5 )=$ 604.15
For (m = 35, n = 60) the total cost is TC =5 ( 35 ) +7 ( 60 )=$ 595
For (m = 125, n =0) the total cost is TC =5 ( 125 ) +7 ( 0 )=$ 625
For (m = 200, n = 0) the total cost is TC =5 ( 200 ) +7 ( 0 ) =$ 1000
The minimum cost solution is (35, 60) which means that the factory should use 35
liters of product A and 60 liters of product B in making the beaverage.
(d) The excell below shows the range of values of liters of product A that can be used
without the total cost changing from $595 to $625.
The range for the cost ($) of A that can be changed without affecting the optimum

solution obtained in (c) is $ 5 ≤ A ≤ $ 5.85.
Question 2
(a) Let xij ≥ 0 be a decision variable that denotes the number of tons of products j for
j ϵ { 1=Spring;2=Autumn ; 3=Winter } to be produced from Materials i 2 for
i ϵ {C=Cotton ,W =Wool , S=Silk } . Also, let π=TR−TC be the profit function to be
maximized. Where TR – total revenue (sales price x demand), and TC – total cost
(production cost (PC) + purchase cost (VC)).
From the information provided:
TR=60 ( xc 1 +xw 1+ xs 1 ) +55 ( xc 2+ xw2 +xs 2 ) +60 ( xc 3+xw 3 + xs 3 ) which simplifies to:
TR=60 xc 1 +60 xw1 +60 xs 1 +55 xc 2 +55 xw2 +55 xs 2+ 60 xc 3 +60 xw 3+60 xs 3
PC =5 ( xc 1 +xw 1+ xs 1 ) + 4 ( xc 2+xw 2 +xs 2 ) +5 ( xc3 + xw 3 +xs 3 )
VC=30 xc 1 +45 xw 1+50 xs 1 +30 xc2 + 45 xw 2 +50 xs 2+ 30 xc 3 +45 xw 3+ 50 xs 3
TC=35 xc1 +50 xw1 +55 xs 1 +34 xc2 + 49 xw 2 +54 xs 2 +35 xc3 +50 xw 3+55 xs 3
Then the objective function is to maximize
π=25 xc 1+10 xw 1+5 x s1 +21 xc2 +6 xw 2 + xs 2+ 25 xc 3 +10 xw 3 +5 xs 3 (1)
Subject to the following constraints:
Demand
xc 1+xw 1 + xs 1 ≤ 4500 (2)
xc 2+ xw 2 +xs 2 ≤ 3000 (3)
xc 3+xw 3 + xs 3 ≤3500 (4)
Proportion of Cotton in Spring
xc1
xc1 + xw 1+ xs 1
≥ 0.5 simplifying to xc 1−xw1 −xs 1 ≥ 0 (5)
Proportion of Wool in Spring

xw1
xc1 +xw 1+ xs 1
≥ 0.3 simplifying to 3 xc1−7 xw 1 +3 xs 1 ≤ 0 (6)
Proportion of Silk in Spring
xs 1
xc1 + xw 1+ xs 1
≥ 0.2 simplifying to xc 1+ xw 1−4 xs 1 ≤ 0 (7)
Proportion of Cotton in Autumn
xc2
xc2 +xw 2+ x s2
≥ 0.5 simplifying to xc 2−xw 2−xs 2 ≥ 0 (8)
Proportion of Wool in Autumn
xw2
xc2 + xw 2+ x s2
≥ 0.4 simplifying to 2 xc2−3 xw 2 +2 xs 2 ≤ 0 (9)
Proportion of Silk in Autumn
xs 2
xc2 + xw 2+x s2
≥ 0.1 simplifying to xc 2+ xw 2−9 xs 2 ≤ 0 (10)
Proportion of Cotton in Winter
xc3
xc3 + xw 3+ xs 3
≥ 0.4 simplifying to 3 xc3 −2 xw 3−2 xs 3 ≥ 0 (11)
Proportion of Wool in Winter
xw3
xc3 + xw 3+ xs 3
≥ 0.5 simplifying to xc 3−xw 3+ x s3 ≤ 0 (12)
Proportion of Silk in Winter
xs 3
xc3 + xw 3+ xs 3
≥ 0.1 simplifying to xc 3+xw 3−9 x s3 ≤ 0 (13)
Non-negativity
xc 1 ≥ 0 , xc 2 ≥ 0 , xc3 ≥ 0 , xs 1 ≥ 0 , xs 2 ≥0 , xs 3 ≥0 , xw 1 ≥ 0 , xw2 ≥ 0 , xw 3 ≥0
Forming equation (14) to (22).
Therefore, we minimize equation (1) constraint to equation (2) to (22).
(b) The first thing is to make a table which we will use to construct constraint matrix.

E
qn xc 1 xw 1 xs 1 xc 2 xw 2 xs 2 xc 3 xw 3 xs 3
si
gn
rh
s
1
2
5 50
5
5
3
4 49
5
4
3
5 50
5
5
2 1 1 1 0 0 0 0 0 0 <=
45
00
3 0 0 0 1 1 1 0 0 0 <=
30
00
4 0 0 0 0 0 0 1 1 1 <=
35
00
5 1 -1 -1 0 0 0 0 0 0 >= 0
6 3 -7 3 0 0 0 0 0 0 <= 0
7 1 1 -4 0 0 0 0 0 0 <= 0
8 0 0 0 1 -1 -1 0 0 0 >= 0
9 0 0 0 2 -3 2 0 0 0 <= 0
10 0 0 0 1 1 -9 0 0 0 <= 0
11 0 0 0 0 0 0 3 -2 -2 >= 0
12 0 0 0 0 0 0 1 -1 1 <= 0
13 0 0 0 0 0 0 1 1 -9 <= 0
14 1 0 0 0 0 0 0 0 0 >= 0
15 0 1 0 0 0 0 0 0 0 >= 0
16 0 0 1 0 0 0 0 0 0 >= 0
17 0 0 0 1 0 0 0 0 0 >= 0
18 0 0 0 0 1 0 0 0 0 >= 0
19 0 0 0 0 0 1 0 0 0 >= 0
20 0 0 0 0 0 0 1 0 0 >= 0
21 0 0 0 0 0 0 0 1 0 >= 0
22 0 0 0 0 0 0 0 0 1 >= 0
The code for used in R-studio is as follows:
library(lpSolve)
## Construct the objective function
objective.fun <- c(25, 50, 55, 34, 49, 54, 35, 50, 55)
## Construct contraint matrix

constraint.matrix <- matrix(c(rep(1,3), rep(0,6),
rep(0,3), rep(1,3), rep(0,3),
rep(0,6), rep(1,3),
1,-1,-1, rep(0,6),3,-7,3, rep(0,6),
1,1,-4, rep(0,6),rep(0,3),
1,-1,-1, rep(0,6),2,-3,2,rep(0,6),
1,1,-9,rep(0,9),3,-2,-2, rep(0,6),
1,-1,1,rep(0,6),1,1,-9,diag(9)),
nrow = 21, ncol = 9, byrow = T)
## Create Constraints direction
constraint.direction <- c(rep("<=",3), ">=",rep("<=",2),
">=",rep("<=",2),">=",rep("<=",2),rep(">=",9))
## Create the right hand side values
rhs <- c(4500,3000,3500, rep(0, 18))
## Solve the linera model
profit.maximization <- lp("max", objective.fun, constraint.matrix,
constraint.direction, rhs, compute.sens
= TRUE)
## Find the solutions
profit.maximization$objval ## maximum profit
profit.maximization$solution ## optimal values of decision
variables
### END OF CODE ###

The maximum profit is $455,000 while the optimal value of the decision variables
are shown in the table below:
xc 1 xw 1 xs 1 xc 2 xw 2 xs 2 xc 3 xw 3 xs 3
225
0
135
0
90
0
150
0
120
0
30
0
140
0
175
0
35
0
Question 3
(a) The game is a two-player zero-sum game since what David gain at each strategy is
equal to what Hellen lose in under the same stragety. The sum of the gains and loss
for each play is equal to zero[4],[5],[7],[8]. Further, in the game there must be a loser
and a winner making it a two-player zero-sum game.
(b) The payoff matrix is as follows
Hellen
(0, 6) (1, 5) (2, 4) (3, 3) (4, 2) (5, 1) (6, 0)
David
(0, 5) -5, 5 -5, 5 0, 0 0, 0 0, 0 -5, 5 -5, 5
(1, 4) 0, 0 -5, 5 -5, 5 0, 0 -5, 5 -5, 5 0, 0
(2, 3) 0, 0 0, 0 0, 0 10 -5, 5 0, 0 0, 0
(3, 2) 0, 0 0, 0 -5, 5 10 -5, 5 0 0, 0
(4, 1) 0, 0 -5, 5 -5, 5 0, 0 -5, 5 -5, 5 0, 0
(5, 0) -5, 5 -5, 5 0, 0 0, 0 0, 0 -5, 5 -5, 5
(c) A saddle point is a payoff that is simultaneously a row minimum and a column
maximum. To locate the saddle point in the matrix obtained in (b) we obtain the row
minimax and column maximin. If the two values are equal then there exist a saddle
point.

Hellen
(0, 6) (1, 5) (2, 4) (3, 3) (4, 2) (5, 1) (6, 0) Row min
David
(0,
5) 5 5 0 0 0 5 5
5
(1,
4) 0 5 5 0 5 5 0
5
(2,
3) 0 0 0 10 5 0 0
5
(3,
2) 0 0 5 10 5 0 0
5
(4,
1) 0 5 5 0 5 5 0
5
(5,
0) 5 5 0 0 0 5 5
5
Column max 5 5 5 10 5 5 5
The maximin is 5 while the minimax is 5. The two values are equal hence the game
have six saddle points.
(d) Given the 6 × 7 matrix in (b) be represented as follows
i\
j 1 2 3 4 5 6 7
1 5 5 0 0 0 5 5
2 0 5 5 0 5 5 0
A = 3 0 0 0 10 5 0 0
4 0 0 5 10 5 0 0
5 0 5 5 0 5 5 0
6 5 5 0 0 0 5 5
Let Row player (David) selects a strategy i∈ {1 , 2, ... , 6 }.
Col player (Hellen) selects a strategy j ∈{1 ,2 , ..., 7 }.
Then, the rows of the A represent deterministic strategies for David, while columns
represent deterministic strategies for Hellen.
Further, suppose David pick strategy i with probability yi and suppose Hellen pick
strategy j with probability x j.
Throughout, x= [ x1 , x2 ,… , x7 ] T and y= [ y1 , y2 , … , y6 ]T denote the stochastic vectors.
The conditions are subject to:

x j ≥ 0 , j=1 ,2 , … , 7
∑
j=1
7
x j=1
Linear program for Hellen
Suppose Hellen adopt strategy x. Then David’s best strategy is to use y that minimizes
yT Ax :min
y
yT Ax. So Hellen choses x which maximizes the possibilities
max
x
min
y
yT Ax
Introduce a scalar variable u to represent the minimization:
max u
Subject to:
u e− Ax ≤ 0 , eT x=1, and x ≥ 0
Where: e represents avector of all 1 and T stands for transpose.
Linear program for David
Suppose David adopt strategy y. Then Hellen’s best strategy is to use x that minimizes
m∈
y max
x
yT Ax which is equivalent to
m ax u
Subject to:
u e− AT y ≥ 0 , eT y=1, and y ≥0
Which is dual to Hellen’s.
(e) The linear prgram for David can be represented in matrix form as follows:
u=payoff
x1 , … , y6= probaility for strategy 1, 2 , … ,5
y6=1− y1− y2− y3 − y4− y5= probaility for strategy 6
Then the objective is to maximize u subject to

u ≤5 y1 +5 ( 1− y1 − y2− y3− y 4− y5 )
−u+0 y1−5 y2−5 y3 −5 y4−5 y5 +5 ≥ 0 (1)
u ≤5 y1 +5 y2 +0 y3+ 0 y4 +5 y5 +5 ( 1− y1− y2− y3− y4 − y5 )
−u+0 y1 +0 y2−5 y3 +−5 y4 + 0 y5 +5 ≥ 0 (2)
u ≤ 0 y1 +5 y2 +0 y3 +5 y4 +5 y5 +0 ( 1− y1− y2− y3− y4 − y5 )
−u+0 y1 +5 y2 +0 y3+ 5 y 4 +5 y5 ≥ 0 (3)
u ≤ 0 y1 +0 y2 +10 y3 +10 y4 +5 y5+0 ( 1− y1− y2 − y3− y4 − y5 )
−u+0 y1 +0 y2 +10 y3+ 10 y 4 +5 y5 ≥ 0 (4)
u ≤ 0 y1 +5 y2 +5 y3+ 5 y4 +5 y5+ 0 ( 1− y1− y2− y3− y4 − y5 )
−u+0 y1 +5 y2 +5 y3+5 y4 + 5 y5 ≥ 0 (5)
u ≤5 y1 +5 y2 +0 y3+ 0 y4 +5 y5 +5 ( 1− y1− y2− y3− y4 − y5 )
−u+0 y1 +0 y2−5 y3−5 y 4+0 y5+5≥ 0 (6)
u ≤5 y1 +0 y2 +0 y3 +0 y4 +0 y5 +5 ( 1− y1 − y2− y3− y 4− y5 )
−u+0 y1−5 y2−5 y3 −5 y4−5 y5 +5 ≥ 0 (7)
y1 , y2 , … , y5 , ( 1− y1 − y2− y3− y 4− y5 ) ≥ 0 Form equation (8) to (13)
Also, y1 , y2 , … , y5 , ( 1− y1 − y2− y3− y 4− y5 ) ≤ 1 form equation (14) to (19).
The code for the solution is
library(lpSolv
e)
obj.fn <- c(1, rep(0,6))
constr.mat <- matrix(c(-1,0,-5,-5,-5,-5,5,
-1,0,0,-5,-5,0,5,
-1,0,5,0,5,5,0,
-1,0,0,10,10,5,0,

-1,0,5,5,5,5,0,
-1,0,0,-5,5,0,5,
-1,0,-5,-5,-5,-5,5,
0,1,rep(0,5),
0,0,1,rep(0,4),
rep(0,3),1,rep(0,3),
rep(0,4),1,0,0,
rep(0,5),1,0,0,rep(-1,5),1,
0,-1,rep(0,5),
0,0,-1, rep(0,4),
rep(0,3),-1,rep(0,3),
rep(0,4),-1,0,0,
rep(0,5),-1,0,
rep(0,6),-1), nrow = 19, byrow = T)
constr.dir <- c(rep(">=",19))
constr.rhs <-c(rep(0,13), rep(-1, 6))
sol <- lp("min", obj.fn, constr.mat, constr.dir, constr.rhs,
compute.sens = T)
sol$objval
sol$solution
sol$objective
(f) The optimal solution for David is zero thus he cannot win the game under any
strategy.
Question 4
(a) Let πi be the profit of company i for i∈ { 1=company 1 , 2=company 2 }
We have been given:
Q1=200−P1− ( P1−P )∧Q2=200−P2− ( P2 −P ) where P= P1 + P2
2 . The two equations
can simplify to
Q1=200−1.5 P1+0.5 P2 (1)
Q2=200+ 0.5 P1 −1.5 P2 (2)
The profit from sale of each cellphone after sale are as follows