雨课堂学堂在线学堂云《组合最优化（东南大学 ）》单元测试考核答案

注：不含主观题第1题判断题(1分)线性规划问题的对偶理论将学习弱对偶性、强对偶性和互补松紧性。第2题判断题(1分)本课程以线性规划的原始对偶算法为桥梁，将其应用到最短路问题、最大流问题和最大匹配问题上。第3题判断题(1分)通过《组合最优化》课程的学习，将加强我们问题转化的思想，提升创新思维的科研能力。第4题判断题(1分)通过《组合最优化》课程的学习，将训练我们从一般到特殊的归纳思维，将赋权优化问题转化为一个新图上的基数优化问题。1.1作业第1题单选题(2分)什么是优化问题？AA.线性规划问题B从一个离散区域能找到一个使目标函数极小的点C在一个可行区域内找一个使目标函数极小或者极大的解D从一个连续区域能找到一个使目标函数极小或者极大的解1.2作业第1题第2题判断题(2分)TSP的2-交换邻域不是精确邻域，3-交换邻域是精确邻域。1.3作业第1题第2题单选题(2分)两个凸函数的乘积是凸函数吗？A是B不是第3题判断题(1分)凸规划问题的特点就是局部最优解等于全局最优解。第4题判断题(2分)整数线性规划问题与线性规划问题的区别在于，前者的变量中有整数变量，后者的变量都是连续变量。第5题判断题(2分)一个优化问题的可行域是凸集，目标函数是定义在凸集上的凸函数，则这个极小化的优化问题是一个凸规划问题。第6题判断题(2分)多个凸集的并集日仍是一个凸集。2.1作业第1题判断题(1分)若线性规划问题存在有限最优解，则最优值必在某个基可行解上达到。第2题判断题(1.5分)两阶段法的第一阶段的辅助线性规划问题的最优值等于0时，再把最优基中的人工变量换出基后，才可以进入第二阶段进行单纯形的迭代。第3题判断题(1分)一个线性规划问题只要可行，则一定存在基本可行解。第4题判断题(1.5分)一个线性规划问题的基可行解中，非基变量的取值必为0。第5题判断题(2分)一个非空的线性规划可行域可能没有极点。2.2作业第1题判断题(2分)在一对互为对偶的线性规划问题中，原问题一定是极小型，对偶问题一定是极大型。第2题判断题(1分)每一个线性规划问题的约束条件都对应一个对偶变量。第3题第4题2.3作业第1题判断题(1分)在互为对偶的一对线性规划问题中，目标极大化的线性规划的最优值小于等于其对偶规划的最优值。第2题判断题(1分)若线性规划问题有两个最优解，则有无穷多个最优解。第3题判断题(1分)如果原问题有最优解，则其对偶问题也有最优解。第4题判断题(1分)如果原问题无界，则其对偶问题也无可行解。第5题判断题(1分)任何一个线性规划都有一个对偶规划。第6题第7题2.4作业第1题判断题(1分)最短路问题的对偶规划的变量的含义可以解释为一个交通运输公司的交通费用。3.0.1作业第1题判断题(1分)两阶段法的第一阶段是为了求得初始基可行解，当第一阶段的最优值>0时，原线性规划问题无解。第2题判断题(1分)当第一阶段的最优值=0时，且基变量不含有人工变量时，可求得原线性规划问题的初始基可行解，将目标函数替换为原问题的目标函数，进入第二阶段求解原问题。第3题判断题(2分)在两阶段法的第一阶段，如果最优值等于0，且基变量中不含有人工变量，则第一阶段的最优表中人工变量的检验数必为1，其他变量的检验数都是0.3.0.2作业第1题填空题(2分)修正单纯形法主要减少的运算量在于计算元素的个数从

____

降到了____。（m+1）×（n+1）;（m+1）×（m+1）+(n-m)正确答案：:["(m+1)*(n+1)","(m+1)(n+1)","(m+1)x(n+1)","（m+1）×（n+1）"]正确答案：:["(m+1)*(m+1)+(n-m)","(m+1)*(m+1)+n-m","(m+1)(m+1)+n-m","(m+1)(m+1)+(n-m)","(m+1)x(m+1)+(n-m)","(m+1)x(m+1)+n-m","（m+1）×（m+1）+(n-m)"]第2题填空题(3分)修正单纯形法的好处可以不计列数的多少，当一个线性规划问题的行数比列数多，可以用____方法求解该线性规划的____问题。正确答案：:["修正单纯形法","修正单纯形"]正确答案：:["对偶","对偶问题"]第3题填空题(3分)修正单纯形法的第一阶段结束时进入第二阶段只需替换检验数行为____和____。正确答案：:["-pi^T","-pi","-(c_B^T)*(B^-1)","-pi'","-cB’*B-1"]正确答案：:["-pi^Tb","-pi*b","-pi^T*b","-(c_B^T)*(B^-1)*b","-pi'b","-cB’*B-1*b"]第4题3.0.3作业第1题判断题(1分)在修正单纯形法中，需要直接计算基矩阵的逆矩阵。第2题判断题(2分)修正单纯形法中，对偶变量、生成的入基列和基可行解的基变量的值，这些向量的计算量和存储量都是O(km),

其中k为迭代次数。3.0.4作业第1题判断题(1分)当用修正单纯性法求解最大流问题时，其系数矩阵是弧链关联矩阵，所以要列出所有从起点s到终点t的链路。第2题判断题(2分)在用修正单纯形法求解最大流问题时，因为每次迭代要选择检验数最小的变量入基，所以每次迭代需要求一条每条边的权值为（-pi）的s-t最短路，则改最短路所对应的链路变量入基。第3题判断题(1分)在用修正单纯形法求解最大流问题时，每次迭代入基的链路变量的序号无关紧要。3.0.5作业第1题判断题(2分)Dantzig-Wolfe分解算法适用于变量可分离的线性规划问题，将该线性规划问题的每个变量描述为各自子问题的极点的凸组合，从而把该线性规划模型转化为变量为凸组合系数的线性规划模型，因此通过增加列数而减少行数，再利用修正单纯形法求解新模型。第2题判断题(2分)Dantzig-Wolfe分解算法用修正单纯形法求解转化后的新模型，每次迭代通过最小检验数选择入基变量的问题转化为一个规模更小的线性规划子问题，当所有子问题的目标值都大于等于当前各自的对偶变量时，则达到了最优。第3题判断题(2分)修正单纯形法适合系数矩阵是扁宽型的线性规划问题的求解，如果系数矩阵是窄条型的，可以用单纯形法求解其对偶问题。因此，可以通过增加列数而减少行数的方法，而列数的增加对于每次迭代的计算量没有影响。第4题判断题(2分)当要求解复杂的线性规划问题时，可以尝试使用列生成的技巧，将入基列的选择转化为一个更易求解的子问题。3.1作业第1题判断题(1分)限制原问题(RP)的目的是求解原问题(P)的一个可行解并满足互补松紧性。第2题填空题(2分)

在什么情况下原始对偶算法终止，可以得到原始问题的最优解？____如何得到P的最优解？____正确答案：:["DRP的最优值为0","DRP的最优值=0","\xiopt=0","DRP的最优值等于0","DRP最优值xi_OPT=0","RP的最优值为0","限制原问题的最优值为0"]正确答案：:["互补松紧性求得对偶问题最优解得到原始问题最优解","互补松紧性","DRP的最优值等于0时，RP的最优解即为P的最优解","根据互补松弛性，用RP的最优解得到P的最优解"]第3题填空题(3分)1.原始对偶算法是保持____

可行性，向____可行性和____

逼近。正确答案：:["对偶","对偶问题"]\xiopt=0","DRP的最优值等于0","DRP最优值xi_OPT=0","RP的最优值为0","限制原问题的最优值为0"]正确答案：:["原始","原始问题"]正确答案：:["互补松紧性","互补松紧","CS_pi"]3.2作业第1题判断题(1分)在原始对偶算法的迭代中，表示(DRP)的最优解，J表示允许列的集合，若下式成立，则对偶问题无界，相应的原问题不可行。第2题判断题(1分)只要原问题可行，那么很容易确定一个初始对偶可行解。第3题判断题(1分)当原线性规划问题的价值向量c是非负向量，则初始对偶可行解只要取π=0.第4题第5题3.3作业第1题判断题(1分)在求解线性规划问题时，如果模型中价值向量c比右端向量b复杂，则将其看成原问题，极小化目标函数，组合化价值向量。第2题判断题(1分)在原始对偶算法的相邻两次迭代的允许列J和J*中，既在J中又在J*中的列是等于0点列。第3题判断题(1分)在原始对偶算法中，关于基列与允许列的关系如下：允许列一定是基列。第4题4.1作业第1题填空题(1分)用原始对偶方法应用到最大流问题上得到Ford-Furkerson标号算法时，为什么将最大流问题看成对偶问题？____正确答案：:["因为b比c复杂","因为右端向量比价值向量复杂","b比c复杂","右端向量比价值向量复杂","右端向量b比价值向量c更复杂","最大流问题的右端向量更复杂","右端向量比价值系数复杂","因为右端向量b比价值向量c复杂"]第2题第3题判断题(1分)最大流的标号算法每次只选取一条增广路,最好的增广路算法是最短增广路算法.4.2作业第1题第2题判断题(1分)任意一个s-t割都能割断从s到t的流量，并且给出了最大流的上界。4.3作业第1题判断题(1.5分)最大流的预流推进算法是针对增广路算法每次迭代只找一条增广路的缺陷而设计的，其每个阶段尽可能多地沿多条路推进流量。第2题判断题(1.5分)通过广度优先搜索方法可以找到当前流对应的剩余网络上从s到t的最短路，并且最短路长都相等，这里最短路长指最短路所含的边数。4.4作业第1题判断题(2分)最大流的预流推进算法中，各个阶段之间最短路的长度严格递增，直到当前增广网络中不存在增广路，则找到了最大流.

第2题4.5作业第1题判断题(1分)最大流的预流推进算法的时间复杂性为O(|V|^3).第2题多选题(3分)关于最大流的预流推进算法，正确的是：A预流推进算法综合利用了BFS求s-t最短路，分层网络的特性，和每次迭代推进尽可能多的流的思想。B预流推进算法每一轮迭代得到的s-t最短路长都是严格递减的。C预流推进算法的迭代次数是O(|V|)，每次迭代的运算量不超过O(|V|2).D预流推进算法每轮迭代增广的流量由最小通行能力的点来确定。正确答案：ACD第3题5.1作业第1题判断题(1.5分)最小费用流的线性规划模型中，价值向量和右端向量都是一般向量，所以用原始对偶算法求解时，既可以将其看成是原问题也可以看成是对偶问题，因此可以分别从这两个角度来设计算法。第2题判断题(1.5分)消圈算法将DRP问题的求解转化为求一个负费用的有向圈。第3题5.2作业第1题判断题(2分)最小费用路算法从零流开始，每次迭代沿一条最小费用路增广流量，若增广前后的流值分别为δ0和δ1，则可以证明增广流值后的流时流值为δ1的最小费用流。第2题判断题(2分)最小费用流问题的消圈算法和最小费用路算法可以设计特定的顺序或结构,得到多项式时间算法.第3题5.3作业第1题多选题(3分)关于最小费用流问题和Hitchcock问题，正确的是A原始对偶方法把Hitchcock问题看成原问题，组合化价值向量，得到的方法称为ab算法。Bab算法每次迭代通过标号算法求解最大流问题RP，并通过最优图中的标号点来确定对偶问题DRP的最优解。Cab算法嵌套使用了原始对偶方法，外层求解RP转化为最大流，内层最大流算法转化为s-t路的可达性问题。D最小费用流问题和Hitchcock问题可以相互转化，因此也可以用ab算法求解最小费用流问题。正确答案：ABCD第2题6.1作业第1题多选题(3分)关于匹配和二部图，请选择正确的选项：A二部图一定是连通图。B一个图是二部图当且仅当其不含有奇圈。C一个二部图的完全匹配必是最大匹配，也是完美匹配。D一个二部图的完全匹配必是最大匹配，完美匹配也是最大匹配。正确答案：BD6.2作业第1题多选题(3分)关于二部图的匹配算法，正确的是：A对应一个最大匹配必存在一条交错增广路。B二部图上的最大匹配问题的交错增广路算法通过构造辅助图来找一条交错增广路，其对应辅助图中从一个未盖点到一个目的点的路。C辅助图上找一条交错增广路是通过广度优先搜索算法完成的。D二部图上的最大匹配问题的交错增广路算法的时间复杂性为O(|E|min{(|V|,|U|}).正确答案：BCD6.3作业第1题判断题(2分)只要存在奇圈必定造成非二部图上找一条交错增广路的困难。第2题判断题(2分)将匹配算法从二部图推广到一般图的困难在于从未盖点到目标点的路不一定是原图中一条交错增广路，产生这个困难的原因是有花的存在。6.4作业第1题判断题(1分)收缩花之后图的结构虽然发生改变，但不需要重新构造辅助图。第2题判断题(2分)在某次迭代从未盖点u开始未能找到交错增广路，那么在后续迭代增广匹配后中仍旧要考虑这个未盖点u相对于新的匹配是否存在交错增广路。第3题7.1作业第1题判断题(1分)求解指派问题的匈牙利算法的时间复杂性是O(n3).第2题判断题(1分)简约矩阵中的元素大于等于0就是流量变量的对偶约束.第3题判断题(1分)二部图的赋权匹配问题也称为指派问题，这是运输问题的特殊情况，特殊在运输问题中约束右端的值a_i和b_j都是1.第4题判断题(1分)求解指派问题的匈牙利算法本质上是求解Hitchcock问题的原始对偶算法，只是用不同的方式来呈现算法的运行。第5题7.2作业第1题判断题(2分)用原始对偶算法求解赋权匹配问题的线性规划模型时，将RP转化为收缩了极大奇集的允许图GJ上的最大基数匹配问题，这很好地体现了将一般赋权匹配问题转化为一系列基数匹配问题求解这一归纳研究思想。第2题判断题(2分)一般图的赋权匹配算法通过收缩\bar{J_b}中的奇圈和收缩辅助图Gc中的花来消除花对于一般图的影响。第3题判断题(1分)为了将二部图的赋权匹配问题的线性规划模型推广到非二部图上，我们引入奇集的概念和奇集中匹配边数不超过其基数的一半的约束,得到其线性规划模型。第4题判断题(1分)一般图的赋权匹配算法的关键是找到一个合适的数学模型，使得其松弛问题的最优基可行解对应一个匹配。7.3作业第1题判断题(2分)非二部图的赋权匹配问题的算法的阶段数为O(n)，因为最外层循环的迭代次数由判断条件|M|<n/2确定。第2题判断题(2分)一般图的赋权匹配算法是原始对偶算法应用的一个典范，其说明了如何将一个赋权问题转化为基数问题进行迭代求解。第3题判断题(1分)在非二部图的赋权匹配算法中，迭代的过程中发现的花可能是