Welcome to the presentation

On

Linear Programming Problem

Presented by :
Dr. Mohammed Nasir Uddin
Professor
Dept. Of ICT
Faculty of Science and Technology(FST)
Bangladesh University of Professionals (BUP)
1 MNU, Prof., Dept. of ICT, BUP. 15 August 2024
 Contents

Introduction
Learning Out comes
Discussion Points
Inequalities

Linear Programming

Optimization of a function
2 MNU, Prof., Dept. of ICT, BUP. 15 August 2024
 Objectives

To know Linear Programming Problem (LPP)

To get an idea about Graphical Method

To solve the application of LPP/Optimization problem

3 MNU, Prof., Dept. of ICT, BUP. 15 August 2024

 Learning Outcomes

Understand the Linear Programming Problem (LPP)

Solve the LPP using Graphical Method

Know the Application of LPP

4 MNU, Prof., Dept. of ICT, BUP. 15 August 2024

 Why It's Important

To find the maximum and minimum values of a function

over a region by using linear programming techniques

To solve Linear Programming problems by solving a

simpler problem.

You can use linear programming to solve practical

problems such as agriculture and manufacturing problem.
5 MNU, Prof., Dept. of ICT, BUP. 15 August 2024
 Linear Programming Problem (LPP)

Linear programming is a procedure for finding the

maximum or minimum value of a function in two
or more variables called the objective function,
subject to given some conditions on the variables
called constraints.

Thus, a Linear programming Problem has two parts.

Part – 1: The Objective function

Part – 2: The Constraints

6 MNU, Prof., Dept. of ICT, BUP. 15 August 2024

 Example
Objective function

Maximize or Minimize, Z = 2x – 3y
Subject to
x + 2y ≤ 9
x≥1 Constraints
y≥2

15 August 2024 MNU, Prof., Dept. of ICT, BUP. 7

 Graphical Procedure for Linear
Programming Problem of two variables

1. Consider the inequalities (constraints ) as equations.

2. Graph these system of equations.
3. Shade the region for each inequality.
4. Find the coordinates of the vertices of the feasible region.

N.B.: The coordinates of the vertices of a feasible region

can be found by reading a graph or by solving a system
of equations.
8 MNU, Prof., Dept. of ICT, BUP. 15 August 2024
5. Substitute the coordinates of the vertices into the
objective function.

N.B.: Mathematicians have shown that the maximum and

minimum values of a function occur at the vertices of
the feasible region.

6. Select the greatest or least result according to the

objective function. Answer the problem.

9 MNU, Prof., Dept. of ICT, BUP. 15 August 2024

 Example-1

Use three step graphical procedure to find

min =5x+7y
Subject to, 2x+3y  12
. 5x+y  17
. x0
. y0
Solution: To solve the above LPP we consider the
inequalities as equations. Thus we get,
2x+3y =12
5x+y =17
15 August 2024 MNU, Prof., Dept. of ICT, BUP. x=0, y=010
 Now we want to y
draw the graph of
these equations.
x=0
x=0 is the y axis
since x 0 so right side
to y axis is our solution
space and it is shaded.
y =0
y =0 is the x axis
since y 0 so the
upper side to x axis is
our solution space (0, 0) x
and it is shaded.
15 August 2024 MNU, Prof., Dept. of ICT, BUP. 11
 Here we use a scale of
For 2x+3y =12, the 1 square = 1units along x axis and
table below gives the y
value of x and the 1 square = 2 unit along y axis.
corresponding value of
y.

2x+3y =12
x 0 6
y 4 0

(0, 4)
Test (0,0) in 2x+3y 12
and the result is false.
So (0,0) is not the (0, 0) (6, 0) x
solution space.
15 August 2024 MNU, Prof., Dept. of ICT, BUP. 2x+3y =12 12
 y
For 5x+y =17, the
table below gives the
value of x and the
corresponding value of (0, 17)
y.

5x+y =17
x 0 3.4 5x+y =17
y 17 0
(0, 4)
Test (0,0) in 5x+y 17
and the result is false.
So (0,0) is not in the (0, 0) (3.4, 0) (6, 0) 2x+3y =12 x
solution space.
15 August 2024 MNU, Prof., Dept. of ICT, BUP. 13
 y

Thus the vertices

on the feasible (0, 17)
region (solution
space) are
A(0, 17)
B(3, 2) 5x+y =17
C(6, 0)
Now we calculate
the value of the (0, 4)
objective function
on these vertices.
(0, 0) (3.4, 0) (6, 0) 2x+3y =12 x
15 August 2024 MNU, Prof., Dept. of ICT, BUP. 14
Vertex  =5x+7y y

A(0,17) 119
B(3, 2) 29 (0, 8.5)
C(6, 0) 30
5x+y =17

Thus minimum of
 is 29 at (3, 2)
(ans.) (3, 2)
(0, 0) (6, 0) x
15 August 2024 2x+3y =12
MNU, Prof., Dept. of ICT, BUP. 15
 Graphical Solution of LPP
Example-2: Maximize or Minimize Z = 2x – 3y
Subject to
x + 2y ≤ 9
x≥1
y≥2
Solution: We consider all the inequalities as equalities
That is we get, x+2y = 9
x=1
y=2

15 August 2024 MNU, Prof., Dept. of ICT, BUP. 16

 Maximize or minimize Z = 2x – 3y
Subject to
x + 2y ≤ 9
x≥1
y≥2 x=1

x=1 is a vertical line 1 unit

right to the origin and since
Solution Space
x ≥1 so right side is our solution
space for x ≥1.

15 August 2024 MNU, Prof., Dept. of ICT, BUP. 17

y=2 is a horizontal line 2 units upper to the origin and since y ≥2
so upper side is our solution space for y ≥2.

x=1

y =2

15 August 2024 MNU, Prof., Dept. of ICT, BUP. 18

For x+2y = 9, we can construct two points (0, 4.5) and (0, 9)
Test:
At origin (0,0)
we have x + 2y ≤ 9 x=1
0 + 2.0 ≤ 9
0≤9
Which is true.
So (0,0) is in the solution
space.
Hence the shaded area is our
y=2
required solution space.

19 15 August 2024 MNU, Prof., Dept. of ICT, BUP.

 The solution space formed is a triangle with vertices at
(1,2), (5,2) and (1,4)
 Now use a chart to find the maximum and minimum
values of the function

(1,4)

(1,2) (5,2)

15 August 2024 MNU, Prof., Dept. of ICT, BUP. 20

 Vertex (x,y) Z= 2x – 3y

A (1,2) 2(1) – 3(2) -4

B (5,2) 2(5) – 3(2) 4

C (1,4) 2(1) – 3(4) -10

The maximum value is 4 at (5,2).

The minimum value is -10 at (1,4)

15 August 2024 MNU, Prof., Dept. of ICT, BUP. 21

A Candy manufacturer has 130 pounds of
chocolate-covered cherries and 170 pounds of
chocolate-covered mints. He decides to sell them in
the form of two different mixtures. One mixture
will contain 1/2 cherries and 1/2 mints and will
sell $1.25 per pound and the other mixture will
contain 1/3 cherries and 2/3 mints and will sell
$2 per pound. How many pounds of each mixture
should the Candy manufacturer prepare in order to
maximize his sales revenue?
22 MNU, Prof., Dept. of ICT, BUP. 15 August 2024
 Solution:
Let, x be the amount of Mixture-1 and
y be the amount of Mixture-2
Mathematical Formulation:
Maximum Sales, R = 1.25x +2y
s/t,
x/2+y/3130
x/2+2y/3170
x0
y0
23 MNU, Prof., Dept. of ICT, BUP. 15 August 2024
A company produces 2 types of leather belts-Type A
and B. Contribution per belt is $4 for type A and $3
for type B. The time requirements of one belt of
type A and type B are in the ratio 2:3. The time
available is 1000 minutes sufficient for only 400
belts. Belt A requires a fancy buckle and only 200
fancy buckles are available. Formulate above as a
linear programming problem and solve it by LPP.

24 MNU, Prof., Dept. of ICT, BUP. 15 August 2024

 Solution:
Let, x be the belt of type A and
y be the belt of type B
Mathematical Formulation:
Max. P = 4x +3y
s/t,
2x+3y1000
x+y400
x200
x0
25
y0
MNU, Prof., Dept. of ICT, BUP. 15 August 2024
ABC Dairy Company wishes to make a new cheese
from two of its current cheeses: Cheese X and
Cheese Y. The mixture is to weight no more than
four pounds and is to contain at least six
ounces of the sharpness ingredient S. Each pound
of X cost $4 and contains three ounces of S,
whereas each pound of Y costs $1 and contains
one ounce of S. How many pounds of each
cheese should be used in the mixture in order to
meet these requirements at a minimum cost? What
is this minimum cost?
26 MNU, Prof., Dept. of ICT, BUP. 15 August 2024
 Solution:
Let, x be the amount of Cheese X
y be the amount of Cheese Y
Mathematical Formulation:
Zmin = 4x +y
s/t,
x+y4
3x+y  6
x0
y0
27 MNU, Prof., Dept. of ICT, BUP. 15 August 2024
28 MNU, Prof., Dept. of ICT, BUP. 15 August 2024