2015年运筹学复习资料

1、运筹学复习一、 填空题1、线性规划中，满足非负条件的基本解称为基本可行解 ，对应的基称为 可行基线 .2、性规划的目标函数的系数是其对偶问题的右端常数 ；而若线性规划为最大化问题， 则3、对偶问题为 最小化问题 。4、在运输问题模型中， m n 1个变量构成基变量的充要条件是 不含闭回路 。5、动态规划方法的步骤可以总结为： 逆序求解 最优目标函数 ，顺序求 _最优策略 、最优 路线 和 最优目标函数值 。6、工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；7、对不定步数问题，用迭代法求解，有 函数 迭代法和 策略 迭代法两种方法。8、在图论方法中，通常用 点 表示人

2、们研究的对象，用 边 表示对象之间的某种联系。9、一个 无圈 且连通的图称为树。10、图解法提供了求解只含有 两个 决策变量的线性规划问题的方法11、图解法求解生产成本最小线性规划问题时，等成本线越往左下角移动， 成本越 低 12、如果线性规划问题有有限最优解，则该最优解一定在可行域的边界上 上达到。13、线性规划中，任何基对应的决策变量称为 基变量 14、原问题与对偶问题是 相互 对应的 线性规划中，对偶问题的对偶问题是 原问题15、在线性规划问题中， 若某种资源的影子价格为 10，则适当增加该资源量， 企业的收益将 _会 （ “会”或“不会” ） 提高16、表上作业法实质上就是求解 运输

3、问题的单纯形法17、产销平衡运输问题的基变量共有 m+n-1 个18、动态规划不仅可以用来解决和时间有关的 多阶段决策 问题，也可以处理 与时间无关的多阶段决策 问题19、构成动态规划模型，需要进行以下几方面的工作：正确选择 阶段（ k ）变 量，正确选择 状态（ Sk）变量，正确选择 _ 决策 （UK）变量，列出 状态转移 方程, 列出_阶段指标函数 _，建立函数基本 方程20、动态规划方法可以用来解决和某些与 时间 有关的问题，但也可以用来解 决和某些与 时间无关的问题 .在图论方法中，图是指由 点与边和点与弧组成的 示意图21、网络最短路径是指从网络起点至终点的一条 权之和 最小的路线简

4、述单纯形法的计算步骤： 第一步：找出初始可行解，建立初始单纯形表。 第二步：判断最优，检验各非基变量 的检验数 。1 若所有的 ，则基 B 为最优基，相应的基可行解即为基本最优解，计算停止。2 若所有的检验数 ，又存在某个非基变量的检验数所有的 ，则线性规划问题有无穷多最优 解。3 若有某个非基变量的检验数 ，并且所对应的列向量的全部分量都非正，则该线性规划问 题的目标函数值无上界，既无界解，停止计算。第三步：换基迭代（1） 当存在 ，选 进基来改善目标函数。 若检验数大于 0 的非基变量不止一个， 则可以 任选其中之一来作为进基变量。（2） 进基变量 确定后， 按最小比值原则选择出基变量 。

5、若比值最小的不止一个， 选择 其中之一出基。 （ 3）做主元变换。 反复进行上述过程就可以找到最优解或判断出没有有限最优解。二、 选择题1. 甲、乙、丙、丁四个球队进行比赛，任两个队都有一场比赛，且没 有和局，用来表示这四个队比赛状况的图是（ D ）。A 、一棵树B、没有圈C 、连通图D、任两点之间有一条带有方向的线2minZ=3x1+4x2, x 1+x24, 2x1+x2 2, x1 、 x2 0，则（ A ）。A. 无可行解 B. 有唯一最优解 C. 有多重最优解 D. 有无界解3互为对偶的两个线性规划问题的解存在关系（D ）。A. 原问题无可行解，对偶问题也无可行解B. 对偶问题有可行

6、解，原问题也有可行解C. 若最优解存在，则最优解相同D. 一个问题有无界解，则另一个问题无可行解5如果某种资源的影子价格大于其市场价格，则说明（B ）。A该资源过剩 B 该资源稀缺 C企业应尽快处理该资源 D企业 应充分利用该资源，开僻新的生产途径6. 运输问题中分配运量的格所对应的变量为 （ A ）。A 基变量 B 非基变量 C 松弛变量 D 剩余变量7maxZ=4x1-x2, 4x1+3x2 24, x2 5, x1 、 x2 0，则（ B ）。A. 无可行解 B. 有唯一最优解C. 有多重最优解 D. 有无界解8对偶单纯形法的最小比值规划则是为了保证（D ）。A. 使原问题保持可行 B.

7、 逐步消除对偶问题不可行性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. 存在某个检验数 k0且aik 0（i=1,2,?,m）C.

8、 可行解集合是空集 D. 最优表中存在非基变量的检验数为零13. minZ=4x1+6x2 ，4x1+3x2 24，x29，x1，x20，则（ 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

9、+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.若最优解存在，则最优解相同

10、B. 原问题无可行解，对偶问题也无可行解C. 一个问题无界，则另一个问题也无界D. 若最优解存在，则最优值相同22在分枝定界法中（ B ）。A.最大值问题的目标值是各分枝的下界B. 最大值问题的目标值是各分枝的上界C. 最小值问题的目标值是各分枝的上界D.以上结论都不对23对于线性规划标准型下例错误的说法是（C ）。A. 标准型的目标函数是求最大值C. 标准型的常数项非正 B. 标准型的目标函数是求最小值 D. 标准型 的变量一定要非负24表上作业法中初始方案均为（ A ）。A 可行解 B 非可行解 C 待改进解 D 最优解25minZ=3x1+4x2，x1+x24，2x1+x2 2， x1、

11、 x2 0，则（ A ）。A无可行解 B 有唯一最优解 C 有多重最优解 D有无界解26. 下列方法中用于求解分配问题的是（ D ）。A单纯形表 B分枝定界法 C表上作业法 D匈牙利法27minZ=x1-x2 ，2x1+x21，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 年代，运筹学运用到研究人口，能源，粮

12、食，第三世界经济发展 等问题上29、下列哪些不是运筹学的研究范围（ D ）A 质量控制B 动态规划C 排队论D 系统设计30、对于线性规划问题，下列说法正确的是（D ）A 线性规划问题可能没有可行解B 在图解法上，线性规划问题的可行解区域都是“凸”区域C 线性规划问题如果有最优解，则最优解可以在可行解区域的顶点上 到达D 上述说法都正确31、下面哪些不是线性规划问题的标准形式所具备的（C ）A 所有的变量必须是非负的B 所有的约束条件（变量的非负约束除外）必须是等式C 添加新变量时，可以不考虑变量的正负性D 求目标函数的最小值32、在求解运输问题的过程中运用到下列哪些方法（D ）A 西北角法B

13、 位势法C 闭回路法D 以上都是33、在用单纯形法求解线性规划问题时，下列说法错误的是（D ）A 如果在单纯形表中，所有检验数都非正，则对应的基本可行解就是最优解B 如果在单纯形表中，某一检验数大于零，而且对应变量所在列中没 有正数，则线性规划问题没有最优解C 利用单纯形表进行迭代，我们一定可以求出线性规划问题的最优解 或是判断线性规划问题无最优解D 如果在单纯形表中，某一检验数大于零，则线性规划问题没有最优 解34、为了在各住宅之间安装一条供暖管道，若要求所用材料最省，则 应采用（ B ）。A求最大流量法 B. 求最小支撑树法C求最短路线法 D. 树的逐步生成法35、下列图形中是一棵树的为：

14、 （B ）A B C D36、若 T 是图 G的最小支撑树，则（ C ）A T必唯一 B. G 不一定是连通图CT 中必不含圈 D.G 中不含圈三、判断题1. 线性规划问题的每一个基本可行解对应可行域的一个顶点。（ ）2. 如果在单纯形表中，所有的检验数都为正，则对应的基本可行解 就是最优解。（ ）3. 在可行解的状态下，原问题与对偶问题的目标函数值是相等的4可行解集非空时 , 则在极点上至少有一点达到最优值。 （ ）5原问题具有无界解，则对偶问题不可行。 （ ）6互为对偶问题，或者同时都有最优解，或者同时都无最优解。（ .）7求最小值问题的目标函数值是各分枝函数值的下界。 （ ）8对偶问题无

15、可行解，原问题具有无界解。 （ ）9对偶问题具有无界解，则原问题无最优解。 （ . ） 10匈牙利法求解指派问题的条件是效率矩阵的元素非负。（ ）11变量取 0 或 1 的规划是整数规划。 （ ）12图解法提供了求解线性规划问题的通用方法。13产地数为 3，销地数为 4 的平衡运输中，变量组 x11, x13, x22, x33, x34 可作为一组基变量。 （ ）14. 在单纯形表中，基变量对应的系数矩阵往往为单位矩阵。15. 若线性规划存在两个不同的最优解 , 则必有无穷个最优解。 （ ） 16若原问题具有 m个约束，则它的对偶问题具有 m个变量。（ ） 17动态规划只是用来解决和时间有关

16、的问题。 （ ）18. 线性规划问题的最优解一定在可行域的顶点达到。 （ ）19. 如果一个线性规划问题有可行解，那么它必有最优解。 （ ）20. 用单纯形法求解一般线性规划时，当目标函数求最大值时，若所 有的检验数 Cj-Zj 0，则问题达到最优。 （ . ）21线性规划的最优解是可行解。 （ . ）22运输问题一定存在最优解。 （ ）23人工变量出基后还可能再进基）24对于一个动态规划问题，应用顺推法和逆推法可能会得到不同的 最优解。（ ）25线性规划可行域无界 , 则具有无界解。 （ ）26. 对于线性规划的原问题和其对偶问题，若其中一个有最优解，另 一个也一定 有最优解。 （ ）27.

17、 表上作业法实质上就是求解运输问题的单纯形法。 （ ）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. 如果原问