运筹学选择和简答

1、一、选择1. 区分 基本解、可行解、基本可行解。 基本解：一定是可行解。可行解：满足所有约束条件的解。 基本可行解：满足所有约束条件的可行解。2. 图解法适用于包含（ 两个决策变量 ）的线性规划问题的求解。3. 图解法基本情况： 有唯一的最优解 无可行解； 无穷解 无界解 若有最优解，则 最优点 一定可以 在顶点处取得，若 最优解在两个顶点处取得且相等 则最优 解可以在 两个顶点构成的线段 上取得。线性规划有最优解，则一定在定点处取得（X）若有最优解，一定有一个可行域顶点对应最优解（对）4. 标准形式特点： 1.约束条件为等式 2.约束条件右端常数项为非负数。 3.决策变量取非负数。5. 单纯

2、形法最优性检验，目标函数，求最大值时 检验数小于等于 0，求极小值时 检验数大于等于 0。6. 对偶价格：在约束条件常数项中增加一个单位而使最优目标函数值得到改进的数量。当约束条件中的（ 松弛变量 或者剩余变量） 不为 0 时，对偶价格为 0 ， 某一约束条件的对偶价格仅仅在（某一范围是有效的） 。一个约束条件对应一个对偶价格 当约束条件常数增加一个单位时， （课本 23 页）1. 如果对偶价格 大于零 ，则其最优目标函数值 得到改进 ，即求 最大值 时，最优目标函数值 变的 更大，求最小值时，最优目标函数值变得更小。2. 如果对偶价格 小于零 ，则其最优目标值 变坏，即求 最大值 时，最优目

3、标函数值 变小；求 最小值时，最优目标函数值变大了。3. 如果对偶价格 等于零 ，则其最优目标函数值 不变 。7. 基、基变量、非基变量满足的条件。 基：线性无关的可逆矩阵（满秩矩阵）由单位矩阵的各列向量组成。 基变量：与基变量相应的变量（ 不为 0）， 非基变量：与非基变量相应的变量（为 0）。8. 单纯形法几种特殊情况出现的条件和判断解的方法。 有最优解：（ 唯一最优解无穷多最优解：非基变量检验数等于0）无最优解：（无可行解无界解 无可行解 ）。9.求目标函数值最小的线性规划问题的单纯形法：大 M 法。10.单纯形法对与约束条件类型对偶价格的取值。约束条件对偶价格的取值等于这个约束条件对应

4、的（ 松弛变量 ）的 Zj 值等于这个约束条件对应的（ 剩余变量 ）的 Zj 值的相反数 -Zj=等于这个约束条件对应的（ 人工变量 ）的 Zj 值11. 对偶规划的基本性质：课本 118 页1）对称性，即对偶问题的对偶是原问题。2）弱对偶性，即即原问题（ 1）和原问题（ 2）的可行解 （ xy ），都有（ Cx bTY ）3）最优性4）强对偶性5）互补松弛变量性。12. 运输问题：1）M 个产地， N 个销地则基变量的个数（ M+N-1 ）个2）平衡运输问题，产地 M=N 销地。13. 表上作业法 闭回路，（从空格开始）以（ 非基变量 ）为起点，以 基变量 的顶点的闭回路， 存在且唯一， 一

5、个空 格存在唯一的闭回路。14. 求运费最小则所有检验数 0.个人 N 项任务指派问题M>N 每个人至多承担一项任务M<N 一项任务至少由一个人完成M=N 一个人只能完成一项任务16. 分枝定界法： 上界 =下界 有最优解。17. 动态规则概念： 状态：指每个阶段开始时所处的自然状况或者客观条件，（ Sk）表示第 k 个阶段状态。决策：是某一段内的选择， Xn（ Sn）表示第 n 阶段处于 Sn 状态是的决策变量。这个决策变 量又决定了第 n+1 阶段的状态。策略：由所有各个阶段的决策变量组成的决策函数序列称为全过程策略，简称策略，记为 P1,n（ S1）。指派函数： P1（S1）

6、 为全过程上的最优指标函数， Fk（Sk）为子过程上的最优指标函数。 指标是指从某点到终点的距离，最有指标到 最短距离。 J阶段的阶段指标记为（ rj（Sj，Xj）表示（ j 阶段 Sj 的状态下作出 Xj 决策的指 标值）。状态转移（ Sn+1=Tn（Sn,Xn） ）。 表示第 n+1 阶段的状态由第 n 阶段的状态和第 n 阶段的决策所决定的。18. 判断连通图和树19 资源分配 问题是 离散确定性 机器负荷问题是连续确定性 简答 ：1 人工变量和松弛变量的区别 人工变量是为了构造初始可行基得到初始可行解而 人为的强加到 原来的约束方程中去的， 求 极小值时使用的变量，取值 0 松弛变量时

7、 化标准型用的变量，可取 0 或正2 弱对偶性推论1）原问题任一可行解的目标函数值是对偶问题目标函数值的下界 ，反之，对偶问题任一可行解的目标函数值是其原问题目标函数值得下界。2）如果原问题有可行解，目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：此性质的逆不成立，当对偶问题无可行解时，原问题或具有无界解或无可行解，反之亦然）3）若原问题有可行解而对偶问题无可行解，则原问题目标函数值无界，反之，对偶问 题有可行解而原问题有可行解，则对偶问题的目标函数值无界。3 单纯形法和对偶单纯形法的区别 对偶单纯形法和单纯形法一样都是求解

8、元线性规划问题的方法， 单纯形法实在保持 原问题的 所有约束条件的常数大于等于 0 的情况下，通过迭代，使得所有的检验数都 小于等于 0，最 后求得最优解对偶单纯形法则是在保持 原问题的所有检验数都小于等于 0 的情况下，通过迭代，使得多 有的约束条件的常数都 大于等于 0 最后求得最优解4 整数规划的解与它对应的线性规划的解有什么关系任何求 最大目标函数值 的 纯整数规划或混合整数规划的最大目标函数值小于或等于 相应的线性规划的 最大目标函数值 ，任何求最小目标函数值得纯整数规划或混合整数规划的最小目 标函数值 大于或等于 相应的线性规划的 最小目标函数值5 最大流问题的基本算法在对弧的容量的表示作了改进的网络图上1) 找出一条从发点到收点的路