运筹学试题3.1答案

第1页共5页参考答案与评分标准课程名称《运筹学》本科一、判断题，本题5小题，每题3分，满分15分。1、√2、√3、×4、×5、√。二、单项选择题，本题共5小题，每题3分，满分15分。1、D2、C3、A4、C5、A。三、填空题，本题共5题,每题3分，满分15分。1、有限最优解2、kkpfx3、保留整数可行解，删除当前最优解/松弛问题最优值增加。4、k5、MK。四、解答题，本题共5小题。1、（5分）解：11221231123223132min...............1..24470...............40,0,.........bwbwst是自由变量......52、（10分）解：首先得到问题P的松弛问题的最优解0310(,)23Tx，0296z。………………2令12x或者11x，则生成P的两个子问题：（P1）12121211212max951..14141232,0,Zxxstxxxxxxxxx取整数（P2）12121211212max951..14141231,0,Zxxstxxxxxxxxx取整数求得P1的松弛问题的最优解223(2,)9Tx，1419z。令23x或者22x，则生成P2的两个子问题：第2页共5页（P3）1212121212max951..141412323,Zxxstxxxxxxxx0，取整数（P4）1212121212max951..141412322,0Zxxstxxxxxxxx，取整数求得P3无解；求得P4的松弛问题的最优解333(,2)14Tx，46114z。令13x或者12x，则生成P4的两个子问题：（P5）1212121212max951..141412332,Zxxstxxxxxxxx0，取整数（P6）1212121212max951..1414123222,0Zxxstxxxxxxxx，取整数求得P5的松弛问题的最优解1(3,1)Tx，54z。求得P6的松弛问题的最优解1(2,2)Tx，14z。求得P2的松弛问题的最优解27(1,)3Tx，11043z。所以停止。………………9故原问题的最优解*3(3,1)or(2,2)TTxx，最优值*54zz。………………103、（12分）解：（1）、（6分）首先把问题NLP化成标准的形式2min(4)..50xstx它的Lagrange函数是2L(,)=(4)(5)xxx………………2因为L=2(4)xx，故问题NLP的K-T条件是2(4)0(5)00xx第3页共5页如果0，由K-T条件得4x，由于此解不满足可行性条件，所以此解被舍弃。如果0，则有互补松紧条件知5x，由K-T条件得2，同时此解满足可行性条件，故*5x为K-T点。………………5易验证2()(4)fxx与()5gxx均为凸函数，因此*5x为其整体最优解。………………6（2）、（6分）罚函数为1()ln5ln5,5kdkBxdxxxk相应的增广目标函数为21()(4)ln5,5kdFxxxxk原问题转化为求解一系列无约束最优化问题min()kdFx，1,2,k………………3用解析法求解上述问题得起最优解为。2922kkkkxk，1,2,k。可以看出，当k无限增大时，kx是从问题可行域外部趋向于它的最优解*5x。………………64、（10分）解：Ford-Fulkerson算法。最优值是5。按迭代步骤平均分配分值。5、（18分）解：（1）、（10分）设该公司生产甲、乙两种家电产品分别为jx，1,2j。这个问题的LP模型（P）：122121212max2..51562245,0Zxxstxxxxxxx………………4问题P的标准形式为：①②③④⑤(2)4(1)1(2)2(1)44(2)2(0)6(2)4(0)5(3)4(1)1ST(2)3第4页共5页122312412512345min2..51562245,,,,0Zxxstxxxxxxxxxxxxx………………1其中345,,xxx为松弛变量。因(15,24,5)0Tb，故基345,,BAAA对应的基本可行解为(0,0,15,24,5)Tx，其目标函数值00z。得到初始单纯形表如下：1x2x3x4x5xRHSz2100003x05100154x62010245x110015以21a为转轴元，进行旋转变换后得到下表：1x2x3x4x5xRHSz01/30-1/30-83x05100151x11/301/6045x02/30-1/611以32a为转轴元，进行旋转变换后得到下表：1x2x3x4x5xRHSz000-1/4-1/2-17/23x0015/4-15/215/21x1001/4-1/27/22x010-1/43/23/2………………9它对应的基本可行解为7315,,,0,0222Tx，此时检验数向量0。故问题P的最优解为73,22Tx，最优值为*172z。………………10（2）、（8分）ⅰ．（4分）问题P的最优单纯形表为:1x2x3x4x5xRHSz000-1/4-1/2-17/23x0015/4-15/215/21x1001/4-1/27/22x010-1/43/23/2第5页共5页此表对应的可行基为：501620110B，那么151514201011082420213042Bbb12TBcBbb。………………2得到新问题的单纯形表如下：1x2x3x4x5xRHSz000-1/4-1/2-21/23x0015/4-15/235/21x1001/4-1/211/22x010-1/43/2-1/2以34a为转轴元，进行旋转变换后得到下表：1x2x3x4x5xRHSz0-100-2-103x05100151x1100154x0-401-62由此该公司的最优计划改变为只生产家电甲5件。………………4ⅱ．（4分）设家电乙的利润为1元反映到最终单纯形表中如下：1x2x3x4x5xRHSz0001441232-17/23x0015/4-15/215/21x1001/4-1/27/24x010-1/43/23/2所以1440，12320，得131。………………3故家电乙的利润2c变化范围应满足2232c。………………4