运筹学判断题讲解

1、谦那愎习线性规划的每或'堡解对应 可行域的一个 顶点.X单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个 基变量的值为负.4单纯形法的迭代计算是从一个可行解转换 到目标函数值更大的另一可行解.X线性规划模型增加一个约束条件,可行域的 范围一般将缩小，减少一个约束案件,可行 域一般将扩大.4若LP模型的可行域非空有界，则其顶点中必存在最优解若可行域是空集，则表明存在矛盾的约束条件。4用单纯形法求LP问题，若最终表上非基变量的检验 数均为非正，则该模型一定有唯一最优解。x对于取值无约束的变量盯通常令士二大厂X' ' j在用单纯形法求稼的最优解中有可能

2、出现JJ 凡具备优化、限制、选择条件且能将条件用关于决策变量的线性表达式表示出来的问题可以考虑用线性规划模型处理4 用单纯形法求解LP时，无论是极大化问题还是极小化问题，用来确定基变量的最小比值原则相同。， 若X是某LP的最优解，贝UX必为该LP可行域的某一个顶点X 用单纯形法求解LP问题，若最终表上非基变量的检验数均严格小于零，则该模型一定有唯一的最优解。 单纯形法通过最小比值法选取换出变量是为了保持 解的可行性。对一个有n个变量m个约束的标准型的线性规划问题，其可行域的顶点恰好为C个。义图解法同单纯形法虽然求解的形式不同，但 从几何上解释，两者是一致的。v一旦一个人工变量在迭代中变为非基变

3、量后,该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。V若X，X2分别是某一线性规划问题的最优解,则x = 4X 也是该线性规划问题的最优解，其中为正的实数。判断： 任何线性规划问题存在并具有唯一的对偶问题. 已知“为线性规划的对偶问题的最优解，如果 二0,说明在最优生产计划中第i种资源一定有 剩余.x 已知火为线性规划的对偶问题的最优解，如果 说明在最优生产计划中第，种资源已经完 全耗尽.判断： 若线性规划的原问题有无穷多最优解，则其对偶 问题也一定具有无穷多解.X 根据对偶的性质，当原问题无界解时，其对偶问愚无可行解，反之，当对偶问题无可行解，其原问题具 有无界解. 若线性规划

4、问题的原问题存在可行解，则对偶问题也一定存在可行解若线性规划的原问题和其对偶问题都具有可行解,则该线性规划问题一定具有有限最优解.X判断：运输问题是一种特殊的线性规划模型,而求解结果也可能出现下列四种情况之一：有惟一最优解，有无穷多最优解，无界解，无可行解。X 表上作业法实质上就是求解运输问题的单纯形法。 如果运输问题单位运价表的某一行（或某一列） 元素分别乘上一个常数K,最优方案将不会发生变 化。 当所有产地产量和销地的销量均为整数值时，运输问题的最优解也为整数值。判断: 在运输问题中，只要任意给出一组含（m+n1）个非零修的且满足斗，尸艺就可以作为一个初始基可行解X 按最小元素法（或伏格尔

5、法）给出的初始基可行解，从每一空格出发可以找出且能找出惟一的闭回路。 如果运输问题单位运价表的某一行（或某一列）元 素分别加上一个常数K,最优方案将不会发生变化。 如果在运输问题或转运问题模型中£j都是从产地i 到销地j的最小运输费用，则运输问题同转运问题将得 到相同的最优解判断题： 线性规划问题是目标规划问题的一种特殊形式 V 正偏差变量取正值，负偏差变量取负值；x 目标规划模型中，应同时包含系统约束（绝对约 束）与目标约束；X 目标规划模型中存在的约束条件内+出+7-4+=3则该约束是系统约束。X判断：>用分支定界法求一个极大化的整数规划时，任何一 个可行解的目标函数值是该

6、问题目标函数值的下 界.7A用分支定界法求一个极大化的整数规划时，当得到 多于一个可行解时，通常可以任取一个作为下界值, 再进行比较和剪枝.XA用割平面求纯整数规划时,要求包括松弛变量在内 的全部变量必须取整数.DA用割平面求整数规划时,构造的割平面有可能切去 一些不属于最优解的整数解。x判断：A整数规划解的目标函数值一般优于其相应的线性规 划问题的解的目标函数值。XA指派问题数学模型的形式同运输问题十分相似，故 也可以用表上作业法求解。7A分枝定界法在需要分枝时必须满足：一是分枝后的 各子问题必须容易求解；二是各子问题解的集合必 须覆盖原问题的解。4> 0-1规划的隐枚举法是分枝定界的

7、特例。 V判断题 1.动态规划模型中，问题的阶段数目等于问题中子 问题的数目；V 2 .动态规划中，定义状态时应保证在各个阶段中所 做决策的相互独立性；V 3.动态规划的最优性原理保证了从某一状态开始 的未来决策独立于先前已作出的决策；4 4 .对于一个动态规划问题，应用顺推或逆推解法可 能会得到不同的结果；X 5 .假如一个线性规划问题含有5个变量和3个约束 条件，则用动态规划求解时将划分为3个阶段，每 个阶段的状态将由一个五维的向量组成；X 6.动态规划问题的基本方程是将一个多阶段的决 策问题转化为一系列具有递推关系的单阶段的决 策问题。V判断题： 图论中的图不仅反映了研究对象之间的关系, 而且是真实图形的写照，以因而对图中点与 点的相对位置、点与点连线的长短曲直等都 要严格注意。X 在任一图G中，当点集V确定后，树图是G中 边数最少的连通图。Y连通图G的支撑树是取图G的点和G的所有 边组成的树。X Dijkstra算法栗求边的长度非负。7 最小割集等于最大流。x 求最小树可用破圈法。' 在最短路问题中，发点到收点的最短路长是唯一的。V 最大流问题是找从发点到收点的路，使得通过这条路 的流量最大。7 容量是弧（访