第三章对偶理论优秀PPT.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《第三章对偶理论优秀PPT.ppt》由会员分享,可在线阅读,更多相关《第三章对偶理论优秀PPT.ppt(75页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第三章对偶理论第三章对偶理论现在学习的是第1页,共75页学习目标理解对偶问题的基本理论;掌握对偶问题的经济解释影子价格;理解对偶单纯性法;掌握灵敏度分析第三章对偶问题与灵敏度分析现在学习的是第2页,共75页对偶问题?.对偶理论是线性规划中最重要的理论之一,是深入了解线性规对偶理论是线性规划中最重要的理论之一,是深入了解线性规对偶理论是线性规划中最重要的理论之一,是深入了解线性规对偶理论是线性规划中最重要的理论之一,是深入了解线性规划问题结构的重要理论基础。同时,由于问题提出本身所具有划问题结构的重要理论基础。同时,由于问题提出本身所具有划问题结构的重要理论基础。同时,由于问题提出本身所具有划问
2、题结构的重要理论基础。同时,由于问题提出本身所具有的经济意义,使得它成为对线性规划问题系统进行经济分析和的经济意义,使得它成为对线性规划问题系统进行经济分析和的经济意义,使得它成为对线性规划问题系统进行经济分析和的经济意义,使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么,对偶问题是怎样提出的,为什敏感性分析的重要工具。那么,对偶问题是怎样提出的,为什敏感性分析的重要工具。那么,对偶问题是怎样提出的,为什敏感性分析的重要工具。那么,对偶问题是怎样提出的,为什么会产生这样一种问题呢?么会产生这样一种问题呢?么会产生这样一种问题呢?么会产生这样一种问题呢?引引 言言现在学习的是
3、第3页,共75页 从两个不同的角度讨论线性规划问题从两个不同的角度讨论线性规划问题从两个不同的角度讨论线性规划问题从两个不同的角度讨论线性规划问题原始的角度原始的角度对偶的角度对偶的角度例例对偶问题的提出现在学习的是第4页,共75页唉唉!我想租您的木工和油漆工一我想租您的木工和油漆工一用。咋样?价格嘛用。咋样?价格嘛好说,好说,肯定不会让您兄弟吃亏讪。肯定不会让您兄弟吃亏讪。王老板做家具赚了王老板做家具赚了 大钱,虽然我也想做家具大钱,虽然我也想做家具生意,却苦于没有生意,却苦于没有足够的木工和油漆工足够的木工和油漆工 咋办?只有租咯。咋办?只有租咯。Hi:王老板,听说:王老板,听说近来家具生
4、意好惨了,近来家具生意好惨了,也帮帮兄弟我哦也帮帮兄弟我哦!家具生意还真赚钱,但家具生意还真赚钱,但 是现在的手机生意这么好,是现在的手机生意这么好,不如干脆把我的木工和油漆不如干脆把我的木工和油漆工租给他,又能工租给他,又能收租金又可做生意。收租金又可做生意。价格嘛价格嘛好商量,好商量,好商量。只是好商量。只是.王王 老老 板板李李 老老 板板引例两家具制造商间的对话:现在学习的是第5页,共75页王老板的王老板的家具生产模型家具生产模型:x1、x2是桌、椅生产量。是桌、椅生产量。Z是家具销售总收入(总利润)。是家具销售总收入(总利润)。max Z=50 x1+30 x2s.t.4x1+3x2
5、 120(木工)木工)2x1+x2 50(油漆工)(油漆工)x1,x2 0原始线性规划问题,记为(原始线性规划问题,记为(P)王老板的王老板的资源出租模型资源出租模型:y1、y2单位木、漆工出租价格。单位木、漆工出租价格。W是资源出租租金总收入。是资源出租租金总收入。min W=120y1+50y2s.t.4y1+2y2 50 3y1+y2 30 y1,y2 0对偶线性规划问题,记为(对偶线性规划问题,记为(D)对偶问题对偶问题王老板按(王老板按(D)的解)的解 y1、y2出租其拥有的木、漆工资源,既保证了自出租其拥有的木、漆工资源,既保证了自己不吃亏己不吃亏(出租资源的租金收入并不低于自己生
6、产时的销售收入出租资源的租金收入并不低于自己生产时的销售收入),又使,又使得出租价格对李老板有极大的吸引力得出租价格对李老板有极大的吸引力(李老板所付出的总租金李老板所付出的总租金W最少最少).现在学习的是第6页,共75页对偶的定义对偶的定义原始原始问题问题max z=Cmax z=CT TX Xs.t.AXs.t.AX b b X 0 X 0对偶问题min W=bTYs.t.ATYC Y 0minCATbTbACTmaxnmnm现在学习的是第7页,共75页项目项目项目项目原问题原问题原问题原问题对偶问题对偶问题对偶问题对偶问题A Ab bC C目标函数目标函数目标函数目标函数约束条件约束条件
7、约束条件约束条件决策变量决策变量决策变量决策变量约束系数矩阵约束系数矩阵约束系数矩阵约束系数矩阵约束条件的右端项向量约束条件的右端项向量约束条件的右端项向量约束条件的右端项向量目标函数中的价格系数向量目标函数中的价格系数向量目标函数中的价格系数向量目标函数中的价格系数向量max Z=Cmax Z=CT TX XAX AX b bX X 0 0其约束系数矩阵的转置其约束系数矩阵的转置其约束系数矩阵的转置其约束系数矩阵的转置目标函数中的价格系数向量目标函数中的价格系数向量目标函数中的价格系数向量目标函数中的价格系数向量约束条件的右端项向量约束条件的右端项向量约束条件的右端项向量约束条件的右端项向量
8、min W=bmin W=bT TY YA AT TY Y C CY Y 0 0对称形式下对偶问题的一般形式现在学习的是第8页,共75页对称的原始问题和对偶问题对称的原始问题和对偶问题对偶问题为min w=2y1+3y2-y3s.t.y1+2y2+y36 2y1-3y2+2y39 y1,y2,y30根据定义,原始问题为max z=6x1+9x2s.t.x1+2x22 2x1-3x23 x1+2x2-1 x1,x20对偶问题是极小化问题对偶问题的约束全为对偶问题有3个变量,2个约束对偶问题的变量全部为非负原始问题是极大化问题原始问题的约束全为原始问题有2个变量,3个约束原始问题的变量全部为非负对
9、偶问题变量的个数(3)等于原始问题约束条件的个数(3)对偶问题约束条件的个数(2)等于原始问题变量的个数(2)现在学习的是第9页,共75页根据定义写出对偶问题的练习根据定义写出对偶问题的练习max z=2x1+x2-3x3s.t.x1-3x2+2x3-5x4 6 4x1+x2-5x3+2x4 9 -x1+2x2 +x4 12 x1,x2,x3,x4 0原始问题有4个变量,3个约束,对偶问题应该有3个变量,4个约束。根据定义,对偶问题为:y1y2y3min w=6y1+9y2+12y3s.t.y1+4y2-y3 2 -3y1+y2+2y3 1 2y1-5y2 -3 -5y1+2y2+y3 0 y
10、1,y2,y3 0 x1x2x3x4现在学习的是第10页,共75页max z=2x1+3x2-x3s.t.x1+2x2+x3=6 2x1-3x2+2x39 x1,x2,x30max z=2x1+3x2-x3s.t.x1+2x2+x36 x1+2x2+x36 2x1-3x2+2x39 x1,x2,x30max z=2x1+3x2-x3s.t.-x1-2x2-x3-6 x1+2x2+x3 6 2x1-3x2+2x39 x1,x2,x30min w=-6w1+6w2+9w3s.t.-w1+w2+2w3 2 -2w1+2w2-3w3 3 -w1+w2+2w3 -1 w1,w2,w30min w=6(w
11、2-w1)+9w3s.t.(w2-w1)+2w3 2 2(w2-w1)-3w3 3 (w2-w1)+2w3 -1 w1,w2,w30min w=6y1+9y2s.t.y1+2y2 2 2y1-3y2 3 y1+2y2 -1 y1:Free y20y1=w2-w1,y1:Free,y2=w3如果原始问题中一个约束是等号约束,则对偶问题中相应的变量没有符号限制非对称形式的对偶原始问题有“=”约束现在学习的是第11页,共75页非对称形式的对偶原始问题有“”约束max z=2x1+3x2-x3s.t.x1+2x2+x3 6 2x1-3x2+2x39 x1,x2,x30max z=2x1+3x2-x3s
12、.t.-x1-2x2-x3-6 2x1-3x2+2x39 x1,x2,x30min w=-6y1+9y2s.t.-y1+2y22 -2y1 -3y23 -y1+2y2-1 y1,y20min w=6y1+9y2s.t.y1+2y22 2y1-3y23 y1+2y2-1 y10,y20y1=-y1,y10如果极大化原始问题中一个约束是“”约束,则对偶问题中相应的变量0现在学习的是第12页,共75页非对称形式的对偶总结原始问题约束条件的性质,影响对偶问题变量的性质。原始问题变量的性质,影响对偶问题约束条件的性质。max z=Cmax z=CT TX Xs.t.AXs.t.AX b b X 0 X
13、0min w=bTYs.t.ATYC Y 0max z=Cmax z=CT TX Xs.t.AXs.t.AX=b b X 0 X 0min w=bTYs.t.ATYC Y:Freemax z=Cmax z=CT TX Xs.t.AXs.t.AX b b X 0 X 0min w=bTYs.t.ATYC Y 0现在学习的是第13页,共75页非对称形式下对偶问题的一般形式项目项目项目项目原问题原问题原问题原问题(对偶问题)(对偶问题)(对偶问题)(对偶问题)对偶问题对偶问题对偶问题对偶问题(原问题)(原问题)(原问题)(原问题)目标函数类型目标函数类型目标函数类型目标函数类型maxmaxminmi
14、n目标函数系数与右边项目标函数系数与右边项目标函数系数与右边项目标函数系数与右边项的对应关系的对应关系的对应关系的对应关系目标函数各变量系数对应目标函数各变量系数对应目标函数各变量系数对应目标函数各变量系数对应约束条件右边项的系数约束条件右边项的系数约束条件右边项的系数约束条件右边项的系数右边项的系数对应目标函右边项的系数对应目标函右边项的系数对应目标函右边项的系数对应目标函数系数数系数数系数数系数变量个数与约束条件个变量个数与约束条件个变量个数与约束条件个变量个数与约束条件个数的对应关系数的对应关系数的对应关系数的对应关系变量个数变量个数变量个数变量个数 n n约束条件个数约束条件个数约束条
15、件个数约束条件个数 m m约束条件个数约束条件个数约束条件个数约束条件个数 n n变量个数变量个数变量个数变量个数 m m原问题变量类型与对偶原问题变量类型与对偶原问题变量类型与对偶原问题变量类型与对偶问题约束条件类型的对问题约束条件类型的对问题约束条件类型的对问题约束条件类型的对应关系应关系应关系应关系 0 0变量类型变量类型变量类型变量类型 0 0 无限制无限制无限制无限制 约束条件类型约束条件类型约束条件类型约束条件类型 =原问题约束条件类型与原问题约束条件类型与原问题约束条件类型与原问题约束条件类型与对偶问题变量类型的对对偶问题变量类型的对对偶问题变量类型的对对偶问题变量类型的对应关系
16、应关系应关系应关系 约束条件类型约束条件类型约束条件类型约束条件类型 =0 0 变量类型变量类型变量类型变量类型 0 0 无限制无限制无限制无限制现在学习的是第14页,共75页max z=2x1+x2-3x3s.t.x1-3x2+2x3-5x46 4x1+x2-5x3+2x4 9 -x1+2x2 +x4 12 x1,x2 0,x3Free,x4 0写对偶问题的练习(1)现在学习的是第15页,共75页min z=2x1+4x2-x3s.t.3x1-x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max y=6w1+12w2+8w3+15w4s.t
17、.3w1-w2+2w3+w4 2 -w1+2w2+w3+3w4 4 2w1-3w2+2w3-w4 -1 w1 0,w2 ,w3 0,w4 0=Free=x10 x20 x3:Freep原始问题变量的个数(3)等于对偶问题约束条件的个数(3);p原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。p原始问题变量的性质影响对偶问题约束条件的性质。p原始问题约束条件的性质影响对偶问题变量的性质。写对偶问题的练习(2)现在学习的是第16页,共75页对偶问题的性质总结1、对偶的对偶就是原始问题对偶的定义max z=Cmax z=CT TX Xs.t.AXs.t.AX b b X 0 X 0min
18、w=bTYs.t.ATYCY 0对偶的定义max w=-bTYs.t.-ATY-CY 0min z=-Cmin z=-CT TX Xs.t.-AXs.t.-AX-b-b X 0 X 0现在学习的是第17页,共75页2、两个问题的可行解对应的目标函数值互为上下界例:min z=2x1+3x2s.t.x1+3x23 2x1+x2 4 x1,x2 0max w=3y1+4y2s.t.y1+2y22 3y1+y2 3 y1,y2 00 1 2 34321A(3,0)B(1.8,0.4)C(0,4)D(2,2)可行解可行解z z最优解最优解A A6 6B B4.84.8是是C C1212D D10103
19、210 1 2A(1,0)B(1.9,0.4)C(0,1)O(0,0)可行解可行解y y最优解最优解O O0 0A A3 3B B4.84.8是是C C4 4现在学习的是第18页,共75页3、若原问题解无界,则其对偶问题无可行解。4、两个问题最优解的目标函数值必相等。5、两个问题都有可行解时则两个问题必都有最优解。6、两个问题最优解中,一个问题中某个变量取值非零,则该变量在对偶问题中对应的约束条件必为紧约束;反之,如果约束条件为松约束,则其对应的对偶变量一定取值为零。互补松弛性定理现在学习的是第19页,共75页互补松弛关系的分量表示现在学习的是第20页,共75页互补松弛关系的分量表示现在学习的
20、是第21页,共75页互补松弛关系的分量表示由于原始问题和对偶问题的所有变量和松弛变量都是非负的,因此以上两式中的每一项都等于0。即在原始问题和对偶问题的最优解中,原始问题的一个变量和对偶问题相应的松弛变量,对偶问题的一个变量和原始问题相应的松弛变量,组成互补松弛对,在每一对变量中,其中一个大于0,另一个一定等于0。互补松弛关系的分量形式现在学习的是第22页,共75页 y1.yi.ym ym+1 .ym+j .yn+m x1 .xj .xn xn+1 xn+i xn+m 对偶问题的变量 对偶问题的松弛变量 原始问题的变量 原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m;j=1
21、,2,n)在一对变量中,其中一个大于0,另一个一定等于0互补松弛关系的分量表示现在学习的是第23页,共75页利用互补松弛关系求解线性规划min z=6x1+8x2+3x3s.t.x1+x2 1 x1+2x2+x3-1 x1,x2,x3 0max w=y1-y2s.t.y1+y2 6 y1+2y2 8 y2 3 y1,y20原始问题对偶问题0 1 2 3 4 5 6 7 8654321y1y2w=-1 w=1w=3w=6最优解为(y1,y2)=(6,0)max w=6先用图解法求解对偶问题。现在学习的是第24页,共75页min z=6x1+8x2+3x3s.t.x1+x2 1 x1+2x2+x3
22、-1 x1,x2,x3 0max w=y1-y2s.t.y1+y2 6 y1+2y2 8 y2 3 y1,y20max w=y1-y2s.t.y1+y2+y3 =6 y1+2y2 +y4 =8 y2 +y5=3 y1,y2,y3,y4,y50(y1,y2)=(6,0)(y1,y2,y3,y4,y5)=(6,0,0,2,3)min z=6x1+8x2+3x3s.t.x1+x2 -x4 =1 x1+2x2+x3 -x5 =-1 x1,x2,x3,x4,x50(x1,x2,x3|x4,x5)(y1,y2|y3,y4,y5)x2=x3=x4=0 x1=1,x5=2引进松弛变量 求对偶引进松弛变量图解法
23、求解代入约束求出松弛变量互补松弛关系代入约束求解(x1,x2,x3,x4,x5)=(1,0,0,0,2)现在学习的是第25页,共75页 我们已经明白原始线性规划与对偶线性规划之间形式我们已经明白原始线性规划与对偶线性规划之间形式我们已经明白原始线性规划与对偶线性规划之间形式我们已经明白原始线性规划与对偶线性规划之间形式上的对偶以及他们的解之间的关系,那么对偶问题的解除上的对偶以及他们的解之间的关系,那么对偶问题的解除上的对偶以及他们的解之间的关系,那么对偶问题的解除上的对偶以及他们的解之间的关系,那么对偶问题的解除了前面引例中提到的租金这种经济含义外其深刻的经济含了前面引例中提到的租金这种经济
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第三 对偶 理论 优秀 PPT
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内