BT2103 Optimization Methods for Business Analytics SEMESTER II 2022-2023 Assignment 3
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
BT2103 Optimization Methods for Business Analytics
SEMESTER II 2022-2023
Assignment 3
Due: Wednesday, 5 April 2023, 9.00 am
Submit to Canvas
Instructions:
• This is an individual assignment. Every student must upload her/his solution to Canvas.
• We will discuss these questions during tutorial #10 on 5 & 7 (make-up to be arranged) April 2023.
1. (20 points) Consider the linear program (LP):
max Z = 2x1 +4x2 +x3 +x4
subject to
x1 +3x2 +x4 < 4
2x1 +x2 < 3
x2 +4x3 +x4 < 3
x1 ,x2 ,x3 ,x4 ≥ 0
The optimal simplex tableau is:
Basic Var. |
Coefficient of |
Right side |
|||||||
Z |
x1 x2 x3 x4 s1 s2 s3 |
||||||||
Z x2 x1 x3 |
1 0 0 0 |
0 0 1 0 |
0 1 0 0 |
0 0 0 1 |
7 20 2 5 1 -5 3 20 |
22 20 2 5 1 -5 1 - 10 |
9 20 − 5 1 20 |
1 4 0 0 1 4 |
6 1 1 1 2 |
(a) (2 points) Load and install R package LPSolve. Cut and paste the following R codes, print the output.
library(lpSolve)
library(linprog)
cvec <- c(2,4,1,1)
bvec <- c(4,3,3)
names(cvec) <- c("X1", "X2","X3","X4")
names(bvec) <- c("Con1","Con2","Con3")
Amat <- rbind( c(1,3,0,1),c(2,1,0,0),c(0,1,4,1))
const_dir <- c("<=", "<=", "<=")
lp(direction="max",objective.in=cvec ,const.mat=Amat,const.dir = const_dir, const .rhs=bvec)$solution
lp(direction="max",objective.in=cvec ,const.mat=Amat,const.dir = const_dir, const .rhs=bvec,compute .sens=TRUE)$duals
lp(direction="max",objective.in=cvec ,const.mat=Amat,const.dir = const_dir, const .rhs=bvec,compute .sens=TRUE)$duals .from
lp(direction="max",objective.in=cvec ,const.mat=Amat,const.dir = const_dir, const.rhs=bvec,compute.sens=TRUE)$duals.to
lp(direction="max",objective.in=cvec ,const.mat=Amat,const.dir = const_dir, const .rhs=bvec,compute .sens=TRUE)$sens .coef .from
lp(direction="max",objective.in=cvec ,const.mat=Amat,const.dir = const_dir, const.rhs=bvec,compute.sens=TRUE)$sens.coef.to
(b) (2 points) State the optimal set of basic variables, the optimal basis matrix and its
inverse.
(c) (2 points) State the optimal set of nonbasic variables, the matrix NB consisting of columns of nonbasic variables and compute B−1NB.
(d) (2 points) Compute the optimal solutions {x2 x1 x3 } = B−1b and the optimal objective function value = Z = cBB−1b.
(e) (2 points) Compute the optimal dual variables (y1 y2 y3 )= cBB−1 .
(f) (2 points) Write the dual of LP and show that {y1 y2 y3 } from part (e) above are
feasible for the dual problem.
(g) (2 points) Compute bty. This is the value of the optimal objective function of the dual
LP.
For parts (h) - (j) below, asnwer the questions using the information from parts (b) - (g) above.
(h) (2 points) Determine the range of the constraint 1’s right hand side (current value b1 =
4) over which the shadow price for constraint 1 is valid.
(i) (2 points) Determine the range over which the objective coefficient of x1 (current value c1 = 2) can vary without affecting the optimal solution.
(j) (2 points) Determine the range over which the objective coefficient of x4 (current value
c4 = 1) can vary without affecting the optimal solution.
2023-03-31