运筹学判断题.pptx

《运筹学判断题.pptx》由会员分享，可在线阅读，更多相关《运筹学判断题.pptx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、判断:线性规划的每一个基解对应可行域的一个顶点线性规划的每一个基解对应可行域的一个顶点单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负一个基变量的值为负单纯形法的迭代计算是从一个可行解转换到目标函数值更大的另一可行解单纯形法的迭代计算是从一个可行解转换到目标函数值更大的另一可行解线性规划模型增加一个约束条件线性规划模型增加一个约束条件,可行域的可行域的范围一般将缩小范围一般将缩小,减少一个约束条件减少一个约束条件,可行域可行域一般将扩大一般将扩大.第1页/共17页若LP模型的可行域非空有界

2、，则其顶点中必存在最优解若可行域是空集，则表明存在矛盾的约束条件。用单纯形法求LP问题，若最终表上非基变量的检验数均为非正，则该模型一定有唯一最优解。n对于取值无约束的变量对于取值无约束的变量xj,通常令通常令xj=xj-xj在用单纯形法求得的最优解中有可能出现在用单纯形法求得的最优解中有可能出现xj0,xj0第2页/共17页凡具备优化、限制、选择条件且能将条件用关于决策变量的线性表达式表示出来的问题可以考虑用线性规划模型处理用单纯形法求解LP时，无论是极大化问题还是极小化问题，用来确定基变量的最小比值原则相同。若X是某LP的最优解，则X必为该LP可行域的某一个顶点用单纯形法求解LP问题，若最

3、终表上非基变量的检验数均严格小于零，则该模型一定有唯一的最优解。单纯形法通过最小比值法选取换出变量是为了保持解的可行性。第3页/共17页对一个有n个变量m个约束的标准型的线性规划问题，其可行域的顶点恰好为Cnm个。图解法同单纯形法虽然求解的形式不同，但从几何上解释，两者是一致的。一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。若X1，X2分别是某一线性规划问题的最优解，则 也是该线性规划问题的最优解，其中 为正的实数。第4页/共17页判断:任何线性规划问题存在并具有唯一的对偶问题.已知y*i为线性规划的对偶问题的最优解,如果y*i=0,说明在

4、最优生产计划中第i种资源一定有剩余.已知y*i为线性规划的对偶问题的最优解,如果y*i0,说明在最优生产计划中第i种资源已经完全耗尽.第5页/共17页判断:若线性规划的原问题有无穷多最优解,则其对偶问题也一定具有无穷多解.根据对偶的性质,当原问题无界解时,其对偶问题无可行解,反之,当对偶问题无可行解,其原问题具有无界解.若线性规划问题的原问题存在可行解，则对偶问题也一定存在可行解若线性规划的原问题和其对偶问题都具有可行解，则该线性规划问题一定具有有限最优解.第6页/共17页判断:运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有惟一最优解，有无穷多最优解，无界解，无可

5、行解。表上作业法实质上就是求解运输问题的单纯形法。如果运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数K，最优方案将不会发生变化。当所有产地产量和销地的销量均为整数值时,运输问题的最优解也为整数值。第7页/共17页判断:在运输问题中,只要任意给出一组含(m+n-1)个非零xij的且满足 就可以作为一个初始基可行解.按最小元素法(或伏格尔法)给出的初始基可行解,从每一空格出发可以找出且能找出惟一的闭回路。如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数K，最优方案将不会发生变化。如果在运输问题或转运问题模型中,Cij都是从产地i到销地j的最小运输费用,则运输问题同转运问题

6、将得到相同的最优解第8页/共17页判断题判断题:线性规划问题是目标规划问题的一种特殊形式线性规划问题是目标规划问题的一种特殊形式正偏差变量取正值，负偏差变量取负值；正偏差变量取正值，负偏差变量取负值；目标规划模型中，应同时包含系统约束（绝对目标规划模型中，应同时包含系统约束（绝对约束）与目标约束；约束）与目标约束；目标规划模型中存在的约束条件目标规划模型中存在的约束条件则该约束是系统约束。则该约束是系统约束。第9页/共17页判断判断:用分支定界法求一个极大化的整数规划时用分支定界法求一个极大化的整数规划时,任何任何一个可行解的目标函数值是该问题目标函数值一个可行解的目标函数值是该问题目标函数值

7、的下界的下界.用分支定界法求一个极大化的整数规划时用分支定界法求一个极大化的整数规划时,当得当得到多于一个可行解时到多于一个可行解时,通常可以任取一个作为下通常可以任取一个作为下界值界值,再进行比较和剪枝再进行比较和剪枝.用割平面求纯整数规划时用割平面求纯整数规划时,要求包括松弛变量在要求包括松弛变量在内的全部变量必须取整数内的全部变量必须取整数.用割平面求整数规划时用割平面求整数规划时,构造的割平面有可能切构造的割平面有可能切去一些不属于最优解的整数解。去一些不属于最优解的整数解。第10页/共17页判断：判断：整数规划解的目标函数值一般优于其相应的线性整数规划解的目标函数值一般优于其相应的线

8、性规划问题的解的目标函数值。规划问题的解的目标函数值。指派问题数学模型的形式同运输问题十分相似，指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解。故也可以用表上作业法求解。分枝定界法在需要分枝时必须满足：一是分枝后分枝定界法在需要分枝时必须满足：一是分枝后的各子问题必须容易求解；二是各子问题解的集的各子问题必须容易求解；二是各子问题解的集合必须覆盖原问题的解。合必须覆盖原问题的解。0-10-1规划的隐枚举法是分枝定界的特例。规划的隐枚举法是分枝定界的特例。第11页/共17页判断题判断题1.1.动态规划模型中动态规划模型中,问题的阶段数目等于问题中问题的阶段数目等于问题中子问题

9、的数目子问题的数目;2.2.动态规划中动态规划中,定义状态时应保证在各个阶段中定义状态时应保证在各个阶段中所做决策的相互独立性所做决策的相互独立性;3.3.动态规划的最优性原理保证了从某一状态开动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已作出的决策始的未来决策独立于先前已作出的决策;4.4.对于一个动态规划问题对于一个动态规划问题,应用顺推或逆推解法应用顺推或逆推解法可能会得到不同的结果；可能会得到不同的结果；5.5.假如一个线性规划问题含有假如一个线性规划问题含有5 5个变量和个变量和3 3个约个约束条件，则用动态规划求解时将划分为束条件，则用动态规划求解时将划分为3 3个

10、阶段，个阶段，每个阶段的状态将由一个五维的向量组成；每个阶段的状态将由一个五维的向量组成；6.6.动态规划问题的基本方程是将一个多阶段的动态规划问题的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段决策问题转化为一系列具有递推关系的单阶段的决策问题。的决策问题。第12页/共17页判断题判断题:图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，以因而对图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，以因而对图中点与点的相对位置、点与点连线的长短曲直等都要严格注意。图中点与点的相对位置、点与点连线的长短曲直等都要严格注意。在任一图在任一图G G中，当点集中

11、，当点集V V确定后，树图是确定后，树图是G G中边数最少的连通图。中边数最少的连通图。连通图连通图G的支撑树是取图的支撑树是取图G的点和的点和G的所有的所有边组成的树。边组成的树。第13页/共17页lDijkstra算法要求边的长度非负。算法要求边的长度非负。l最小割集等于最大流。最小割集等于最大流。l求最小树可用破圈法。求最小树可用破圈法。l在最短路问题中，发点到收点的最短路长是唯一的。在最短路问题中，发点到收点的最短路长是唯一的。l最大流问题是找从发点到收点的路，使得通过这条路最大流问题是找从发点到收点的路，使得通过这条路的流量最大。的流量最大。l容量容量Cij是弧是弧(i,j)的实际通过量。的实际通过量。l可行流是最大流的充要条件是不存在发点到收点的增可行流是最大流的充要条件是不存在发点到收点的增广链。广链。第14页/共17页 任意可行流的流量不超过任意割量。任意可行流的流量不超过任意割量。任意可行流的流量不小于最小割量。任意可行流的流量不小于最小割量。可行流的流量等于每条弧上的流量之和。可行流的流量等于每条弧上的流量之和。连通图一定有支撑树。连通图一定有支撑树。是一条增广链，则后向弧上满足流量是一条增广链，则后向弧上满足流量f 0.第15页/共17页第16页/共17页感谢您的观看！第17页/共17页