Chapter04-线性规划：建模与应用

运筹学OperationsResearch,潘燕春博士深圳大学管理学院pan_yc,OperationsResearch,Chapter4.LP-FormulationandApplications,Chapter4.LinearProgramming:FormulationandApplications,第四章.线性规划：建模与应用,OperationsResearch,Chapter4.LP-FormulationandApplications,满足以下三个条件的模型称为线性规划模型每一个问题都用一组决策变量(通常非负)表示某一方案，这组决策变量的值就代表一个具体方案存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示都有一个要求达到的目标，它可用决策变量的线性函数(称为目标函数)来表示，按照问题的不同，要求目标函数实现最大化或最小化,什么是线性规划模型,Chapter4.LP-FormulationandApplications,线性规划模型的一般形式,Chapter4.LP-FormulationandApplications,什么是线性规划模型,资源分配问题(resource-allocation)：资源约束。伟恩德玻璃制品公司产品组合问题成本收益平衡问题(cost-benefit-trade-off)：收益约束。利博公司广告组合问题，大沼泽地金色年代公司的现金流问题网络配送问题(distribution-network)：确定需求约束。混合问题(mix)：多种约束。,Chapter4.LP-FormulationandApplications,线性规划问题的分类,SuperGrainCorp.Advertising-MixProblem(Section4.1)(超级食品公司的广告组合问题)ResourceAllocationProblemsj=C1,C2,C3)Minimize(最小化)Cost=$700SF1-C1+$900SF1-C2+$800SF1-C3+$800SF2-C1+$900SF2-C2+$700SF2-C3,Chapter4.LP-FormulationandApplications,subjectto(约束)Factory1:SF1-C1+SF1-C2+SF1-C3=12Factory2:SF2-C1+SF2-C2+SF2-C3=15Customer1:SF1-C1+SF2-C1=10Customer2:SF1-C2+SF2-C2=8Customer3:SF1-C3+SF2-C3=9andSij0(i=F1,F2;j=C1,C2,C3).,Chapter4.LP-FormulationandApplications,AlgebraicFormulation(数学模型),SpreadsheetFormulation(电子表格模型),Chapter4.LP-FormulationandApplications,配送网络问题,配送网络问题的函数约束是确定的需求约束，可表示为：提供的数量=需要的数量,Chapter4.LP-FormulationandApplications,ContinuingtheSuperGrainCaseStudy,DavidandClaireconcludethatthespreadsheetmodelneedstobeexpandedtoincorporatesomeadditionalconsiderations.(大卫和克莱略认为公司的电子表格模型还需要进一步扩展以增加一些考虑事项)Inparticular,theyfeelthattwoaudiencesshouldbetargetedyoungchildrenandparentsofyoungchildren.(他们尤其觉得必须将目标观众定位为儿童及他们的家长),Chapter4.LP-FormulationandApplications,Twonewgoals(两个新的目标)Theadvertisingshouldbeseenbyatleastfivemillionyoungchildren.(必须至少有500百万儿童看到该广告)Theadvertisingshouldbeseenbyatleastfivemillionparentsofyoungchildren.(必须至少有500万儿童家长看到该广告)Furthermore,exactly$1,490,000shouldbeallocatedforcents-offcoupons.(而且正好还有149万美元的预算可以分配到商家优惠卷),Chapter4.LP-FormulationandApplications,ContinuingtheSuperGrainCaseStudy,BenefitandFixed-RequirementData,Chapter4.LP-FormulationandApplications,AlgebraicFormulation,Let(假定)TV=Numberofcommercialsforseparatespotsontelevision(电视上的广告时段数目)M=Numberofadvertisementsinmagazines(杂志上的广告数目)SS=NumberofadvertisementsinSundaysupplements(星期天增刊上的广告数目)Maximize(最大化广告受众量)Exposure=1,300TV+600M+500SS,Chapter4.LP-FormulationandApplications,subjectto(约束)AdSpending(广告花费):300TV+150M+100SS4,000($thousand)PlanningCost(计划成本):90TV+30M+30SS1,000($thousand)NumberofTVSpots(TV广告时段数):TV5Youngchildren:1.2TV+0.1M5(millions)Parents:0.5TV+0.2M+0.2SS5(millions)Coupons(优惠卷):40M+120SS=1,490($thousand)andTV0,M0,SS0.,Chapter4.LP-FormulationandApplications,AlgebraicFormulation,SpreadsheetFormulation,Chapter4.LP-FormulationandApplications,TypesofFunctionalConstraints,Chapter4.LP-FormulationandApplications,混合问题,混合问题也是一类典型的线性规划问题，它包含的约束是多种多样的，即可能有资源约束，也可能有收益约束，还可能有确定需求的约束,Chapter4.LP-FormulationandApplications,TheSave-ItCompanyoperatesareclamationcenterthatcollectsfourtypesofsolidwastematerialsandthentreatsthemsothattheycanbeamalgamatedintoasalableproduct.(赛维特公司经营一个回收中心，专门从事四种固体废弃物的回收，并将回收物处理、混合成为可销售的产品)Threedifferentgradesofproductcanbemade:A,B,andC(dependingonthemixofmaterialsused)(不同的原料混合，一共可以生成3种不同等级的产品：A、B和C),Save-ItCompanyWasteReclamation,Chapter4.LP-FormulationandApplications,ProductDatafortheSave-ItCompany,Chapter4.LP-FormulationandApplications,MaterialDatafortheSave-ItCompany,Chapter4.LP-FormulationandApplications,Save-ItCompanyWasteReclamation,Whatquantityofeachofthethreegradesofproductshouldbeproducedfromwhatquantityofeachofthefourmaterials?(四种原料各应使用多少？三种不同等级的产品各应生产多少？),Chapter4.LP-FormulationandApplications,AlgebraicFormulation,Let(假定)xij=Poundsofmaterialjallocatedtoproductiperweek(i=A,B,C;j=1,2,3,4)(每周原料j分配给产品i的数量)Maximize(最大化收益)Profit=5.5(xA1+xA2+xA3+xA4)+4.5(xB1+xB2+xB3+xB4)+3.5(xC1+xC2+xC3+xC4),Chapter4.LP-FormulationandApplications,subjectto(约束)MixtureSpecifications(混合比例规定):xA10.3(xA1+xA2+xA3+xA4)xA20.4(xA1+xA2+xA3+xA4)xA30.5(xA1+xA2+xA3+xA4)xA4=0.2(xA1+xA2+xA3+xA4)xB10.5(xB1+xB2+xB3+xB4)xB20.1(xB1+xB2+xB3+xB4)xB4=0.1(xB1+xB2+xB3+xB4)xC10.7(xC1+xC2+xC3+xC4),Chapter4.LP-FormulationandApplications,AlgebraicFormulation,AvailabilityofMaterials(可获得的材料):xA1+xB1+xC13,000 xA2+xB2+xC22,000 xA3+xB3+xC34,000 xA4+xB4+xC41,000Restrictionsonamounttreated(处理的材料数量约束):xA1+xB1+xC11,500 xA2+xB2+xC21,000 xA3+xB3+xC32,000 xA4+xB4+xC4500,Chapter4.LP-FormulationandApplications,AlgebraicFormulation,Restrictionontreatmentcost(处理成本约束):3(xA1+xB1+xC1)+6(xA2+xB2+xC2)+4(xA3+xB3+xC3)+5(xA4+xB4+xC4)=30,000andxij0(i=A,B,C;j=1,2,3,4),Chapter4.LP-FormulationandApplications,AlgebraicFormulation,SpreadsheetFormulation,Chapter4.LP-FormulationandApplications,混合问题建模过程,明确问题的各种活动确定总绩效测度确定活动对绩效测度的单位贡献确定分配给各种活动的有限资源，明确每一种资源的可用量和活动的单位使用量确定各种活动可获得的收益，明确收益的最低可接受水平以及每种活动的单位收益贡献,Chapter4.LP-FormulationandApplications,判别确定的需求，明确每一种活动对需求的单位贡献输入数据单元格内容确定可变单元格(活动水平)使用输出单元