第三章 线性规划在工商管理中的应用(应用运筹学)).ppt

第三章建模与应用线性规划在工商管理中的应用,1市场营销中的应用2人力资源分配的问题3生产计划的问题4套裁下料问题5配料问题6投资问题,一、超级食品公司的广告媒体选择问题P93,超级食品公司某种新食品(crunchystart)全国性促销活动，该产品成功与否关系到公司的前途。营销部副总裁克莱略负责此事，上次产品促销由于考虑的因数不全而导致失败，公司总裁斯隆对此事非常重视。雇佣广告公司G；2)如果任何时候全值咨询员数量必须超过兼职咨询员数的2倍，方案如何改变？,解1）设x1=上午8:00下午4:00工作的全值咨询员数；x2=中午12:00晚上8:00工作的全职咨询员数；设x3=下午4:00午夜12:00工作的全职咨询员数。yj(j=1,2,4)为聘用在第j时段工作的兼职咨询员数minf188(x1x2x3)154(y1y2y3y4)s.t.x1y112x1x2y218x2x3y324x3y414xi0,yj0(i=1,2,3);(j=1,2,4)解得：x1=x2=x3=0；y1=12；y2=18；y3=24；y4=14。最小费用4080元2）在原模型中加入约束x12y1；x1x22y2；x2x32y3；x32y4即可解得：x1=8；x2=6；x3=10；y1=4；y2=4；y3=8；y4=4。最小费用4656元,3生产计划的产品组合问题,六、某工厂在计划期内要安排、和三种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制如下表：生产单件产品的劳动成本为20元，生产单件产品和的劳动成本均为28元。产品为公司的的主打产品，代表了公司的形象，这种产品产量要占三种产品总量的60%以上。问题：工厂应分别生产多少单位、和产品才能使工厂获利最多？,解：设x1，x2和x3分别代表三种产品的产量产品单件产品的利润为84(10212)2030元，同理产品单件产品的利润为140(1012318)2836元的单件产品利润分别为34元。目标函数：Maxz=30 x1+36x2+34x3约束条件：s.t.x1+x2+2x3260020 x1+10 x2+10 x3300030 x2+20 x34580 x20.6(x1+x2+x3)x1,x2,x30求解得：x1700，x21380；x3220。总利润为78160元,LPExample(DietProblem)饮食问题,Aprisonistryingtodecidewhattofeeditsprisoners.Theywouldliketooffersomecombinationofmilk,beans,andoranges.Theirgoalistominimizecost,subjecttomeetingtheminimumnutritionalrequirementsimposedbylaw.Thecostandnutritionalcontentsofeachfood,alongwiththeminimumnutritionalrequirementsareshownbelow.,Question:Whatshouldthedietforeachprisonerbe?,AlgebraicFormulation,Letx1=gallonsofmilkperprisoner,每个囚犯所需的牛奶数量(加仑)x2=cupsofbeansperprisoner,所需的菜豆数量(杯)x3=numberoforangesperprisoner.橘子数量MinimizeCost=$2.00 x1+$0.20 x2+$0.25x3subjecttoNiacin:VPP3.2x1+4.9x2+0.8x313mgThiamin:AB11.12x1+1.3x2+0.19x31.5mgVitaminC:32x1+93x345mgandx10,x20,x30.,3生产计划的问题,七、某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？,3生产计划的问题,解：设x1自,x2自,x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x1外,x2外分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。求单位产品的利润：利润=售价-各成本之和产品甲全部自制的x1自利润=23-(3+2+3)=15产品甲铸造外协，其余自制的x1外利润=23-(5+2+3)=13产品乙全部自制的x2自利润=18-(5+1+2)=10产品乙铸造外协，其余自制的x2外利润=18-(6+1+2)=9产品丙x3的利润=16-(4+3+2)=7可得到x1自,x2自,x3,x1外,x2外的利润分别为15、10、7、13、9元。,通过以上分析,可建立如下的数学模型:目标函数：Max15x1自+10 x2自+7x3+13x1外+9x2外约束条件：5x1自+10 x2自+7x380006x1自+4x2自+8x3+6x1外+4x2外120003x1自+2x2自+2x3+3x1外+2x2外10000 x1自,x2自,x3,x1外,x2外0解得：x1自=1600；x2自=x3=x1外=0；x2外=600利润为29400元,八、有加工设备配套约束生产计划的问题,永久机械厂生产、三种产品，均要经过A、B两道工序加工。设有两种规格的设备A1、A2能完成A工序；有三种规格的设备B1、B2、B3能完成B工序。可在A、B的任何规格的设备上加工；可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；只能在A2与B2设备上加工。数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？,解：将产品加工的设备配套方案全部列出，产品的加工方案有6种，设每种方案加工产品的数量为x1i,产品,A1,B1,A1,B2,A1,B3,A2,B1,A2,B2,A2,B3,x11,x12,x13,x14,x15,x16,产品,A1,B1,A2,B2,x21,x31,产品的加工方案有2种，每种方案数量为x2i,产品,A2,B1,x22,A1设备实际使用小时数=5(x11+x12+x13)+10 x21)设备A2实际使用小时数=7(x14+x15+x16)+9x22+12x31设备B1实际使用小时数=6(x11+x14)+8(x21+x22)；B2小时数=4(x12+x15)+11x31,加工产品的数量=x11+x12+x13+x14+x15+x16,产品的数量=x21+x22,目标函数为计算利润最大化，利润的计算公式为：利润=（销售单价原料单价）产品件数之和(每台时的设备费用设备实际使用的总台时数)之和。这样得到目标函数：Maxz=(1.25-0.25)(x11+x12+x13+x14+x15+x16)+(20.35)(x21+x22)+(2.800.5)x31300/60005(x11+x12+x13)+10 x21)321/100007(x14+x15+x16)+9x21+12x31250/40006(x11+x14)+8(x21+x21)783/70004(x12+x15)+11x31200/40007(x13+x16)经整理可得：Maxz=0.375x11+0.3024x12+0.4x13+0.4013x14+0.3277x15+0.4255x16+0.65x21+0.8611x22+0.6839x31,A1设备实际使用小时数,A2设备实际使用数,B1设备实际使用数,Maxz=0.375x11+0.3024x12+0.4x13+0.4013x14+0.3277x15+0.4255x16+0.65x21+0.8611x22+0.6839x31s.t.5(x11+x12+x13)+10 x2160007(x14+x15+x16)+x21+9x21+12x31100006(x11+x14)+8(x21+x21)40004(x12+x15)+11x3170007(x13+x16)4000 xij0,九、考虑库存与缺货的多产品动态生产计划,彩虹电子公司生产、两种电子产品，两种产品一年四个季度的需求量见下表,产品的生产成本为150元/件，库存成本为生产成本的2%；产品的生产成本为200元/件，库存成本为生产成本的2.5%。两种产品在年初的库存为100件，要求在年末库存为150，该公司每季的设备生产能力15000小时，生产产品、每件分别需4、3小时。因更换工艺装备，产品第2季度最多只能生产500件。产品允许延期交货，规定产品延期交货(缺货)成本为：产品每件6元/季，产品每件8元/季。问该公司应如何安排生产计划，在满足需求和库存要求的前提下，使总成本（生产、库存和缺货）最少。,解：设xij表示第i(i=1,2)种产品在第j(j=1,4)个季度的生产量，总成本包括生产成本，库存成本和缺货成本。设Iij为第i产品第j个季度末的库存量；Fij为第i产品第j个季度末的延期交货量，Sij为第i种产品第j个季度末的净库存量，则总成本为Min150(x11+x12+x13+x14)+200(x21+x22+x23+x24)+3(I11+I12+I13+I14)+5(I21+I22+I23+I24)+6(F11+F12+F13)+8(F21+F22+F23)生产、需求、库存的平衡方程为上季末的净库存+本季生产量=本季需求量+本季末的净库存100+x11=1500+S11；S11+x12=1000+S12；S12+x13=2000+S13；S13+x14=1200+I14；S11=I11F11；S12=I12F12；S13=I13F13；I14=150100+x21=1500+S21；S21+x22=1500+S22；S22+x23=1200+S23；S23+x24=1500+I24；S21=I21F21；S22=I22F22；S23=I23F23；I24=150,设备生产能力约束：4x1j+3x2j15000(j=1,4)第2季度产品生产约束x22500加上所有变量均0求解得：x11=1400；x12=1000；x13=2000；x14=1350；x21=2400；x22=500 x23=1200；x24=1650，I14=I24=150；S21=I21=1000，其余为0试将设备生产能力改为每季12500小时计算，会出现缺货情况,4套裁下料问题,十、某工厂要做1000套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各1根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？解：共可设计下列5种下料方案，见下表,设x1,x2,x3,x4,x5,x6,x7,x8分别为上面7种方案下料的原材料根数。这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6+x7+x8约束条件：s.t.x1+2x2+x4+x610002x3+2x4+x5+x6+3x710003x1+x2+2x3+3x5+x6+4x81000 x1,x2,x3,x4,x5,x6,x7,x80,用软件计算得出最优下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。即x1=300;x2=100；x3=0；x4=500；x5=0；x6=0；x7=0；x8=0只需900根原材料就可制造出1000套钢架。注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。如果2.9m圆钢需要10根，2.1m的圆钢需要50根，1.5m的圆钢需要20根，答案如何变化（第7种方案将选用）,5配料问题,十一、某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如右表。问：该厂应如何安排生产，使利润收入为最大？,解：设x甲j表示甲产品中原料j的含量，x乙j表示乙产品中原料j的含量，x丙j表示丙产品中原料j的含量。这样我们建立数学模型时，要考虑：甲产品的生产量：x甲1x甲2x甲3；乙产品的生产量：x乙1x乙2x乙3；丙产品的生产量：x丙1x丙2x丙3；原料1的使用量：x甲1x乙1x丙1；原料2的使用量：x甲2x乙2x丙2；原料3的使用量：x甲3，x乙3，x丙3；目标函数：利润最大，利润=收入-原料支出。,利润=总收入-总成本=甲乙丙三种产品的销售单价产品数量甲乙丙使用的原料单价原料数量，故有目标函数Max50(x甲1+x甲2+x甲3)+35(x乙1+x乙2+x乙3)+25(x丙1+x丙2+x丙3)65(x甲1+x乙1+x丙1)25(x甲2+x乙2+x丙2)35(x甲3+x乙3+x丙3）=15x甲1+25x甲2+15x甲330 x乙1+10 x乙240 x丙110 x丙3约束条件：从第1个表中有：x甲10.5(x甲1+x甲2+x甲3)x甲20.25(x甲1+x甲2+x甲3)x乙10.25(x乙1+x乙2+x乙3)x乙20.5(x乙1+x乙2+x乙3)原材料的供应限额(x甲1+x乙1+x丙1)100(x甲2+x乙2+x丙2)100(x甲3+x乙3+x丙3）60 xij0,整理得（续）目标函数：Maxz=15x甲1+25x甲2+15x甲330 x乙1+10 x乙240 x丙110 x丙3s.t.0.5x甲10.5x甲20.5x甲30（原材料1不少于50%）0.25x甲1+0.75x甲20.25x甲30（原材料2不超过25%）0.75x乙10.25x乙20.25x乙30（原材料1不少于25%）0.5x乙1+0.5x乙20.5x乙30（原材料2不超过50%）(x甲1+x乙1+x丙1)100(供应量限制）(x甲2+x乙2+x丙2)100(供应量限制）(x甲3+x乙3+x丙3）60(供应量限制）xij0,i=1,2,3;j=1,2,3求解得：x甲1=100，x甲2=50，x甲3=50。其他变量为0,Save-ItCompanyWasteReclamation回收,TheSave-ItCompanyoperatesareclamationcenterthatcollectsfourtypesofsolidwastematerialsandthentreatsthemsothattheycanbeamalgamatedinto混合asalable适于销售的product.Threedifferentgradesofproductcanbemade:A,B,andC(dependingonthemixofmaterialsused).Question:Whatquantityofeachofthethreegradesofproductshouldbeproducedfromwhatquantityofeachofthefourmaterials?,MaterialDatafortheSave-ItCompany,AlgebraicFormulation,Letxij=Poundsofmaterialjallocatedtoproductiperweek(i=A,B,C;j=1,2,3,4).MaximizeProfit=5.5(xA1+xA2+xA3+xA4)+4.5(xB1+xB2+xB3+xB4)+3.5(xC1+xC2+xC3+xC4)subjecttoMixtureSpecifications: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)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+xC4500Restrictionontreatmentcost: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).,十二、汽油混合问题。一种汽油的特性可用两种指标描述，用“辛烷数”来定量描述其点火特性，用“蒸汽压力”来定量描述其挥发性。某炼油厂有1、2、3、4种标准汽油，其特性和库存量列于表4-6中，将这四种标准汽油混合，可得到标号为1，2的两种飞机汽油，这两种汽油的性能指标及产量需求列于表4-7中。问应如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标，又使2号汽油满足需求，并使得1号汽油产量最高？（这类问题需要借助物理性质：辛烷值；蒸汽压力）,表4-6,表4-7,解：设xij为飞机汽油i中所用标准汽油j的数量(L)。目标函数为飞机汽油1的总产量：,库存量约束为：,产量约束为飞机汽油2的产量：,由物理中的分压定律，可得有关蒸汽压力的约束条件：,同样可得有关辛烷数的约束条件为：(书P50),综上所述，得该问题的数学模型为：,由软件求解得：,6投资问题,十三、资金预算问题：(数据、模型与决策P103)梦大(Think-Big)发展公司是商务房地产开发项目的主要投资商。目前，公司有机会投资下列三个建设项目：项目一：建造高层办公楼；项目2：建造宾馆；项目三：建造购物中心。每一个项目要求投资者在四个不同时期投资，在当前预付定金(adownpaymentnow)以及在一年、二年，三年后追加投资。四个时期每个项目所需的投资资金和收益的净现值见下表,项目的收益按投资者投资项目的比例来分配，梦大公司目前有2500万美元资金可供投资，预计一年后又可追加2000万美元的投资，两年后可以获得2000万美元用于投资，三年后有1500万美元可供投资，现在，梦大公司需要确定在三个项目中投资的百分比，使投资组合的收益最大。值得注意是，梦大公司各年投资金额可以累计使用，既未用完的资金可在下一年度使用。因此，在考虑可用投资金额这一资源时，用前几年累计可获得投资资金作为资源,解：设x1表示梦大公司投资办公楼项目的投资资金比例，x2投资宾馆项目的投资资金比例，x3投资购物中心项目的投资资金比例。则线性规划模型为Max45x1+70 x2+50 x3s.t.40 x1+80 x2+90 x325100 x1+160 x2+140 x345190 x1+240 x2+160 x365200 x1+310 x2+220 x380 x1，x2，x30求解得：x10；x20.16504916.5%,x3o.13106813.11%,收益总净现值1811万美元如果用每年可用投资资金作为当年资金资源约束，则x113.18%;x23.18%;x319.01%,收益总净现值1770.45万美元,SpreadsheetFormulation,十四、某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。据测定每万元每次投资的风险指数如右表：问：a)应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b)应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？,解：1）确定决策变量：连续投资问题设xij(i=15，j=14)表示第i年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量：,资金流动图如下，箭头向上表示资金在年末回收，箭头向下表示资金在年初投资：,1,1.1x11,x11,x21,x31,x41,项目A,各年初投资金额各年末资金回收额Ax11x21x31x41x511.1x111.1x111.1x111.1x111.1x11Bx12x22x32x421.25x121.25x221.25x321.25x42Cx331.4x33Dx241.55x24,2,1.1x21,1.1x31,3,4,5,6,1.1x41,1.1x51,1,1.25x12,x12,x22