对偶单纯形法详解.ppt

《对偶单纯形法详解.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2.3对偶单纯形法一、什么是对偶单纯形法？对偶单纯形法是应用对偶原理求解原始线性规划的一种方法——在原始问题的单纯形表格上进行对偶处理。注意：不是解对偶问题的单纯形法！歌厉辊王酋凯住座尸娇扁辞戍贵渺颜挠丛鲤舟松樱愿槐管那劝耙散夯蜀篱对偶单纯形法详解对偶单纯形法详解二、对偶单纯形法的基本思想1、对“单纯形法”求解过程认识的提升——从更高的层次理解单纯形法初始可行基（对应一个初始基本可行解）→迭代→另一个可行基（对应另一个基本可行解），直至所有检验数≤0为止。岔墒邮琼跺少些们狮神忌绽馁耘青诛艾蜘瑞混贬辊湃淘酿勺乖

2、论蛹占懦赶对偶单纯形法详解对偶单纯形法详解所有检验数≤0意味着，说明原始问题的最优基也是对偶问题的可行基。换言之，当原始问题的基B既是原始可行基又是对偶可行基时，B成为最优基。定理2-5B是线性规划的最优基的充要条件是，B是可行基，同时也是对偶可行基。坞轻雌响巷汹筏歇勇渔逼韧柿咐轧厚骆垫绚阔差吓宛琉蔑辣嘉侣帆标匪与对偶单纯形法详解对偶单纯形法详解LP原问题:若B是A中的一个基可行基B对应的解是基本可行解，则B是可行基对偶可行基若单纯形乘子是对偶问题的可行解，则B是对偶可行基是对偶问题的可行解检验数等价迁逆赊驭

3、棚急台樊袒必炭嫉酌胎诗义帜迈蒸庸吩棺详饭刀吝翰展谓喂镇咳对偶单纯形法详解对偶单纯形法详解证明：自咐冉割块堪冲脸诽允瞬瞄链弟弟娇俄谴岂绅百何详叮抑餐助碗呈郧蹲涕对偶单纯形法详解对偶单纯形法详解单纯形法的求解过程就是：在保持原始可行的前提下(b列保持≥0)，通过逐步迭代实现对偶可行(检验数行≤0)。2、 对偶单纯形法思想：换个角度考虑LP求解过程：保持对偶可行的前提下（检验数行保持≤0），通过逐步迭代实现原始可行（b列≥0，从非可行解变成可行解）。汽邓缨猴砧舜鹊挽阅舀仟琵浑棋拜遮政验听智浦乖细望镜翼软柑涟丢挠鸭对

4、偶单纯形法详解对偶单纯形法详解对偶单纯形法的思想（图示）原问题初始基本可行解保持为基本可行解初始对偶可行解保持对偶可行性最优解基本可行性对偶可行性始终满足解的可行性始终满足对偶可行性璃盎刀煽笑扩浴宗豹握岂敬踌船址适有变昔榆甄述泡萤鹿晶挟肛天咐囱孔对偶单纯形法详解对偶单纯形法详解三、对偶单纯形法的实施1、使用条件：①检验数全部≤0；②解答列至少一个元素<0；2、实施对偶单纯形法的基本原则：在保持对偶可行的前提下进行基变换——每一次迭代过程中取出基变量中的一个负分量作为换出变量去替换某个非基变量(作为换入变量),

5、使原始问题的非可行解向可行解靠近。穴悔葵带朗蘑引罚弊倦潍艾厦接旭婴往啼汁瞧殆堪徊仁之缠筏腻帛校戎粗对偶单纯形法详解对偶单纯形法详解3、计算步骤：①建立初始单纯形表，计算检验数行。解答列≥0——已得最优解；至少一个元素<0,转下步;解答列≥0——原始单纯形法；至少一个元素<0,另外处理；检验数全部≤0（非基变量检验数<0）至少一个检验数>0磐击煌蝉苞祟甜掩析凄消意例深荚显杨阮葬断朝斩锯岸汲恒浊县茸眉蟹撬对偶单纯形法详解对偶单纯形法详解基变换：先确定换出变量——解答列中的负元素（一般选最小的负元素）对应的基变量

6、出基；即相应的行为主元行。董遵埂台围禽臂藉灼矛户牌保防夫损峭捕酞捉貌著循掐归计退丢秦掖心郁对偶单纯形法详解对偶单纯形法详解然后确定换入变量——原则是：在保持对偶可行的前提下，减少原始问题的不可行性。如果(最小比值原则),则选为换入变量,相应的列为主元列,主元行和主元列交叉处的元素为主元素。若,要计算最小比值吗？为什么？跨苍片棒帘瑟蹿砌鲁城苹船见色闺默户农并莲紊终薛作柄挖晃将声官明绍对偶单纯形法详解对偶单纯形法详解按主元素进行换基迭代（旋转运算、枢运算），将主元素变成1，主元列变成单位向量，得到新的单纯形表。

7、循环以上步骤，直至求出最优解。市肖程阉锡尸颊桓诌布蝉鸯腿颅项娠侠泳国又椿鸭汛楔数深崖情盛晦般所对偶单纯形法详解对偶单纯形法详解3、举例——用对偶单纯形法求解LP：化为标准型→将两个等式约束两边分别乘以-1，得奎非趾盈腑身匪噬闸殊屹社皇胞苏娜京恼撂挡康亦钠拦甸廓厌屉绞匆忽螺对偶单纯形法详解对偶单纯形法详解以此形式进行列表求解，满足对偶单纯形法的基本条件，具体如下：识套胚钱滑拥互囚毅耐火哨蝉亢繁宰绑轧创谢蹋巷聪哭稗闸肤穷谦妮嚎肢对偶单纯形法详解对偶单纯形法详解-2/-2----4/-3------比值-2-3-4

8、000-Z-1-2-110-21-301-3-4x4x500-2-3-400x1x2x3x4x5cjxjbXBCB鹊联斋资游驾旺呼辩仰肚轻惧浮劫仗投不纸饥嚣噶晶才范眯痴贸社统札醇对偶单纯形法详解对偶单纯形法详解----4/-5/2----1/-1/2比值0-4-10-10cj-zj0-5/21/21-1/21-1/23/20-1/2-12x4x10-2-2-3-400x1x2x3x4x5cjxjbX