运筹学基础对偶线性规划(1).ppt
《运筹学基础对偶线性规划(1).ppt》由会员分享,可在线阅读,更多相关《运筹学基础对偶线性规划(1).ppt(42页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、2.3 对偶单纯形方法对偶单纯形方法原问题是:原问题的标准型是:minZ=15y1+24y2+5y3 6y2+y3 2 5y1+2y2+y3 1 y1,y2,y3 0maxw=-15y1-24y2-5y3+0y4+0y5 6y2+y3-y4 =25y1+2y2+y3 -y5=1 y1,y2,y3,y4,y5 0利用单纯形法:maxw=-15y1-24y2-5y3+0y4+0y5-My6-My7 6y2+y3-y4 +y6 =25y1+2y2+y3 -y5 +y7=1 y1,y2,y3,y4,y5,y6,y7 0一、一、一、一、用对偶单纯形方法解线性规划用对偶单纯形方法解线性规划用对偶单纯形方法
2、解线性规划用对偶单纯形方法解线性规划对偶单纯形方法对偶单纯形方法对偶单纯形方法对偶单纯形方法是使用对偶原理求解原问题解的一种方法,而不是求解对偶问题解的单纯形方法。与对偶单纯形方法相对应,原已有的单纯形方法称原始单纯形方法原始单纯形方法原始单纯形方法原始单纯形方法。用对偶单纯形方法解下述线性规划问题用对偶单纯形方法解下述线性规划问题原问题是:原问题的标准型是:minZ=15y1+24y2+5y3 6y2+y3 2 5y1+2y2+y3 1 y1,y2,y3 0maxw=-15y1-24y2-5y3+0y4+0y5 6y2+y3-y4 =25y1+2y2+y3 -y5=1 y1,y2,y3,y4
3、,y5 0maxw=-15y1-24y2-5y3+0y4+0y5 -6y2-y3+y4 =-2 -5y1-2y2-y3 +y5=-1 y1,y2,y3,y4,y5 0对偶单纯形方法对偶单纯形方法对偶单纯形方法对偶单纯形方法 Cj比比值值CBXBb检验数检验数 jy1y2y3y4y5-15-24-500-20-6-110-1-5-2-101y4Y5000-15-24-500检验数检验数 j1/3011/6-1/60-1/3-50-2/3-1/31Y2y5-2408-150-1-40maxw=-15y1-24y2-5y3+0y4+0y5 -6y2-y3+y4 =-2 -5y1-2y2-y3 +y5
4、=-1 y1,y2,y3,y4,y5 0检验数检验数 j1/4-5/410-1/41/41/215/2011/2-3/2Y2y3-24-517/2-15/200-7/2-3/2最优解最优解最优解最优解:Y Y*=(0,1/4,1/2,0,0)=(0,1/4,1/2,0,0)T T,maxmaxw*=-17/2=-17/24531.512MinZ=17/2=17/2应用对偶单纯形方法之矩阵法maxw=-15y1-24y2-5y3+0y4+0y5 -6y2-y3+y4 =-2 -5y1-2y2-y3 +y5=-1 y1,y2,y3,y4,y5 000-5-24-15-W-11-1-2-50-20-
5、1-60000180-10-15-W-1/31-2/30-501/301/6100-4-1/3-1/617/2-3/200-15/2-W1/2-3/21015/201/4001-5/40-7/21/2-1/4最优解最优解最优解最优解:Y Y*=(0,1/4,1/2,0,0)=(0,1/4,1/2,0,0)T T,max max w*=-17/2*=-17/2Min Z=17/2=17/2两种方法的主要区别区别区别区别在于:而对偶单纯形方法在整个迭代过程中,则是始终保持对偶对偶问题的可行性问题的可行性即亦即,,也就是全部检验数0,最后达到全部右边项所有负分量逐步变为全部右边项0,即满足原问题的可
6、行性时为止。所以,对偶单纯形方法实质对偶单纯形方法实质对偶单纯形方法实质对偶单纯形方法实质就是在保证对偶问题可行的条件下向原问题可行的方向迭代。原始单纯形方法在整个迭代过程中,始终是保持原问题的原问题的可行性可行性,最后达到检验数即即maxZ取得最优值时为止。-2560-24-1400-Z162/5-1/1001012-1/53/101 100相当于:直到对偶问题的解可行为止相当于:直到对偶问题的解可行为止相当于:即直到原问题的解可行为止相当于:即直到原问题的解可行为止用对偶单纯形方法解下述线性规划问题原问题是:原问题的标准型是:minZ=2x1+3x2+4x3 x1+2x2+x3 3 2x1
7、-x2+3x3 4 x1,x2,x3 0maxZ=-2x1-3x2-4x3+0 x4+0 x5 x1+2x2+x3 -x4 =32x1-x2+3x3 -x5=4 x1,x2,x3,x4,x5 0maxw=-2x1-3x2-4x3+0 x4+0 x5 -x1-2x2-x3+x4 =-3 -2x1+x2-3x3 +x5=-4 x1,x2,x3,x4,x5 0应用对偶单纯形方法之矩阵法00-4-3-2-W-41-31-20-30-1-2-100014-1-1-40-W2-1/23/2-1/210-1-1/21/2-5/20000128/5-1/5-3/500-W11/5-2/57/50102/51/
8、5-1/5100-8/5-1/5-2/5最优解最优解最优解最优解:Y Y*=(11/5,2/5,0,0,0)=(11/5,2/5,0,0,0)T T,MaxwMaxw=-28/5=-28/5maxw=-2x1-3x2-4x3+0 x4+0 x5 -x1-2x2-x3+x4 =-3 -2x1+x2-3x3 +x5=-4 x1,x2,x3,x4,x5 0MinZMinZ*=28/5*=28/5小结:对偶单纯形方法的解题过程一般分为四步(1)写写出出与与已已有有的的初初始始基基B对对应应的的初初始始单单纯纯形形表表。根据模型的标准型,若若若若右右右右边边边边项项项项的的的的数数数数字字字字都都都都为
9、为为为非非非非负负负负,且且且且检检检检验验验验数数数数都都都都为为为为非非非非正正正正,则已得到最优解,计算结束;否则,若右边项中至少有一个负分量,且检验数也仍然非正,则进行如下计算。(2)确定出基变量)确定出基变量。若有:则以对应的变量xr为出基变量。(3)确确定定入入基基变变量量。在单纯形表中观察xr所在行的各系数arj,若所有的arj0,则无可行解,停止计算;否则若存在:,则以xk为入基变量。(4)以以ark为主元按原始单纯形方法的迭代方法进行迭代为主元按原始单纯形方法的迭代方法进行迭代,得到新的单纯形表。对偶单纯形方法的显著优点:对偶单纯形方法的显著优点:(1)初始解可以是不可行解,
10、当检验数都非正时,即可以进行基的变换,这时不需要引进人工变量,因此就简化了计算。(2)对于变量个数多于约束方程个数的线性规划问题,采用对偶单纯形法计算量较少。因此对于变变变变量量量量较较较较少少少少、约约约约束束束束较较较较多多多多的线性规划问题,可以先将它转化成对偶问题,然后用对偶单纯形方法求解。2.4 影子价格影子价格 从对偶问题的基本性质可以看出,在单纯形法的每步迭代中有目标函数 其中bi代表第i种资源的拥有量;对偶变量yi代表第i种资源的估价。此时的估价不是市场价格,而是根据资源在生产中的贡献而作的估价。此时的定价区别于市场价格称为影子价此时的定价区别于市场价格称为影子价格。格。n 说
11、明说明 1、市场价格主要随市场供求变化;而它的影子价格有赖于资源的利用情况。生产任务、结构的改变会影响影子价格。生产任务、结构的改变会影响影子价格。2、影子价格是一种边际价格。y yi i代表代表b bi i每增加一个单位,每增加一个单位,目标函数目标函数z z的增量的增量maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0+1 (1 1)z*=42 z*=42 不变,不变,A A的边际价格为的边际价格为0 0+1 (2 2)x*=(10/3,13/2)z*=42.5x*=(10/3,13/2)z*=42.5,B B的边际价格为的边际价格为0.50.5
12、+1 (3 3)x*=(13/3,6)z*=43x*=(13/3,6)z*=43,C C的边际价格为的边际价格为1 1x1=82x2=123x1+4 x2=36n 说明说明3、资源的影子价格实际上是一种机会成本。市场价格低于影子价格时,可以买进这种资源。市场价格低于影子价格时,可以买进这种资源。市场价格高于影子价格时,可以卖出这种资源。市场价格高于影子价格时,可以卖出这种资源。随着资源的买进和卖出,它的影子价格也随之发生变化。4、生产过程中,如果某种资源bi未得到充分利用时,该种资源的影子价格为0;某种资源的影子价格不为0时,表明该种资源已经耗尽。由对偶互补松弛定理即可说明由对偶互补松弛定理即
13、可说明 灵敏度分析灵敏度分析,是指对系统或事物因周围条件变化所表现出的敏感性程度的分析。在前面讲的线性规划问题中,通常都是假定问题中的aij,bi,cj系数是已知的常数,但实际上这些参数都是一些估计或预测的数字。在现实中,如果市场条件变化,cj值就会发生变化;如果工艺技术条件改变,则aij就会变化;如果资源的可用量发生变化,则bi也会发生变化。2.4 灵敏度分析灵敏度分析问题:1、参数发生变化时,问题的最优解会有什么变化?2、参数多大的范围内变化时,原最优解保持不变。解决方法:解决方法:1、当参数变化时,用单纯形法从头计算,看最优解有无变化,但这样做既麻烦又没有必要。2、把个别参数的变化直接在
14、获得最优解的最终单纯形表上反映出来。这样就不需要从头计算,而只需对获得最优解的单纯形表进行审查,看一些数字变化后是否仍满足最优解的条件,如果不满足的话,再从这个表开始进行迭代计算,求得最优解即可。这也就是灵敏度分析。灵敏度分析的步骤如下:1.将参数的改变计算反映到最终单纯形表上来b*=B-1 b 具体计算方法是,按下列公式计算出由参数aij、bi、cj的变化而引起的最终单纯形表上有关数字的变化:Pi*=B-1 Pi(cj-zi)*=(cj-zi)-aijyi*2.检验原问题是否仍为可行解;即右端常数是否大于03.检验对偶问题是否仍为可行解;即检验数是否小于04.按下表所列情况得出结论和决定继续
15、计算的步骤。常数项常数项bi的改变量的改变量系数系数aij的改变量的改变量目标函数系数目标函数系数cj的改变量的改变量解的情况判定表一、分析cj变化的影响 目标函数中的系数cj的变化仅仅影响到检验数(cj-zi)的变化。所以将cj 的变化直接反映到最终单纯形表中,只可能出现表中的前两种情况。【例】已知线性规划问题:maxZ=2x1+x2 5x2 15 6x1+2x2 24 x1+x2 5 x1,x2 0用单纯形法求得最终单纯形表如下最终单纯形表Cj比比值值CBXBb检验数检验数 jx1x2x3x4x52100015/20015/4-15/27/21001/4-1/23/2010-1/43/2x
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 基础 对偶 线性规划
限制150内