《运筹学课后习题答案林齐宁版本北邮出版社.doc》由会员分享，可在线阅读，更多相关《运筹学课后习题答案林齐宁版本北邮出版社.doc（17页珍藏版）》请在三一文库上搜索。
1、No.1 线性规划1、某织带厂生产A、B两种纱线和C、D两种纱带，纱带由专门纱线加工而成。这四种产品的产值、成本、加工工时等资料列表如下： 产品 项目ABCD单位产值 (元)1681401050406单位成本 (元)4228350140单位纺纱用时 (h)32104单位织带用时 (h)0020.5工厂有供纺纱的总工时7200h，织带的总工时1200h。(1) 列出线性规划模型，以便确定产品的数量使总利润最大；(2) 如果组织这次生产具有一次性的投入20万元，模型有什么变化？对模型的解是否有影响？解：(1)设A的产量为x1，B的产量为x2，C的产量为x3，D的产量为x4，则有线性规划模型如下：m
2、ax f(x)=(168-42)x1 +(140-28)x2 +(1050-350)x3 +(406-140)x4=126 x1 +112 x2 +700 x3 +266 x4s.t. (2)如果组织这次生产有一次性的投入20万元，由于与产品的生产量无关，故上述模型只需要在目标函数中减去一个常数20万，因此可知对模型的解没有影响。2、将下列线性规划化为极大化的标准形式解：将约束条件中的第一行的右端项变为正值，并添加松弛变量x4，在第二行添加人工变量x5，将第三行约束的绝对值号打开，变为两个不等式，分别添加松弛变量x6, x7，并令，则有max-f(x)= -2 x1 -3 x2 -5()+0
3、x4 -M x5+0 x6 +0 x7s.t. 3、用单纯形法解下面的线性规划解：在约束行1,2,3分别添加x4, x5, x6松弛变量，有初始基础可行解和单纯形法迭代步骤如下：Cj 253000CBXBbx1x2x3x4x5x6bi/aij*0x461032-1100610/20x5125-1(6)3010125/6*0x6420-211/2001420/1OBJ=0zj 000000cj - zj253000Cj 253000CBXBbx1x2x3x4x5x6bi/aij*0x41705/3(10/3)0-21-1/30170.55x2125/6-1/611/201/600x62395/6
4、-11/6000-1/61OBJ=625/6zj -5/655/205/60cj - zj17/601/20-5/60Cj 253000CBXBbx1x2x3x4x5x6bi/aij*2x1341/210-3/53/10-1/1005x5197/401(2/5)1/203/200125.1250x62847/400-11/1011/20-7/201OBJ=2349/4zj 254/517/2011/200cj - zj0011/50-11/200Cj 253000CBXBbx1x2x3x4x5x6bi/aij*2x11955/813/203/81/803x3985/805/211/83/800
5、x613555/16011/4011/161/161OBJ=6865/8zj 221/239/811/80cj - zj0-11/20-9/8-11/80答：最优解为x1 =244.375, x2 =0, x3 =123.125, 剩余变量x6 =847.1875；最优解的目标函数值为858.125。No.2 两阶段法和大M法1、用两阶段法解下面问题：解：将原问题变为第一阶段的标准型第一阶段单纯形表Cj 0000-1-1CBXBbx1x2x3x4x5x6bi/aij*-1x58012-101080-1x675(3)10-10175/3*OBJ=-155zj -4-311-1-1cj - zj4
6、3-1-100Cj 0000-1-1CBXBbx1x2x3x4x5x6bi/aij*-1x5550(5/3)-11/31-1/3553/5*0x12511/30-1/301/3253OBJ=-55zj 0-5/31-1/3-11/3cj - zj05/3-11/30-4/3Cj 0000-1-1CBXBbx1x2x3x4x5x6bi/aij*0x23301-3/51/53/5-1/50x114101/5-2/5-1/52/5OBJ=0zj 000000cj - zj0000-1-1第二阶段Cj -4-600CBXBbx1x2x3x4bi/aij*-6x23301-3/51/5-4x114101
7、/5-2/5OBJ=-254zj -4-614/52/5cj - zj00-14/5-2/5答：最优解为x1 =14，x2 =33，目标函数值为254。2、用大M法解下面问题，并讨论问题的解解：第1、2行约束条件添加x4, x5松弛变量，第3行添加x6剩余变量和x7人工变量，有如下初始单纯形表和迭代步骤：Cj 101512000-MCBXBbx1x2x3x4x5x6x70x49(5)3110000x515-56150100-Mx7521100-11OBJ=-5Mzj -2M-M-M00M-Mcj - zj10+2M15+M12+M00-M0Cj 101512000-MCBXBbx1x2x3x4
8、x5x6x710x19/513/51/51/50000x52409(16)1100-Mx77/50-1/53/5-2/50-11OBJ=18-7M/5zj 106+M/52-3M/52+2M/50M-Mcj - zj09-M/510+3M/5-2-2M/50-M0Cj 101512000-MCBXBbx1x2x3x4x5x6x710x13/2139/8003/10-1/100012x33/209/1611/203/2000-Mx71/20-43/80011/20-7/20-11OBJ=33-M/2zj 1093/8+43M/801221/8+7M/165/8+3M/80M-Mcj - zj02
9、7/8-43M/800-21/8-7M/16-5/8-3M/80-M0答：最后单纯形表中检验数都小于等于0，已满足最优解判定条件，但人工变量x7仍未迭代出去，可知原问题无可行解(无解)。No.3 线性规划的对偶问题1、写出下列线性规划问题的对偶问题：(1) 解：对偶问题为 (2) 解：原问题的约束条件可改写为右式令改写后约束条件每行对应的对偶变量为y1,.,y6，则有对偶规划如下：2、写出下问题的对偶问题，解对偶问题，并证明原问题无可行解 解：对偶问题为 约束条件标准化为 有对偶问题解的单纯形表如下：Cj 1-1100CBYBby1y2y3y4y50y44-101100y53-1(1)-201
10、OBJ=0zj 00000zj - cj-11-100Cj 1-1100CBYBby1y2y3yy50y44-10(1)10-1y23-11-201OBJ=-3zj 1-120-1zj - cj0010-1Cj 1-1100CBYBby1y2y3y4y51y34-10110-1y211-31021OBJ=-7zj 2-11-1-1zj - cj100-1-1 入变量答：迭代到第三步，x1为入变量，但主列中技术系数全为负值，故对偶问题有可行解但解无界，由弱对偶定理推论可知，原问题无可行解。3、用对偶单纯形法求下面问题解：Cj 4600min( zj - cj)/ai*jCBXBbx1x2x3x4
11、ai*j00x3-80-1(-2)104,3*0x4-75-3-101OBJ=0zj 0000zj - cj-4-600Cj 4600CBXBbx1x2x3x46x2401/21-1/200x4-35(-5/2)0-1/212/5*,6OBJ=240zj 36-30zj - cj-10-30Cj 4600CBXBbx1x2x3x46x23301-3/51/54x114101/5-2/5OBJ=254zj 46-14/5-2/5zj - cj00-14/5-2/5答：最优解为x1 =14，x2 =33，目标函数值为254。No.4 线性规划的灵敏度分析1、下表是一线性规划最优解的单纯形表Cj 2
12、194000CBXBbx1x2x3x4x5x621x14101/32/301/30x5200-2/3-4/311/39x223011/3-1/30-2/3zj219101101cj - zj00-6-110-1原问题为max型，x4，x5为松驰变量，x6为剩余变量，回答下列问题：(1)资源1、2、3的边际值各是多少？(x4，x5是资源1、2的松驰变量，x6是资源3的剩余变量)(2)求C1, C2 和C3的灵敏度范围；(3)求Db1，Db2的灵敏度范围。解：(1) q1 =11, q2 =0, q3 = -1。(2) x1 , x2 为基变量，故x3 为非基变量，故(3) 同理有 No.5 运输
13、问题1、分别用西北角法、最低费用法和运费差额法，求下面运输问题(见表)的初始可行解，并计算其目标函数。(可不写步骤)2、以上题中最低费用法所得的解为初始基础可性解，用表上作业法（踏石法）求出最优解。（要求列出每一步的运费矩阵和基础可行解矩阵）销地产地B1B2B3B4B5产量A16948520A2106128730A365920940A4213614360销量2515354530解：(1) 西北角法205151025153030OBJ1415(2) 最低费用法20x143015101525530(2) 差额法51530152525530OBJ850OBJ955 运费表 (检验数zij |wij
14、)06094(15)8154-710-76-3128-67-356592069922136171436-4-4011-3迭代后的分配表xij 51530152525530OBJ850运费表 (检验数zij |wij )0609481540100641281745659132069922136101436-4-404-3答：x13=5, x14=15, x24=30, x32=15, x33=25, x41=25, x43=5, x45=30, OBJ=850。No.6 指派问题1、有4个工人。要指派他们分别完成4项工作。每人做各项工作所消耗的时间(h) 如下表，问如何分派工作，使总的消耗时间最
15、少？消耗 工作工人ABCD甲3353乙3252丙1516丁46410解：变换效率矩阵如下：3353逐(0)0*20*逐(0)0*20*3252行1030列1(0)30*1516标0*4(0)5标0*4(0)546410记0*20*6记0*20*6每行每列都有两个以上的0 未找到最优解4(0) 0*2 0*重0*(0)20*81(0)3 0*新10*3(0)5 0*4(0)5标0*4(0)51 0*2 0*6记(0)20*62637划线过程(发现有4条直线) 找到最优解答：容易看出，共有四个最优解：甲B，乙D，丙A，丁C；甲D，乙B，丙A，丁C；甲B，乙D，丙C，丁A；甲D，乙B，丙C，丁A；O
16、BJ=10。 b a 1.52.51.52.5 0.5 335(3) -0.53(2)52 -0.5(1)516* 0.546410slack2327nbour4444S*=1下面是用匈亚利算法求解的过程： b a 1212 * 03353 03(2)52 0(1)516* * 046410slack2131nbour1141S*=0.5 b a 2.53.52.53.5 -0.5335(3) -1.53(2)52 -1.5(1)516 1.546(4)10slacknbour第一个最优解：OBJ10 b a 2.53.52.53.5 -0.5335(3) -1.53(2)52 -1.515(
17、1)6 1.5(4)6410slacknbour第二个最优解：OBJ102、学生A、B、C、D的各门成绩如下表，现将此4名学生派去参加各门课的单项竞赛。竞赛同时举行，每人只能参加一项。若以他们的成绩为选派依据，应如何指派最有利？得分 课程学生数学物理化学外语A89926881B87886578C95908572D75788996解：变换效率矩阵为适用于min化问题，用96减去上面矩阵中所有元素值，742815逐302411逐3(0)17113983118行102310列1 0*16101161124变051023变(0)5323211870换211870换2118(0) 0*22(0)1610
18、52(0)137答：A物理(0) 0*1593(0)0*126B数学OBJ= 0*63231 0*6(0)20C化学3602119(0) 0*2422 0*(0)D外语24No.7 动态规划1、某公司有9个推销员在全国三个不同市场里推销货物，这三个市场里推销员人数与收益的关系如下表，做出各市场推销人员数的分配方案，使总收益最大。推销员市场012345678912032475766718290100110240506071829310411512513535061728497109120131140150解：令分配到各地区的推销员人数为决策变量xk ，k=1,2,3代表第1、2、3地区；令各地区
19、可供分配的推销员人数为状态变量sk 。最先分配给第1地区，然后第2、第3地区，则 s1=9。状态转移公式为：sk+1 = sk -xk ；目标函数为：第1阶段：第3地区， s3 有09种可能，由收益表第3行可知d(x3)单调增，故有x3 *= s3；列表如下：x3*=s30123456789f1*5061728497109120131140150第2阶段：第2地区，s2 仍有09种可能，列表如下： x20123456789x2*f2* s2090*0901101*10001012112*11111001123124*12212112101244137*13413213213201375149*
20、14714414314314301496160*15915715515415415401607171*17016916816616516516501718180181*18018017917717617617511819190190191*191*191*1901881871861852,3,4191s39876543210第3阶段：第1地区，由s1 =9， 列表如下： x1 s10123456789x1*f3*9211213218*2172152082062022012002218s29876543210答：第1地区分配2名推销员，第2 地区不分配人员，第3地区分配7名推销员，总收益为218
21、。2、设某工厂要在一台机器上生产两种产品，机器的总运转时间为5小时。生产这两种产品的任何一件都需占用机器一小时。设两种产品的售价与产品产量成线性关系，分别为(12-x1)和(13-2x2)。这里x1和x2分别为两种产品的产量。假设两种产品的生产费用分别是4x1和3x2，问如何安排两种产品的生产量使该机器在5小时内获利最大。(要求用连续变量的动态规划方法求解)解：设可用机时为状态si，先分配产品1机时，故有状态转移方程sk+1 = sk -xk (i =1,2)边界值s1 =5, s3=0目标函数为：由边界条件s3 = s2 -x2 =0，得 x2 = s2，因此有则动态规划总效果的递推方程为由
22、状态方程 s2 = s1 -x1 5-x1，代入上式得令 ，解得 x1 =3。因此，答：最优策略为第1种产品生产3件，第二种产品生产2件，5小时内最大利润为27元。No.8 最短路问题1、求下图中v1到所有点的最短路径及其长度。(要求最短路用双线在图中标出，保留图中的标记值)解：最短路及其长度如图中粗线和节点上永久标记所示，2、将上图看作无向图，写出边权邻接矩阵，用Prim算法求最大生成树，并画出该树图。解：由图可得邻接矩阵，由Prim 算法的最大生成树如下图，123456781 11(4)3 2153(5)2 34(5)126 43163(7)4 55(6)(7)5 637217 7272(
23、5)8 815答：最大生成树的权值为39。No.9 网络流问题1、求下面网络s到t的最大流和最小截，从给定的可行流开始标号法。(要求每得到一个可行流后，即每次增广之后，重新画一个图，标上增广后的可行流，再进行标号法)解：答：最大流为15，最小割截为习题课11、某工厂生产用2单位A和1单位B混合而成的成品出售，市场无限制。A和B可以在该工厂的3个车间中的任何车间生产，生产每单位的A和B在各车间消耗的工时如下表。工时消耗车间1车间2车间3A211.5B121.5可用工时100120100试建立使成品数量最大的线性规划模型。解：设车间1生产x1A单位A、生产x1B单位B；设车间2生产x2A单位A、生
24、产x2B单位B；设车间3生产x3A单位A、生产x3B单位B；则有生产安排最优化的模型如下：这是一个可分解的线性规划，这类问题就容易出现退化现象。2、某饮料工厂按照一定的配方将A、B、C三种原料配成三种饮料出售。配方规定了这三种饮料中A和C的极限成分，具体见下表，饮料品种规 格每升售价(元)需求量甲 (1)A60，C206.801500乙 (2)A15，C605.703000丙 (3)C504.50无限制A、B、C三种原料每月的供应量和每升的价格如下表。供应量(升/月)价格(元/升)A20007.00B25005.00C12004.00饮料甲、乙、丙分别由不同比例的A、B、C调兑而成，设调兑后不
25、同成分的体积不变，求最大收益的生产方案。解：设x1A为饮料甲中A的总含量 (升)，设x2A为饮料乙中A的总含量 (升)设x1B为饮料甲中B的总含量 (升)，设x2B为饮料乙中B的总含量 (升)设x1C为饮料甲中C的总含量 (升)，设x2C为饮料乙中C的总含量 (升)设x3A为饮料丙中A的总含量 (升)， 设x3B为饮料丙中B的总含量 (升)设x3C为饮料丙中C的总含量 (升)则有模型如下：3、将下列线性规划化为标准形式 4、求上题的对偶规划。 习题课21用连续型动态规划求解下题解：设分配顺序为x1, x2, x3，三阶段与分配顺序一致，逆向运算。由约束条件有状态转移方程：Sk=Sk-1/xk-
26、1第三阶段：边界条件为S4=1，所以有 ，第二阶段：S3= S2/x2，第一阶段：S2= S1/x1=27/x1，回溯得：。答：最优解为x1=3, x2=3, x3=3，min f* =9。2求下面网络的中心和中位点（图中每条边上标的是两点间的距离）。解：先求所有点间的最短距离矩阵，如右下表： Max S5712121515515388101034735577*27*1285421231128546123515107261540根据中心和中位点的定义和最大最小原则可知节点3既是中心又是中位点。3存货问题（1）某小型超市洗发水日销售量为几何分布 px=p(1p)x, x=0,1,2,。缺货损失费
27、为每瓶1元，当日售不出去经计算损失0.1元，若p=0.5，问最佳日进货量为多少？（2）某小型超市食用油日销售量为负指数分布，日均销售量统计值为100公斤，当a=1, b=0.25，求最佳日进货量。（3）若食用油日销售量为正态分布，均值为100，方差49，a, b同上，求最佳日进货量。标准正态分布表：ZF(Z)ZF(Z)0.000.5000000.750.7733730.500.6914630.800.7881450.600.7257470.850.8023380.700.7580360.900.815940解：（1）由几何分布公式，可得离散概率和累积概率如下表：日销量 i0123概率Pi0.50.250.1250.0625累积概率Fi0.50.750.8750.9375临界比： a/(a+b)=0.9091答：最佳日进3瓶洗发水。（2）由负指数分布和日均销售量100公斤，可知有概率分布临界比： a/(a+b)=1/1.25=0.8，解答：最佳日进160.94公斤食用油。（3）由正态分布，查表得 Z 0.85，x=100+70.85=105.95答：最佳日进105.95公斤食用油。