运筹期末复习.ppt

,习题及复习课,一、选择（20）二、线性规划（20）三、运输问题（10）四、分配问题（20）五、图与网络分析（20）六、建模（10）,题型,一、单纯形法及对偶理论二、运输问题三、分配问题四、图与网络分析,复习要点,一、单纯形法及对偶理论二、运输问题三、分配问题四、图与网络分析,复习要点,单纯形法的基本方法,基本方法：,确定初始基可行解,检验是否最优？,转到另一更好的基可行解,停,Y,N,方法前提：模型化为标准型,单纯形法总结,1、Min型单纯形表与Max型的区别仅在于：令k=minj0的xk进基，当0时最优。,2、解的几种情况及其在单纯形表上的体现（讨论Max型）,唯一最优解,j0,非基0,无穷多最优解,j0有非基k=0,无界解,有k0但B-1Pk0,无可行解,用大M法求解，最优基中含有X人,退化解,有两个或两个以上的min,原问题（P）：,对偶问题（D）：,MinW=bTY,ATYCTY0,s.t.,1、对称性,（P）与（D）互为对偶,对偶性质与定理,2、弱对偶性,设X、Y分别为（P）、（D）的任一可行解，则,证：,X、Y为（P）、（D）的可行解,5、对偶定理,若（P）有最优解，则（D）也有最优解，且二者最优值相等.,3、解的最优性,设、分别为（P）与（D）的可行解，且,则,4、无界性,若（P）为无界解，则（D）无可行解,若（D）为无界解，则（P）无可行解,6、松紧定理（互补松弛性）最重要！,设分别为（P）与（D）的可行解,对偶问题最优解的经济解释影子价格,Y*=(y1*,y2*,，ym*）为DP的最优解，则yi*表示LP某资源bi变化1个单位对目标产生的影响，称yi*为bi的影子价格。,对偶单纯形法,单纯形法是以保持原问题可行为条件，即不论进行怎样的基变换，常数列必须保持非负。利用对偶问题的对称性，我们从另一个角度来考虑求解原问题最优解的方法，这种方法以保持对偶问题可行为条件，即不论进行何种基变换，必须保持所有的检验数非负，同时取消原问题必须可行的要求，即取消常数列的非负限制，通过基变换使原问题在非可行解的基础上逐步转换成基本可行解，一旦原问题的基本解可行，则该基本可行解也就是最优解，这就是对偶单纯形法的基本思想。单纯形法：可行性最优性对偶单纯形法：最优性可行性,灵敏度分析,线性规划问题所对应的数据集合，b，常常是通过预测或估计所得到的统计数据，在实际使用中，不免会有一定的误差。而且随着市场环境，工艺条件和资源数量的改变，这些数据完全可能发生变化。,因此有必要来分析一下当这些数据发生波动时，对目前的最优解，最优值或者最优基会产生什么影响，这就是所谓的灵敏度分析。,灵敏度分析主要讨论如下二类问题：数据集合在什么范围内波动将不影响最优解或最优基？若最优解发生变化，应如何找到新的最优解。,列出标准型线性规划问题最优单纯形表：,（1）价值向量C的改变,当价值向量由时，检验行应修改为：,目标函数值应为。,只要非基变量检验数那么原最优解仍然为最优。至于目标函数值是否改变，取决于,（2）资源系数b的变化,当右端项向量时，改变的是表中右端常数列。此时基变量，目标函数值。而检验行的检验向量保持不变。,（3）约束矩阵A的改变,假设原线性规划问题有一个最优解其中为最优基，,约束矩阵A的改变可能导致不同的最优解和最优基.以下介绍增加一个变量的情形：,增加一个变量,增加一个新变量，对应的价值系数为，对应的系数列向量为，可得新的线性规划问题：,设，则为新问题的一个可行解。因此可在此基础上开始单纯形法，求新的最优解。,如果，则，是新问题的最优解。否则以为换入变量进行基变换，继续使用单纯形算法为新的线性规划寻求一个最优解。,一、单纯形法及对偶理论二、运输问题三、分配问题四、图与网络分析,复习要点,运输问题的求解表上作业法,确定初始可行调运方案最小元素法、伏格尔法（至少掌握其中一种）判别当前可行方案是否最优闭回路法对现有方案进行调整闭回路法,用最小元素法确定初始可行调运方案最小元素法的基本思想：就近尽量满足供应,3,1,3,4,6,3,0,1,0,4,0,3,0,3,0,3,0,0,用闭回路法进行最优性检验1、找空格的闭回路：以某空格为起点，用水平线或垂直线向前划，只能在碰到某一数字格时才能转弯，按照这一规则继续前进，直到回到起始的空格为止。,2、根据闭回路计算空格的检验数：检验数=奇数顶点的单位运价之和偶数顶点的单位运价之和,1,2,1,-1,10,12,检验数的经济含义：当由产地Ai往销地Bj增运一个单位货物时所引起的总运输成本的变化数,结论：若所有检验数都大于等于0，则当前方案最优,对现有方案进行调整在负的检验数中选择绝对值最大的空格，在方案表中从该空格出发，沿着其闭回路依次标上“+q”、“-q”，,+q,-q,+q,-q,其中q表示最大调整量，它的取值为标“-q”的数字中最小的数值。,于是q=min3,1=1,调整后的方案