Linear Programming

Y = m.X + C … That’s all folks!!! 1

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025
History
 1947 - George B. Dantzig first used it in his paper “Programming in Linear Structure”
 1948 - Koopmans used the term “Linear Programming”
 1949 - Dantzig published the Simplex method to solve Linear Programming Problems

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 2
How to Formulate?
1. Study and analyse the given problem carefully.
2. Identify the decision variables of the problem.
3. Formulate the objective function in terms of the decision variables.
4. Formulate the constraints of the problem in terms of the decision variables.
5. Add the non-negativity constraints.

 If you found all the above formulas of the problem are linear equation / inequality, then
the problem is a Linear Programming Problem.

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 3
Example : Product Mix Problem
 A manufacturer makes two products A and B.
 Two resources R1 and R2 is required to make these products.
 1 unit of A is made from 1 unit of R1 and 3 units of R2.
 1 unit of B is made from 1 unit of R1 and 2 units of R2.
 Only 5 units of R1 and 12 units of R2 available.
 Profit of ₹6 is earned for one unit of product A.
 Profit of ₹5 is earned for one unit of product B.
 Manufacturer wants to produce A and B such that the profit is maximized.

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 4
1. Analyzing Problem

How
Whenmany
can A we
and
sellB Availability of the
How
Whatcan
is stopping
we earn Maximizing
ByAsselling
many asthe
the
should
the
What
Who
products
dowe
are
wemake
we?
want?
A and
to resources
After
Manufacturers!!
we make
R1 andit.
profit?
us? products
Possible
profit…
A and B
maximize
B? profit? R2

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 5
2. Identify Decision Variables
 What we need to decide?
 How many units of A and B needs to be manufactured.

 Let, X = units of A to be manufactured

 Let, Y = units of B to manufactured
 X and Y are the Decision Variables here

Decision Variables represents the decision

or output of the problem.

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 6
3. Formulate Objective
Function
 What is our objective?
 Maximize the profit

 How profit is defined?

 ₹6 for one unit of product A.
 ₹5 for one unit of product B.
 Therefore, overall profit, Z = 6.X + 5.Y

 Maximize Z = 6.X + 5.Y -- is our Objective Function

Represents the objective of making

the decisions

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 7
4. Formulate the Constraints
 What is stopping us from making A and B as many as possible?
 Availability of resources R1 and R2.

 How much R1 is available?

 5 units • Link up the resource requirement
 How much R1 is required to build one unit of A? with resource availability
 1 unit
 Therefore, how much R1 is required to build X units of A?
• Usually restricts the values that the
 X units decision variable can take
 How much R1 is required to build one unit of B?
 1 unit
 Therefore, how much R1 is required to build Y units of B?
 Y units

 Therefore, as per the availability of resource R1, X+Y≤5 -- Constraint Function

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 8
4. Formulate the Constraints
 How much R2 is available?
 12 units

 How much R2 is required to build one unit of A?

 3 units
 Therefore, how much R2 is required to build X units of A?
 3.X units

 How much R2 is required to build one unit of B?

 2 units
 Therefore, how much R2 is required to build Y units of B?
 2.Y units

 Therefore, as per the availability of resource R2, 3.X + 2.Y ≤ 12 (Constraint Function)

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 9
5. Add Non-negativity
Constraints
 Can you produce negative number of units of A?
 No
 Therefore, X ≥ 0

 Can you produce negative number of units of B?

 No
 Therefore, Y ≥ 0

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 10
Final LP Formulation
 Maximize Z = 6.X + 5.Y
subject to, X+Y≤5
3.X + 2.Y ≤ 12
X, Y ≥ 0

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 11
Example : Chemistry of Garden
 A person requires 10, 12, and 12 units of chemical A, B, C for his garden.
 A liquid product contains 5, 2 and 1 units of A, B, C respectively per jar.
 A dry product contains 1, 2 and 4 units of A, B, C respectively per carton.
 The liquid Product is sold for ₹3 per jar
 The dry product is sold for ₹2 per carton
 How many of Jars and Cartons should be purchased in order to minimize the cost and
meet requirements?

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 12
Solution
 Decision Variable
 Let X be the number of Jars to be purchased
1
 Let X be the number of Carton to be purchased
2

 Objective Function
 Min Z = 3.X + 2.X
1 2

 Constraints
 5.X + X ≥ 10 [ Requirement constraint for chemical A ]
1 2
 2.X + 2.X ≥ 12 [ Requirement constraint for chemical B ]
1 2
 X + 4.X ≥ 12 [ Requirement constraint for chemical C ]
1 2
 X,X ≥0 [ Non-Negativity Constraints]
1 2

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 13
Example : Reddy Mikks
Company
 Reddy Mikks produces both interior and exterior paints from two raw materials M1 and M2.

Tons of raw material per ton of Maximum availability

(in tons/day)
Exterior Paint Interior Paint

Raw Material, M1 6 4 24
Raw Material, M2 1 2 6
Profit per ton($1000) 5 4
 Market survey indicates that daily demand for interior paint cannot exceed that of exterior paint by
more than 1 ton.
 Maximum daily demand for interior paint is 2 tons.
 Determine best product mix of interior and exterior paint that maximizes total daily profit.
Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 14
Solution
 Decision Variable
 Let X be the number of Exterior paints
1
 Let X be the number of Interior paints
2

 Objective Function
 max Z = 5.X + 4.X
1 2

 Constraints
 6.X + 4.X ≤ 24 [ Availability constraint for raw material M1 ]
1 2
 X + 2.X ≤ 6 [ Availability constraint for raw material M2 ]
1 2
 X –X ≤1 [ Demand constraint for Interior & Exterior Paint ]
2 1
 X ≤2 [ Demand constraint for Interior paint ]
2
 X,X ≥0 [ Non-Negativity Constraints]
1 2

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 15
Example : Farming Vegetables
 A farmer has 100 acres farm.
 He can sell tomatoes, lettuce or radish for ₹1/kg, ₹0.75/head and ₹2/kg respectively.
 Average yield per acre is 2000 Kgs, 3000 heads and 1000 Kgs for tomatoes, lettuce
or radish respectively
 Fertilizer are available at ₹0.50/Kg
 Amount of fertilizer required per acre 100 Kgs/acre for both tomatoes and lettuce and
50 Kgs/acre for radish.
 Labour required for farming is 5 man-days/acre for tomatoes and radish, and 6 man-
days/acre for lettuce
 A total of 400 man-days are available at ₹20 / man-day
 Determine farming area for each vegetables to maximize farmer’s profit.
Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 16
Solution
 Decision variables
 Let X be the acres for farming tomatoes.
1
 Let X be the acres for farming lettuce.
2
 Let X be the acres for farming radish.
3

 Objective Function
 Profit = Income – Expenditure
= (1 x 2000).X1 + (0.75 x 3000).X2 + (2 x 1000).X3
- ((0.50 x 100).X1 + (0.50 x 100).X2 + (0.50 x 50).X3) [for fertilizer]
- ((20 x 5).X1 + (20 x 6).X2 + (20 x 5).X3) [for labour]
=1850.X1 + 2080.X2 + 1875.X3
 Max Z = 1850.X + 2080.X + 1875.X
1 2 3

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 17
Solution
 Constraints
 X + X + X ≤ 100 [Land Availability Constraint]
1 2 3
 5.X + 6.X + 5.X ≤ 400 [Man-power Availability Constraint]
1 2 3
 X,X,X ≥0 [Non-Negativity Constraint]
1 2 3

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 18
Properties of LP Model
 Proportionality
 Contribution of all decision variables has to be directly proportional to the value of the
variables in both the objective functions and constraints.
 Additivity
 Total contribution of all the variables in both the objective function and constraints has to be
the sum of individual contributions of all the decision variables
 Certainty
 All the coefficients of the objective function and constraints of LP model are deterministic.

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 19
General Formulation of LPP
 If there are n decision variables and m constraints, the generalized formulation of LPP
looks like –
 Min or Max Z = c x + c x + … + c x =
1 1 2 2 n n

 Subject to,
a11x1 + a12x2 + … +a1nxn ( ≤ = ≥ ) b1
a21x1 + a22x2 + … +a2nxn ( ≤ = ≥ ) b2
:
:
am1x1 + am2x2 + … +amnxn ( ≤ = ≥ ) bm

x1, x2, …, xn ≥ 0

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 20
Matrix Form of LPP
 If there are n decision variables and m constraints, the generalized formulation of LPP
looks like –
 Min or Max Z = C.X
 Subject to,
A.X ( ≤ = ≥ ) B
X≥0
 Where,

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 21
Summary
 To formulate linear programming problem, we first need to determine the decision
variables.
 Then we need to represent the objective function in terms of those decision variables.
 After that, we need to represent the constraints using those decision variables.
 And, finally have to add those non-negativity constraints.
 LP models holds the property of Proportionality, Additivity and certainty.
 LP models can be represented in matrix format.

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 22
Thank You!

Preetam K Sur, Assistant Professor, Computer Science & Engineering Department, GCETTS September 6, 2025 23