运筹学课后习题集规范标准答案林齐宁版本北邮出版社

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)=(16842) X1 +(14028) X2 +(1050350) X3+(406140) X4=126 X1 +112 X2 +700 X3 +266 X4720012003x1 2x210x3 4x4s.t.2x30.5X4Xi 0,i1,2,3,420万元，由于与产品的生产量无关，20万，因此可知对模型(2)如果组织这次生产有一次性的投入故上述模型只需要在目标函数中减去一个常数的解没有影响。2、将下列线性规划化为极大化的标准形式min f (x)2xi 3x2 5x3X1 st 6X1 st |19X1X1,X2X2 X357x2 9x3167x2 5x3 | 130,

3、X3不限解：将约束条件中的第一行的右端项变为正值， 并添加松弛变量X4，在第二行添加人工变量变为两X6, X7，并令X5，将第三行约束的绝对值号打开, 个不等式，分别添加松弛变量，则有max f (x)= 2 xi3 X2 5()+0X4 M x 5+0X6 +0 X7Xi X2 X3 X3 X4s.t.6x1 7x2 9x3 9x3 x516X61319xi 7x2 5X3 5X3(1 7X2 5X3 5X3X7 13Xi,X2,X3,X3,X4,X5,X6,X703、用单纯形法解下面的线性规划f(x)2x15x23x33x12x2X3610Xi6X23x31252xiX20.5x3420s

4、.t.Xi,X2,X30,max解：在约束行1,2,3分别添加 X4, X5, X6松弛变量，有初始基础可行解和单纯形法迭代步骤如下：Cj253000CbXbbX1X2X3X4X5X6bi/ aij*0X4610321100610/20X51251(6)3010125/6*0X6420211/2001420/1OBJ=0Zj000000Cj - z j253000Cj253000CbXbbX1X2X3X4X5X6b i/ aij*0X41705/3(10/3)0211/30170.55X2125/61/611/201/60一0X62395/611/60001/61一OBJ=625/6Zj5/6

5、55/205/60Cj - z j17/601/205/60Cj253000CbXbbX1X2X3X4X5X6b i/ aij*2X1341/2103/53/101/100一5X5197/401(2/5)1/203/200125.1250X62847/40011/111/207/201一0OBJ=2349/Zj254/517/2011/2004Cj - Z j0011/5011/200Cj253000CbXbbX1X2X3X4X5X6bi/ aij*2X11955/813/203/81/803X3985/805/211/83/800X613555/011/4011/161/16116OBJ=6

6、865/Zj221/239/811/808Cj - Z j011/209/811/80答：最优解为X1 =244.375, X2 =0, X3 =123.125, 剩余变量 X6 =847.1875最优解的目标函数值为858.125。No .2两阶段法和大M法min f(x) 4x1 6X2max f (x)0x10 x2X5X6X1 2X280X12x2X3X580s.t.3x1 X275s.t. 3x1X2X4X675X1,X20X1，X2，X3，X4，X5，X60第一阶段单纯形表Cj000011CbXbbX1X2X3X4X5X6bi/ aij*1X580121010801X675(3)1

7、010175/3*OBJ=155Zj431111Cj - z j431100Cj000011CbXbbX1X2X3X4X5X6b i/ aij*1X5550(5/3)11/311/3553/5*0X12511/301/301/325 3OBJ=55Zj05/311/311/3Cj - z j05/311/304/3Cj000011CbXbbX1X2X3X4X5X6b i/ aij*0X233013/51/53/51/50X114101/52/51/52/5OBJ=0Zj000000Cj - z j000011第二阶段Cj4600CbXbbX1X2X3X4b i/ aij*6X233013/51

8、/54X114101/52/5OBJ=254Zj4614/52/5Cj - z j0014/52/51、用两阶段法解下面问题:解：将原问题变为第一阶段的标准型254。答：最优解为 X1 =14 , X2=33，目标函数值为2、用大 M法解下面问题，并讨论问题的解maxf(X)10x115X212x35x13x2X395xi6X215x315s.t.2xiX2X35Xi,X2,X30,解：第1、2行约束条件添加 X4, X5松弛变量，第 3行添加X6剩余变量和 X7 人工变量，有如下初始单纯形表和迭代步骤：Cj101512000MCbXbbX1X2X3X4X5X6X70X49(5)3110000

9、X51556150100MX752110011OBJ=5Mzj2MMM00MMcj - z j10+2M15+M12+M00M0Cj101512000MCbXbbX1X2X3X4X5X6X710X19/513/51/51/50000X52409(16)1100MX77/501/53/52/5011OBJ=18 7M/zj106+M/52 3M/52+2M/50MM5Cj - z j09 M/510+3M/2 2M/50M05Cj101512000MCbXbbX1X2X3X4X5X6X710X13/2139/8003/101/100012X33/209/1611/203/2000MX71/204

10、3/80011/207/2011OBJ=33 M/2zj1093/8+1221/8+5/8+MM43M/807M/163M/80cj - z j027/8021/85/8M043M/807M/163M/80答：最后单纯形表中检验数都小于等于0,已满足最优解判定条件，但人工变量X7仍未迭代出去，可知原问题无可行解（无解）。max f (x) 2X-13x2 5x3mi ng(y) 5y1 4y2 6y3X1X2X3 X45y1 2y222X1X34y1y 3s.t.X2X3X46s.t.y1y2y35X10,X2,X30, X4不限y1y30y10,y20, y3 不限X16X12min f (

11、x) 4x13x2 8x3x2142X16X24st. 4 X214X3812X38X312写出下列线性规划问题的对偶问题:解：对偶问题为原问题的约束条件可改写为右式不限,X2X1No.3线性规划的对偶问题解：0,X30令改写后约束条件每行对应的对偶变量为maxg(y)6yi2y214y3yist.y2y3yi,y3,y5y4y5 y60, y2,y4,y64y44380y1,.,y6，则有对偶规划如下:8y5 12y6第二种解法：将原问题的约束条件该写为X1X20 X3126104并令 X1X1 2, X2 X2 4, X3 X3 12,则原问题改写为下左式，并有对偶问题如下式，min f(

12、X ) 4x1 3x2 x18x2 10st X348X3116X1 ,X2,X30maxg(y) 8y110y2 4y3y14y23s.t , oy3 8y1,y2,y32、写出下问题的对偶问题，解对偶问题,max f(X)并证明原问题无可行解X1st.4x1 3x2X21X212x21X1X1 , X20,解：对偶问题为min g(y) y1 y?约束条件标准化为y3y1 y34s.t. y1 y2 2y3y1, y2,y3 0y1y3 y4y1 y2 2y3+y1, y2, y3, y4, y54y530有对偶问题解的单纯形表如下:Cj11100CbYbby1y2y3y4y50y4410

13、1100y531(1)201OBJ=0Zj00000ZjCj11100Cj11100CbYbby1y2y3yy50y4410(1)101y2311201OBJ=3Zj11201ZjCj00101Cj11100CbYbby1y2y3y4y51y34101101y21131021OBJ=7Zj21111ZjCj10011入变量答：迭代到第三步，X1为入变量，但主列中技术系数全为负值，故对偶问题有可行解但解无界，由弱对偶定理推论可知，原问题无可行解。3、用对偶单纯形法求下面问题6X2min f(x) 4x1X12X2st. 3x1x2X1, X280750解:Cj4600min( Zj - Cj)/

14、ai*jCbXbbX1X2X3X4ai*j <00X3801(2)104,3*0X4753101OBJ=0Zj0000Zj - C j4600Cj4600CbXbbX1X2X3X46X2401/211/200X435(5/2)01/212/5*,6OBJ=240Zj3630Zj - c j1030Cj4600CbXbbX1X2X3X46X233013/51/54X114101/52/5OBJ=254Zj4614/52/5Zj - C j0014/52/5254。答：最优解为 X1 =14 , X2=33，目标函数值为No .4线性规划的灵敏度分析Cj2194000CbXbbX1X2X3X

15、4X5X621X14101/32/301/30X52002/34/311/39X223011/31/302/31、下表是一线性规划最优解的单纯形表219101101乙11Cj Zj原问题为 max型，X4，X5为松驰变量， X6为剩余变量，回答下列问题：(1) 资源1、2、3的边际值各是多少？(X4，X5是资源1、2的松驰变量，X6是资源3的剩余变量)求C1, C2和C3的灵敏度范围;(1) q1 =11, q2 =0, q3 =X1 , X2为基变量，故求b1, b2的灵敏度范围。解：X3为非基变量，故max 4b12/3min2234/3 1/36 b11.5同理有No.5运输问题（见表）

16、的初分别用西北角法、最低费用法和运费差额法，求下面运输问题始可行解，并计算其目标函数。（可不写步骤）20 j X14301510"1525530205151025153030OBJ = 1415（2）最低费用法以上题中最低费用法所得的解为初始基础可性解，用表上作业法（踏石 法）求出最优解。（要求列出每一步的运费矩阵和基础可行解矩阵）''''''''''"地产地B1B2B3B4B5丿量A16948520A2106128730A365920940A4213614360销量2515354530解：（1

17、）西北角法51530152525530(2)差额法OBJ = 8501151530152525530迭代后的分配表 Xij OBJ = 850OBJ =955运费表(检验数Zij |Wij )0丨610 ! 914(15 i 811 5141111 J11!1i1)11 111L1-710 -17 S61-3丨118r-6 ! 71311111111!121111115 ! 6159206 ! 91922 1116117 !141136iI3!111运费表(检验数Zij|wij )0 610 ! 9 i481 ! 54010110 i 61412181丨71415 1 615913 1201r

18、6 1 91922 1 1 !610 丨 14136|311i44043答：X13 =5, X14 =15, X24 =30, X32 =15, X33 =25, X41 =25, X43 =5, X45 =30,OBJ=850。No .6指派问题1、有4个工人。要指派他们分别完成4项工作。每人做各项工作所消耗的工作ABCD甲3353乙3252丙1516丁46410时间(h)如下表，问如何分派工作，使总的消耗时间最少?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解：变换效率矩阵如下:

19、未找到最优解4(0)0*0*重0*(0)20*8II1II(0)t1310*新10*3(0)5II0*II45标0*4(0)51II0*20*6记(0)20*62637每行每列都有两个以上的划线过程（发现有4条直线）找到最优解答:容易看出，甲 D，乙B,乙 D，丙B，丙 A，丁 C;甲 B,乙 D，丙共有四个最优解：甲A，丁 C ；丁 A ;甲C,D，乙 B,丙 C, 丁 A ； OBJ=10 。12121.52.51.52.5* 0-3353335(3)03(2)52J0.50(1)5163(2)52* 046410*l 00-0.5slack2131(1)516nbo1141-0.5ur*

20、 0.546410S*=0.5slack2327nbo4444urS*=1下面是用匈亚利算法求解的过程： 0、2.53.52.53.52.53.52.53.5-0.515(1)-1.51.5slacknbour6104-0.5-1.5-1.51.5slacknbour641021第一个最优解：OBJ = 10第二个最优解：OBJ = 102、学生 A、B、C、D的各门成绩如下表，现将此4名学生派去参加各门课'得八S课程数学物理化学外语A89926881B87886578C95908572D75788996的单项竞赛。竞赛同时举行，每人只能参加一项。若以他们的成绩为选派依 据，应如何指派

21、最有利？解：变换效率矩阵为适用于min化问题，用96742815逐302411逐3（0）1711983118行102310列10*1610161124变051023变(0)-3 -23"211870换211870换2118i.-(0)-.0*-减去上面矩阵中所有元素值,312(0)161052(0)137答：A物理0*1593(0)0*126B数学OBJ=632310*6(0)20C化学36019(0)0*24220*(0)D外语2II(0)0*No .7动态规划这三个市场里推1、某公司有 9个推销员在全国三个不同市场里推销货物,销员人数与收益的关系如下表，做出各市场推销人员数的分配

22、方案，使总收 益最大。推销员市场、*012345678912032475766718290100110240506071829310411512513535061728497109120131140150解：令分配到各地区的推销员人数为决策变量2、3地区；令各地区可供分配的推销员人数为状态变量 区，然后第 2、第3地区，则状态转移公式为：Sk+1 = Sk Xk目标函数为：xk , k=1,2,3 代表第 1、Sk。最先分配给第s 1 =9 O第1阶段：第3地区，S3有09种可能，由收益表第3行可知单调增，故有 X3 *= S3 ；列表如下：123d (X3)X3*=S3fi*50617284

23、97109120131140150第2阶段：第2地区，S2仍有09种可能，列表如下:、S2-0123456789X2*f2*S390f、101* 一. 100)、112*r、111 工。f124* J 122 ''-.121 、'121 137*134'- .J32"'" 132 0 ” .- J、 f '、149* . 147'-.144- 143160*、. 159 ”r1.57155% , r - d . .0.171* - 1沁 *169 '''168180'-M81*180 &

24、#39;180190、. 190191* 191*132、"143、143“54、15牛、f孑66、165'r179 ,177 -191*1901881871861851 严 7、；165f» 1.6.5176、1761752,3,4901011121241371491601711811919876543210第3阶段：第1地区，由S1 =9 , 列表如下:71、S10123456789X1*f3*9211213218*2172152082062022012002218S29876543210答：第1地区分配 2名推销员，第 2地区不分配人员，第3地区分配 7名推销

25、员，总收益为218。2、设某工厂要在一台机器上生产两种产品，机器的总运转时间为5小时。生产这两种产品的任何一件都需占用机器一小时。设两种产品的售价与产品产量成线性关系，分别为 (12 X1)和(13 的产量。假设两种产品的生产费用分别是 的生产量使该机器在5小时内获利最大。2X2)。这里X1和X2分别为两种产品4X1和3x2，问如何安排两种产品(要求用连续变量的动态规划方法求解)解：设可用机时为状态Si，先分配产品1机时，故有状态转移方程Sk+1 = s k Xk(i =1,2)边界值目标函数为:Si =5, S3=0f2 max( 12 x1 )x12max( 8x1x1 )4x1(13 2

26、x2 )x2 3x2(10X2 2x|)由边界条件S3 = S2 X2 =0，得 X2 = S2，因此有2 2f1 (s2)10x2 2x210s2 2s2则动态规划总效果的递推方程为f2 (Xl)max( 8x1X12)f1 (S2)由状态方程S2 = Sif2 (Xi)maX( 8x1X, 0X1 = 5max( 8X1N 0X12)(10S2 2s2)X1，代入上式得xf) 10(5 X1) 2(5 X1)2max18x1 3x12为0，解得 Xi =3。因此,f2答：最优策略为第18 3 3 9271种产品生产 3件，第二种产品生产2件，5小时内最大利润为 27元。No .8 最短路问

27、题1、求下图中V1到所有点的最短路径及其长度。(要求最短路用双线在图中标出，保留图中的标记值)解：最短路及其长度如图中粗 线和节点上永久标记所示,2、将上图看作无向图，写出 边权邻接矩阵，用 Prim算法 求最大生成树，并画出该树 图。解：由图可得邻接矩阵，由 Prim 算法的最大生成树如 下图，答：最大生成树的权值为39。No .9 网络流问题1、求下面网络 s到 求每得到一个可行流后, 行流，再进行标号法t的最大流和最小截，从给定的可行流开始标号法。即每次增广之后，重新画一个图，标上增广后的可解:答:最大流为15，最小割截为No .10随机服务系统：输入过程1、对一服务系统进行观察，总观察

28、时间为 数为40人，顾客累计的排队等待时间为 间为79.6分钟，求(1) 系统中平均排队长度；(2) 平均同时接受服务的人数。解：总观察时间为T=102.7 分钟，累计到达人数t = 40/ T=0.3895 人 /分钟102.744.8分钟，到达系统的累计人 分钟，顾客累计的服务时由题意可知由little 公式,=44.8/102.7=0.436=79.6/102.7=0.775答:平均排队队长 0.436人，平均同时接受服务的人数为0.775 人。某选举站对甲、乙二人进行选举，选票中只能选其中一人才有效。假设投票的人流服从泊松分布，投甲票的人的到达率为1 =4人/小时，投乙票的人的到达率为

29、2 =2人/小时；再假设所有投票人的票都是有效的，而选举结果的统计是在一个与选民不见面的屋里与投票过程同时进行的。问选举开始后半小时统计结果为：(1)甲得三票，乙得1票的概率；总票数为5的概率；(3) 甲得全票的概率。解:(1 )假设投甲、乙票的人流不相关，则有3P 甲 3(1/2) P 乙 1(1/2)=(4 1/2) e 4 1/2某自动交换台有 4条外线，打外线的呼叫强度为2次/分钟，为泊松流，平均通话时长为2分钟。当4条外线全忙时，用户呼叫将遇忙音。假设用户遇忙音后立即停止呼叫。问(1) 用户拨外线遇忙的概率为多大？(2) 一小时内损失的话务量为多少？(3) 外线的利用率为多少？ 已知

30、损失制系统， n =4，遇忙的概率为 B=P4 =0.31一小时内损失的话务量=外线利用率为过负荷100%时，外线利用率为 某车间机器发生故障为一泊松流，平均4台/小时。车间只有一名维修工， 1/2=0.066;3!1P,(1/2)(6 1/2) e 6 1/22.025e 平均7分钟处理一台故障。若为该维修工增加一特殊工具可使平均故障 处理时间降到 5分钟，但这一特殊工具的使用费用为5元/分钟。机器故0.1008;5!甲得全票的事件为投乙票的人一个未来而投甲票的人至少来一个，即1 2P 乙 0(1 P 甲 0)= e (1 e )0.368 (10.135)0.318 oNo.11随机服务系

31、统：标准服务系统(4)过负荷为100%时，外线的利用率为多少?=2次/分钟，分钟， =4erl ，解:(1)2、B =1.24erl障停工每台每分钟损失5元，问购置这台特殊工具是否合适？分钟,解：该系统可认为是M/M/1 无限源等待制， 已知 =4台/小时，分钟； 、分别为增加特殊工具前后修复一台机器故障的平均用时。先求增加特殊工具前后每台机器的平均故障停机历时（等待时间+维修时间），由单服务员等待系统的平均队长公式有：由Little 公式得,小时）=13.125 分钟，分钟，C1=5 Wd1 =65.625 元；C2=5 Wh+5 Wd2 =62. 5=0.875/4=0.21875（=0.

32、 5/4=0.125（ 小时）=7.5则不引入特殊工具时每台故障的总费用为 而引入特殊工具时每台故障的总费用为元；答：购置特殊工具是合适的。3、有M/M/ n : / /FIFO（先到先服务）系统，输入业务量为，求当n =1,2,3时的等待概率D ,和平均逗留队长Ld的公式。解：由爱尔兰等待公式n =1时，D=,n=2时，D =n=3时，D =No .12随机服务系统,Ld =特殊服务系统1、Ld =，Ld =F面是四个点间的双向业务量矩阵fij和距离矩阵dij1一5641011125一20210123621.5311014401.5一4121034fij1234dij1 2所谓双向业务量 f

33、ij，它表示i呼叫j的业务量与 j呼叫i的业务量之和，因此有 路是无向网路，各点间的电路群都是双向电路， 叫服务。假设每条电路单位长度的费用为 接口费用为 1单位。(1) 根据业务量矩阵求最佳的骨干线路网， (电路数)，要求各线束的呼损小于fij = fji。根据双向业务量所得的网 可同时为电路两端的用户呼1单位，汇接局的交换机每条电路并求骨干线路各点间线束容量0.01，并计算全网费用。计算此时网路(2) 若在不存在骨干电路的点对间开设独立的直达电路群， 中各点对间的线束容量及全网费用，仍要求各线束的呼损小于(3) 若在不存在骨干电路的点对间开设高效直达电路群， 计算此时网路中各点对间的线束容

34、量及全网费用， 损小于0.01 。解：(1)由流量矩阵fij可得最大生成树如下图，显然节点 形结构，即为骨干电路，点间路由表如下矩阵所示。1 20.01。其呼损小于0.3 ,要求骨干线束的呼1为汇接局，该树为星1-21-31-42-132-143-14123434由路由表可计算骨干电路上的双向业务流量:F12 = f 12+ f23 + f24 =5+2+0=7erl,F14 = f 14 + f24 + f34 =4+0+1.5=5.5erlFi3 = fi3 + f 23 + f 43 =6+2=1.5=9.5erl.该网路结构是完全的汇接制，骨干电路仍是全利用度的，根据 务等级要求，查爱

35、尔兰损失表可得B<0.01 的服n 12=14, n 13=17, n 14 =12 ,由此可计算出全网费用为C1 =2(14+17+12)=86 若在节点(2-3)和(3-4)间开独立的直达电路，网路如下图，只有节点(2-4)间需转接，但f24=0，故该网中没有转接业务量。查表结果(Fj, nj)标于图上。由此可计算出全网费用为C2 =2 (11 + 13+10)+ (7+6)=81。 若在节点(2-3)和(3-4)间开高效直达电路，网路结构仍如上图，但骨干电路(1-2), (1-3), (1-4) 上存在节点(2-3)和(3-4)间的溢流，由此它是一个部分 利用度系统，需要利用Wil

36、k inson等效流理论来作计算。首先计算高效电路,因为它们是全利用度的，由B<0.3，查表得n 23 =3, n 34 =3求(2,3)和(3,4)的溢出话务量，有同理有下面求(1-2),(1-3),(1-4)上的等效流和所需电路数,骨干电路(1,2)ni2上的业务流为等效流为查表得 n + N=12，故 N=120.3114=11.6886 ，取N=12 ，即 n 12=12 。骨干电路(1,4)n14上的业务流为等效流为查表得 n+ N=10，取N=10，即骨干电路 (1,3)，n13上的业务流为ni4 =10 。(有两个溢流)等效流为查表得 n + N =14，取ni3 =14

37、。N=14，即所得网路配置入右图，骨干电路上标的是(Aw , w2)及电路数。全网费用为C3 =2(12+14+10)+(3+3)=78经比较设置高效电路的网路配置最优。答:No.13 存储论某工厂每年需某种原料价k的关系为1000kg，一次定购费为200元，定购量 Q与单5001000已知原料存储费也与< 500kg<1000kgQ,Q有关k1 =2 元 /kgk2 =1.5 元 /kgk3 =1.2 元/kg500Q < 500kgQ <1000kgQ,Cs1 =2 元/kg.年元/kg.年元/kg.年C(Q m )。Cs2 =1.5Cs3 =1.21000kg求最

38、佳订货量Qm，并求该订货量下的全年总费用解：已知 D=1000 公斤/年，Cd =200 元，Cs如题意;(1)用公式先求 Q01, Q02 , Q03，< 500 公斤，(落入该批量价区间)< 1000 公斤,（落入该批量价区间）< 1000 公斤,（落在该批量价区间外） 计费各方案年费用Ci ,因为Q01, Q02 都落入各自适用批量价区间，故元而按第三批量段购买，最少购买1000公斤，故答：最佳订货量为每次1000公斤，全年总费用（含购料费）为2000元。习题课11、某工厂生产用 2单位A和1单位B混合而成的成品出售，市场无限制。A和B可以在该工厂的3个车间中的任何车间生产，生产每单位的A和B这是一个可分解的线性规划,这类问题就容易出现退化现象。2、某饮料工厂按照一定的配方将A、B、C三种原料配成三种饮料出售。配在各车间消耗的工时如下表。工时消耗车间1车间2车间3A211.5B121.5可用工时100120100试建立使成品数量最大的线性规划模型。解：设车间1生产X1A单位A、生产X1B单位B ；设车间2生产X2A单位A、生产X2B单位B ；设车间3生产X3A单位A、生产X3B单位B ；则有生产安排最优化的