Linear Programming Models And Game Theory: Building And Solving
Linear Programming Models
Solution: This scenario could be described as linear programming because it involves optimization. The main aim is to maximize the profit by determining the amount of time for each process (cutting, sewing, and packaging. Furthermore, there are constraints of the number of workers for each process as well as the amount of time for each process (Will, 2014).
Solution: The linear model is formulated by first identifying the constraints as well as the objective function. The objective function is given by;
Z=8X1+15X2 Where X1 represents the number of dresses while X2 represents the number of coats that are being produced in a day (Toriello, et al., 2017). The objective function implies that given the optimal number of dresses and number of the coast, the above equation will give the maximum profit (Toriello, et al., 2017).
The constraints are based on the number of hours for each process. We know that the total number of working hours is 8 in a day. This implies that any of the processes must not exceed 8 hours (480minutes). Therefore, the constraints are given by;
25×1+12×2<480
25×1+55×2<480
15×1+15×2<480
X1+x2<25
X1+x2<52
X2+x2<14
X1>=0,X2>=12 (Sanchez- Soriano & Joaquin, 2013).
Solution: The R code for getting the optimal profit:
library(lpSolve)#Attaching the lpsolve package
library(lpSolveAPI)
objective.funct<-c(8,15) #The objective function. This will give the profit from the production of dresses and coats
constraints<-matrix(c(25,12,25,55,15,15,1,1,1,1,1,1),ncol=2,byrow = TRUE) # The constraints
constraints.direction<-c(“<“,”<“,”<“,”<“,”<“,”<“) #The direction of the constrints
right.hand.side<-c(480,480,480,25,52,14) #The right hand side of the constrints
optimal.profit<-lp(“max”,objective.funct,constraints,constraints.direction,right.hand.side,compute.sens = TRUE)#This will give the optimal profit
optimal.profit
#The output of the optimal profit is
|
> library(lpSolve)#Attaching the lpsolve package > library(lpSolveAPI) > objective.funct<-c(8,15) #The objective function. This will give the profit from the production of dresses and coats > constraints<-matrix(c(25,12,25,55,15,15,1,1,1,1,1,1),ncol=2,byrow = TRUE) # The constraints > constraints.direction<-c(“<“,”<“,”<“,”<“,”<“,”<“) #The direction of the constrints > right.hand.side<-c(480,480,480,25,52,14) #The right hand side of the constrints > optimal.profit<-lp(“max”,objective.funct,constraints,constraints.direction,right.hand.side,compute.sens = TRUE)#This will give the optimal profit > optimal.profit Success: the objective function is 142.3333 Therefore, the optimal profit is $142.33 |
#The R code for getting the range of profit is shown below
library(lpSolve)#Attaching the lpsolve package
library(lpSolveAPI)
objective.funct<-c(8,15) #The objective function. This will give the profit from the production of dresses and coats
constraints<-matrix(c(25,12,25,55,15,15,1,1,1,1,1,1),ncol=2,byrow = TRUE) # The constraints
constraints.direction<-c(“<“,”<“,”<“,”<“,”<“,”<“) #The direction of the constrints
right.hand.side<-c(480,480,480,25,52,14) #The right hand side of the constrints
max.profit<-lp(“max”,objective.funct,constraints,constraints.direction,right.hand.side,compute.sens = TRUE)#This will give the optimal profit
max.profit
min.profit<-lp(“max”,objective.funct,constraints,constraints.direction,right.hand.side,compute.sens = TRUE)#This will give the optimal profit
profit.range<-c(min.profit,max.profit)
profit.range
min.profit
> library(lpSolve)#Attaching the lpsolve package
> library(lpSolveAPI)
> objective.funct<-c(8,15) #The objective function. This will give the profit from the production of dresses and coats
> constraints<-matrix(c(25,12,25,55,15,15,1,1,1,1,1,1),ncol=2,byrow = TRUE) # The constraints
> constraints.direction<-c(“<“,”<“,”<“,”<“,”<“,”<“) #The direction of the constrints
> right.hand.side<-c(480,480,480,25,52,14) #The right hand side of the constrints
> max.profit<-lp(“max”,objective.funct,constraints,constraints.direction,right.hand.side,compute.sens = TRUE)#This will give the optimal profit
> max.profit
Success: the objective function is 142.3333
> min.profit<-lp(“min”,objective.funct,constraints,constraints.direction,right.hand.side,compute.sens = TRUE)#This will give the optimal profit
Game Theory
> min.profit
Success: the objective function is 0
> profit.range<-c(min.profit,max.profit)
> profit.range
$`direction`
[1] 0
$x.count
[1] 2
$objective
[1] 8 15
$const.count
[1] 6
$constraints
[,1] [,2] [,3] [,4] [,5] [,6]
25 25 15 1 1 1
12 55 15 1 1 1
const.dir.num 1 1 1 1 1 1
const.rhs 480 480 480 25 52 14
$int.count
[1] 0
$int.vec
[1] 0
$bin.count
[1] 0
$binary.vec
[1] 0
$num.bin.solns
[1] 1
$objval
[1] 0
$solution
[1] 0 0
$presolve
[1] 0
$compute.sens
[1] 1
$sens.coef.from
[1] 0 0
$sens.coef.to
[1] 1e+30 1e+30
$duals
[1] 0 0 0 0 0 0 8 15
$duals.from
[1] -1e+30 -1e+30 -1e+30 -1e+30 -1e+30 -1e+30 -1e+30 -1e+30
$duals.to
[1] 1.000000e+30 1.000000e+30 1.000000e+30 1.000000e+30 1.000000e+30 1.000000e+30
[7] 1.400000e+01 8.727273e+00
$scale
[1] 196
$use.dense
[1] 0
$dense.col
[1] 0
$dense.val
[1] 0
$dense.const.nrow
[1] 0
$dense.ctr
[1] 0
$use.rw
[1] 0
$tmp
[1] “Nobody will ever look at this”
$status
[1] 0
$direction
[1] 1
$x.count
[1] 2
$objective
[1] 8 15
$const.count
[1] 6
$constraints
[,1] [,2] [,3] [,4] [,5] [,6]
25 25 15 1 1 1
12 55 15 1 1 1
const.dir.num 1 1 1 1 1 1
const.rhs 480 480 480 25 52 14
$int.count
[1] 0
$int.vec
[1] 0
$bin.count
[1] 0
$binary.vec
[1] 0
$num.bin.solns
[1] 1
$objval
[1] 142.3333
$solution
[1] 9.666667 4.333333
$presolve
[1] 0
$compute.sens
[1] 1
$sens.coef.from
[1] 6.818182 8.000000
$sens.coef.to
[1] 15.0 17.6
$duals
[1] 0.0000000 0.2333333 0.0000000 0.0000000 0.0000000 2.1666667 0.0000000
[8] 0.0000000
$duals.from
[1] -1.000000e+30 3.500000e+02 -1.000000e+30 -1.000000e+30 -1.000000e+30
[6] 8.727273e+00 -1.000000e+30 -1.000000e+30
$duals.to
[1] 1.00e+30 7.70e+02 1.00e+30 1.00e+30 1.00e+30 1.92e+01 1.00e+30 1.00e+30
$scale
[1] 196
$use.dense
[1] 0
$dense.col
[1] 0
$dense.val
[1] 0
$dense.const.nrow
[1] 0
$dense.ctr
[1] 0
$use.rw
[1] 0
$tmp
[1] “Nobody will ever look at this”
$status
[1] 0
$duals
[1] 0.0000000 0.2333333 0.0000000 0.0000000 0.0000000 2.1666667 0.0000000
[8] 0.0000000
$duals.from
[1] -1.000000e+30 3.500000e+02 -1.000000e+30 -1.000000e+30 -1.000000e+30
[6] 8.727273e+00 -1.000000e+30 -1.000000e+30
$duals.to
[1] 1.00e+30 7.70e+02 1.00e+30 1.00e+30 1.00e+30 1.92e+01 1.00e+30 1.00e+30
The above solution shows a range of solutions. However, it can be easily pointed out the lowest profit possible is $0 while the maximum profit possible is $142.33. Therefore, the range of profits is ($0,$142.33) (Peter & Dennis, 2012).
Constructing and Solving Models with R
2a.
Solution: The appropriate decision variables are the optimal number of materials of each category that should be used for the production. Let serial A be x1, serial be x2 and cereal C be x3. The linear model can be formulated as follows;
The objective function for minimizing the cost of production is gevine by:
Z=4.2×1+2.60×2+3.60×3 (Martin, et al., 2013)
On the other hand, the constraints are given by;
0.8×1+0.1×2+0.05×3+0.05×4=1000
0.6×1+0.25×2+0.05×3+0.10×4=800
0.45×1+0.15×2+0.10×3+0.30×4=750 (Perea & Andres, 2014)
The solution for the maximum profit is given by library(lpSolve)
> library(lpSolveAPI)
> object.funct<-c(4.2,2.6)
> consts<-matrix(c(0.8,0.1,0.05,0.05,0.8,0.25,0.05,0.10,0.45,0.15,0.10,0.30),ncol = 2,byrow = TRUE)
> const.dir<-c(“<=”,”<=”)
> rhs<-c(1000,800)
> opt.sol<-lp(“max”,object.funct,consts,const.dir,rhs,compute.sens = TRUE)
> opt.sol
Success: the objective function is 8483.721
library(lpSolve)
library(lpSolveAPI)
object.funct<-c(4.2,2.6)
consts<-matrix(c(0.8,0.1,0.05,0.05,0.8,0.25,0.05,0.10,0.45,0.15,0.10,0.30),ncol = 2,byrow = TRUE)
const.dir<-c(“<=”,”<=”)
rhs<-c(1000,800)
opt.sol<-lp(“min”,object.funct,consts,const.dir,rhs,compute.sens = TRUE)
opt.sol
The output
|
> library(lpSolve) > library(lpSolveAPI) > object.funct<-c(4.2,2.6) > consts<-matrix(c(0.8,0.1,0.05,0.05,0.8,0.25,0.05,0.10,0.45,0.15,0.10,0.30),ncol = 2,byrow = TRUE) > const.dir<-c(“<=”,”<=”) > rhs<-c(1000,800) > opt.sol1<-lp(“max”,object.funct,consts,const.dir,rhs,compute.sens = TRUE) > opt.sol Success: the objective function is 8483.721 > opt.sol2<-lp(“min”,object.funct,consts,const.dir,rhs,compute.sens = TRUE) > opt.sol Success: the objective function is 8483.721 > y<-c(opt.sol2,opt.sol1) > y $`direction` [1] 0 $x.count [1] 2 $objective [1] 4.2 2.6 $const.count [1] 6 $constraints [,1] [,2] [,3] [,4] [,5] [,6] 8e-01 5e-02 0.80 5e-02 0.45 0.1 1e-01 5e-02 0.25 1e-01 0.15 0.3 const.dir.num 1e+00 1e+00 1.00 1e+00 1.00 1.0 const.rhs 1e+03 8e+02 1000.00 8e+02 1000.00 800.0 $int.count [1] 0 $int.vec [1] 0 $bin.count [1] 0 $binary.vec [1] 0 $num.bin.solns [1] 1 $objval [1] 0 $solution [1] 0 0 $presolve [1] 0 $compute.sens [1] 1 $sens.coef.from [1] 0 0 $sens.coef.to [1] 1e+30 1e+30 $duals [1] 0.0 0.0 0.0 0.0 0.0 0.0 4.2 2.6 $duals.from [1] -1e+30 -1e+30 -1e+30 -1e+30 -1e+30 -1e+30 -1e+30 -1e+30 $duals.to [1] 1.000000e+30 1.000000e+30 1.000000e+30 1.000000e+30 1.000000e+30 1.000000e+30 [7] 1.250000e+03 2.666667e+03 $scale [1] 196 $use.dense [1] 0 $dense.col [1] 0 $dense.val [1] 0 $dense.const.nrow [1] 0 $dense.ctr [1] 0 $use.rw [1] 0 $tmp [1] “Nobody will ever look at this” $status [1] 0 $direction [1] 1 $x.count [1] 2 $objective [1] 4.2 2.6 $const.count [1] 6 $constraints [,1] [,2] [,3] [,4] [,5] [,6] 8e-01 5e-02 0.80 5e-02 0.45 0.1 1e-01 5e-02 0.25 1e-01 0.15 0.3 const.dir.num 1e+00 1e+00 1.00 1e+00 1.00 1.0 const.rhs 1e+03 8e+02 1000.00 8e+02 1000.00 800.0 $int.count [1] 0 $int.vec [1] 0 $bin.count [1] 0 $binary.vec [1] 0 $num.bin.solns [1] 1 $objval [1] 8483.721 $solution [1] 465.1163 2511.6279 $presolve [1] 0 $compute.sens [1] 1 $sens.coef.from [1] 0.8666667 1.3125000 $sens.coef.to [1] 8.32 12.60 $duals [1] 0.000000 0.000000 4.651163 0.000000 0.000000 4.790698 0.000000 0.000000 $duals.from [1] -1.000000e+30 -1.000000e+30 6.666667e+02 -1.000000e+30 -1.000000e+30 [6] 1.250000e+02 -1.000000e+30 -1.000000e+30 $duals.to [1] 1.000000e+30 1.000000e+30 1.352174e+03 1.000000e+30 1.000000e+30 1.200000e+03 [7] 1.000000e+30 1.000000e+30 $scale [1] 196 $use.dense [1] 0 $dense.col [1] 0 $dense.val [1] 0 $dense.const.nrow [1] 0 $dense.ctr [1] 0 $use.rw [1] 0 $tmp [1] “Nobody will ever look at this” $status [1] 0 |
Therefore, the optimal solution is ] 8483.721
$solution
[1] 465.1163 2511.6279
That is the amount of A that should be produced is 8483.72 grams, B should be 465.12 grams, and C should be 2511.63 grams (Marco, et al., 2011).
a. Give reasons why/how this game can be described as a two-players-zero-sum game
Solution: A zero-sum game is a game where the gain of one player is equivalent to the loss of the opponent (Manuel, et al., 2013). In this scenario, we have two players (Halpern, et al., 2018). The gain of one player in each play is equivalent to the loss of the opponent (Gongyun, 2010). Therefore, the sum of the gains and the losses for each play is equivalent to zero (Avrachenko, et al., 2012).
Question 3b.
Solution: The payoff table is shown below
|
Alice |
|||||
|
John |
1 |
2 |
3 |
4 |
5 |
|
0 |
1 |
2 |
3 |
4 |
|
|
1 |
0 |
1 |
2 |
3 |
|
|
1 |
2 |
0 |
1 |
2 |
|
|
1 |
2 |
2 |
0 |
1 |
|
|
1 |
2 |
3 |
4 |
5 |
In game theory, a saddle point is a condition that is necessary and sufficient for an element of a game in a payoff table of a game to be a minimum on its column as well as a maximum on its row (Gerard & Giacomo, 2011). In other words, a saddle point is a payoff value that is a maximum as well as a minimum depending on the point at which the reference is made (Martin, et al., 2013)
Let the gains of Alice be x1, and the gains of John be x2. The objective function can be formulated as:
Z=x1+x2 (Owen & Guillermo, 2013).
The constrainsts are:
x2>0
y2>0
x1P2+x2P2=0
x1P4+x2P4=0
x1P5+x2P5=0 (Gerard & Giacomo, 2011).
Solution:
library(lpSolve)
library(lpSolveAPI)
object.funct<-c(4,1)
consts<-matrix(c(1,1,1,1,1,1,1,1),ncol = 2,byrow = TRUE)
const.dir<-c(“<=”,”<=”,”<=”,”<=”)
rhs<-c(0,0,0,0)
opt.sol1<-lp(“max”,object.funct,consts,const.dir,rhs,compute.sens = TRUE)
opt.sol
opt.sol2<-lp(“min”,object.funct,consts,const.dir,rhs,compute.sens = TRUE)
opt.sol
y<-c(opt.sol2,opt.sol1)
y
The output
> #Question 3
> library(lpSolve)
> library(lpSolveAPI)
> object.funct<-c(4,1)
> consts<-matrix(c(1,1,1,1,1,1,1,1),ncol = 2,byrow = TRUE)
> const.dir<-c(“<=”,”<=”,”<=”,”<=”)
> rhs<-c(0,0,0,0)
> opt.sol1<-lp(“max”,object.funct,consts,const.dir,rhs,compute.sens = TRUE)
> opt.sol
Success: the objective function is 8483.721
> opt.sol2<-lp(“min”,object.funct,consts,const.dir,rhs,compute.sens = TRUE)
> opt.sol
Success: the objective function is 8483.721
> y<-c(opt.sol2,opt.sol1)
> y
$`direction`
[1] 0
$x.count
[1] 2
$objective
[1] 4 1
$const.count
[1] 4
$constraints
[,1] [,2] [,3] [,4]
1 1 1 1
1 1 1 1
const.dir.num 1 1 1 1
const.rhs 0 0 0 0
$int.count
[1] 0
$int.vec
[1] 0
$bin.count
[1] 0
$binary.vec
[1] 0
$num.bin.solns
[1] 1
$objval
[1] 0
$solution
[1] 0 0
$presolve
[1] 0
$compute.sens
[1] 1
$sens.coef.from
[1] 0 0
$sens.coef.to
[1] 1e+30 1e+30
$duals
[1] 0 0 0 0 4 1
$duals.from
[1] -1e+30 -1e+30 -1e+30 -1e+30
[5] -1e+30 -1e+30
$duals.to
[1] 1e+30 1e+30 1e+30 1e+30 0e+00
[6] 0e+00
$scale
[1] 196
$use.dense
[1] 0
$dense.col
[1] 0
$dense.val
[1] 0
$dense.const.nrow
[1] 0
$dense.ctr
[1] 0
$use.rw
[1] 0
$tmp
[1] “Nobody will ever look at this”
$status
[1] 0
$direction
[1] 1
$x.count
[1] 2
$objective
[1] 4 1
$const.count
[1] 4
$constraints
[,1] [,2] [,3] [,4]
1 1 1 1
1 1 1 1
const.dir.num 1 1 1 1
const.rhs 0 0 0 0
$int.count
[1] 0
$int.vec
[1] 0
$bin.count
[1] 0
$binary.vec
[1] 0
$num.bin.solns
[1] 1
$objval
[1] 0
$solution
[1] 0 0
$presolve
[1] 0
$compute.sens
[1] 1
$sens.coef.from
[1] -1e+30 -1e+30
$sens.coef.to
[1] 1e+30 4e+00
$duals
[1] 4 0 0 0 0 -3
$duals.from
[1] 0e+00 -1e+30 -1e+30 -1e+30
[5] -1e+30 -1e+30
$duals.to
[1] 0e+00 1e+30 1e+30 1e+30 1e+30
[6] 0e+00
$scale
[1] 196
$use.dense
[1] 0
$dense.col
[1] 0
$dense.val
[1] 0
$dense.const.nrow
[1] 0
$dense.ctr
[1] 0
$use.rw
[1] 0
$tmp
[1] “Nobody will ever look at this”
$status
[1] 0
Solution: The payoff for Alice can be founf in the output above. From the output, it is clear that Alice will earn $4, $0, $0, $0,$0 and $-3 in the successive plays (Fraenkel, et al., 2018).
$sens.coef.to
[1] 1e+30 4e+00
$duals
[1] 4 0 0 0 0 -3
References
Avrachenko, A., Burachik, R. S., Filar, J. A. & Gaitsgory, V., 2012. Constraint augmentation in pseudo-singularly perturbed linear programs. Journal of Mathematical Programming, 132(1), p. 30.
Fraenkel, et al., 2018. Special issue on combinatorial game theory. International Journal of Game Theory, 47(02).
Gerard, C. & Giacomo, N., 2011. Practical strategies for generating rank-1 split cuts in mixed-integer linear programming. Journal of Mathematical Programming Computation, 3(4), p. 38.
Gongyun, Z., 2010. Representing the space of linear programs as the Grassmann manifold. Mathematical Programming, 121(2), p. 34.
Halpern, Joseph, Y., Pass & Rafael, 2018. Game theory with translucent players. International Journal of Game Theory, Volume 6.
Manuel, et al., 2013. Cooperative Game Theory in Sport. International Game Theory Review, 15(03).
Marco, C., Jacek, G. & Andreas, G., 2011. A warm-start approach for large-scale stochastic linear programs. Journal of Mathematical Programming, 127(02), p. 27.
Martin, Mathieu, Salles & Maurice, 2013. Social Choice and Cooperative Game Theory: Voting Games as Social Agregation Function. International Game Theory Review, 15(03).
Owen & Guillermo, 2013. Application of Game Theory to Economics. International Game Theory Review, 15(3).
Perea & Andres, 2014. From Classical to Empistemic Game Theory. International Game Theory Review, 16(01).
Peter, B. & Dennis, A., 2012. Robust smoothed analysis of a condition number for linear programming. Journal of Mathematical Programming, 131(1), p. 31.
Sanchez- Soriano & Joaquin, 2013. An Overview of Game Theory Applications to Engineering. International Game Theory Review, 15(3).
Toriello, Alejandro, Uhan & Nelson, A., 2017. Dynamic linear programming games with risk-averse players. Journal of Mathematical Programming, 163(1).
Will, J., 2014. The combinatorial game theory of well-tempered scoring games. International Journal of Game Theory, 43(02).