第三章-对偶理论与灵敏度分析

§1单纯形法的矩阵描述设线性规划问题0maxXbAXCXz000maxsssXXbIXAXXCXz设B是一个可行基，令（A，I）=（B，N，I），则：0000maxsNBsNBSNNBBXXXbIXNXBXXXCXCz000max111sNBsNBNNBBXXXbBXBNXBXXCXCz000)(max111111sNBsNBsBNBNBXXXbBXBNXBXXBCXNBCCbBCz1.检验数的矩阵描述：σB=CB-CBB-1B=0σN=CN-CBB-1NσS=-CBB-1θ=min{(B-1b)i/(B-1Pk)i|(B-1Pk)i0}=(B-1b)l/(B-1Pk)lXBbXBXNXsθB-1bIB-1NB-1(B-1b)i(B-1Pk)i-zCBB-1b0CN-CBB-1N-CBB-13.单纯形表的矩阵描述：σ=C-CBB-1A2.θ的矩阵描述：§2改进单纯形法用改进单纯形法求解线性规划问题的计算步骤：1.确定初始可行基B1。求出B1-1；2.计算非基变量的检验数σN。若σN≤0已求的最优解，停止计算,否则进行下一步；3.确定换入变量xk；4.计算B1-1b，B1-1Pk及θ；若θ≤0那么无最优解，停止计算，否则进行下一步；5.确定换出变量xl;6.计算B2-1；7.重复2—7步。1-1-1BBii计算由-11-1BBiiE10/aa0000/a10000/aa0000/aa0121lkmklklkklkkE其中：)(111mlleeee，，，，，，例：用改进单纯形法求解01241648232max54321524132121xxxxxxxxxxxxxxz，，，，100100040004121A12168b)00032(，，，，C01241648232max54321524132121xxxxxxxxxxxxxxz，，，，解：TNTBxxXxxxX)()(2115431，，，)32(400421100010001)000()32(1，，，，N2x换入变量4120162841201628100010001)(211PbB，3/45x换出变量100010001111BB[][]2x换入变量4120162841201628100010001)(211PbB，5x换出变量TNTBxxXxxxX)()(5122432，，，4/1000102/1011000100014/1000102/10111212BEB)4/32(100401/4/1000102/101)300()02(2，，，，N1x换入变量3x换出变量0341612012416184/1000102/101)(112PbB，/42[]1x换入变量3x换入变量0341612012416184/1000102/101)(112PbB，[]TNTBxxXxxxX)()(5332413，，，4/1002142/1014/1000102/10110001400112313BEB)4/12(1000014/1002142/101)302()00(3，，，，N5x换入变量4x换出变量4/13282/12112016084/1002142/101)(513PbB，124/[][]5x换入变量4x换入变量4/13282/12112016084/1002142/101)(513PbB，[])()(4342514xxXxxxXNB，，，08/12/112/1204/104/1002142/10118/1002/1004/1113414BEB)8/12/3(00100108/12/112/1204/10)302()00(4，，，，N2441216808/12/112/1204/1014bB14)40024(**zXTB，，，，§3对偶问题的提出例：ⅠⅡ设备原材料A原材料B1402048台时16kg12kg利润23x101241648232max21212121xxxxxxxxz，1y2y3y32112168yyymin3402321yyy204321yyy0321yyy，，x2x1x2y1y2y3当该问题达到最优时有：01ABCCB01BCBbBCzB1则令YBCB1YbzYYAC00z的上界为无限大，所以只存在最小值。于是得到另一个线性规划问题0minYCYAYb对线性规划问题0maxXbAXCXz对偶问题原问题CYA§4线性规划的对偶理论4.1原问题与对偶问题的关系0maxXbAXCXz0maxXbAXCXz0minYCYAYb无约束YCYAYbmin0maxXbAXCXz0minYCYAYb0##maxXbAXCXz0##minYCYAYb原问题（对偶问题）对偶问题（原问题）#X#Y例：无约束，，，4321432431432143210642253532minxxxxxxxxxxxxxxxxxxz321645maxyyy212yy31yy32123yyy321yyy无约束，，32100yyy23-511y2y3y1x2x3x4x0)()(min212121YYCAAYYbbYY，，，0maxXbAXbAXCXz0)()(min212121YYCAYYbYY，YYY)(21令无约束YCYAYbmin0maxXbAXCXz0maxXbAXCXz0maxXbAXCXz0()-(min111YCAYbY）0)()(min111YCAYbY1YY令0minYCYAYb4.2对偶问题的性质1.对称性对偶问题的对偶是原问题。2.弱对偶性若X*是原问题的可行解，Y*是对偶问题的可行解,则存在CX*≤Y*b证设原问题及对偶问题为maxz=CX，AX≤b，X≥0minω=Yb，YA≥CY≥0∵若X*是原问题的可行解，Y*是对偶问题的可行解∴AX*≤bY*A≥C∴Y*AX*≤Y*bY*AX*≥CX*∴CX*≤Y*AX*≤Y*bCX*Y*b3.无界性若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。4.可行解是最优解的性质设X^是原问题的可行解，Y^是对偶问题的可行解，当CX^=Y^b时，X^，Y^是最优解。5.对偶定理若原问题有最优解，则对偶问题也有最优解，且目标函数相等。6.互补松驰性若X^是原问题的可行解，Y^是对偶问题的可行解，那么Y^Xs=0，YsX^=0，当且仅当X^，Y^为最优解。6.互补松驰性若X^是原问题的可行解，Y^是对偶问题的可行解，那么Y^Xs=0，YsX^=0，但且仅当X^，Y^为最优解。证：设原问题及对偶问题的标准型是maxz=CX，AX+XS=b，X，XS≥0minω=Yb，YA—YS=CY，YS≥0z=(YA—YS)X=YAX—YSXω=Y(AX+XS)=YAX+YXS∵X^是原问题的可行解，Y^是对偶问题的可行解∴z^=Y^AX^—YSX^ω^=Y^AX^+Y^XS当Y^Xs=0，YsX^=0时z^=ω^，则X，Y^是最优解。当X，Y^是最优解时z^=ω^，则Y^Xs=0，YsX^=0例：已知线性规划问题033243232532min54321543215432154321xxxxxxxxxxxxxxxxxxxxz，，，，2134yymax321yy2221yy021yy，其对偶问题的最优解为55/35/4*2*1zyy试用对偶理论求原问题的最优解解：53221yy221yy3321yy2134yymax3421yyy22321yyy021yy，2621yyy532521yyy33721yyy∵5/35/4*2*1yy∴05/35/85/140*7*6*5*4*3yyyyy54321xxxxx21yy∴0*4*3*2xxx0*7*6xx**15**153423xxxx11*5*1xx∴3476xx076xx，，5)1,0,0,0,1(**1zXT7.设原问题及对偶问题的标准型是maxz=CX，AX+XS=b，X，XS≥0minω=Yb，YA－YS=CY，YS≥0则原问题单纯形表的检验数行对应其对偶问题的一个基解，对应关系如下表：XBXNXs0CN－CBB-1N－CBB-1－Ys1－Ys2－Y证:CBB-1A－(0，－CN+CBB-1N)=CBB-1(B，N)－(0，－CN+CBB-1N)=(CB，CN)=C§5对偶问题的经济解释——影子价格设B是线性规划问题的一可行基，这目标函数为YbbBCzB1YBCbzB1所以变量yi的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数值的变化。yi的值代表对第i种资源的估价。这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。Q2(4,2)X2X101234543210121680011zXT，，，，901623022zXT，，，，130803233zXT，，，，144002444zXT，，，，Q1(4,0)Q3(2,3)Q4(0,3)OQ4Q2Q3**03200011，，，，Y9024/30012，，，，Y13004/10213，，，，Y140008/12/314，，，，YA增加4，利润增加4×1/8=1/2设备增加2，利润增加2×3/2=3Q(5,3/2)Q(4,3)§6对偶单纯形法bXBXNXsθXBB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1-Ys1-Ys2-YXBbXBXNXsXBB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1≤0变为≤0变为≥0≥0θ单纯形法对偶单纯形法对偶单纯形法的计算