运筹学 试卷及答案 卷6

课程名称:课程名称:运筹学题号一二三四五六七八九十总分得分评分人一、（10分）设有如下线性规划问题：（1）写出其对偶问题；（2）利用对偶问题的性质证明原问题目标函数值。二、（15分）用顺序法或逆序法，求解Ａ到Ｅ的最长路问题。三、（15分）运用表上作业法求解下列运输问题，表格中间的数字为运价。产销甲乙丙丁产量A9181109B11681810C14122166销量4975学院：专业：学号：姓名：装订线四、（15分）求如下最大指派问题，系数矩阵为：五、（10分）用图解法求解目标规划问题六、（20分）已知线性规划问题用单纯形法求的最终单纯形表如下3/2015/14-3/14110-1/72/700-5/14-25/14若价值系数=13，该问题的最优解如何改变。（10分）右端项由变为时，该问题的最优解如何变化？（10分）七、（15分）下图为一网络图：若不考虑方向时，边上数字为边的长度，求该图的最小支撑树；（5分）若边上数字为容量，求从顶点v1到顶点v8的最大流。（7分）求最小割（3分）VV1V2V4V3V5V7V6V85679446459754课程名称:运筹学一（10分）解：（1）设对偶变量分别为y1，y2，y3，则对偶规划为：（min1分，目标函数系数1分，右端向量1分，约束系数矩阵1分，变量取值范围1分）（2）证明：令y=(1,0,2)，易证满足上述对偶问题的所有约束条件所以y=(1,0,2)是对偶问题的一个可行解，（可行解3分）代入对偶问题的目标函数得w=2×1+5×0+2×2=6由弱对偶性得：原问题目标函数值z≤w=6.得证（弱对偶性2分）二（15分）方法一：（逆序法标号）AAB1B2B3C1C3C2D1D2E1025115137105675713414(18)(18)(26)(0)(1)(4)(8)(8)(9)(24)（12分）所以，A到E最长路为26（1分）路径为A→B1→C1→D2→E（2分）方法二：分4个阶段，k=1,2,3,4K=4时，（1.5分）K=3时，（1.5分）（1.5分）（1.5分）K=2时，（1.5分）（1.5分）（1.5分）K=1时，（1.5分）所以，A到E最长路为26（1分）路径为A→B1→C1→D2→E（2分）四（15分）解：首先变成最小化指派问题。B=(41-Cij)5×5矩阵变换（3分）矩阵变换（3分）（3分）（试指派3分，划直线1分）调整（2分）所以（1分）调整（2分）（再指派1分）此时最大值W=33+19+41+35+19=147（1分）三（15分）解：由最小元素法得初始运输方案如下表所示：（初始解4分，检验数4分）甲乙丙丁产量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分）五（10分）解：图解法见下图X111X1111055.65.5d1+Bx1-x2=02x1+x2=118x1+10x2=56x1+2x2=10d2+d3-7X211Ad2-由图知目标规划的满意解为线段AB，A(2,4),B(10/3,10/3)，即满意解为：α1(2,4)+α2(10/3,10/3)=(2α1+10/3α2,4α1+10/3α2)其中0≤α1，α2≤1，α1+α2=1（坐标系：1分，绝对约束1分，三个目标约束2分×3=6分，结果2分）六（20分）解：（1）当c1变为13时，代入最终单纯型表得：Cj→13500θCBXBbx1x2x3x45x23/201[5/14]-3/1410/213x1110-1/72/7-σj001/14-31/14（4分）0x321/5014/51-3/513x18/51201/5σj0-1/50-2/5（4分）因为σj≤0，所以X*=（8/5，0，21/5，0）T，Z*=104/2（2分）（2）当右边向量b变为(8,9)T时，（8分）所以X*=（10/7，13/14，0，0）T，Z*=265/14（2分）V1V2V1V2V4V3V5V7V6V85544454（4分）最小树的权数为：5+5+5+4+4+4+4=31（1分）（2）增广链流量调整量V1→V2→V4→V6→V84（2分）V1→V3→V5→V7→V86（2分）V1VV1V2V4V3V5V7V6V8(5,0)(6,6)(7,6)(9,6)(4,0)