1

UPSC 2026
Mathematics

PYQ LPP
 2

PREVIOUS YEARS QUESTIONS

1. FORMULATION OF LPP

GRAPHICAL SOLUTION

2. SIMPLEX METHOD

BASIC FEASIBLE SOLUTIONS (BFS)

SIMPLEX METHOD- BIG M METHOD

3. DUALITY PRINCIPLE

4. TRANSPORTATION PROBLEM

5. ASSIGNMENT PROBLEM

TRAVELLING SALESMAN PROBLEM

CHAPTER 1. FORMULATION OF LPP

Q1. An automobile dealer wishes to put four repairmen R1 , R2 , R3 and R4 to four different jobs J1 , J 2 , J 3 and J 4 . But R3
cannot do the job J 2 . The dealer has estimated the number of man-hours that would be required for each job-man on one-one
basis as given in the following table:

R1 R2 R3 R4

J1 6 2 3 4

J2 9 7 - 5

J3 6 4 7 5

J4 6 8 8 9

Formulate the above as a Linear Programming Problem. [1d IFoS 2022]

Q2. UPSC maintenance section has purchased sufficient number of curtain cloth pieces to meet the 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 variable pieces. Form a linear programming problem in standard form that
decides the number of pieces cut in different ways so that the total trim loss is minimum. Also give a basic feasible solution
to it. [1e UPSC CSE 2020]

CHAPTER 2. GRAPHICAL SOLUTION

Q1. Solve graphically the following LLP:

Max z  5 x1  3x2

subject to

3x1  2 x2  12

 x1  x2  1

 x1  x2  2

x1 , x2  0

If the objective function z is changed to Max z  6 x1  4 x2 , while the constraints remain the same, then comment on the
number of solutions. Will  4, 0  be also a solution? [1d 2020 IFoS]
Q2. A firm manufactures two product A and B on which the profits earned per unit are ₹3 and ₹4 respectively. Each product
is processed on two machines M1 and M2. Product A requires one minute of processing time on M1 and two minutes on M2,
while B requires one minute on M1 and one minute on M2. machine M1 is available for not more than 7 hours 30 minutes,
while machine M2 is available for 10 hours during any working day. Find the number of units of products A and B to be
manufactured to get maximum profit, using graphical method. [1e 2019 IFoS]

Q3. Using graphical method, find the maximum value of

2x  y subject to

4 x  3 y  12

4x  y  8

4x  y  8

x, y  0 . [1e UPSC CSE 2017]

Q4. Find the maximum value of 5 x  2 y with constraints x  2 y  1, 2 x  y  1, x  0 and y  0 by graphical method.
[1e UPSC CSE 2016]

Q5. Solve graphically:

Maximize z  7x  4 y

subject to 2 x  y  2, x  10 y  10 and x  8 . (Draw your own graph without graph paper).

Q6. Solve graphically:

Maximize Z  6 x1  5 x2

subject to 2 x1  x2  16
 4

x1  x2  11

x1  2 x2  6

5 x1  6 x2  90

x1 , x2  0 . [1e UPSC CSE 2014]

CHAPTER3. BASIC FEASIBLE SOLUTIONS (BFS)

Q1. How many basic solutions are there in the following linearly independent set of equations? Find all of them.

2 x1  x2  3x3  x4  6

4 x1  2 x2  x3  2 x4  10 . [3c UPSC CSE 2018]

[1e 2016 IFoS]

Q3. Consider the following linear programming problem:

Maximize Z  x1  2 x2  3x3  4 x4

subject to x1  x2  2 x3  3x4  12

x2  2 x3  x4  8

x1 , x2 , x3 , x4  0
Using the definition, find its all basic solutions. Which of these are degenerate basic feasible solutions and which are non-
degenerate basic feasible solutions?

Without solving the problem, show that it has an optimal solution. Which of the basic feasible solution(s) is/are optimal? [3c
UPSC CSE 2015]

Q4. x1  4, x2  1, x3  3 is a feasible solution of the system of equations

2 x1  3x2  x3  8

x1  2 x2  3x3  15

Reduce the feasible solution to two different basic feasible solutions. [4c 2013 IFoS]

SIMPLEX METHOD

Q1. Solve the linear programming problem using simplex method:

Minimize z  6 x1  2 x2  5x3

subject to 2 x1  3x2  x3  14
 5

4 x1  4 x2  10 x3  46

2 x1  2 x2  4 x3  37

x1  2, x2  1, x3  3 . [3b UPSC CSE 2020]

Q2. Solve the following LPP by simplex method:

Max z  2 x1  x2
subject to

2 x1  2 x2  1

2 x1  4 x2  3

2 x1  x2  2

x1 , x2  0

Dies there exist an alternate optimal solution? If yes, give one and hence find all the optimal solutions.

[3c 2020 IFoS]

Q3. Use simplex method to solve the following problem:

Maximize z  2 x1  5 x2

subject to x1  4 x2  24

3x1  x2  21

x1  x2  9

x1 , x2  0 . [3c 2019 IFoS]

Q4. Solve by simplex method the following Linear Programming Problem:

Maximize Z  3x1  2 x2  5x3

subject to the constraints

x1  2 x2  x3  430

3x1  2 x3  460

x1  4 x2  420
 6

x1 , x2 , x3  0 . [1d 2018 IFoS]

Q5. Solve the following linear programming problem by simplex method

Maximize

z  3x1  5x2  4 x3
subject to

2 x1  3x2  8

2 x2  5 x3  10

3x1  2 x2  4 x3  15

x1 , x2 , x3  0 . [3c UPSC CSE 2017]

Q6. Solve by simplex method the following LPP:

Minimize Z  x1  3x2  2 x3
subject to the constraints

3x1  x2  2 x3  7

2 x1  4 x2  12

4 x1  3x2  8 x3  0

and x1 , x2 , x3  0 . [1d 2017 IFoS]

Q7. Maximize

z  2 x1  3x2  6 x3

subject to

2 x1  x2  x3  5

3x2  2 x3  6

x1  0, x2  0, x3  0

Is the optimal solution unique? Justify your answer. [2c UPSC CSE 2016]
 7

Q8. A manufacturer wants to maximize his daily output of bulbs which are made by two processes P 1 and P2. If x1 is the output
by process P1 and x2 is the output by process P2, then the total labour hours is given by 2 x1  3x2 and this cannot exceed 130,
the total machine time is given by 3x1  8 x2 which cannot exceed 300 and the total raw material is given by 4 x1  2 x2 and
this cannot exceed 140. What should x1 and x2 be so that the total output x1  x2 is maximum? Solve by the simplex method
only.

[3c 2015 IFoS]

Q9. Find all optimal solutions of the following linear programming problem by the simplex method:

Maximize Z  30 x1  24 x2
subject to

5x1  4 x2  200

x1  32

x2  40

x1 , x2  0 . [4c UPSC CSE 2014]

SIMPLEX METHOD – BIG M METHOD

Q1. Solve the linear programming problem using Simplex method.

Minimize Z  x1  2 x2  3x3  2 x4

subject to

x1  2 x2  3x3  x4  4

x1  2 x2  x3  2 x4  4

and x1 , x2 , x3 , x4  0 . [3b UPSC CSE 2019]

Q2. Solve the following linear programming problem by Big M-method and show that the problem has finite optimal solutions.
Also find the value of the objective function:

Minimize z  3x1  5 x2

subject to x1  2 x2  8

3x1  2 x2  12

5x1  6 x2  60 ,
 8

x1 , x2  0 . [2b UPSC CSE 2018]

Q3. Maximize z  2 x1  3x2  5x3

subject to x1  x2  x3  7

and 2 x1  5 x2  x3  10, xi  0 . [1e UPSC CSE 2013]

6. DUALITY PRINCIPLE

Q1. Use graphical method to solve the linear programming problem.

Maximize Z  3x1  2 x2
subject to

x1  x2  1

x1  x3  3

and x1 , x2 , x3  0 . [1e UPSC CSE 2019]

Q2. Consider the following LPP,

Maximize Z  2 x1  4 x2  4 x3  3x4

subject to

x1  x2  x3  4

x1  4 x2  x4  8

and x1 , x2 , x3 , x4  0

Use the dual problem to verify that the basic solution  x1, x2  is not optimal. [4d UPSC CSE 2019]
Q3. 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:

Maximize Z  2 x1  4 x2  5x3

subject to

x1  4 x2  2 x3  2
 9

 x1  2 x2  3x3  1

x1 , x2 , x3  0 . [4c UPSC CSE 2015]

TRANSPORTATION PROBLEM

Q1. 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.

Destinations
D1 D 2 D3 D4
10 0 20 11
S1 15
12 8 9 20
Sources S2 25 Availability
S3 0 14 16 18
10
5 20 15 10

Demand
[4c UPSC CSE 2020]

Q2. Find the minimum transportation cost using Vogel's approximation method for the following transportation problem:

Destinations
D1 D 2 D3 D4 Availability

S1 9 16 15 9 15
Sources S2 2 1 3 5 25
S3 6 4 7 3 20
Demand 10 15 25 10
[4c 2020 IFoS]

Q3. The capacities of three production facilities S1, S2 and S3 and the requirements of four destinations D1, D2, D3 and D4
and transportation costs in rupees are given in the following table:

D1 D2 D3 D4 Capacity

S1 19 30 50 10 7

S2 70 30 40 60 9

S3 40 8 70 20 18
 10

Demand 5 8 7 14 34

Find the minimum transportation cost using Vogel's Approximation Method (VAM).

[4d 2018 IFoS]

Q4. Find the initial basic feasible solution of the following transportation problem using Vogel's approximation method and
find the cost.

Destinations
D1 D2 D3 D4 D5
O1 4 7 0 3 6 14
Origins O2 1 2 3 3 8 9 Supply
O3 3 1 4 0 5 17
8 3 8 13 8
Demand
[4b UPSC CSE 2017]

Q5. Solve the following transportation problem:

D1 D2 D3 Supply

O1 5 3 6 20

O2 4 7 9 40

Demand 15 22 23 60

[4c 2015 IFoS]

Q6. 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:

Destinations

D1 D2 D3 D4 Supply

O1 6 4 1 5 15

Origins O2 8 9 2 7 16

O3 4 3 6 2 5

Demand 6 10 15 4

[2c UPSC CSE 2014]

Q7. Obtain the initial basic feasible solution for the transportation problem by North-West corner rule:
 11

Retail Shop

R1 R2 R3 R4 R5 Supply

F1 1 9 13 36 51 50

Factory F2 24 12 16 20 1 100

F3 14 35 1 23 26 150

100 70 50 40 40

[1d 2014 IFoS]

CHAPTER 5. ASSIGNMENT PROBLEM

Q1.

Machine

M1 M2 M3 M4 M5

O1 24 29 18 32 19

O2 17 26 34 22 21
Operator O3 27 16 28 17 25

O4 22 18 28 30 24

O5 28 16 31 24 27

In a factor there are five operators O1, O2, O3, O4, O5 and five machines M1, M2, M3, M4, M5. The operating costs are given
when the Oi operator operates the Mj machine i, j  1, 2,....,5 . But there is a restriction that O3 cannot be allowed to operate
the third machine M3 and O2 cannot be allowed to operate the fifth machine M 5. The cost matrix is given above. Find the
optimal assignment and the optimal assignment cost also. [4c UPSC CSE 2018]

Q2. A computer centre has four expert programmers. The centre needs four application to programs to be developed. The head
of the centre after studying carefully the programs to be developed, estimates the computer times in hours required by the
experts to the application programs as follows:

Programs

A B C D

P1 5 3 2 8

Programmer P2 7 9 2 6

P3 6 4 5 7

P4 5 7 7 8
 12

Assign the programs to the programmers in such a way that total computer time is least.

[4d 2017 IFoS]

TRAVELLING SALESMAN PROBLEM

Q1. A salesman wants to visit cities C1, C2, C3 and C4. He does not want to visit any city twice before completing the four of
all the cities and wishes to return to his home city, the starting station. Cost of going from one city to another in rupees is given
below in the table. Find the least cost route.

To City

C1 C2 C3 C4

C1 0 30 80 50

From City C2 40 0 140 30

C3 40 50 0 20

C4 70 80 130 0

[4c 2019 IFoS]

Q2. Solve the following assignment problem to maximize the sales:

Territories

I II III IV V

A 3 4 5 6 7

B 4 15 13 7 6
Salesmen C 6 13 12 5 11

D 7 12 15 8 5

E 8 13 10 6 9

