运筹学 试卷及答案 卷1

《运筹学》期末考试试卷A专业班级姓名学号题号一二三四五六七八考试成绩得分得分一、单选题(2分*10=20分)（）1、对一个极大化的线性规划问题用单纯形法求解，若存在某检验数，且它所在列的系数所有系数均不大于0，则该线性规划问题。A．有唯一最优解B．有无穷多最优解C．为无界解D．无可行解（）2、若原问题中xj为自由变量，那么对偶问题中的第j个约束一定为。A．等式约束B．“≤”型约束C．“≥”约束D．无法确定（）3、有m个产地，n个销地的产销平衡的运输问题中，用表上作业法求解得到时，表中空格数是。A．m×nB．m+n－1C．m+nD．m×n－(m+n－1)（）4、解最大化指派问题时，先转化为最小化指派问题，转化的方法是。A.用矩阵的最大元素减去所有元素；B．用矩阵的最小元素减去所有元素；C．每行的元素减去本行最小元素，然后再对各列的元素减去本列最小元素；D．用每行的最大元素减去本行元素，然后再用各列的最大元素减去对本列的元素。（）5、关于凸集，不正确的描述是。A．凸集里面的任意两个点的连线上的点仍然在该凸集内;B．线性规划问题的可行域一定是一个凸集;C．若线性规划问题的可行域是凸集，则该凸集上任一个顶点都可能是最优解;D．若线性规划问题存在最优解，则最优解一定是可行域凸集上的某一个顶点或边上。（）6、用沃格尔法求解运输问题时，如果差值很大时，应尽量优先安排所在行或列的运输。A．最小元素B．最大元素C．最大差D．最小差（）7、若一个指派问题的系数矩阵的某行各元素都加上常数得到一个新的矩阵，这一新矩阵对应着一个新的指派问题，则。A．新问题与原问题有相同的最优解B．新问题最优目标值大于原问题最优目标函数值C．新问题最优解等于原问题最优解加上D．新问题最优解小于原问题最优解（）8、下列命题中不正确的是。A．整数规划问题的可行解一定是其松弛问题的可行解;B．整数规划问题最优目标函数值不超过其松弛问题最优目标函数值;C．若松弛问题的最优解是整数规划问题的可行解,则它是整数规划问题的最优解;D．整数规划一定存在最优解.（）9、若是原问题为极小问题的可行解，而是其对偶问题的可行解，则有。；B．；C．；D．与没有关系。（）10、当某一cj发生改变，则（）A.原最优解发生改变；B.原可行解可能改变；C.原可行解不变；D.不确定得分二、判断题（2分*10=20分,把答案填在序号前）（）1、对偶问题的对偶问题等同于原问题。（）2、整数规划问题的可行解集合是它的松弛问题可行解集合的一个子集。（）3、用位势法求检验数时，位势不同则求出的检验数不一定不同。（）4、对于最大化问题，其最终表检验数的相反数是对偶问题的最优解。（）5、影子价格是指外部市场价格，它是机会成本，是边际利润。（）6、根据互补松弛定理，当时，=0。（）7、图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。（）8、若某种资源的影子价格等于C，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5C。（）9、0-1规划问题中，当决策变量个数是4时，则它的可行解个数是32。（）10、采用分支定界法解整数规划问题时，如果某个问题恰好获得整数规划问题的一个可行解，那么可以把它作为目标函数值的“界限”。得分三、计算题（60分）1、写出下面线性规划的标准形式和对偶规划。（8分）2、已知线性规划问题（1）用单纯形法求出最优解。（8分）（2）约束条件右端项由变为，最优解如何改变。（5分）（3）直接写出对偶问题的最优解。（5分）3、运用表上作业法求解下列运输问题，表格中间的数字为运价。（12分）产销甲乙丙丁产量A9181109B11681810C14122166销量49754、求如下最大指派问题，系数矩阵为：（10分）5、下图为一网络图，边上数字为边的容量或者长度：用Dijkstra算法求解从顶点1到顶点8最短路；（5分）求从顶点1到顶点8的最大流，并求最小割。（7分）VV1V2V4V3V5V7V6V85679446459754<运筹学>课程A卷参考答案一、选择题（每小题2分，共20分）1--5、CADAB6--10、CADCC判断题（每小题1分，共10分）1--5、√√√√×6--10、√√××√三、计算题1、则标准形式为：设对偶变量分别为y1，y2，y3，则对偶规划为：或者2、解：（1）首先写出线性规划问题的标准形式（1分）Cj→23100θCBXBbx1x2x3x4x50x45111105/10x54-1[2]0014/2δj23100（2分）0x43[3/2]011-1/223x22-1/21001/2—δj5/2000-3/2（2分）2x12102/32/3-1/33x23011/31/31/3δj00-4/3-7/3-1/3（2分）此时，原问题得到最优解为X*=(2，3，0，0，0)T，maxZ＝13（1分）（2）当右边向量b变为(3,7)T时，（2分）代入最终单纯型表继续迭代：Cj→23100CBXBbx1x2x3x4x52x1-1/3102/32/3[-1/3[3x210/3011/31/31/3δj00-4/3-7/3-1/3（2分）0x51-30-2-213x2311110δj-10-2-30（2分）所以X*=（0，3，0，0，1）T，Z*=9Y*=（7/3,1/3,0,0,4/3）（2分，1分，1分，1分，1分）x1x1x2x3x4x5y1y2y3y4y5（说明：如果本部分的思路正确，并且答案和第一步表中检验数案契合，仅仅扣掉1分。只写出关键的y1和y2也给满分）3.解：由最小元素法得初始运输方案如下表所示：（初始解3分，检验数3分）甲乙丙丁产量uiA918110902(14)7(-1)B11681810219(5)(5)C1412216651(3)(-4)5销量4975Vj94111因为σ14，σ33＜0，所以该方案不是最优方案。进行调整：（调整2分，新检验数2分）甲乙丙丁产量uiA918110903(14)6(-5)B11681810219(5)(1)C141221661(4)(7)15销量4975Vj94115因为σ14＜0，故该方案不是最优方案，再调整。新方案如下：（再调整1分，检验数1分）甲乙丙丁产量uiA918110903(14)15B11681810219(5)(6)C141221661(4)(7)6(5)销量4975Vj94110因为，所以该方案是最优方案。总运费为155。（1分）（说明：此题如果采用差值法求初始方案时，则无需调整，直接通过计算检验数马上可以得出最优答案，计算过程会简洁很多，最终结果都是155）4、首先变成最小化指派问题。B=35-Cij)5×5（2分）行列变换（2分）行列变换（2分）试指派2分，划直线3分调整（2分）调整（2分）再指派2分即：S1→J5，S2→J1，S3→J2，S4→J3，S5→J3此时总得分W=33+19+41+35+19=147（1分）（说明：此题方案不唯一，但是最终结果都是147）（1）66(8,8)(14,14)V1V2V4V3V5V7V6V8571446459754(4,4)(9,9)(13,13)(6,6)(17,15)（5分）所以V1到V8的最短路长为15。路径为：V1→V2→V5→V7→V8。（2分）（2）V1→V2→V4→V6→V84（1分）V1→V3→V5→V7→V86