Tutorial 5

MTL103 (Optimization Methods and Applications )

1. Using simplex method, solve the following linear programming problem:

Min −3x1 − 2x2
subject to
x1 +2x2 ≤ 6
2x1 + x2 ≤ 6
x1 , x2 ≥ 0.
• Does addition of constraint x1 + x2 ≥ 3 change the optimal solution? If yes, find
the new optimal solution.
• Update the original optimal simplex  tableau
 if an additional variable x3 with
1
corresponding column vector A3 = and cost coefficient c3 = 2 is introduced
1
in the original problem and find its optimal solution.

2. Consider the linear programming problem

Min −x1 − 6x2
subject to
x1 +3x2 ≤ 12
3x1 + x2 ≤ 12
x1 + x2 = 13
x1 , x2 ≥0,
and let following be its last tableau

xB b x1 x2 x3 x4 a1
x2 3 0 1 3/8 −1/8 0
x1 3 1 0 −1/8 3/8 0
a1 7 0 0 −1/4 −1/4 1
17+2M 2M −3
21 0 0 8 8
0

(a) What conclusion can you draw from the tableau?

(b) Update the table if b is changed to (12, 12, 6)T , what do you infer now?
(c) Identify the redundant constraint (if any) and hence find the new optimal basic
feasible solution of the reduced problem?
(d) Does the addition of the constraint x1 + x2 = 3 in the reduced problem affects
the solution. If yes, then find the optimal basic feasible solution.

3. Consider the following LPP problem and its optimal tableau:

Min −2x1 − x2 + x3
subject to
x1 + 2x2 + x3 ≤ 8

1
 −x1 + x2 − 2x3 ≤ 4
x1 , x2 , x3 ≥ 0.

xB b x1 x2 x3 x4 x5
x1 8 1 2 1 1 0
x5 12 0 3 −1 1 1
16 0 3 3 2 0

(a) Find new optimal solution if the coefficient of x2 in the objective function is
changed from -1 to -6.
(b) Find new optimal solution if the coefficient of x2 in the first constraint is changed
from 2 to 14 .
(c) What will be the change in the optimal solution, if a new constraint x2 + x3 = 3
is added?
(d) What will be the change in the optimal solution, if a new variable x4 is introduced
with cost coefficient 4 and column vector A4 = (1, 2)T ?

4. Let following be the optimal simplex tableau for a given LPP of the minimization type,
where x3 , x4 are slack variables.

xB b x1 x2 x3 x4
x2 6 0 1 2 −1
x1 2 1 0 −1 1
26 0 0 2 1
Does the addition of constraint x1 + x2 ≤ 6 in the problem affect the solution? If yes,
then find the optimal basic feasible solution.

5. Let following be the optimal tableau for a given LPP, in which x3 , x4 are slack variable.

xB b x1 x2 x3 x4
x3 4 1 0 1 0
x2 9 3/2 1 0 1/2
9/2 0 0 5/2
Let a new variable x5 be introduced with c5 = 7 and A5 = (a, b)T . Find the minimum
value of b for which condition of optimality will not violate.

6. Consider the following linear programming problem

min 4x1 + 5x3

s.t. 2x1 + x2 − 5x3 = 1
− 3x1 + 4x3 + x4 = 2
x1 , x2 , x3 , x4 ≥ 0.

• Write down optimal simplex tableau. Is optimal solution unique?

• Find the optimal solution of a dual . Is it unique?

2
 • Suppose now that we change the vector b from (1, 2) to (1 − 2θ, 2 − 3θ), where θ
is a scale parameter. Find an optimal solution and the value of optimal cost for
all values of θ.

7. While solving a standard from linear programming problem using the simplex method,
we arrive at the following tableau:

xB b x1 x2 x3 x4 x5
x2 1 0 1 −1 0 β

x4 2 0 0 2 1 γ

x1 3 1 0 4 0 δ
0 0 c̄3 0 c̄5
Suppose that the last three columns of the matrix A form an identity matrix.

(a) Give necessary and sufficient conditions for the basis described by this tableau to
be optimal (in terms of the coefficients in the tableau).
(b) Assume that this basis is optimal and that c̄3 = 0. Find an optimal basic feasible
solution, other than the one described by this tableau.
(c) Suppose that γ > 0. Show that there exists an optimal basic feasible solution,
regardless the values of c̄3 and c̄5 .
(d) Assume that the basis associated with this tableau is optimal . Suppose also that
b1 in the original problem is replaced by b1 + ϵ. Give upper and lower bounds on
ϵ so that this basis remains optimal.
(e) Assume that the basis associated with this tableau is optimal. Suppose also that
c1 in the original problem is replaced by c1 + ϵ. Give upper and lower bounds on
ϵ so that this basis remains optimal.

8. Cookwell Co. manufactures and sells three models of large-size pressure cookers for
canteen use. While market demands pose no constraints, supplies of aluminium limited
to 750 kg. per week and availability of machine-time limited to 600 hours per week.
The resource usages of the three models are given in table below:

Models
M1 M2 M3
Aluminium kg./unit 6 3 5
Machine-time hr./unit 3 4 5
Profit Rs./unit 60 20 80

(a) Formulate the linear programming problem which maximizes the total weekly
profit.
(b) Find the optimal number of pressure cookers of each type by solving equivalent
minimization problem using simplex method.

3
(c) Using optimal simplex tableau, determine whether the current optimal solution
would be sensitive to the following changes. Treat each condition given below
independently and find a new optimal in each case in case current optimal solution
is no longer remain optimal with these changes.
(i) An additional 150 kg. of aluminium would become available.
(ii) Machine hour would reduce from current level of 600 hours to 450 hours.
(iii) Following a reduction in selling price of M3 , its per unit profit decreases by
Rs. 45.
(iv) A new model has been developed requiring 3 kg. of aluminium and 3 hours
of machine-time per unit, with an estimated unit profit of Rs. 40. Would it
be worthwhile manufacturing this new model?
(v) The market would demand at least 150 pressure cookers in total.
Justify your answer with proper arguments