Linear Programming Problem (LPP) , Formulation of LPP, LPP by graphical method.
Linear Programming
Problem (LPP)
Linear programming problem having three parts
(i) Objective function (ii) Constraints
(iii) Non-negativity restrictions
LPP with x and y decision variable
Max/min Z = c1 x +
c2 y (objective
function)
Subject to
a11 x + a12 y (£,=,³) b1
a21 x + a22 y (£,=,³) b2
×
............................ Constraints
×
×
am1 x + am2 y (£,=,³) bm
x, y ³ 0 (unrestricted non negativity)
Example
Maximize / Minimize
Z = 7x + 4y
Subject to
4x + 3 £ 200,
5x – 7y ³ 30
4x
+ 5y = 85,
x ³ 0 y ³ 0
Mathematical formulation of LPP. In this all the equation are
linear with number of variable is maximized or minimized subject to a number of
constraints those things are expressed in linear inequalities.
Decision variable
In this LPP we are to find out a variables which are unknown these variables
are called decision variables. It may takes non-negative values that is it is
unrestricted in sign.
Constraints
Inequalities in terms of equation with decision variable are
called constraints. In LPP the constraints are linear in nature.
Objective function
Find the objectives in model are called as objective
function. It is max or minimized.
So by summarizing
(1) Identify the decision variable
from problem
(2) Identify the constraints from
problem
(3) Identify the objective
function from problem
Ex
1: A company has to
produce A and B two types of product. Each product has to be processed by three
machines (i) moulding (M1) (ii) grinding (M2)
(iii) finishing (M3) suppose machine M1 can be operated for
total time of
2700 minutes. It takes 12 minute for an item of type A and 5 minutes for an
item of type B.
Machine M2 is available for
2000 minutes and it takes 5 minutes for processing an item of type A and 10
minutes for an item of type B.
Machine M3 is available for 450
minutes and it takes for processing an item of type A and 2 minutes for an item
of type B.
The profit per item of type A is 10 and that of per item of
type B is 15 find the number of item of type A and B to be produced so as
maximize the profit. Formulate the L.P.P.
Manufactured item types are two so that there
are two decision variable
X = A type
total number of items
Y = B type
total number of items
The objective function Z is profit of company when A type of
item manufacture is X item an B type of item manufactured by item profit per
item y type A is 10 ` and B is ` 15 so maximize = 10x + 15y
Here the constraint will be time required to process X item
of A and Y items of B on machine M1 which is run for maximum 2700 minutes.
So, 12x + 5y £ 2700 …(1)
A time required to process X item of A and Y items of B on
machine M2 is maximum 2000 minutes
5x + 10y £ 2000 …(2)
Similarly for M3
2x + 2y £ 450 …(3)
Thus the L.P.P is
Maximize Z = 10x + 15y …objective
function
Subject to
Constraints
12x
+ 5y £ 2700
5x + 10y £ 2000
2x + 2y £ 450
x ³ 0 y ³ 0 …non
negative restriction
Ex2: A
paper mill produces two grades of paper namely X and Y. Because of raw material
restrictions, it cannot produces more than 400 tons of grade X and
300 tons of grade y in week. There are 160 production hours in week. It
requires 0.2 and 0.4 hours to produce a ton of products X and Y respectively
with corresponding profits of Rs. 200 and Rs. 500 per ton. Formulate it as LPP.
Ans. :
Number of tons of grade X is denoted by x and
number of tons of grade y is denoted by y. Profits per product of x is zero and
per product of y is 500
Max Z = 200x +
500y
The required time for ton of product X and Y respectively is
0.2 and 0.4 hours and available hours is 160 per week
0.2x + 0.4y £ 160
Maximum production of X is 400 ton of grade X and 300 tons of
grade Y in a week.
X £ 400
Y £ 300
So formulated LPP is
Maximize Z = 200x + 500y objective subject to conditions
Constraints
X £400
Y £ 300
0.2x + 0.4y £ 160
y, x, ³ 0 non negative
Ex 3.
Egg contains 6 units of vitamin A per gram and 7 units of vitamin B per gram
and cost 12 paisa per gram. Milk contains 8 units of vitamin A per gram and 12
units of vitamin B per gram and cost 20 paisa per gram. The daily minimum
requirement of vitamin A and vitamin B are 100 units and 200 units
respectively. Formulate the problem as linear programming problem.
Ans. :
From given information we have
|
|
Egg x |
Milk y |
Minimum requirement |
|
Vitamin A |
6 |
8 |
100 |
|
Vitamin B |
7 |
12 |
200 |
|
Cost per
gram |
12 |
20 |
|
Minimum cost
Z = 12x +
20y
Hence formulated LPP is
Minimum
Z = 12x
+ 20y objective
Subject
6x
+ 8y ³ 100
7x + 12y ³ 200
x,
y ³ 0 non negative
Ex 4 A firm makes two types of furniture chairs and tables. The
contribution for each product as calculated by the accounting department is `
20 per chair and ` 30 per table. Both products are processed on three machines
M1,
M2,
M3.
The time required (in hours) by each product and total time available per check
on each machine are as follows.
|
Machine |
Chair |
Table |
Available
hours per week |
|
M1 |
3 |
3 |
36 |
|
M2 |
5 |
2 |
50 |
|
M3 |
2 |
6 |
60 |
How should be
the manufacturer schedule his production in order to maximise contribution? Formulate
the problem as LPP.
Ans. :
x is no. of chair produced
y is no. of table produced
Here feasible demand is non negative
x ³ 0 y
³ 0
Also a machine availability restriction per week are three so
3x + 3y £ 36
5x + 2y £ 50
2x + 6y £ 60
x ³ 0 y ³ 0
There are profit per output is given profit = 20x + 30y
So from above data LPP formulation
Maximize
Z = 20x
+ 30y (objective function)
5x + 2y £ 50
2x
+ 6y £ 60
x ³ 0
y ³
0
Non negative restrictions
Explain
(a) Solution (b) Feasible solution (c) Optimal solution (d)
Convex set
(a) Solution :
A set of decision
variable which satisfies the constraints of linear programming problem is
called as a solution to corresponding linear programming.
(b) Feasible Solution :
In LPP a solution
which satisfies the non negative restriction is called as feasible solution to
corresponding LPP.
(c) Optimal Solution :
In LPP corresponding
feasible solution which optimizes the objective functions is called as optimal
solution of that linear programming problem.
(d) Convex set :
A region in x – y
plane is called as convex set or region if line segment which is created by
joining two points in the set lies completely within the region.
Solution of LPP by graphical method.
Following steps are in value in
graphical method.
Step 1 : Formulate mathematical problem
Step 2 : Representing all the constraints of problem
after plotting a graph and identify the
feasible region.
Step 3 : Find all corner points of feasible region.
Step 4 : Determine the value of objective function
which is find from step 3.
Step 5 : Optimizes the value of objective function
after selecting the corner point. It gives the optimum feasible solution.
Maximize
Z = 60x + 75y
Subject
to
X
+ 2y £
70
2x
+ 1.5y £
60
X,
y ³
0
Ans. :
Given LPP is
Subject to x + 2y £ 70
2x + 1.5y £ 60
x, y ³ 0
First taking equalizing in given constraints, for finding feasible region
x + 2y = 70
2x + 1.5 y = 60
x + 2y = 70
When x = 0 y = 35
when y = 0, x = 70
(0, 35) (70, 0)
2x + 1.5y = 60
When x = 0 y = = = 40
When y = 0 x = 30
(0, 40) (30,0)
Ex2 Solve the following linear programming
problem by graphically
Maximize z = 20x + 17y
Subject to 2x + 2y £ 22
12x + 10y £ 120
x, y ³ 0
Ans. :
Given LPP is
Maximize Z = 20x + 17y
2x + 2y £ 22
12x + 10y £ 120
X, y ³ 0
Replacing inequalities into equalities
L1
: 2x + 2y = 22
L2 : 12x + 10y = 120
x + y = 11
when, x = 0 y = 11 (0, 11)
y = 120
When x = 0 y
= 12 (0, 12)
y = 0 x = 10 (10, 0)
There are four point OABC
\
Feasible region is a convex region OABC
Having point O(0, 0) A (10, 0)
B(0, 11) C(5, 6)
Here point C is a intersection point of
L1 and L2.
z = 20x +
17y
z0 = 0
zA = z(10,
0) = 20 ´ 10 + 17 ´ 0 = 200
zB = z(0, 11) = 20 ´ 0 + 17(11) = 187
zC = z(5, 6) = 20(5) + 17(6) = 100 + 102 = 202
zmax = zC = 202
Ex 4 Solve the following LPP graphically
Minimize Z
= 2x1 + 4x2
Subject
to 6x1 + x2 ³
18
x1 + 4x2 ³
12
2x1 + x2 ³
10
x1, x2 ³
0
Ans. :
From given data
LPP is
Minimize Z
= 2x1 + 4x2
Subject to 6x1 + x2 ³ 18
x1 + 4x2 ³ 12
2x1 + x2 ³ 10
x1, x2 ³ 0
first we find feasible region for that
we equalize each equation
6x1 + x2 = 18 x1 = 0 x2 = 18
x2 = 0 x1 = 3
(0, 18) (3, 0)
x1 + 4x2 = 12 x1 = 0 x2 = 3
X2 = 0 x1 = 12
(0, 3) (12, 0)
2x1 + x2 = 10 x2 = 0 x1 = 5
(0, 10) (5, 0)
x2 = 0 x1 = 5
(0, 10) (5, 0)
Put all these point on graph
Let point of intersection of L1 and L3 is G (2, 6) and point
of intersection of L2 and L3 is H (4, 2)
The shaded region is feasible region of LPP
The minimum value of z will be at one of the point CHGB
So Z = 2x1 + 4x2
z(0, 18) = 2 ´ 0 + 4 ´ 18 = 72
z(2, 6) = 2 ´ 2 + 4 ´ 6 = 28
z(4, 2) = 2 ´ 4 + 4 ´ 2 = 16
z(12, 0) = 2 ´ 12 + 4 ´ 0 = 24
out of these above point minimum value of z at point z(4, 2).
