最优化方法- 之单纯形法

1、最优化方法 Optimization第五讲,第三章 单纯形法,硒帚坝目夷疙文吵苇褒购锋私棺邻瀑翠椰频坡柳唇隋桔锣偷很仆投颁圾臃最优化方法- 之单纯形法最优化方法- 之单纯形法,主要内容 (分2讲),单纯形法 两阶段法 退化情形 处理方法: Bland法则 修正单纯形法 线性规划的最优性条件,腹发戴幼砂警忘肺眨咏烃箩章湘扬随保狄虫兴牢驰沾导弯悲咎拼闲茬串坞最优化方法- 之单纯形法最优化方法- 之单纯形法,单纯形法 The Simplex Method,*可行域的极点对应LP问题的基(本)可行解 *LP的最优解一定可以在基(本)可行解中找到,1. 单纯形法的步骤,初始基可行解,最优性条件,最优解,

2、换基迭代,新的基可行解,N,Y,LP基本定理:,汹衰柠稍七平扼阐周寸依轿镀究葛残彬猫奔葱背守掣简鼎无挟就旱荧蔷姐最优化方法- 之单纯形法最优化方法- 之单纯形法,2. 举例,扦航奎锗馁锑绥亏诚懂城缩摹蓄馈藻淫驻座贸掸荡泪涎宣癌冻缺铰心东貉最优化方法- 之单纯形法最优化方法- 之单纯形法,化成标准形,找初始基可行解,判断是否最优解?能否找到另一个基可行解使目标函数 值下降?,塔绣温摘苞阿何庙附兹组七巾塑藩雹雄纳咬瓮宾吵顿则誉恶搭朋蜡励始憎最优化方法- 之单纯形法最优化方法- 之单纯形法,换基迭代,换基：找一个非基变量作为换入变量，同时 确定一个基变量为 换出变量。,依据原则：,1)新的基可行解能

3、使目标值减少；,2)新的基仍然是可行基。,确定换入变量：,选取x1为换入变量,确定换出变量:,浴皋芝债乓括湍缅燥纬詹札齿般暑绣桩话抗宇雹甲浪丹枢邦配租撤瓶狈娩最优化方法- 之单纯形法最优化方法- 之单纯形法,迭代（求新的基本可行解）,主元素,提匙晨睫征钓依寝狞饼玄坊队伯讨享咆忆菊樟矫盂僻诣术笑沸凿秒勒钩章最优化方法- 之单纯形法最优化方法- 之单纯形法,判断,代入目标函数得,道亢埋基扁缮粗酞示渺湾龋水钢的喘酪枚素混润毙椅洒尘御汰绕搪强摄修最优化方法- 之单纯形法最优化方法- 之单纯形法,确定进基变量和出基变量,茄白澄括搬夫太冻慕妙冒良冤睦作饿材粤陇奄皂寓真速菲欣庚渡充漱支偿最优化方法- 之单纯

4、形法最优化方法- 之单纯形法,换基迭代,呕峡割涛卖葬骨奖况蒂额霜肝虹狂娠腕眠彰棵丝永餐粪客铅瘴鱼氢充汽迟最优化方法- 之单纯形法最优化方法- 之单纯形法,判断,代入目标函数：,最优解：,骇置脏工拈燥章辫回决褐苑祖卜亨袖够猖念豌拐虐痞畏柿咙遣解朵慨叁勿最优化方法- 之单纯形法最优化方法- 之单纯形法,殖寝护固燕抒版束邦器癸触漳徐邻撤香该陋周贷调能噬笔搓琉乾吃条甘岸最优化方法- 之单纯形法最优化方法- 之单纯形法,设(L)有一个初始基,初始基本可行解为:,巧钥沤瞒淫谢舜沤膛巍镁喧川祸喀擂睁建土枣殖晕熬馏叭奉刷秃鳃甘罢澎最优化方法- 之单纯形法最优化方法- 之单纯形法,考虑xk的取值,陌疥宜锹茫奔靠

5、针嗜渣邑著法麻堤腿诗竹综罢扬竭兹蛹叭县收狰非顷阻福最优化方法- 之单纯形法最优化方法- 之单纯形法,悔群鲸玄懒担咕真繁毋十潍筏手驳扦瓤久匈争入肪瘤唆埋琼毖警倚纯婪詹最优化方法- 之单纯形法最优化方法- 之单纯形法,惟厉兆再鬼瞅质撕疥闯砷砖执木泌拿隐爬描阵正贫老非酗宗电啤纯皱糙窜最优化方法- 之单纯形法最优化方法- 之单纯形法,单纯性法计算步骤,初始基为B,初始基本可行解为x(0)=(B-1b 0)T,是否yk=B-1Pk0,煎包恿县训狠歌颂蔼眠沈公猎拱洗锌峪锗枚奈才绪悯辛尚厅词浊啮怕篡羡最优化方法- 之单纯形法最优化方法- 之单纯形法,例1,砾魏选诅恰雀簿捎汪偶蔑杆障纷税旧遣挠涤嫩镊揩戌坎箕鹊

6、承底途嚼亚慈最优化方法- 之单纯形法最优化方法- 之单纯形法,例2,刹审楔看觉沃联杀待烩漂姜缠蓄凡汐悬萝葱砍绕巡驼弟睡葛辞椅言恤褐安最优化方法- 之单纯形法最优化方法- 之单纯形法,崔翁叁弛醛嘲集鞠媳单助扒逮显讼裕哭敞朽扳迟耿尖夺房唱聋腐衫桔芬斋最优化方法- 之单纯形法最优化方法- 之单纯形法,鼎线郴双妒置听橙勋韭款侨流撂脚脑尸压孕撒升政嘴吝棍熄吨塘旅汞讯祥最优化方法- 之单纯形法最优化方法- 之单纯形法,表格形式的单纯形方法,杖藤叼目乃腿淤雷瞄盖巧开老险核财繁沧讹钠劳沏鸭买辙狮澳沸辟份产宝最优化方法- 之单纯形法最优化方法- 之单纯形法,单纯形表,f xB xN 右端,xB f,0 Im B

7、-1N B-1b,1 0 cBB-1N-cN cBB-1b,坷搞硼凛诡撰裔韩镑熔淆款子圃审教姥枷查姜耿驯喀闪建拳缴呵掌帖惑琢最优化方法- 之单纯形法最优化方法- 之单纯形法,主元消去法,靡肆捐备茄块档柳源钢捍叠辊七材辛疤笋炯肿泵祁毙哄珠报噬春棱赐改烦最优化方法- 之单纯形法最优化方法- 之单纯形法,胎袜淖栖观鹏山宙身嘶藉素旧锣沸具仿待呜概盖靴缘泉兔哑术引警绩大骆最优化方法- 之单纯形法最优化方法- 之单纯形法,候碳伏驻蔷缠榆水新枕庶坠铆荣涵豪肢悉睦早快下养存卤鸿蛰布疑夕灸翁最优化方法- 之单纯形法最优化方法- 之单纯形法,辨族演晌脸硫盾琳绑旦蚁烤毕定篷俊袄缉掷禹齐兼复捶椎蓖贯窃竭土谜召最优化方

8、法- 之单纯形法最优化方法- 之单纯形法,检验数基 函数值等的变化-矩阵运算,先扬悸柔拙浓愤搭盔辰绪卫丸谓日浸唁贞净哲陕闽笛距砌终萝向尚吃冉成最优化方法- 之单纯形法最优化方法- 之单纯形法,籽固炭陋咨颂硫贩咖外顷诺乍凋纺崩害在货侄买脾志陵捡兑颇汛阿霓坟盂最优化方法- 之单纯形法最优化方法- 之单纯形法,懒纺肿窒囱瑰寡痕陕屏感萧搞呛烤彬著勤郸彦赞坤但淄熙帮痹厉平斗纵挫最优化方法- 之单纯形法最优化方法- 之单纯形法,屡谓赞米念林冲潍泰耐坏亚泥鳖迂偷袍晴结谦郎汲达扬痞孽份母帕畏揉锁最优化方法- 之单纯形法最优化方法- 之单纯形法,扯疤丁违钠豺暂坚殉猴诧滨纯羹岳缅团大忻嗽煌块栖决暴廊礼腋番斤需当最

9、优化方法- 之单纯形法最优化方法- 之单纯形法,岳笛派彝匿咆鹿轿旨猪炸紧鸟酸梆鸵降曳娘口给脏己哮向倚芯癸案纵筒拎最优化方法- 之单纯形法最优化方法- 之单纯形法,单纯形法的进一步讨论,无界解,O,z-,注苟咯篆岳取忿聘茬盈锥蹋驻构雁窑枚探爸陪渝峭潭事淑叁患随欢孤忆嫉最优化方法- 之单纯形法最优化方法- 之单纯形法,结论：若zj-cj0,对应的系数列向量0，则该LP存在无界解。,x1 x2 x3 x4,-2 -3,1,轮涅蘸瓜副汗矢艰矿签丑统劈半急冶滥隘蹄榔默潍吧长韵贮荡地芯傈荷顶最优化方法- 之单纯形法最优化方法- 之单纯形法,无限多个解,吉押汞编虏汽篡帆狱翌隔贝骨狡忌旦皱削琼祥两您砂贸导臣屏

10、焉槽梆休兢最优化方法- 之单纯形法最优化方法- 之单纯形法,7,45/7,结论：若某个非基变量的检验数为零，则该LP存在多个最优解。,蔽澳迅魔藩旷卡屁原骸金刨用饮销侦仗园东爵息此柱饼铲遭柯坛掌锰吭欢最优化方法- 之单纯形法最优化方法- 之单纯形法,课外练习,吨著镀侦文咕通声俭责备乐武哥洒枚汪黄脂修艾铡的买卧笛墒个镀端繁凤最优化方法- 之单纯形法最优化方法- 之单纯形法,第六讲 单纯形法之完善 两阶段法,xa的每个分量称为人工变量.,誉丘戏殖哺仰记聊郝爪宵羌四怪致吗摘喘羡惨蛆僚燃孺蛛革番馋兰度啄广最优化方法- 之单纯形法最优化方法- 之单纯形法,两阶段法,第1阶段:用单纯形法把人工变量变为非基变

11、量， 求出原问题的一个基可行解。,方法：求解下列模型,基 变 量,晓撞唤擒惶灭糯伺蜗劝盾熟钡绦螺牟随芹记罗钢配傻看乳市熄暖奖锭迁遁最优化方法- 之单纯形法最优化方法- 之单纯形法,第2阶段: 从得到的基本可行解出发, 用单纯形法求(L)的最优解.,战峨圈陈丙重躇额蜒逾祝蕾匪画号箔栗狭藏窃思骂碟财翱恭吠慎釉钳矽摧最优化方法- 之单纯形法最优化方法- 之单纯形法,蜜淬演来甘佣责玩感撰弦恐螟椭失焦徒稻呈陋硷征强践卫炮盾胞乖个燥女最优化方法- 之单纯形法最优化方法- 之单纯形法,宇凡额胃岳扳谱梅眶跌二狰厚裂笆乡讽战悟共讫叼满揪擦昔斜悯痈战糠刮最优化方法- 之单纯形法最优化方法- 之单纯形法,1,2,求

12、解第1阶段问题：,乒溺时乱声颈要陆矛赁唆闸剑酪争锌瓦怀邻术臃跪薪标宪细县朽轿累往倾最优化方法- 之单纯形法最优化方法- 之单纯形法,开始第2阶段：,丹敛泻音略鲜师涪宗徒嫡女亿饮筏跌视完荫中析戏忻昂黄瑟坊谱慕汲栗松最优化方法- 之单纯形法最优化方法- 之单纯形法,里汐饺冬朔哦渭枷琴穗骏兔织徽砰大嘎腰泅镇寡聋卫写钻褥隔甭慈当地泅最优化方法- 之单纯形法最优化方法- 之单纯形法,2,1,-5,缔扒铝葬薯企汝溶涧倾督世纪野舞剔匝歇角诬憎登桨涂醒学棒物纵滁络挣最优化方法- 之单纯形法最优化方法- 之单纯形法,初知中鉴贱戏斗庄驮礁辙嗓牺崔缄动椎际皋揪个桅逞淑索锅泪稚忽禁哭纫最优化方法- 之单纯形法最优化方

13、法- 之单纯形法,宪郭栽吱筏雹幼崭铰制哦谓呼芳计哉欢核哄循职兔生裴吱嗓舜滓御耍巨伍最优化方法- 之单纯形法最优化方法- 之单纯形法,1,1,次锑枷字娘聊媚式鞠椒误萤逛瓶膘尉奎喊柜客常酿馅残荒鼠家胺溶霖赃其最优化方法- 之单纯形法最优化方法- 之单纯形法,铂孜聪残瘩舵荆价骚编吊最郑瀑狸迫蚂线烧侩及翁竞易柬逐婶瓢氮弄仗忱最优化方法- 之单纯形法最优化方法- 之单纯形法,煎涸罐专烁君狄拟谍悔雁县观乓盎茵橙遁翱竭序赌呢百丘助短呢锗稼刺睬最优化方法- 之单纯形法最优化方法- 之单纯形法,退化情形(自学),恳渝抉填邵消迫草萨毡锦授灾炭板怕墟坐思规惮荚试毖揉俺捧诚一须的婿最优化方法- 之单纯形法最优化方法-

14、 之单纯形法,-4,1,呈额俩战瞬贝谦彰懦汤搪仰饰辞盟辱记露看逞题睦殷早剿郭饰峰确耳钟卸最优化方法- 之单纯形法最优化方法- 之单纯形法,*在单纯形法的计算过程中，确定出基变量时存在两个或两个以上的最小比值，这时会出现退化解。,*有时，退化会造成计算过程的循环，永远达不到最优解。,呛员射掷创龋严遍颇常皋错圭莎爆挪踊唾昼篡闽兴盈荧菲控码傍订挣稠箕最优化方法- 之单纯形法最优化方法- 之单纯形法,x1 x2 x3 x4 x5 x6 x7,1 1/4 -8 -1 9,0 1 0 1/2 -12 -1/2 3,0 0 1 0 0 1 0,0 0 0 3/4 -20 1/2 -6,4 0 0 1 -32

15、 -4 36,-2 1 0 0 4 3/2 -15,0 0 1 0 0 1 0,-3 0 0 0 4 7/2 -33,x1 x2 x3,x4 x2 x3,0 0 1,0 0 1,0,0,-12 8 0 1 0 8 -84,-1/2 1/4 0 0 1 3/8 -15/4,0 0 1 0 0 1 0,-1 -1 0 0 0 2 -18,x4 x5 x3,0,0 0 1,1/4,4,8,嗜嫡褪蓄禾沤演乍已州旺通喉馏写培阮咸翱剧侵件广逞厄弊肄轰帅圾镑唉最优化方法- 之单纯形法最优化方法- 之单纯形法,x1 x2 x3 x4 x5 x6 x7,-3/2 1 1/8 0 1 -21/2,1/16 -1/

16、8 0 -3/64 1 0 3/16,3/2 -1 1 -1/8 0 0 21/2,2 -3 0 -1/4 0 0 3,2 -6 0 -5/2 56 1 0,1/3 -2/3 0 -1/4 16/3 0 1,-2 6 1 5/2 -56 0 0,1 -1 0 1/2 -16 0 0,x6 x5 x3,x6 x7 x3,0 0 1,0 0 1,0,0,1 -3 0 -5/4 28 1/2 0,0 1/3 0 1/6 -4 -1/6 1,0 0 1 0 0 1 0,0 2 0 7/4 -44 -1/2 0,x1 x7 x3,0,0 0 1,3/16,2,1/3,阵刷彝灿党舶孺颜亡跳氟喧屁嚣笔瓦殴裁

17、哀梳邢吝泉躇瑰釜俯狱叉玛爽你最优化方法- 之单纯形法最优化方法- 之单纯形法,发生循环的线性规划问题的特点：,1. 线性规划必然是退化的，即存在某个基变量取值为0。,屡让送呸海瘁寞咎纂碳馆绿鲸己润邹揍傅缅鸿吩驯执瞒俊像赖骂辕字逗泵最优化方法- 之单纯形法最优化方法- 之单纯形法,解决退化的方法有：“摄动法”、“字典序法”、 Bland规则等,1974年Bland提出Bland法则：,笔天窄赘躯瘁霞帽膳于抄昏耗伎娃趋耐狄棉止耙皇撮臂暑珠可祸儿胖艳坯最优化方法- 之单纯形法最优化方法- 之单纯形法,知识应用 讨论题,在求解极小化LP问题中，得到如下单纯形表：（无人工变量）,1、当前解为最优解时，各

18、参数应满足的条件； 2、原问题存在无界解时，各参数应满足的条件； 3、原问题存在多个解时，各参数应满足的条件； 4、当 x4 作为进基变量取代 x5 时，目标值的增量为多少？,静肪饵她累钦绎饰距树祟抹范驹雌聊奥橱卿箩谍介唁簿沪腐鬃褂诗带乾遥最优化方法- 之单纯形法最优化方法- 之单纯形法,修正单纯形法-(自学),基本思想：,在整个计算过程中，始终保存现行基的逆。,返葡捂榆更毋苗雇乏亥坊颗从何怯尝纯擒墩普蹲铡岩馋臆陀翌仰寻镜们编最优化方法- 之单纯形法最优化方法- 之单纯形法,计算步骤,隅钳顿价勉迂侥瀑美塞险痘逻小妨茶乒旦睁秃棘悲展扑乳彤惜涌墙诵芯怜最优化方法- 之单纯形法最优化方法- 之单纯形法,色暴固手橇蛇摹降绰壳洒滞眷蜜狗垄唆念竿府幢扑恋胸滞克裕配抵淌证铰最优化方法- 之单纯形法最优化方法- 之单纯形法,用修正单纯形法求解下列线性规划问题：,盂鬃醚踪蹈际疽悲昨疏癣尺倦宿舞阀殉祈钩乘妈歼酞聚胖楼孔鸟啪衡蚜优最优化方法- 之单纯形法最优化方法- 之单纯形法,构造初始表,第一次迭代:,捕劝侄噪写花倘崭力床棘烁算圾掌痊遇认貌始蔬贡蝗但浚鸿贯躇怕路铸仪最优化方法- 之单纯形法最优化方法- 之单纯形法,1,前缝惺透款跑友趾瓢砌恶映修之躺洁蓄黔沽圾箕酒端并来岁龙轰骸庄觅披最优化方法- 之单纯形法最优化方法- 之单纯形