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

一、判断题（共计10分，每小题1分，对的打√，错的打X）1.无孤立点的图一定是连通图。2.对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定有最优解。3.如果一个线性规划问题有可行解，那么它必有最优解。4．对偶问题的对偶问题一定是原问题。5．用单纯形法求解标准形式（求最小值）的线性规划问题时，与0j对应的变量都可以被选作换入变量。6．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。7.度为0的点称为悬挂点。8.表上作业法实质上就是求解运输问题的单纯形法。9.一个图G是树的充分必要条件是边数最少的无孤立点的图。10.任何线性规划问题都存在且有唯一的对偶问题。①②③④⑤⑥⑦⑧⑨10X√X√√√X√X√1、线性规划的解有唯一最优解、无穷多最优解、无界解和无可行解四种。2、在求运费最少的调度运输问题中，如果某一非基变量的检验数为4，则说明如果在该空格中增加一个运量运费将增加4。3、“如果线性规划的原问题存在可行解，则其对偶问题一定存在可行解”，这句话对还是错？错4、如果某一整数规划：MaxZ=X1+X2X1+9/14X2≤51/14-2X1+X2≤1/3X1,X2≥0且均为整数所对应的线性规划（松弛问题）的最优解为X1=3/2，X2=10/3，MaxZ=6/29，我们现在要对X1进行分枝，应该分为X1≤1和X1≥2。5、在用逆向解法求动态规划时，fk(sk)的含义是：从第k个阶段到第n个阶段的最优解。6.假设某线性规划的可行解的集合为D，而其所对应的整数规划的可行解集合为B，那么D和B的关系为D包含B7.已知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“≤”型不等式）其中X3,X4,X5为松驰变量。XBbX1X2X3X4X5X4300-213X14/310-1/302/3X210100-1Cj-Zj00-50-23问：（1）写出B-1=1003/20.3/1312(2)对偶问题的最优解：Y＝（5，0，23，0，0）T8.线性规划问题如果有无穷多最优解，则单纯形计算表的终表中必然有___某一个非基变量的检验数为0______；9.极大化的线性规划问题为无界解时，则对偶问题_无解_________；10.若整数规划的松驰问题的最优解不符合整数要求，假设Xi=bi不符合整数要求，INT（bi）是不超过bi的最大整数，则构造两个约束条件：Xi≥INT（bi）＋1和Xi≤INT（bi），分别将其并入上述松驰问题中，形成两个分支，即两个后继问题。11.知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“≤”型不等式）其中X4,X5,X6为松驰变量。XBbX1X2X3X4X5X6X12110201X32/3001104X510-20116Cj-Zj000-40-9问：(1)对偶问题的最优解：Y＝(4,0,9,0,0,0)T（2）写出B-1=611401102