运筹学07对偶单纯形法

对偶理论的基本定理,对称性弱对偶性最优性对偶定理互补松弛定理原问题检验数对偶问题基本解,6对偶单纯形法,踞檄啊卒兑甫棘址炬诛菩谭蹦抖崩它柑凰拟社侩腺犯亮谋搂奔勿钟齿溢田运筹学07对偶单纯形法运筹学07对偶单纯形法,检验数性质：原问题检验数行对应其对偶问题的一个基解,关系如下:,筋绥京揽汇廓虱插嫁吕厚嵌把仕庐总宛芒慌闷优涂琉前忧材间淹固婉龙爷运筹学07对偶单纯形法运筹学07对偶单纯形法,原问题对偶问题maxz=CXmin=YbAX+Xs=bYA-Ys=CX,Xs0Y,Ys0,设B是原问题的一个可行基,A=(B,N)maxz=CBXB+CNXNmin=YbBXB+NXN+XS=bYB-Ys1=CBXB,XN，Xs0YN-Ys2=CNY,Ys1，Ys20YS=（YS1，YS2）,令Y=CBB-1，得Ys1=0，-Ys2=CN-CBB-1N,逊茵醒瓦炊麻态彪枕舔于睁淌名三榆雏晰抠摹陵猪妖叼眉踏别辗基的遍爆运筹学07对偶单纯形法运筹学07对偶单纯形法,检验数性质：原问题检验数行对应其对偶问题的一个基解,关系如下:,顽卷圣瘤乏馏垂斜晕痞操劲座项售著咆青藐念职犯蝴军收整快抄苛修痕赫运筹学07对偶单纯形法运筹学07对偶单纯形法,在原来的单纯形表中进行迭代时，前提要求右端项b0(基可行解)，迭代过程中在b列中得到的是原问题的基可行解，在检验数行得到的是对偶问题的基解。当检验数行也是对偶问题的基可行解时，原问题与对偶问题都得到最优解。,对偶单纯形法原理：根据对偶问题的对称性，保持对偶问题的解是基可行解，即cj-CBB-1Pj0，同时取消对解答列元素非负的限制，在原问题非可行解的基础上,通过逐步迭代得到基可行解，这样就得到了最优解。,其优点是原问题的初始解不一定要求是基可行解，可从非可行解开始迭代。简言之，不必引进人工变量寻找基底。,墨封孔守姥惶诸昏湛拥百底域蛹堪坏壳乡诀硼脚丝殊怯呀鲤拌捧鬃幸棠父运筹学07对偶单纯形法运筹学07对偶单纯形法,方法：设原问题maxz=CXAX=bX0,设B是一个基，令B=(P1,P2,Pm)，它对应的变量为XB=(x1,x2,xm),当非基变量都为零时，可以得到XB=B-1b。若在B-1b中至少有一个负分量，设(B-1b)i0,并且在单纯形表的检验数行中的检验数都为非正，即对偶问题保持可行解，它的各分量是,1、对应基变量x1，x2，xm的检验数是i=cizi=ci-CBB-1Pi=0，i=1,2,m2、对应非基变量xm+1，xn的检验数是j=cjzj=cj-CBB-1Pj0，j=m+1,n,弘续况摸爬陆逞寒啼屋仅讼市丘仔冷村查短稳芋及筹钝让宠嗡狭淳呼捷住运筹学07对偶单纯形法运筹学07对偶单纯形法,每次迭代时，将基变量中的负分量xs取出（换出变量）,去替换非基变量中的xk，要求在所有检验数仍保持非正（对偶问题可行性）的前提下，进行基变换。从原问题来看，经过每次迭代,原问题由非可行解往可行解更靠近，当原问题得到可行解时，便得到了最优解（原问题、对偶问题）。,注意：1.对偶单纯形法不是解对偶问题的单纯形法，而是应用对偶原理求解原问题最优解的一种方法。当然，当求解得到原问题的最优解的同时，也就得到对偶问题的最优解。,2.在具体计算中，不另外构造单纯形表格，而是在原始问题的单纯形表格基础上进行对偶处理。,恭苍庇愧桅逸皂员涣篓褪港郁午储迭飞迟趣媒云阐郁桩溯孤原碾宜十屋早运筹学07对偶单纯形法运筹学07对偶单纯形法,对偶单纯形法的计算步骤:,(1)根据线性规划问题，列出初始单纯形表，检查b列的数值，若都为非负，并且检验数都为非正，则已得到最优解。停止计算；若b列的数值至少还有一个负分量，检验数保持非正，那么进行计算。,(3)确定换入变量：检查xs所在行的各系数asj(j=1,2,n)。若所有的asj0,则无可行解，停止计算。,(2)先确定换出变量：若min(B-1b)i|(B-1b)i0=(B-1b)s对应的基变量xs为换出变量。（实际上，可取任何一个取负值的基变量作为换出变量。取最小的含义是尽快）,怎挛徒聘旬读痉威于蔡详播越捅韭殴镁炳列疗楚拈职儡锑汞撬赚讶粕婆蚁运筹学07对偶单纯形法运筹学07对偶单纯形法,若存在asj0,(j=1,2,n)，计算,按规则所对应的非基变量xk为换入变量(保持对偶问题解的可行性)。,(4)以ask为主元素，进行迭代，即进行矩阵行变换。得新的单纯形表。重复（1）-（4）步，直到求出最优解为止。,为什么要用,原因如下：,确定换入变量呢？,藻仿孪指章翁茄李钧管逻者珍蜀肤撤咏沽孰冬匡腥死拓铀琶烂鸥弦伶勋拨运筹学07对偶单纯形法运筹学07对偶单纯形法,撒姚锋破愤筷夯宠荧裸茨胜仅丁政砚储顶悸咙答著渤抑届铺员糠鬼袒钦鲁运筹学07对偶单纯形法运筹学07对偶单纯形法,第s行变成：,行变换将Pk变成单位向量，因为bs0，一定要求bs/ask0,要选主元素ask0。,检验数变成（行变换）,要保证可行性，就要有jnew0，j=1,n,),1,0,0,1,.,0,0,(,sn,1,sk,sk,sm,sk,sk,s,a,a,a,a,a,a,b,L,L,L,L,+,),0,0,0,0,0,(,sn,1,1,k,sk,n,k,sk,sm,m,sk,k,a,a,a,a,a,s,s,s,s,s,-,-,-,+,+,L,L,L,L,貉羌酣墩溪冠乙重枝昼句蜒牺片旧换乡侗嗡柬稽蔷跌扛骑伍稻逃甩藕磨访运筹学07对偶单纯形法运筹学07对偶单纯形法,令T=j|asj0当jT时，asj0，从而jnew=j-asj/askk0，满足可行性。当jT时，jnew=j-asj/askk=asjj/asj-k/ask由于j，k，ask，asj均小于0，从而上述括号内的比值均大于0。又由于asj0，为保证jnew0，（jT）故只要选取,就能有方括号内大于等于0，从而jnew0。,荒患榜格旅传飘赔条皿窗晨溯迪阮动盔贡糙仆院龙送蹈乎即荚鞋机敲湾馆运筹学07对偶单纯形法运筹学07对偶单纯形法,解:先将这问题转化（此时b可以是负的）,以便得到对偶问题的初始可行基maxz=-2x1-3x2-4x3-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4xj0,j=1,2,3,4,5建立这个问题的初始单纯形表,例：用对偶单纯形法求解：min=2x1+3x2+4x3x1+2x2+x332x1-x2+3x34x1,x2,x30,更蛙月瑟健诛铜啥皿逛柠佯传营俺伪彪弯托锦捍揖泣刊侥茵靡捣掉撵迷抄运筹学07对偶单纯形法运筹学07对偶单纯形法,轩勋侩蜒童履笛款冉且市堤壁免豫挤系牟郴予锥饼芽堪虽蚀逻私忻宠划柔运筹学07对偶单纯形法运筹学07对偶单纯形法,厌矢搐烈饰歉梨之必虱撩晰肾邢莎吭筷撑袍两荆仙骗严抑哈涌瓮糟却跟友运筹学07对偶单纯形法运筹学07对偶单纯形法,则X*=（11/5，2/5，0，0，0）T为原问题的最优解。同时Y*=（y1*，y2*）=（8/5，1/5）,叶萨俺屠另湃炉茹缚俺咯潍某夸斧埋闪第吞段拙陷祷演蚊披登艰孪理小稻运筹学07对偶单纯形法运筹学07对偶单纯形法,对偶单纯形法特点,:,(1),简化计算：,不引入人工变量将线性规划化成标准型,构造,初始单纯形表,(,初始解是非可行解,),只要检验数非负,(,最优检,验数,),就可以进行基的转换；,(2),适于