电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

运筹学大作业单纯性法与对偶单纯性法比较VIP免费

运筹学大作业单纯性法与对偶单纯性法比较_第1页
1/5
运筹学大作业单纯性法与对偶单纯性法比较_第2页
2/5
运筹学大作业单纯性法与对偶单纯性法比较_第3页
3/5
对偶单纯形法与单纯形法对比分析1.教学目标:通过对偶单纯形法的学习,加深对对偶问题的理解2.教学内容:1)对偶单纯形法的思想来源2)对偶单纯形法原理3.教学进程:1)讲述对偶单纯形法解法的来源:所谓对偶单纯形法,就是将单纯形法应用于对偶问题的计算,该方法是由美国数学家C.莱姆基于1954年提出的,它并不是求解对偶问题解的方法,而是利用对偶理论求解原问题的解的方法。2)为什么要引入对偶单纯形法:单纯形法是解线性规划的主要方法,对偶单纯形法则提高了求解线性规划问题的效率,因为它具有以下优点:(1)初始基解可以是非可行解,当检验数都为负值时,就可以进行基的变换,不需加入人工变量,从而简化计算;(2)对于变量多于约束条件的线性规划问题,用对偶单纯形法可以减少计算量,在灵敏度分析及求解整数规划的割平面法中,有时适宜用对偶规划单纯形法。由对偶问题的基本性质可以知道,线性规划的原问题及其对偶问题之间存在一组互补的基解,其中原问题的松弛变量对应对偶问题的变量,对偶问题的剩余变量对应原问题的变量;这些互相对应的变量如果在一个问题的解中是基变量,则在另一问题的解中是非基变量;将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w。据此可知,用单纯形法求解线性规划问题时,在得到原问题的一个基可行解的同时,在检验数行得到对偶问题的一个基解,并且将两个解分别代入各自的目标函数时其值相等。我们知道,单纯形法计算的基本思路是保持原问题为可行解(这时一般其对偶问题为非可行解)的基础上,通过迭代,增大目标函数,当其对偶问题的解也为可行解时,就达到了目标函数的最优值。那么对偶单纯形法的基本思想可以理解为保持对偶问题为可行解(这时一般原问题为非可行解)的基础上,通过迭代,减小目标函数,当原问题也达到可行解时,即达到了目标函数的最优值。其实对偶单纯形法本质上就是单纯形法,只不过在运用时需要将单纯形表旋转一下而已。一.单纯形法和对偶单纯性法单纯形法是求解线性规划的主要方法,单纯形表则是单纯形法和对偶单纯形法的运算工具。设线性规划问题为MaxnjjjxcZ1),....,1(0),...,1(..1njmitsxbxajnjijij⑴将其化为标准形式,得MaxZ=CXs.t.0,XXssXbAX⑵其中),(CCNBC,)0,...,0,0(0CN,),(NBA,XXNBX,则其对应的线性约束转换为011XBXBXsNB,XBXBBXsNBb111,代入目标函数得XBCXBCCBCSBNBNBbZ111)(,相应的一个基解为bBXB1,0XN,0XS。显然,若01bB,且0)(1NBCCBN,01XBCSB,则基解01bXB为该线性规划的最优解,此时检验数均大于零,见表1。通过上面的分析,我们知道单纯形表的检验数实际上是目标函数中基变量、非基变量的价值系数,又由对偶理论知道它们是相应对偶问题的一个(加一个负号)基解。那么表中b列的数字仅仅表示的是XB的取值吗?我们可以猜想bB1很可能是对偶问题的检验数。这里首先给出问题(1)的对偶问题的一般形式Minmiiiybw1s.t.),....,1(0),...,1(1minjycyaimijiij⑶将问题(3)化为标准形式,得MinYBws.t.0,YYSSYCYA⑷由),(CCNBC,),(NBA,Ys为松弛变量,Ys相应分解为YsB、YsN,其中0),....,,(211yyyYmmmsB,0),....,,(22212yyyYnmmsN。得:CYBsBYB⑸CYNsNYN⑹由式⑸得到BYBCsBBY11⑺通过令0YsB,由式(5)得对偶问题的基解BCBY1,代入式(6)得CBCYNBsNN1,将式(7)对偶问题的目标函数得bbwBYBCsBB11。显然若目标函数达到最小,非基变量YsB的价值系数要求大于等于零,单纯形表b列01bB,即01bB实际上是对偶问题的非基变量检验数。二.对偶单纯形法的算法步骤(1)确定换出基的变量设原问题为(1),对偶问题为(3)。由),(),,(CCNBCNBA,不等式CYA则可分解为CCNBYNYB,(8)进一步添加松弛变量有等式(5)、(6),对等式(5)两端同时左乘B1有BCBYBsBY11(9)将BYsB1移至等式右端得BCBYBsBY11(10)由不等式(8)得0YBCB(11)0YNCN(12)将式(10)代入不等式(11)、(12)得011BBYBBYBCCCsBBBB(13)011NNYNBYBCCCsBBNN(14)将(13)、(14)合并得0),)((),(),(),(11NBNBYBYBCCCCCsBBNBNB(15)整理得011AACBYBCsBB(16)其中ACBCB1是单纯形表中X变量的检验数,记)(1jBACBC,(j=1,2,....,n),nmijaBAx'1)(矩阵,显然,若Y为基可行...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

运筹学大作业单纯性法与对偶单纯性法比较

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部