線形計画法（方程式）の解き方

質問

今、線形計画法について学習しております。下記の問題について、考え方は理解できたのですが、お恥ずかしながら方程式の解き方等で難儀しております。どうか、できる限りわかりやすく解法手順をご教授いただければ幸いです。どうぞ、よろしくお願い申し上げます。

（問題）
「製品Ｘを１kg生産するには，原料Ａを４kg，原料Ｂを２kg，原料Ｃを１kg必要とし，製品Ｙを１kg生産するには，原料Ａ１kg，原料Ｂを２kg，原料Ｃを３kg必要とします。原料の在庫量は，Ａは７２kg，Ｂは４８kg，Ｃは４８kgあります。製品Ｘの売価は３万円／kg，製品Ｂの売価を２万円とするとき，利益（＝売上高。原料や生産の費用は考えないことにします）を最大にするには，製品Ｘと製品Ｙをどれだけ生産すればよいでしょうか。」
この問題文を表にすると次表になります。

　　　　　製品Ｘ　　製品Ｙ　　　原料在庫量
原料Ａ　　　４　　　　１　　　　　７２　
原料Ｂ　　　２　　　　２　　　　　４８
原料Ｃ　　　１　　　　３　　　　　４８

目的関数　
　Ｚ：　　　３　　　　２　　　→　最大

という問題なので、下記のような式が成り立つことまでは理解できたのです。ただ、この方程式の解き方がわかりません。どうか、よろしくお願いいたします。

　　　　　　　４ｘ＋１ｙ≦７２
　　　　　　　２ｘ＋２ｙ≦４８
　　　　　　　１ｘ＋３ｙ≦４８
　　　　　　（ｘ≧０，ｙ≧０）
　　　　目的関数
　　　　　Ｚ＝３ｘ＋２ｙ
　　　　を最大にする，ｘとｙの値を求める。

回答No.3

rmrmrm · ベストアンサー

こんにちは。大学院で数理工学を専門にしておりました。

線形計画法の解放は、よく「シンプレックス法」と「内点法」があると言われますが、これらは、変数(ご質問の例では x とか y とか) が何十個も何百個もある場合に、コンピュータで解く場合のアルゴリズム(プログラムの方法)の話です。

ご質問の例では、変数が 2つしかないので、平面図を描くことで、簡単に解くことができます。
「式で解く」のではなく「絵で解く」というのが、この手の問題を解くコツです。
不等式を満たす (x,y) の領域を図で表して、目的関数 (3x+2y) をスライドさせて、該当する領域内で最大の値を求めればいいわけです。

最近はどうか分かりませんが、昔は初歩的な高校数学で扱われていたと記憶しております。(意外と高校の教科書が参考になるかも知れません)

お礼

rmrmrmさん
このたびは、ご回答ありがとうございました。やはり初歩的な数学から勉強しなおす必要があると痛感しました。
どうぞ、今後ともよろしくお願いいたします。

回答No.2

qaz_qwerty_me

こちらのカテゴリーではなくて数学の方が適切な回答が得られる気がします。

Ｇｏｏｇｌｅで探すとＬＰ問題でヒットしますよね？
http://www.kogures.com/hitoshi/webtext/lp-intro/

確かこの解法がソフトウェアで始めての特許を得たとして話題になったと思いました。

お礼

qaz_qwerty_meさま

ご回答ありがとうございます。
教えていただいたHP拝見させていただきました。
全部見たわけではありませんが、
内容的にすごく充実したページですね。
どうもありがとうございました。

今後ともよろしくお願いいたします。

回答No.1

lucky111

素人ですが、数学としては興味を持ちましたので、投稿します。

解法の考え方ですが、

ｘ－ｙ平面上に

４ｘ＋１ｙ＝７２
２ｘ＋２ｙ＝４８
１ｘ＋３ｙ＝４８

の３つの一次関数のグラフを書いて、

Ｚ＝３ｘ＋２ｙ

で、Ｚに任意の数字を入れて、一次関数のグラフを書いてみれば、最大のＺの数値が出てくると思います。

もしでないとすれば、数学的に式がまちがっている、ということになります。

専門的には、きちんとした解法があるのかも知れませんね。

お礼

lucky111さま

ご回答ありがとうございます。
う～ん、私の硬直しはじめた脳には、まだ、ピンと来ませんが、
再度、lucky111さんからいただいたヒントをもとに
よ～く、噛み砕いて考えてみます。

どうもありがとうございました。