第二章--对偶理论与灵敏度分析ppt课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 对偶理论与灵敏度分析,第二章 对偶理论与灵敏度分析,1,第一节 单纯形法的矩阵描述,对于标准形式的线性规划模型：,Max z CX,AX b,X 0,设B为一个基，它占据了A的m列，其它nm列用N表示，A=（B，N）。对X和C做对应的分块：,第一节 单纯形法的矩阵描述对于标准形式的线性规划模型：M,2,C=（C,B,，C,N,）,X,B,X,N,X=,则：,AX=（B，N）,X,B,X,N,=BX,B,NX,N,=b,得：,X,B,=B b B NX,N,（2.1）,-1,-1,C=（CB，CN）XBX=则：AX=（B，N）XB,3,z=CX=（C,B,，C,N,）,X,B,X,N,=C,B,X,B,C,N,X,N,=C,B,（B b B NX,N,）C,N,X,N,-1,-1,=C,B,B b（C,N,C,B,B N）X,N,（2.2）,-1,-1,式（2.1）、（2.2）分别为基变量和目标函数用非基变量的表达式，称为关于B的,典则形式,，简称,典式,。,设B为可行基，令X,N,=0，X,B,=B b 0，于是有基可行解：X,1,=（B b，0），对应的目标函数值：z,1,=C,B,B b。,由（2.2）可知非基变量的检验数为：,-1,-1,-1,T,z=CX=（CB，CN）XB=CBXB,4,N,=C,N,C,B,B N,对于基变量X,B,，检验数,B,=C,B,C,B,B B=0；故所有变量的检验数可统一为：,=C C,B,B A,写成分量形式，任意变量x,j,的检验数为：,j,=c,j,C,B,B P,j,当所有,j,0时，X,1,=（B b，0）是最优解，z,1,=C,B,B b 是最优值。,考虑线性规划的规范形式，其初始基变量是松弛变量，此时，A=（B，N，I），C=（C,B,，C,N,，0），用,-1,-1,-1,-1,-1,-1,N=CN CBB N-1-1-1,5,典式表示，写于单纯形表相应位置：,表2-1,C,B,X,B,B b,C,B,C,N,0,X,B,X,N,X,S,0,X,S,b,B,N,I,z,0,C,B,C,N,0,C,B,X,B,B b,I,B N,B,z,C,B,B b,0,C,N,C,B,B N,C,B,B,-1,-1,-1,-1,-1,-1,-1,典式表示，写于单纯形表相应位置：CBXBB bCBCN0,6,从表2-1可以看到，以B为基的单纯形表中的增广矩阵，是以B 左乘初始表的增广矩阵的结果。因此，在B为基的表中，与初始表单位矩阵相同位置处即为B的逆矩阵B 。,-1,-1,从表2-1可以看到，以B为基的单纯形表中的增,7,第二节 对偶问题的概念,一、对偶问题的提出,1、举例：,说明对偶问题的经济意义。,2、规范形式的对偶问题,LP（DP）：Max z=CX DP（LP）：Min w=Yb,AXb YAC,X0 Y0,第二节 对偶问题的概念一、对偶问题的提出,8,二、一般形式的对偶问题,一般形式对偶问题之间的对应规律：,目标函数：max与min相互对应；,目标函数系数与约束条件右端项相互对应；,约束条件：技术约束与变量符号约束相互对应。若规定线性规划问题两种规范形式的技术约束方向及变量符号约束方向为正向的，与之方向相反为反向的，等式技术约束和变量符号约束无限制为双向的，则一个问题中的正向、反向和双向约束，对应于另一个问题的正向、反向和双向约束，即两个对应的约束总属于同样的类型。,二、一般形式的对偶问题,9,第三节 对偶问题的基本性质,定理2.1,对偶问题的对偶是原问题。,（对称性定理）,定理2.2,设X、Y分别为原问题与对偶问题的可行解，则CXYb。,（弱对偶定理）,定理2.3,若X、Y分别为原问题与对偶问题的可行解，且CX=Yb，则两者均为最优解。,（最优性判定定理）,定理2.4,若原问题有最优解，则对偶问题也有最优解。设前者的最优基为B，则对偶最优解为Y=C,B,B ，且两者的最优值相等。,（强对偶定理）,-1,第三节 对偶问题的基本性质 定理2.1,10,定理2.5,若X、Y分别为原问题与对偶问题的可行解，则它们都是最优解的充要条件是：YX,S,=0和Y,S,X=0。,（互补松弛定理）,定理2.5 若X、Y分别为原问题与对,11,第四节 影子价格,一、影子价格的概念,设Y*=（y,1,*，y,2,*，y,m,*）为对偶问题的最优解，则称 y,i,*为原问题第i个约束对应的,影子价格,（Shadow Price）。,z*=w*=Y*b=,b,i,y,i,*,上式表示企业按照最优计划安排生产，最大产值等于各种资源的数量与对应的影子价格乘积的总和。上式对b,i,求偏导，得：,i=1,m,第四节 影子价格 一、影子价格的概念i=1m,12,z*/b,i,=y,i,*,表示第i种资源的影子价格y,i,*是z*对资源b,i,的变化率，即第i种资源变化一个单位时，最大产值的变化量。,二、影子价格的经济意义,1.影子价格是对系统资源的一种最优估价，只有系统达到最优状态时才能赋予该资源这种价值。,2.影子价格是一种动态价格，当系统的状态发生变化时，影子价格也会发生变化。,3.影子价格反映资源在系统内的稀缺程度。决策者可对比该资源的市场价格做出合理决策。,z*/bi=yi*,13,4.影子价格反映系统对资源的利用水平。影子价格越高，说明系统的资源利用水平越高，因此，影子价格可作为考核和比较企业经营水平的重要指标。,4.影子价格反映系统对资源的利用水平。影子价,14,第五节 对偶单纯形法,一、对偶单纯形法的基本思路,原问题最优单纯形表检验数行的相反数对应于对偶问题的最优解，其中对偶决策变量的值与原问题松弛变量的检验数对应，对偶松弛变量的值与原问题决策变量的检验数对应，不仅如此，,原问题每张单纯形表检验数的相反数，都按上述规律对应于对偶问题的一个“基本解”。,利用上述规律，可以从对偶理论的角度来认识单纯形法，同时得出对偶单纯形法的求解思路。,第五节 对偶单纯形法 一、对偶单纯形法的基,15,单纯形法和对偶单纯形法的比较分析,单纯形法,对偶单纯形法,从原问题的一个基可行解出发（b列非负）,对应于对偶问题的一个基本解（检验数行）,换基迭代使对偶基本解负分量逐渐减少,当对偶基本解达到可行（0），原问题与对偶问题同时得到最优解,从对偶问题的一个基可行解出发（检验数行非正）,对应于原问题的一个基本解（b列）,换基迭代使原问题基本解负分量逐渐减少,当原问题基本解达到可行（b 0），对偶问题与原问题同时得到最优解,单纯形法和对偶单纯形法的比较分析单纯形法对偶单纯形法从原问,16,二、对偶单纯形法的步骤,1、建立初始单纯形表，所有检验数,j,0；,2、检查b列元素，如果所有b,i,0，则已得到最优解，结束。否则，转入下一步；,3、确定出基变量：设minb,i,|b,i,0=b,l,，则其对应的基变量为出基变量，l行为主元行；,4、确定入基变量：若l行所有a,lj,0，则问题无可行解，结束。否则，计算=min,j,/a,lj,|a,lj,0=,k,/a,lk,，则x,k,为入基变量，k列为主元列；,5、以a,lk,为主元进行换基迭代，方法与单纯形法相同，得到新的单纯形表，返回步骤2。,二、对偶单纯形法的步骤,17,第六节 灵敏度分析,一、灵敏度分析的意义,在前面的讨论中，线性规划模型的参数A、b、C都是当作已知常数来处理的。但在实践中，它们往往是根据统计数据测算的，不可能完全准确，而且实际情况是在经常变化的，某些参数会随之改变。因此有必要研究参数的变化对最优解的影响，这就是,灵敏度分析（Sensitivity Analysis）,，具体来讲，主要讨论下列两类问题：,1、在最优解（或最优基）不变的前提下，确定参数的变化范围；,第六节 灵敏度分析 一、灵敏度分析的意义,18,2、当参数或系数矩阵发生变化时，确定最优解的变化。,当参数发生变化时，利用新的数据，重新建立模型，从头开始计算，固然可以解决问题，但这样做显然是不经济的，而且也得不到更多有用的信息。灵敏度分析是在原问题最优解（最优单纯形表）上直接进行分析计算，得出需要的答案。因此，灵敏度分析也称为,优化后分析,。,2、当参数或系数矩阵发生变化时，确定最优解的,19,二、灵敏度分析,参数变化会影响原最优解的最优性和可行性，最优性由,j,=c,j,C,B,B P,j,确定，可行性由B b 确定。,1、目标函数系数c,j,的变化分析,目标函数系数的变化会引起检验数,j,的变化，从而影响解的最优性。,非基变量的目标函数系数,若非基变量x,k,的目标函数系数c,k,发生变化，只会影响x,k,的检验数,k,。,基变量的目标函数系数,-1,-1,二、灵敏度分析-1-1,20,基变量的目标函数系数发生变化，会影响所有非基变量的检验数。,2、右端项b,i,的变化分析,b,i,的变化会影响解的可行性。,3、增加一个新变量的分析,4、增加新约束的分析,5、其它变化情况的分析,基变量的目标函数系数发生变化，会影响所有非基,21,