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

Theteachingobjectsare:(1)Mastertheformulationoflinearprogrammingmodel(2)UnderstandtheprocedureofsolvinglinearprogrammingbyusingEXCELSOLVER

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

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

plantProductiontimeperbatch,hoursProductiontimeavailableperweek,hoursproduct1212310302241218Profitperbatch$3,000$5,000TheORteamgatherthefollowingproductiondata:Thequestionis:Determinewhattheproductionratesshouldbeforthetwoproductsinordertomaximizetheirtotalprofit,subjecttotherestrictionsimposedbythelimitedproductioncapacitiesavailableinthethreeplants.(Eachproductwillbeproducedinbatchesof20,sotheproductionrateisdefinedasthenumberofbatchesproducedperweek.)QuestionAnalysis

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

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

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

4.Equalproportionoflandplanted:5.Nonnegativity：So,wecansee,anylinearprogrammingmodelinstituteofthreeparts:

Decisionvariables,Objectivefunction,Constraints

AndtoformulateamodeloflinearprogramminginstitutethreestepsDeterminedecisionvariablesDeterminetheobjectivefunctionDeterminetheconstraintsWecannowformulatethemathematicalmodelforthisgeneralproblemofallocatingresourcestoactivities.Inparticular,thismodelistoselectthevaluesforx1,x2,…,xnsoastoWecallthisourstandardformforthelinearprogrammingproblem.Anysituationwhosemathematicalformulationfitsthismodelisalinearprogrammingproblem.3.2TheLinearProgrammingModelCommonterminologyforthelinerprogrammingmodelcannowbesummarized.Thefunctionbeingmaximized,c1x1+c2x2+…+cnxniscalledtheobjectivefunction.Therestrictionsnormallyarereferredtoasconstraints.Thefirstmconstraintsarecalledfunctionalconstraints.Thexj≥0restrictionsarecallednonnegativityconstriants(or

nonnegativityconditions).ResourceResourceusageperuni