《运筹学》 期末考试 试卷A 答案

《运筹学》期末考试试卷A答案

《运筹学》试题样卷（一）一、判断题（共计10分，每小题1分，对的打√，错的打X）1.√2.√3.X4.√5.√6.X7.X8.√9.√10.√二、建立下面问题的线性规划模型（8分）设大豆、玉米、小麦的种植面积分别为x1、x2、x3，饲养的奶牛头数为x4，饲养的鸡只数为x5，则该农场的经营方案可以表示为：max3000x1+4100x2+4600x3+900x4+2x5s.t.1.5x4+0.6x5≤3500（秋冬季）0.5x4+0.3x5≤4000（春夏季）x4≤200x5≤1500800x4+3x5≤15000x1,x2,x3,x4,x5≥0三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中45为松弛变量，问题的约束为形式（共8分）(1)原线性规划问题：maxcxs.t.Ax≤bx≥0其中：c=(-5/2,0,-5/21,0,0)A=(5/2,-5/2,-4,0,0;1,0,0,-1/6,0;1/2,-1/2,-4,0,-1/3;1,0,0,0,-2)b=(0,0,0,0)(2)原问题的对偶问题：minybs.t.yA≥cy≥0其中：y=(y1,y2,y3,y4)b=(0,0,0)A=(5/2,1,-1/2,1;-5/2,0,1/2,0;-4,0,-4,0;0,-1/6,0,0;0,0,-1/3,-2)c=(-z1,-z2,-z3,0)(3)对偶问题的最优解为y*=(0,0,5/21,0)，此时对应的原问题的最优解为x*=(0,0,5/21,0,0)。+3x3+x6=20x1,x2,x3,x4,x5,x6≥0最优解为x1=20,x2=0,x3=10,x4=0,x5=0,x6=0，最优解为maxZ=40。十、用标号法求V1到V6的最短路。（6分）解：按照标号法的步骤，先标号V1为0，其余节点为∞。然后选择V1到V4的边，更新V4的标号为3。接着选择V4到V5的边，更新V5的标号为7。最后选择V5到V6的边，更新V6的标号为10。因此，V1到V6的最短路为V1→V4→V5→V6，长度为10。运筹学样卷（一）答案一、判断题。共计10分，每小题1分1.√2.X3.√4.√5.√6.√7.X8.√9.X10.√二、建线性规划模型。共计8分（酌情扣分）解：用x1、x2、x3分别表示大豆、玉米、麦子的种植公顷数；用x4、x5分别表示奶牛和鸡的饲养数；用x6、x7分别表示秋冬季和春夏季的劳动力（人日）数，则有：maxZ=3000x1+4100x2+4600x3+900x4+20x5+20x6+25x7s.t.x1+x2+x3+1.5x4≤100(土地限制)400x4+3x5≤15000(资金限制)20x1+35x2+10x3+100x4+0.6x5+x6≤3500(劳动力限制)50x1+175x2+40x3+50x4+0.3x5+x7≤4000(劳动力限制)x4≤200(牛栏限制)x5≤1500(鸡舍限制)xj≥0(j=1,2,...,7)三、对偶问题。共计8分原问题：maxZ=2x1-x2+x3s.t.3x1+x2+x3+x4=60x1-x2+2x3+x5=10x1+x2+3x3+x6=20xi≥0(i=1,2,3,4,5,6)对偶问题：minW=60y1+10y2+20y3s.t.3y1+y2+y3≥2y1-y2+y3≥-1y1+2y2+3y3≥1yi≥0(i=1,2,3)最优解为Y=(4,2)，最优解为minW=140。四、单纯形表求解线性规划。共计16分解：引入松弛变量x4、x5、x6，标准化得：maxZ=2x1-x2+x3s.t.3x1+x2+x3+x4=60x1-x2+2x3+x5=10x1+x2+3x3+x6=20xi≥0(i=1,2,3,4,5,6)构造初始单纯形表：x4x5x6--------------60|3111006010|1-120101020|11300120--------------Z|2-110000通过单纯形法，得到最优解为x1=20，x2=0，x3=10，x4=0，x5=0，x6=0，最优解为maxZ=40。6=x1,x2,x3,x4,x5,x6,≥0我们可以建立初始单纯形表，并进行迭代运算，得到最优单纯形表：CBσ123x4x1x2x4x1x6Xbx4x5x6b'6010203010102010155252x13[1]12*11-1x21-11-14-1[2]1*11x312-11-52-3-310.5-1.5-1.5x4111x51-31-1-2-10.5-0.5-1.5x611-20.50.5-0.5θ2010*207.5由最优单纯形表可知，原线性规划的最优解为：(15,5,0)T，最优值为z*=25。五、求解运输问题。（1）最小元素法：设xij为由Ai运往Bj的运量（i=1,2,3;j=1,2,3,4），列表如下：销地B1B2B3B4产量产地123销量151520203030255535252550100所以，基本的初始可行解为：x14=25；x22=20；x24=5；x31=15；x33=30；x34=5，其余的xij=0。（2）求最优调运方案：1.求检验数，检验解的最优性：σ11=2；σ12=2；σ13=3；σ21=1；σ23=5；σ32=-1。2.求调整量进行调整：=5。销地B1B2B3B4产量产地123销量15151552030302510352525501003.再次检验。4.可以得出最优