Linear Programming
UPSC Mathematics Optional
Asiya Shaikh
AROUSH ACADEMY
, Linear Programming Problem (LPP)-Model Formulation
Definition
Linear programming (LP) is a mathematical optimization technique used to find the best outcome in a
mathematical model with linear relationships, subject to a set of constraints. The goal of linear programming is
to maximize or minimize a linear objective function while satisfying a system of linear inequalities or equations.
In simple terms, Linear Programming problem is a method to optimize a linear objective function subject to
constraints represented by linear equations or inequalities.
Key components of a linear programming problem:
1. Objective Function: It is a linear equation that represents what we want to optimize (either minimize or
maximize).
It is usually written in the form "𝑎1 𝑥1 + 𝑎2 𝑥2 + 𝑎2 𝑥3 + ⋯ + 𝑎𝑛 𝑥𝑛 " where 𝑥1 , 𝑥2 , … 𝑥𝑛 are decision variables &
𝑎1 , 𝑎2 , … , 𝑎𝑛 are coefficients defining their impact on optimization.
2. Decision variables: These are the variables that we can control or adjust to achieve the desired outcome.
They are typically represented as 𝑥, 𝑦, 𝑧, etc., and can take on real values.
3. Constraints: These are a set of linear equations or inequalities that restrict the values of the decision
variables. Constraints represent limitations or requirements of the problem.
4. Non-negativity restriction: It refers to a constraint that specifies that decision variables must take on
non-negative values.
5. Feasible Region: The feasible region is the set of all possible combinations of values for the decision
variables that satisfy all the constraints. It is the region in which a solution to the problem must lie.
6. Optimization Goal: The ultimate goal of LPP is to find the values of the decision variables that either
maximize or minimize the objective function while staying within the feasible region. That is, maximize or
minimize some numerical value representing profit, cost, production quantity, etc.
Formulation of a Linear Programming Problem
The standard form of a linear programming problem is
Decision variables: 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛 :(which need to be found)
Objective Function: Maximize / Minimize: 𝒵 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + 𝑐3 𝑥3 + ⋯ + 𝑐𝑛 𝑥𝑛
Constraints:
Subject to: 𝑎11 𝑥1 + 𝑎12 𝑥2 + 𝑎13 𝑥3 + ⋯ + 𝑎1𝑛 𝑥𝑛 (≤ = ≥)𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + 𝑎23 𝑥3 + ⋯ + 𝑎2𝑛 𝑥𝑛 (≤ = ≥)𝑏2
⋮
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + 𝑎𝑚3 𝑥3 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 (≤ = ≥)𝑏𝑚
Non negativity: 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛 ≥ 0
Here 𝑎11 , 𝑎12 , … 𝑎1𝑛 , 𝑎21 , 𝑎22 , … , 𝑎2𝑛 , … 𝑎𝑚𝑛 are input output constraints and
𝑏1 , 𝑏2 , 𝑏3 , … , 𝑏𝑚 are capacities where ∀ 𝑏𝑖 ≥ 0 and
𝑐1 , 𝑐2 , 𝑐3 , … , 𝑐𝑚 are cost or profit coefficients.
Note: Subject to may be any one of the following ≤, =, 𝑜𝑟 ≥. And here 𝑛 = number of decision variables and
𝑚 = number of constraints.
The linear programming can be stated in matrix form as follows:
To find the Decision variables: 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛 and to optimize the
Objective Function: Max/Min: 𝒵 = 𝐂𝓍
Subject to: 𝐀𝓍 (≤ = ≥ )𝐛
Non negativity: 𝓍≥𝟎
Where 𝐀 = [𝑎𝑖𝑗 ]𝑚×𝑛 is called coefficient matrix, where 𝑎𝑖𝑗 indicates the amount of 𝑖 𝑡ℎ type of resource
necessary to manufacture one unit of product 𝑗, 𝐂 = [𝑐1 𝑐2 𝑐3 … 𝑐𝑚 ] are cost vector or sometime called as profit
matrix, 𝟎 is null matrix of type 𝑛 × 1,
, 𝑏1 𝑥1
𝑏2 𝑥2
𝐛 = [ ] are requirement vector referred as availability matrix or resource matrix & 𝓍 = [ ⋮ ] are matrix of
⋮
𝑏𝑚 𝑥𝑛
decision variables.
Formulation of LPP involves the following steps
1. Define the decision variables
2. State the objective function: Maximize the profit or Minimize the loss
3. Define the constraints: Limitation or Restrictions
4. Specify the feasible region: Set of all feasible solution that satisfy the constraints.
5. Solve the problem: Using LPP method, to find the optimal solution.
Note: step 4 and 5 we will be done later.
Examples for formulation of LPP
Q: A manufacturer producing a line of patent medicines is setting up a production plant for medicines 𝑀1 & 𝑀2 .
There are sufficient ingredients available to produce 20,000 bottles of 𝑀1 & 40,000 bottles of 𝑀2 . However,
there are only 45,000 bottles into which either of the medicines can be filled. Furthermore, it takes 3 hours to
prepare enough material to fill 1,000 bottles of 𝑀1 & 1 hour to prepare enough material to fill 1,000 bottles of
𝑀2 , with a total of 66 hours available for this operation. The profit margins are ₹8 per bottle of 𝑀1 & ₹7 per
bottle of 𝑀2 . Formulate the problem as a linear programming problem (LPP).
Solution:
Decision variables are:
𝑥1 = Number of bottles of 𝑀1
𝑥2 = Number of bottles of 𝑀2
The Objective function is
Maximize 𝒵 = 8𝑥1 + 7𝑥2 : total profit
Constraints
To produce bottles of 𝑀1 : 𝑥1 ≤ 20000
To produce bottles of 𝑀2 : 𝑥1 ≤ 40000
3 1
Time required to prepare bottles in hours: 𝑥1 + 𝑥2 ≤ 66
1000 1000
Total bottle into which medicines are filled: 𝑥1 + 𝑥2 ≤ 45000
Non negativity: 𝑥1 , 𝑥2 ≥ 0
Q: A factory manufactures two products A and B. To manufacture one unit of A, 1.5 machine hours & 2.5
machine hours are required. In a month 300 machine hours and 240 labour hours are available. To manufacture
product B 2.5 labour hours and 1.5 labour hours are required. Profit per unit for A is ₹50 and for B is ₹40.
Formulate as LPP.
Solution:
Decision variables are:
𝑥1 = Number of units of A manufactured
𝑥2 = Number of units of B manufactured
The Objective function is
Maximize 𝒵 = 50𝑥1 + 40𝑥2
Constraints
For machine hours: 1.5𝑥1 + 2.5𝑥2 ≤ 300
For labour hours: 2.5𝑥1 + 1.5𝑥2 ≤ 240
Non negativity: 𝑥1 , 𝑥2 ≥ 0
Portfolio Selection (Investment Decisions)
Q: An investor is considering investing in two securities A and B. The risk and return associated with these
securities is different. Security A gives a return of 9% and has a risk factor of 5 on a scale of 0 to 10. Security
, B gives a return of 15% but has a risk factor of 8. Total amount invested is ₹5,00,000. Total minimum return on
investment should be 12%. Maximum combined risk should be more than 6. Formulate the LPP.
Solution:
Decision variables are:
𝑥1 = Amount invested in A
𝑥2 = Amount invested in B
The Objective function is
Maximize 𝒵 = 0.09𝑥1 + 0.15𝑥2
Constraints
Related to total investment: 𝑥1 + 𝑥2 = 5,00,000
Related to return: 0.09𝑥1 + 0.15𝑥2 = 0.12 × 5,00,000 = 60,000
Related to Risk: 5𝑥1 + 8𝑥2 = 6 × 5,00,000 = 30,00,000
Non negativity: 𝑥1 , 𝑥2 ≥ 0
Inspection Problem
Q: In the context of quality control inspection, a company employs two grades of inspectors, Grade I and Grade
II. The task is to perform quality control inspections, with a requirement of inspecting at least 1,500 pieces in
an 8-hour workday. Grade I inspectors can examine 20 pieces per hour with an accuracy rate of 96%, while
Grade II inspectors can check 14 pieces per hour with an accuracy rate of 92%.
The company incurs different wages for these inspectors, with Grade I inspectors earning ₹5 per hour & Grade
II inspectors earning ₹4 per hour. Additionally, any inspection error by an inspector result in a cost of ₹3 to the
company. Given that the company employs 10 Grade I inspectors and 15 Grade II inspectors, the objective is to
determine the optimal assignment of inspectors to minimize the daily inspection cost.
Solution:
Hourly cost of a Grade I inspector: ₹(5 + 3 × 0.04 × 20) = ₹7.40
Hourly cost of a Grade II inspector: ₹(4 + 3 × 0.08 × 14) = ₹7.36
Decision variables are:
𝑥1 = Number of Grade I inspector
𝑥2 = Number of Grade II inspector
The Objective function is
Minimize 𝒵 = 7.40𝑥1 + 7.36𝑥2 : daily inspection cost
Constraints
Number of Grade I inspector: 𝑥1 ≤ 10
Number of Grade I inspector: 𝑥2 ≤ 15
Number of pieces Inspected daily: 160𝑥1 + 112𝑥2 ≥ 1500
Non negativity: 𝑥1 , 𝑥2 ≥ 0
Trim Loss Problem:
Q: A manufacturer of cylindrical containers receives tin sheets in widths of 30cm and 60cm. These sheets need
to be cut into three different widths of 15cm, 21cm, & 27cm to manufacture containers. The production plan
involves creating 400 containers of 15cm width, 200 containers of 21cm width, & 300 containers of 27cm width.
The manufacturer purchases bottom plates and top covers separately, and there are no limitations on the
lengths of standard tin sheets. The goal is to formulate a Linear Programming Problem (LPP) to determine the
production schedule that minimizes trim losses.
Solution:
Decision variables: Let 𝑥𝑖𝑗 represent the cutting combinations where each combination results in a
certain amount of trim loss.
Possible cutting combinations for both types of sheets are:
Width 30 cm 60 cm
𝑥11 𝑥12 𝑥13 𝑥21 𝑥22 𝑥23 𝑥24 𝑥25 𝑥26
15 2 0 0 4 2 2 1 0 0
21 0 1 0 0 1 0 2 1 0
27 0 0 1 0 0 1 0 1 2
Loss cm 0 9 3 0 9 3 3 12 6
UPSC Mathematics Optional
Asiya Shaikh
AROUSH ACADEMY
, Linear Programming Problem (LPP)-Model Formulation
Definition
Linear programming (LP) is a mathematical optimization technique used to find the best outcome in a
mathematical model with linear relationships, subject to a set of constraints. The goal of linear programming is
to maximize or minimize a linear objective function while satisfying a system of linear inequalities or equations.
In simple terms, Linear Programming problem is a method to optimize a linear objective function subject to
constraints represented by linear equations or inequalities.
Key components of a linear programming problem:
1. Objective Function: It is a linear equation that represents what we want to optimize (either minimize or
maximize).
It is usually written in the form "𝑎1 𝑥1 + 𝑎2 𝑥2 + 𝑎2 𝑥3 + ⋯ + 𝑎𝑛 𝑥𝑛 " where 𝑥1 , 𝑥2 , … 𝑥𝑛 are decision variables &
𝑎1 , 𝑎2 , … , 𝑎𝑛 are coefficients defining their impact on optimization.
2. Decision variables: These are the variables that we can control or adjust to achieve the desired outcome.
They are typically represented as 𝑥, 𝑦, 𝑧, etc., and can take on real values.
3. Constraints: These are a set of linear equations or inequalities that restrict the values of the decision
variables. Constraints represent limitations or requirements of the problem.
4. Non-negativity restriction: It refers to a constraint that specifies that decision variables must take on
non-negative values.
5. Feasible Region: The feasible region is the set of all possible combinations of values for the decision
variables that satisfy all the constraints. It is the region in which a solution to the problem must lie.
6. Optimization Goal: The ultimate goal of LPP is to find the values of the decision variables that either
maximize or minimize the objective function while staying within the feasible region. That is, maximize or
minimize some numerical value representing profit, cost, production quantity, etc.
Formulation of a Linear Programming Problem
The standard form of a linear programming problem is
Decision variables: 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛 :(which need to be found)
Objective Function: Maximize / Minimize: 𝒵 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + 𝑐3 𝑥3 + ⋯ + 𝑐𝑛 𝑥𝑛
Constraints:
Subject to: 𝑎11 𝑥1 + 𝑎12 𝑥2 + 𝑎13 𝑥3 + ⋯ + 𝑎1𝑛 𝑥𝑛 (≤ = ≥)𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + 𝑎23 𝑥3 + ⋯ + 𝑎2𝑛 𝑥𝑛 (≤ = ≥)𝑏2
⋮
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + 𝑎𝑚3 𝑥3 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 (≤ = ≥)𝑏𝑚
Non negativity: 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛 ≥ 0
Here 𝑎11 , 𝑎12 , … 𝑎1𝑛 , 𝑎21 , 𝑎22 , … , 𝑎2𝑛 , … 𝑎𝑚𝑛 are input output constraints and
𝑏1 , 𝑏2 , 𝑏3 , … , 𝑏𝑚 are capacities where ∀ 𝑏𝑖 ≥ 0 and
𝑐1 , 𝑐2 , 𝑐3 , … , 𝑐𝑚 are cost or profit coefficients.
Note: Subject to may be any one of the following ≤, =, 𝑜𝑟 ≥. And here 𝑛 = number of decision variables and
𝑚 = number of constraints.
The linear programming can be stated in matrix form as follows:
To find the Decision variables: 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛 and to optimize the
Objective Function: Max/Min: 𝒵 = 𝐂𝓍
Subject to: 𝐀𝓍 (≤ = ≥ )𝐛
Non negativity: 𝓍≥𝟎
Where 𝐀 = [𝑎𝑖𝑗 ]𝑚×𝑛 is called coefficient matrix, where 𝑎𝑖𝑗 indicates the amount of 𝑖 𝑡ℎ type of resource
necessary to manufacture one unit of product 𝑗, 𝐂 = [𝑐1 𝑐2 𝑐3 … 𝑐𝑚 ] are cost vector or sometime called as profit
matrix, 𝟎 is null matrix of type 𝑛 × 1,
, 𝑏1 𝑥1
𝑏2 𝑥2
𝐛 = [ ] are requirement vector referred as availability matrix or resource matrix & 𝓍 = [ ⋮ ] are matrix of
⋮
𝑏𝑚 𝑥𝑛
decision variables.
Formulation of LPP involves the following steps
1. Define the decision variables
2. State the objective function: Maximize the profit or Minimize the loss
3. Define the constraints: Limitation or Restrictions
4. Specify the feasible region: Set of all feasible solution that satisfy the constraints.
5. Solve the problem: Using LPP method, to find the optimal solution.
Note: step 4 and 5 we will be done later.
Examples for formulation of LPP
Q: A manufacturer producing a line of patent medicines is setting up a production plant for medicines 𝑀1 & 𝑀2 .
There are sufficient ingredients available to produce 20,000 bottles of 𝑀1 & 40,000 bottles of 𝑀2 . However,
there are only 45,000 bottles into which either of the medicines can be filled. Furthermore, it takes 3 hours to
prepare enough material to fill 1,000 bottles of 𝑀1 & 1 hour to prepare enough material to fill 1,000 bottles of
𝑀2 , with a total of 66 hours available for this operation. The profit margins are ₹8 per bottle of 𝑀1 & ₹7 per
bottle of 𝑀2 . Formulate the problem as a linear programming problem (LPP).
Solution:
Decision variables are:
𝑥1 = Number of bottles of 𝑀1
𝑥2 = Number of bottles of 𝑀2
The Objective function is
Maximize 𝒵 = 8𝑥1 + 7𝑥2 : total profit
Constraints
To produce bottles of 𝑀1 : 𝑥1 ≤ 20000
To produce bottles of 𝑀2 : 𝑥1 ≤ 40000
3 1
Time required to prepare bottles in hours: 𝑥1 + 𝑥2 ≤ 66
1000 1000
Total bottle into which medicines are filled: 𝑥1 + 𝑥2 ≤ 45000
Non negativity: 𝑥1 , 𝑥2 ≥ 0
Q: A factory manufactures two products A and B. To manufacture one unit of A, 1.5 machine hours & 2.5
machine hours are required. In a month 300 machine hours and 240 labour hours are available. To manufacture
product B 2.5 labour hours and 1.5 labour hours are required. Profit per unit for A is ₹50 and for B is ₹40.
Formulate as LPP.
Solution:
Decision variables are:
𝑥1 = Number of units of A manufactured
𝑥2 = Number of units of B manufactured
The Objective function is
Maximize 𝒵 = 50𝑥1 + 40𝑥2
Constraints
For machine hours: 1.5𝑥1 + 2.5𝑥2 ≤ 300
For labour hours: 2.5𝑥1 + 1.5𝑥2 ≤ 240
Non negativity: 𝑥1 , 𝑥2 ≥ 0
Portfolio Selection (Investment Decisions)
Q: An investor is considering investing in two securities A and B. The risk and return associated with these
securities is different. Security A gives a return of 9% and has a risk factor of 5 on a scale of 0 to 10. Security
, B gives a return of 15% but has a risk factor of 8. Total amount invested is ₹5,00,000. Total minimum return on
investment should be 12%. Maximum combined risk should be more than 6. Formulate the LPP.
Solution:
Decision variables are:
𝑥1 = Amount invested in A
𝑥2 = Amount invested in B
The Objective function is
Maximize 𝒵 = 0.09𝑥1 + 0.15𝑥2
Constraints
Related to total investment: 𝑥1 + 𝑥2 = 5,00,000
Related to return: 0.09𝑥1 + 0.15𝑥2 = 0.12 × 5,00,000 = 60,000
Related to Risk: 5𝑥1 + 8𝑥2 = 6 × 5,00,000 = 30,00,000
Non negativity: 𝑥1 , 𝑥2 ≥ 0
Inspection Problem
Q: In the context of quality control inspection, a company employs two grades of inspectors, Grade I and Grade
II. The task is to perform quality control inspections, with a requirement of inspecting at least 1,500 pieces in
an 8-hour workday. Grade I inspectors can examine 20 pieces per hour with an accuracy rate of 96%, while
Grade II inspectors can check 14 pieces per hour with an accuracy rate of 92%.
The company incurs different wages for these inspectors, with Grade I inspectors earning ₹5 per hour & Grade
II inspectors earning ₹4 per hour. Additionally, any inspection error by an inspector result in a cost of ₹3 to the
company. Given that the company employs 10 Grade I inspectors and 15 Grade II inspectors, the objective is to
determine the optimal assignment of inspectors to minimize the daily inspection cost.
Solution:
Hourly cost of a Grade I inspector: ₹(5 + 3 × 0.04 × 20) = ₹7.40
Hourly cost of a Grade II inspector: ₹(4 + 3 × 0.08 × 14) = ₹7.36
Decision variables are:
𝑥1 = Number of Grade I inspector
𝑥2 = Number of Grade II inspector
The Objective function is
Minimize 𝒵 = 7.40𝑥1 + 7.36𝑥2 : daily inspection cost
Constraints
Number of Grade I inspector: 𝑥1 ≤ 10
Number of Grade I inspector: 𝑥2 ≤ 15
Number of pieces Inspected daily: 160𝑥1 + 112𝑥2 ≥ 1500
Non negativity: 𝑥1 , 𝑥2 ≥ 0
Trim Loss Problem:
Q: A manufacturer of cylindrical containers receives tin sheets in widths of 30cm and 60cm. These sheets need
to be cut into three different widths of 15cm, 21cm, & 27cm to manufacture containers. The production plan
involves creating 400 containers of 15cm width, 200 containers of 21cm width, & 300 containers of 27cm width.
The manufacturer purchases bottom plates and top covers separately, and there are no limitations on the
lengths of standard tin sheets. The goal is to formulate a Linear Programming Problem (LPP) to determine the
production schedule that minimizes trim losses.
Solution:
Decision variables: Let 𝑥𝑖𝑗 represent the cutting combinations where each combination results in a
certain amount of trim loss.
Possible cutting combinations for both types of sheets are:
Width 30 cm 60 cm
𝑥11 𝑥12 𝑥13 𝑥21 𝑥22 𝑥23 𝑥24 𝑥25 𝑥26
15 2 0 0 4 2 2 1 0 0
21 0 1 0 0 1 0 2 1 0
27 0 0 1 0 0 1 0 1 2
Loss cm 0 9 3 0 9 3 3 12 6
