Transcript Linear Programming

Linear Programming
Terminology
Contents
1.
2.
3.
4.
What is a Mathematical Model?
Illustration of LPP: Maximization Case
What is Linear Programming Problem (LPP)?
Graphical Solution
o
o
Feasible Solutions
Optimal Solution
5. Concepts:
o
o
o
What is Feasibility?
What is an Optimal Solution?
Convex Sets & LPP
http://www.rajeshtimane.com/
2
I. What is a Mathematical Model ?
F=ma
‘Mathematical Expressions’
o
Here m and a are called as ‘Decision Variables’
o
F can be called as ‘Objective Functions’
o
Now, F can be controlled or restricted by limiting m or
a … say m < 50 kg …here, m can be called as a
‘Constraint’
o
Similarly if a > o …always, then this condition is called
as ‘Non-Negativity Condition’
http://www.rajeshtimane.com/
3
II. Illustration:
Objective
Function
Maximize: Z = 3x1 + 5x2
Subject to restrictions:
x1
2x2
3x1 + 2x2
<4
< 12
< 18
Functional
Constraints
Non negativity condition
x1
x2
>0
>0
Non-negativity
constraints
http://www.rajeshtimane.com/
4
III. What is Linear Programming?
 The most common application of LP is allocating
limited resources among competing activities in a
best possible way i.e. the optimal way.
 The adjective linear means that all the mathematical
functions in this model are required to be linear
functions.
 The word programming does not refer to computer
programming; rather, essentially a synonym for
planning.
http://www.rajeshtimane.com/
5
IV. Graphical Solution
Ex) Maximize: Z = 3x1 + 5x2
Subject to restrictions:
x1 < 4
2x2 < 12 i.e. x2 < 6
3x1 + 2x2 < 18
Non negativity condition
x1, x2 > 0
Solution: finding coordinates for the constraints (assuming perfect equality), by putting
one decision variable equal to zero at a time.
Restrictions (Constraints)
Co-ordinates
x1 < 4
(4 , 0)
x2 < 6
(0 , 6)
3x1 + 2x2 < 18
(0 , 9) & (6 , 0)
http://www.rajeshtimane.com/
6
Restrictions (Constraints)
Co-ordinates
Non-negativity Constraint
x1 < 4
(4 , 0)
x1, > 0
x2 < 6
(0 , 6)
x2 > 0
3x1 + 2x2 < 18
(0 , 9) & (6 , 0)
X2
10
8
6
A
B
4
C
Feasible Region (Shaded / Points A, B, C, D and E)
2
D
0
E
2
4
6
8
10
X1
http://www.rajeshtimane.com/
7
Feasible Solutions
 Try co-ordinates of all the corner points of
the feasible region.
 The point which will lead to most
satisfactory objective function will give
Optimal Solution.
 Note: for co-ordinates at intersection; solve
the equations (constraints) of the two lines
simultaneously.
http://www.rajeshtimane.com/
8
Optimal Solution
Corner
Limiting Constraint
Co-ordinate
Max. Z= 3x1 + 5x2
A
x2 = 6
(0 , 6)
30
B
x2 = 6 & 3x1 + 2x2 = 18
(2 , 6)
36
C
x1 = 4 & 3x1 + 2x2 = 18
(4 , 3)
27
D
x1 = 4
(4 , 0)
12
E
Origin
(0 , 0)
0
From the above table, Z is maximum at point ‘B’ (2 , 6) i.e. The
Optimal Solution is:
X1 = 2 and
X2 = 6
ANSWER
http://www.rajeshtimane.com/
9
Conceptual Understanding
 Feasibility
 Optimal Solution
 Convex Set
http://www.rajeshtimane.com/
10
What is Feasibility ?
 Feasibility Region
[Dictionary meaning of feasibility is possibility]
“The region of acceptable values of the
Decision Variables in relation to the
given Constraints (and the Non-Negativity
Restrictions)”
http://www.rajeshtimane.com/
11
What is an Optimal Solution ?
 It is the Feasible Solution which Optimizes.
i.e. “provides the most beneficial result for the specified
objective function”.
 Ex: If Objective function is Profit then Optimal Solution
is the co-ordinate giving Maximum Value of ‘Z’…
While; if objective function is Cost then the optimum
solution is the coordinate giving Minimum Value of ‘Z’.
http://www.rajeshtimane.com/
12
Convex Sets and LPP’s
“If any two points are selected in the feasibility region
and a line drawn through these points lies completely
within this region, then this represents a Convex Set”.
Convex Set
Non-convex Set
A
A
B
B
http://www.rajeshtimane.com/
13
Contact
For any further queries/details be in
touch with the author at:
http://www.rajeshtimane.com
http://www.rajeshtimane.com/
14