多変数関数の最大値

7変数の多変数関数をf(a,b,c,d,e,f,g)＝19a＋18b＋17c＋16d＋15e＋13f+11gとする。次の3つ条件をすべて満たす時のfの最大値を求めよ

(1)a,b,c,d,e,f,gは0≦a,b,c,d,e,f,g≦98を満たす整数

(2)a＋b＋c＋d＋e＋f＋g＝98

(3)3a＋4b＋5c＋7d＋8e＋10f＋12g＝544

この問題はどっかの問題集にあったものではなくあるものを求めるために自分で作った問題です。しかしいくらがんばっても自分ではどうすることもできません。この問題はどうすれば解くことができるのでしょうか？この問題を解けるようなフリーソフトを探しましたが見つかりませんでした。もし問題を解けるフリーソフトがあるならそれも教えて欲しいです。

No.1 回答者： N64 回答日時： 2006/11/20 21:02

線形計画法　というキーワードで探してみたらいかがでしょう。

この回答へのお礼

線形計画法と打ち込んで検索したところ一応プログラムを見つけることができました。どうもありがとうございました！

お礼日時：2006/11/20 23:24

No.2 ベストアンサー 回答者： rtz 回答日時： 2006/11/20 21:49

まず、関数をfとするなら内部変数にfを使うのはやめるべき。

直後のfの最大値は関数なのか変数なのか分からない。

19a＋18b＋17c＋16d＋15e＋13f＋11g
＝23(a＋b＋c＋d＋e＋f＋g)－(3a＋4b＋5c＋7d＋8e＋10f＋12g)－a－b－c
＝23*98－544－(a＋b＋c)
＝1710－(a＋b＋c)
この最大値を求めるので、(a＋b＋c)が最小のときを考える。
つまりなるべくdefgの値を増やすことを考える。

a＋b＋c=0とすると、
d+e+f+g=98だが7d＋8e＋10f＋12g>=7(d+e+f+g)=98*7=686となり544を超えてしまう。

よって仮にdが98、残りが0のときを考えると、
3a＋4b＋5c＋7d＋8e＋10f＋12g=686
dを減らす代わりにefgを増やしても686から大きくなるだけなので、
仕方が無いのでabcの値を大きくすることを考える。

dを1減らしたとき、aかbかcを1増やすわけだが、aなら4、bなら3、cなら2が686から減っていく。
なるべくdを減らしたくないので、aを増やすのが効率がよい。
(686-544)/4=35.5

つまりa=35でc=1とするか、a=34でb=2とするかすればa＋b＋cが最小の36になる。
このときd=62。

(a,b,c,d,e,f,g)=(35,0,1,62,0,0,0)(34,2,0,62,0,0,0)で
19a＋18b＋17c＋16d＋15e＋13f＋11gは最大値1674をとる。

コードを書いた方が簡単だったかも知れない。

この回答へのお礼

わざわざご解答ありがとうございます！下に書いたとおり一応プログラムを見つけれたのでそれで計算したところ最大値は1674と出ましたが、はたして本当にこの値でよいかわかりませんでした。しかし値は正しいこととが確認できたのでどうもありがとうございました。

お礼日時：2006/11/20 23:28

No.3 回答者： InugasaGinjiro 回答日時： 2006/11/20 21:53

大概、多変数関数の条件付き極値の問題は、ラグランジュの未定乗数法を用いますが、各変数が整数であり、かつ（この場合は）乗数も定まらないので、プログラミングを使うのが妥当かもしれませんね。

私は専門外ですが、C 言語の for 文を使えば（原理的には）可能かと思います。但し、その前に、(2)(3) の式を e, f についてそれぞれ解いて、f(a, ... , g) に代入し、5変数函数に直した方が良いでしょう。とはいえ、for 文を単純に繰り返し使えば、99^5 = 9509900499 回の計算をしなくてはならなくなるので、時間がかかるかもしれません。

この回答への補足

わざわざご解答ありがとうございます。

補足日時：2006/11/20 23:28