运筹学试题及答案11.doc

------------------------------------------------------------------------------------------------ ——————————————————————————————————————运筹学试题及答案 11 运筹学试题及答案一、填空题: (每空格 2 分,共 16 分) 1 、线性规划的解有唯一最优解、无穷多最优解、无界解和无可行解四种。 2 、在求运费最少的调度运输问题中,如果某一非基变量的检验数为 4 ,则说明如果在该空格中增加一个运量运费将增加 4。 3、“如果线性规划的原问题存在可行解, 则其对偶问题一定存在可行解”,这句话对还是错? 错 4 、如果某一整数规划: MaxZ=X1+X2 X1+9/14X2 ≤ 51/14 -2X1+X2 ≤ 1/3 X1,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 包含 B ------------------------------------------------------------------------------------------------ —————————————————————————————————————— 7. 已知下表是制订生产计划问题的一张 LP 最优单纯形表( 极大化问题,约束条件均为“≤”型不等 3???21??-1 问:(1 )写出 B=??1/? ?00?1??? (2) 对偶问题的最优解: Y =( 5,0, 23,0,0)T 8. 线性规划问题如果有无穷多最优解,则单纯形计算表的终表中必然有___ 某一个非基变量的检验数为 0______ ; 9. 极大化的线性规划问题为无界解时,则对偶问题_ 无解_____ ; 10. 若整数规划的松驰问题的最优解不符合整数要求, 假设 Xi=b i 不符合整数要求, INT ( bi )是不超过 bi 的最大整数, 则构造两个约束条件: Xi≥ INT ( bi)+1和 Xi≤ INT ( bi) ,分别将其并入上述松驰问题中,形成两个分支,即两个后继问题。 11. 知下表是制订生产计划问题的一张 LP 最优单纯形表(极大化问题,约束条件均为“≤”型不等式)其中 1/8 问:(2 )写出 B-1= ?201??? ?104? ?116??? 二、计算题( 60 分) 1 、已知线性规划( 20 分) MaxZ=3X1+4X2 ------------------------------------------------------------------------------------------------ —————————————————————————————————————— 1+X2 ≤5 2X1+4X2 ≤ 12 3X1+2X2 ≤8 1,X2 ≥02