运筹学判断题.ppt

运筹判断复习 判断 线性规划的每一个基解对应可行域的一个顶点 单纯形法计算中 如不按最小比值原则选取换出变量 则在下一个解中至少有一个基变量的值为负 单纯形法的迭代计算是从一个可行解转换到目标函数值更大的另一可行解 线性规划模型增加一个约束条件 可行域的范围一般将缩小 减少一个约束条件 可行域一般将扩大 若LP模型的可行域非空有界 则其顶点中必存在最优解 若可行域是空集 则表明存在矛盾的约束条件 用单纯形法求LP问题 若最终表上非基变量的检验数均为非正 则该模型一定有唯一最优解 对于取值无约束的变量xj 通常令xj x j x j在用单纯形法求得的最优解中有可能出现x j 0 x j 0 凡具备优化 限制 选择条件且能将条件用关于决策变量的线性表达式表示出来的问题可以考虑用线性规划模型处理用单纯形法求解LP时 无论是极大化问题还是极小化问题 用来确定基变量的最小比值原则相同 若X是某LP的最优解 则X必为该LP可行域的某一个顶点用单纯形法求解LP问题 若最终表上非基变量的检验数均严格小于零 则该模型一定有唯一的最优解 单纯形法通过最小比值法选取换出变量是为了保持解的可行性 对一个有n个变量m个约束的标准型的线性规划问题 其可行域的顶点恰好为Cnm个 图解法同单纯形法虽然求解的形式不同 但从几何上解释 两者是一致的 一旦一个人工变量在迭代中变为非基变量后 该变量及相应列的数字可以从单纯形表中删除 而不影响计算结果 若X1 X2分别是某一线性规划问题的最优解 则也是该线性规划问题的最优解 其中为正的实数 判断 任何线性规划问题存在并具有唯一的对偶问题 已知y i为线性规划的对偶问题的最优解 如果y i 0 说明在最优生产计划中第i种资源一定有剩余 已知y i为线性规划的对偶问题的最优解 如果y i 0 说明在最优生产计划中第i种资源已经完全耗尽 判断 若线性规划的原问题有无穷多最优解 则其对偶问题也一定具有无穷多解 根据对偶的性质 当原问题无界解时 其对偶问题无可行解 反之 当对偶问题无可行解 其原问题具有无界解 若线性规划问题的原问题存在可行解 则对偶问题也一定存在可行解若线性规划的原问题和其对偶问题都具有可行解 则该线性规划问题一定具有有限最优解 判断 运输问题是一种特殊的线性规划模型 因而求解结果也可能出现下列四种情况之一 有惟一最优解 有无穷多最优解 无界解 无可行解 表上作业法实质上就是求解运输问题的单纯形法 如果运输问题单位运价表的某一行 或某一列 元素分别乘上一个常数K 最优方案将不会发生变化 当所有产地产量和销地的销量均为整数值时 运输问题的最优解也为整数值 判断 在运输问题中 只要任意给出一组含 m n 1 个非零xij的且满足就可以作为一个初始基可行解 按最小元素法 或伏格尔法 给出的初始基可行解 从每一空格出发可以找出且能找出惟一的闭回路 如果运输问题单位运价表的某一行 或某一列 元素分别加上一个常数K 最优方案将不会发生变化 如果在运输问题或转运问题模型中 Cij都是从产地i到销地j的最小运输费用 则运输问题同转运问题将得到相同的最优解 判断题 线性规划问题是目标规划问题的一种特殊形式正偏差变量取正值 负偏差变量取负值 目标规划模型中 应同时包含系统约束 绝对约束 与目标约束 目标规划模型中存在的约束条件 则该约束是系统约束 判断 用分支定界法求一个极大化的整数规划时 任何一个可行解的目标函数值是该问题目标函数值的下界 用分支定界法求一个极大化的整数规划时 当得到多于一个可行解时 通常可以任取一个作为下界值 再进行比较和剪枝 用割平面求纯整数规划时 要求包括松弛变量在内的全部变量必须取整数 用割平面求整数规划时 构造的割平面有可能切去一些不属于最优解的整数解 判断 整数规划解的目标函数值一般优于其相应的线性规划问题的解的目标函数值 指派问题数学模型的形式同运输问题十分相似 故也可以用表上作业法求解 分枝定界法在需要分枝时必须满足 一是分枝后的各子问题必须容易求解 二是各子问题解的集合必须覆盖原问题的解 0 1规划的隐枚举法是分枝定界的特例 判断题 1 动态规划模型中 问题的阶段数目等于问题中子问题的数目 2 动态规划中 定义状态时应保证在各个阶段中所做决策的相互独立性 3 动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已作出的决策 4 对于一个动态规划问题 应用顺推或逆推解法可能会得到不同的结果 5 假如一个线性规划问题含有5个变量和3个约束条件 则用动态规划求解时将划分为3个阶段 每个阶段的状态将由一个五维的向量组成 6 动态规划问题的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的决策问题 判断题 图论中的图不仅反映了研究对象之间的关系 而且是真实图形的写照 以因而对图中点与点的相对位置 点与点连线的长短曲直等都要严格注意 在任一图G中 当点集V确定后 树图是G中边数最少的连通图 连通图G的支撑树是取图G的点和G的所有边组成的树 Dijkstra算法要求边的长度非负 最小割集等于最大流 求最小树可用破圈法 在最短路问题中 发点到收点的最短路长是唯一的 最大流问题是找从发点到收点的路 使得通过这条路的流量最大 容量Cij是弧 i j 的实际通过量 可行流