运筹学基础-对偶线性规划(2).ppt

定理4 (可行解是最优解的性质)
定理5 (强对偶定理)
设X*是原问题的可行解,Y*是对偶问题的可行解,当CX*=Y*b时, X*与Y*是最优解。
若原问题有最优解,那么对偶问题也有最优解,且目标函数值相等
综合上述结论得原问题与对偶问题的解的关系
一般是:cx≤yb
对偶问题
有最优解无界无可行解
原有最优解一定不可能不可能
问无界不可能不可能一定
题无可行解不可能可能可能
原问题与对偶问题解的对应关系
由原问题与对偶问题的解的关系可以判定线性规划的解。
例4 已知线性规划问题
Max z=x1 + x2
. –x1 + x2 + x3 ≤ 2
– 2x1 + x2 – x3 ≤ 1
xi ≥ 0 (i=1,2 ,3)
Min w = 2y1 +y2
. – y1 – 2y2 ≥ 1 ①
y1 + y2 ≥ 1 ②
y1 –y2 ≥ 0 ③
y1,y2 ≥ 0
应用如上关系求解线性规划问题
试用对偶理论证明上述规划问题无最优解。
由第一约束条件可知对偶问题无可行解,则原问题的解无界或无可行解, 由于原问题存在可行解,所以解无界。
表2: 原问题与对偶问题解的对应关系
对偶问题
有最优解无界无可行解
原有最优解一定不可能不可能
问无界不可能不可能一定
题无可行解不可能可能可能
[解] 该问题存在可行解,如X=(0,0,0);
其对偶问题为:
对偶问题无可行解
定理6(互补松弛定理)
在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值为非零,则该约束条件取严格等式;反之如果约束条件取严格不等式,则其对应的对偶变量一定为零。
注:证明过程参见教材59页性质5证明
讨论:
互补松弛定理也称松紧定理,它描述了线性规划达到最优时,原问题(或对偶问题)的变量取值和对偶问题(或原问题)约束松紧之间的对应关系。
当线性规划问题达到最优时,我们不仅同时得到了原问题和对偶问题的最优解,而且也还得到了变量和约束之间的一种对应关系。互补松弛定理即揭示了这一点。
(严格等式:松弛变量为零),该约束对应的对偶变量应大于或等于零;
(严格不等式:松弛变量大于零),则对应的对偶变量必为零;
(严格等式);
,该变量对应的对偶约束可能是紧约束(严格等式),也可能是松约束(严格不等式)。
线性规划达到最优时的关系
例5 已知线性规划问题
Min S=2x1 + 3x2 + 5x3 + 2x4 + 3x5
. x1 + x2 + 2x3 + x4 + 3x5 ≥ 4
2x1 – x2 + 3x3 + x4 + x5 ≥ 3
xi ≥ 0 (i=1,2 ,3,4,5)
2=2
1/5 < 3
17/5<5
7/5 < 2
3=3
解:写出对偶问题为:
Max Z = 4y1 + 3y
. y1 + 2y2 ≤2 ①
y1 – y2 ≤3 ②
2y1 +3y2 ≤5 ③
y1 + y2 ≤2 ④
3y1 +y2 ≤3 ⑤
y1,y2 ≥ 0
又例:应用如上关系求解线性规划问题
已知对偶问题的最优解为 y1 = 4/5, y2 = 3/5, 试应用对偶理论求解原问题。
x2 = 0
x3 = 0
x4 = 0
等号
又因y1,y2 >0,故原问题的两个约束必为紧约束,即
x1+3 x5= 4
2x1+ x5 = 3
解得:x1 = x5 = 1。
maxZ=5=minS=5
得原问题的最优解X*=(1,0,0,0,1) minS=5
=2x1+4x2+x3+x4
. x1+3x2 +x4≤8
2x1+x2 ≤6
x2 + x3 +x4≤6
x1 + x2 +x3 ≤9
xj≥0(j=1,2,3,4)
附练****答案:y1=4/5, y2=3/5, y3=1, y4=0
已知原问题的最优解为:X*=(2,2,4,0)T,试根据互补松弛定理解出其对偶问题的最优解。
线性规划问题的对偶问题为:
=8y1+6y2+6y3+9y4
. y1+2y2 +y4 ≥ 2
3y1+y2 + y3 +y4 ≥ 4
y3 +y4 ≥ 1
y1 +y3 ≥ 1
yj≥0(j=1,2,3,4)
练****已知线性规划问题为:
④为严格不等式,由互补松弛定知,必有y4 = 0;
=2x1+4x2+x3+x4
. x1+3x2 +x4≤8
2x1+x2 ≤6
x2 + x3 +x4≤6
x1 +