对偶理论与灵敏度分析讲稿.pptx
《对偶理论与灵敏度分析讲稿.pptx》由会员分享,可在线阅读,更多相关《对偶理论与灵敏度分析讲稿.pptx(94页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、对偶理论与灵敏度分析第一页,讲稿共九十四页哦第三章 对偶理论与灵敏度分析第二页,讲稿共九十四页哦第一节 对偶问题的提出例:常山机械厂生产例:常山机械厂生产和和两种产品。生产中需使用两种产品。生产中需使用A、B、C三种设备进行加工,加工每件三种设备进行加工,加工每件产品或产品或产品所需的设备产品所需的设备机时数、利润值及每种设备可利用机时数列于下表,请问:充分利用设备机台时,工厂应生产机时数、利润值及每种设备可利用机时数列于下表,请问:充分利用设备机台时,工厂应生产和和产品各多少件产品各多少件才能获得最大利润?试列出相应的线性规划数学模型。才能获得最大利润?试列出相应的线性规划数学模型。ABC产
2、品利润(元件)产品利润(元件)24022053设备可用机时数(工时)设备可用机时数(工时)121615第三页,讲稿共九十四页哦第一节 对偶问题的提出解:设解:设、产品的生产数量分别为产品的生产数量分别为x1和和x2,建立问题数学模型如下:,建立问题数学模型如下:max z=2x1+3x2 2x1+2x212 4x1 16 5x2 15 xj0,j=1,2现假设有另一家四海机器厂,为了扩大生产想租借常山机器厂拥有的设备资源,问常山厂分别以每小时什么样的价格才愿意现假设有另一家四海机器厂,为了扩大生产想租借常山机器厂拥有的设备资源,问常山厂分别以每小时什么样的价格才愿意出租自己的设备呢?出租自己的
3、设备呢?第四页,讲稿共九十四页哦第一节 对偶问题的提出设设A、B、C设备的机时单价分别为设备的机时单价分别为y1、y2、y3,新的线性规划数学模型为,新的线性规划数学模型为min w=12y1+16y2+15y32y1+4y2 22y1 +5y33yj0,j=1,2,3A(y1)B(y2)C(y3)产品利润(元件)产品利润(元件)(x1)2402(x2)2053设备可用机时数(工时)设备可用机时数(工时)121615max z=2x1+3x2 2x1+2x212 4x1 16 5x2 15 xj0,j=1,2第五页,讲稿共九十四页哦第一节 对偶问题的提出23x1 x2 原问题原问题12y1 2
4、21216y2 401615y30515对偶问题对偶问题23第六页,讲稿共九十四页哦第一节 对偶问题的提出X1 ,X2 ,Xnxjyi对偶问题对偶问题 原问题原问题 Min wMax ZMax Z=Min w原问题与对偶问题的形式关系原问题与对偶问题的形式关系原问题与对偶问题的形式关系原问题与对偶问题的形式关系第七页,讲稿共九十四页哦第一节 对偶问题的提出原始问题原始问题max z=CXs.t.AXbX 0对偶问题对偶问题min w=bTYs.t.ATYCT Y 0maxbACCTATbTminmnmn第八页,讲稿共九十四页哦第一节 对偶问题的提出原问题与对偶问题原问题与对偶问题原问题与对偶问
5、题原问题与对偶问题 max z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm xj 0(j=1,2,n)min w=b1 y1+b2 y2+bm yms.t.a11y1+a21 y2+am1ym c1 a12y1+a22y2 +am2 ym c2 a1ny1+a2ny2+amnym cn yi 0(i=1,2,m)设原设原 LP 问题为问题为则称下列则称下列 LP 问题问题第九页,讲稿共九十四页哦第一节 对偶问题的提出例:写出下列线性规划问题的对偶问题例:写出下列线性规划问题的对
6、偶问题min w=12x1+8x2+16x3+12x4 s.t.2x1+x2+4x3 2 2x1+2x2 +4x4 3 x1,x2,x3,x4 0解:该问题的对偶问题:解:该问题的对偶问题:max z=2y1+3y2 s.t.2y1+2y2 12 y1+2y2 8 4 y1 16 4y2 12 y1,y2 0y1y2第十页,讲稿共九十四页哦第一节 对偶问题的提出例:写出下列线性规划问题的对偶问题例:写出下列线性规划问题的对偶问题 max z=10 x1+x2 +2x3 s.t.x1+x2+2x3 10 y1 4x1+2x2 -x3 20 y2 x1,x2,x3 0解:该问题的对偶问题:解:该问
7、题的对偶问题:min w=10 y1+20 y2 s.t.y1+4y2 10 y1+2y2 1 2 y1-y2 2 y1,y2 0第十一页,讲稿共九十四页哦例:写出下列线性规划问题的对偶问题例:写出下列线性规划问题的对偶问题 min w=x1+2x2+3x3s.t.2x1+3x2+5x3 2 3x1+x2+7x3 3 x1,x2,x3 0解:用(解:用(-1)乘以第二个约束方程两边)乘以第二个约束方程两边 min w=x1+2x2+3x3s.t.2x1+3x2+5x3 2 y1 -3x1-x2-7x3 -3 y2 x1,x2,x3 0该问题的对偶问题:该问题的对偶问题:max z=2 y1-3
8、y2 s.t.2y1-3y2 1 3y1-y2 2 5y1-7y2 3 y1,y2 0第一节 对偶问题的提出第十二页,讲稿共九十四页哦第一节 对偶问题的提出解:化为对称形式。解:化为对称形式。max x10,x20,x3 无约束无约束s.t.a11x1+a12x2+a13x3 b1z=c1x1+c2x2+c3x3 a31x1+a32x2+a33x3 b3 a21x1+a22x2+a23x3=b2令令maxs.t.例:写出下述线性规划问题的对偶问题例:写出下述线性规划问题的对偶问题第十三页,讲稿共九十四页哦第一节 对偶问题的提出maxs.t.对偶变量对偶变量mins.t.对偶问题:对偶问题:第十
9、四页,讲稿共九十四页哦第一节 对偶问题的提出maxs.t.对偶变量对偶变量mins.t.对偶问题:对偶问题:第十五页,讲稿共九十四页哦第一节 对偶问题的提出原问题(对偶问题)原问题(对偶问题)对偶问题(原问题)对偶问题(原问题)A约束系数矩阵约束系数矩阵约束系数矩阵的转秩约束系数矩阵的转秩b约束条件右端项向量约束条件右端项向量目标函数中价格系数向量目标函数中价格系数向量c目标函数中价格系数向量目标函数中价格系数向量约束条件右端项向量约束条件右端项向量目标函数目标函数变量变量 xj(j=1,n)约束条件有约束条件有n个个xj 0cjxj 0cjxj 无约束无约束=cj约束条件有约束条件有m个个变
10、量有变量有m个个yi(i=1,m)biyi0biyi0=biyi无约束无约束第十六页,讲稿共九十四页哦第一节 对偶问题的提出例:写出原问题的对偶问题例:写出原问题的对偶问题min z=7x1+4x2-3x3 -4x1+2x2-6x324 -3x1-6x2-4x3 15 5x2+3x3=30 x1 0 x2无符号限制无符号限制 x3 0 max w=24y1+15y2+30y3 y1 0 y20 y3无符号限制无符号限制 -4y1-3y2 72 2y1-6y2+5y3 =4 -6y1 -4y2+3y3 -3 第十七页,讲稿共九十四页哦第一节 对偶问题的提出例:写出例:写出(P)问题的问题的(D)
11、问题问题max z=2x1+3x2-5x3+x4 s.t.4x1+x2-3x3+2x4 5 3x1-2x2 +7x4 4 -2x1+3x2+4x3+x4=6 x1 0,x2,x3 0,x4 无符号限制无符号限制min w=5y1+4y2+6y3 s.t.4y1+3y2-2y3 2 y1-2y2+3y3 3 -3y1 +4y3 -5 2y1+7y2+y3=1 y1 0,y20,y3无符号限制无符号限制第十八页,讲稿共九十四页哦第二节 对偶问题的基本性质min Z=-CXs.t.-AX-bX 01 1、对称性:对偶问题的对偶是原问题。、对称性:对偶问题的对偶是原问题。、对称性:对偶问题的对偶是原问
12、题。、对称性:对偶问题的对偶是原问题。min W=Y bs.t.YA C Y 0max Z=C Xs.t.AXb X 0对偶的定义对偶的定义对偶的定义对偶的定义max W=-Ybs.t.YA C Y 0第十九页,讲稿共九十四页哦2 2、弱对偶性:设、弱对偶性:设、弱对偶性:设、弱对偶性:设 和和和和 分别是问题(分别是问题(分别是问题(分别是问题(P P)和()和()和()和(D D)的可行解,则必有)的可行解,则必有)的可行解,则必有)的可行解,则必有第二节 对偶问题的基本性质第二十页,讲稿共九十四页哦Z ZY YX X在在在在Y=0Y=0的平面上鞍点是的平面上鞍点是的平面上鞍点是的平面上鞍
13、点是z=f(0,y)z=f(0,y)的极大值点的极大值点的极大值点的极大值点第二节 对偶问题的基本性质第二十一页,讲稿共九十四页哦X XY YZ Z在在在在X=0X=0的平面上鞍点是的平面上鞍点是的平面上鞍点是的平面上鞍点是z=f(0,y)z=f(0,y)的极小值点的极小值点的极小值点的极小值点第二节 对偶问题的基本性质第二十二页,讲稿共九十四页哦3 3、无界性:在一对对偶问题(、无界性:在一对对偶问题(、无界性:在一对对偶问题(、无界性:在一对对偶问题(P P)和()和()和()和(D D)中,若其中一个问题可行但目标函数无界,则另一个问题不可)中,若其中一个问题可行但目标函数无界,则另一个
14、问题不可)中,若其中一个问题可行但目标函数无界,则另一个问题不可)中,若其中一个问题可行但目标函数无界,则另一个问题不可行;反之不成立。行;反之不成立。行;反之不成立。行;反之不成立。原问题原问题对偶问题对偶问题问题无界问题无界无可无可行解行解无可无可行解行解问题无界问题无界第二节 对偶问题的基本性质第二十三页,讲稿共九十四页哦4、互互补补松松弛弛性性:设设 和和 分分别别是是原原问问题题和和其其对对偶偶问题的最优解,问题的最优解,若对偶变量若对偶变量 ,则原问题相应的约束条件,则原问题相应的约束条件若约束条件若约束条件 ,则相应的对偶变量,则相应的对偶变量第二节 对偶问题的基本性质第二十四页
15、,讲稿共九十四页哦例:给定线性规划问题例:给定线性规划问题min z=2x1+3x2+x3 3x1-x2+x3 1 x1+2x2 -3x3 2 x1,x2,x3 0已知对偶问题的最优解为已知对偶问题的最优解为y=(y1,y2)T=(1/7,11/7)试用互补松弛性质,求原问题的最优解。)试用互补松弛性质,求原问题的最优解。第二节 对偶问题的基本性质第二十五页,讲稿共九十四页哦解:先写出它的对偶问题解:先写出它的对偶问题max w=y1+2y2 3y1 +y2 2 -y1+2y2 3 y1 -3y2 1 y1,y2 0将最优解将最优解y=(y1,y2)T=(1/7,11/7)代入上面的线性规划中
16、,第三个约束条件严格不等,说明)代入上面的线性规划中,第三个约束条件严格不等,说明x3=0,第一、第一、二个约束条件严格取等,说明,二个约束条件严格取等,说明,x1=4/7,x2=5/7第二节 对偶问题的基本性质第二十六页,讲稿共九十四页哦例例:已知线性规划问题已知线性规划问题 Min.Z=2x1+3x2+5x3+2x4 +3x5 S.t.x1+x2+2x3+x4+3x5 4 2x1 x2+3x3+x4+x5 3 xi 0(i=1,2,3,4,5)已知对偶问题的最优解为已知对偶问题的最优解为 y1=4/5,y2=3/5,试应用对偶理论解原问题。试应用对偶理论解原问题。第二节 对偶问题的基本性质
17、第二十七页,讲稿共九十四页哦221/5 317/557/5 23=3将将y1、y2的值代入,得知的值代入,得知、为严格不等式,于是由互补松弛定理知,必有为严格不等式,于是由互补松弛定理知,必有x2=x3=x4=0;又因;又因y1,y2 0,故原问题的两个约束必为紧约束,于是有:,故原问题的两个约束必为紧约束,于是有:x1+3x5=4 2x1+x5 =3解之,解之,x1=x5=1。Z(1,0,0,0,1)=5 解:写出对偶问题为:解:写出对偶问题为:Max.S=4y1+3y2 S.t.y1+2y2 2 y1 y2 3 2y1+3y2 5 y1+y2 2 3y1+y2 3 y1,y2 0第二节 对
18、偶问题的基本性质第二十八页,讲稿共九十四页哦例例:已知线性规划问题已知线性规划问题试通过求对偶问题的最优解来求解原问题的最优解。试通过求对偶问题的最优解来求解原问题的最优解。第二节 对偶问题的基本性质第二十九页,讲稿共九十四页哦用图解法求出:用图解法求出:Y*=(1.3),),W=11。将。将y*1=1,y*2=3 代入对偶约束条件,(代入对偶约束条件,(1)()(2)()(5)式为紧约束,)式为紧约束,(3)()(4)为松约束。令原问题的最优解为)为松约束。令原问题的最优解为X*=(x1.x2.x3.x4.x5),则根据互补松弛条件,必有),则根据互补松弛条件,必有x3=x4=0(1.3)(
19、1)(2)(3)(4)(5)解:对偶问题为解:对偶问题为第二节 对偶问题的基本性质第三十页,讲稿共九十四页哦 又由于又由于y*10,y*2 0,原问题的约束必为等式,即,原问题的约束必为等式,即化简为化简为此方程组为无穷多解此方程组为无穷多解令令x5=0,得到得到x1=1,x2=2 即即X*1=(1.2.0.0.0)为原问题的一个最优解,)为原问题的一个最优解,Z=11。再令再令 x5=2/3,得到,得到x1=5/3,x2=0 即即X*2(5/3.0.0.0.2/3)也是原问题的一个最优解,)也是原问题的一个最优解,Z=11。第二节 对偶问题的基本性质第三十一页,讲稿共九十四页哦例例:已知线性
20、规划问题及其对偶问题已知线性规划问题及其对偶问题max z=2x1+3x2+0 x3+0 x4+0 x5 2x1+2x2+x3 =12 y1 4x1 +x4 =16 y2 5x2+x5=15 y3 xj0min w=-12y1-16y2-15y3+0y4+0y5 -2y1-4y2 +y4 =-2 x1 -2y1 -5y3 +y5=-3 x2 yi 0分别求解,得到如下两个最优单纯形表。分别求解,得到如下两个最优单纯形表。第二节 对偶问题的基本性质第三十二页,讲稿共九十四页哦 基基 b原问题变量原问题变量原问题松弛变量原问题松弛变量 x1 x2 x3 x4 x5 x1 3 1 0 1/2 0 -
21、1/5 x4 4 0 0 -2 1 4/5 x2 3 0 1 0 0 1/5 0 0 1 0 1/5 变量变量对偶问题的剩余变量对偶问题的剩余变量对偶问题变量对偶问题变量 y4 y5 y1 y2 y3 基基 b对偶问题变量对偶问题变量对偶问题的剩余变量对偶问题的剩余变量 y1 y2 y3 y4 y5 y1 1 1 2 0 -1/2 0 y2 1/5 0 -4/5 1 1/5 -1/5 0 4 0 3 3变量变量原问题松弛变量原问题松弛变量原问题变量原问题变量 x3 x4 x5 x1 x2第二节 对偶问题的基本性质第三十三页,讲稿共九十四页哦w1 wi wm wm+1 wm+j wn+m x1
22、xj xn xn+1 xn+i xn+m 对偶问题的变量对偶问题的变量 对偶问题的松弛变量对偶问题的松弛变量 原始问题的变量原始问题的变量 原始问题的松弛变量原始问题的松弛变量 xjwm+j=0,wixn+i=0(i=1,2,m;j=1,2,n)在一对变量中,其中一个大于在一对变量中,其中一个大于0,另一个一定等于,另一个一定等于0第二节 对偶问题的基本性质第三十四页,讲稿共九十四页哦第三节 对偶单纯形法 我们前面介绍的一般单纯形法,是从我们前面介绍的一般单纯形法,是从“可行可行”(右端项非负右端项非负)开始,逐步地迭代运算,直到得出)开始,逐步地迭代运算,直到得出最优解最优解。而。而应用对偶
23、规划的性质,可以找到一种求解线性规划的新方法应用对偶规划的性质,可以找到一种求解线性规划的新方法对偶单纯形法对偶单纯形法。对偶单纯形法则是从。对偶单纯形法则是从“不可行不可行”(右端项含负右端项含负)开始,在)开始,在保持最优性保持最优性之下逐步迭代,直到之下逐步迭代,直到不可行变为可行不可行变为可行,即得到,即得到可行最优解可行最优解为止。为止。当对偶问题的约束条件的数目较原问题为少时,应用对偶单纯形法求解较为方便。当对偶问题的约束条件的数目较原问题为少时,应用对偶单纯形法求解较为方便。第三十五页,讲稿共九十四页哦例:用对偶单纯形法解下列线性规划问题例:用对偶单纯形法解下列线性规划问题 mi
24、n w=12y1+16y2+15y3s.t.2y1+4y2 2 2y1 +5y3 3 y1,y2,y3 0解:此题可用人工变量方法求,但也可用对偶单纯形法。解:此题可用人工变量方法求,但也可用对偶单纯形法。max w=-12y1-16y2 15y3s.t.-2y1-4y2 +y4 =-2 -2y1 -5y3 +y5=-3 y1,y2,y3,y4,y5 0第三节 对偶单纯形法第三十六页,讲稿共九十四页哦列初始单纯形表列初始单纯形表列初始单纯形表列初始单纯形表Cj12161500CBXBby1y2y3y4y500y4y5-2-3-2-2-400-51001-12-16-1500第三节 对偶单纯形法
25、第三十七页,讲稿共九十四页哦Cj12161500CBXBby1y2y3y4y500y4y5-2-3-2-2-400-51001-12-16-15000-15y4y3-23/5-22/5-4001100-1/5-6-1600-3第三节 对偶单纯形法第三十八页,讲稿共九十四页哦Cj12161500CBXBby1y2y3y4y500y4y5-2-3-2-2-400-51001-12-16-15000-15y4y3-23/5-22/5-4001100-1/5-6-1600-3-12-15y1y311/5102-4/501-1/21/50-1/50-40-3-3Y*=(1,0,1/5,0,0)第三节 对
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 对偶 理论 灵敏度 分析 讲稿
限制150内