《管理运筹学》练习册答案

《管理运筹学》练习册答案 线性规划专题 【例1】 试求下述线性规划问题的对偶问题 maxZ,x，2x，3x，4x1234 ，，,x，x,x,3x,51,y1 1234 ,y2 ，，6x，7x，3x,5x,82,1234 ,y3 ，，12x,9x,9x，9x,2031234, ,x,x,0,x,0,x无限制1234 , minW,5y，8y，20y123 minW,x，x12,y，6y，12y,1,123 ,,2x，x,4y，7y,9y,212123 ,,,x，2x,6,,y，3y,9y,3 12,123,, x,4,3y1,5y，9y,4,123,, x,x,0,y无限制，y,0,y,0,12,123, 【例2】用对偶单纯形法求解线性规划问题 解:引入松弛变量x1,x2,将问题化为 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 型: Wxx max,,, 12 xxx,,2,，,4 123, xxx,,2，,6, 124, xx，,4, 15 ,xj？,0,1,2,,5j, 二、灵敏度分析 【例3】某工厂在计划期内要安排生产?、?两种产品，已知生产单位产品所需要的设备台时及 A、B两种原材料的消耗，如下表所示。 ? ? 设备 1 2 8台时 原材料A 4 0 16kg 原材料B 0 4 12kg 单位利润 2 3 应如何安排生产，时该工厂获利最多。 设x1,x2分别为计划期内?、?两种产品的产量。 这个线性规划问题的模型及求解结果如下。 运输问题 整数规划建模及求解 【例1】某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。 若10个井位的代号为s1,s2, …,s10,相应的钻探费用为c1,c2, …,c10,并且井位选择上要 满足下列限制条件: 1. 或选择s1和s7，或选择s8; 2. 选择了s3 或s4 就不能选择s5，或反过来也一样; 3. 在s5，s6，s7，s8中最多只能选两个。 试建立这个问题的整数规划模型。 解:设决策变量 1选择钻探第井位,sj,x,j 0否则, 目标函数为 10 minZ,cx,jjj,1 约束条件: 从10个可供选择的井位中确定5个井位探油，则 10 x,5,j j,1 或选择s1和s7，或选择s8可表使为 x，x,1,x，x,11878选择了s3 或s4 就不能选择s5，或反过来也一样，表示为 x，x,1,x，x,13545 在s5，s6，s7，s8中最多只能选两个，可表示为 x，x，x，x,25678 综上所述，该问题的整数规划模型为: 10 minZ,cx,jjj,1 10, x,5,j, j,1,, s.t.x，x,1,x，x,1,1835 ,x，x,1,x，x,17845, ,x，x，x，x,25678, 动态规划专题 【例1】机器负荷分配问题: 某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为 g=8u1, 其中u1为投入生产的机器数量，年完好率为a=0.7;在低负荷下生产的产量函数为 h=5y，其中y为投入生产的机器数量，年完好率为b=0.9。 假定开始生产时完好的机器数量s1=1000台，第5年度结束时完好的机器数量 s6=500台，问:每年如何安排机器在高低负荷下的生产，使在5年内生产的产品总产量最 高。 解:设阶段数k表示年度; 状态变量sk表示第k年度初拥有完好机器数; 决策变量uk表示第k年度中分配高负荷下生产 的机器数量; fk(sk):由资源量sk出发，从第k年开始到第5年结束 时所生产的产品的总产量最大值。 则状态转移方程为: s,au，bs,u，，kkkk，1 ，，,0.7u，0.9s,uk,1,2,？,5kkk ，，,,Ds,u0,u,sk段允许决策集合 kkkkk 递推关系式为 ，，，，，，,,，，fs,max8u，5s,u，f0.7u，0.9s,ukkkkkk，1kkk u,Ds，，kkk ，，fs,044 ，，0.7u，0.9s,u,500555 u1*=0, f1(s1)=29.333s1-7500 然后顺序反推 ? s1=1000, ? f1(s1)=21833(台) 最优策略为u1*= u2*= u3*= u4*=0, u5*= 4.5s5-2500 s2=0.7 u1*+0.9(s1- u1*)= 0.9 s1=900 (台) s3=0.7 u2*+0.9(s2- u2*)= 0.9 s2=810 (台) s4=0.7 u3*+0.9(s3- 0.9 s3=729 (台) u3*)= s5=0.7 u4*+0.9(s4- u4*)= 0.9 s4=656 (台) u5*=4.5×656-2500=452 (台) 前4年应把年初全部完好机器数投入低负荷生产，第5年应把452台完好机器数投入高负荷生产， 这样所得的产量最高，其最高产量为21833台。 【例2】某厂为新一年制定前四个月的生产计划，其每批产品的固定成本为3(千元)，每单位产 品生产成本为1(千元)，每单位产品每月库存费用为0.5(千元)，同时年初和4月底皆无 库存，每月产品的需求量分别为2、3、2、4单位，该厂库存容量为3单位，最大生产能力 为6单位，试确定费用最小的生产计划。 解:按4个月的顺序分为4个阶段。 sk:第k阶段初的库存量; uk:第k阶段的生产量; dk:第k阶段的需求量。 状态转移方程: s,s，u,dk，1kkk 允许条件: 4,,d,s,u,min6,d,s,3，d,s,, ,kkkikkk,,i,1 0,s,3k 成本:固定成本、变动成本、库存成本。 3，，0.5，0us当u,kkk,,vsu，，, 0.5s当u,0kk, 基本方程: 当k=4时，因要求4月底的库存量为0，即s5=0,有 s，u,d444 4月初的库存量s4只能是0，1，2，3单位，相应生产量也已确定。因而 f4(0)=v4(0,4)=7 f4(1)=v4(1,3)=6.5 f4(2)=v4(2,2)=6 f4(3)=v4(3,1)=5.5 当K=3时，有 v0,2，f05，7,,34,,，，，， ,,,,v0,3，f16，6.5，，，，34,,,, ，，f0,min,min,123,,,,，，，，v0,4，f27，634,,,, ,,,,，，，，8，5.5v0,5，f334,,,, v1,1，f0，，，，4.5，7,,,,34 ,,,,v1,2，f1，，，，5.5，6.5,,,,34 ，，f1,min,min,11.5,,,,3，，，，v1,3，f26.5，634 ,,,, ,,,,，，，，7.5，5.5v1,4，f3 34,,,, v2,0，f0，，，，1，7,,,,34 ,,,,v2,1，f1，，，，5，6.5,,,,34 ，，f2,min,min,8,,,,3，，，，v2,2，f26，634,,,, ,,,,，，，，7，5.5v2,3，f3,,34,, v3,0，f0，，，，1.5，6.5 ,,,,34,,,,，，，，，，f3,minv3,1，f1,min5.5，6,8当K=2时，有 ,,,,334,,,, ，，，，6.5，5.5v3,2，f234,,,,v0,3，f0，，，，6，12,,,,23 ,,,,v0,4，f1，，，，7，11.5,,,,23 ，，f0,min,min,16,,,,2，，，，8，8v0,5，f224,,,, ,,,,，，，，9，8v0,6，f3,,24,, v1,2，f0 ，，，，5.5，12,,,,23,,,, v1,3，f1，，，，6.5，11.5,,,,23，，f1,min,min,15.5,,,,2 ，，，，7.5，8v1,4，f224,,,, ,,,,，，，，8.5，8v1,5，f3,,24,, v2,1，f0，，，，5，12,,,,23 ,,,,v2,2，f1，，，，6，11.5,,,,23 ，，f2,min,min,15,,,,2，，，，7，8v2,3，f224,,,, ,,,,，，，，8，8v1,4，f324,,,, v3,0，f0，，，， 1.5，12,,,,23,,,, v3,1，，，，，f15.5，11.5,,,,23，，f3,min,min,13.5,,,,2 ，，，，6.5，8v3,2，f224,,,, ,,,,，，，，7.5，8v3,3，f3,,24,, 当K=1时，有 v0,2，f0，，，，5，16,,,,12,,,,v0,3，f1，，，，6，15.5,,,,12，，f0,min,min,21,,,,1，，，，v0,4，f27，1512,,,, ,,,,，，，，8，13.5v0,5，f312,,,, 从上述计算可知，最优生产计划为:1月份生产2单位，2月份生产5单位，3月份不生产，4 月份生产4单位，总费用为21单位。 思考:若无库存限制，最优生产计划, 【例3】某厂接到1、2、3月的订单分别为100、110、120件，12月底无库存。3月底仓库也不 需要库存，其存贮费用是每件每月10元，生产成本是产量的平方，要使总费用最少，求最 佳生产计划。 解:按月的顺序分为3个阶段， sk:第k阶段初的库存量; uk:第k阶段的生产量; dk:第k阶段的需求量。 状态转移方程 表示第k阶段到第3阶段的总费用， 2,，10，0usukkk ,fs，，,kk10su,0 ,kk 利用逆推法求解 当k=3时，有s3+u3-d3=0 因而 u3=120-s3 2fs,minu，10s，，,,3333 120u,,s33 2* ，，,120,s，10su,120,s3333 当k=2时，有s2+u2-d2= s3 因而 110- s2? u2?230 2fs,minu，10s，fs，，，，,,222233 110,s,u,23022 22 ,minu，10s，230,s,u，10s，u,110,,，，，，222222 110,s,u,23022 ,,，，,minhs,u222 110,s,u,23022 2 ，，，，,,fs,minu，10s，fs222233 110,s,u,23022 22,,，，，，,minu，10s，230,s,u，10s，u,110222222 110,s,u,23022 ,,，，,minhs,u222 110,s,u,23022 ，， ,hsu,222 ,u2 ，，,2u,2230,s,u，10,0222 ,s450*2 u,24当k=1时，有s1+u1-d1= s2 因而 100- s1? u1?330 2fs,minu，10s，fs，，，，,,111122 100,s,u,33011 22 ,,,,450,2s470,2s,,,,222,,,minu，10s，，，25，15s,,,,112 ,,44,,,,,,,, 100,s,u,33011 ,650,2s,2u,,211,minu，10s，，,,,11 4,,, 2670,2s,2u,,11 ，，,，，25，15s，u,100,,114,, ，，,,,minhs,u11 1 100,s,u,330 11 练习题答案 第一章 数学模型为: 1.答案:设下月生产两种产品分别为x,x吨，所获产值为Z, 12 maxZxx,1200，80012.x.x085，088,400,12, .x.x011，003,4412s.t.,.x.x004，009,3612,x,x,012, 2. 答案: 可能的下料 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 : 4尺 3尺 余料 (1) 2 0 2 (2) 1 2 0 (3) 0 3 1 minZ,x，x，x1232x，x,100122x，3x,10023x,x,x,0123 设按方案1、2、3各截取x,x,x根原料，则设在产品甲中，原料A、B、C的用量分别为x,x,x,123123 则x+x+x为甲产品的产量，其中，A原料的含量?60%，可表示为 123 x1 ,0.6x，x，x123 即 ,0.4x，0.6x，0.6x,0123 x,x,x,则x+x+x为产品的产量，其中，A原料的含量?15%，可表示为 456456 的产量，其中，A原料的含量?15%，可表示为 x4,0.15 x，x，x455 设 为甲产品的产量，其中，A原料的含量?60%，可表示为 x1,0.6 x，x，x123 即 ,0.4x，0.6x，0.6x,0 123 x,x,x,则x+x+x为产品的产量，其中，C原料的含量?50%，可表示为 789789 x9,0.5 x，x，x789 目标函数为 Z,3.40,0.50x，x，x，2.85,0.40x，x，x，2.25,0.30x，x，x，，，，，，，，，，，，123456789将以上约，，，，，，,2.00，x，，x,1.50，x，x，x,1.00，x，x，x147258369束与目标整理到一起形成该问题的线性规划模型。 第二章 1. 答案 minW,5y，8y，20y123maxW,2y，3y，5y123,y，6y，12y,1,1232y，3y，y,2,,123y，7y,9y,2123,,3y，y，4y,2,,(1) (2) 123s.t.,y，3y,9y,3s.t.,,123yyy5，7，6,4123,,,3y,5y，9y,1123,,y,y,y,0,0123,,y自由，y,0,y,0123, 2(答案 12,, Y*,,,0,0,,77,, 3(答案 最优解为 x=2/3,x=8/3,最优值为min W=10/3 12 4.答案 (1) 单纯形最优表为 c 3 1 5 0 0 b j C X x x x x x BB123450 x 3 -1 0 1 -1 15 4 5 x 3/5 4/5 1 0 1/5 6 3 R 0 3 0 0 1 -30 j 最优解:生产A、B产品均为0，生产产品6个单位，最大利润30单位。 (2) 劳动力和资源的影子价格分别为0和1。原料资源已耗尽。 若原料市场价格为0.8 元/单位,影子价格1元/单位，应适当购进原料以扩大生产。 原料最多可购进15个单位，总利润增加为15单位，净利润增加3个单位。 (3)当产品A的单位利润c?3时，最优计划不变。 3 当产品C的单位利润c?5时，最优计划不变。 3 (4)劳动力可以减少15单位，原最优计划不变。 5.答案 (a)可作为初始方案; (b)不可作为初始方案，因为填有运量的格数少于m+n-1=9个; (c)不可作为初始方案，因为填有运量的格数多于m+n-1=9个; 6(答案 产地 B B B B 产量 1234 销地 A 3 3 1 A 2 4 6 2 A 1 3 2 6 3 销量 4 3 4 4 最到运费 minZ=69 7. 答案 (1) 不考虑正、负偏差，可行域如图。 X2 30 A 20 x+3x=60 12+ d3+ d2 -+ 10 d1 d1 -d 3-+3x=40 x12 d 215x+25x=600 12 X 110 300 B 40 20 ++A点为最优点,即满意解为x=24，d=12，d=32，其余均为0。两个目标均达到最优值2230。 第三章 答案 1. (2)、(5)、(6)正确 (1)、(3)、(4)不正确 2(甲种炉建4个，乙种炉建2个，总收益为32单位。 z3(模型为:设购买甲、乙、丙货车分别为台。运输净利为，为使运输净利最大，x,x,x123满足 x，x，x,30,123,6.7x，5.0x，3.5x,150123,, 54,x，x，x,40123,33,,x,x,x,0且为整数123, 使 maxZ,4.2x，3.0x，2.3x123 T4(最优解X*= (4，1)，Z=14 T5(最优解X*= (0，0，4 )，Z=-16 6(最优分派方案 工人1?工作1; 工人2?工作3; 工人3?工作2; 工人4?工作4; 总时间154。 7( 优分派方案 机器??零件E; 机器??零件D; 机器??零件C; 机器??零件A; 零件暂时不加工，总费用10单位。 第四章 答案 1.最优路线为A?C?E?H?J 或 A?D?E?H?J 2.分配给A分店3人，B分店不分配，C分店1人。总月销售量164单位。 ***3( 最优解为最优值。 x,2,x,1,x,0,maxZ,13123 4( (1)B; C、 D 、 G 、H 、I、 L;F; K (2)A、 B、 C 5( 最优决策表: 月份 ysxkkk 1 200 200 0 2 0 0 900 3 900 900 900 4 900 900 0 ***6(最优解为，整个项目失败的概率为0.060. x,1,x,0,x,1123 第 五 章 答案 1( 这是一个求最小树问题，求得图示网络的最小树后，不在最小树上的边，可以暂 时不修铁路。这样的边有:vv，vv，vv，vv，vv，vv，vv，vv。此61116121338131489510910 题答案不唯一。注意保留下来的边有14条，最小树的权为25。 2(分配给A分店3人，B分店不分配，C分店1人。月总销售量164单位。 3(最大流如图。 V1V8，4 4 7，7 4，4 3，0 4，3 V 3 vs3，3 2，0 v t 5，3 3，3 10，7 8，7 4，4 V V 52 最小截 {vv,vv,vv} 。 s1s3s3 4(此题可用指派问题的匈牙利法求解。但在本章要求用网络最小费用最大流法求解。设x，1 x，x为三个点，y，y，y为三个点，若 x可用y加工，则在两点之间连一条边，再设一23123ij个发点x，一个收点y，在x与x，x，x之间，y与y，y，y之间各连一条边，各边的容123123量均为1，边xy的费用为b，边xx与yy的费用为0，于是可将原题化为如下的网络最iixiyjij 小费用最大流问题。 1,4 y1X 1 1,0 1,3 1，0 1,4 1,0 1,5 1，0 x y 2X 2y 1，0 1,4 1,0 X y3 3 1,5 5(最小费用最大流如下图所示。 3,0 2,0 1,1 1,0 2,1 v tv s 1,0 3,3 4,4 4,3 第 六 章 答案 1((1)Q*=548 (2)L=600包 * (3)元/天 (4)T=1.83天 f,110 *2((1)件/次 (2)L=48件 Q,101S c**s(3)元/天 f,kf,2Rcc,4.7sshsc，chs 3(订购(全年按360天计): 全年费用F=货款+存贮费F+订货费F11h1o1 =12×360×11+1/2Q×360C+n×20 1h11 2，12，20Q,,155 (件) 10.02 360，12 (次) n,,281155 f=12×360×11+1/2×155×360×0.02+28×20 1 ?48638 (元/年) 存贮水平L=8×12=96(件) 1 自行生产:全年费用F=货款+存贮费F+订货费F22h2o2 =12×360×9.6+1/2Q×360C+n×20 222h 2，12，90 2RCA,Rp0.02 ，，Q,,,,215件225,12CAh 25 360，12n ，，,,20次2215 1 f,12，360，9.6，，215，360，0.02，20，9022 ?44046(元/年) 存贮水平: L=12×13=156(件) 2 ?应自行生产，费用节约比率(48638-44046)/440466?10% 4(C=400元，存贮费率10%，全年需求量R=200,000元，每年订购一次，折扣30%，下面分0 两种情况讨论: (1) 不接受优惠，最佳订购量: R2，C0,2RC2RCV2，200000，40040000*001 Q,,,,,122VrVrVV0.1Vr11111 200000 V1全年定购次数:次 n,,5140000 V1 全年费用: 140000元 200000，，，V，0.1，5，400,20400012V1 (2) 接受优惠:V=0.7V,每次订购量为全年用量的1/4: 21 200000 V50000*1 ，全年订购次数:次 n,4Q,,224V1 全年费用: 500001*4，V，QV，0.1，n，4002222V21 150000,4，50000，0.7，，V，0.7，0.1，4，400,14335012V1 所以应接受该优惠条件。 5(R=2800罐/年,v=20元/罐,v=18元/罐,最低订购量800罐，v=15.5元/罐，最低订购量123 1000罐。季存贮费为原料价的20%， 每次订购费200元。 2，2800，200(1) 向甲厂订购:265罐 Q*,,120，4，0.20 全年费用: 2800×20+1/2×265×20×4×0.2+200×2800/265=60233 2，2800，200(2) 向乙厂订购:279罐， Q*,,218，4，0.20 订购量 应调整为800罐,全年费用: 2800×18+1/2×800×18×4×0.2+200×2800/800=56860元 2，2800，200(3) 向丙厂订购:301罐， Q*,,215.5，4，0.20 订购量应调整为1000罐，全年费用: 2800×15.5+1/2×1000×15.5×4×0.8+200×2800/1000=50160元 所以应向丙厂订购。 6(累计概率如下表: 需求量R 0 1 2 3 4 5 概率P(R) 0.05 0.10 0.25 0.35 0.15 0.10 累计概率,P(R) 0.05 0.15 0.40 0.75 0.90 1.00 ,5,,0.71,=5，,=2， ,,，5，2 Q,1Q,，，，，根据公式 PR,,PR ,,,,，,0R,0R 应选订货量3千箱。 7.各种可能情况下的利润期望值如下表: 0 1 2 3 4 5 6 7 利润期 望值 0 0.05 0.15 0.25 0.25 0.20 0.10 0 0 0 0 0 0 0 0 0 0 0 1 0 10 10 10 10 10 10 10 10 2 -4 10 20 20 20 20 20 20 19.5 3 -12 6 20 30 30 30 30 30 27.3 4 -16 -2 16 30 40 40 40 40 31.8 5 -20 -6 8 26 40 50 50 50 32.4 6 -24 -10 4 18 36 50 60 60 29.6 7 -28 -14 0 14 28 46 60 70 25 从上表可知，应选订购量为5千件。 第七章 答案 1( 选乙种方案。 2( 选甲地。 3( 大厂的期望收益为: 10×〔0.5×100+0.3×60+0.2×(-20)〕-280=360万元; 小厂的期望收益为: 10×〔0.5×25+0.3×45+0.2×55〕-140=230万元。 所以应建大厂。 4( 乐观法决策应选推销策略S。 1 5( 悲观法决策应选推销策略S。 3 6( 后悔值矩阵如下: 状况 有油 无油 方案 Q Q 开采 0 1 不开采 5 0 按最大后悔值最小准则,应选开采。 7( 按这种系数准则应选S方案。 2 8(按等可能准则应选S方案。 2 模拟1 答案 一、1.B 2.D 3.D 4.B 5.A 6.D 7.B 8.B 9.A 10.B 15333二、 x,,x,,Z,12444 三、 产地 B B B B 产量 1234 销地 A 3 3 1 A 2 4 6 2 A 1 3 2 6 3 销量 4 3 4 4 四、用分枝定界法求解: maxZ,3x1，2x2 2x，3x,14,12,2x，x,9 ,12,x,x,012, ,x,x为整数12, 五、最优路线为A?C?E?H?J 或 A?D?E?H?J 六、分配给A分店3人，B分店不分配，C分店1人。总月销售量164单位。 七、订购(全年按360天计): 全年费用F=货款+存贮费F+订货费F11h1o1 =12×360×11+1/2Q×360C+n×20 1h11 2，12，20 (件) Q,,15510.02 360，12 (次) n,,281155 f=12×360×11+1/2×155×360×0.02+28×20 1 ?48638 (元/年) 存贮水平L=8×12=96(件) 1 自行生产:全年费用F=货款+存贮费F+订货费F222o2 h =12×360×9.6+1/2Q×360C+n×20 2h22 2，12，90 2RCA,Rp0.02 ，，Q,,,,215件225,12CAh 25 360，12n，， ,,20次2215 1 f,12，360，9.6，，215，360，0.02，20，9022 ?44046(元/年) 存贮水平: L=12×13=156(件) 2 ?应自行生产，费用节约比率(48638-44046)/440466?10% 八、(,)悲观准则:选方案,。 2 (,)乐观准则:选方案,。 3 (,)折衷主义准则:选方案,。 1 (,)后悔值准则:选方案,。 1 (,)等可能准则:选方案,。 1 模 拟 试 题 2 答 案 一、1.D 2.B 3.A 4.B 5.B 6.A 7.B 8.C 9.D 10.B 二、(1)单纯形最优表为 c 3 1 5 0 0 b j C X x x x x x BB12345 0 x 3 -1 0 1 -1 15 4 5 x 3/5 4/5 1 0 1/5 6 3 R 0 3 0 0 1 -30 j 最优解:生产A、B产品均为0，生产产品6个单位，最大利润30单位。 (2) 动力和资源的影子价格分别为0和1。原料资源已耗尽。 若原料市场价格为0.8 元/单位,影子价格1元/单位，应适当购进原料以扩大生产。 原料最多可购进15个单位，总利润增加为15单位，净利润增加3个单位。 (3) 当产品A的单位利润c?3时，最优计划不变。 3 当产品C的单位利润c?5时，最优计划不变。 3 三、答案 不可作为初始方案，因为填有运量的格数少于m+n-1=9个。 四、设购买甲、乙、丙货车分别为台。运输净利为，为使运输净利最大，满足 zx,x,x123 x，x，x,30,123,6.7x，5.0x，3.5x,150123,, 54,x，x，x,40123,33,,x,x,x,0且为整数123, 使 maxZ,4.2x，3.0x，2.3x123 五、分配给A分店3人，B分店不分配，C分店1人。总月销售量164单位。 六、最大流如图。 V1V8，4 4 7，7 4，4 3，0 4，3 V 3 vs3，3 2，0 v t 5，3 3，3 10，7 8，7 4，4 最小截 {vv,vv,vv} 。 s1s3s3 VV 52 七、(1)Q*=548 (2)L=600包 * (3)元/天 (4)T=1.83天 f,110 八、大厂的期望收益为: 10×〔0.5×100+0.3×60+0.2×(-20)〕-280=360万元; 小厂的期望收益为: 10×〔0.5×25+0.3×45+0.2×55〕-140=230万元。 所以应建大厂。