线性规划解的各种情形.ppt

《线性规划解的各种情形.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四節線性規劃解的各種情形在第二章第三節圖解法時介紹線性規劃的解有多種情況，本節要探討如何由單形表中辨認之。例5：(多重最佳解，第二章例2)Maxz=x1+2x2s.t.x1+2x2≦10x1+x2≧1x2≦4x1≧0，x2≧0对辣笆燥忘僧枝滤害肿霞距诽此捧冤唬座埃绰遁汲卑蔚洲溉玻买锋籽教伙线性规划解的各种情形线性规划解的各种情形將問題寫成標準形並加入人工變數Maxz=x1+2x2+0s1+0s2－MA2+0s3s.t.x1+2x2+s1=10x1+x2-s2+A2=1x2+s3=4xj≧0，j=1,2.si≧0

2、，i=1,2,3.A2≧0灿淫餐练遮拉桩桑挑孽宋昂骗谢敝般疚笛柬锻更绿壤婴袋咽峙地淖盔石纺线性规划解的各种情形线性规划解的各种情形cj1200-M0cBxBx1x2s1s2A2s3bibi/aij0s1-1012-20842x2110-1101負數不考慮0s3-1001-1133zj220-2202cj-zj-1002-2-M00s1121000105-MA2110-110110s301000144zj-M-M0M-M0-Mcj-zj1+M2+M0-M00倾蜗爆挑停虽罢识归锭椭忘皆揍恋效惟姻破褒葫跳倘弃瞻缩赚散朱

3、段待乱线性规划解的各种情形线性规划解的各种情形cj1200-M0cBxBx1x2s1s2A2s3bibi/aij1x110100-22負數不考慮2x2010001440s20011-1-15負數不考慮zj12100010cj-zj00-10-M0≤0(已最佳解)0s110100-2222x201000140s2-1001-113負數不考慮zj0200028cj-zj1000-M-2岗征随署尾须翼忽芝瞎啮齿琉砧寡夜貌酞棉翰灭店拣懂欧魔烦准慕灭霄雀线性规划解的各种情形线性规划解的各种情形cj1200-M0cBxBx

4、1x2s1s2A2s3bibi/aij1x110100-22負數不考慮x2010001440s20011-1-15負數不考慮zj12100010cj-zj00-10-M0≤0(最佳解)第四表第五表1x11210001020s301000140s20111-109負數不考慮zj12100010cj-zj00-10-M0≤0(最佳解)皆坚窗量馅吾辖劫遂羹半埠菲前镀控刽妈磐蹦谐蛔辆诺最二粟褂氓你呛灯线性规划解的各种情形线性规划解的各种情形由第四表可以發現所有的cj-zj≦0最佳解已得到，其解為(x1，x2，s1，s2

5、，A2，s3)=(2，4，0，5，0，0)Maxz=10。第五表亦是最佳解，其解為(x1，x2，s1，s2，A2，s3)=(10，0，0，9，0，4)Maxz=10。雖然xj值並完全不相同，但目標函數值z=10是一樣的，由第五表中亦可引進s1，其z值也為10，因此本例題有多重解。那麼如何辨認是否為多重最佳贡迈阎驳物讽南羊颐方蛊在慎晃掷嫌搀焦臆厩轩桂辽包杠训仇讹猴瑚回荷线性规划解的各种情形线性规划解的各种情形解呢？我們是由{cj－zj}所在的列來判斷，先前曾提及基礎變數所對應的cj-zj為0，在第四表中，x1,x2

6、和s3是基礎變數，其對應的c1-z1=c2-z2=c4-z4=0，我們也發現到s3的c6-z6=0引進為基礎變數的話，對目標函數值的邊際貢獻為0，也就是對目標函數沒有影響，所以將s3引進成基礎變數，其目標函數值亦為z=10，將第四表、第五表與第二章圖2-5對照，完全一樣。第四表(x1,x2)=(2,4)第二章圖2-5,D(2,4)第五表(x1,x2)=(10,0)第二章圖2-5,E(10,0)鞭诬蹲胺族媒顶返咏焕弥麓脱祝舅档遂虚逝眼韶菇攫实胜包槛胀氛攒驱矣线性规划解的各种情形线性规划解的各种情形多重最佳解如何辨認

7、呢？簡言之，從{cj-zj}所在列來判斷，如果基礎變數有K個，{cj-zj}所在列的0超過K個，則表示此題就有多重最佳解。如本例題有3個基礎變數，而在第四表中，{cj-zj}所在列有4個0；而在第五表中，{cj-zj}所在列有4個0，故本題為多重解。珊让骨判眠迢蒋音议纠腊蚤依谦贸鞭提狮讣址醚密福单挞享扔次抉闽焉凹线性规划解的各种情形线性规划解的各种情形例6：(無限值解，第二章例3)Maxz=3x1+4x2s.t.x1+x2≧4x1-2x2≦5x1≧0，x2≧0將問題寫成標準型並引進人工變數Maxz=3x1+4x2

8、+0s1-MA1+0s2s.t.x1+x2-s1+A1=4x1-2x2+s2=5x1，x2，s1，s2，A1≧0丧忿瞄收犀仰驶起赣劳来辈撇兔笑捆某鞍淹气镜拔舜效嫁碳霸由啊辰奔捂线性规划解的各种情形线性规划解的各种情形cj340-M0cBxBx1x2s1A2s2bibi/aij-MA111-110440s21-20015負數不考慮zj-M-MM-M0-4Mcj-zj3+M4