第三章对偶理论与灵敏度分析精选文档.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(41页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第三章对偶理论与灵敏度分析本讲稿第一页,共四十一页1 单纯形法的矩阵描述单纯形法的矩阵描述设线性规划问题设线性规划问题设设B是一个可行基,令(是一个可行基,令(A,I)=(B,N,I),则:),则:本讲稿第二页,共四十一页1.检验数的矩阵描述:检验数的矩阵描述:B=CB-CBB-1B=0 N=CN-CBB-1N S=-CBB-1 =min(B-1b)i/(B-1Pk)i|(B-1Pk)i0=(B-1b)l/(B-1Pk)lXBbXBXNXsB-1bIB-1NB-1(B-1 b)i(B-1Pk)i-zCBB-1b0CN-CBB-1N-CBB-13.单纯形表的矩阵描述:单纯形表的矩阵描述:=C-C
2、BB-1A2.的矩阵描述:的矩阵描述:本讲稿第三页,共四十一页2 改进单纯形法改进单纯形法用改进单纯形法求解线性规划问题的计算步骤:用改进单纯形法求解线性规划问题的计算步骤:1.确定初始可行基确定初始可行基B1。求出。求出B1-1;2.计计算算非非基基变变量量的的检检验验数数N。若若N 0已已求求的的最最优优解解,停止计算停止计算,否则进行下一步;否则进行下一步;3.确定换入变量确定换入变量 xk;4.计算计算B1-1b,B1-1 Pk及及;若若 0那么无最优解,停止计算,否则进行下一步;那么无最优解,停止计算,否则进行下一步;5.确定换出变量确定换出变量 xl;6.计算计算B2-1;7.重复
3、重复27步。步。本讲稿第四页,共四十一页 本讲稿第五页,共四十一页 例:用改进单纯形法求解例:用改进单纯形法求解本讲稿第六页,共四十一页解:解:本讲稿第七页,共四十一页 本讲稿第八页,共四十一页 本讲稿第九页,共四十一页 本讲稿第十页,共四十一页3 对偶问题的提出对偶问题的提出 例:例:设备设备原材料原材料A原材料原材料B1402048 台时台时16 kg12 kg利润利润23x1minx2x1x2y1y2y3本讲稿第十一页,共四十一页当该问题达到最优时有:当该问题达到最优时有:z的上界为无限大,所以只存在最小值。于是得到另一个线的上界为无限大,所以只存在最小值。于是得到另一个线性规划问题性规
4、划问题对线性规划问题线性规划问题对偶问题对偶问题原问题原问题本讲稿第十二页,共四十一页4 线性规划的对偶理论线性规划的对偶理论 4.1 原问题与对偶问题的关系原问题与对偶问题的关系本讲稿第十三页,共四十一页原问题(对偶问题原问题(对偶问题)对偶问题(原问题)对偶问题(原问题)例:例:23-51本讲稿第十四页,共四十一页本讲稿第十五页,共四十一页本讲稿第十六页,共四十一页4.2 对偶问题的性质对偶问题的性质1.对称性对称性 对偶问题的对偶是原问题。对偶问题的对偶是原问题。2.弱弱对对偶偶性性 若若X*是是原原问问题题的的可可行行解解,Y*是是对对偶偶问问题题的可行解的可行解,则存在则存在 CX*
5、Y*b证证 设原问题及对偶问题为设原问题及对偶问题为 max z=CX,AXb,X0 min=Yb,YAC Y0 若若X*是原问题的可行解,是原问题的可行解,Y*是对偶问题的可行解是对偶问题的可行解 AX*b Y*AC Y*AX*Y*b Y*AX*CX*CX*Y*AX*Y*bCX*Y*b本讲稿第十七页,共四十一页3.无无界界性性 若若原原问问题题(对对偶偶问问题题)为为无无界界解解,则其对偶问题(原问题)无可行解。则其对偶问题(原问题)无可行解。4.可可行行解解是是最最优优解解的的性性质质 设设X是是原原问问题题的的可可行行解解,Y是是对对偶偶问问题题的的可可行行解解,当当CX=Yb时,时,X
6、,Y是最优解。是最优解。5.对对偶偶定定理理 若若原原问问题题有有最最优优解解,则则对对偶偶问问题也有最优解,且目标函数相等。题也有最优解,且目标函数相等。6.互互补补松松驰驰性性 若若X是是原原问问题题的的可可行行解解,Y是是对对偶偶问问题题的的可可行行解解,那那么么YXs=0,Ys X=0,当且仅当当且仅当 X,Y为最优解。为最优解。本讲稿第十八页,共四十一页6.互互补补松松驰驰性性 若若X是是原原问问题题的的可可行行解解,Y是是对对偶偶问问题题的可行解,那么的可行解,那么YXs=0,Ys X=0,但且仅当,但且仅当 X,Y为最优解。为最优解。证:设原问题及对偶问题的标准型是证:设原问题及
7、对偶问题的标准型是 max z=CX,AX+XS=b,X,XS 0 min=Yb,YAYS=C Y,YS 0 z=(YAYS)X=YAXYSX =Y(AX+XS)=YAX+YXS X是原问题的可行解,是原问题的可行解,Y是对偶问题的可行解是对偶问题的可行解 z =YAXYS X =YAX+YXS当当YXs=0,Ys X=0时时z=,则,则X,Y是最优解。是最优解。当当 X,Y是最优解时是最优解时 z=,则,则YXs=0,Ys X=0 本讲稿第十九页,共四十一页例:已知线性规划问题例:已知线性规划问题max其对偶问题的最优解为其对偶问题的最优解为试用对偶理论求原问题的最优解试用对偶理论求原问题的
8、最优解解:解:max本讲稿第二十页,共四十一页 7.设原问题及对偶问题的标准型是设原问题及对偶问题的标准型是 max z=CX,AX+XS=b,X,XS 0 min=Yb,YAYS=C Y,YS 0 则则原原问问题题单单纯纯形形表表的的检检验验数数行行对对应应其其对对偶偶问问题题的的一个基解,对应关系如下表:一个基解,对应关系如下表:XBXNXs0CNCBB-1NCBB-1Ys1Ys2Y证证:CBB-1A(0,CN+CBB-1N)=CBB-1(B,N)(0,CN+CBB-1N)=(CB,CN)=C本讲稿第二十一页,共四十一页5 对偶问题的经济解释对偶问题的经济解释影子价格影子价格 设设B是是线
9、线性性规规划划问问题题的的一一可可行行基基,这这目目标标函函数为数为 所所以以变变量量yi的的经经济济意意义义是是在在其其他他条条件件不不变变的的情情况况下,单位资源变化所引起的目标函数值的变化。下,单位资源变化所引起的目标函数值的变化。yi的的值值代代表表对对第第i种种资资源源的的估估价价。这这种种估估价价是是针针对对具具体体工工厂厂的的具具体体产产品品而而存存在在的的一一种种特特殊殊价价格格,称称它它为为“影子价格影子价格”。本讲稿第二十二页,共四十一页Q2(4,2)X2X10 1 2 3 4 54321Q1(4,0)Q3(2,3)Q4(0,3)OQ4Q2Q3*A增加增加4,利润增加,利润
10、增加41/8=1/2设备增加设备增加2,利润增加,利润增加23/2=3Q(5,3/2)Q(4,3)本讲稿第二十三页,共四十一页6 对偶单纯形法对偶单纯形法bXBXNXsXBB-1b IB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1-Ys1-Ys2-YXBbXBXNXsXBB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1 0变为0变为 00单单纯纯形形法法对对偶偶单单纯纯形形法法本讲稿第二十四页,共四十一页 对偶单纯形法的计算步骤:对偶单纯形法的计算步骤:1.确定初始的基,使非基变量的检验数小于等于零。确定初始的基,使非基变量的检验数小于等于零。2.若若b
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第三 对偶 理论 灵敏度 分析 精选 文档
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内