excel在运筹学中的应用1

1第一章线性规划模型（LP）§1.数学模型§2.应用举例§3.运输问题§4.任务指派问题§5.0-1变量应用2§1.线性规划数学模型Max(orMin)Z=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn(≤,≥,=)b1a21x1+a22x2+…+a2nxn(≤,≥,=)b2………………………………am1x1+am2x2+…+amnxn(≤,≥,=)bmx1,x2,…,xn≥0,orInt.orBin.s.t.•可行解—满足约束条件的解，可行方案•可行域—全体可行解（可行方案）•最优解—使目标函数取得最优的可行解X*=(x1*,x2*,…,xn*)TZ*=Z(X*)=Zmax(ormin)3§2.应用举例•Ex.总利润最大，生产计划（产品最优组合）？单件消耗量产品Ⅰ产品Ⅱ可利用资源12212资源2128资源34016资源40412单件利润23解.设生产计划x1、x2（件）总利润ZMaxZ=2x1+3x2s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12x1,x2≥0最优解X*=(4，2)TZ*=144例人事安排连续工作8小时，总人数最少，排班规则？期间时间要求1234566:~10:10:~14:14:~18:18:~22:22:~2:2:~6:≥60≥70≥60≥50≥20≥30解.设6班倒，第i班人数xi，i=1,2…6,总人数Zx1x2x3x4x5x6x661jxZMin.Int,0x30xx20xx50xx60xx70xx60xxj655443322116X*=（60,10,50,0,30,0）TZ*=1505P.108人员排程一天10个时段5个班8小时工作，每日总成本最小，如何排班？代理商个数1班2班3班4班5班要求06:-08:≥4808:-10:≥7910:-12:≥6512:-14:≥8714:-16:≥6416:-18:≥7318:-20:≥8220:-22:≥4322:-24:≥5224:-06:≥15每个代理商日成本$170$160$175$180$195x1x2x3x4x5解：设每班代理商个数xj，j=1,2…5,日总成本Z最优解（P.110）X*=(48,31,39,43,15)Z*=$30,6106P.65借贷款目前现金1百万，03~12年现金流需要，10年长贷率0.07，1年短贷率0.1，每年末现金余额≥50万，如何贷款，项目余额最大？年份年初金流长贷短贷长息短息还长还短余额至少2003-8xy010.52004-2y020.52005-4y030.520063y040.520076y050.520083y060.52009-4y070.520107y080.52011-2y090.5201210y100.5结算162115-0.42-0.2-21.38△△----Max非整数求解：Z*=2.92，整数求解：Z*=2.407建模：设长贷x，每年初短贷y1，y2，…，y10，项目结算余额Z约束：每年末余额至少0.5百万。目标：项目结算余额Z最大。约束：第1年末：1-8+x+y1≥0.5第2年末：上左-2+y2-0.07x-0.1y1-y1≥0.5第3年末：上左-4+y3-0.07x-0.1y2-y2≥0.5第4年末：上左+3+y4-0.07x-0.1y3-y3≥0.5第5年末：上左+6+y5-0.07x-0.1y4-y4≥0.5第6年末：上左+3+y6-0.07x-0.1y5-y5≥0.5第7年末：上左-4+y7-0.07x-0.1y6-y6≥0.5第8年末：上左+7+y8-0.07x-0.1y7-y7≥0.5第9年末：上左-2+y9-0.07x-0.1y8-y8≥0.5第10年末：上左+10+y10-0.07x-0.1y9-y9≥0.5目标：MAXZ=上左-x-0.07x-0.1y10-y108整理：约束：第1年末：-7+x+y1≥0.5第2年末：-9+0.93x+y2-0.1*（y1）≥0.5第3年末：-13+0.86x+y3-0.1*（y1+y2）≥0.5第4年末：-10+0.79x+y4-0.1*（y1+y2+y3）≥0.5第5年末：-4+0.72x+y5-0.1*（y1+y2+y3+y4）≥0.5第6年末：-1+0.65x+y6-0.1*（y1+y2+y3+y4+y5）≥0.5第7年末：-5+0.58x+y7-0.1*（y1+y2+y3+y4+y5+y6）≥0.5第8年末：2+0.51x+y8-0.1*（y1+y2+y3+y4+y5+y6+y7）≥0.5第9年末：0+0.44x+y9-0.1*（y1+y2+y3+y4+y5+y6+y7+y8）≥0.5第10年末：10+0.37x+y10-0.1*（y1+y2+y3+y4+y5+y6+y7+y8+y9）≥0.5变量性质：x，y1，y2，…，y10≥0，or整数目标：MAXZ=10-0.7*x-0.1*(y1+y2+y3+y4+y5+y6+y7+y8+y9+y10)9P.101资金预算各年需要资金（百万）办公楼OB宾馆H购物中心SC可获得资金（百万）第一年初第二年初第三年初第四年初40609010808080709050206025202015净现值457050如何投资项目，总净现值最大？解MaxNPV=45OB+70H+50SCs.t.40OB+80H+90SC≤25100OB+160H+140SC≤45190OB+240H+160SC≤65200OB+310H+220SC≤80OB,H,SC≤1OB,H,SC≥0最优解（P.104）OB*=0%H*=16.5%SC*=13.11%NPV*=18.11（百万）10例投资组合；50万元如何投资组合使平均年收益率最高？投资品种投资期(年)年收益(%)风险系数增长潜力(%)国库券公司债券房地产股票短期定期长期保值现金存款3106215011152520101231386120015302015100要求(平均)≤5≥13≤4≥10解.设xi为第i投资品种在总投资中的比率，年平均收益率Z(%)MaxZ=11x1+15x2+25x3+20x4+10x5+12x6+3x7s.t.3x1+10x2+6x3+2x4+x5+5x6≤511x1+15x2+25x3+20x4+10x5+12x6+3x7≥13x1+3x2+8x3+6x4+x5+2x6≤415x2+30x3+20x4+15x5+10x6≥10x1+x2+x3+x4+x5+x6+x7=1xj≥0,j=1,…,7.Z*=17%11例两个工厂生产的油漆要运给三个客户；油漆在工厂必须经过着色和调和两道工序；如何生产销售使总费用最小？运费（元/吨）建材批发站化工批发站建筑公司从工厂1180260320从工厂2250230190订单（吨）5510085工序处理时间（小时/吨）处理成本（元/小时）处理能力（小时）工厂1着色工厂1调和工厂2着色工厂2调和57463802604002506008001000120012工厂1工厂2建材化工建筑x1x2x3x4x5x6解.工厂1生产(x1+x2+x3)吨，工厂2生产(x4+x5+x6)吨总费用Z（元）着色调和着色调和MinZ=总运费+总处理成本=总运费++380(…)+260(…)+400(…)+250(…)x1+x4≥55（建材订单）x2+x5≥100（化工订单）x3+x6≥85（建筑订单）5(x1+x2+x3)≤600（厂1着色）7(x1+x2+x3)≤800（厂1调和）4(x4+x5+x6)≤1000（厂2着色）6(x4+x5+x6)≤1200（厂2调和）xj≥0,j=1,2,…,613例一个五位数的4倍（5、6、7、8倍），正好数位反转过来，求这个数；不存在、唯一、多个？解.设这个数位数的数字是abcde,这个数是Z4(10000a+1000b+100c+10d+e)=10000e+1000d+100c+10b+a0≤a,b,c,d,e≤9,整数a,e≥1MaxZ=10000a+1000b+100c+10d+eMinZ=10000a+1000b+100c+10d+eZmax=Zmin=21978（唯一）14例.某公司拟在A1…A7中选址建立门市部，要求A1A2A3至多选两个A4A5至少选一个A6A7选一个Ai需要资金bi，年获利ci，总资金B年总获利最大，如何选点？解.令xi=1(yes),xi=0(no),总利润ZMaxZ=c1x1+…+c7x7s.t.x1+x2+x3≤2x4+x5≥1x6+x7=1b1x1+…+b7x7≤Bxj=0或1，j=1…715例.6个区，每个区都可以设消防站；政府希望设置的消防站数量最少，但必须满足15分钟内赶到火警区域现场；在哪些区设消防站使总数最少？距离(分钟)1区2区3区4区5区6区1区2区3区4区5区6区010162827200243217100122721015250140x1x2x6x3x5x4解.设xi=1(Yes),0(No)总数量ZMinZ=x1+x2+x3+x4+x5+x6x1+x2≥1x1+x2+x6≥1x3+x4≥1x3+x4+x5≥1x4+x5+x6≥1x2+x5+x6≥1xj=0,1j=1,…,616P.377航班排程总成本最小，航程方案？11个航班12个可行航程方案（只有三个机组）要求1234567891011121.旧→洛1111开通2.旧→丹1111开通3.旧→西1111开通4.洛→芝22323开通5.洛→旧2355开通6.芝→丹334开通7.芝→西33334开通8.丹→旧2445开通9.丹→芝222开通10.西→旧2445开通11.西→洛22442开通成本(千元)23467578998917设12个0-1变量xj=1（取第j航程），0（不取第j航程）11个航班12个可行的航程方案（只有三个机组）约束x1x2x3x4x5x6x7x8x9x10x11x12≤31.旧→洛1111≥12.旧→丹1111≥13.旧→西1111≥14.洛→芝11111≥15.洛→旧1111≥16.芝→丹111≥17.芝→西11111≥18.丹→旧1111≥19.丹→芝111≥110.西→旧1111≥111.西→洛11111≥1成本(千元)23467578998918MinZ=2x1+3x2+4x3+6x4+…+8x11+9x12s.t.x1+x2+…+x11+x12≤3x1+x4+x7+x10≥1x2+x5+x8+x11≥1x3+x6+x9+x12≥1x4+x7+x9+x10+x12≥1x1+x6+x10+x11≥1x4+x5+x9≥1x7+x8+x10+x11+x12≥1x2+x4+x5+x9≥1x5+x8+x11≥1x3+x7+x8+x12≥1x6+x9+x10+x11+x12≥1xj=Bin.j=1,…,12最优解（P.380）x3*,x4*,x11*=1Z*=18(千元)19例.有出租车票若干，允许报销一定数额的发票，如何做？20例修污水处理站，备选的站址有3个；每年清除8万吨污染物1和6万吨污染物2；要求年运营费和年处理费总和最小。年运营费(万元)处理能力(万吨/年)水处理费(元/万吨)污水处理(吨/万吨)污染物1污染物2站址14008002008060站址23005003005040站址32504004004050解.设第i站yi=1(Yes),0(No)；处理量xi(万吨)；总费用Z(万元)MinZ=0.02x1+0.03x2+0.04x3+400y1+300y2+250y3s.t.80x1+50x2+40x3≥8000060x1+40x2+50x3≥60000x1≤800y1x2≤500y2x3≤400y3xi≥0,yi=0,1,i=1,2,3最优解Y*=(1,0,1)X*=(800,0,400)Z*=682(万元)21•例某钻井队要从s1…s10十个井位中确定5个，使总费用最少；已知si钻井费ci，要求1°要么取s1和s7，要么取s8（二居一