运筹学选择和简答

一、选择 1.区分 基本解、可行解、基本可行解。基本解：一定是可行解。可行解：满足所有约束条件的解。 基本可行解：满足所有约束条件的可行解。2.图解法适用于包含（两个决策变量）的线性规划问题的求解。3.图解法基本情况：有唯一的最优解 无可行解； 无穷解 无界解 若有最优解，则最优点一定可以在顶点处取得，若最优解在两个顶点处取得且相等则最优解可以在两个顶点构成的线段上取得。 线性规划有最优解，则一定在定点处取得（X） 若有最优解，一定有一个可行域顶点对应最优解（对）4.标准形式特点： 1.约束条件为等式2.约束条件右端常数项为非负数。3.决策变量取非负数。5.单纯形法最优性检验，目标函数，求最大值时 检验数小于等于0，求极小值时 检验数大于等于0。6.对偶价格：在约束条件常数项中增加一个单位而使最优目标函数值得到改进的数量。当约束条件中的（松弛变量或者剩余变量）不为0时，对偶价格为0 ，某一约束条件的对偶价格仅仅在（某一范围是有效的）。一个约束条件对应一个对偶价格当约束条件常数增加一个单位时，（课本23页）1. 如果对偶价格大于零，则其最优目标函数值得到改进，即求最大值时，最优目标函数值变的更大，求最小值时，最优目标函数值变得更小。2. 如果对偶价格小于零，则其最优目标值变坏，即求最大值时，最优目标函数值变小；求最小值时，最优目标函数值变大了。3. 如果对偶价格等于零，则其最优目标函数值不变。7.基、基变量、非基变量满足的条件。基：线性无关的可逆矩阵（满秩矩阵）由单位矩阵的各列向量组成。基变量：与基变量相应的变量（不为0），非基变量：与非基变量相应的变量（为0）。8.单纯形法几种特殊情况出现的条件和判断解的方法。有最优解：（ 唯一最优解 无穷多最优解：非基变量检验数等于0）无最优解：（无可行解 无界解 无可行解 ）。9.求目标函数值最小的线性规划问题的单纯形法：大M法。10.单纯形法对与约束条件类型对偶价格的取值。 约束条件对偶价格的取值等于这个约束条件对应的（松弛变量）的 Zj值等于这个约束条件对应的（剩余变量）的 Zj值的相反数-Zj =等于这个约束条件对应的（人工变量）的 Zj 值11.对偶规划的基本性质：课本118页 1) 对称性，即对偶问题的对偶是原问题。2) 弱对偶性，即即原问题（1）和原问题（2）的可行解 （xy ），都有（CxbTY ）.3) 最优性4) 强对偶性5) 互补松弛变量性。12.运输问题：1) M个产地，N个销地则基变量的个数（M+N-1）个2) 平衡运输问题，产地M=N销地。13.表上作业法 闭回路，（从空格开始）以（ 非基变量）为起点，以基变量的顶点的闭回路，存在且唯一，一个空格存在唯一的闭回路。14.求运费最小则所有检验数0.15.M个人N 项任务指派问题MN每个人至多承担一项任务MN一项任务至少由一个人完成M=N 一个人只能完成一项任务16.分枝定界法：上界=下界 有最优解。17.动态规则概念：状态：指每个阶段开始时所处的自然状况或者客观条件，（Sk）表示第k个阶段状态。决策：是某一段内的选择，Xn（Sn）表示第n阶段处于Sn 状态是的决策变量。这个决策变量又决定了第n+1阶段的状态。策略：由所有各个阶段的决策变量组成的决策函数序列称为全过程策略，简称策略，记为P1,n（S1）。指派函数：P1(S1) 为全过程上的最优指标函数， Fk(Sk)为子过程上的最优指标函数。指标是指从某点到终点的距离，最有指标到最短距离。J阶段的阶段指标记为（rj（Sj，Xj）表示（j阶段Sj的状态下作出Xj决策的指标值）。状态转移（Sn+1=Tn(Sn,Xn) ）。表示第n+1阶段的状态由第n阶段的状态和第n阶段的决策所决定的。18.判断连通图和树19资源分配问题是离散确定性 机器负荷问题是连续确定性简答：1 人工变量和松弛变量的区别？人工变量是为了构造初始可行基得到初始可行解而人为的强加到原来的约束方程中去的，求极小值时使用的变量，取值0松弛变量时化标准型用的变量，可取0或正2弱对偶性推论 1） 原问题任一可行解的目标函数值是对偶问题目标函数值的下界，反之，对偶问题任一可行解的目标函数值是其原问题目标函数值得下界。2） 如果原问题有可行解，目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：此性质的逆不成立，当对偶问题无可行解时，原问题或具有无界解或无可行解，反之亦然）3） 若原问题有可行解而对偶问题无可行解，则原问题目标函数值无界，反之，对偶问题有可行解而原问题有可行解，则对偶问题的目标函数值无界。3单纯形法和对偶单纯形法的区别对偶单纯形法和单纯形法一样都是求解元线性规划问题的方法，单纯形法实在保持原问题的所有约束条件的常数大于等于0的情况下，通过迭代，使得所有的检验数都小于等于0，最后求得最优解对偶单纯形法则是在保持原问题的所有检验数都小于等于0的情况下，通过迭代，使得多有的约束条件的常数都大于等于0最后求得最优解4整数规划的解与它对应的线性规划的解有什么关系？任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值，任何求最小目标函数值得纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值5最大流问题的基本算法在对弧的容量的表示作了改进的网络图上1） 找出一条从发点到收点的路，在这