运筹学复习资料

运筹学复习
一、    填空题
1、线性规划中，满足非负条件的基本解称为基本可行解，对应的基称为可行基线.
2、性规划的目标函数的系数是其对偶问题的右端常数；而若线性规划为最大化问题，则3、对偶问题为最小化问题。
4、在运输问题模型中， m+n-1个变量构成基变量的充要条件是不含闭回路。
5、动态规划方法的步骤可以总结为：逆序求解最优目标函数，顺序求__最优策略、最优路线和最优目标函数值。
6、工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；7、对不定步数问题，用迭代法求解，有函数迭代法和策略迭代法两种方法。
8、在图论方法中，通常用点表示人们研究的对象，用边表示对象之间的某种联系。
9、一个无圈且连通的图称为树。
10、图解法提供了求解只含有两个决策变量的线性规划问题的方法．
11、图解法求解生产成本最小线性规划问题时，等成本线越往左下角移动，成本越低．
12、如果线性规划问题有有限最优解，则该最优解一定在可行域的边界上上达到。
13、线性规划中，任何基对应的决策变量称为基变量． 
14、原问题与对偶问题是相互对应的． 线性规划中，对偶问题的对偶问题是原问题．
15、在线性规划问题中，若某种资源的影子价格为10，则适当增加该资源量，企业的收益将_会 (“会”或“不会”)提高．
16、表上作业法实质上就是求解运输问题的单纯形法．
17、产销平衡运输问题的基变量共有m+n-1个． 
18、动态规划不仅可以用来解决和时间有关的多阶段决策问题，也可以处理与时间无关的多阶段决策问题．
19、构成动态规划模型，需要进行以下几方面的工作：正确选择阶段（k）变量，正确选择状态（Sk）变量，正确选择_ 决策（UK）变量，列出状态转移方程, 列出_阶段指标函数_，建立函数基本方程．
20、动态规划方法可以用来解决和某些与时间有关的问题，但也可以用来解决和某些与时间无关的问题.在图论方法中，图是指由点与边和点与弧组成的示意图．
21、网络最短路径是指从网络起点至终点的一条权之和最小的路线．    
简述单纯形法的计算步骤：
   第一步：找出初始可行解，建立初始单纯形表。
   第二步：判断最优，检验各非基变量 的检验数 。
1若所有的 ，则基B为最优基，相应的基可行解即为基本最优解，计算停止。
2若所有的检验数 ，又存在某个非基变量的检验数所有的 ，则线性规划问题有无穷多最优解。
3若有某个非基变量的检验数 ，并且所对应的列向量的全部分量都非正，则该线性规划问题的目标函数值无上界，既无界解，停止计算。
第三步：换基迭代
（1）    当存在 ，选 进基来改善目标函数。若检验数大于0的非基变量不止一个，则可以任选其中之一来作为进基变量。
（2）    进基变量 确定后，按最小比值原则选择出基变量 。若比值最小的不止一个，选择其中之一出基。（3）做主元变换。
反复进行上述过程就可以找到最优解或判断出没有有限最优解。
二、    选择题
 1.甲、乙、丙、丁四个球队进行比赛，任两个队都有一场比赛，且没有和局，用来表示这四个队比赛状况的图是（ D ）。
A 、一棵树           B、没有圈
C 、连通图             D、任两点之间有一条带有方向的线
2．minZ=3x1+4x2, x1+x2≥4, 2x1+x2≤2, x1、x2≥0，则（ A ）。
A.无可行解 B.有唯一最优解 C.有多重最优解 D.有无界解
3．互为对偶的两个线性规划问题的解存在关系（ D ）。
A.原问题无可行解，对偶问题也无可行解
B.对偶问题有可行解，原问题也有可行解
C.若最优解存在，则最优解相同
D.一个问题有无界解，则另一个问题无可行解
5．如果某种资源的影子价格大于其市场价格，则说明（ B ）。
A．该资源过剩 B．该资源稀缺 C．企业应尽快处理该资源 D．企业应充分利用该资源，开僻新的生产途径
6. 运输问题中分配运量的格所对应的变量为 （ A ）。
A基变量 B 非基变量 C 松弛变量 D 剩余变量
7．maxZ=4x1-x2, 4x1+3x2≤24, x2≤5, x1、x2≥0，则（ B ）。
A.无可行解 B.有唯一最优解
C.有多重最优解 D.有无界解
8．对偶单纯形法的最小比值规划则是为了保证（ D ）。
A.使原问题保持可行 B.逐步消除对偶问题不可行性
C.使原问题有最优解 D.使对偶问题保持可行
9. 线性规划模型不包括下列（ D ）要素。
A．目标函数 B．约束条件 C．决策变量 D．状态变量
10.在约束方程中引入人工变量的目的是（ D ）。
A 体现变量的多样性 B 变不等式为等式 C 使目标函数为最优 D 形成一个单位阵
11. 求目标函数为极大的线性规划问题时，若全部非基变量的检验数≤O，且基变量中有人工变量时该问题有（ B ）。
A无界解 B无可行解 C 唯一最优解 D无穷多最优解
12.线性规划最优解不唯一是指（ D ）。
A.可行解集合无界 B.存在某个检验数λk>0且aik≤0(i=1,2,?,m)
C.可行解集合是空集 D.最优表中存在非基变量的检验数为零
13.minZ=4x1+6x2，4x1+3x2≤24，x2≥9，x1，x2≥0，则（ A ）。
A.无可行解 B.有唯一最优解 C.有无界解 D.有多重解
14.原问题有5个变量3个约束，其对偶问题（ C ）。
A.有3个变量3个约束 B.有5个变量3个约束
C.有3个变量5个约束 D.有5个变量5个约束
15.下列错误的结论是（ B ）。
A.原问题没有最优解，对偶问题也没有最优解
B.对偶问题有可行解，原问题也有可行解
C.原问题有最优解，对偶问题也有最优解
D.原问题无界解，对偶问题无可行解
16.maxZ=3x1+2x2,2x1+3x2≤14,x1+0.5x2≤4.5,x1,x2≥0且为整数，对应线性规划的最优解是（3.25，2.5），它的整数规划的最优解是（ A ）。
A．(4，1)   B．(4，3)   C．(3，2)    D．(2，4)
19．若线性规划存在可行解，则（ B ）。
A.一定有最优解    B.可行域非空
C.有多重解    D.具有无界解
20．有4个产地5个销地的平衡运输问题模型具有特征（ C ）。
A.有9个变量9个约束 B.有9个变量20个约束
C.有20个变量9个约束 D.有9个基变量
21．互为对偶的两个线性规划问题的解存在关系（ D ）。
A.若最优解存在，则最优解相同
B.原问题无可行解，对偶问题也无可行解
C.一个问题无界，则另一个问题也无界
D.若最优解存在，则最优值相同
22．在分枝定界法中（ B ）。
A.最大值问题的目标值是各分枝的下界
B.最大值问题的目标值是各分枝的上界
C.最小值问题的目标值是各分枝的上界
D.以上结论都不对
23．对于线性规划标准型下例错误的说法是（ C ）。
A.标准型的目标函数是求最大值
C.标准型的常数项非正 B.标准型的目标函数是求最小值 D.标准型的变量一定要非负
24．表上作业法中初始方案均为（A ）。
A 可行解 B 非可行解 C 待改进解 D 最优解
25．minZ=3x1+4x2，x1+x2≥4，2x1+x2≤2，x1、x2≥0，则（A ）。
A．无可行解 B．有唯一最优解 C．有多重最优解 D．有无界解
26. 下列方法中用于求解分配问题的是（ D ）。
A．单纯形表B．分枝定界法C．表上作业法D．匈牙利法
27．minZ=x1-x2，2x1+x2≥1，x1+4x2≤4，x1，x2=0或1，最优解是（ B ）。
A．(0,0） B．(0,1） C．(1,0） D．(1,1)
28、最早运用运筹学理论的是（ A ）
A 二次世界大战期间，英国军事部门将运筹学运用到军事战略部署
B 美国最早将运筹学运用到农业和人口规划问题上
C 二次世界大战期间，英国政府将运筹学运用到政府制定计划
D 50年代，运筹学运用到研究人口，能源，粮食，第三世界经济发展等问题上
29、下列哪些不是运筹学的研究范围（ D ）
A 质量控制
B 动态规划
C 排队论
D 系统设计
30、对于线性规划问题，下列说法正确的是（ D ）
A 线性规划问题可能没有可行解
B 在图解法上，线性规划问题的可行解区域都是“凸”区域
C 线性规划问题如果有最优解，则最优解可以在可行解区域的顶点上到达
D 上述说法都正确
31、下面哪些不是线性规划问题的标准形式所具备的（ C ）
A 所有的变量必须是非负的
B 所有的约束条件（变量的非负约束除外）必须是等式
C 添加新变量时，可以不考虑变量的正负性
D 求目标函数的最小值
32、在求解运输问题的过程中运用到下列哪些方法（ D ）
A 西北角法
B 位势法
C 闭回路法
D 以上都是
33、在用单纯形法求解线性规划问题时，下列说法错误的是（ D ）
A 如果在单纯形表中，所有检验数都非正，则对应的基本可行解就是最优解
B 如果在单纯形表中，某一检验数大于零，而且对应变量所在列中没有正数，则线性规划问题没有最优解
C 利用单纯形表进行迭代，我们一定可以求出线性规划问题的最优解或是判断线性规划问题无最优解
D 如果在单纯形表中，某一检验数大于零，则线性规划问题没有最优解
34、为了在各住宅之间安装一条供暖管道，若要求所用材料最省，则应采用（ B ）。
A．求最大流量法 B.求最小支撑树法
C．求最短路线法 D.树的逐步生成法
35、下列图形中是一棵树的为：(B )
A B C D
36、若T是图G的最小支撑树，则（ C ）
A．T必唯一 B. G不一定是连通图
C．T中必不含圈 D.G中不含圈
三、判断题
1. 线性规划问题的每一个基本可行解对应可行域的一个顶点。( √ )
2. 如果在单纯形表中，所有的检验数都为正，则对应的基本可行解就是最优解。（ × ）
3. 在可行解的状态下，原问题与对偶问题的目标函数值是相等的。×
4．可行解集非空时,则在极点上至少有一点达到最优值。（× ）
5．原问题具有无界解，则对偶问题不可行。（ √ ）
6．互为对偶问题，或者同时都有最优解，或者同时都无最优解。（ .√ ）
7．求最小值问题的目标函数值是各分枝函数值的下界。（ √ ）
8．对偶问题无可行解，原问题具有无界解。（ × ）
9．对偶问题具有无界解，则原问题无最优解。（ .√ ）
10．匈牙利法求解指派问题的条件是效率矩阵的元素非负。（ √ ）
11．变量取0或1的规划是整数规划。（ √ ）
12．图解法提供了求解线性规划问题的通用方法。×
13．产地数为3，销地数为4的平衡运输中，变量组{x11, x13, x22, x33, x34}可作为一组基变量。（ × ）
14. 在单纯形表中，基变量对应的系数矩阵往往为单位矩阵。√
15.若线性规划存在两个不同的最优解,则必有无穷个最优解。（√ ）
16．若原问题具有m个约束，则它的对偶问题具有m个变量。（ √ ）
17．动态规划只是用来解决和时间有关的问题。（ × ）
18. 线性规划问题的最优解一定在可行域的顶点达到。（ × ）
19. 如果一个线性规划问题有可行解，那么它必有最优解。（ × ）
20. 用单纯形法求解一般线性规划时，当目标函数求最大值时，若所有的检验数Cj-Zj≤0，则问题达到最优。( .√ )
21．线性规划的最优解是可行解。（ .√ ）
22．运输问题一定存在最优解。（ √ ）
23．人工变量出基后还可能再进基。（ × ）
24．对于一个动态规划问题，应用顺推法和逆推法可能会得到不同的最优解。（× ）25．线性规划可行域无界,则具有无界解。（× ）
26. 对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。( √ )
27. 表上作业法实质上就是求解运输问题的单纯形法。( √ )
28. 指派问题的解中基变量的个数为m＋n。( × )
29. 整数规划的可行解集合是离散型集合。（ √ ）
30. 在解静态规划模型时，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量的维数。（ .√ ）
31．在用割平面法求解整数规划时，经过有限次迭代一定可以割出极点为整数的点。（ √ ）
32.在任一图G中，当点集V确定后，树图是G中边数最少的连通图。（ √ ）
三、填空
1.原问题的第1个约束方程是“=”型，则对偶问题相应的变量是 自由 变量。
 2．可以作为表上作业法的初始调运方案的填有数字的方格数应为 m+n-1 个(设问题中含有m个供应地和n个需求地)
3. 调运方案的调整是要在检验数出现 负值 的点为顶点所对应的闭回路内进行运量的调整。
4．用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的 下界 。
5．在0 - 1整数规划中变量的取值可能是 0或 。
6. 分枝定界法一般每次分枝数量为 2 个。
7．线性规划题中，如果在约束条件中出现等式约束，我们通常用增加 人工变量 的方法来产生初始可行基。
8. 若线性规划问题有最优解，则最优解一定可以在可行域的 顶点（极点） 达到。
9. 如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为 等式 。
10. 若X、Y分别是线性规划的原问题和对偶问题的可行解，则有CX ≤ Yb。
11．如果线性规划的原问题增加一个约束条件，相当于其对偶问题增加一个 变量 。
 12．按照表上作业法给出的初始调运方案，从每一空格出发可以找到且仅能找到 1 条闭回路。
13. 对于一个有n项任务需要有n个人去完成的分配问题，其解中取值为1的变量数为 n 个。
14.经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数为动态规划的 阶段数 。
15、求支撑树有 破圈 法和 避圈 法两种方法。