资源描述：
《清华大学《运筹学》第二章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章对偶理论与灵敏度分析§1单纯形法的矩阵描述设maxz=CXAX=bX≥0A为m×n阶矩阵RankA=m,取B为可行基,N为非基，123求解步骤：432利润12kg40材料B16kg04材料A8台时21设备台时限制ⅡⅠ§2对偶问题的提出[eg.1]制定生产计划M1:maxz=2x1+3x21x1+2x2≤84x1≤164x2≤12x1，x2≥05现在出租，设y1为设备单位台时的租金y2,y3为材料A、B转让附加费(kg-1)则M2为M1的对偶问题，反之亦然。M2:minw=8y1+16y2+12y3y1+4y
2、2≥22y1+4y3≥3y1,y2,y3≥032利润12kg40材料B16kg04材料A8台时21设备台时限制ⅡⅠ6一般的，原问题：maxz=CXAX≤bX≥0对偶问题：minw=YbYA≥CY≥0比较：maxzminw决策变量为n个约束条件为n个约束条件为m个决策变量为m个“≤”“≥”7§3对偶问题的化法1、典型情况[eg.2]maxz=x1+2x2+x32x1+x2≤62x2+x3≤8x1,x2,x3≥0对偶：minw=6y1+8y22y1≥1y1+2y2≥2y2≥1y1,y2≥082、含等式的情况[eg.3
3、]maxz=x1+2x2+4x32x1+x2+3x3=3x1+2x2+5x3≤4x1,x2,x3≥0对偶：minw=3y1’-3y1”+4y22y1’-2y1”+y2≥1y1’-y1”+2y2≥23y1’-3y1”+5y2≥4y1’,y1”,y2≥0令y1=y1’-y1”,则：minw=3y1+4y22y1+y2≥1y1+2y2≥23y1+5y2≥4y2≥0，y1无约束一般，原问题第i个约束取等式，对偶问题第i个变量无约束。2x1+x2+3x3≤3-2x1-x2-3x3≤-393、含“≥”的max问题[eg.4]
4、maxz=x1+2x2+4x32x1+x2+3x3≥3x1+2x2+5x3≤4x1,x2,x3≥0对偶：minw=-3y1’+4y2-2y1’+y2≥1-y1’+2y2≥2-3y1’+5y2≥4y1’,y2≥0令y1=-y1’，则：minw=3y1+4y22y1+y2≥1y1+2y2≥23y1+5y2≥4y1≤0,y2≥0-2x1-x2-3x3≤-310一般:①max问题第i个约束取“≥”，则min问题第i个变量≤0；②min问题第i个约束取“≤”，则max问题第i个变量≤0；③原问题第i个约束取等式，对偶问题第
5、i个变量无约束；④max问题第j个变量≤0,则min问题第j个约束取“≤”；⑤min问题第j个变量≤0，则max问题第j个约束取“≥”；⑥原问题第j个变量无约束，对偶问题第j个约束取等式。11[eg.5]minz=2x1+3x2-5x3+x4x1+x2-3x3+x4≥52x1+2x3-x4≤4x2+x3+x4=6x1≤0,x2,x3≥0,x4无约束对偶：maxw=5y1+4y2+6y3y1+y2≥2y1+y3≤3-3y1+2y2+y3≤-5y1-y2+y3=1y1≥0,y2≤0,y3无约束12§4对偶问题的性质1
6、、对称性对偶问题的对偶为原问题.131415推论：(1)max问题任一可解的目标值为min问题目标值的一个下界；(2)min问题任一可解的目标值为max问题目标值的一个上界。3、无界性若原问题(对偶问题)为无界解，则对偶问题(原问题)为无可行解。注：该性质的逆不存在。若原(对偶)问题为无可行解，对偶(原问题)问题或为无界解，或为无可行解。164、最优性设X*，Y*分别为原问题和对偶问题可行解，当CX*=Y*b时，X*，Y*分别为最优解。175、对偶定理若原问题有最优解，那么对偶问题也有最优解，且目标值相等。18∴
7、Y*为对偶问题的最优解，且原问题和对偶问题的目标值相等。证毕6、松弛性若X*，Y*分别为原问题及对偶问题的可行解，那么Ys*X*=0，Y*Xs*=0，当且仅当X*，Y*分别为最优解。证明：19将b,C分别代入目标函数：20其中：用分量表示：217、检验数与解的关系(1)原问题非最优检验数的负值为对偶问题的一个基解。(2)原问题最优检验数的负值为对偶问题的最优解。分析：maxz=CX+0Xs=(C0)(XXs)TAX+Xs=bX,Xs≥0minw=Yb+YS0YA-Ys=CY,Ys≥0检验数：σ=(C0)-CBB-
8、1(AI)=(C-CBB-1A-CBB-1)=(σcσs)σc=C-CBB-1AX对应的检验数σs=-CBB-1Xs对应的检验数22[eg.6]已知：minw=20y1+20y2的最优解为y1*=1.2,y2*=0.2-ys1y1+2y2≥1①试用松弛性求对偶-ys22y1+y2≥2②问题的最优解。-ys32y1+3y2≥3③-ys43y1+2y2≥4④y1,y2≥0解：
