运筹学习题2-单纯形法

运筹学习题系列（二）OR教研室1《运筹学》习题（二）班级姓名一、判断题1、无约束的变量xj，通常令jjjxxx，其中00jjxx,，在用单纯形法求得的最优解中有可能同时出现00jjxx,。2、用单纯形法求解标准形的线性规划问题时，与0j对应的变量都可以被选作换入变量。3、单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负。4、单纯形法计算中，选取最大正检验数k对应的变量xk作为换入变量，将使目标函数值得到最快的增长。答：二、单纯形法迭代中，任何从基变量中替换出来的变量，在紧接着的下一次迭代中，会不会再进入基变量中？为什么？答：三、下表为用单纯形法计算时某一步的表格，已知该线性规划问题中目标函数为2135maxxxz，约束条件均用“≤”关系连接，3x,4x为松弛变量，该表中解代入目标函数可得z=10。求a---g的值；问此表所给的解是否为最优解。1x2x3x4x3x1x2acd0e100.21cjzjb1fg答：四、用单纯形法求解下述问题：maxS=x1+x22x1+x2≤82x1+5x2≤20x1+x2≤5x1,x2≥0解：加入松弛变量，用单纯形法解得如下：Cj→11000θiCBXBbX1X2X3X4X5000X3X4X582052*21151100010001S011000←λj运筹学习题系列（二）OR教研室2100X1X4X541211001/241/2*1/2010001S01/200←λj101X1X4X23421000011010-1-82S000-1←λj五、试利用两阶段法第一阶段的求解，找出下述方程组的一个可行解，并利用计算得到的最终单纯形表说明该方程组有多余方程。074321322321321321321xxxxxxxxxxxx,,解：运筹学习题系列（二）OR教研室3附《运筹学》习题（二）答案一、1、对（因为jjxx与的系数列向量只差一个符号，所以它们线性相关，不可能是某个可行基中的两列，因此在同一个基可行解中不可能出现00jjxx,）；2、对；3、对；4、错。二、解：不可能。因为刚从基中替换出来的变量在下一个单纯形表中，起检验数一定为负数。三、答：a=2，b=0，c=0，d=1，e=0.8，f=0，g=5；表中的解是最优解。四、解：Cj→11000θiCBXBbX1X2X3X4X5000X3X4X582052*21151100010001S011000←λj100X1X4X541211001/241/2*1/2010001S01/200←λj101X1X4X23421000011010-1-82S000-1←λj五、解：用两阶段法求解时，在第一阶段应该构造如下的线性规划问题：654xxxzmin61074321322632153214321,,jxxxxxxxxxxxxxj经单纯形法的计算得到如下单纯形表7：表7XBbx1x2x3x4x5x6x10.5x31.5x601002.50.500100.50.530.50.51001cjzj000420由于非基变量x2的检验数为零，即问题有无穷多最优解，这一点说明了此线性方程组有多余方程。