Page 1 of 20

UNIT 5
LINEAR PROGRAMMING PROBLEMS (10 MARKS)
Topic Content:
5.1 Introduction, Basic terms in Linear Programming Problems.
MR SUDHIR S DESAI
5.2 Mathematical formulation of Linear Programming Problems.

5.3 Method of solving Linear Programming Problems (Two equations in two variables): Graphical
(corner point) method, Simplex method.

Course Outcome: After completion of this course, students will be able to

CO5: Apply the linear programming problem concept to obtain optimal solution.

 Introduction.

In Mathematics, linear programming is a method of optimising operations with some constraints.

The main objective of linear programming is to maximize or minimize the numerical value. It consists
of linear functions which are subjected to the constraints in the form of linear equations or in the form of
inequalities. Linear programming is considered an important technique that is used to find the optimum
resource utilisation. The term “linear programming” consists of two words as linear and programming. The
word “linear” defines the relationship between multiple variables with degree one. The word
“programming” defines the process of selecting the best solution from various alternatives.

Linear Programming is widely used in Mathematics and some other fields such as economics,
business, telecommunication, and manufacturing fields. In this article, let us discuss the definition of linear
programming, its components, and different methods to solve linear programming problems.

 Formation of LPP:
STEP I: Define the decision variables.
STEP II: Construct the objective function which has to be optimized as a linear equation involving decision
variables.
STEP III: Express every condition as a linear inequality involving decision variables.

MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING

 Page 2 of 20
 Example:
1. A company manufactures two types of toys A and B. Each type of toy A requires 2 minutes for cutting
and 1 min for assembling. Each type of toy B requires 3 min for cutting and 4 minutes for assembling.
There are 3 hrs. for cutting and 2 hrs. for assembling. On selling a toy of type A the company gets
profit of Rs. 10 and that on toy B is Rs. 20. Formulate the LPP to maximize profit. [Summer-24] 2M
Sol: Let us prepare first table of given data.
Toy A Toy B Availability/Limitations
Cutting 2 1 3
Assembling 3 4 2
Profit 10 20
STEP I: Consider company manufactures 𝑥1 number of toys A & 𝑥2 number of toys B
Total profit on selling toys A is 10𝑥1
Total profit on selling toys B is 20𝑥2
STEP II: Maximum profit 𝑍 = 10𝑥1 + 20𝑥2
STEP III: Subjected to
2𝑥1 + 𝑥2 ≤ 3
3𝑥1 + 4𝑥2 ≤ 2
𝑥1 , 𝑥2 ≥ 0

2. A company manufactures two products 𝑷𝟏 & 𝑷𝟐 . Product 𝑷𝟏 required 5 units & 𝑷𝟐 requires 6 units of
electronic components. The supply of electronics components is limited to 600 units per day, labour
supply is limited 160 man day. one unit of product 𝑷𝟏 requires 1 man day of labour and one unit of 𝑷𝟐
requires 2 man days of labour. Formulate the LPP to produce maximum profit. Profit earns is 50 Rs.
From 𝑷𝟏 & 80 Rs. From one unit of 𝑷𝟐 .
Sol: Let us prepare first table of given data.
Product 𝑷𝟏 Product 𝑷𝟐 Availability/Limitations
Electronic Components 5 6 600
Labour 1 2 160
Profit 50 80
STEP I: Consider company manufactures 𝑥1 number of product 𝑃1 & 𝑥2 number of product 𝑃2
Total profit on selling product 𝑃1 is 50𝑥1
Total profit on selling product 𝑃2 is 80𝑥2
STEP II: Maximum profit 𝑍 = 50𝑥1 + 80𝑥2
STEP III: Subjected to
5𝑥1 + 6𝑥2 ≤ 600
𝑥1 + 2𝑥2 ≤ 160
𝑥1 , 𝑥2 ≥ 0
MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING
 Page 3 of 20
3. A furniture dealer deals only two items, like table & chairs. He has to invest Rs. 10,000 |- & a space to
store at most 60 pieces. A table cost him Rs. 500 & a chair cost him Rs. 200. He can sell all the items
that he buys. He is getting a profit of Rs. 50 per table & Rs. 15 per chair. Formulate this problem as an
LPP, so as to maximize the profit.
Sol: Let us prepare first table of given data.
Table Chairs Availability/Limitations
Space 60
Cost 500 200 10,000
Profit 50 15

STEP I: Consider furniture dealer manufactures 𝑥1 number of tables & 𝑥2 number of chairs.
Total profit on selling tables is 50𝑥1
Total profit on selling chairs is 15𝑥2
STEP II: Maximum profit 𝑍 = 50𝑥1 + 15𝑥2
STEP III: Subjected to
𝑥1 + 𝑥2 ≤ 60
500𝑥1 + 200𝑥2 ≤ 10000
𝑥1 , 𝑥2 ≥ 0

MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING

 Page 4 of 20
UNIT 5
LINEAR PROGRAMMING PROBLEMS (10 MARKS)
Topic Content:
5.1 Introduction, Basic terms in Linear Programming Problems.
MR SUDHIR S DESAI
5.2 Mathematical formulation of Linear Programming Problems.

5.3 Method of solving Linear Programming Problems (Two equations in two variables): Graphical
(corner point) method, Simplex method.

Course Outcome: After completion of this course, students will be able to

CO4: Apply the linear programming problem concept to obtain optimal solution.

 Introduction.

In Mathematics, linear programming is a method of optimising operations with some constraints.

The main objective of linear programming is to maximize or minimize the numerical value. It consists
of linear functions which are subjected to the constraints in the form of linear equations or in the form of
inequalities. Linear programming is considered an important technique that is used to find the optimum
resource utilisation. The term “linear programming” consists of two words as linear and programming. The
word “linear” defines the relationship between multiple variables with degree one. The word
“programming” defines the process of selecting the best solution from various alternatives.

Linear Programming is widely used in Mathematics and some other fields such as economics,
business, telecommunication, and manufacturing fields. In this article, let us discuss the definition of linear
programming, its components, and different methods to solve linear programming problems.

 Definition:

It is a process of finding the optimal value (Maximum or Minimum) of a linear function (Objective
function) of some variables, subject to linear constraints (equalities/inequalities)

 Graphical Method (Corner Method): 6M

The graphical method is used to optimize the two-variable linear programming. If the problem has
two decision variables, a graphical method is the best method to find the optimal solution. In this method,
the set of inequalities are subjected to constraints. Then the inequalities are plotted in the 𝑋𝑌 plane. Once,
all the inequalities are plotted in the XY graph, the intersecting region will help to decide the feasible region.
The feasible region will provide the optimal solution as well as explains what all values our model can
take. Let us see an example here and understand the concept of linear programming in a better way.
STEP I: Write all inequality constraints in the form of equations.
STEP II: Plot these lines on a graph by identifying test points.
STEP III: Identify the feasible region.
STEP IV: Determine the coordinates of the corner points.
STEP V: Substitute each corner point in the objective function to find optimal solution.

MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING

 Page 5 of 20
 Example:
4. Solve the following LPP using graphical method :
Maximize 𝒁 = 𝟏𝟏𝒙 + 𝟖𝒚
Subject to 𝒙 ≤ 𝟒, 𝒚 ≤ 𝟔, 𝒙 + 𝒚 ≤ 𝟔, 𝒙 ≥ 𝟎, 𝒚 ≥ 𝟎. [summer 24 – 6M]
Sol: Given, Maximize 𝑍 = 11𝑥 + 8𝑦 … … … . (1)
Subject to 𝑥 ≤ 4, 𝑦 ≤ 6, 𝑥 + 𝑦 ≤ 6, 𝑥 ≥ 0, 𝑦 ≥ 0.
STEP I:
𝑥 = 4, 𝑦 = 6, 𝑥 + 𝑦 = 6
STEP II:
𝑥 = 4 Is a straight line passing through (4,0) & parallel to 𝑦 − 𝑎𝑥𝑖𝑠.
𝑦 = 6 Is a straight line passing through (0,6) & parallel to 𝑥 − 𝑎𝑥𝑖𝑠.
𝑥 = 0, 𝑦 − 𝑎𝑥𝑖𝑠
𝑦 = 0, 𝑥 − 𝑎𝑥𝑖𝑠
For 𝑥 + 𝑦 = 6
𝑥 0 6
𝑦 6 0

𝑦 − 𝑎𝑥𝑖𝑠

𝑥≤4
𝑦≤6 𝐴(0,6)

𝐵(4,2)

𝑂 𝐶(4,0) 𝑥 − 𝑎𝑥𝑖𝑠

𝑥+𝑦 ≤6

To find intersection point B

Solving equations 𝑥 = 4 … … . . (1) & 𝑥 + 𝑦 = 6 … . . (2)
Put 𝑥 = 4 in equation 2)
∴4+𝑦 =6→𝑦 =6−4→ 𝑦 =2
The coordinates of point 𝐵(4,2)
STEP III: Feasible region is 𝑂𝐴𝐵𝐶
STEP IV: To find Z at corner points.
Corner Points 𝒁 = 𝟏𝟏𝒙 + 𝟖𝒚
𝑂(0,0) ∴ 𝑍 = 11(0) + 8(0) = 0
𝐴(0,6) ∴ 𝑍 = 11(0) + 8(6) = 48
MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING
 Page 6 of 20
𝑩(𝟒, 𝟐) ∴ 𝒁 = 𝟏𝟏(𝟒) + 𝟖(𝟐) = 𝟔𝟎
𝐶(4,0) ∴ 𝑍 = 11(4) + 8(0) = 44
STEP V: Hence we find that 𝑍 is maximum at point 𝐵(4,2) & Maximum value is 𝑍 = 60

5. Solve the following Linear Programming Problem graphically to find optimal solution:
Maximize 𝒁 = 𝟐𝒙 + 𝟓𝒚
Subject to 𝒙 + 𝟐𝒚 ≤ 𝟏𝟔, 𝟓𝐱 + 𝟑𝐲 ≤ 𝟒𝟓, 𝒙 ≥ 𝟎, 𝒚 ≥ 𝟎. [summer 23 - 6M]
Sol: Given, Maximize 𝑍 = 2𝑥 + 5𝑦 … … … . (1)
Subject to 𝑥 + 2𝑦 ≤ 16, 5𝑥 + 3𝑦 ≤ 45, 𝑥 ≥ 0, 𝑦 ≥ 0.
STEP I:
𝑥 + 2𝑦 = 16, 5𝑥 + 3𝑦 = 45, 𝑥 = 0, 𝑦 = 0.
STEP II:
𝑥 = 0, 𝑦 − 𝑎𝑥𝑖𝑠
𝑦 = 0, 𝑥 − 𝑎𝑥𝑖𝑠
For 𝑥 + 2𝑦 = 16
𝑥 0 16
𝑦 8 0
For 5𝑥 + 3𝑦 = 45
𝑥 0 9
𝑦 15 0

𝑦 − 𝑎𝑥𝑖𝑠

(0,15)

𝐴(0,8)
𝐵(6,5)

𝑂 𝐶(9,0) (16,0) 𝑥 − 𝑎𝑥𝑖𝑠

𝑥 + 2𝑦 ≤ 16

5𝑥 + 3𝑦 ≤ 45

To find intersection point B

Solving equations 𝑥 + 2𝑦 = 16 → 𝑥 = 16 − 2𝑦 … … . . (1) & 5𝑥 + 3𝑦 = 45 … . . (2)

Put 𝑥 = 16 − 2𝑦 in equation 2)
∴ 5(16 − 2𝑦) + 3𝑦 = 45
∴ 80 − 10𝑦 + 3𝑦 = 45

MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING

 Page 7 of 20
−35
∴ −7𝑦 = 45 − 80 → −7𝑦 = −35 → 𝑦 = ∴𝑦=5
−7
Put 𝑦 = 5 in equation 1)
𝑥 = 16 − 2(5) → 𝑥 = 16 − 10 ∴ 𝑥 = 6
The coordinates of point 𝐵(6,5)
STEP III: Feasible region is 𝑂𝐴𝐵𝐶
STEP IV: To find Z at corner points.
Corner Points 𝒁 = 𝟐𝒙 + 𝟓𝒚
𝑂(0,0) ∴ 𝑍 = 2(0) + 5(0) = 0
𝑨(𝟎, 𝟖) ∴ 𝒁 = 𝟐(𝟎) + 𝟓(𝟖) = 𝟒𝟎
𝐵(6,5) ∴ 𝑍 = 2(6) + 5(5) = 37
𝐶(9,0) ∴ 𝑍 = 2(9) + 5(0) = 18
STEP V: Hence we find that Z is maximum at point 𝐴(0,8) & Maximum value is 𝑍 = 40

6. Solve the following Linear Programming Problem graphically to find optimal solution:
Maximize 𝒁 = 𝟓𝒙 + 𝟑𝒚
Subject to 𝟑𝒙 + 𝟓𝒚 ≤ 𝟏𝟓, 𝟓𝐱 + 𝟐𝐲 ≤ 𝟏𝟎, 𝒙 ≥ 𝟎, 𝒚 ≥ 𝟎. [winter 23 - 6M]
Sol: Given, Maximize 𝑍 = 5𝑥 + 3𝑦 … … … . (1)
Subject to 3𝑥 + 5𝑦 ≤ 15, 5x + 2y ≤ 10, 𝑥 ≥ 0, 𝑦 ≥ 0.
STEP I:
3𝑥 + 5𝑦 = 15, 5x + 2y = 10, 𝑥 = 0, 𝑦 = 0.
STEP II:
𝑥 = 0, 𝑦 − 𝑎𝑥𝑖𝑠
𝑦 = 0, 𝑥 − 𝑎𝑥𝑖𝑠
For 3𝑥 + 5𝑦 = 15
𝑥 0 5
𝑦 3 0
For 5𝑥 + 2𝑦 = 10
𝑥 0 2
𝑦 5 0
𝑦 − 𝑎𝑥𝑖𝑠

(0,5)
20 45
𝐵 ,
𝐴(0,3) 19 19

𝑂 𝐶(2,0) (5,0) 𝑥 − 𝑎𝑥𝑖𝑠

5𝑥 + 2𝑦 ≤ 10 3𝑥 + 5𝑦 ≤ 15

MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING

 Page 8 of 20
To find intersection point B
15−5𝑦 5
Solving equations 3𝑥 + 5𝑦 = 15 → 𝑥 = → 𝑥 = 5 − 𝑦 … … . . (1) & 5𝑥 + 2𝑦 = 10 … . . (2)
3 3
5
Put 𝑥 = 5 − 3 𝑦 in equation 2)
5
∴ 5 5 − 𝑦 + 2𝑦 = 10
3
25
∴ 25 − 𝑦 + 2𝑦 = 10
3
19 19 3 45
∴ − 𝑦 = 10 − 25 → − 𝑦 = −15 → 𝑦 = −15 × − ∴𝑦=
3 3 19 19
45
Put 𝑦 = in equation 1)
19
5 45 20
∴𝑥 =5− × ∴ 𝑥=
3 19 19
20 45
The coordinates of point 𝐵 (19 , 19)
STEP III: Feasible region is 𝑂𝐴𝐵𝐶
STEP IV: To find Z at corner points.

Corner Points 𝒁 = 𝟓𝒙 + 𝟑𝒚
𝑂(0,0) ∴ 𝑍 = 5(0) + 3(0) = 0
𝐴(0,3) ∴ 𝑍 = 5(0) + 3(3) = 9
𝟐𝟎 𝟒𝟓 𝟐𝟎 𝟒𝟓
𝑩 , ∴𝒁=𝟓 +𝟑 = 𝟏𝟐. 𝟑𝟔𝟖𝟒
𝟏𝟗 𝟏𝟗 𝟏𝟗 𝟏𝟗
𝐶(2,0) ∴ 𝑍 = 2(2) + 5(0) = 4

20 45
STEP V: Hence we find that 𝑍 is maximum at point 𝐵 ( , )& Maximum value is 𝑍 = 12.3684
19 19

 Homework:
1. Calculate the maximal and minimal value of 𝒛 = 𝟓𝒙 + 𝟑𝒚 for the following constraints graphically.
𝒙 + 𝟐𝒚 ≤ 𝟏𝟒, 𝟑𝒙 – 𝒚 ≥ 𝟎, 𝒙 – 𝒚 ≤ 𝟐, 𝒙 ≥ 𝟎, 𝒚 ≥ 𝟎
Ans: Max 𝒛 = 𝟒𝟐 at (𝟔, 𝟒) & Min 𝒛 = −𝟏𝟒 at (−𝟏, −𝟑)
2. Solve the following Linear Programming Problem graphically to find optimal solution:
Maximize 𝒁 = 𝟐𝒙𝟏 + 𝟓𝒙𝟐
Subject to 𝒙𝟏 + 𝟒𝒙𝟐 ≤ 𝟐, 𝟑𝒙𝟏 + 𝒙𝟐 ≤ 𝟐𝟏, 𝒙𝟏 + 𝒙𝟐 ≤ 𝟗, 𝒙𝟏 ≥ 𝟎, 𝒙𝟐 ≥ 𝟎. Ans: Max 𝒛 = 𝟑𝟑 at (𝟒, 𝟓)
3. Solve the following Linear Programming Problem graphically to find optimal solution:
Minimize 𝒁 = 𝟓𝒙𝟏 + 𝟒𝒙𝟐
Subject to 𝟒𝒙𝟏 + 𝟒𝒙𝟐 ≥ 𝟒𝟎, 2𝒙𝟏 + 𝟑𝒙𝟐 ≥ 𝟗𝟎, 𝒙𝟏 ≥ 𝟎, 𝒙𝟐 ≥ 𝟎. Ans: Min 𝒛 = 𝟏𝟐𝟕 at (𝟑, 𝟐𝟖)
4. Solve the following Linear Programming Problem graphically to find optimal solution:
Maximize 𝒁 = 𝟐𝒙𝟏 + 𝟑𝒙𝟐
Subject to 𝒙𝟏 + 𝒙𝟐 ≤ 𝟑𝟎, 𝒙𝟏 ≤ 𝟐𝟎, 𝒙𝟐 ≤ 𝟏𝟐, 𝒙𝟏 ≥ 𝟎, 𝒙𝟐 ≥ 𝟎.

MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING

 Page 9 of 20
UNIT 5
LINEAR PROGRAMMING PROBLEMS (10 MARKS)
Topic Content:
5.1 Introduction, Basic terms in Linear Programming Problems.
MR SUDHIR S DESAI
5.2 Mathematical formulation of Linear Programming Problems.

5.3 Method of solving Linear Programming Problems (Two equations in two variables): Graphical
(corner point) method, Simplex method.

Course Outcome: After completion of this course, students will be able to

CO5: Apply the linear programming problem concept to obtain optimal solution.

 Introduction.
Simplex method also called simplex technique or simplex algorithm was developed by G.B.
Dantzig, An American mathematician. Simplex method is suitable for solving linear programming
problems with a large number of variables. The method through an iterative process progressively
approaches and ultimately reaches to the maximum or minimum values of the objective function.

 Procedure to find Maximum value using Simplex Method:

STEP 1) Write objective function & constraints by adding basic (slack) variables (𝒙𝟑 &𝒙𝟒 )
STEP 2) Construct an initial simplex table as follows.
Min Ratio
𝑪𝒋 Coefficient of variables in Z 𝒃
𝒙𝒊

𝑪𝒃 𝑿𝒃 𝒃 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒

Coeff of Const.
𝒙𝟑 Coefficient of variables in equation 1
𝒙𝟑 in z on RHS 1
Coeff of Const.
𝒙𝟒 Coefficient of variables in equation 2
𝒙𝟒 in z on RHS 2

∑[𝑪𝒃 × 𝒙𝒊 ] = 𝒁𝒋

𝒁𝒋 − 𝑪𝒋

STEP 3) Find the entering variable whose coefficient in 𝒁𝒋 − 𝑪𝒋 row is most negative
STEP 4) Find the exit variable i.e. the basic variable in the row where the min ratio is small as possible.
(non negative).
STEP 5) Find the Key Element at the intersection of the entering variable column the exit variable row.
STEP 6) Make key element one by dividing the row by Key element
STEP 7) Now make element above or below Key element zero & construct new table
STEP 8) Repeat the steps form 2) to 7) until you get all 𝒁𝒋 − 𝑪𝒋 ≥ 𝟎.
STEP 9) Find value of 𝒙𝟏 & 𝒙𝟐 from final table & put in Z to find optimal solution.
MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING
 Page 10 of 20
 Example:
7. Solve the following Linear programming problem using Simplex method to find optimal solution:
Maximize 𝒁 = 𝟑𝒙𝟏 + 𝟒𝒙𝟐
Subject to 𝒙𝟏 + 𝒙𝟐 ≤ 𝟒𝟓𝟎, 𝟐𝒙𝟏 + 𝒙𝟐 ≤ 𝟔𝟎𝟎, 𝒙𝟏 ≥ 𝟎, 𝒙𝟐 ≥ 𝟎. [winter 23 – 6M]
Sol: Consider,
𝑍 = 3𝑥1 + 4𝑥2 + 0𝒙𝟑 + 0𝒙𝟒
𝑥1 + 𝑥2 + 𝒙𝟑 + 0𝒙𝟒 = 450
2𝑥1 + 𝑥2 + 0𝒙𝟑 + 𝒙𝟒 = 600 Key Element
Table 1:
Min Ratio
𝑪𝒋 3 4 0 0 𝒃
𝒙𝟐

𝑪𝒃 𝑿𝒃 𝒃 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒
𝟒𝟓𝟎
0 𝒙𝟑 450 1 𝟏 1 0 = 𝟒𝟓𝟎 Exit Variable
𝟏
600
0 𝒙𝟒 600 2 1 0 1 = 600
1

∑[𝑪𝒃 × 𝒙𝒊 ] = 𝒁𝒋 0 0 0 0
𝒁𝒋 − 𝑪𝒋 -3 -4 0 0

Here, key element is already one Enter Variable

To make element below key element equal to zero.
Old line – New line
600 – 450 150

2–1 1

1–1 0
0–1 -1

1–0 1

Table 2:
𝑪𝒋 3 4 0 0
𝑪𝒃 𝑿𝒃 𝒃 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒

4 𝑥2 450 1 1 1 0

0 𝑥4 150 1 0 -1 1

∑[𝑪𝒃 × 𝒙𝒊 ] = 𝒁𝒋 4 4 4 0

𝒁𝒋 − 𝑪𝒋 1 0 4 0

Here all 𝒁𝒋 − 𝑪𝒋 ≥ 𝟎 ∴ 𝒙𝟏 = 𝟎, 𝒙𝟐 = 𝟒𝟓𝟎

The maximum value of 𝑍 = 3(0) + 4(450)
∴ 𝒁 = 𝟏𝟖𝟎𝟎

MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING

 Page 11 of 20
8. Solve the following Linear programming problem using Simplex method to find optimal solution:
Maximize 𝒁 = 𝟏𝟐𝒙𝟏 + 𝟏𝟔𝒙𝟐
Subject to 𝟏𝟎𝒙𝟏 + 𝟐𝟎𝒙𝟐 ≤ 𝟏𝟐𝟎, 𝟖𝒙𝟏 + 𝟖𝒙𝟐 ≤ 𝟖𝟎, 𝒙𝟏 ≥ 𝟎, 𝒙𝟐 ≥ 𝟎. [summer 23 – 6M]
Sol: Consider,
𝑍 = 12𝑥1 + 16𝑥2 + 0𝒙𝟑 + 0𝒙𝟒
10𝑥1 + 20𝑥2 + 𝒙𝟑 + 0𝒙𝟒 = 120 Key Element
8𝑥1 + 8𝑥2 + 0𝒙𝟑 + 𝒙𝟒 = 80
Table 1:
𝑪𝒋 12 16 0 0 Min Ratio
𝒃
𝑪𝒃 𝑿𝒃 𝒃 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟐
𝟏𝟐𝟎
0 𝒙𝟑 120 10 𝟐𝟎 1 0 =𝟔 Exit Variable
𝟐𝟎
80
0 𝒙𝟒 80 8 8 0 1 = 10
8

∑[𝑪𝒃 × 𝒙𝒊 ] = 𝒁𝒋 0 0 0 0
𝒁𝒋 − 𝑪𝒋 -12 -16 0 0
Enter Variable
Here, key element is 20
So make it one by dividing each element by 20
To make element below key element equal to zero.
Old line – 8 x New line
80 – 8 x 6 32
1 4
8–8x2

8–8x1 0
1 2
0–8x −
20 5
1–8x0 1

Key Element
Table 2:
𝑪𝒋 12 16 0 0 Min Ratio
𝒃
𝑪𝒃 𝑿𝒃 𝒃 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟏
𝟔
1 1 = 𝟏𝟐
16 𝑥2 6 1 0 𝟏⁄
2 20 𝟐
2 𝟑𝟐
0 𝒙𝟒 32 𝟒 0 − 1 =𝟖
5 𝟒 Exit Variable
4
∑[𝑪𝒃 × 𝒙𝒊 ] = 𝒁𝒋 8 16 0
5
0 4
𝒁𝒋 − 𝑪𝒋 -4 0
5
Enter Variable
Here, key element is 4
So, make it one by dividing each element by 4
To make element above key element equal to zero.

MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING

 Page 12 of 20
𝟏
Old line – 𝟐
x New line
1 2
6– x8
2
1 1 0
– x1
2 2
1 1
1–2x0
1 1 1 1
– 2 x−
20 10 10
1 1 −1
0–2x4 8
Table 3:
𝑪𝒋 12 16 0 0
𝑪𝒃 𝑿𝒃 𝒃 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒
1 −1
16 𝑥2 2 0 1 8
10
1 1
12 𝑥1 8 1 0 − 4
10
2 1
∑[𝑪𝒃 × 𝒙𝒊 ] = 𝒁𝒋 12 16
5
2 1
𝒁𝒋 − 𝑪𝒋 0 0
5
Here all 𝒁𝒋 − 𝑪𝒋 ≥ 𝟎 ∴ 𝒙𝟏 = 𝟖, 𝒙𝟐 = 𝟐
The maximum value of 𝑍 = 12(8) + 16(2)
∴ 𝒁 = 𝟏𝟐𝟖

9. Solve the following Linear programming problem using Simplex method to find optimal solution:
Maximize 𝒁 = 𝟓𝒙𝟏 + 𝟑𝒙𝟐
Subject to 𝟑𝒙𝟏 + 𝟓𝒙𝟐 ≤ 𝟏𝟓, 𝟓𝒙𝟏 + 𝟐𝒙𝟐 ≤ 𝟏𝟎, 𝒙𝟏 ≥ 𝟎, 𝒙𝟐 ≥ 𝟎.
Sol: Consider,
𝑍 = 5𝑥1 + 3𝑥2 + 0𝒙𝟑 + 0𝒙𝟒
3𝑥1 + 5𝑥2 + 𝒙𝟑 + 0𝒙𝟒 = 15
5𝑥1 + 2𝑥2 + 0𝒙𝟑 + 𝒙𝟒 = 10 Key Element
Table 1:
𝑪𝒋 5 3 0 0 Min Ratio
𝒃
𝑪𝒃 𝑿𝒃 𝒃 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟏
15
0 𝒙𝟑 15 3 5 1 0 =5
3
10
0 𝒙𝟒 10 𝟓 2 0 1 =𝟐 Exit Variable
5

∑[𝑪𝒃 × 𝒙𝒊 ] = 𝒁𝒋 0 0 0 0
𝒁𝒋 − 𝑪𝒋 -5 -3 0 0

Enter Variable
Here, key element is 5
So make it one by dividing each element by 5
To make element above key element equal to zero.
MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING
 Page 13 of 20
Old line – 3 x New line
15 – 3 x 2 9

3–3x1 0

2 19
5–3x 5
5

1–3x0 1
1 −3
0–3x 5
5

Key Element
Table 2:
𝑪𝒋 5 3 0 0 Min Ratio
𝒃
𝑪𝒃 𝑿𝒃 𝒃 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟐
5 45
𝟏𝟗 3 9× =
0 𝒙𝟑 9 0 1 − 19 19 Exit Variable
𝟓 5 = 𝟐. 𝟑𝟕
2 1 5
5 𝒙𝟏 2 1 0 2× =5
5 5 2

∑[𝑪𝒃 × 𝒙𝒊 ] = 𝒁𝒋 5 2 0 1
𝒁𝒋 − 𝑪𝒋 0 -1 0 1
19
Here, key element is
5 Enter Variable
5
So make it one by multiplying each element by 19
To make element below key element equal to zero.
𝟐
Old line – 𝟓 x New line
2 45 20
2− × 19
5 19
2
1− ×0 1
5
2 2
− ×1 0
5 5
2 5 2
0− × −
5 19 19
1 2 −3 5
− ×
5 5 19 19
Table 3:
𝑪𝒋 5 3 0 0
𝑪𝒃 𝑿𝒃 𝒃 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒
45 5 3
3 𝒙𝟐 0 1 −
19 19 19
20 2 5
5 𝒙𝟏 1 0 − 19
19 19
5 16
∑[𝑪𝒃 × 𝒙𝒊 ] = 𝒁𝒋 5 3 19
19
5 16
𝒁𝒋 − 𝑪𝒋 0 0 19
19
MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING
 Page 14 of 20
𝟐𝟎 𝟒𝟓
Here all 𝒁𝒋 − 𝑪𝒋 ≥ 𝟎 ∴ 𝒙𝟏 = 𝟏𝟗 , 𝒙𝟐 = 𝟏𝟗
𝟐𝟎 𝟒𝟓
The maximum value of 𝑍 = 5 (𝟏𝟗) + 3 (𝟏𝟗)
∴ 𝒁 = 𝟏𝟐. 𝟑𝟔𝟖𝟒

 Homework:
1. Find solution using Simplex method. (not in syllabus but you can try)
Maximize 𝒁 = 𝟑𝟎𝒙𝟏 + 𝟒𝟎𝒙𝟐
Subject to 𝟑𝒙𝟏 + 𝟐𝒙𝟐 ≤ 𝟔𝟎𝟎, 𝟑𝒙𝟏 + 𝟓𝒙𝟐 ≤ 𝟖𝟎𝟎, 𝟓𝒙𝟏 + 𝟔𝒙𝟐 ≤ 𝟏𝟏𝟎𝟎 𝒙𝟏 ≥ 𝟎, 𝒙𝟐 ≥ 𝟎.
[Ans: 𝒙𝟏 = 𝟏𝟎𝟎, 𝒙𝟐 = 𝟏𝟎𝟎, 𝐌𝐚𝐱 𝒛 = 𝟕𝟎𝟎𝟎]
2. Find solution using Simplex method.
Maximize 𝒁 = 𝟒𝟎𝒙𝟏 + 𝟑𝟎𝒙𝟐
Subject to 𝒙𝟏 + 𝒙𝟐 ≤ 𝟏𝟐, 𝟐𝒙𝟏 + 𝒙𝟐 ≤ 𝟏𝟔, 𝒙𝟏 ≥ 𝟎, 𝒙𝟐 ≥ 𝟎.
[Ans: 𝒙𝟏 = 𝟒, 𝒙𝟐 = 𝟖, 𝐌𝐚𝐱 𝒛 = 𝟒𝟎𝟎]
3. Find solution using Simplex method.
Maximize 𝒁 = 𝟑𝒙𝟏 + 𝟐𝒙𝟐
Subject to 𝒙𝟏 + 𝒙𝟐 ≤ 𝟒, 𝒙𝟏 + 𝟑𝒙𝟐 ≤ 𝟔, 𝒙𝟏 ≥ 𝟎, 𝒙𝟐 ≥ 𝟎.
[Ans: 𝒙𝟏 = 𝟑, 𝒙𝟐 = 𝟏, 𝐌𝐚𝐱 𝒛 = 𝟏𝟑]

MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING

 Page 15 of 20
UNIT 5
LINEAR PROGRAMMING PROBLEMS (10 MARKS)
Topic Content:
5.1 Introduction, Basic terms in Linear Programming Problems.
MR SUDHIR S DESAI
5.2 Mathematical formulation of Linear Programming Problems.

5.3 Method of solving Linear Programming Problems (Two equations in two variables): Graphical
(corner point) method, Simplex method Big M Method.

Course Outcome: After completion of this course, students will be able to

CO5: Apply the linear programming problem concept to obtain optimal solution.

 Procedure to find Maximum value using Simplex Method:

STEP 1) Write minimization problem as 𝑴𝒂𝒙𝒊𝒎𝒊𝒛𝒆 𝒛’ = −𝑴𝒊𝒏 𝒛
STEP 2) Write objective function & constraints by subtracting surplus variables (𝒙𝟑 & 𝒙𝟒 ) and adding
artificial variables (𝑨𝟏 & 𝑨𝟐 )
STEP 3) Construct an initial simplex table as follows.
Min Ratio
𝑪𝒋 Coefficient of variables in Z 𝒃
𝒙𝒊

𝑪𝒃 𝑿𝒃 𝒃 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝑨𝟏 𝑨𝟐
Coeff Const.
of 𝑨𝟏 on RHS Coefficient of variables in equation 1
𝑨𝟏 in z 1
Coeff Const.
of 𝑨𝟐 on RHS Coefficient of variables in equation 2
𝑨𝟐 in z 2

∑[𝑪𝒃 × 𝒙𝒊 ] = 𝒁𝒋

𝒁𝒋 − 𝑪𝒋

STEP 4) Find the entering variable whose coefficient in 𝒁𝒋 − 𝑪𝒋 row is most negative
STEP 5) Find the exit variable i.e. the basic variable in the row where the min ratio is small as possible.
(non negative).
STEP 6) Find the Key Element at the intersection of the entering variable column the exit variable row.
STEP 7) Make key element one by dividing the row by Key element
STEP 8) Now make element above or below Key element zero & construct new table by eliminating
artificial variable
STEP 9) Repeat the steps form 2) to 7) until you get all 𝒁𝒋 − 𝑪𝒋 ≥ 𝟎.
STEP 10) Find value of 𝒙𝟏 & 𝒙𝟐 from final table & put in Z to find optimal solution.

MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING

 Page 16 of 20
 Example:
10. Solve the following Linear programming problem using Simplex method to find optimal solution:
Minimize 𝒁 = 𝒙𝟏 + 𝒙𝟐
Subject to 𝟐𝒙𝟏 + 𝒙𝟐 ≥ 𝟒, 𝒙𝟏 + 𝟕𝒙𝟐 ≥ 𝟕, 𝒙𝟏 ≥ 𝟎, 𝒙𝟐 ≥ 𝟎.
Sol: Consider, 𝑴𝒂𝒙 𝒁′ = −𝑴𝒊𝒏 𝒁
𝑀𝑎𝑥 𝑍 ′ = −𝑥1 − 𝑥2 + 0𝑥3 + 0𝑥4 − 𝑀𝐴1 − 𝑀𝐴2
2𝑥1 + 𝑥2 − 𝑥3 + 0𝑥4 + 𝐴1 + 0𝐴2 = 4
𝑥1 + 7𝑥2 + 0𝑥3 − 𝑥4 + 0𝐴1 + 𝐴2 = 7
Key Element
Table 1:
Min Ratio
𝑪𝒋 -1 -1 0 0 −𝑀 −𝑀 𝒃
𝒙𝟐

𝑪𝒃 𝑿𝒃 𝒃 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝑨𝟏 𝑨𝟐
4
−𝑀 𝑨𝟏 4 2 1 -1 0 1 0 =4
1
𝟕
−𝑀 𝑨𝟐 7 1 𝟕 0 -1 0 1 =𝟏
𝟕 Exit Variable
∑[𝑪𝒃 × 𝒙𝒊 ] = 𝒁𝒋 −3𝑀 −8𝑀 𝑀 𝑀 −𝑀 −𝑀
𝒁𝒋 − 𝑪𝒋 −3𝑀 + 1 −8𝑀 + 1 𝑀 𝑀 0 0

Enter Variable
Here, key element is 7
To make it one divide each element of that row by 7
To make element above key element equal to zero.
Old line – New line
4−1 3
1 13
2−
7 7
1−1 0

−1 − 0 −1
−1 1
0−
7 7
1−0 1

Key Element
Table 2:
Min Ratio
𝑪𝒋 -1 -1 0 0 −𝑀 𝒃
𝒙𝟏

𝑪𝒃 𝑿𝒃 𝒃 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝑨𝟏
𝟕
13 1 𝟑×
−𝑀 𝑨𝟏 3 0 -1 1 𝟏𝟑 Exit Variable
7 7 = 𝟏. 𝟔𝟐
1 1 7
−1 𝒙𝟐 1 1 0 − 0 1× =7
7 7 1
−13𝑀 − 1 −𝑀 + 1
∑[𝑪𝒃 × 𝒙𝒊 ] = 𝒁𝒋 1 𝑀 −𝑀
7 7
MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING
 Page 17 of 20
−𝟏𝟑𝑴 − 𝟏 −𝑀 + 1
𝒁𝒋 − 𝑪𝒋 𝟕
+𝟏 0 𝑀 0
7

Enter Variable
13
Here, key element is 7
7
To make it one multiply each element of that row by 13
To make element above key element equal to zero.
1
Old line – 7 × New line
1 21 10
1− ×
7 13 13
1 1
− ×1 0
7 7
1
1− ×0 1
7
1 −7 1
0− ×
7 13 13
−1 1 1 2
− × −
7 7 13 13

Table 3:
𝑪𝒋 -1 -1 0 0

𝑪𝒃 𝑿𝒃 𝒃 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒
21 −7 1
−1 𝒙𝟏 1 0
13 13 13
10 1 2
−1 𝒙𝟐 0 1 −
13 13 13
6 1
∑[𝑪𝒃 × 𝒙𝒊 ] = 𝒁𝒋 −1 −1
13 13
6 1
𝒁𝒋 − 𝑪𝒋 0 0
13 13

𝟐𝟏 𝟐𝟏
Here all 𝒁𝒋 − 𝑪𝒋 ≥ 𝟎 ∴ 𝒙𝟏 = 𝟏𝟑 , 𝒙𝟐 = 𝟏𝟑
21 10
The minimum value of 𝑍 = 13 + 13
𝟑𝟏
∴𝒁= = 𝟐. 𝟑𝟖𝟒𝟔
𝟏𝟑

MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING

 Page 18 of 20
11. Solve the following Linear programming problem using Simplex method to find optimal solution:
Minimize 𝒁 = 𝟒𝒙𝟏 + 𝟔𝒙𝟐
Subject to 𝒙𝟏 + 𝒙𝟐 ≥ 𝟖, 𝟔𝒙𝟏 + 𝒙𝟐 ≥ 𝟏𝟐, 𝒙𝟏 ≥ 𝟎, 𝒙𝟐 ≥ 𝟎.
Sol: Consider, 𝑴𝒂𝒙 𝒁′ = −𝑴𝒊𝒏 𝒁
𝑀𝑎𝑥 𝑍 ′ = −4𝑥1 − 6𝑥2 + 0𝑥3 + 0𝑥4 − 𝑀𝐴1 − 𝑀𝐴2
𝑥1 + 𝑥2 − 𝑥3 + 0𝑥4 + 𝐴1 + 0𝐴2 = 8
6𝑥1 + 𝑥2 + 0𝑥3 − 𝑥4 + 0𝐴1 + 𝐴2 = 12
Key Element
Table 1:
Min Ratio
𝑪𝒋 −4 −6 0 0 −𝑀 −𝑀 𝒃
𝒙𝟏

𝑪𝒃 𝑿𝒃 𝒃 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝑨𝟏 𝑨𝟐
8
−𝑀 𝑨𝟏 8 1 1 -1 0 1 0 =8
1
𝟏𝟐
−𝑀 𝑨𝟐 12 6 1 0 -1 0 1 =𝟐
𝟔 Exit Variable
∑[𝑪𝒃 × 𝒙𝒊 ] = 𝒁𝒋 −7𝑀 −2𝑀 𝑀 𝑀 −𝑀 −𝑀
𝒁𝒋 − 𝑪𝒋 −7𝑀 + 4 −2𝑀 + 1 𝑀 𝑀 0 0

Enter Variable
Here, key element is 6
To make it one divide each element of that row by 6
To make element above key element equal to zero.

Old line – New line

8−2 6

1−1 0
1 5
1−
6 6
−1 − 0 −1
−1 1
0−
6 6
1−0 1

Key Element
Table 2:
Min Ratio
𝑪𝒋 −4 −6 0 0 −𝑀 𝒃
𝒙𝟐

𝑪𝒃 𝑿𝒃 𝒃 𝑥1 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝑨𝟏
𝟓 1 𝟔
−𝑀 𝑨𝟏 6 0 −1 1 𝟔× = 𝟕. 𝟐
𝟔 6 𝟓 Exit Variable
1 1 6
−4 𝒙𝟏 2 1 0 − 0 2 × = 12
6 6 1
−5𝑀 − 4 −𝑀 + 4
∑[𝑪𝒃 × 𝒙𝒊 ] = 𝒁𝒋 −4 𝑀 −𝑀
6 6

MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING

 Page 19 of 20
−𝟓𝑴 − 𝟒 −𝑀 + 4
𝒁𝒋 − 𝑪𝒋 0 𝟔
+𝟔 𝑀 0
6

Enter Variable
5
Here, key element is
6
6
To make it one multiply each element of that row by 5
To make element below key element equal to zero.
1
Old line – × New line
6
1 36 4
2− ×
6 5 5
1
1− ×0 1
6
1 1
− ×1 0
6 6
1 −6 1
0− ×
6 5 5
1 1 1 1
− − × −
6 6 5 5

Table 3:
𝑪𝒋 −4 −6 0 0 Min Ratio
𝒃
𝑪𝒃 𝑿𝒃 𝒃 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟒
36 −6 𝟏 𝟑𝟔 𝟓
−6 𝒙𝟐 0 1 × = 𝟑𝟔
5 5 𝟓 𝟓 𝟏 Exit Variable
4 1 1 4 −5
−4 𝒙𝟏 1 0 − × = −4
5 5 5 5 1
32 2
∑[𝑪𝒃 × 𝒙𝒊 ] = 𝒁𝒋 −4 −6 −
5 5
32 2
𝒁𝒋 − 𝑪 𝒋 0 0 −
5 5

1 Enter Variable
Here, key element is 5
5
To make it one multiply each element of that row by
1
To make element below key element equal to zero.
1
Old line + 5
× New line
4 1
+ × 36 8
5 5
1
1+ ×0 1
5
1
0+ ×5 1
5
1 1
+ × −6 −1
5 5
1 1
− + ×1 0
5 5

MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING

 Page 20 of 20
Table 4:

𝑪𝒋 −4 −6 0 0
𝑪𝒃 𝑿𝒃 𝒃 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒
0 𝒙𝟒 36 0 5 −6 1

−4 𝒙𝟏 8 1 1 −1 0

∑[𝑪𝒃 × 𝒙𝒊 ] = 𝒁𝒋 −4 −4 4 0

𝒁𝒋 − 𝑪𝒋 0 2 4 0

Here all 𝒁𝒋 − 𝑪𝒋 ≥ 𝟎 ∴ 𝒙𝟏 = 𝟖, 𝒙𝟐 = 𝟎
The minimum value of 𝑍 = 4(8) + 6(0)
∴ 𝒁 = 𝟑𝟐

MR. SUDHIR S DESAI 8087348936 MATHEMATICS FOR MACHINE LEARNING