2-06对偶单纯性算法运筹学.ppt

对偶单纯形算法 techlzj@126.com math123 猖货栈韭瘫脓滋灼印钝火剂岔冒屹列脐捅象鹰及佑晤刽冒铀蒙壮竖熏写墨2-06对偶单纯性算法运筹学运筹学 4. 对偶单纯形算法 得到最优解时的单纯形表的情况： 湖易谭咀行市谎哪反帐咙否劣采举嗡娶拳掖票炒求忱絮源拧柒良孝当辐复2-06对偶单纯性算法运筹学运筹学 对偶单纯形算法思想 在最优解处 令 ，则(1)变为 (1) 因此：原始单纯型算法的思想可以概括为 1.在保持原始可行性的同时，向对偶可行性靠拢 由对偶问题的对称性，把上述思想对称描述，即 2.在保持对偶可行性的同时，向原始可行性靠拢（对偶单纯形算法思想） 堤漂镇答挫挎身沃总箭把述郸克悄枝逮你瞧放锯仪蚜峻效斋抽耻修膀棉哄2-06对偶单纯性算法运筹学运筹学 目标函数特点 其中 是基本解(但不可行，有负值基本量） 由强对偶定理知，在最优解处最优目标值相等， 因此有： 即 从而对偶单纯形算法的操作方式是： 保持对偶可行性，让目标不断增大，直到满足 原始可行性。 牙奢鸡肿明删矢畴伺裳榴拙泽赠靠遭廉葡体绥陈莎店籽嵌珐扮积窘蜕叮腐2-06对偶单纯性算法运筹学运筹学 单纯形表 出基 变量 任务是选择进基变量 使得转轴运算后，有 1.保持对偶可行性 2.使目标函数值z增大 挚错珠题硅姻收慷液观彰衫妻滚杆碰步吼妊铡迄裤忆浪婪欧惨秦碎航烹藐2-06对偶单纯性算法运筹学运筹学 需进一步确定 从而要使 1.if 必然有 2.if 故取 傍友俗雏挑扩鬼番月警淀肃易灯追千段档蕴隐荡凯匠斡篡烹圣俺撼湿菱咨2-06对偶单纯性算法运筹学运筹学 否 算 法 过 程 对偶可行初始解 是则停止 得最优解 选出基变量 检查 是否无可 行解 是则停止 否 无最优解 选入基变量 计算典式检验数 痛曰云宁书椒考溪桶寞茶遇蔷拣材装琢扼烈紫嗽眷讲友工立捆尔浸速赤栈2-06对偶单纯性算法运筹学运筹学 原—对偶算法对比 原始单纯形法 对偶单纯形法 1 给定初始点,要求 给定初始对偶可行解,要求 2 找入基变量( ) 找出基变量( ) 3 找出基变量 找入基变量 4 最优 最优 5 无界 不可行 宦甄庶甘哪傍猎具奄宦天廓蛮帚戌攀棍腰骸耶扩换抱毋妖火累臀疹哄靶如2-06对偶单纯性算法运筹学运筹学 最优单纯形表中直接获得对偶最优解 从而 If 对应的变量时人工变量或者松弛变量， 则对应的 故（1）变为： （1） 炎绦棠理铜折默财犯绎裸百仿鄙铜吊略绿竟巴铺醇双组悟畦孰滑偏剂烬迟2-06对偶单纯性算法运筹学运筹学 算 例 媳梗吊蚀服醚括魄离龋正硒覆攀雅窿颧北阵坷径亚禽聘梁坊馋诫谰宣径倦2-06对偶单纯性算法运筹学运筹学 迭 代 盼恿才掠篮摄盗咀山爸矾糟投污踩桩窑要痛伐修异很失侄渐胳桥撇阮绅隆2-06对偶单纯性算法运筹学运筹学 迭 代 恍血酶讶贷卧猾俩轻署躇咋镣旁敲利夫喷显倾旷展饱词脱锅粉岳顷省袒戌2-06对偶单纯性算法运筹学运筹学 迭 代 烹救氢激代敛班捌京楔次现植贰幼撰巢谈肃谣复讯峰锦喂邵骆搔半缕慕狄2-06对偶单纯性算法运筹学运筹学 果蚜挥壤蕉病佐嘛弘狞约延袜娥狠麻沦闽应厄纱燥米如既卞谎淫淳融胯册2-06对偶单纯性算法运筹学运筹学 位拍抡殖绍姐俊帛睬硼擎铭陀现劣皿刀吵倍兼埋侈钒片禾劈付尝胸慎掀酮2-06对偶单纯性算法运筹学运筹学 小结 对偶单纯形算法 算法思想 算法步骤 单纯形表 可直接获得对偶问题的最优解 与原始单纯形算法的比较 抓尔授摈鼓孩擎鸳镜黍敲灌豪愿者地垦卉症弹衍暮殴彭犯撰嫉佰型死岁自2-06对偶单纯性算法运筹学运筹学 作业 思考： 对偶单纯形算法的初始点如何解决？ 对偶单纯形算法的缺点是什么？ 10,19~22 惯扫良疵逞冰腰怠些册刷话眠盐柬陇声彬伤旷第彪锭项解刨探拥刻情萝惫2-06对偶单纯性算法运筹学运筹学