《运筹学判断题》PPT课件.ppt

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