Instructions:
Attempt ALL questions. Unless otherwise speci ed, numerical answers should be either
exact or correct to 3 signi cant gures.
Hint: The matrix equations for the initial tableau and any subsequent tableau are
respectively given by:
2 3
1 c 0 4 Zx 5 = Z0
0 A I xs b
2 3
Z
1 y A c y 4 x 5 = y b Z0
0 SA S xs Sb
where y = cB S and S = B 1 .
Question 1 (40 marks).
Consider the following problem (P ):
Maximize Z = x1 6x 2 + 7x3
subject to x1 x2 + 2x3 6 (1)
x1 2x 2 + 3x3 5 (2)
x1 0; x2 0; x3 0:
Let M ! 1. Let e1 and a1 be the excess and arti cial variables, respectively, for the
constraint 1. Let s2 be the slack variable for the constraint 2. A portion of an optimal
big-M simplex tableau is given as follows:
Basic Coecient of: Right-Hand
Variable Z x1 x2 x3 e1 a1 s2 Side
Z 1 0 0
0 1 0
0 0 1
(a) (7 marks) Construct the initial big-M simplex tableau in canonical form.
(b) (7 marks) Using the portion of the big-M simplex tableau provided above and the
results in (a), show by the fundamental insight that
y = M 4; 5 ; S = 32 2 :
1
Show all calculations.
(c) (4 marks) Using the results in (b), determine the allowable range to stay feasible
for the right-hand side of the constraint 2. Show all calculations.
(d) (4 marks) Using the results in (b), determine the allowable range to stay optimal
for the coecient of x1 in the objective function. Show all calculations.
(e) (12 marks) Using the results in (b), nd all basic variables and missing numbers
in the above big-M simplex tableau by the fundamental insight. Show all
calculations.
(f) (6 marks) Using the results in (e), determine ALL optimal solutions for
(x1; x2 ; x3 ). (Note: You may use either tabular form or matrix form of the big-M
simplex method.)
Question 2 (35 marks).
(a) Consider the following problem (P1), where the value of k has not yet been given:
Maximize Z = 2x1 + 5x2 kx3
subject to x1 + 3x2 x3 4 (1)
x1 0; x2 0; x3 0:
(i) (5 marks) By letting y1 be the dual variable for the functional constraint 1
of problem (P1), construct its dual problem (D1 ) in terms of k.
(ii) (2 marks) By inspection, nd the range of k so that problem (D1) has
feasible solution(s).
(iii) (5 marks) Let k = 3. By inspection, determine the optimal solution
for y1 to problem (D1) and the associated optimal objective value. Which
functional constraint(s) in problem (D1) is/are binding at the optimal
solution?
(iv) (8 marks) Let k = 3. Using the results in (a)(iii), the complementary
slackness property and the complementary optimal solutions property to
determine the optimal solution for (x1 ; x2 ; x3) to problem (P1) and the
associated optimal value for Z .
(b) We now consider problem (P1) with k = 2. By letting s1 be the slack variable
for the functional constraint 1, the simplex method yields the following simplex
tableau:
Basic Coecient of: Right-Hand
Variable Z x1 x2 x3 s1 Side
Z 1 0 1 0 2 8
x1 0 1 3 1 1 4
(i) (3 marks) Identify the current basic solution. Is it optimal? If yes, does
there exist other optimal solutions? If no, determine an optimal solution
for (x1 ; x2 ; x3).
(ii) (2 marks) What is the shadow price for the functional constraint 1?
(c) (10 marks) By adding a new functional constraint to problem (P1) with k = 2,
we obtain the following problem (P2):
Maximize Z = 2x1 + 5x2 2x3
subject to x1 + 3x2 x3 4 (1)
x1 + 2x2 + 3x3 3 (2)
x1 0; x2 0; x3 0:
Let s2 be the slack variable for the functional constraint 2. Using the information
provided in the simplex tableau in (b), determine the optimal solution for (x1 ; x2; x3 )
and the associated optimal value for Z by the dual simplex method.
(Note: Solving the problem by the simplex method will get 0 marks.)
Question 3 (17 marks).
Consider the transportation problem having the following parameter (cost and
requirement) table.
Destination (j )
Source (i) 1 2 3 Supply (si)
1 6 5 3 10
2 7 4 5 10
Demand (dj ) 8 7 5
Let Z denote the total shipping cost, and let xij (i = 1; 2; j = 1; 2; 3) be the number of
units to be shipped from source i to destination j .
(a) (4 marks) Use the northwest corner rule to obtain an initial basic feasible
solution.
(b) (13 marks) Starting with the initial basic feasible solution obtained in (a), use
the transportation simplex method to determine the optimal solution for
(x11 ; x12 ; x13; x21 ; x22 ; x23 ) and the associated optimal value for Z .
Question 4 (8 marks).
Consider the assignment problem having the following cost table:
Job (j )
Person (i) 1 2 3 4
1 5 6 2 3
2 4 1 6 8
3 7 3 4 9
4 3 8 5 4
Let Z denote the total cost of the assignment; and let xij = 1 if person i is assigned to
do job j and xij = 0 otherwise (where i = 1; 2; 3; 4; j = 1; 2; 3; 4). Use the Hungarian
method to determine an optimal solution and the associated optimal value for Z .
| End of Paper |
