华中科技大学2014年自动化运筹学答案

2014年-2015学年度第一学期

华中科技大学本科生课程考试试卷（A卷）课程名称：运筹学（一） 课程类别■专共课考试形式■闭卷所在院系:自动化学院专业及班级: 考试日期:2014.11.24学号： 姓名： 任课教师： 润及有关数据如表下所示。两种原料生产三种产品的有关数据甲乙丙原料拥有量A73550B34530单件利润435请分别回答下列问题：（1） 求使该厂获利最大的生产计划数学模型;（2） 将此数学模型化为标准型；（3） 用单纯形法求最优解。解：假设安排生产甲、乙、丙三种产品分别为：■■- :■:1)2)1)2)数学模型为：标准型为：maxz=4x+3x+5x1237x+3x+5x<501 2 3<3x+4x+5x<301 2 3x,x,x>0123maxz=4x+3x+5x+0x+0x123457x+3x+5x+x=5012 3 4<3x+4x+5x+x=301 2 3 5x,x,x,x,x>03)3)单纯型法解的过程Cj43500CBxBbx1x2x3x4x590x45073510100x53034[5]016j435

第二步Cj43500CBxBbx1x2x3x4x500x420[4]-101-155x363/54/5101/510oj1-100-1第三步Cj43500CBxBbx1x2x3x4x504x151-1/401/4-1/45x33019/201-3/207/20oj0-3/40-1/4-3/4最优解：［5,0,3,0,0］，最优值为：35.

得分评卷人、得分评卷人、（10分）求解线性规划：minz=2x+x+5x312x+x-x>6123<—2x +x>2i3x,x,x>0123解：增加剩余变量xx，化为标准型：4,5minz=2x+x+5x+0x+0x1 2 3 4 5x+x-x-x=61234-2x+x-x=2135x,x,x,xx>0123 4, 5+0x+Mx+0x+Mx56minz=2x+x+5x+0x1234x+x—x—x=61234<—2x +x—x+x=2i356x,x,x,xx,x>0123 4, 5 6单纯型表如下：Cj21500MCBxBbx1x2x3x4x5x691x2611-1-100Mx62-20[1]0-112J1+2M06-M1M0

取x为换入变量，x为换出变量，迭代一步为：36Cj21500MCBxBbx1x2x3x4x5x691x28-110-1-115x32-2010-11j130016M-6从上述表来看，非基变量的b>0，所以对应的解为最优解，最j优解为：「x*x*X*］二［082］，最优值为：minz*=18得分评卷人三、（20分）已知线性规划问题：对偶变量TOC\o"1-5"\h\zL得分评卷人三、（20分）已知线性规划问题：对偶变量maxz=2x+x+5x+6x1 2 3 42x+2x+x+2x<12 y1 2 3 4 2x>0j=1,A,4j其对偶问题的最优解为y其对偶问题的最优解为y*=4，y1=1，试应用对偶问题的性质，求原问题的最优解。解：对偶模型为

min®=8y+12y122y+2y>2122y>12y+2y>612y1,y2>0(1)(2)(3)(4)(1)(2)(3)(4)由y*=4，y*=1，上式中,121）、（2）为严格真分式，所以x*=0,x*=0，因为y,y>0，所以对应原问题的两个约束条1212件应取等式，因此有：x*+x*=8=4,x*=44=4,x*=44x*+2x*=12 334原问题的最优解为：X*=（0 0 4 4）;z*=44得分评卷人四、试用对偶单纯形法求解下列线性规划问题。minz=x+x122x+x>412<x+7x>712x,x>012解：化简问题得到如下形式maxzz=-x-x12—2x—x+x=41 2 3<—x—7x+x=7124x,x,x,x>01234

z*z*=31/13Cj-1-100CBxBbx1x2x3x40x3-4-2-1100x4-7-1[-7]01j-1-100变换后：Cj-1-100CBxBbx1x2x3x40x3-3[-13/7]01-1/7-1x211/710-1/7j-6/700-1/7进一步变换：Cj-1-100CBxBbx1x2x3x4-1x121/1310-7/131/3-1x210/13011/13-2/13cj00-6/13-1/13表中结果为最优解X*=(21/13 10/1300);

产地、、销地甲乙丙丁产量110671242161059935410104销量5246优值。得分评卷人得分评卷人五、求如下产销平衡表中运输问题的最优解与最解：利用vogel方法产生初始解产地、、销地甲乙丙丁行差110671212161059435410101列差⑸221第一步分配：产地销地甲乙丙丁产量1429344销量5246

产地、、销地甲乙丙丁行差11067121216105943541010列差[6]423第二步分配：产地、、销地甲乙丙丁产量11429344销量5246产地、、销地EF乙丙丁行差110671212161059[4]35) 4W—W—列差423

第三步分配：产地、、_销地甲乙丙丁产量114249344销量5246产地、、销地EF乙丙j丁行差1106LiF12[6]21610591 3 4 —10— W—列差43第四步分配：产地、一、、销地甲乙丙丁产量1124249344销量5246

产地销地B1B213B4行差110()712216105931 ——10———W—列差初解：产地、、、销地B1B2B3B4产量112142459344销量5246位势法判断最优解：产地、、销地B1B2B3B4ui1106-1』120291671059-335347[103[10-5vJ106812位势法判断最优解：有检验数都小于0，所以该解进行调整。

产地\一、销地BiB2B3B4ui1106-1』120291671059-335347103[10-5vJ106812有一空格的检验数为-1，因此需要调整。产地销地B1B2B3B4产量112(+1).…(-1)1424(-1)—(+1)59344销量5246调整量为1，调整后为：产地、、销地B1B2B3B4产量112142369344销量5246调整后检验：

产地\一、销地B1B2B3B4ui110671|12028