[运筹学]_期末考试_试卷A_答案
一、判断题(共计10分,每小题1分,对的打√,错的打X )
1. 无孤立点的图一定是连通图。
2. 对于线性规划的原问题和其对偶问题,若其中一个有最优解, 另一个也一定有最优解。
3. 如果一个线性规划问题有可行解,那么它必有最优解。 4.对偶问题的对偶问题一定是原问题。
5.用单纯形法求解标准形式(求最小值)的线性规划问题时,与都可以被选作换入变量。
6.若线性规划的原问题有无穷多个最优解时,其对偶问题也有无穷 多个最优解。
7. 度为0的点称为悬挂点。
8. 表上作业法实质上就是求解运输问题的单纯形法。 9. 一个图G 是树的充分必要条件是边数最少的无孤立点的图。
σj >0
对应的变量
1、线性规划的解有唯一最优解、无穷多最优解、四种。
2、在求运费最少的调度运输问题中,如果某一非基变量的检验数为4,则说明 如果在该空格中增加一个运量运费将增加4 。
3、“如果线性规划的原问题存在可行解,则其对偶问题一定存在可行解”,这句话对还是错? 错 4、如果某一整数规划: MaxZ=X1+X2 X 1+9/14X2≤51/14 -2X 1+X2≤1/3 X 1,X 2≥0且均为整数
所对应的线性规划(松弛问题)的最优解为X 1=3/2,X 2=10/3,MaxZ=6/29,我们现在要对X 1进行分枝,应该分为 X 1≤1 和 X 1≥2 。
5、在用逆向解法求动态规划时,f k (sk ) 的最优解 。
6. 假设某线性规划的可行解的集合为D ,而其所对应的整数规划的可行解集合为B ,那么D
和B 的关系为 D 包含 B
7. 已知下表是制订生产计划问题的一张LP 最优单纯形表(极大化问题,约束条
3⎫⎛-21
⎪-1
问:(1)写出B = -1/3. 02/3⎪
00-1⎪⎝⎭
(2)对偶问题的最优解: Y=(5,0,23,0,0)T
8. 线性规划问题如果有无穷多最优解,则单纯形计算表的终表中必然有___某一个非基变量的检验数为0______;
9. 极大化的线性规划问题为无界解时,则对偶问题_无解_________;
10. 若整数规划的松驰问题的最优解不符合整数要求,假设X i =bi 不符合整数要求,INT (b i )是不超过b i 的最大整数,则构造两个约束条件:Xi ≥INT (b i )+1 和 Xi≤INT (b i ) ,分别将其并入上述松驰问题中,形成两个分支,即两个后继问题。
11. 知下表是制订生产计划问题的一张LP 最优单纯形表(极大化问题,约束条
问:(1)对偶问题的最优解: Y=(4,0,9,0,0,0)T (2)写出B -1=
⎛201⎫ ⎪
104⎪
116⎪⎝⎭