运筹期末复习.ppt

《运筹期末复习.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、习题及复习课一、选择（20）二、线性规划（20）三、运输问题（10）四、分配问题（20）五、图与网络分析（20）六、建模（10）题型一、单纯形法及对偶理论二、运输问题三、分配问题四、图与网络分析复习要点一、单纯形法及对偶理论二、运输问题三、分配问题四、图与网络分析复习要点单纯形法的基本方法基本方法：确定初始基可行解检验是否最优？转到另一更好的基可行解停YN方法前提：模型化为标准型单纯形法总结1、Min型单纯形表与Max型的区别仅在于：令σk=min{σj≤0}的xk进基，当σ≥0时最优。2、解的几种情况及其在单纯形表上的体现（讨论Ma

2、x型）唯一最优解σj≤0,非基σ≤0无穷多最优解σj≤0有非基σk=0无界解有σk>0但B-1Pk≤0无可行解用大M法求解，最优基中含有X人退化解有两个或两个以上的min{θ}MaxZ=CXAX≤bX≥0s.t.原问题（P）：对偶问题（D）：MinW=bTYATY≥CTY≥0s.t.原问题对偶问题目标函数maxmin目标函数约束条件≤≥=≥变量≤无约束≥变量符号≤无约束≥≤约束条件=1、对称性（P）与（D）互为对偶对偶性质与定理2、弱对偶性设X、Y分别为（P）、（D）的任一可行解，则证：X、Y为（P）、（D）的可行解5、对偶定理若（P

3、）有最优解，则（D）也有最优解，且二者最优值相等.3、解的最优性设、分别为（P）与（D）的可行解，且则4、无界性若（P）为无界解，则（D）无可行解若（D）为无界解，则（P）无可行解★6、松紧定理（互补松弛性）最重要！设分别为（P）与（D）的可行解对偶问题最优解的经济解释——影子价格Y*=(y1*,y2*,……，ym*）为DP的最优解，则yi*表示LP某资源bi变化1个单位对目标产生的影响，称yi*为bi的影子价格。对偶单纯形法单纯形法是以保持原问题可行为条件，即不论进行怎样的基变换，常数列　　　必须保持非负。利用对偶问题的对称性，我们

4、从另一个角度来考虑求解原问题最优解的方法，这种方法以保持对偶问题可行为条件，即不论进行何种基变换，必须保持所有的检验数非负，同时取消原问题必须可行的要求，即取消常数列的非负限制，通过基变换使原问题在非可行解的基础上逐步转换成基本可行解，一旦原问题的基本解可行，则该基本可行解也就是最优解，这就是对偶单纯形法的基本思想。单纯形法：可行性　→　最优性对偶单纯形法：最优性　→　可行性灵敏度分析线性规划问题所对应的数据集合Ａ，b，Ｃ常常是通过预测或估计所得到的统计数据，在实际使用中，不免会有一定的误差。而且随着市场环境，工艺条件和资源数量的改变

5、，这些数据完全可能发生变化。因此有必要来分析一下当这些数据发生波动时，对目前的最优解，最优值或者最优基会产生什么影响，这就是所谓的灵敏度分析。灵敏度分析主要讨论如下二类问题：数据集合在什么范围内波动将不影响最优解或最优基？若最优解发生变化，应如何找到新的最优解。CC1C2…CnCBXBbx1x2…xnCB1XB1B-1bB-1A=B-1(P1，P2，…，Pn)CB2XB2::CBmXBmC-CBTB-1A列出标准型线性规划问题最优单纯形表：（1）价值向量C的改变当价值向量由　　　　　　　　　　　　　　　　时，检验行应修改为：目标函数值

6、应为。只要非基变量检验数那么原最优解仍然为最优。至于目标函数值是否改变，取决于（2）资源系数b的变化当右端项向量　　　　　时，改变的是表中右端常数列。此时基变量　　　　　　，目标函数值　　　　　　　　　。而检验行的检验向量保持不变。若　　　　　　　，可用对偶单纯形法再次进行迭代，直到求得新最优解。为了使B可行，只要或（3）约束矩阵A的改变假设原线性规划问题有一个最优解　　　　其中Ｂ为最优基，约束矩阵A的改变可能导致不同的最优解和最优基.以下介绍增加一个变量的情形：增加一个变量增加一个新变量　　，对应的价值系数为　　，对应的系数列向量为

7、　　，可得新的线性规划问题：设　　　，则为新问题的一个可行解。因此可在此基础上开始单纯形法，求新的最优解。如果　　，则　　　　，　　　是新问题的最优解。否则以　　　为换入变量进行基变换，继续使用单纯形算法为新的线性规划寻求一个最优解。一、单纯形法及对偶理论二、运输问题三、分配问题四、图与网络分析复习要点运输问题的求解——表上作业法确定初始可行调运方案最小元素法、伏格尔法（至少掌握其中一种）判别当前可行方案是否最优闭回路法对现有方案进行调整闭回路法用最小元素法确定初始可行调运方案最小元素法的基本思想：就近尽量满足供应3134630104

8、03030300用闭回路法进行最优性检验1、找空格的闭回路：以某空格为起点，用水平线或垂直线向前划，只能在碰到某一数字格时才能转弯，按照这一规则继续前进，直到回到起始的空格为止。3134632、根据闭回路计算空格的检验数