ECS716/QMT710:OperationsResearch
PnPaezahHamzah
Part1:
WhatisLinearProgramming(LP)? GeneralformofLPmodel AssumptionsofLPmodel FormulationofLPmodel GraphicalSolution onlyforLPproblemsin2variables
Part2:
SimplexSolution ComputerSolution
2
Attheendofthisclass,studentsshouldbeable to: describethebasicapproachofLP explainthetypesofproblemsthatcanbe solvedusingLP formulateLPproblems solveLPproblemsin2variblesbythe graphicalmethod
3
Explainthemeaningoftheterms:
Linearprogramming Objectivefunction Constraints Feasiblesolutions Optimalsolution Equalityandinequality Graphicalmethod Isoprofit/isocostfunction Cornerpoint(extremepoint)
4
Linearprogrammingisamathematical programmingandanoptimizationtechnique thathasbeenwidelyusedbybusinessand industryformanyyears. Itinvolvesallocatingscarceresourcesonthe basisofagivencriterionofoptimality.
Mostoften,thiscriterioniseithermaximumprofit
orminimumcost.
5
ExamplesofproblemssolvedbyLP:
allocationofproductionfacilities,productionmix
determination,blending,manpowerallocationand assignment,personnelallocation,transportation planning,scheduling,advertisingbudgetallocation.
LPusesmathematicalmodeltodescribethe problemofconcern. Thewordlinear impliesthatallmathematical relationshipsinthemodelarelinear. Thewordprogramming doesnotreferto computerprogramming;itreferstoplanning.
6
EveryLPproblemconsistsof:
decisions thatmustbemade anobjectivetobeachieved asetofrestrictions(orconstraints)toconsider
ThegeneralLPmodelinvariablesXi forallocatingm resourceswith nconstraintscanbeformulatedasfollows: MAXIMIZE(orMINIMIZE)Z=c1X1 +c2X2 ++cnXn subjectto:a11X1 +a12X2 ++a1nXn b1 a21X1 +a22X2 ++a2nXn b2 ak1X1 +ak2X2 ++aknXn bk am1X1 +am2X2 ++amnXn bm wherei=1,,n Xi 0
theobjective function
constraints
nonnegativity constraints
Note: Allmathematicalrelationshipsarelinear. >and<relationshipsarenotallowed(sinceLPmodelisdeterministic.)
Ifallthefunctions inthemodelarelinear LinearProgramming(LP)problem. Ifallthevariables intheLPmodelareinteger IntegerLinearProgramming(ILP) problem. Ifsomeofthevariables areinteger MixedIntegerLinearProgramming(MILP) problem.
9
1.
Certainty Additivity
allparametersofthemodelareknownwithcertainty. thetotalconsumptionofeachresource,aswellastheoverall
objectivevaluearetheaggregatesoftheresourceconsumptions andthecontributionstotheproblemobjective,resultedfrom carryingouteachactivityindependently. thecontributionofeachvariableintheobjectivefunctionorits usageoftheresourcesaredirectlyproportionaltothevalueof thevariable.
2.
3.
Proportionality
4.
Divisibility
thedecisionvariablescantakeonanyfractionalvalues.
5.
Nonnegativity thedecisionvariablescantakeonanyvaluegreaterthanorequal
tozero.
10
Step1:Identifyanddefinethedecisionvariables (unknowns)oftheproblem. Step2:Writetheobjectivefunctiontobeoptimized (maximize/minimize)asalinearfunctionof thedecisionvariables. Step3:Translatetherequirements,restrictions,or wishes,thatareinnarrativeformtolinear equationsorinequalitiesintermsofthe decisionvariables. Step4:Addthenonnegativityconstraints.
11
ABCInc.producestwotypesofchandelier:Design1andDesign2. Thecriticalresourcesareavailablelaborhours,crystalsand switchesforthenextproductioncycle.Thefollowingtableoutlines usagefactorsandunitprofit:
Design1 Switch Labor Crystal UnitProfit 1 9hours 12pieces RM350 Design2 1 6hours 16pieces RM300
Thereare200switches,1566hoursoflabor,and2880piecesof crystalsavailable. FormulateanLPmodeltodeterminethequantityofeachtypeof chandeliertoproduceinordertomaximizeprofit.
12
MaxiDesignSdn.Bhd.hasbeenawardedacontracttodesignalabelforanew computerproducedbyKCComputerCompany.MaxiDesignestimatesthatat least160hourswillberequiredtocompletetheproject.Threeofthefirms graphicdesignersareavailableforassignmenttothisproject.Aida,aseniorteam leader;Bakri,aseniordesigner;andCarol,ajuniordesigner. SinceAidahasworkedonseveralprojectsforKC,themanagementhasspecified thatAidamustbeassignedwithatleast45%ofthetotalnumberofhours assignedtothetwoseniordesigners.Toprovidelabeldesigningexperiencefor Carol,Carolmustbeassignedatleast20%ofthetotalprojecttime.However,the numberofhoursassignedtoCarolmustnotexceed25%ofthetotalnumberof hoursassignedtothetwoseniordesigners.Duetootherprojectcommitments, Aidahasamaximumof50hoursavailabletoworkonthisproject. HourlysalaryratesareRM40forAida,RM30forBakri,andRM20forCarol. FormulateanLPmodeltodeterminethenumberofhourseachgraphicdesigner shouldbeassignedtotheprojectinordertominimizethetotalsalary.
13
ThereareTWOmethodstosolvebygraphing:
A.
Isoprofit/IsocostLineMethod
isoprofit linemethodformaximizationproblems. isocost linemethodforminimizationproblems.
B.
Corner(Extreme)PointMethod
forbothmaximizationandminimizationproblems.
14
Step1:Formulatetheproblem. Step2:Foreachconstraint,drawagraphofthefeasiblesolutions.
ThesolutionsetoftheLPproblemisthatregion(orsetof orderedpairs),whichsatisfiesALLtheconstraints simultaneously. Thisregioniscalledtheareaoffeasiblesolution (orfeasible region.)
Step3:Drawanobjectivefunctionline. Step4:Determinetheoptimumpoint.
15
Step4:Determinetheoptimumpoint. Formaximizationproblems:
Moveparallelobjectivefunctionlinestoward largerobjectivefunctionvalueswithoutentirely leavingthefeasibleregion.
Forminimizationproblems:
Moveparallelobjectivefunctionlinestoward smallerobjectivefunctionvalueswithoutentirely leavingthefeasibleregion.
16
Optimumpoint
Feasible Region
x
Objective Function
17
Step1:Graphtheconstraints. Step2:Locateallthecornerpointsofthegraph.
Thecoordinatesofthecornerswillbedeterminedalgebraically. Itisimportanttonotethattheoptimalpointisobtainedatthe boundaryofthefeasibleregionandfurthermoreatthecorner points. Forlinearprograms,itcanbeshownthattheoptimalpointwill alwaysbeobtainedatcornerpoints.
Step3:Determinetheoptimalvalue.
Testallthecornerpointstoseewhichoneyieldstheoptimum valuefortheobjectivefunction.
18
SolvetheABCCo.problembygraphing.
a. Ifthecompanycansellallthechandeliersitcan produce,howmanyofeachdesignshoulditmakein ordertomaximizetheprofit? b. Determinethequantityofeachresourceusedatthe optimalproductionlevel.Identifyallresourcesthatare fullyutilized.
19
Adieticianisconsideringasimplebreakfastmenu(excludingbeverages) consistingofscrambledeggandcurrypuffs,forparticipantsofan orientationprogram.Anadequateamountofthefollowingnutrientsin thebreakfast:vitaminA,vitaminB,andironmustbeincluded.Each smallscoopofscrambledeggcontains3milligramsofvitaminA,4 milligramsofvitaminB,and1milligramofiron.Eachcurrypuffcontains 3milligramsofvitaminA,2milligramsofvitaminB,and2milligramof iron.TheminimumrequirementsforvitaminA,vitaminBandironare30 milligrams,24milligramsand12milligramsrespectively.Eachscoopof scrambledeggcosts30senandeachcurrypuffcosts35sen.The dieticianwouldliketodeterminehowmuchofeachtypeoffoodtoserve inordertomeetthenutrientrequirementsandalsotominimisethetotal cost.Thefollowingtablesummarisestherelevantinformation.
20
NutrientContent(mg.) Nutrient VitaminA VitaminB Iron Unit Cost ScrambledEgg 3 4 1 30sen CurryPuff 3 2 2 35sen
Nutrient Requirement (mg.) 30 24 12
a. b. c.
Formulatealinearprogrammingmodelforthisproblem. Determinetheoptimalsolution.Whatisthelowestcostthat meetsthenutrientrequirements? Determinethequantityofeachnutrientintheoptimalsolution.
21
