运筹学习题答案(1).doc

第一章 线性规划及单纯形法（作业）1.4 分别用图解法和单纯型法求解下列线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。（1）Max z=2x1+x2St.解：图解法：OCBEDA9/48/55534由作图知，目标函数等值线越往右上移动，目标函数越大，故c点为对应的最优解，最优解为直线的交点，解之得X=(15/4,3/4)T。 Max z =33/4. 单纯形法：将上述问题化成标准形式有： Max z=2x1+x2+0x3+0x4St. 其约束条件系数矩阵增广矩阵为： P1 P2 P3 P4 P3,P4为单位矩阵，构成一个基，对应变量向，x3,x4为基变量，令非基变量x1,x2为零，找到一个初始基可行解X=(0,0,15,24)T .Cj2100基可行解及对应点C基bX1X2X3X40X31535105X=，O点0X424201421000X3301-1/23/4X=，D点2X1411/301/61201/30-1/31X23/4011/4-1/8X=，C点2X115/410-1/125/2400-1/12-7/24由于所有0且基变量中不含人工变量，故表中的可行解X=（15/4，3/4，0，0）T为最优解，代入目标函数得Max z=33/4.1.7 分别用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属哪一类。（3）Min z=4x1+x2解：这种情况化为标准形式：Max z=-4x1-x2添加人工变量y1,y2Max z=-4x1-x2+0x3+0x4-My1-My2(1) 大M法：Cj-4-100-M-MC基bX1X2X3X4Y1 Y2-MY13100101-MY2643-10013/20X441201004-4+7M-1+4M-M000-4X1111/3001/303-MY220-10-4/316/50X4305/301-1/309/5 01/3+5/3M-M04/3-7M/30-4X13/5101/509/15-1/53-1X26/501-3/50-4/53/5-20X410011-11001/50-M+8/5-M-1/5-4X12/5100-1/52/50-1X29/50103/5-1/500X3100111-1000-1/5-M+7/5-M由于所有0，故表中的基可行解X=(2/5,9/5,1,0,0,0)T为最优解，Min z=17/5.(2) 两阶段法：Min =y1+y2St.单纯形迭代法的过程如下表：Cj0000-1-1C基bX1X2X3X4Y1 Y2-1Y13100101-1Y2643-10013/20X44120100474-1000-4X1111/3001/303-1Y220-10-4/316/50X4305/301-1/309/5 05/3-10-7/300X13/5101/509/15-1/50X26/501-3/50-4/53/50X4100111-10000-1-1第二阶段，将表中y1,y2去掉，目标函数回归到Max z=-4x1-x2+0x3+0x4Cj-4-100C基bX1X2X3X4-4X13/5101/503-1X26/501-3/50-20X410011001/50-4X12/5100-1/5-1X29/50103/50X310011000-1/5由于所有0，故表中的基可行解X=(2/5,9/5,1,0,0,0)T为最优解，Min z=17/5.第二章 线性规划的对偶理论与灵敏度分析（作业）2.7给出线性规划问题：Max z=2x1+4x2+x3+x4要求：（1）写出其对偶问题；（2）已知原问题最优解为X=(2,2,4,0),试根据对偶理论，直接求出对偶问题的最优解。解：（1）对偶问题为Min=8y1+6y2+6y3+9y4(2)由互补松弛性可知：x1+x2+x3=89 为严格不等式 y4=0. 相反，其对偶问题的约束条件（1），（2），（3）的对偶变量值为非零（对偶问题的对偶即原问题），有y1=4/5,y2=3/5,y3=1即对偶问题的最优解为Y=(4/5,3/5,1,0)2.11 已知线性规划问题Max z=2x1-x2+x3先用单纯型法求出最优解，再分析在下列条件变化的情况下最优解的变化（1） 目标函数变为Max z=2x1+3x2+x3;（2） 约束右端项由变为；（3） 增添一个新的约束条件-x1+2x3.解：单纯形法求解：先化为标准形式有Max z =2x1-x2+x3+0x4+0x5系数矩阵的增广矩阵为： P1 P2 P3 P4 b初始基可行解为：x=(0,0,0,6,4)用单纯型法求解过程如下： Cj2-1100C基bX1X2X3X4X50X4611100X54-12001 Cj-Zj2-11002X16111100X51003111Cj-Zj0-3-1-20因此最优解为（x1,x2,x3,x4,x5）=(6,0,0,0,10),最优值Max z=12. (1) 目标函数改变，即系数Cj的变化，反映到最终单纯型表中得：Cj23100C基bX1X2X3X4X52X16111100X51003111Cj-Zj01-1-20 因为变量x2的检验数大于零，故继续用单纯型迭代计算得表：Cj23100C基bX1X2X3X4X52X18/3102/32/3-1/33X210/3011/31/31/3Cj-Zj00-4/3-7/3-1/3即最优解变化为（x1,x2,x3,x4,x5）=（8/3，10/3，0，0，0）（2）由上可得 B=,而= 则 =B=其反映到最终单纯型表中得：Cj2-1100C基bX1X2X3X4X52X19111100X5130-3111Cj-Zj0-3-1-20原问题对偶问题均有可行解，即最优解为（x1,x2,x3,x4,x5）=（9，0，0，0，13）.(2) 将原问题的最优解代入约束条件，因-6+02,即原问题最优解不是本例的最优解.在新的约束条件中加剩余变量得：-x2+2x3-x6=2,即x1-2x3+x6=-2.以x6为基变量，将上式反映到最终单纯型表中得：Cj2-1100C基bX1X2X3X4X5X62X161111000X5100311100X6-210-2001Cj-Zj0-3-1-200上表x1列不是单位向量，故需进行变换，得：Cj2-1100C基bX1X2X3X4X5X62X161111000X5100311100X6-80-1-101Cj-Zj0-3-1-200对偶问题为可行解，即原问题为非可行解，故用对偶单纯形迭代计算得：Cj2-1100C基bX1X2X3X4X5X62X110/312/302/301/30X522/308/302/311/31X38/301/311/30-1/3Cj-Zj-1-8/30-5/30-1/3即添加新的约束条件使得最优解变为（x1,x2,x3,x4,x5）=（10/3，0，8/3，0，22/3，0）.第七章 动态规划（作业）第八章 图与网络技术（作业）8 12求图网络中各顶点间的最短路。权矩阵：D=D=D(k)=(d(k)ij)nn=(Min)nn则：D(1)=其中D(1) =(Min)表示从Vi点到Vj点的最短路。同理，D(2)= D(3)=其中d(2)ij与d(3)ij 分别表示从Vi到Vj最多经中间点V1,V2与V1,V2,V3的最短路长。D(4)=D(5)= 如上D(5)就给出了任意两点间不论几步到达的最短路长。8.14 求图中网络最大流，边上数为（C,f）.解：从Vs出发标号，得到下图：找到一条增广链，：Vs-V3-V2-Vt且。在上修改可行流得：f2t =6+1=7.f32 =3+1=4; .fs3 =2+1=3.修改后的网络图如下：再对上图进行标号，得到下图：找到一条增广链， ：Vs-V4-V5-Vt 且。 在上修改可行流得： .f5t=3+2=5; .f45=2+2=4; .fs4=4+2=6.修改后的网络图如下：再对上图进行标号，得到下图：找到一条增广链，Vs-V4-V3-V5-Vt 且。 在上修改可行流得：f5t=5+1=6; .f35=3+1=4; .f43=2+1=3; fs4=6+1=7.修改后的网络图如下：同理，再对上图进行标号，找到一条增广链，：Vs-V1-V3-V5-Vt 且。在上修改可行流，得：f5t=6+1=7； f35=4+1=5； f13=2+1=3; fs1=3+1=4.修改后的网络图如下:再对上图标号，进行到V4时无法进行下去。上述可行流就是最大流。割集为（Vs,V1）,(Vs,V3),(V4,V3),(V4,V5),最大流量为：F=fs1+fs3+fs4=4+3+7=14.8.19 下图所示网络中，有向边旁数字为（Cij,dij）,Cij表示容量，dij表示单位流量费用，试求从Vs到Vt流值为6的最小费用流。 (图a)解：构造费用网络图，如下： （图b）L(f(0) Vs-V3-V4-Vt 为最短路。 （图c）f(1) (图d) L(f(1) )Vs-V3-V2-Vt 为最短路。 （图 e） f(2) (图f) L(f(2) )Vs-V1-V2-Vt 为最短路。 （图g）f(3)（图b）为费用图L(f(0) ，其中f 0=0为零流，最短路为Vs-V3-V4-Vt，记为0。（图c）为容量图f(1)，在0上可增加流量1=3，得新的可行流，流量f1=3,边上有序对为（Cij,fij）. (图d) 为费用图L(f(1) )，最短路为Vs-V3-V2-Vt，记为1。（图 e）为容量图，新增流量2=1，f2=4.(图f) 为费用图L(f(2) )，最短路为Vs-V1-V2-Vt，记为2。（图g）为容量图，新增流量3=2，f3=6,此流量图为最大流，即W(f(3)=6. .d (f(3)=22+25+31+14+41+33+31=37.第九章 网络计划 （作业） 9.6对下图所示网络，各项工作旁边的3个数分别为工作的最乐观时间，最可能时间和最悲观时间，确定其关键路线和最早完工时间的概率。解：根据网络图列出相应的时间表：（用公式（9.1）和（9.2）计算出各项工作的平均工时t和方差）工作ambtttR12320.33302246860.66700028107.3331.33302.6672.66712320.33302.6672.6671252.3330.667227.66725.66724640.66766012320.3336282268199.52.167101002453.8330.519.519.509101210.1670.519.522.8333.3331111019.54020.5310159.667223.33323.3330101112110.33323.333240.6672585183022281482333303696134.333350.667由表中可得时差为零的工作为（1，3），（3，4），（4，5），（5，6），（6，8），（8，10），所以关键路线为。总完工期为41天，由于关键工作为（1，3），（3，4），（4，5），（5，6），（6，8），（8，10），所以= = 3.779最早完工时间为27（最乐观时间），则最早完工时间概率为P(T27)=(-3.76)-1-(3.76)=0.0001. 9.7 某项工程各道程序时间及每天需要的人力资源如下图。图中箭头上的英文字母表示工序代号，括号内数值是该工序总时差，箭线下边数为工序时，括号内为该工序每天需要的人力数。若人力资源限制每天只有15人，求此条件下工期最短的施工方案。解：甘特图如上所示：（黑色表示（1，5）时间段网络图，红色表示（5，7）时间段移动后的网络图，绿色表示（7，8）时间段移动后的网络图）（1）第一阶段为，需求量为21人/天，在调整时对各工作按总时差递增顺序排队编号； 工作为（1，5），总时差为零，编号为1#； 工作为（1，2），总时差为1，编号为2#； 工作为（1，3），总时差为2，编号为3#； 工作为（1，4），总时差为7，编号为4#； 限制人力为15人/天，所以把（1，4）移出时间段，把（1，3）后移一天（注意到（2，5）需求量为6）。（2）第二阶段为，编号如下： 工作（5，7），总时差为0，编号为1#； 工作为（3，6），总时差为1，编号为2#； 工作为（3，7），总时差为2，编号为3#； 工作为（1，4），总时差为3，编号为4#； 限制人力为15人/天，所以把（1，4）后移3天（注意到（3，7）总时差为2，第七天完成）。（3）第三阶段为，各项工作在人力充分利用情况下，没有超过限制，直至工程结束。9.8 已知下列网络图有关数据如表，设间接费用为15元/天，求最低成本日程。工 作 代 号正 常 时 间特 急 时 间成本斜率工时（d）费用（元）工时（d）费用（元）610041201092005280203802110300000/71505180158250337525212011705011001100/41803200205130222030合 计13101755解：首先使用求网络最大流的标号法来确定关键路线： 计算出各工序的成本斜率：（1，2）：10 （