运筹学 对偶问题.ppt

《运筹学 对偶问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章LP的对偶理论与灵敏度分析线性规划的对偶问题III每天可用能力设备A（h）设备B（h）调试工序（h）06152115245利润（元）21问公司应每天制造两种家电各多少件，使获取的利润最大。例1问题美佳公司愿意以多大的代价出让自己所拥有的生产资源？设y1,y2和y3分别表示出让资源A，B和调试工序的单价，则美佳公司同意出让的条件将是同意出让生产产品I的资源同意出让生产产品II的资源购买者希望用最少的代价获得这些资源，因此这样得到一个新的线性规划问题称这一问题是原来的LP问题的对偶线性规划问题或对偶问题，原来的LP问题也称为原问题。LP问题的对称形

2、式变量：所有变量均具有非负约束约束条件：最大化问题所有约束条件都是“≤”型的最小化问题所有约束条件都是“≥”型的对称形式下的对偶关系项目原问题对偶问题AbC目标函数约束条件决策变量约束条件系数矩阵约束条件右端项向量目标函数系数向量maxz=CXAX≤bX≥0约束条件系数矩阵转置目标函数的系数向量约束条件的右端项向量minw=Yb’A’Y≥C’Y≥0原问题maxz对偶问题minwn个决策变量m个约束条件n个约束条件m个决策变量约束条件“≤”型决策变量≥0决策变量≥0约束条件“≥”型对称形式的对应关系对偶问题的对偶是原问题，即对偶关系是相互对称的关系非对

3、称形式下的对偶关系原问题（对偶问题）maxz对偶问题（原问题）minwn个决策变量m个约束条件n个约束条件m个决策变量约束条件“≤”型约束条件“≥”型约束条件“=”型决策变量≥0决策变量≤0决策变量无约束决策变量≥0决策变量≤0决策变量无约束约束条件“≥”型约束条件“≤”型约束条件“=”型单纯形法的矩阵表示添加松弛变量XS将XB的系数矩阵化为单位矩阵CBCN0XBXNXS0XSbBNICBCN0CBCN0XBXNXSCBXBB-1bIB-1NB-10CN–CBB-1N–CBB-1初始单纯形表迭代后的单纯形表在初始单纯形表中单位矩阵经过迭代后变为基矩阵

4、B的逆在初始单纯形表给出的解中基变量Xs=b,而在迭代后的表给出的解中基变量XB=B-1b系数矩阵的变化:[A,I]B-1[A,I]在初始单纯形表中变量xj的系数为Pj经过迭代后变为Pj′,并且Pj′=B-1Pj若迭代后的单纯形表为最终表则该表也同时给出对偶问题的最优解项目原问题变量原问题松弛变量x1x2x3x4x5x315/20015/415/2x17/21001/4-1/2x23/2010-1/43/2-σj0001/41/2对偶问题剩余变量对偶问题变量y4y5y1y2y3项目对偶问题变量对偶问题剩余变量y1y2y3y4y5y21/4-5/41

5、0-1/41/4y31/215/2011/2-3/2σj15/2007/23/2原问题松弛变量原问题变量x3x4x5x1x2原问题最终单纯形表对偶问题最终单纯形表例1最大化问题检验数的相反数给出了对偶问题的解原本在对偶关系中，原问题的变量对应着对偶问题的约束条件，原问题的约束条件对应着对偶变量。但在分别添加了松弛变量和剩余变量后，也可以建立原问题变量与对偶问题变量之间的对应关系原问题对偶问题第i个约束条件中添加的松弛变量第i个对偶变量第j个变量第j个约束条件中添加的松弛变量注上表中我们将松弛变量与剩余变量统称为松弛变量对偶问题的基本性质弱对偶性原问题

6、可行解的目标函数不超过对偶问题可行解的目标函数弱对偶性的推论（1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是原问题目标函数值的上界。（2）如原问题有可行解且目标函数无界（即原问题为无界解），则对偶问题无可行解；反之对偶问题有可行解且目标函数无界，则原问题无可行解。注意该推论的逆命题不成立。（3）若原问题有可行解而对偶问题无可行解，则原问题目标函数无界；反之对偶问题有可行解而原问题无可行解，则原问题目标函数无界。最优性若原问题一个可行解目标函数等于对偶问题的某个可行解的目标函数,则这两个可行解分别是原

7、问题和对偶问题的最优解强对偶性若原问题和对偶问题都有可行解,则它们都有最优解,且最优解的目标函数值相等互补松弛性在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值非零,则其对应的约束条件取等式;反之若一个约束条件为严格的不等式,则其对应的对偶变量为零互补松弛性的另一种表述在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值非零,则该约束条件中松弛变量等于零;反之若一个约束条件中松弛变量非零,则其对应的对偶变量为零。例（p76.7）原问题对偶问题将原问题最优解X*=(2,2,4,0)代入原问题约束条件中得第一个约束条件：2+6=8，为等式

8、第二个约束条件：4+2=6，为等式第三个约束条件：2+4=6，为等式第四个约束条件：2+2+4<9，为不等式