Date: 23/05/2023
Time: 11.30 am – 13.00 am
Business Optimization
Number of pages: 4
Total marks: 100
Final Exam Solutions
Part 1:
Question 1 (25 points)
Consider the following LP:
S.t. (1)
(2)
(3)
1) This linear program (6 points)
□ has a unique optimal solution □ is infeasible
□ is unbounded □ has multiple optimal solutions
2) Point (20,20) is a feasible solution (5 points) □ True □ False
3) One of following solutions is a feasible corner point (5 points)
□ (10,10) □ (15,15) □ (10,20)
4) One of following points is the optimal solution: (5 points)
□ (10,20) □ (20,20) □ (20, 0) □ (10,10)
5) Constraint (3) is non-binding (4 points) □ True □ False
1
Question 2 (20 points)
The following tableau is one of the simplex tableaus obtained when maximizing the objective
function subject to 2 technological “≤” constraints:
Cj 3 2 2 0 0 -
CB Basis X1 X2 X3 S1 S2 R.H.S
3 X1 1 0 0.5 0.5 0 12.5
2 X2 0 1 0.75 -0.25 0.5 13.75
Zj 3 2 3 1 1 65
C bar 0 0 -1 -1 -1
1) The Cj row contains: (4 points)
□ [3; 0; 0; 0; 2] □ [3; 2; 2; 0; 0] □ [1; 2; 3; 1; 2]
2) C_bar (S2) is equal to: (3 points)
□0 □1 □ -1
3) This tableau is optimal: (3 points)
□ True □ False
4) The missing value in S1 column is: (3 points)
□ 0.25 □ -1 □ 0.5
5) The optimal solution is: (3 points)
□ (12.5,0) □ (12.5, 13.75) □ (12.5, 12. 5)
6) The Basis column contains: (4 points)
□ □ □
2
Question 3 (25 points)
The optimal simplex tableau of a given LP maximizing profit under resource constraints is as follows
X1 X2 X3 S1 S2 S3 RHS
2 X1 1 0.5 0 0.5 0 -0.5 13
0 S2 0 -1.5 0 0.5 1 -2.5 5
1 X3 0 0.5 1 -0.5 0 1.5 11
Zj 2 1.5 1 0.5 0 1.5 37
Cj- Zj 0 -0.5 0 -0.5 0 -0.5 -
1) The dual optimal solution is (4 points)
Y1=13 ; Y2=5 ; Y3=11 ; W=37□ b) Y1=0.5 ; Y2=0 ; Y3=0.5 ; W=37□
c) Y1=-0.5 ; Y2=0 ; Y3= -0.5 ; W=37□ d) Y1=0.5 ; Y2= 0 ; Y3= -0.5 ; W=37□
2) If one unit of one resource can be purchased at the same cost as the others, then, it is most beneficial
to purchase: (4 points)
a) resource 1 □ b) resource 2 □ c) resource 3 □ d) resource 1 or 3 □
3) Product 2 will be profitable if its profit rate increases by at least: (4 points)
a) 1 unit □ b) 1.5 units□ c) 0.5 units □ d) 0 unit □
4) The optimal basis is preserved when the profit rate of product 1 is decreased by no more than: (8
points)
a) 1 unit □ b) 13 units□ c) 2 units □ d) 0 units □
5) If constraint 2 is relaxed (omitted), then the optimal production plan will (5 points)
a) increase □ b) decrease □ c) remain stable □
3
Question 4 (30 points)
Let xij= 1 if the professor i (i=1..4) is assigned to the course j (j=1..4).
= 0 otherwise
d
i be the positive deviation from effectiveness level of 7 with i=1,2,3,4
d
i be the negative deviation from effectiveness level of 7 with i=1,2,3,4
Min Z d d d d
1 2 3 4
6 x 8x 6 x 8x d d 7
11 21 31 41 1 1
6 x 5 x 4 x 7 x d 2 d 2 7
12 22 32 42
8x 6 x 9 x 8x d d 7
13 23 33 43 3 3
7x 9x 9x 7x d d 7
14 24 34 44 4 4
x x x x 2
11 12 13 14
x x x x 2
21 22 23 24
x x x x 2
31 32 33 34
x x x x 2
41 42 43 44
x x x x 1
11 21 31 41
x x x x 1
12 22 32 42
x x x x 1
13 23 33 43
x x x x 1
14 24 34 44
xij 0,1
All d i , d i 0
Xij : 2 points ; di- : 1 point ; di+ : 1 point ; each constraint : 2 points (we have 12 constraints); non-
negativity constraints : 2 points
4
2+∆c1
X1 X2 X3 S1 S2 S3 RHS
2+∆c1 X1 1 0.5 0 0.5 0 -0.5 13
0 S2 0 -1.5 0 0.5 1 -2.5 5
1 X3 0 0.5 1 -0.5 0 1.5 11
Zj 2+∆c1 1.5+0.5∆c1 1 0.5+0.5∆c1 0 1.5-0.5∆c1 37
Cj- Zj 0 -0.5- 0 -0.5- 0 - -
0.5∆c1 0.5∆c1 0.5+0.5∆c1
