运筹学自测试卷2

数学13级运筹学自测试卷2一、单项选择题1使用人工变量法求解极大化的线性规划问题时，当所有的检验数0j,但在基变量中仍含有非零的人工变量，表明该线性规划问题(D)A．有唯一的最优解B．有无穷多最优解C．为无界解D．无可行解2当线性规划的可行解集合非空时一定（D）A.包含原点B.有界C．无界D.是凸集3线性规划具有多重最优解是指（B）A.目标函数系数与某约束系数对应成比例。B．最优表中存在非基变量的检验数为零。C．可行解集合无界。D．存在基变量等于零。4使用人工变量法求解极大化线性规划问题时，当所有的检验数0j，在基变量中仍含有非零的人工变量，表明该线性规划问题（C）A.有唯一的最优解；B.有无穷多个最优解；C.无可行解；D.为无界解5在产销平衡运输问题中，设产地为m个，销地为n个，那么基可行解中非零变量的个数（A）A.不能大于(m+n-1)；B.不能小于(m+n-1)；C.等于(m+n-1)；D.不确定。6如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足（B）A.0dB.0dC.0dD.0,0dd7下列说法正确的为（D）A．如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解B．如果线性规划的对偶问题无可行解，则原问题也一定无可行解C．在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数D．如果线性规划问题原问题有无界解，那么其对偶问题必定无可行解4.用最小元素法求初始调运方案是，运输表中数字格的个数为（D）个。m*nB、m+nC、m*n-1D、m+n-18对于第二类存储模型——进货能力有限，不允许缺货，下列哪项不属于起假设前提条件（D）A需求是连续，均匀的B进货是连续，均匀的C当存储降至零时，可以立即得到补充D每个周期的定货量需要一次性进入存储，一次性满足9对于风险型决策问题，下列说法错误的是（D）A风险型决策问题是指决策者根据以往的经验及历史统计资料，可以判明各种自然因素出现的可能性大小B风险型决策除了满足一般决策问题的四个条件外，还需要加一个条件：存在两个或两个以上的自然因素，并可估算所有自然因素出现的概率C期望值法就是决策者根据各个方案的期望值大小，来选择最优方案D确定型决策其实是风险型决策的一个特例，即自然因素出现的概率为0，而其他自然因素出现的概率为1的风险型决策问题10下面哪些不是线性规划问题的标准形式所具备的（C）A所有的变量必须是非负的B所有的约束条件（变量的非负约束除外）必须是等式C添加新变量时，可以不考虑变量的正负性D求目标函数的最小值11下面哪项不是求解“不确定型决策问题”的方法（B）A悲观法B期望值法C折衷法D最小遗憾法12用单纯形法求解线性规划问题时引入的松弛变量在目标函数中的系数为（A）A．0B.1C.-1D.213如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足（B）A.0dB.0dC.0dD.0,0dd14.在一个网络中，如果从一个起点出发到所有的点，找出一条或几条路线，以使在这样一些路线中所采用的全部支线的总长度最小，这种方法称之为(D)A．点的问题B.线的问题C.树的问题D.最小枝叉树问题15．线性规划可行域的顶点一定是()A．基本可行解B．非基本解C．非可行解D．最优解16．X是线性规划的基本可行解则有()A．X中的基变量非零，非基变量为零B．X不一定满足约束条件C．X中的基变量非负，非基变量为零D．X是最优解17．要求不低于目标值，其目标函数是()A．B．C．D．二、填空题1.线性规划问题中，如果在约束条件中没有单位矩阵作为初始可行基，我们通常用增加人工变量的方法来产生初始可行基。0dd2.当原问题可行，对偶问题不可行时，常用的求解线性规划问题的方法是单纯形法。4对策行为的三个基本要素分别为局中人、策略集、赢得函数（支付函数）5用大M法求目标函数为极大值的线性规划问题时，引入的人工变量在目标函数中的系数应为：－M6可以作为表上作业法的初始调运方案的填有数字的方格数应为：m+n－1个(设问题中含有m个供应地和n个需求地)8求解运输问题时，常用的判断运输方案是否最优的方法，一个是闭合回路，另一个是位势法11因为决策值不可能既超过目标值同时又未达到目标值，所以对于正、负偏差变量恒有（）三、判断题判断题（共计10分，每小题1分，对的打√，错的打X）1.无孤立点的图一定是连通图。（X）2．用单纯形法求解标准形式（求最小值）的线性规划问题时，与对应的变量都可以被选作换入变量。（√）3度为0的点称为悬挂点。（X）4表上作业法实质上就是求解运输问题的单纯形法。（√）5一个图G是树的充分必要条件是边数最少的无孤立点的图。（X）6如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。（对）7单纯形法计算中，如不按最小比列原则选取换出变量，则在下一个解中至少有一个基变量的值为负。(对）8若线性规划的原问题有无穷多最优解，则其最偶问题也一定具有无穷多最优解。（对）9运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有惟一最优解，有无穷多最优解，无界解，无可行解。（错）10如果运输问题的单位运价表的某一行（或某一列）元素再乘上那个一个常数k，最有调运方案将不会发生变化。（错）11目标规划模型中，应同时包含绝对约束与目标约束。（错）12线性规划问题是目标规划问题的一种特殊形式。（错）14在线性规划的图解法中，基可行解一定可以在顶点得到。（√）15运输问题解的情况有四种：无可行解；无界解；唯一最优解；无穷多最优解。（×）16如果单纯形表中，某一检验数大于0，而且对应变量所在列中没有正数，则线性规划问题无最优解（√）18线性规划问题标准型中，使目标函数达到最小值的可行解称为最优解。（×）四、计算题1.用单纯形法解下列线性规划问题3212maxxxxZs.t.3x1+x2+x360x1-x2+2x310x1+x2-x320x1,x2,x30解：引入松弛变量x4、x5、x6，标准化得，3212maxxxxZs.t.3x1+x2+x3+x4=60x1-x2+2x3+x5=10x1+x2-x3+x6=0x1,x2,x3，x4、x5、x6，≥0建初始单纯形表，进行迭代运算：CBXbb’2-11000θx1x2x3x4x5x60x460311100200x510[1]-1201010*0x62011-100120102*-110000x43004-51-307.52x1101-12010---0x6100[2]-30-115*22001*-30-200x4100011-1-22x115100.500.50.5-1x2501-1.50-0.50.532500-1.50-1.5-0.5由最优单纯形表可知，原线性规划的最优解为：(15,5,0)T最优值为：z*=25。2.求解下面运输问题。某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示：问：应如何调运，可使得总运输费最小?销地产地1B2B3B4B产量1A2A3A1089523674768252550销量15203035100解：（1）最小元素法：设xij为由Ai运往Bj的运量（i=1,2,3;j=1,2,3,4）,列表如下：销地产地1B2B3B4B产量1231520302555252550销量15203035100所以，基本的初始可行解为：x14=25；x22=20；x24=5；X31=15；x33=30；x34=5其余的xij=0。（2）求最优调运方案：会求检验数，检验解的最优性：11=2；12=2；13=3；21=1；23=5；32=-1会求调整量进行调整：=5销地产地1B2B3B4B产量12315155302510252550销量15203035100再次检验能够写出正确结论解为：x14=25；x22=15；x24=10x31=15，x32=5x33=30其余的xij=0。最少运费为：5353.某种子商店希望订购一批种子。据已往经验，种子的销售量可能为500，1000，1500或2000公斤。假定每公斤种子的订购价为6元，销售价为9元，剩余种子的处理价为每公斤3元。要求：（1）建立损益矩阵；（2）用悲观法决定该商店应订购的种子数。（3）建立后悔矩阵，并用后悔值法决定商店应订购的种子数。（1）益损矩阵如下表所示：销售订购S1500S21000S31500S42000A1500A21000A31500A4200015000－1500－3000150030001500015003000450030001500300045006000（2）悲观法：A1，订购500公斤。（3）后悔矩阵如下表所示：S1S2S3S4最大后悔值A101500300045004500A215000150030003000A330001500015003000A445003000150004500按后悔值法商店应取决策为A2或A3，即订购1000公斤或1500公斤。4（15分）用表上作业法求下表中给出的运输问题的最优解。销地产地甲乙丙丁产量Ⅰ327650Ⅱ752360Ⅲ254525销量60402015解：因为销量：3+5+6+4+3=21；产量：9+4+8=21；为产销平衡的运输问题。（1分）由最小元素法求初始解：销地产地甲乙丙丁戊产量Ⅰ459Ⅱ44Ⅲ31138销量35463（5分）用位势法检验得：销地产地甲乙丙丁戊UⅠ○10○145○70Ⅱ○114○12○30○12-9Ⅲ31○1131V019593（7分）所有非基变量的检验数都大于零，所以上述即为最优解且该问题有唯一最优解。此时的总运费：min45594103112011034150z。（2分）5求下表所示效率矩阵的指派问题的最小解，工作工人ABCDE甲127979乙89666丙71712149丁15146610戊14107109解：系数矩阵为：1279798966671712149151466104107109（3分）从系数矩阵的每行元素减去该行的最小元素，得：50202230000105729800406365经变换之后最后得到矩阵：70202430000835011800404143相应的解矩阵：0100000010000010010010000（13分）由解矩阵得最有指派方案：甲—B，乙—D,丙—E，丁—C，戊—A或者甲—B,乙—C,丙—E，丁—D，戊—A（2分）所需总时间为：Minz=32（2分）6某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？解：共可设计下列5种下料方案，见下表设x1,x2,x3,x4,x5分别为上面5种方案下料的原材料根数。这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5约束条件：s.t.x1+2x2+x4≥1002x3+2x4+x5≥100方案1方案2方案3方案4方案52.9m120102.1m002211.5m31203合计7.47.37.27.16.6剩余料头00.10.20.30.83x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥07运用单纯形法求解下面线性规划问题。12121212max33515.6224,0zxxxxstxxxx解（1）加入松弛变量34,xx，上述模型可转化为1212312412max33515.6224,0zxxxxxstxxxxxcj3130θCBXBbx1x2x3x40x315351050x424[6]2014z031000x