「2013《运筹学》考试题及其答案」1

2012-2013学年第1学期《运筹学》考试题答案要求：第一题必做(50要求：第一题必做(50分)，二三四题任选两题(每题各25分)。考虑下面线性规划问题mi氏=4x+xTOC\o"1-5"\h\z123x+x=3(1)124x+3x>6(2)S.tA12X+2x<3(3)12x,x>0v12(1)用图解法求解该问题；(2)写出该问题的标准形式；(3)求出该问题的松弛变量和剩余变量的值；(4)用单纯形法求解。【解答】(1)图中阴影部分为此线性规划问题的TOC\o"1-5"\h\z可行域，目标函数z=4x+x，即，=-4x+z是斜率为-4的一族平行直线，由线性规划1221的性质知，其最值在可行域的顶点取得,将直线z=4x+X沿其法线方向逐渐向上平移，直至12A点,A点的坐标为(J1),所以minz=4义3+6=18此线性规划问题有唯一解X=3,X=6。1525(2)给等式(2)左端添加剩余变量x，给等式(3)左端添加松弛变量x，则得到该问题的标34准型为：maxz=-4x-x+0x+0x12343x+x=3,(1)124x+3x-x=6,(2)s.tX123/、x+2x+x=3,(3)124X,X,X,X>0[1234(3)在上面标准型中令X1二3,X2二6，得到剩余变量X3=0，松弛变量X4=。。(4)先在上面标准型中约束条件(1)、(2)中分别加入人工变量X,X，得到如下数学模型，56maxz=-4x-x+0x+0x-Mx-MxTOC\o"1-5"\h\z1234563x+x+x=3,(1)1254x+3x-x+x=6,(2)S.t.<1236x+2x+x=3,(3)124x,x,x,x,x,x>0123456由此列出单纯形表逐步迭代用大M法求解计算结果如下表所示。—4-100—M—Mxxxxxxbei-Mx5【3】1001031—Mx643—100163/0xA12010033r.j7M-44M—1一M000—9M—4x11/3001/3013-Mx60【5/3】—10-4/3126/0x05/301-1/3026/5rj(-z)0(5M+1)/3—M0(—7M+4)/30—4-2M—4x1101/03/5/53/51/-1x201-3/50—4/53/56/0x400【1】11100rj(—z)001/50-M+8/5-M-1/.18/-4x1100-1/52/503/5-1x20103/5—1/506/50x300111—10rj(-z)000-1/5-M+7/5-M-18/5表中所有检验数j0，根据最优解定理，问题存在唯一的最优解X=(3,6,0,0,0,0)T,目标函55数的最优值maxz=4义3+5=158二、试用表上作业法求解下列运输问题的最优解。二、试用表上作业法求解下列运输问题的最优解。■产地^销地B1B2B3B4产量A148846A,95634A33114212销量6277【解答】：显然该问题是一个供需平衡问题,利用伏格法求出初始方案，如下表所示。B1B2B3B4产量A1648846A29256234A30311745212销量6277用位势法求出各非基变量（即空格）的检验数，如下表所示。B1B2B3B4uA164(3)8⑶8(1)4u=0A2⑸925⑴623u=0A303⑺117452u3=-1v.v=41v=52v=53v=34因为所有非基变量的检验数均为非负