乔2-对偶理论与灵敏度分析.pdf

运筹学运筹学运筹学运筹学————第第2 2章章 对偶理论与灵敏度分析对偶理论与灵敏度分析2011/5/14同济大学 电子与信息工程学院乔非乔非第第2章 对偶理论与灵敏度分析章 对偶理论与灵敏度分析2.1 单纯形法的矩阵描述单纯形法的矩阵描述2.2 对偶问题的提出对偶问题的提出2.3 线性规划的对偶理论线性规划的对偶理论2.4 对偶单纯形法对偶单纯形法2.5 灵敏度分析灵敏度分析Generated by Foxit PDF Creator © Foxit Software For evaluation only.运筹学运筹学运筹学运筹学————第第2 2章章 对偶理论与灵敏度分析对偶理论与灵敏度分析2011/5/14同济大学 电子与信息工程学院乔非乔非第第2章 对偶理论与灵敏度分析章 对偶理论与灵敏度分析2.1 单纯形法的矩阵描述单纯形法的矩阵描述2.2 对偶问题的提出对偶问题的提出2.3 线性规划的对偶理论线性规划的对偶理论2.4 对偶单纯形法对偶单纯形法2.5 灵敏度分析灵敏度分析Generated by Foxit PDF Creator © Foxit Software For evaluation only.运筹学运筹学运筹学运筹学————第第2 2章章 对偶理论与灵敏度分析对偶理论与灵敏度分析2011/5/14同济大学 电子与信息工程学院乔非乔非第第2章 对偶理论与灵敏度分析章 对偶理论与灵敏度分析2.1 单纯形法的矩阵描述单纯形法的矩阵描述l可能性可能性–单纯形求解方法是以线性方程组的形式为基础进行的单纯形求解方法是以线性方程组的形式为基础进行的–矩阵是产生于线性方程组的常用且重要的数学工具矩阵是产生于线性方程组的常用且重要的数学工具l必要性必要性–便于进一步讨论修正单纯形法便于进一步讨论修正单纯形法–便于理论推导便于理论推导Generated by Foxit PDF Creator © Foxit Software For evaluation only.运筹学运筹学运筹学运筹学————第第2 2章章 对偶理论与灵敏度分析对偶理论与灵敏度分析2011/5/14同济大学 电子与信息工程学院乔非乔非第第2章 对偶理论与灵敏度分析章 对偶理论与灵敏度分析2.1 单纯形法的矩阵描述单纯形法的矩阵描述£=bAXCXZMax一般一般LP的 矩阵表达的 矩阵表达一般一般LP的 矩阵表达的 矩阵表达) 0('CCM=)('SXXXM=)('IAAM=îíì ³=++=0,..0SSSXXbIXAXtsXCXZMax加入松驰 变量加入松驰 变量XSLP标准型矩阵表达标准型矩阵表达LP标准型矩阵表达标准型矩阵表达XB:基变量基变量 XN:非基变量非基变量B:基矩阵基矩阵N:非基变量系数矩阵非基变量系数矩阵Generated by Foxit PDF Creator © Foxit Software For evaluation only.运筹学运筹学运筹学运筹学————第第2 2章章 对偶理论与灵敏度分析对偶理论与灵敏度分析2011/5/14同济大学 电子与信息工程学院乔非乔非第第2章 对偶理论与灵敏度分析章 对偶理论与灵敏度分析2.1 单纯形法的矩阵描述单纯形法的矩阵描述l单纯形法矩阵描述的单纯形法矩阵描述的关键关键关键关键————两个基本的表达式两个基本的表达式两个基本的表达式两个基本的表达式îíì ³=++=0,. .0SSSXXbIXAXt sXCXZMax标准型矩阵表达标准型矩阵表达标准型矩阵表达标准型矩阵表达îíì ³=++=0,. .NBNBNNBBXXbNXBXt sXCXCZMax提取基变量的表达提取基变量的表达提取基变量的表达原有变量取作基变量的变量提取基变量的表达原有变量取作基变量的变量XB1 松驰变量作为基变量的变量松驰变量作为基变量的变量XS1原有变量作为非基变量的变量原有变量作为非基变量的变量XN1 松驰变量作为非基变量的变量松驰变量作为非基变量的变量XS2基变量基变量XB非基变量非基变量XN变量变量松驰变量松驰变量原有变量原有变量îíì ³=++++=0,. .22112211NBSNBSSNNBBXXbXSXNBXt sXCXCXCZMax提取基变量的展开表达提取基变量的展开表达提取基变量的展开表达提取基变量的展开表达Generated by Foxit PDF Creator © Foxit Software For evaluation only.运筹学运筹学运筹学运筹学————第第2 2章章 对偶理论与灵敏度分析对偶理论与灵敏度分析2011/5/14第第2章 对偶理论与灵敏度分析章 对偶理论与灵敏度分析2.1 单纯形法的矩阵描述单纯形法的矩阵描述l举例举例ïïïîïïïíì³³+-£££++=0,2212416482. .322121212121xxxxxxxxtsxxMaxZïïïîïïïíì³=-+-=+=+=+++=0,,,,2212416482. .326, 54321621524132121xxxxxxxxxxxxxxxxtsxxMaxZïïïîïïïíì³=+--=++=+=+++=0,,,,22448164425. .326, 543212615614136121xxxxxxxxxxxxxxxxxtsxxMaxZT NT BT sTXXxxxxXxxX))),,,(),(654321 ====Generated by Foxit PDF Creator © Foxit Software For evaluation only.运筹学运筹学运筹学运筹学————第第2 2章章 对偶理论与灵敏度分析对偶理论与灵敏度分析2011/5/14同济大学 电子与信息工程学院乔非乔非第第2章 对偶理论与灵敏度分析章 对偶理论与灵敏度分析2.1 单纯形法的矩阵描述单纯形法的矩阵描述l单纯形表与矩阵表达的关系单纯形表与矩阵表达的关系2121SNBNB NBSNBXXXXX úûù êëé= úúúûùêêêëéúúúûùêêêëé =úûù êëéîíì ³=++++=0,. .22112211NBSNBSSNNBBXXbXSXNBXt sXCXCXCZMax目标函数系数向量目标函数系数向量基变量原问题 非基变量松驰变量 非基变量等式右边系数矩阵检验数０基变量原问题 非基变量松驰变量 非基变量等式右边系数矩阵检验数０11 1NBCCBN--1--BCB11=-BB11NB-1-B bBCB1--bB1-2SX1NX BXGenerated by Foxit PDF Creator © Foxit Software For evaluation only.l单纯形表与矩阵表达的关系（证明）单纯形表与矩阵表达的关系（证明）2121SNBNB NBSNBXXXXX úûù êëé= úúúûùêêêëéúúúûùêêêëé =úûù êëéîíì ³=++++=0,. .22112211NBSNBSSNNBBXXbXSXNBXt sXCXCXCZMax目标函数系数向量目标函数系数向量基变量原问题 非基变量松驰变量 非基变量等式右边系数矩阵检验数０基变量原问题 非基变量松驰变量 非基变量等式右边系数矩阵检验数０11 1NBCCBN--1--BCB11=-BB11NB-1-B bBCB1--bB1-2SX1NX BX原有变量取作基变量的变量原有变量取作基变量的变量XB1 松驰变量作为基变量的变量松驰变量作为基变量的变量XS1原有变量作为非基变量的变量原有变量作为非基变量的变量XN1 松驰变量作为非基变量的变量松驰变量作为非基变量的变量XS2基变量基变量XB非基变量非基变量XN变量变量 松驰 变量松驰 变量原有 变量原有 变量 ISCS==220Generated by Foxit PDF Creator © Foxit Software For evaluation only.bBCB1--1--BCB11 1NBCCBN--bB1- 11NB-1-B11=-BBl单纯形表与矩阵表达的关系（证明）单纯形表与矩阵表达的关系（证明）îíì ³=++++=0,) 2(. .) 1 (22112211NBSNBSSNNBBXXbXSXNBXt sXCXCXCZMax) 3 (1 221 1111bBXSBXNBBXBSNB----=++(2)式左乘式左乘B-1)4(21 1111 SNBXBXNBbBX-----=化简化简(3)式并移项式并移项21 2111 11)()(SBSNBNBXBCCXNBCCbBCZ----+-+=将将(4)式代入式代入(1)ISCS==220基变量原问题 非基变量松驰变量 非基变量等式右边系数矩阵检验数０基变量原问题 非基变量松驰变量 非基变量等式右边系数矩阵检验数０2SX1NX BX) 5 ()(21 111 11 SBNBNBXBCXNBCCbBC-----+=02=SCQbBCZXBCXNBCCBSBNBN1 21 111 1)(----=--化简化简(5)式并移项式并移项Generated by Foxit PDF Creator © Foxit Software For evaluation only.运筹学运筹学运筹学运筹学————第第2 2章章 对偶理论与灵敏度分析对偶理论与灵敏度分析2011/5/14同济大学 电子与信息工程学院乔非乔非NCCBBNB®¬-1NBCCBNN1--=s基变量原问题 非基变量等式右边系数矩阵检验数０基变量原问题 非基变量等式右边系数矩阵检验数０11 1NBCCBN--11=-BB11NB- bBCB1--bB1-1NX BXþýüîíì>=- -- 0)()(min1 11k ikiPBPBbBq迭代迭代——矩阵求逆矩阵求逆确定换入量（入基）确定换出量（出基）确定换入量（入基）确定换出量（出基）第第2章 对偶理论与灵敏度分析改进单纯形法章 对偶理论与灵敏度分析改进单纯形法Generated by Foxit PDF Creator © Foxit Software For evaluation only.运筹学运筹学运筹学运筹学————第第2 2章章 对偶理论与灵敏度分析对偶理论与灵敏度分析2011/5/14同济大学 电子与信息工程学院乔非乔非第第2章 对偶理论与灵敏度分析章 对偶理论与灵敏度分析2.1 单纯形法的矩阵描述单纯形法的矩阵描述2.2 对偶问题的提出对偶问题的提出2.3 线性规划的对偶理论线性规划的对偶理论2.4 对偶单纯形法对偶单纯形法2.5 灵敏度分析灵敏度分析Generated by Foxit PDF Creator © Foxit Software For evaluation only.运筹学运筹学运筹学运筹学————第第2 2章章 对偶理论与灵敏度分析对偶理论与灵敏度分析2011/5/14同济大学 电子与信息工程学院乔非乔非第第2章 对偶理论与灵敏度分析章 对偶理论与灵敏度分析2.2 对偶问题的提出对偶问题的提出l对偶思想举例对偶思想举例–周长一定的矩形中，以正方形面积最大；面积一定 的矩形中，以正方形周长最小周长一定的矩。