运筹学自测试卷.docx

数学13级运筹学自测试卷2一、单项选择题1使用人工变量法求解极大化的线性规划问题时，当所有的检验数0jd,但在基变量中仍含有非零的人工变量，表明该线性规划问题 (D)A有唯一的最优解B有无穷多最优解C为无界解D无可行解2当线性规划的可行解集合非空时一定（D）A.包含原点B.有界C无界D.是凸集3线性规划具有多重最优解是指（B）A.目标函数系数与某约束系数对应成比例。B最优表中存在非基变量的检验数为零。C可行解集合无界。D存在基变量等于零。4使用人工变量法求解极大化线性规划问题时，当所有的检验数，在基变量中仍含有非零的人工变量，表明该线性规划问题（ C ）A. 有唯一的最优解； B. 有无穷多个最优解；C. 无可行解；D. 为无界解 5在产销平衡运输问题中，设产地为个，销地为个，那么基可行解中非零变量的个数（ A ）A. 不能大于(m+n-1)； B. 不能小于(m+n-1)； C. 等于(m+n-1)； D. 不确定。 6如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足（B ）A. B. C. D. 7下列说法正确的为（ D ） A如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解 B如果线性规划的对偶问题无可行解，则原问题也一定无可行解 C在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数D如果线性规划问题原问题有无界解，那么其对偶问题必定无可行解4.用最小元素法求初始调运方案是，运输表中数字格的个数为（D）个。 m*n B、m+n C、m*n-1 D、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 0 B.1 C.-1 D.213如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足（B）A. B. C. D. 14.在一个网络中，如果从一个起点出发到所有的点，找出一条或几条路线，以使在这样一些路线中所采用的全部支线的总长度最小，这种方法称之为( D )A点的问题B.线的问题C.树的问题D.最小枝叉树问题15线性规划可行域的顶点一定是( ) A基本可行解 B非基本解 C非可行解 D最优解16X是线性规划的基本可行解则有( ) AX中的基变量非零，非基变量为零 BX不一定满足约束条件 CX中的基变量非负，非基变量为零 DX是最优解17要求不低于目标值，其目标函数是( ) A B C D二、填空题1. 线性规划问题中，如果在约束条件中没有单位矩阵作为初始可行基，我们通常用增加 人工变量 的方法来产生初始可行基。2. 当原问题可行，对偶问题不可行时，常用的求解线性规划问题的方法是 单纯形法。4对策行为的三个基本要素分别为局中人、策略集、赢得函数（支付函数）5用大M法求目标函数为极大值的线性规划问题时，引入的人工变量在目标函数中的系数应为：M6可以作为表上作业法的初始调运方案的填有数字的方格数应为：m+n1个(设问题中含有m个供应地和n个需求地)8 求解运输问题时，常用的判断运输方案是否最优的方法，一个是闭合回路，另一个是位势法11因为决策值不可能既超过目标值同时又未达到目标值，所以对于正、负偏差变量恒有（ ）三、判断题判断题（共计10分，每小题1分，对的打，错的打X）1.无孤立点的图一定是连通图。（ X ）2用单纯形法求解标准形式（求最小值）的线性规划问题时，与对应的变量都可以被选作换入变量。（ ）3度为0的点称为悬挂点。（ X ）4表上作业法实质上就是求解运输问题的单纯形法。（ ）5一个图G是树的充分必要条件是边数最少的无孤立点的图。（ X ）6如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。（ 对 ）7单纯形法计算中，如不按最小比列原则选取换出变量，则在下一个解中至少有一个基变量的值为负。 (对 ） 8若线性规划的原问题有无穷多最优解，则其最偶问题也一定具有无穷多最优解。（ 对 ） 9运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有惟一最优解，有无穷多最优解，无界解，无可行解。 （ 错 ）10如果运输问题的单位运价表的某一行（或某一列）元素再乘上那个一个常数，最有调运方案将不会发生变化。 （错 ） 11目标规划模型中，应同时包含绝对约束与目标约束。 （ 错 ）12线性规划问题是目标规划问题的一种特殊形式。 （ 错 ）14在线性规划的图解法中，基可行解一定可以在顶点得到。（ ）15运输问题解的情况有四种：无可行解；无界解；唯一最优解；无穷多最优解。（ ）16如果单纯形表中，某一检验数大于0，而且对应变量所在列中没有正数，则线性规划问题无最优解（）18线性规划问题标准型中，使目标函数达到最小值的可行解称为最优解。（ ）四、计算题1. 用单纯形法解下列线性规划问题 s. t. 3 x1 + x2 + x3 60 x 1- x 2 +2 x 3 10 x 1+ x 2- x 3 20 x 1, x 2 , x 3 0 解：引入松弛变量x4、 x5、 x6，标准化得， s. t. 3 x1 + x2 + x3+ x4 = 60 x 1- x 2 +2 x 3 + x5 = 10 x 1+ x 2- x 3 + x6 = 0 x 1, x 2 , x 3， x4、 x5、 x6，0 建初始单纯形表，进行迭代运算： CBXbb2-11000x1x2x3x4x5x60x460311100200x5101-1201010*0x62011-100120s102*-110000x43004-51-307.52x1101-12010-0x61002-30-115*s22001*-30-200x4100011-1-22x115100.500.50.5-1x2501-1.50-0.50.5s32500-1.50-1.5-0.5由最优单纯形表可知，原线性规划的最优解为： ( 15 , 5 , 0 )T 最优值为： z*=25。2. 求解下面运输问题。 某公司从三个产地A1、A2、A3 将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示：问：应如何调运，可使得总运输费最小? 销 地 产 地 产 量1089523674768252550销 ：（1）最小元素法： 设xij为由Ai运往Bj的运量（i=1,2,3; j=1,2,3,4）,列表如下： 销 地产 地产 量1231520302555252550销 所以，基本的初始可行解为：x14 =25； x22=20 ； x24 =5 ； X31 =15； x33 =30； x34=5 其余的xij=0。 （2）求最优调运方案：会求检验数，检验解的最优性：s11=2；s12=2；s13=3；s21=1；s23=5；s32= - 1 会求调整量进行调整：=5 销 地产 地产 量12315155302510252550销 次检验 能够写出正确结论解为：x14=25 ； x22 =15 ； x24 =10 x31 =15， x32 =5 x33=30其余的xij=0。 最少运费为： 5353. 某种子商店希望订购一批种子。据已往经验，种子的销售量可能为500，1000，1500或2000公斤。假定每公斤种子的订购价为6元，销售价为9元，剩余种子的处理价为每公斤3元。要求：（1）建立损益矩阵； （2）用悲观法决定该商店应订购的种子数。（3）建立后悔矩阵，并用后悔值法决定商店应订购的种子数。（1）益损矩阵如下表所示： 销 售订 购S1500S21000S31500S42000A1 500A2 1000A3 1500A4 20001500015003000150030001500015003000450030001500300045006000（2）悲观法：A1 ，订购500公斤。（3）后悔矩阵如下表所示： S1S2S3S4最大后悔值A101500300045004500A215000150030003000A330001500015003000A445003000150004500 按后悔值法商店应取决策为A2或A3 ，即订购1000公斤或1500公斤。 4（15分）用表上作业法求下表中给出的运输问题的最优解。销地产地 甲乙丙丁产量327650752360254525销量60402015解：因为销量：3+5+6+4+3=21；产量：9+4+8=21；为产销平衡的运输问题。 （1分）由最小元素法求初始解：销地产地 甲乙丙丁戊产量4594431138销量35463 （5分）用位势法检验得：销地产地甲乙丙丁戊U4504-931131V019593 （7分）所有非基变量的检验数都大于零，所以上述即为最优解且该问题有唯一最优解。此时的总运费：。（2分）5求下表所示效率矩阵的指派问题的最小解， 工作工人ABCDE甲127979乙89666丙71712149丁15146610戊14107109 解：系数矩阵为： （3分） 从系数矩阵的每行元素减去该行的最小元素，得： 经变换之后最后得到矩阵：相应的解矩阵：（13分）由解矩阵得最有指派方案：甲B，乙D,丙E，丁C，戊A或者甲B,乙C,丙E，丁D，戊A （2分）所需总时间为：Minz=32 （2分）6某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？解： 共可设计下列5 种下料方案，见下表设 x1,x2,x3,x4,x5 分别为上面 5 种方案下料的原材料根数。这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 约束条件： s.t. x1 + 2x2 + x4 100 2x3 + 2x4 + x5 100 3x1 + x2 + 2x3 + 3x5 100 x1,x2,x3,x4,x5 0 7运用单纯形法求解下面线性规划问题。 解（1）加入松弛变量，上述模型可转化为 cj3130CBXBbx1x2x3x40x315351050x42462014z031000x33041-0.51.23x1411/301/6-z12000-0.5最优解，最优值8已知运输问题的产销平衡表与单位运价表如下表所示 销地产地B1B2B3B4产量A11067124A21610599A35410104销量5246试用运用伏格尔法求出初始运输方案。解、 （1）用最小元素法求得初始可行基如下 销地产地B1B2B3B4产量A110 36 7 12 14 0 A216 10 5 49 59 -3A35 24 210 10 4 -5销量5 102 94 86 12（2）位势方程组为u1+v1=10 u1+v4=12u2+v3=5 u2+v4=9u3+v1=5 u3+v2=4令u10，解得v1=10 v2=9 v3=8 v4=12 u2 =-3 u3 =-5 各非基变量检验数为126（09）-3137（08）-12116（103）92210（93）43310（85）73410（125）3存在非基变量检验数为负，没有达到最优解9 已知某运输问题的产量、销量及运输单价如表。又知B地区需要的115单位必须满足要求：（1）列出该运输问题的产销平衡及单位运价表； （2）用最小元素法求出此运输问题的初始解。解：（1）据题意，需大于供，需要增加一个假想的产地丁，列出产销平衡及单位运价表如下：（2）用最小元素法求得初始解（因计算过程中最小元素有多个，可任选其一计算，计算的初始解不唯一）如下：10求解指派问题，并求出最小费用。（15分）Min z =（cij）44=解：用 “匈牙利法”求解。效率矩阵表示为：行约简标号列约简 至此已