運籌學英文上課錄象課件

3IntroductiontoLinearProgramming3.1PrototypeExample3.2TheLinearProgrammingModel3.3AssumptionsofLinearProgramming3.4AdditionalExamples3.5SomeCaseStudies3.6Conclusions3IntroductiontoLinearProgr1Inthislesson:

Theteachingobjectsare:(1)Mastertheformulationoflinearprogrammingmodel(2)UnderstandtheprocedureofsolvinglinearprogrammingbyusingEXCELSOLVER

Theteachingcontentsare:(1)PrototypeExample(2)Thebasicstepsofformulatingamodeloflinearprogramming(3)SolvingalinearprogrammingbyuseEXCELSOLVER

Inthislesson:2Thedevelopmentoflinearprogramminghasbeenrankedamongthemostimportantscientificadvancesofthemid-20thcentury,andwemustagreewiththisassessment.Itsimpactsincejust1950hasbeenextraordinary.Todayitisastandardtoolthathassavedmanythousandsormillionsofdollarsformostcompaniesorbusinessesofevenmoderatesizeinthevariousindustrializedcountriesoftheworld;anditsuseinothersectorsofsocietyhasbeenspreadingrapidly.Linearprogramminginvolvesthegeneralproblemofallocatinglimitedresourcesamongcompetingactivitiesinabestpossibleway.Itusesamathematicalmodeltodescribetheproblemofconcern.Andtheremarkablyefficientsolutionproceduretothelinearprogrammingiscalledthesimplexmethod.Thedevelopmentoflinear33.1PrototypeexampleTheWKYNDORGLASSCO.produceshigh-qualityglassproducts,includingwindowsandglassdoors.Ithasthreeplants.AluminumframesandhardwarearemadeinPlant1,woodframesaremadeinPlant2,andPlant3producestheglassandassemblestheproducts.Becauseofdecliningearnings,topmanagementhasdecidedtorevampthecompany’sproductline.Unprofitableproductsarebeingdiscontinued,releasingproductioncapacitytolaunchtwonewproductshavinglargesalespotential:Product1:an8-footglassdoorwithaluminumframingProduct2:A4*6footdouble-hungwood-famedwindow

3.1PrototypeexampleTh4plantProductiontimeperbatch,hoursProductiontimeavailableperweek,hoursproduct1212310302241218Profitperbatch$3,000$5,000TheORteamgatherthefollowingproductiondata:Thequestionis:Determinewhattheproductionratesshouldbeforthetwoproductsinordertomaximizetheirtotalprofit,subjecttotherestrictionsimposedbythelimitedproductioncapacitiesavailableinthethreeplants.(Eachproductwillbeproducedinbatchesof20,sotheproductionrateisdefinedasthenumberofbatchesproducedperweek.)plantProductiontimeperbatch5QuestionAnalysis

plantProductiontimeperbatch,hoursProductiontimeavailableperweek,hoursproduct1212310302241218Profitperbatch$3,000$5,000Thedecisionvariableis:x1=?x2=?Theobjectiveismaximizetheprofit:Theconstraintsare:Plant1Plant2Plant3QuestionAnalysisplantProduct6FormulatethemodelplantProductiontimeperbatch,hoursProductiontimeavailableperweek,hoursproduct1212310302241218Profitperbatch$3,000$5,000FormulatethemodelplantProduc7AnotherExample:RegionalPlanningTHESOUTHERCONFEDERATIONKIBBUTZIMisagroupofthreekibbutizm(communalfarmingcommunities)inIsrael.Thisofficeisplanningagriculturalproductionforthecomingyear.TheagricultureoutputofeachkibbutzislimitedbyboththeamountofavailableirrigablelandandthequantityofwaterallocatedforirrigationbytheWaterCommissioner.ThesedataaregiveninTable3.8.KibbutzUsableLand(Acres)WaterAllocation(AcreFeet)123400600300600800375AnotherExample:RegionalPlan8Thecropssuitedforthisregionincludesugarbeets,cotton,andsorghum,andthesearethethreebeingconsideredfortheupcomingseason.Thesecropsdifferprimarilyintheirexpectednetreturnperacreandtheirconsumptionofwater.Inaddition,theMinistryofAgriculturehassetamaximumquotaforthetotalacreagethatcanbedevotedtoeachofthesecropsbytheSouthernConfederationofKibbutzim,asshowninTable3.9.cropMaximumquota(acres)Waterconsumption(acrefeet/acre)Netreturn($/acre)SugarbeetsCottonsorghum6005003253211,000750250Thecropssuitedforthi9Becauseofthelimitedwateravailableforirrigation,theSouthernConfederationofKibbutzimwillnotbeabletouseallitsirrigablelandforplanningcropsintheupcomingseason.Toensureequitybetweenthethreekibbutzim,ithasbeenagreedthateverykibbutzwillplantthesameproportionofitsavailableirrigableland.However,anycombinationofthecropsmaybegrownatanyofthekibbutzim.

Thequestionis:Howmanyacrestodevotetoeachcropattherespectivekibbutzimwhilesatisfyingthegivenrestrictions.TheobjectiveistomaximizethetotalnetreturntothesouthernConfederationofKibbutzimasawhole.Becauseofthelimitedwa10AnalyzeandformulatethemodelcropMaximumquota(acres)Waterconsumption(acrefeet/acre)Netreturn($/acre)SugarbeetsCottonSorghum6005003253211,000750250So,thedecisionvariablesareCropAllocationusablelandtoKibbutz123Sugarx11x12x13Cottonx21x22x23Sorghumx31x32x33Analyzeandformulatethemod11The

objectiveistomaximizetheNetReturnTheconstraintsaremorecomplicated,wedividedthemintoafewkinds1.Usablelandforeachkibbutz:2.Waterallocationforeachkibbutz:Theobjectiveistomaximizet123.Totalacreageforeachcrop:

4.Equalproportionoflandplanted:5.Nonnegativity：3.Totalacreageforeachcrop:13So,wecansee,anylinearprogrammingmodelinstituteofthreeparts:

Decisionvariables,Objectivefunction,Constraints

AndtoformulateamodeloflinearprogramminginstitutethreestepsDeterminedecisionvariablesDeterminetheobjectivefunctionDeterminetheconstraintsSo,wecansee,anylinearpro14Wecannowformulatethemathematicalmodelforthisgeneralproblemofallocatingresourcestoactivities.Inparticular,thismodelistoselectthevaluesforx1,x2,…,xnsoastoWecallthisourstandardformforthelinearprogrammingproblem.Anysituationwhosemathematicalformulationfitsthismodelisalinearprogrammingproblem.3.2TheLinearProgrammingModelWecannowformulatethe15Commonterminologyforthelinerprogrammingmodelcannowbesummarized.Thefunctionbeingmaximized,c1x1+c2x2+…+cnxniscalledtheobjectivefunction.Therestrictionsnormallyarereferredtoasconstraints.Thefirstmconstraintsarecalledfunctionalconstraints.Thexj≥0restrictionsarecallednonnegativityconstriants(or

nonnegativityconditions).ResourceResourceusageperunitofactivityAmountofresourceavailableActivity12….nContributiontoZperunitactivityCommonterminologyforth163.3SolvingLinearProgrammingbyusingEXCEL(1)Add-inExcelSolver3.3SolvingLinearProgrammin17(2)Input