资源描述：
《シンプレックス法のアツゴリズム》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、経営科学概論（高井）配布プリントＬＰ…線形計画法（LinearProgramming）シンプレックス法による、ＬＰの解法について、簡単な資源配分の問題を用いて説明する。問題：２種類の製品Ｐ,Ｑを製造するために、それぞれ２種類の原料Ａ,Ｂを用いる。 製品原料ＰＱ使用可能量(1日当たり)Ａ3145Ｂ1240利益65右の表は、製品１単位の生産に要する原材料の量、原材料の１日当たり使用可能量、および、製品１単位当たりの利益を表している。 最大利益を得るためには、どのようＯ(0,0)Ａ(15,0)B(10,15)
2、C(0,20)①「②「③「xy図１2変数の場合は、図による解法が可能 な生産を行えばよいか。解法手順1.問題の定式化：制約条件と目的関数による表現 制約条件： 目的関数：手順2.スラック変数の導入：問題を等式で表わす 等式表現された 制約条件と 目的関数 ※スラック変数s1,s2は、それぞれ原料A,Bの使い残し分と捉えておく。 基底変数右辺定数変数xyスラック変数s1s2s1453110s2401201Z0-6-500※｢１が１つで他は０｣である列に対応する変数を基底変数、それ以外を非基
3、底変数と言う。※基底変数の値は右辺定数欄に表示。非基底変数の値はゼロ。手順3.シンプレックス表の作成：基底変数：s1=45s2=40非基底変数：x=0y=0↓この段階では、上の図で、原点Ｏ(0,0)を示している。ＮＯ手順4.最適解の探索：(1)最下行に負の値あるか？ 探索終わり YES↓探索開始(2)最下行の負の値の中で、絶対値が最大のものがある列をC列とする(3)現在の基底変数に対応する右辺定数を、それぞれC列の値で割り、この値が、正で最小のものがある行をＲ行とする(4)第Ｒ行C列をピボット
4、と呼ぶ。C列に対応する非基底変数を新たな基底変数にし、Ｒ列に対応する基底変数を非基底変数に追い出すよう、シンプレックス表を変換。許される変換は、(a)ある行を、定数（≠0）倍する(b)ある行に他の行をたす（ひく）変換を完了し、基底変数を入れ替える2基底変数右辺定数変数xyｽﾗｯｸ変数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、。 最終表で、最適解が示されている。ｼﾝﾌﾟﾚｯｸｽ表初期表第２表最終表基底変数s1=45s2=40x=15s2=25x=10y=15非基底変数x=0y=0s1=0y=0s1=0s2=0目的関数Z=0Z=90Z=135 図１上の点 ： Ｏ（0,0）→A(15,0)→B(10,15)影の価格（限界価値）： 最終表の最終行において、s1の列は7/5、s2の列は9/5となっている。 これを、それぞれ原料A,Bの影の価格、あるいは、限界価値と呼ぶ。双対問題： 扱ってきた左の問題に対し、右のような問題を考
7、える。 主問題 双対問題 ※非負条件以外について、縦に並んだ係数を横に不等号の向きを逆にし、最大化を最小化にしてある。 双対問題の意味解釈： この例に関しては、 主問題が、「最大利益を上げるために、製品の生産配分を求める」という、工場主の問題であるのに対し、 双対問題は、「工場主からできるだけ安く、全部の原料を買い取る」という、大金持ちの問題と見なせる。 ここで、変数m,nは、それぞれ原料A,Bの単位量当たりの
8、買い取り単価を表す。一般に、次の双対定理が成り立つので、 大金持ちは、原料A,B買い取り単価を、それぞれm=７/5,n=９/5 として、総額Z=135で買い取ることができる。これは、工場主が原料A,Bを使って生産活動をした結果、得られるであろう最大利益と一致する。※この例の双対問題も２変数なので、図による解法が可能。確認のため、各自解いてみよう。双対定理 (1)主問題の最適解における目的関数の値と、
