管理运筹学B

管理运筹学B第1次作业（注意：若有主观题目，请按照题目，离线完成，完成后纸质上交学习中心，记录成绩。在线只需提交客观题答案。)本次作业是本门课程本学期的第1次作业，注释如下：二、判断题(判断正误，共14道小题)1.判断正误线性规划问题的一般模型中不能出现等式约束。正确答案：说法错误解答参考：2.在线性规划模型的标准型中,bj（j=1，2，…m）一定是非负的。正确答案：说法正确解答参考：3.判断正误线性规划问题的基本解一定是基本可行解正确答案：说法错误解答参考：4.线性规划问题的最优解只能在可行域的顶点上达到。正确答案：说法错误解答参考：5.判断正误同一问题的线性规划模型是唯一的。正确答案：说法错误解答参考：6.判断正误任何线性规划问题存在并具有唯一的对偶问题。正确答案：说法正确解答参考：7.对偶问题的对偶不一定是原问题。正确答案：说法错误解答参考：8.判断正误运输问题的求解结果可能出现下列4种情况之一：有唯一解；有无穷多最优解；无界解；可行解。正确答案：说法错误解答参考：9.在运输问题中，只要给出一组含有（m+n-1）个非零的xij且满足全部约束，就可以作为基本可行解。正确答案：说法错误解答参考：10.判断正误整数规划解的目标函数值一般优于其相应的线性规划问题的目标函数值。正确答案：说法错误解答参考：11.用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。正确答案：说法错误解答参考：12.第一个顶点和最后一个顶点相同的闭链叫回路。正确答案：说法错误解答参考：13.判断正误任一运输网络中至少存在一个流。正确答案：说法正确解答参考：14.判断正误Djisktra算法可求出非负赋权图中一顶点到任一顶点的最短距离。正确答案：说法正确解答参考：（注意：若有主观题目，请按照题目，离线完成，完成后纸质上交学习中心，记录成绩。在线只需提交客观题答案。)三、主观题(共3道小题)15.简述编制统筹图的基本原则。参考答案：统筹图是有向图，箭头一律向右；统筹图只有一个起始点。一个终点，没有缺口；两个节点之间只能有一个作业相连；统筹图中不能出现闭合回路。16.已知线性规划maxZ=3x1+x2+3x3（1）、求出不考虑x3为整数约束时的最优解。（2）、写出分支条件及约束方程。（3）、求最优解。参考答案：（1）x1=16/3，x2=3，x3=10/3；（2）[10/3]=3，x3≥4或x3≤3；-4/9x1–1/9x5–4/9x6+x7=-1/3；-4/9x1–1/9x5–4/9x6+x7=2/3；17.简述西北角法、最小元素法、差值法确定运输问题初始基本可行解的过程并指出那种方法得出的解较优。参考答案：西北角法：按照地图中的上北下南，左西右东的判断，对调运表中的最西北角上的空格优先满足最大供应，之后划去一行或一列，重复这种做法，直至得到初始可行解。最小元素法：对调运表中的最小运价对应的空格优先没醉最大供应，之后划去一行或一列，重复这种做法，直至得到初始可行解。差值法：在运价表中，计算各行和各列的最小运价和次最小运价之差，选出最大者，它所在某行或某列中的最小运价对应的空格优先满足最大供应，重复这种做法，直至得到初始可行解。一般来讲，用差值法求出的初始可行解最接近最优解，也就是最优的。管理运筹学B第2次作业（注意：若有主观题目，请按照题目，离线完成，完成后纸质上交学习中心，记录成绩。在线只需提交客观题答案。)本次作业是本门课程本学期的第2次作业，注释如下：二、判断题(判断正误，共16道小题)1.线性规划一般模型中的变量不一定是非负的。正确答案：说法正确解答参考：2.用图解法求最优解时，只需求出可行域顶点对应的目标值，通过比较大小，就能找出最优解。正确答案：说法正确解答参考：3.图解法与单纯形法求解的形式不同，但从几何上理解，两者是一致的。正确答案：说法正确解答参考：4.单纯形法计算中，选取最大正检验数对应的变量作为换入变量，将使目标函数的值增加更快。正确答案：说法错误解答参考：5.若原问题可行，而对偶问题不可行，则原问题无界。正确答案：说法正确解答参考：6.若原问题有无穷多最优解，则其对偶问题也一定有无穷多最优解。正确答案：说法正确解答参考：7.按最小元素法给出的初始基本可行解，从每一个空格出发仅能找出唯一的闭回路。正确答案：说法正确解答参考：8.表上作业法中，任何一种确定初始基本可行解的方法都必须保证有（m+n-1）个变量。正确答案：说法正确解答参考：9.用分枝定界法求解一个极大化整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界正确答案：说法正确解答参考：10.用割平面法解整数规划问题时，要求包括松弛变量在内的全部变量必须取整数。正确答案：说法正确解答参考：11.有向图G中任意两点是可达的，称此图为强连通图正确答案：说法正确解答参考：12.数T的任两顶点间恰有一条初等链。正确答案：说法正确解答参考：13.G的任一流f的流值valf可能超过任一割的容量。正确答案：说法错误解答参考：14.f为G上一个流，若e为f不饱和边，那么e也一定为f正边。正确答案：说法错误解答参考：15.判断正误统筹网络中任一节点都表示前一道工序的结束和后一道工序的开始正确答案：说法错误解答参考：16.．在统筹网络图中只能有一个始点和一个终点。正确答案：说法正确解答参考：（注意：若有主观题目，请按照题目，离线完成，完成后纸质上交学习中心，记录成绩。在线只需提交客观题答案。)三、主观题(共8道小题)17.Djisktra算法能否求有负权的有向图中两点间的最短路径，举例说明。参考答案：Djisktra算法不能求有负权的有向图中两点间的最短路径。如下图：左边的点为v1，右边的点为v3，下面的点为v2，若v1到v2的权重为1，v1到v3的权重为2，v3到v2的权重为-3，则，若用Djisktra算法则最短路径的数值不能收敛，致使求不出最优解。18.指出统筹图网络中的错误，并改正。参考答案：（1）e，d工序有错。（2）两个终点。（3）两个始点，两个终点。（4）工序循环不是统筹图。19.简述在求最大流过程中，寻找由到源到汇的不饱和链的方法。参考答案：标号法寻找增流链的步骤：第一步：对未检查的边(u,v)的顶点v进行标号，标号的方式为(u,边的方向,l(v))，其中标号的各个部分按照如下确定：（1）u：表示被标号点v的前一个顶点。（2）边的方向：当被标号点v为终点时，即边(u,v)为前向边时，用“+”标示；当被标号点v为始点时，即边(u,v)为后向边时，用“-”标示。（3）l(v)：当被标号点v为终点时，l(v)=min{l(u),c(u,v)-f(u,v)}；当被标号点v为始点时，l(v)=min{l(u),f(u,v)}。另外，默认源x的标号为(0,+,+∞)。第二步：继续检查，判断顶点v后面的边(v,z)能否成为增流链的边，边(v,z)若成为增流链中的边所具备的条件如下：（1）如果边(v,z)是前向边，则应该有f(v,z)c(v,z)。由前面知识可知，前向边流量只能增加，那么边(v,z)就不能是饱和边。（2）如果边(v,z)为后向边，则必有f(v,z)0。由前面知识可知，后向边流量只能减少，那么边(v,z)就不能是零边。第三步：若边(v,z)能够成为增流链的边，就使顶点z成为被标号的点，再对被标号点z按照第一步的标号方式进行标号。第四步：返回第二步，不断循环，直至不能找到被标号点，则反向追踪找出不饱和链。20.用标号法求图所示的网络中从vs到vt的最大流。参考答案：（1）Valf=5（2）Valf=721.简述分枝定界法的主要步骤参考答案：第一步：先不考虑整数约束条件，对一般情况的线性规划问题用单纯形法或对偶单纯形法求解。如果求出的最优解满足整数规划问题的所有整数约束条件，那么这个最优解也就是整数规划问题的最优解，如果有一个或多个整数约束条件没有被满足，转到第二步。第二步：任意选择一个应该是整数而不是整数解的变量xk，设它的非整数解是bk，同时设bk对应的整数位是[bk]，现在将原问题分成两枝，一枝是在原问题的基础上，增加约束条件xk≤[bk]；另一枝是在原问题的基础上，增加约束条件xk≥[bk]+1，这样就构成了两个新的线性规划问题的子问题。第三步：按照第3.3节对偶单纯形法扩展应用的思路，分别对分枝后的两个新线性规划子问题继续求解。若新的解不满足原问题整数约束，再按第二步进行新的分枝，直到满足下面的情况停止分枝：22.已知某整数规划不考虑整数约束时最优单纯型表，写出一个割平面方程。参考答案：-1/7x3–2/7x5+x6=-6/7；23.求解下列0-1规划问题的解。（1）minZ=8x1+2x2+4x3+7x4+5x5参考答案：（1）（x1，x2，x3，x4，x5）=（0，1，1，0，0），Z=6（2）（x1，x2，x3，x4，x5）=（1，1，0，0，0），Z=5（3）（x1，x2，x3，x4，x5）=（0，0，1，1，1），Z=624.简述运输方案的调整过程。参考答案：第一步：确定换入变量同单纯形法一样，在所有的负检验数中，一般选取检验数最小的非基变量作为换入变量。第二步：确定换出变量和调整量由定理5.4可知，由此时还是非基变量的换入变量和一组基变量可以组成一个唯一的闭回路，找到这个闭回路以后，以此非基变量为起点，取此闭回路中偶数顶点取值最小的基变量做为换出变量，调整量的量值即为此基变量的值。第三步：调整方法（1）闭回路以外的变量取值均保持不变。（2）针对闭回路，奇数顶点变量的值全部加上调整量，偶数顶点变量的值全部减去调整量。第四步：标识方法为了保证基变量的个数为m+n-1个，在标识上作如下处理：（1）调整后，原来作为非基变量的换入变量就变成了基变量，所以要把这个变量的值标识成“○”。（2）调整后，原来作为基变量的换出变量就变成了非基变量，所以要在这个变量的位置打上“×”。第五步：继续求检验数，如果存在负的检验数，就返回第一步，否则计算停止，说明找到了最优解。管理运筹学B第3次作业（注意：若有主观题目，请按照题目，离线完成，完成后纸质上交学习中心，记录成绩。在线只需提交客观题答案。)本次作业是本门课程本学期的第3次作业，注释如下：二、判断题(判断正误，共11道小题)1.一般情况下，松弛变量和多余变量的目标函数系数为零。正确答案：说法正确解答参考：2.用单纯形法求解标准型线性规划问题时，与检验数大于0相对应的变量都可被选作换入变量。正确答案：说法正确解答参考：3.由应用问题建立的线性规划模型中，其约束方程有多种形式正确答案：说法正确解答参考：4.yi为对偶问题的最优解，若yi0，说明在最优生产计划中第i种资源已完全耗尽。正确答案：说法正确解答参考：5.当所有产量和销量均为整数值时，运输问题的最优解也为整数解。正确答案：说法错误解答参考：6.整数规划问题的可行解与其线性规划问题的可行域内的整数点相对应。正确答案：说法正确解答参考：7.判断正误任一图G中，当点集确定之后，树图是G中边数最少的连通图。正确答案：说法正确解答参考：8.在有向图中，如图所示中的边e和eˊ是平行边正确答案：说法错误解答参考：9.若Q为f饱和链，则链中至少有一前向边条边为f饱和边，同时至少有一条边后向为f零边。正确答案：说法错误解答参考：10.既要满足流值最大又要满足费用最小的流是不存在的。正确答案：说法错误解答参考：11.标号法每迭代一步，没有取得永久性标号顶点的标号都会被改变一次。正确答案：说法正确解答参考：（注意：若有主观题目，请按照题目，离线完成，完成后纸质上交学习中心，记录成绩。在线只需提交客观题答案。)三、主观题(共9道小题)12.求下列图中的指定顶点（1）到（5）的最短距离和路(径)。参考答案：（1）路线：（1）—（4）—（3）—（5）（2）路径：（1）→（3）→（2）→（4）→（5）13.简述在求最小费用流的过程中，寻找由到源到汇的不饱和链的方法参考答案：第一步：如果运输网络G的流值没有达到A，先用最大流算法把流值调到A；如果运输网络G的