Problem Set # 1
1. (a) Consider the following LP problem.
Min z = 4 x1 + 6 x 2 + 12 x3 + 18 x 4
Subject to
x1 + 2 x 2 + 3x3 + 2 x 4 3 (1)
x1 + x 2 + x3 + 3x 4 2 (2)
x1 , x 2 , x3 , x 4 0
What are the optimal values of the variables and objective function?
Variable/Objective
Optimal value
function
x1 1
x2 1
x3 0
x4 0
z 10
1. (b) In problem 1 (a), if y1 and y2 represent the dual variables corresponding to
constraint (1) and constraint (2), respectively, then what are their optimal
values?
Variable Optimal value
y1 2
y2 2
1. (c) In problem 1 (a), if the right hand side (R.H.S.) values of constraint (1) and
constraint (2) are changed to 2 and 1 (from 3 and 2), respectively, then how
many solutions would the dual of the problem now have? (Clearly mark your
choice in the box below)
Mark () your
No. of solutions
choice
Zero
One
Two
Infinitely many
2. Consider the following LP problem.
Min z = −3x1 + 2 x 2
Subject to
− x1 + x 2 4 (1)
− 2 x1 + x 2 6 (2)
x1 free (unrestricted )
x2 0
If y1 and y2 represent the dual variables corresponding to constraint (1) and
constraint (2), respectively, then what are their optimal values?
Variable Optimal value
y1 1
y2 1
3. Consider a Goal Programming Problem with the following three goals:
Goal 1 : x1 + 2 x2 6
Goal 2 : 3x1 + x2 12
Goal 3 : x1 + x2 = 5
x1 , x2 0
Goal 1 and Goal 2 have the same importance, and Goal 3 is thrice as
important as either Goal 1 or Goal 2. If you wish to solve the problem by the
weighting method, then what are the optimal values of the variables?
Variable Optimal value
x1 3.5
x2 1.5
Problem Set # 2
1. (a) Consider the following LP problem.
Max z = 2 x1 + 3x 2
Subject to
x1 + x 2 4 (1)
x1 + 3 x 2 6 (2)
x1 + 4 x 2 4 (3)
x1 , x 2 0
What are the optimal values of the variables and objective function?
Variable/Objective
Optimal value
function
x1 3
x2 1
z 9
1. (b) In problem 1 (a), if y1, y2 and y3 represent the dual variables corresponding
to constraint (1), constraint (2) and constraint (3), respectively, then what are
their optimal values?
Variable Optimal value
y1 1.5
y2 0.5
y3 0
1. (c) In problem 1 (a), if the relationships of all the three constraints are reversed,
then how many solutions would the problem now have? (Clearly show the
logic and mark your choice in the box below)
Mark () your
No. of solutions
choice
Zero
One
Two
Infinitely many
2. Consider the following LP problem.
Min z = −4 x1 + x 2
Subject to
x1 − x 2 1 (1)
2 x1 + x 2 1 (2)
x1 0
x2 0
If y1 and y2 represent the dual variables corresponding to constraint (1) and
constraint (2), respectively, then what are their optimal values?
Variable Optimal value
y1 -2
y2 -1
3. Consider a Goal Programming Problem with the following three goals:
Goal 1 : x1 + x 2 6
Goal 2 : x1 + 6 x 2 12
Goal 3 : x1 + 2 x 2 8
x1 , x 2 0
Goal 1 and Goal 2 have the same importance, and Goal 3 is twice as
important as either Goal 1 or Goal 2. If you wish to solve the problem by the
weighting method, then what are the optimal values of the variables?
Variable Optimal value
x1 6
x2 1
Problem Set # 3
1. Solve the following linear programming (LP) problem by the simplex
algorithm.
Min z = x + 2 y
S .T .
x+ y 2
x + 4y 4
2x + 5 y 6
x, y 0
Variable/Objective Optimal
value value
x 4/3
y 2/3
z 8/3
2. Solve the following goal programming problem by the weighting method in
LP. Note that all goals are equally important.
Goal 1 : x + y 4
Goal 2 : 3 x + y 3
Goal 3 : x + 3 y 3
x, y 0
Variable Optimal value
x 3/4
y 3/4
Problem Set # 4
1. (a) For the forthcoming summer placements, you have to decide as to how many
hours you are going to devote to academics and preparations for placements
on a daily basis. You estimate that for every hour you devote to academics,
your annualized salary would be Rs. 4 lakh, and for every hour you devote to
preparations for placements, you will receive an annualized salary of Rs. 6
lakh. You decide that you are not going to devote more than 4 hours daily to
these two activities. Moreover, you estimate that every hour of academics
and every hour of placement preparations require 200 calories and 600
calories, respectively, and you decide that you are not going to burn more
than 1200 calories daily on these two activities. If you want to maximize the
annualized salary in placements, how many hours should you devote to
academics and preparations for placements daily? What is the maximum
annualized salary that you expect to receive?
Activity / Objective Optimal value
function (Hours / Rs.)
Academics 3
Placement preparations 1
Annualized salary 18 Lakh
1. (b) What are the shadow prices (dual values) of the two resources, time and
energy?
Resource Shadow price (Rs.)
Time 3 Lakh
Energy 500
1. (c) According to your estimate, the contribution of one hour of academics to the
annualized salary is Rs. 4 lakh. What is the range of the said contribution,
which will not alter the optimal values of the primal variables as obtained in
the solution to Problem 1 (a)?
Range of the contribution of Value
academics to salary (Rs.)
Minimum value 2 Lakh
Maximum value 6 Lakh
1. (d) In Problem 1 (a), apart from academics and preparations for placements,
you may also engage in extra-curricular activities. You estimate that for
every hour spent in extra-curricular activities, the annualized salary would
be Rs. 5 lakh and 200 calories would be burnt. Other data remaining the
same, how many hours would you now devote to these three activities daily to
maximize the annualized salary?
Optimal value
Activity
(Hours)
Academics 0
Placement preparations 1
Extra-curricular 3
2. Consider the following LP problem.
Min 2 x1 + 6 x2
S .T . x1 + 4 x2 10
2 x1 + 3x2 5
x1 0, x2 free
If y1 and y2 are the dual variables, formulate and solve the dual problem.
Dual formulation:
Max 10 y1 + 5 y2
S .T . y1 + 2 y2 2
4 y1 + 3 y2 = 6
y1 , y2 0
Dual variable Optimal value
y1 1.2
y2 0.4
4. Consider the following goal programming problem.
Goal 1 : 3x + y 3
Goal 2 : x + y 2
Goal 3 : x + 3 y = 3
where x, y 0
If Goal 2 is twice more important than Goal 1 and Goal 3 is thrice more
important than Goal 1, formulate the problem by the weighted linear
programming method (Assign weights 1, 2 and 3 to Goal 1, Goal 2 and Goal
3, respectively).
LP Formulation:
Min s1− + 2s2+ + 3s3+ + 3s3−
S .T . 3x + y + s1+ − s1− = 3
x + y + s2+ − s2− = 2
x + 3 y + s3+ − s3− = 3
x, y free, si+ , si− 0 i = 1, 2, 3
Problem Set # 5
1. (a) A company wishes to manufacture two products using three machines. The
following table shows the unit profits, the number of hours required to process a
unit of a product by a machine and the maximum available machine hours.
Product 1 Product 2
Maximum availability of
Unit profit Rs. 50 70
machine hours
Machine 1 Hours 10 5 2500
Machine 2 Hours 5 10 2000
Machine 3 Hours 1 1.5 450
How many units of each product should the company manufacture to maximize the
total profit? Also, determine the maximum total profit.
Product/Total
Optimal value
profit
Product 1 200 units
Product 2 100 units
Total profit Rs. 17,000
1. (b) What is the per hour worth (shadow price) of each of the three machines?
Machine Per hour worth (Rs.)
Machine 1 2
Machine 2 6
Machine 3 0
1. (c) Determine the range of the profit per unit of each product that will not alter the
optimal values of the primal variables as obtained in the solution to Problem 1 (a)?
Range of the Minimum value Maximum value
profit per unit of (Rs.) (Rs.)
Product 1 35 140
Product 2 25 100
2. (a) Consider the following LP problem in which the objective function and constraint
coefficients have been suppressed. The problem has been solved using the MS Excel
Solver and a partial report on the sensitivity analysis is available after the LP
formulation.
Max c1 x1 + c2 x2
S .T . a11 x1 + a12 x2 10 (1)
a21 x1 + a22 x2 35 (2)
x1 , x2 0
Partial report on the sensitivity analysis:
Final Shadow Constraint R. Allowable Allowable
Constraint
value price H. side increase decrease
Constraint (1) 10 1 10 7.5 3
Constraint (2) 35 1 35 15 15
Determine the new optimal objective function values if the R. H. S. values of the
constraints are changed according to the following:
Change in the R. H. S. values of the New optimal objective
constraints function value
The R. H. S. value of Constraint (1) is
50
changed from 10 to 15
The R. H. S. value of Constraint (2) is
40
changed from 35 to 30
2. (b) Formulate the dual of the following primal problem where y1 and y2 represent the
dual variables corresponding to Constraints (1) and (2), respectively.
Max 3x1 + 5 x2
S .T . x1 + x2 8 (1)
2 x1 + 5 x2 25 (2)
x1 , x2 0
Dual formulation:
Min 8 y1 + 25 y2
s.t. y1 + 2 y2 3
y1 + 5 y2 5
y1 , y2 0
The solution space for the dual problem is [Indicate () the correct answer]
feasible and bounded feasible but unbounded infeasible