资源描述：
《运筹学基础对偶线性规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、线性规划的对偶理论包括以下几个基本定理。定理1（对称性定理）§2.2线性规划的对偶理论定理2（弱对偶定理）即对偶问题的对偶是原问题。设x和y分别是原问题和对偶问题的可行解，则必有cx≤yb，即原问题的目标值小于对偶问题的目标值定理3（无界性）若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。若原（对偶）问题有可行解,对偶（原）问题无可行解，则原（对偶）问题一定无界；注:此定理可以判定解的情况定理4（可行解是最优解的性质）定理5（强对偶定理）设X*是原问题的可行解，Y*是对偶问题的可行解，当CX*=Y*b时，X*与Y*是最优解
2、。若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等综合上述结论得原问题与对偶问题的解的关系一般是：cx≤yb对偶问题有最优解无界无可行解原有最优解一定不可能不可能问无界不可能不可能一定题无可行解不可能可能可能原问题与对偶问题解的对应关系由原问题与对偶问题的解的关系可以判定线性规划的解。例4已知线性规划问题Maxz=x1+x2S.t.–x1+x2+x3≤2–2x1+x2–x3≤1xi≥0(i=1,2,3)Minw=2y1+y2S.t.–y1–2y2≥1①y1+y2≥1 ②y1–y2≥0 ③y1,y2≥0应用如上关系求解线性规划问
3、题试用对偶理论证明上述规划问题无最优解。由第一约束条件可知对偶问题无可行解，则原问题的解无界或无可行解，由于原问题存在可行解，所以解无界。表2：原问题与对偶问题解的对应关系对偶问题有最优解无界无可行解原有最优解一定不可能不可能问无界不可能不可能一定题无可行解不可能可能可能[解]该问题存在可行解，如X=(0，0，0)；其对偶问题为：对偶问题无可行解定理6（互补松弛定理）在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。注：证明过程参见教材59
4、页性质5证明讨论:互补松弛定理也称松紧定理，它描述了线性规划达到最优时，原问题（或对偶问题）的变量取值和对偶问题（或原问题）约束松紧之间的对应关系。当线性规划问题达到最优时，我们不仅同时得到了原问题和对偶问题的最优解，而且也还得到了变量和约束之间的一种对应关系。互补松弛定理即揭示了这一点。1.如果原问题的某一约束为紧约束（严格等式:松弛变量为零），该约束对应的对偶变量应大于或等于零；2.如果原问题的某一约束为松约束（严格不等式:松弛变量大于零），则对应的对偶变量必为零；3.如果原问题的某一变量大于零该变量对应的对偶约束必为紧约束(严格等
5、式)；4.如果原问题的某一变量等于零，该变量对应的对偶约束可能是紧约束(严格等式)，也可能是松约束(严格不等式)。线性规划达到最优时的关系例5已知线性规划问题MinS=2x1+3x2+5x3+2x4+3x5S.t.x1+x2+2x3+x4+3x5≥42x1–x2+3x3+x4+x5≥3xi≥0(i=1,2,3,4,5)2＝21/5＜317/5＜57/5＜23=3解：写出对偶问题为：MaxZ=4y1+3yS.t.y1+2y2≤2①y1–y2≤3 ②2y1+3y2≤5③y1+y2≤2 ④3y1+y2≤3 ⑤y1,y2≥0又例:应用如上关系求
6、解线性规划问题已知对偶问题的最优解为y1=4/5,y2=3/5,试应用对偶理论求解原问题。x2=0x3=0x4=0等号又因y1,y2＞0，故原问题的两个约束必为紧约束，即x1+3x5=42x1+x5=3解得：x1=x5=1。maxZ=5=minS=5得原问题的最优解X*=(1,0,0,0,1)minS=5Max.Z=2x1+4x2+x3+x4s.t.x1+3x2+x4≤82x1+x2≤6x2+x3+x4≤6x1+x2+x3≤9xj≥0（j=1,2,3,4）附练习答案：y1=4/5,y2=3/5,y3=1,y4=0已知原问题的最优解为:X
7、*=(2,2,4,0)T，试根据互补松弛定理解出其对偶问题的最优解。线性规划问题的对偶问题为：Min.Z=8y1+6y2+6y3+9y4s.t.y1+2y2+y4≥23y1+y2+y3+y4≥4y3+y4≥1y1+y3≥1yj≥0（j=1,2,3,4）练习：已知线性规划问题为：④为严格不等式，由互补松弛定知，必有y4=0；Max.Z=2x1+4x2+x3+x4s.t.x1+3x2+x4≤82x1+x2≤6x2+x3+x4≤6x1+x2+x3≤9xj≥0（j=1,2,3,4）①8=8②6=6③6=6④8<9解之，有：y1=4/5,y2=3
8、/5,y3=1，y4=0答案：因为原问题的最优解为:X*=(2,2,4,0)T：又因x1,x2,x3＞0，故对偶问题的前三个约束必为紧约束线性规划问题的对偶问题为：Min.Z=8y1+6y2+6y3+9y4
