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