运筹学基础对偶线性规划.pptx

该【运筹学基础对偶线性规划 】是由【wxq362】上传分享，文档一共【13】页，该文档可以免费在线阅读，需要了解更多关于【运筹学基础对偶线性规划 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。§
参数aij、bi、cj在什么范围内变化时最优解不变是实际问题中常常要研究的问题,当这些参数超出这个范围时,最优解会发生怎样的变化,即为参数线性规划要研究的问题。
【例】线性规划问题
maxZ(l)=2x1+x2
5x2≤15
6x1+2x2≤24
x1+x2≤5+l
x1,x2≥0
第三个约束右端不断增大,分析最优解会发生怎样的变化?
此时l≥0
第一页,共十三页。
参数线性规划求解步骤
1、令l=0求解得最终单纯形表
2、将参数的变化反映到最终单纯形表中;因
第二页,共十三页。
反映到最终单纯形表中
Cj
比
值
CB
XB
b
检验数j
x1
x2
x3
x4
x5
2
1
0
0
0
15/2-(15/2)l
0
0
1
5/4
-15/2
7/2-(1/2)l
1
0
0
1/4
-1/2
3/2+(3/2)l
0
1
0
-1/4
3/2
x3
x1
x2
0
2
1
-17/2-(1/2)l
0
0
0
-1/4
-1/2
3、让l逐步增大,观察原问题与对偶问题解的变化,看哪一个首先出现非可行解。
15/2-(15/2)l≥0
x1=7/2-(1/2)l
x2=3/2+(3/2)l
Z*=17/2+(1/2)l
7/2-(1/2)l≥0
3/2+(3/2)l≥0
当0≤l≤1表中解为最优解。此时
第三页,共十三页。
Cj
比
值
CB
XB
b
检验数j
x1
x2
x3
x4
x5
2
1
0
0
0
15/2-(15/2)l
0
0
1
5/4
-15/2
7/2-(1/2)l
1
0
0
1/4
-1/2
3/2+(3/2)l
0
1
0
-1/4
3/2
x3
x1
x2
0
2
1
-17/2-(1/2)l
0
0
0
-1/4
-1/2
当l>1时,用对偶单纯形法迭代
注:不用讨论7/2-(1/2)l≤0的情况,因为此时,15/2-(15/2)l也是负的,且绝对值更大。因此出基项仍然是x3(第一行)。
第四页,共十三页。
Cj
比
值
CB
XB
b
检验数j
x1
x2
x3
x4
x5
2
1
0
0
0
-1+l
0
0
-2/15
-1/6
1
3
1
0
-1/15
1/6
0
3
0
1
1/5
0
0
x5
x1
x2
0
2
1
-9
0
0
-1/15
-1/3
0
当l继续增大,原问题与对偶问题都保持可行解,故计算至此结束。
结论:0<l≤1时x1=7/2-(1/2)l,x2=3/2+(3/2)l,maxZ=17/2+(1/2)l
l>1,x1=3,x2=3,maxZ=9
第五页,共十三页。
【图示】目标函数Z(l)与l的变化关系图
l
Z(l)
1
2
l

15

9
l≤1,Z=17/2+(1/2)l
l>1,Z=9
注:问题中多个参数变化时,应使目标函数z(l)是l的线性函数。
第六页,共十三页。
【例】求解下述参数线性规划问题
maxZ=(2+l)x1+(1+2l)x2
5x2≤15
6x1+2x2≤24
x1+x2≤5
x1,x2≥0
【解】按参数线性规划求解问题的第一、二步,令l=0求得最优解,并将cj的变化值反映到最终单纯形表中。
第七页,共十三页。
反映到最终单纯形表中
Cj
比
值
CB
XB
b
检验数j
x1
x2
x3
x4
x5
2+l
1+2l
0
0
0
15/2
0
0
1
5/4
-15/2
7/2
1
0
0
1/4
-1/2
3/2
0
1
0
-1/4
3/2
x3
x1
x2
0
2+l
1+2l
-17/2
l
2l
0
-1/4
-1/2
当-1/5≤l≤1时,表中解为最优解。此时
当l>1,变量x4的检验数为正值,用单纯形法继续迭代得
z*=7/2(2+l)+3/2(1+2l)=17/2+13l/2
-17/2-13l/2
0
0
0
-1/4+l/4
-1/2-5l/2
-1/4+l/4≤0
-1/2-5l/2≤0
-1/5≤l≤1
当l<-1/5,变量x5的检验数为正值,用单纯形法继续迭代得
第八页,共十三页。
Cj
比
值
CB
XB
b
检验数j
x1
x2
x3
x4
x5
2+l
1+2l
0
0
0
6
0
0
4/5
1
-6
2
1
0
-1/5
0
1
3
0
1
1/5
0
0
x4
x1
x2
0
2+l
1+2l
-7-8l
0
0
1/5-1/5l
0
-2-l
当l>1,原问题与对偶问题都保持可行解,故计算至此结束。
工厂的最优计划为x1=2,x2=3,z*=2(2+l)+3(1+2l)=7+8l
当l≥1,变量x4的检验数为正值,用单纯形法继续迭代得
第九页,共十三页。
当l<-1/5
Cj
比
值
CB
XB
b
检验数j
x1
x2
x3
x4
x5
2+l
1+2l
0
0
0
15/2
0
0
1
5/4
-15/2
7/2
1
0
0
1/4
-1/2
3/2
0
1
0
-1/4
3/2
x3
x1
x2
0
2+l
1+2l
-17/2
l
2l
0
-1/4
-1/2
当l<-1/5时,变量x5的检验数为正值,用单纯形法继续迭代得
-17/2-13l/2
0
0
0
-1/4+l/4
-1/2-5l/2
第十页,共十三页。