シンプレックス法のアツゴリズム

《シンプレックス法のアツゴリズム》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應用文檔-天天文庫。

1、経営科學概論（高井）配布プリントＬＰ…線形計畫法（LinearProgramming）シンプレックス法による、ＬＰの解法について、簡単な資源配分の問題を用いて説明する。問題：２種類の製品Ｐ,Ｑを製造するために、それぞれ２種類の原料Ａ,Ｂを用いる?！　　⊙u品原料ＰＱ使用可能量(1日當たり)Ａ3145Ｂ1240利益65右の表は、製品１単位の生産に要する原材料の量、原材料の１日當たり使用可能量、および、製品１単位當たりの利益を表している?！　∽畲罄妞虻盲毪郡幛摔稀ⅳ嗓韦瑜Γ?0,0)Ａ(15,0)B(10,15)

2、C(0,20)①「②「③「xy図１2変數(shù)の場合は、図による解法が可能　な生産を行えばよいか。解法手順1.問題の定式化：制約條件と目的関數(shù)による表現(xiàn)　　　制約條件：　　目的関數(shù)：手順2.スラック変數(shù)の導入：問題を等式で表わす　　等式表現(xiàn)された　　　制約條件と　　　目的関數(shù)　　※スラック変數(shù)s1,s2は、それぞれ原料A,Bの使い殘し分と捉えておく?！　　』讐鋽?shù)右辺定數(shù)変數(shù)xyスラック変數(shù)s1s2s1453110s2401201Z0-6-500※?１が１つで他は０?である列に対応する変數(shù)を基底変數(shù)、それ以外を非基

3、底変數(shù)と言う。※基底変數(shù)の値は右辺定數(shù)欄に表示。非基底変數(shù)の値はゼロ。手順3.シンプレックス表の作成：基底変數(shù)：s1=45s2=40非基底変數(shù)：x=0y=0↓この段階では、上の図で、原點Ｏ(0,0)を示している。ＮＯ手順4.最適解の探索：(1)最下行に負の値あるか？　　探索終わり　　　　　　　　YES↓探索開始(2)最下行の負の値の中で、絶対値が最大のものがある列をC列とする(3)現(xiàn)在の基底変數(shù)に対応する右辺定數(shù)を、それぞれC列の値で割り、この値が、正で最小のものがある行をＲ行とする(4)第Ｒ行C列をピボット

4、と呼ぶ。C列に対応する非基底変數(shù)を新たな基底変數(shù)にし、Ｒ列に対応する基底変數(shù)を非基底変數(shù)に追い出すよう、シンプレックス表を変換。許される変換は、(a)ある行を、定數(shù)（≠0）倍する(b)ある行に他の行をたす（ひく）変換を完了し、基底変數(shù)を入れ替える2基底変數(shù)右辺定數(shù)変數(shù)xy????変數(shù)s1s21s14531102s24012013Z0-6-5004x1511/31/305s22505/3-1/316Z900-3207x10102/5-1/58y1501-1/53/59Z135007/59/5Step1(1)3行

5、目に負の値あり(2)絶対値最大は-6　　のあるxの列(3)45/3=15,　　40/1=40で　　s1を追い出すことに(4)○をピボットとし、変換　4行目=1行目×1/3　5行目=2行目-4行目　6行目=3行目+4行目×6Step2(1)6行目に負の値あり(2)絶対値最大は-3のあるyの列(3)15/(1/3)=45,　　25/(5/3)=15　でs2を追い出すことに(4)○をピボットとし、変換　8行目=5行目×3/5　7行目=4行目-8行目×1/3　9行目=6行目+8行目×3探索された可能解は、以下のとおり

6、。　最終表で、最適解が示されている。????????表初期表第２表最終表基底変數(shù)s1=45s2=40x=15s2=25x=10y=15非基底変數(shù)x=0y=0s1=0y=0s1=0s2=0目的関數(shù)Z=0Z=90Z=135　　図１上の點　?。骸　　　。希?,0）→A(15,0)→B(10,15)影の価格（限界価値）：　最終表の最終行において、s1の列は7/5、s2の列は9/5となっている。　　　これを、それぞれ原料A,Bの影の価格、あるいは、限界価値と呼ぶ。雙対問題：　扱ってきた左の問題に対し、右のような問題を考

7、える?！　　　　　　　　　　　　　　　　≈鲉栴}　　　　　　　　　　　　　　　　　　　　　　　　　　　雙対問題　　　※非負條件以外について、縦に並んだ係數(shù)を橫に不等號の向きを逆にし、最大化を最小化にしてある。　雙対問題の意味解釈：　この例に関しては、　　　主問題が、「最大利益を上げるために、製品の生産配分を求める」という、工場主の問題であるのに対し、　　　雙対問題は、「工場主からできるだけ安く、全部の原料を買い取る」という、大金持ちの問題と見なせる。　　　ここで、変數(shù)m,nは、それぞれ原料A,Bの単位量當たりの

8、買い取り単価を表す。一般に、次の雙対定理が成り立つので、　大金持ちは、原料A,B買い取り単価を、それぞれm=７/5,n=９/5　として、総額Z=135で買い取ることができる。これは、工場主が原料A,Bを使って生産活動をした結(jié)果、得られるであろう最大利益と一致する?！长卫坞p対問題も２変數(shù)なので、図による解法が可能。確認のため、各自解いてみよう。雙対定理　(1)主問題の最適解における目的関數(shù)の値と、