Mathematics Optional Foundation Course

By Avinash Singh (Ex IES, B.Tech IITR)

Previous Year Questions: Linear Programming (2008-2022)

Formulation of LPP

1. A paint factory produces both interior and exterior paint from two raw materials 𝑀1 and
𝑀2 .The basic data is as follows:
Tons of Raw material per
ton of Maximum daily
Exterior Interior availability
Paint Paint
Raw Material 𝑴𝟏 6 4 24
Raw Material 𝑴𝟐 1 2 6
Profit per Ton
5 4
(1000)

A market survey indicates that the daily demand of interior paint cannot exceed that of exterior
paint by more than 1 ton. The maximum daily demand of interior paint is 2 tons. The factory
wants to determine the optimum product mix of interior and exterior paint that maximizes daily
profits. Formulate the LP problem for this situation.

2. For each hour per day that Ashok studies mathematics, it yields him 10 marks and for each
hour that he studies physics, it yields him 5 marks. He can study at most 14 hours a day
and he must get at least 40 marks in each. Determine graphically how many hours a day he
should study mathematics and physics each, in order to maximize his marks?
3. An agricultural firm has 180 tons of nitrogen fertilizer, 250 tons of phosphate and 220 tons of
potash. It will be able to sell a mixture of these substances in their respective ratio 3: 3: 4 at
a profit of Rs.1500 Per ton and a mixture in the ratio 2: 4: 2 at a profit of Rs. 1200 per ton.
Pose a linear programming problem to show how many tons of these two mixtures should be
prepared to obtain the maximum profit.
4. How many basic solutions are there in the following linearly independent set of equations?
Find all of them.
2𝑥1 − 𝑥2 + 3𝑥3 + 𝑥4 = 6; 4𝑥1 − 2𝑥2 − 𝑥3 + 2𝑥4 = 10

1
5. UPSC maintenance section has purchased sufficient number of curtain cloth pieces for
curtain requirement of its building. The length of each piece is 17 feet. The requirement
according to curtain length is as follows:
Curtain Length (in feet) Number Required

5 700

9 400

7 300

The width of all curtains is same as that of available pieces. Form a linear programming problem
in standard from that decide the number of pieces cut in different ways so that the total trim
loss is minimum. Also give a basic feasible solution to it.

Graph Method

1. Solve Graphically 𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒 𝑍 = 6𝑥1 + 5𝑥2

2𝑥1 + 𝑥2 ≤ 16,
𝑥1 + 𝑥2 ≤ 11
𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 ∶ 𝑥1 + 2𝑥2 ≥ 6
5𝑥1 + 6𝑥2 ≤ 90
𝑥1 , 𝑥2 ≥ 0
2. Find the maximum value of 5𝑥 + 2𝑦 with constraints 𝑥 + 2𝑦 ≥ 1, 2𝑥 + 𝑦 ≤ 1, 𝑥 ≥ 0 𝑎𝑛𝑑 𝑦 ≥ 0 by
graphical method.
3. Using graphical method, find the maximum value of 2𝑥 + 𝑦
Subject to 4𝑥 + 3𝑦 ≤ 12, 4𝑥 + 𝑦 ≤ 8, 4𝑥 − 𝑦 ≤ 8, 𝑥, 𝑦 ≥ 0
4. Using graphical method, solve the linear programming problem.
𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒 𝑍 = 3𝑥1 + 2𝑥2
𝑥1 − 𝑥2 ≥ 1,
Subject to 𝑥1 + 𝑥3 ≥ 3
𝑥1 , 𝑥2 , 𝑥3 ≥ 0

Simplex Method

1. 𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒 𝑍 = 3𝑥1 + 5𝑥2 + 4𝑥3

2𝑥1 + 3𝑥2 ≤ 8,
3𝑥1 + 2𝑥2 + 4𝑥3 ≤ 15
𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 ∶
2𝑥2 + 5𝑥3 ≤ 10
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
2. Solve by simplex method, the following LP Problem:
𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒 𝑍 = 5𝑥1 + 3𝑥2
3𝑥1 + 5𝑥2 ≤ 15,
𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 ∶ 5𝑥1 + 2𝑥2 ≤ 10
𝑥1 , 𝑥2 ≥ 0

2
3. 𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒 𝑍 = 2𝑥1 + 3𝑥2 − 5𝑥3
𝑥1 + 𝑥2 + 𝑥3 = 7,
𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 ∶ 2𝑥1 − 5𝑥2 + 𝑥3 ≥ 10
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
𝑥1 + 2𝑥2 − 2𝑥3 + 4𝑥4 ≤ 40
2𝑥1 − 𝑥2 + 𝑥3 + 2𝑥4 ≤ 8
4. 𝑀𝑖𝑛𝑖𝑚𝑖𝑠𝑒 𝑍 = 5𝑥1 − 4𝑥2 + 6𝑥3 − 8𝑥4 , subject to the constraints,
4𝑥1 − 2𝑥2 + 𝑥3 − 𝑥4 ≤ 10
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0
5. Find all optimal solutions of the following linear programming problem by the simplex method:
𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒 𝑍 = 30𝑥1 + 24𝑥2

5𝑥1 + 4𝑥2 ≤ 200,

𝑥1 ≤ 32
𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 ∶
𝑥2 ≤ 40
𝑥1 , 𝑥2 ≥ 0
6. Consider the following linear programming problem:
Maximise: 𝑥1 + 2𝑥2 − 3𝑥3 + 4𝑥4
𝑥1 + 𝑥2 + 2𝑥3 + 3𝑥4 = 12
Subject to 𝑥2 + 2𝑥3 + 𝑥4 = 8
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0
a. Using the definition, find its all basic solutions. Which of these are degenerate basic
feasible solutions and which are non-degenerate basic feasible solutions?
b. Without solving the problem, show that it has an optimal solution and which of the
basic feasible solution(s) is/are optimal?

7. 𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒 𝑍 = 2𝑥1 + 3𝑥2 + 6𝑥3

2𝑥1 + 𝑥2 + 𝑥3 ≤ 5,
𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 ∶ 3𝑥2 + 2𝑥3 ≤ 6
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
Is the optimum solution unique? Justify the answer.
8. Solve the following linear programming problem by simplex method:
𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒 𝑍 = 3𝑥1 + 5𝑥2 + 4𝑥3

2𝑥1 + 3𝑥2 ≤ 8,
2𝑥2 + 5𝑥3 ≤ 10
𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 ∶
3𝑥1 + 2𝑥2 + 4𝑥3 ≤ 15
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
9. Solve the following liner programming problem by Big M-method and show that the problem
has finite optimal solutions. Also Find the value of the objective Function:
𝑥1 + 2𝑥2 ≥ 8
3𝑥 + 2𝑥2 ≥ 12
𝑀𝑖𝑛 𝑍 = 3𝑥1 + 5𝑥2 , subject to the constraints, 1
5𝑥1 + 6𝑥2 ≤ 60
𝑥1 , 𝑥2 ≥ 0

3
10. Solve the linear programming problem using Simplex Method
Minimise: 𝑥1 + 2𝑥2 − 3𝑥3 − 2𝑥4

𝑥1 + 2𝑥2 − 3𝑥3 + 𝑥4 = 4
Subject to 𝑥1 + 2𝑥2 − 𝑥3 + 2𝑥4 = 4
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0

11. Solve the linear programming problem using simplex method:

𝑀𝑖𝑛𝑖𝑚𝑖𝑠𝑒 𝑍 = −6𝑥1 − 2𝑥2 − 5𝑥3

2𝑥1 − 3𝑥2 + 𝑥3 ≤ 14,

−4𝑥1 + 4𝑥2 + 10𝑥3 ≤ 46
𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 ∶
2𝑥1 + 2𝑥2 − 4𝑥3 ≤ 37
𝑥1 ≥ 2, 𝑥2 ≥ 1, 𝑥3 ≥ 3
12. Solve the following linear Programming problem using Big M method:
𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒 𝑍 = 4𝑥1 + 5𝑥2 + 2𝑥3

2𝑥1 + 𝑥2 + 𝑥3 ≥ 10,
𝑥 + 3𝑥2 + 𝑥3 ≤ 12
𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 ∶ 1
𝑥1 + 𝑥2 + 𝑥3 = 6
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
13. Use two phase method to solve the following linear programming problem:
Minimise 𝑧 = 𝑥1 + 𝑥2

2𝑥1 + 𝑥2 ≥ 4
Subject to 𝑥1 + 7𝑥2 ≥ 7
𝑥1 , 𝑥2 ≥ 0

Duality

1. Find the dual of the following linear programming problem:

𝑀𝑎𝑥 𝑍 = 2𝑥1 − 𝑥2 + 𝑥3

𝑥1 + 𝑥2 − 3𝑥3 ≤ 8
4𝑥1 − 𝑥2 + 𝑥3 = 2
𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 ∶
2𝑥1 + 3𝑥2 − 𝑥3 ≥ 5
𝑥1 , 𝑥2 , 𝑥3 ≥ 0

4
2. Construct the dual of the primal problem: 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑍 = 2𝑥1 + 𝑥2 + 𝑥3 , subject to the
𝑥1 + 𝑥2 + 𝑥3 ≥ 6
3𝑥1 − 3𝑥2 + 2𝑥3 = 3
constraints,
−4𝑥1 + 3𝑥2 − 6𝑥3 = 1
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
3. Write down the dual of the following LP problem and hence solve it by graphical method
2𝑥1 + 𝑥2 ≥ 1
𝑀𝑖𝑛 𝑍 = 6𝑥1 + 4𝑥2 , subject to the constraints, 3𝑥1 + 4𝑥2 ≥ 1.5
𝑥1 , 𝑥2 ≥ 0
4. Solve the following linear programming problem by the simplex method. Write its dual. Also,
write the optimal solution of the dual from the optimal table of the given problem:
𝑥1 + 4𝑥2 − 2𝑥3 ≤ 2
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑍 = 2𝑥1 − 4𝑥2 + 5𝑥3 , subject to the constraints, −𝑥1 + 2𝑥2 + 3𝑥3 ≤ 1
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
5. Consider the following LPP,
Maximise: 2𝑥1 + 4𝑥2 + 4𝑥3 − 3𝑥4

𝑥1 + 𝑥2 + 𝑥3 = 4
Subject to 𝑥1 + 4𝑥2 + 𝑥4 = 8
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0
Use the dual problems to verify that the basic solution (𝑥1 , 𝑥2 ) is not optimal.
6. Convert the following LPP into dual LPP:
3𝑥1 − 𝑥2 − 2𝑥3 ≤ 7
2𝑥1 − 4𝑥2 ≥ 12
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑍 = 𝑥1 − 3𝑥2 − 2𝑥3 , subject to the constraints,
−4𝑥1 + 3𝑥2 + 8𝑥3 = 10
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
Where 𝑥1 , 𝑥2 ≥ 0 𝑎𝑛𝑑 𝑥3 is unrestricted in sign.
7. Solve the following linear programming problem by the simplex method. Write its dual. Also,
write the optimal solution of the dual from the optimal table of the given problem:

𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒 𝑍 = 𝑥1 + 𝑥2 + 𝑥3

2𝑥1 + 𝑥2 + 𝑥3 ≤ 2,
4𝑥1 + 2𝑥2 + 𝑥3 ≤ 2
𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 ∶ (15, 2022)
3𝑥1 + 2𝑥2 + 4𝑥3 ≤ 15
𝑥1 , 𝑥2 , 𝑥3 ≥ 0

5
Transport Problem

1. Solve the following transportation problem

Destination
𝐷1 𝐷2 𝐷3 𝐷4 𝐷5 𝐷6 Availability
𝐹1 2 1 3 3 2 5 50

Factories
𝐹2 3 2 2 4 3 4 40
𝐹3 3 5 4 2 4 1 60
𝐹4 4 2 2 1 2 2 30
Demand 30 50 20 40 30 10

by finding the initial solution by Matrix Minima Method.

2. Determine an optimal transportation programme so that the transportation cost of 340 tons
of a certain type of material from three factories to five warehouses 𝑊1 , 𝑊2 , 𝑊3 , 𝑊4 , 𝑊5 is
minimized. The five warehouses must receive 40 tons, 50 tons, 70 tons, 90 tons and 90 tons
respectively. The availability of the material at 𝐹1 , 𝐹2 , 𝐹3 , is 100 tons, 120 tons, 120 tons
respectively. The transportation costs per ton from factories to warehouses are given in the
table below:

𝑾𝟏 𝑾𝟐 𝑾𝟑 𝑾𝟒 𝑾𝟓
𝑭𝟏 4 1 2 6 9
𝑭𝟐 6 4 3 5 7
𝑭𝟑 5 2 6 4 8

Use Vogel’s Approximation Method to obtain the initial basic feasible solution.
3. By the method of Vogel, determine an initial basic feasible solution for the following
transportation problem: Products 𝑃1 , 𝑃2 , 𝑃3 & 𝑃4 have to be sent of destinations 𝐷1 , 𝐷2 𝑎𝑛𝑑 𝐷3.
The cost of sending product 𝑃𝑖 to destinations 𝐷𝑗 is 𝐶𝑖𝑗 , where the matrix
10 0 15 5
[𝐶𝑖𝑗 ] = [ 7 3 6 15]
0 11 9 13
The total requirements of destinations 𝐷1 , 𝐷2 𝑎𝑛𝑑 𝐷3 are given by 45, 45, 95 respectively and
the availability of the products 𝑃1 , 𝑃2 , 𝑃3 & 𝑃4 are respectively 25, 35, 55 and 70.

4. Find the initial basic feasible solution to the following transportation problem by Vogel’s
approximation method. Also, find its optimal solution and the minimum transportation cost.

6
 𝐷1 𝐷2 𝐷3 𝐷4 Supply

origins 𝑂1 6 4 1 5 14

𝑂2 8 9 2 7 16

𝑂3 4 3 6 2 5

Demand 6 10 15 4

5. Find the initial basic feasible solution of the following transportation problem using Vogel’s
approximation methods and find the cost.
𝐷1 𝐷2 𝐷3 𝐷4 𝐷5 Supply

𝑂1 4 7 0 3 6 14

origins 𝑂2 1 2 -3 3 8 9

𝑂3 3 -1 4 0 5 17

Demand 8 3 8 13 8

6. Find the initial basic feasible solution of the following transportation problem by Vogel’s
approximation method and use it to find the optimal solution and the transportation cost of
the problem.
𝐷1 𝐷2 𝐷3 𝐷4 Supply

Sources 𝑆1 10 0 20 11 15

𝑆2 12 8 9 20 25

𝑆3 0 14 16 18 10

Demand 5 20 15 10

7. Find the initial basic feasible solution of the following transportation problem by Vogel’s
approximation method and use it to find the optimal solution and the transportation cost of
the problem:
Destination

𝐴 𝐵 𝐶 𝐷

Source 𝑆1 21 16 25 13 11

𝑆2 17 18 14 23 13

𝑆3 32 27 18 41 19

Requirement 6 10 12 15 43

(20, 2022)

7
Assignment Problem

1. Solve the minimum time assignment problem:

Machines
𝑀1 𝑀2 𝑀3 𝑀4
𝐽1 3 12 5 14
𝐽2 7 9 8 12
𝐽3 5 11 10 12
𝐽4 6 14 4 11

2. Solve the assignment problem to maximise the sale:

Territories
I II III IV V
Salesmen A 3 4 5 6 7
B 4 15 13 7 6
C 6 13 12 5 11
D 7 12 15 8 5
E 8 13 10 6 9

3. In a factory there are five operators 𝑂1 , 𝑂2 , 𝑂3 , 𝑂4 , 𝑂5 and five machines 𝑀1 , 𝑀2 , 𝑀3 , 𝑀4 , 𝑀5 . The

operating costs are given when the operator 𝑂𝑖 operates the 𝑀𝑗 machine. There are
restrictions that 𝑂3 cannot be allowed to operate the 𝑀3 and 𝑂2 cannot be allowed to operate
the 𝑀5 . The cost matrix is given below. Find the optimal assignment and the optimal
assignment cost also.
Machines
𝑀1 𝑀2 𝑀3 𝑀4 𝑀5
𝑂1 24 29 18 32 19
𝑂2 17 26 34 22 21
𝑂3 27 16 28 17 25
𝑂4 22 18 28 30 24
𝑂5 28 16 31 24 27

8
4. A department of company has five employees with five jobs to be performed. The time (in
hours) that each man takes to perform each job is given in the effectiveness matrix. Assign all
the jobs to these five employees to minimize the total processing time:

Employees

I II III IV V

Jobs A 10 5 13 15 16

B 3 9 18 13 6

C 10 7 2 2 2

D 7 11 9 7 12

E 7 9 10 4 12