chapter2-Introduction to Linear Programming(001)

《chapter2-Introduction to Linear Programming(001)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Chapter2IntroductiontoLinearProgrammingIntroductiontoLinearProgramming•LPisatoolforsolvingoptimizationproblems.In1947,GeorgeDantzigdevelopedthesimplexalgorithmforsolvingLPproblem,sincethen,LPhasbeenusedtosolveoptimizationproblemsinindustriesasdiverseasbanking,education,petroleum,andt

2、rucking.•InasurveyofFortune500firms,85%ofthoserespondingsaidthattheyhadusedLP.LinearProgrammingProblem•Example1Giapetto’sWoodcarving,Inc.,manufacturestwotypesofwoodentoys:soldiersandtrains.Requirestwotypesofskilledlabor:carpentryandfinishing.ASoldiersellsfor$27anduses$10worthofrawmat

3、erials,eachcostsvariablelaborandoverheadby$14.requires2hoursoffinishinglaborand1hourofcarpentrylabor.Atrainsellsfor$21anduses$9worthofrawmaterials,eachcostvariablelaborandoverheadby$10.requires1houroffinishinglaborand1hourofcarpentrylabor.Eachweek,Giapettocanobtainalltheneededrawmate

4、rialbutonly100finishinghoursand80carpentryhours.Demandfortrainsisunlimited,butatmost40soldiersarebought.FormulateamathematicalmodeltomaximizeGiapetto’sweeklyprofit(revenues-costs).Solution–explorecharacteristics•DecisionVariablesGiapettomustdecidehowmanysoldiersandtrainsshouldbemanuf

5、acturedeachweek.Withthisend,wedefinex=numberofsoldiersproducedeachweek.1x=numberoftrainsproducedeachweek.2•ObjectiveFunctionThedecisionmakerwantstomaximize(usuallyrevenueorprofit)orminimize(usuallycost)somefunctionofthedecisionvariables.Thefunctioniscalledtheobjectivefunction.Solutio

6、n–explorecharacteristicsWeeklyrevenues=weeklyrevenuesfromsoldiers+weeklyrevenuesfromtrains=(dollars/soldier)(soldiers/week)+(dollars/train)(trains/week)=27x+21x12Also,Weeklyrawmaterialcosts=10x+9x12Otherweeklyvariablecosts=14x+10x12ThenGiapettowantstomaximize,(27x+21x)-(10x+9x)-(14x+

7、10x)=3x+2x12121212Solution–explorecharacteristicsWeusethevariableztodenotetheobjectivefunctionvalueofLP.Giapetto’sobjectivefunctionis,Maximizez=3x+2x12Thecoefficientofavariableintheobjectivefunctioniscalledtheobjectivefunctioncoefficientofthevariable.Solution–explorecharacteristics•C

8、onstraintsTh