《运筹学期末考试试卷.pdf》由会员分享，可在线阅读，更多相关《运筹学期末考试试卷.pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、运 筹 学 期 考 试 试 卷学 院 班级 姓名 学号 运 筹 学(I)课 程 试 卷 A(本卷考试时间120分钟)题号一二三四五弋七八九十总得分题分151310121010101010100得分一、辨析题(注：请详细说明理由)。(每小题3 分，本题共15分)1.一个极小化线性规划的某轮表格中有r=(,-2,0,0,0),请问是否可以选择王作为进基变量？为什么？2.线性规划原问题min X|A X b,X 2 0 和对偶问题 为、a5,a6分别为何值时：(本题共13分)XBx?须 4%bX3-301 0-12x2ai10 0 234%a200 1 a34ra500 0a6(1)(1)表中给出线
2、性规划是唯一解;(2)表中给出线性规划有无穷多解;表中给出线性规划的可行解无界;(4)表中给出线性规划为换入变量，与为换出变量;三、给出线性规划：(本题共1 0分)m a xs.tf=6x1-2X2+3X32再一4+2工3 4 2jj+4x3 0 x2 0 x3 0(1)写出对偶问题；(2)已知*=4,*2=6,*3=0,是上述线性规划的最优解，用互补松弛定理求对偶问题的最优解。四、已知线性规划：(本题共1 2分)m a x /=7 X、+1 2 x2+1 0 x32 1 1+2X2+/3 0X j +x2+x3 0 x2 0 x3 0标准化后的初始表和最优表如下(r=一/)CjCB XB-7
3、 -1 2 -1 0 0 0Xi x2 x3 x4 x5b0 X40 X51 11102 2 10 12030r-7 -1 2 -1 0 0 0-i o x3-1 2 X20 0 12-11 1 o-ll1010r5 0 0 8 2(1)求对偶问，(2)若该 L P|,(3)若右端喘题的最优解。可题原目标函数中X i的系数由7变为9,问最优解有什么变化？仔 0)(4 0、数由变为3 0人 间最优解有什么变化？五、若发点4,4及收点用，鸟，层的有关数据如下表所示。假定4,4处允许物资存储，问怎样调配以使总的支付费用最少？试建立运输模型再进行求解。(本题共i o分)供应量存储费24 6 86 2
4、4200200而 不 里1UU 1UU六、用分支定界法求解整数规划问题：（本题共10分）maxz=3占 +2X2st 2X1+2X2 7玉 2x2（）,4 。（3 分）（2）%W0、&W0 为？,“5=0,40。（3 分）（3）a5 0,0,%0,“6 2 0 且 2%或 生 0。（4分）三、解：（1）其对偶问题如下：m i n Z =2%+4 2s t 2u+%62%+4U2 3出2 0。（3 分）（2）使用互补松弛定理，得到如下结果：（其中4为U取最优解时约束条件不等号左右两边的差值，,=1，2,3.）min z=2%+4%s.t 2%+%2 6u -22w,+4%3w.1 0 uo0,4
5、 O由此得到：4=o,2=o0所以：X xi（=4）=0 2 X%（=6）=0 3 X 刍（=0）=0（2分）（2分）2u+电=6-u=-2u1=2得到：14则对偶问题的最优解为U=（2,2），（1分）=2（2 分）四、解：（1）根据对偶问题最优解与原问题最优表的联系，可以直接得到对偶问题的最优解为：=（8 ，（3 分）由题意可知：A C|=_ 2,0=5 2=3,因此可知：该最优表中的最优基不变，所以：最优解不发生变化。（3分）（3）由最优表中的信息可得：2-1、T 1 J,（1 分）则 5 0、将 1 ,b=Blb=2-P-1 L40、30,5 0、吐（2分）代替最优表中的10采用对偶单纯
6、形法继续求解得到最终最优表为:7，10、CBXBXix2X3X4X5b-1 0 x322101300X4-1-101-110r1380010由此可知：最优解产生了变化，且最优解为X*=（0,0,30,10,0），（1分）（2分）五、解：该运输问题为产 销的问题，虚拟销地8”，形成新的问题:d tf2 勺 名供应量44 6 8 56 2 4 4200200而 刁 工 里DU 1UU 1UU 1DU（2分）设A得的运尊重空修 遇胪碑鸿罂曙物22+3+4程m i n J 4/4xn+6XI2+8%3 +5玉4=2006X21+2X22+4X23+4X24=200s.t.-14-12-10-7-14、
7、-7-5 -8-6 1 -8：（2 分）2 3 d 但 1 2/4 1 2 Q 3,1 1V 1 （）3（2 分）：（2 分）（KJ?）无可行解（2分）（2,1），其对应的最优值为：/*=8。（2因此按照极大化问题转化为极小化问题的 i o Q4 3 2 0（1 2 3 Hr0 2 4 7 L 20J 3 0 2j Y）0 70 2 0 0 l 1 M）2,（2分）P J从而得到本题的最优分配方案i：4-B|,4&-4,A4f%；最优分配方案n：4-当，4-4，4 f4，A&-鸟。最大收益为4。仁 分）八、九、用标号法求最大流，并 给 与 证 啊（本题共x分）所以，该图中的流为可行流。在该运输网络中找到不饱和链:（6,1）调整量为8=1,得到新的流：0)匕匕（2 分）再找到不饱和链:调整量为夕=3,得到新的流:上图即为最大流。（3 分）（3）由上图中的/中不存在/的增流链，因此上图中的流/即为最大流。（2 分）S=V S,V 1,V 2）S*=V 3,V 4,V t C（S,S*）=V a l f=6