Graphical method

Graphical Method of Linear Programming Problem

1. Operation Research
Graphical Method
Prof. V. D. Zanzrukiya
Department of Computer Science
Smt. C. K. Patel M.Sc.(CA & IT) College
Kadi(Gujarat) -INDIA
[email protected]

2. Definition of Operation Research
•Operationresearchistheapplicationofthemethodsofscienceto
complexproblemsinthedirectionandmanagementoflarge
systemsofmen,machines,materialsandmoneyinindustry,
business,governmentanddefence.Thedistinctiveapproachisto
developascientificmodelofthesystemincorporating
measurementsoffactorssuchaschanceandrisk,withwhichto
predictandcomparetheoutcomesofalternativedecisions
strategiesorcontrols.Thepurposeistohelpmanagementin
determiningitspolicyandactionsscientifically.
-Operation Research Society, UK
Prof. V. D. Zanzrukiya

3. General Structure of Linear Programming Model
•ThegeneralstructureofL.P.Modelconsistsofthreebasiselementsor
components
1.Decisionvariables(Activities)
2.Theobjectivefunction(ORGoalFunction)
3.TheConstraints
Inourdaytodaylifeorinanindustrialcompanytherearecertain
problemsinwhichobjectiveslikeprofit,cost,revenue,distance,time,etc.are
eithertobemaximizedorminimizedsubjecttocertainconditionsovercertain
factors(variables).Ifsuchanobjectiveaswellasconditionscanbewrittenas
Linearfunctionintermsofcertainvariablesthensuchaproblemiscalled
LinearProgrammingProblem.
Prof. V. D. Zanzrukiya

4. •General L.P. Model can be described as follows:
Find the values of x
1,x
2, …, x
nso as to optimize (maximize or minimize)
Z = c
1x
1+ c
2x
2+ … + c
nx
n
Subject to the constraints
a
11x
1+ a
12x
2+ … + a
1nx
n(≤, =, ≥) b
1
a
21x
1+ a
22x
2+ … + a
2nx
n(≤, =, ≥) b
2
⋮ ⋮ ⋮ ⋮ ⋮
a
m1x
1+ a
m2x
2+ … + a
mnx
n(≤, =, ≥) b
m
Such that x
1,x
2, …, x
n≥ 0
(1) is called the objective (goal) function
(2) Represents set of constraints
(3) Represents the non-negative constraints
------(1)
------(2)
------(3)
Prof. V. D. Zanzrukiya

5. Remarks
i.x
1,x
2, …, x
nare called decision variables.
ii.The constants c
1,c
2, …, c
nin the objective functions are called cost
coefficients.
iii.Constants b
1,b
2, …, b
min the set of constraints are called the right hand
side constants.
iv.In each and every constrains of set (2) one and only one of the relation ≤, =
or ≥ holds true. Different relations may occur in different constraints.
v.Constants a
i’s in set of constraints (2) are called input-output coefficients
or technological coefficients.
Prof. V. D. Zanzrukiya

6. Formulation of LPP
Prof. V. D. Zanzrukiya

7. Problem:
AfirmmanufacturestwotypesofproductA&Bandsellsthemataprofitof`2and`3
respectively.EachproductisprocessedontwomachinesG&H.TypeArequires1minute
processingtimeonmachineGand2minutesofprocessingtimeonmachineH.TypeB
requires1minuteofprocessingoneachmachine.MachineGisavailablefornotmorethan6
hours40minuteswhilemachineHisavailablefor10hoursduringanyworkingday.How
manyproductofeachtypeshouldthefirmproduceofeachdayinordertogetmaximum
profit?FormulatetheLPP.
Solution:
Thegivendatacanbetubulizedinthefollowingform.
Machine
Time of Product in Minute
Avaibility of Time
A B
G 1 1 400
H 2 1 600
Profit per Unit (`) 2 3
Prof. V. D. Zanzrukiya

8. Continue…
Letthefirmmanufacturex
1unitsoftheproductoftypeAandx
2unitsoftheproduct
oftypeB.
Findx
1andx
2inorderto
maximizeZ=2x
1+3x
2
Subjecttotheconstraints
x
1+x
2≤400
2x
1+x
2≤600
andx
1,x
2≥0
Prof. V. D. Zanzrukiya

9. Linear Programming
The Graphical Method
Prof. V. D. Zanzrukiya

10. Introduction
AnoptimalaswellasafeasiblesolutiontoanLPproblemisobtainedby
choosingavaluefromseveralpossiblevaluesofdecisionvariablesx
1,x
2,…,x
n,
theonesetofvaluesthatsatisfiesthegivensetofconstrainssimultaneouslyand
alsoprovidestheoptimal(maximumorminimum)valueofthegivenobjective
function.
ForLPproblemsthathaveonlytwovariables,itispossiblethatthe
entiresetoffeasiblesolutionscanbedisplayedgraphicallybyplottinglinear
constraintsonagraphpaperinordertolocatethebest(optimal)solution.The
Techniqueusedtoidentifytheoptimalsolutioniscalledthegraphicalsolution
approachortechniqueforanLPproblemwithtwovariables.
Prof. V. D. Zanzrukiya

11. Important Definition
Slack Variable
Anon-negativevariablewhichconverts≤typeconstraintofaLPPintotheequationis
calledaslackvariablesuchavariableisaddedtotheLHSof≤typeconstraints.
Example:
2x
1+x
2≤600
2x
1+x
2+S=600
Surplus Variable
Anon-negativevariablewhichconverts≥typeconstraintofaLPPintotheequationis
calledasurplusvariablesuchavariableissubtractedfromtheLHSof≥typeconstraints.
Example:
2x
1+3x
2≥900
2x
1+3x
2–S=900
Slack Variable
Surplus Variable
Prof. V. D. Zanzrukiya

12. Solution
Thesetofvaluesofdecisionvariablesx
j(j=1,2,…,n)thatsatisfytheconstraintsofan
LPproblemissaidtoconstitutethesolutiontothatLPproblem
FeasibleSolution
Thesetofvaluesofdecisionvariablesx
j(j=1,2,…,n)thatsatisfyalltheconstraintsand
non-negativityconditionsofanLPproblemsimultaneouslyissaidtoconstitutethefeasible
solutiontothatLPproblem
InfeasibleSolution
Thesetofvaluesofdecisionvariablesx
j(j=1,2,…,n)thatdonotsatisfyallthe
constraintsandnon-negativityconditionsofanLPproblemsimultaneouslyissaidtoconstitute
theinfeasiblesolutiontothatLPproblem
BasicSolution
Forasetofmsimultaneousequationsinnvariables(n>m),asolutionobtainedby
setting(n–m)variablesequaltozeroandsolvingforremainingmequationsinmvariablesis
calledabasicsolution.
The(n–m)variableswhosevaluedidnotappearinthissolutionarecallednon-basic
variablesandtheremainingmvariablesarecalledbasicvariables.
Prof. V. D. Zanzrukiya

13. Basic Feasible Solution
AfeasiblesolutiontoanLPproblemwhichisalsothebasicsolutioniscalledthebasic
feasiblesolution..Thatis,allbasicvariablesassumenon-negativevalues.
Basicfeasiblesolutionsareoftwotypes:
(a)Degenerate:Abasicfeasiblesolutioniscalleddegenerateifthevalueofatleast
onebasicvariableiszero.
(b)Non-degenerate:Abasicfeasiblesolutioniscallednon-degenerateifvaluesofallm
basicvariablesarenon-zeroandpositive.
OptimumBasicFeasibleSolution
Abasicfeasiblesolutionthatoptimizes(maximizesorminimizes)theobjective
functionvalueofthegivenLPproblemiscalledanoptimumbasicfeasiblesolution.
UnboundedSolution
Asolutionthatcanindefinitelyincreaseordecreasethevalueoftheobjectivefunction
oftheLPproblemiscalledanunboundedsolution.
Prof. V. D. Zanzrukiya

14. GRAPHICAL SOLUTIONMETHODS OFLPPROBLEM
•ExtremePointSolutionMethod
Inthismethod,thecoordinatesofallcorner(orextreme)pointsofthefeasibleregion(spaceor
area)aredeterminedandthenvaluesoftheobjectivefunctionatthesepointsarecomputed
andcomparedbecausethemathematicaltheoryofLPstatesthatanoptimalsolutiontoany
LPproblemalwayslieatoneofthecorner(extreme)pointsofthefeasiblesolutionspace.
Thestepsofthemethodaresummarizedasfollows:
Step-1:DevelopanLPmodel
GeneratethemathematicalmodelofthegivenLPproblem.
Step-2:Plotconstraintsongraphpaperanddecidethefeasibleregion
(a)Replace≤and≥signto=ineachconstraint(inequalitytoequality).
(b)Findthetwopointsofeachlineanddrawitongraph.
Prof. V. D. Zanzrukiya

15. Continue…
(c)Forinequalitysignofeachconstraint,decidetheareaoffeasiblesolution.
(For≤constraintitisleftsideofthelineandfor≥constraintitisrightsideoftheline.
Soforeasyunderstanding,takeanypointofleftsideoflineandifitsatisfiesthe
constraintthenmarktheleftsideareaotherwisemarktherightsidearea)
(d)Shadethecommonportionofthegraph.
Step-3:Examineextremepointsofthefeasiblesolutionspacetofindanoptimal
solution
(a)Decidetheextremepoints(cornerpoints)ofthefeasibleregion.
(b)Calculatetheobjectivefunctionvalueateachextremepoints.
(c)Findoutminormaxvalue(optimalvalue)oftheobjectivefunction.
Prof. V. D. Zanzrukiya

16. Examples on Maximization LP Problem
Example:Usethegraphicalmethodtosolve
thefollowingLPproblem
Maximize??????=15??????
1+10??????
2
Subjecttotheconstraints
4??????
1+6??????
2≤360
3??????
1≤180
5??????
2≤200
and ??????
1,??????
2≥0
Solution:
HereGivenLPproblemis
Maximize??????=15??????
1+10??????
2
Subjecttotheconstraints
4??????
1+6??????
2≤360
3??????
1≤180
5??????
2≤200
and ??????
1,??????
2≥0
Prof. V. D. Zanzrukiya

17. To draw a constraint
4??????
1+6??????
2≤360------(1)
Treat it as 4??????
1+6??????
2=360
When ??????
1=0then ??????
2=?
⇒40+6??????
2=360
⇒6??????
2=360
⇒??????
2=
360
6
=60
∴??????
1,??????
2=(0,60)
When ??????
2=0then ??????
1=?
⇒4??????
1+60=360
⇒4??????
1=360
⇒??????
1=
360
4
=90
∴??????
1,??????
2=(90,0)
To draw a constraint
3??????
1≤180------(2)
Treat it as 3??????
1=180
⇒3??????
1=180
⇒??????
1=
180
3
=60
Here Line is parallel to Y-axis
To draw a constraint
5??????
2≤200------(3)
Treat it as 5??????
2=200
⇒5??????
2=200
⇒??????
2=
200
5
=40
Here Line is parallel to X-axis
Prof. V. D. Zanzrukiya

18. Prof. V. D. Zanzrukiya
??????
1
??????
2
0 20 40 60 80 100
100
80
60
40
20
(0, 60)
(90, 0)
1
1 4??????
1+6??????
2=360
2
2 3??????
1=180
3
3
5??????
2=200
Feasible
Region
O(0, 0)
A(60, 0)
B(60, 20)
C(30, 40)D(0, 40)

19. Extreme Point
Coordinates
??????
1,??????
2
Objective Function
??????=15??????
1+10??????
2
O (0, 0) 15(0) + 10(0) = 0
A (60, 0) 15(60) + 10(0) = 900
B (60, 20) 15(60) + 10(20) = 1100
C (30, 40) 15(30) + 10(40) = 850
D (0, 40) 15(0) + 10(40) = 400
Prof. V. D. Zanzrukiya
The optimal solution to the given LP problem is ??????
1=60, ??????
2=20 and Maximize
Z=1100

20. Examples on Minimization LP Problem
Example:Usethegraphicalmethodtosolve
thefollowingLPproblem
Minimize??????=3??????
1+2??????
2
Subjecttotheconstraints
5??????
1+??????
2≥10
??????
1+??????
2≥6
??????
1+4??????
2≥12
and ??????
1,??????
2≥0
Solution:
HereGivenLPproblemis
Minimize??????=3??????
1+2??????
2
Subjecttotheconstraints
5??????
1+??????
2≥10
??????
1+??????
2≥6
??????
1+4??????
2≥12
and ??????
1,??????
2≥0
Prof. V. D. Zanzrukiya

21. To draw a constraint
5??????
1+??????
2≥10------(1)
Treat it as 5??????
1+??????
2=10
When ??????
1=0then ??????
2=?
⇒50+??????
2=10
⇒0+??????
2=10
⇒??????
2=10
∴??????
1,??????
2=(0,10)
When ??????
2=0then ??????
1=?
⇒5??????
1+0=10
⇒??????
1=
10
5
=2
∴??????
1,??????
2=(2,0)
To draw a constraint
??????
1+4??????
2≥12------(3)
Treat it as ??????
1+4??????
2=12
When ??????
1=0then ??????
2=?
⇒0+4??????
2=12
⇒4??????
2=12
⇒??????
2=
12
4
=3
∴??????
1,??????
2=(0,3)
When ??????
2=0then ??????
1=?
⇒??????
1+4(0)=12
⇒??????
1+0=12
⇒??????
1=12
∴??????
1,??????
2=(12,0)
Prof. V. D. Zanzrukiya
To draw a constraint
??????
1+??????
2≥6------(2)
Treat it as ??????
1+??????
2=6
When ??????
1=0then ??????
2=?
⇒0+??????
2=6
⇒??????
2=6
∴??????
1,??????
2=(0,6)
When ??????
2=0then ??????
1=?
⇒??????
1+0=6
⇒??????
1=6
∴??????
1,??????
2=(6,0)

22. Prof. V. D. Zanzrukiya
??????
1
??????
2
0 2 4 6 8 10 12 14
10
8
6
4
2
1
1 5??????
1+??????
2=10
2
2 ??????
1+??????
2=6
3
3
??????
1+4??????
2=12
A(12, 0)
B(4, 2)
C(1, 5)
D(0, 10)
Feasible
Region

23. Extreme Point
Coordinates
??????
1,??????
2
Objective Function
??????=�??????
1+�??????
2
A (12, 0) 3(12) + 2(0) = 36
B (4, 2) 3(4) + 2(2) = 16
C (1, 5) 3(1) + 2(5) = 13
D (0, 10) 3(0) + 2(10) = 20
Prof. V. D. Zanzrukiya
The optimal solution to the given LP problem is ??????
1=1, ??????
2=5 and Minimize Z = 13

24. Examples on Mixed Constraints LP Problem
Example:Usethegraphicalmethodtosolve
thefollowingLPproblem
Maximize??????=2??????
1+3??????
2
Subjecttotheconstraints
??????
1+??????
2≤30
??????
2≥3
0≤??????
2≤12
0≤??????
1≤20
??????
1−??????
2≥0
and ??????
1,??????
2≥0
Solution:
HereGivenLPproblemis
Maximize??????=2??????
1+3??????
2
Subjecttotheconstraints
??????
1+??????
2≤30
??????
2≥3
0≤??????
2≤12
0≤??????
1≤20
??????
1−??????
2≥0
and ??????
1,??????
2≥0
Prof. V. D. Zanzrukiya

25. To draw a constraint
??????
1+??????
2≤30------(1)
Treat it as ??????
1+??????
2=30
When ??????
1=0then ??????
2=?
⇒0+??????
2=30
⇒??????
2=30
∴??????
1,??????
2=(0,30)
When ??????
2=0then ??????
1=?
⇒??????
1+0=30
⇒??????
1=30
∴??????
1,??????
2=(30,0)
To draw a constraint
??????
1−??????
2≥0 ------(5)
Treat it as ??????
1−??????
2=0
⇒??????
1=??????
2
When ??????
1=0then ??????
2=?
⇒??????
2=0
∴??????
1,??????
2=(0,0)
When ??????
2=25then ??????
1=?
⇒??????
1=25
∴??????
1,??????
2=(25,25)
Prof. V. D. Zanzrukiya
To draw a constraint
??????
2≥3------(2)
Treat it as ??????
2=3
Here Line is parallel to X-axis
To draw a constraint
0≤??????
2≤12------(3)
Treat it as ??????
2=12
Here Line is parallel to X-axis
To draw a constraint
0≤??????
1≤20------(4)
Treat it as ??????
1=20
Here Line is parallel to Y-axis

26. Prof. V. D. Zanzrukiya
??????
1
??????
2
0 5 10 15 20 2530 35
30
25
20
15
10
5
1
1??????
1+??????
2=30
2
2??????
2=3
3
3??????
2=12
4
4??????
1=20
5
5??????
1−??????
2=0
Feasible
Region
A(3, 3) B(20, 3)
C(20, 10)
D(18, 12)E(12, 12)

27. Extreme Point
Coordinates
??????
1,??????
2
Objective Function
??????=�??????
1+�??????
2
A (3, 3) 2(3) + 3(3) = 15
B (20, 3) 2(20) + 3(3) = 49
C (20, 10) 2(20) + 3(10) = 70
D (18, 12) 2(18) + 3(12) = 72
E (12, 12) 2(12) + 3(12) = 60
Prof. V. D. Zanzrukiya
The optimal solution to the given LP problem is ??????
1=18, ??????
2=12 and Maximize Z = 72