运筹学第二章电子讲稿精.ppt
《运筹学第二章电子讲稿精.ppt》由会员分享,可在线阅读,更多相关《运筹学第二章电子讲稿精.ppt(58页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、运筹学第二章电子讲稿第1页,本讲稿共58页XB=B-1b-B-1NXN=CB(B-1b-B-1NXN)+CNXN=CBB-1b+(CN-CBB-1N)XN单纯形表 XB XN XS B-1b I B-1N B-1-CBB-1b 0 CN-CBB-1N -CBB-1第2页,本讲稿共58页3.对偶问题的提出 原问题:有n种食物,每种食物含有m种营养成分,第j种食物每个单位含第i种营养成分为aij单位。现知每人每天需要第i种营养成分为bi单位,第j种食物的单价为cj。试问一个消费者如何选购食物,才能使得既满足需要,又花费最小?问题归结为 min CX s.t.AXb X0第3页,本讲稿共58页xj选
2、购第j种食物的数量(单位)对偶问题:设有一个制造商,要生产 m种不同的药丸来代替上述 n 种不同的食物。试问每种药丸的价格如何确定,才能获利最大?设第i种药丸的价格为yi max w=Yb YAC Y0第4页,本讲稿共58页4.线性规划的对偶理论4.1.原问题与对偶问题的关系原问题(P)max=c1x1+c2x2+cnxn s.t.a11x1+a12x2+a1nxnb1 a21x1+a22x2+a2nxnb2 am1x1+am2x2+amnxnbm xj0,j=1,2,n第5页,本讲稿共58页(P)max=CX AXb X0对偶问题(D)min=b1y1+b2y2+bmym s.t.a11y1
3、+a21y2+am1ymc1 a12y1+a22y2+am2ymc2 a1ny1+a2ny2+amnymcn yi0,i=1,2,m第6页,本讲稿共58页(D)min=Yb YAC Y0 x1 x2 xn y1 a11 a12 a1n b1 y2 a21 a22 a2n b2 ym am1 am2 amn bm c1 c2 cn maxmin第7页,本讲稿共58页 例 写出下面问题的对偶问题max=8x1+9x2s.t.4x1+x25 2x1+3x26 x1,x20对偶问题是:min=5y1+6y2 s.t.4y1+2y28 y1+3y29 y1,y20第8页,本讲稿共58页对于标准形式的线性
4、规划问题max=CX s.t.AX=b X0其对偶问题是 min=Yb s.t.YA C Y无非负约束证标准形式的线性规划问题可以写为第9页,本讲稿共58页max=CX s.t.AXb -AX-b X0其对偶问题为min=Yb-Y”bs.t.YA-Y”AC Y,Y”0令Y=Y-Y”,则上述问题变为第10页,本讲稿共58页 min=Yb s.t.YAC Y没有限制一般,有下列结论第11页,本讲稿共58页原问题(对偶问题)对偶问题(原问题)目标函数 max z目标函数 min 变 量n 个约束条件n个00无约束=m个m个约束条件00=无约束变 量约束条件右端项目标函数变量的系数目标函数变量的系数约
5、束条件右端项第12页,本讲稿共58页例 max=2x1+x2+3x3+x4 s.t.x1+x2+x3+x45 2x1-x2+3x3 =-4 x1 -x3+x4 1 x10,x2,x4无约束,x3 0 min=5y1+4y2-y3 s.t.y1-2y2-y3 2 y1+y2 =1 y1+3y2-y3 3 y1 +y3=1其对偶问题为第13页,本讲稿共58页y10,y2无约束,y3 0第14页,本讲稿共58页4.2.对偶问题的基本性质 1.对称性对称性:对偶问题的对偶问题是原问题。:对偶问题的对偶问题是原问题。2.弱对偶性弱对偶性:若X和分别为(P),(D)的可行解,则有 =CXb=3.无界性:若
6、原问题(对偶问题)为无界解,则其对偶问题(原问题)无可行解。4.可行解是最优解的性质可行解是最优解的性质:若:若X,分别是问题分别是问题(P),(D)的可行解。并且的可行解。并且CX=b,则,则X,分别分别为为(P),(D)的最优解。的最优解。第15页,本讲稿共58页 5.对偶定理对偶定理:若原问题有最优解,那么对偶:若原问题有最优解,那么对偶问题也有最优解,且目标函数值相等。问题也有最优解,且目标函数值相等。6.互补松驰性互补松驰性(松紧定理松紧定理):若:若X,分别是分别是(P),(D)问题的可行解,那么问题的可行解,那么X,为最优解的充要为最优解的充要条件是:条件是:XS=0,YSX=0
7、 (即若 AiX i=0 AiX=bi 0 Pj=Cj 0 PjCj=Xj=0)第16页,本讲稿共58页例1.求解下列线性规划问题 max=x1+2x2+3x3+4x4 s.t.x1+2x2+2x3+3x420 2x1+x2+3x3+2x420 xj0,j=1,2,3,4解其对偶问题为 min=20y1+20y2 s.t.y1+2y21 2y1+y22 2y1+3y23 3y1+2y24 y1,y20(1.2,0.2)1212.y1y2第17页,本讲稿共58页用图解法得最优解 y1=1.2,y2=0.2 根据松紧定理,原问题的最优解必满足 XS=0 及YSX=0及 (y3,y4,y5,y6)=
8、0 x5 (y1,y2)x6 =0 x1x2x3x4 将y1=1.2,y2=0.2代入对偶问题的约束条件,得 y30,y40,所以x1=x2=0 又因y10,y20。所以x5=x6=0,即原问题为等式约束第18页,本讲稿共58页 x1=x2=0 x1+2x2+2x3+3x4=20 2x1+x2+3x3+2x4=20即 x1=x2=0,x3=4,x4=4 原问题的最优解为(0,0,4,4)T 7.原问题单纯形表的检验数行对应其对偶问题的一个基解.其对应关系见表:XB XN XS 0 CN-CBB-1N -CBB-1 YS1 YS2 -Y第19页,本讲稿共58页YS1为对应原问题中基变量XB的剩余
9、变量,YS2是对应问题中非基变量XN的剩余变量。设B是原问题的一个可行基,则A=(B,N)max=CBXB+CNXN BXB+NXN+XS=b XB,XN,XS0相应地对偶问题可表示为 min=Yb YB-YS1=CB YN-YS2=CN Y,YS1,YS20第20页,本讲稿共58页令Y=CBB-1,则 YS1=0 -YS2=CN-CBB-1N 例1.max=x1+4x2+3x3 s.t.2x1+2x2+x34 x1+2x2+2x36 xj0对偶问题为 min=4y1+6y2 s.t.2y1+y21 2y1+2y24 第21页,本讲稿共58页 y1+2y23 y1,y20初始单纯形表为 4 2
10、 2 1 1 0 6 1 2 2 0 1 0 1 4 3 0 0 对偶问题的基本解为对偶问题的基本解为y1=0,y2=0,ys1=-1,ys2=-4,ys3=-3其最终表为第22页,本讲稿共58页1 3/2 1 0 1 -1/22 1 0 1 1 1-10 2 0 0 1 -1 由原问题的最终表可知,y1=1,y2=1(最优解),ys1=2第23页,本讲稿共58页5.对偶问题的经济解释影子价格 设B是最优基,则目标函数的最优值是 *=CBB-1b=Y*b yi*的经济意义是:在其它条件不变的情况下,单位资源变化所引起的目标函数最优值的变化。影子价格:在其它数据不变的条件下,一个约束右边的项增加
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 第二 电子 讲稿
限制150内