Operations Research- LPP formulation with examples

LPP formulation

1. Module-1
Formulation of Linear
Programming Problem
1

2. Introduction
•Manymanagementdecisionsinvolvetryingtomakethemosteffectiveuseof
anorganization’sresources.
•Resourcestypicallyincludemachinery,labor,money,time,warehousespace,
orrawmaterials.
•Resourcesmaybeusedtoproduceproducts(suchasmachinery,furniture,
food,orclothing)orservices(suchasschedulesforshippingandproduction,
advertisingpolicies,orinvestmentdecisions).
•Linearprogramming(LP)isawidelyusedmathematicaltechniquedesignedto
helpmanagersinplanninganddecisionmakingrelativetoresourceallocation.
•Despitethename,linearprogramming,andthemoregeneralcategoryof
techniquescalled“mathematicalprogramming”,haveverylittletodowith
computerprogramming.
•IntheworldofOperationsResearch,programmingreferstomodelingand
solvingaproblemmathematically.
•Computerprogramminghas,however,playedanimportantroleinthe
advancementanduseofLPtosolvereal-lifeLPproblems
2

3. LinearProgrammingProblem(LPP)isconcernedwithfindingthe
optimalvalue(maximumorminimumvalue)ofalinearfunction(called
objectivefunction)ofseveralvariables(sayxandy),subjecttothe
conditionsthatthevariablesarenon-negativeandsatisfyasetoflinear
inequalities(calledlinearconstraints)
Theobjectivefunctionmaybeprofit,cost,productioncapacityorany
othermeasureofeffectiveness,whichistobeobtainedinthebest
possibleoroptimalmanner.
Theconstraintsmaybeimposedbydifferentresourcessuchasraw
materialavailability,marketdemand,productionprocessand
equipment,storagecapacity,etc.
3
Linear Programming Problem

4. Bylinearityismeantamathematicalexpressioninwhichtheexpressions
amongthevariablesarelineare.g.,theexpressiona1x1+а2x2+a3x3+...+
anxnislinear.Thevariablesobeythepropertiesofproportionality(e.g.,ifa
productrequires3hoursofmachiningtime,5unitsofitwillrequire15
hours)andadditivity(e.g.,amountofaresourcerequiredforacertain
numberofproductsisequaltothesumoftheresourcerequiredforeach).
ALinearProgrammingmodelseekstomaximizeorminimizealinear
function,subjecttoasetoflinearconstraints.Thelinearmodelconsistsof
thefollowingcomponents:
Asetofdecisionvariables
Anobjectivefunction
Asetofconstraints
4

5. ImportanceofLinearProgramming
Manyrealworldproblemslendthemselvestolinearprogramming
modeling.
Therearewell-knownsuccessfulapplicationsin:
Manufacturing-Productmixproblems,Blendingproblems,
Productionschedulingproblems,Trimlossproblems,Assembly-line
balancing.
Management-Mediaselectionproblems,Portfolioselection
problems,Profitplanningproblems,Transportationproblems,
Assignmentproblems,Man-powerschedulingproblems
Finance(investment)
Advertising
Agriculture
5
Linear Programming Problem

6. 6
LPP -Formulation
Max/Min Z= c
1x
1+ c
2x
2+ ... + c
nx
n
subject to:
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
x
1, x
2, …..,x
n≥ 0
x
j= decision variables
b
i= constraint levels
c
j = objective function coefficients
a
ij= constraint coefficients

7. Q1
Supposeyouconsideracademicsandextra-curricularactivitiesarethe
twomostimportantaspectsthathavedirectimpactonyourprospectsfor
placements.Youestimatetheratiooftheimpactofdevoting1hourto
academicstotheimpactofdevoting1hourtoextra-curricularactivities
onyourplacementprospectstobe3:5.Youdecidenottospendmore
than8hoursdailyforthesetwoactivities.Moreover,youestimatethat1
hourofacademicsand1hourofextra-curricularactivitiesburn,onan
average,100and250calories,respectively,andyoucannotaffordtoburn
morethan1250caloriesforthesetwoactivitiesbasedonyouraverage
dailycalorieintake.Howmanyhoursshouldyoudevotetoacademicsand
extra-curricularactivitiesdaily?
7
LPP -Formulation

8. Q1
Supposeyouconsideracademicsandextra-curricularactivitiesarethe
twomostimportantaspectsthathavedirectimpactonyourprospectsfor
placements.Youestimatetheratiooftheimpactofdevoting1hourto
academicstotheimpactofdevoting1hourtoextra-curricularactivities
onyourplacementprospectstobe3:5.Youdecidenottospendmore
than8hoursdailyforthesetwoactivities.Moreover,youestimatethat1
hourofacademicsand1hourofextra-curricularactivitiesburn,onan
average,100and250calories,respectively,andyoucannotaffordtoburn
morethan1250caloriesforthesetwoactivitiesbasedonyouraverage
dailycalorieintake.Howmanyhoursshouldyoudevotetoacademics
andextra-curricularactivitiesdaily?
8
LPP -Formulation

9. Q1
Supposeyouconsideracademicsandextra-curricularactivitiesarethe
twomostimportantaspectsthathavedirectbearingsonyourprospects
forplacements.Youestimatetheratiooftheimpactofdevoting1hourto
academicstotheimpactofdevoting1hourtoextra-curricularactivities
onyourplacementprospectstobe3:5.Youdecidenottospendmore
than8hoursdailyforthesetwoactivities.Moreover,youestimatethat1
hourofacademicsand1hourofextra-curricularactivitiesburn,onan
average,100and250calories,respectively,andyoucannotaffordtoburn
morethan1250caloriesforthesetwoactivitiesbasedonyouraverage
dailycalorieintake.Howmanyhoursshouldyoudevotetoacademicsand
extra-curricularactivitiesdaily?
9
LPP -Formulation

10. Q1
Supposeyouconsideracademicsandextra-curricularactivitiesarethe
twomostimportantaspectsthathavedirectbearingsonyourprospects
forplacements.Youestimatetheratiooftheimpactofdevoting1hourto
academicstotheimpactofdevoting1hourtoextra-curricularactivities
onyourplacementprospectstobe3:5.Youdecidenottospendmore
than8hoursdailyforthesetwoactivities.Moreover,youestimatethat
1hourofacademicsand1hourofextra-curricularactivitiesburn,on
anaverage,100and250calories,respectively,andyoucannotafford
toburnmorethan1250caloriesforthesetwoactivitiesbasedonyour
averagedailycalorieintake.Howmanyhoursshouldyoudevoteto
academicsandextra-curricularactivitiesdaily?
10
LPP -Formulation

11. Q1
Solution-
Decisionvariables:
Objectivefunction:
Constraints:
11
LPP -Formulation

12. Q1
Solution-
Decision variables:
x
1: No. of hours devoted to academics daily
x
2: No. of hours devoted to extra-curricular activities daily
Objective function:
Maximize the impact on placement prospects
Max, Z= 3x
1+ 5x
2
Constraints:
x
1+ x
2<= 8 (hours)
100x
1+ 250x
2<= 1250 (calories)
x
1, x
2>= 0
12
LPP -Formulation

13. 13
Example: Giapetto woodcarving Inc.,
•GiapettoWoodcarving,Inc.,manufacturestwotypesofwoodentoys:
soldiersandtrains.Asoldiersellsfor$27anduses$10worthofraw
materials.EachsoldierthatismanufacturedincreasesGiapetto’s
variablelaborandoverheadcostby$14.Atrainsellsfor$21anduses
$9worthofrawmaterials.EachtrainbuiltincreasesGiapetto’s
variablelaborandoverheadcostby$10.Themanufactureofwooden
soldiersandtrainsrequirestwotypesofskilledlabor:carpentryand
finishing.Asoldierrequires2hoursoffinishinglaborand1hourof
carpentrylabor.Atrainrequires1houroffinishingand1hourof
carpentrylabor.Eachweek,Giapettocanobtainalltheneededraw
materialbutonly100finishinghoursand80carpentryhours.
Demandfortrainsisunlimited,butatmost40soldiersarebought
eachweek.Giapettowantstomaximizeweeklyprofit.Formulatea
linearprogrammingmodelofGiapetto’ssituationthatcanbeusedto
maximizeGiapetto’sweeklyprofit

14. 14
Solution: Giapetto woodcarving Inc.,
•Step1:Modelformulation
1.Decisionvariables:webeginbyfindingthedecision
variables.InanyLP,thedecisionvariablesshould
completelydescribethedecisionstobemade.Clearly,
Giapettomustdecidehowmanysoldiersandtrains
shouldbemanufacturedeachweek.Withthisinmind,
wedefine:
X
1=numberofsoldiersproducedeachweek
X
2=numberoftrainsproducedeachweek

15. 15
Solution: Giapetto woodcarving Inc.,
2.Objectivefunction:inanyLP,thedecisionmakerwantsto
maximize(usuallyrevenueorprofit)orminimize(usually
costs)somefunctionofthedecisionvariables.The
functiontobemaximizedorminimizediscalledthe
objectivefunction.FortheGiapettoproblem,wewill
maximizethenetprofit(weeklyrevenues–rawmaterials
cost–laborandoverheadcosts).
Weeklyrevenuesandcostscanbeexpressedintermsofthe
decisionvariables,X
1andX
2asfollowing:

16. 16
Solution: Giapetto woodcarving Inc.,
•Weeklyrevenues=weeklyrevenuesfromsoldiers+
weeklyrevenuesfromtrains
=27X
1+21X
2
Also,
Weeklyrawmaterialscosts=10X
1+9X
2
Otherweeklyvariablecosts=14X
1+10X
2
Therefore,theGiapettowantstomaximize:
(27X
1+21X
2)–(10X
1+9X
2)–(14X
1+10X
2)=3X
1+2
X
2
Hence,theobjectivefunctionis:
MaximizeZ=3X
1+2X
2

17. 17
Solution: Giapetto woodcarving Inc.,
3.Constraints:asX
1andX
2increase,Giapetto’sobjective
functiongrowslarger.ThismeansthatifGiapettowere
freetochooseanyvaluesofX
1andX
2,thecompany
couldmakeanarbitrarilylargeprofitbychoosingX
1and
X
2tobeverylarge.Unfortunately,thevaluesofX
1andX
2
arelimitedbythefollowingthreerestrictions(often
calledconstraints):
Constraint1:eachweek,nomorethan100hoursof
finishingtimemaybeused.
Constraint2:eachweek,nomorethan80hoursof
carpentrytimemaybeused.
Constraint3:becauseoflimiteddemand,atmost40
soldiersshouldbeproduced.

18. 18
Solution: Giapetto woodcarving Inc.,
•Thethreeconstraintscanbeexpressedintermsof
thedecisionvariablesX
1andX
2asfollows:
Constraint1:2X
1+X
2100
Constraint2:X
1+X
280
Constraint3:X
140
Note:
Thecoefficientsofthedecisionvariablesinthe
constraintsarecalledtechnologicalcoefficients.This
isbecauseitsoftenreflectthetechnologyusedto
producedifferentproducts.Thenumberonthe
right-handsideofeachconstraintiscalledRight-
HandSide(RHS).TheRHSoftenrepresentsthe
quantityofaresourcethatisavailable.

19. 19
Solution: Giapetto woodcarving Inc.,
•Sign restrictions:to complete the formulation of the
LP problem, the following question must be
answered for each decision variable: can the
decision variable only assume nonnegative values,
or it is allowed to assume both negative and positive
values?
Ifa decision variable X
ican only assume a nonnegative
values, we add the sign restriction (called
nonnegativityconstraints)
X
i0.
If a variable X
ican assume both positive and negative
values (or zero), we say that X
iis unrestricted in
sign (urs).
In our example the two variables are restricted in sign,
i.e., X
10 and X
20

20. 20
Solution: Giapetto woodcarving Inc.,
•Combiningthenonnegativityconstraintswiththe
objectivefunctionandthestructuralconstraintsyield
thefollowingoptimizationmodel(usuallycalledLP
model):
MaxZ=3X
1+2X
2(objectivefunction)
subjectto(st)
2X
1+X
2100(finishingconstraint)
X
1+X
280 (carpentryconstraint)
X
140 (soldierdemandconstraint)
X
10andX
20(nonnegativityconstraint)
Theoptimalsolutiontothisproblemis:
X
1=20,andX
2=60,Z=180

21. TYPESOFFORMULATIONPROBLEMS
AProductMixExample
ADietExample
AnInvestmentExample
AMarketingExample
ATransportationExample
ABlendExample
AMulti-PeriodSchedulingExample
ADataEnvelopmentAnalysisExample
21
LPP -Formulation

22. Q2
Supposethatafarmerhasapieceoffarmland,sayAsquarekilometers
large,tobeplantedwitheitherwheatorbarleyorsomecombinationof
thetwo.ThefarmerhasalimitedpermissibleamountFoffertilizerandP
ofinsecticidewhichcanbeused,eachofwhichisrequiredindifferent
amountsperunitareaforwheat(F1,P1)andbarley(F2,P2).LetS1be
thesellingpriceofwheat,andS2thepriceofbarley.Ifwedenotethearea
plantedwithwheatandbarleywithx1andx2respectively,thenthe
optimalnumberofsquarekilometerstoplantwithwheatvs.barleycan
beexpressedasalinearprogrammingproblem.
22
LPP -Formulation

23. Q2
Solution-
Maximize, Z= S
1x
1+ S
2x
2(maximize the revenue )
subject to x
1+x
2<A (limit on total area)
F
1x
1+ F
2x
2<F(limit on fertilizer)
P
1x
2+ P
2x
2<P(limit on insecticide)
x
1, x
2>0(cannot plant a negative area)
23
LPP -Formulation

24. Q3
CycleTrendsisintroducingtwonewlightweightbicycleframes,the
DeluxeandtheProfessional,tobemadefromaluminumandsteelalloys.
TheanticipatedunitprofitsareRs10fortheDeluxeandRs15forthe
Professional.Thenumberofkgofeachalloyneededperframeis
summarizedbelow.Asupplierdelivers100kgofthealuminumalloyand
80kgofthesteelalloyweekly.HowmanyDeluxeandProfessionalframes
shouldCycleTrendsproduceeachweek?
Kg of each alloy needed per frame
24
LPP -Formulation
Aluminum AlloySteel Alloy
Deluxe 2 3
Professional 2 4

25. Q3
Solution-
MaxZ=10x+15y
SubjectTo
2x+2y<=100(aluminumconstraint)
3x+4y<=80(steelconstraint)
x,y>0 (non-negativityconstraints)
25
LPP -Formulation

26. Q4
Ananimalfeedcompanymustproduceexactly200kgofamixture
consistingofingredientsG1andG2.TheingredientG1costsRs.3perkg
andG2costsRs.5perkg.Notmorethan80kgofG1canbeusedand
atleast60kgofG2mustbeused.Findtheminimumcostmixture.
Formulatethisasalinearprogrammingmodel.
26
LPP -Formulation

27. Q4
Solution-
Letx1=No.ofunits(inKg)ofingredientG1.
&x2=No.ofunits(inKg)ofingredientG2.
Objectivefunctionis,Minimize,Z=3x1+5x2
Subjecttoconstraints,
x1+x2=200
x1≤80
x2≥60
x1,x2≥0 27
LPP -Formulation

28. Q5
Acompanysupplyingthreetypesofpartstoanautomaticmanufacturingcompany,
purchasescastingsofthreepartsfromanearbyfoundryandperformsthreetypes
ofoperatorsbeforesellingtheseandcostperhourofthesemachinesisgiveninthe
tablebelow:
ThecostofthecastingsforA,Rs120,forBRs200,forCRs400andtheselling
priceofthesepartsisRs200,Rs350andRs500respectively.Allthepartsthatare
processedbythecompanycanbesold,Whatquantityofvariouspartsshouldthe
companyprocessforsellinginordertomaximizetheirprofits? 28
LPP -Formulation
Machine Capacity/hourCapacity/hourCapacity/hourCost/hour (Rs.)
A B C
Cutting 20 60 25 150
Drilling 40 20 40 100
Polishing 50 50 20 200

29. Q5
Solution-
Letx,y,zbethenumberofpartsthecompanyshouldprocess.
ProfitfrompartA=200–120–costof(Cutting+Drilling+Polishing)
=200–120–[(150/20)+(100/40)+(200/50)]
=200–120–14=Rs66
ProfitfrompartB=Rs118.5
ProfitfrompartC=Rs81.5
29
LPP -Formulation

30. Q5
Solution-
Max,
Z=66x+118.5y+81.5z
Subjectto:
Cuttingmachineconstraint;(x/20)+(y/60)+(z/25)≤1
Drillingmachineconstraint;(x/40)+(y/20)+(z/40)≤1
Polishingmachineconstraint;(x/50)+(y/50)+(z/20)≤1
x,y,z≥0
30
LPP -Formulation

31. Q6
TheSkyshoppromotesitsproductsfromalargecitytodifferentpartsinthestate.
TheSkyshophasbudgeteduptoRs.8,000perweekforlocaladvertising.The
moneyistobeallocatedamongfourpromotionalmedia:TVspots,newspaperads,
andtwotypesofradioadvertisements.Skyshop’sgoalistoreachthelargest
possiblehigh-potentialaudiencethroughthevariousmedia.Thefollowingtable
presentsthenumberofpotentialcustomersreachedbymakinguseofan
advertisementineachofthefourmedia.Italsoprovidesthecostper
advertisementplacedandthemaximumnumberofadsthatcanbepurchasedper
week.
31
LPP -Formulation

32. Q6
Skyshop’scontractualarrangementsrequirethatatleastfiveradiospotsbeplaced
eachweek.Toensureabroad-scopedpromotionalcampaign,managementalso
insiststhatnomorethanRs.1,800bespentonradioadvertisingeveryweek.
FormulatethisproblemasaLPP.
32
LPP -Formulation

33. Q6
Solution-
Let
X1=numberof1-minuteTVspotstakeneachweek.
X2=numberoffull-pagedailynewspaperadstakeneachweek
X3=numberof30-secondprime-timeradiospotstakeneachweek
X4=numberof1-minuteafternoonradiospotstakeneachweek
Objective:Maximizeaudiencecoverage
33
LPP -Formulation

34. Q6
Solution-
Objective:Maximizeaudiencecoverage,
Z=5,000X1+8,500X2+2,400X3+2,800X4
Subjectto:
X1<=12
X2<=05
X3<=25
X4<=20
800X1+925X2+290X3+380X4<=8000
X3+X4>=5
290X3+380X4<=1800
X1,X2,X3,X4>=0
34
LPP -Formulation