数理計画問題について

質問

以下の問題についてのアドバイスが欲しいのですが

下記の条件を持つとき
y(1)+y(2)+y(3)の合計が最も小さくなるように
x(11)～x(36)の値をそれぞれ求めなさい

【条件】
x(nm)は変数で正数のいずれかの値が入る
x(nm)≧0

1x(11)+4x(12)+16x(13)-1x(14)-4x(15)-16x(16)=　2
1x(21)+4x(22)+16x(23)-1x(24)-4x(25)-16x(26)=　5
1x(31)+4x(32)+16x(33)-1x(34)-4x(35)-16x(36)=　8

y(1)=max{x(11)…x(16)}…(A)
y(2)=max{x(21)…x(26)}…(B)
y(3)=max{x(31)…x(36)}…(C)

(A)　x(11)からx(16)のうち一番大きい数値をy(1)とする
(B)　x(21)からx(26)のうち一番大きい数値をy(2)とする
(C)　x(31)からx(36)のうち一番大きい数値をy(3)とする

という問題が分からなくて質問しています。
私的に整数計画問題とも思いましたが、式の構造から
違うのではないかと思ったりもしています。

この問題を解くのに、似たような問題や
もしくは解法を求める為の御意見、
これは解けるような問題なのかどうかなど
を是非お聞かせ下さい。宜しくお願いします。

回答No.4

mocapapa89

No.3です。

>私もEXCELのソルバーを用いて解を得ることができました。

あのような拙い説明にも関わらず結果まで得ることができてよかったです。

>２，５，８の数値を変えてみると値が整数にならないことが
>あるのですが、これは精度の設定の問題でしょうか

今回は正整数と仮定して解きましたが、目的が目的関数の最小化ですから、整数の制約をはずせばより良い最小値と解の値が出る可能性があります。例えばリンゴの個数として最適な値が2.5だったとして、リンゴの数は整数だから最も近い2(ないし3)とするか(最初から整数の制約で解いても良い)、リンゴをナイフで切って2個と半分とするかは問題の背景を見なければわかりません。また、ソルバが局所解を出した可能性も否定できません。

>いずれにせよ。ソルバーというツールを初めて使いましたので
>これから少しずつ勉強していきたいと思います

マイクロソフトの回し者ではありませんが、Excelソルバは無料のわりに簡単に非線形の最適化ができる優れものなので、いろいろと試されてみたらよろしいかと思います。なおExcelソルバで使用している(らしい)アルゴリズムを最近ネットで見つけたので参考URLを乗せておきました。

参考URL：

http://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/nonlinear/nonlinear.htm#2.2

回答No.3

mocapapa89

Excelのソルバーでは簡単に解けます。解いた結果を載せておきます。各変数は正の整数と仮定しました。

x(11)=2 x(12)=0 x(13)=0 x(14)=0 x(15)=0 x(16)=0
x(21)=1 x(22)=1 x(23)=0 x(24)=0 X(25)=0 X(26)=0
x(31)=1 X(32)=0 X(33)=2 X(34)=1 X(35)=2 X(36)=1

解き方はExcelのソルバーに上記のセルをつくり、目的関数として最小値にしたい式を記述したセルを指定します。さらに制約として各セルを整数とする条件と制約式
>1x(11)+4x(12)+16x(13)-1x(14)-4x(15)-16x(16)=　2
>1x(21)+4x(22)+16x(23)-1x(24)-4x(25)-16x(26)=　5
>1x(31)+4x(32)+16x(33)-1x(34)-4x(35)-16x(36)=　8
を入れ、オプションで非負数を指定し実行するだけです。

ちなみにこれはNP(非線形最適化)問題であり、数値計算で解くしかないかと思います。

参考URL：

http://office.microsoft.com/ja-jp/excel/HA011245951041.aspx

お礼

ご検討のほど有難うございました。

私もEXCELのソルバーを用いて解を得ることができました。
２，５，８の数値を変えてみると値が整数にならないことが
あるのですが、これは精度の設定の問題でしょうか

いずれにせよ。ソルバーというツールを初めて使いましたので
これから少しずつ勉強していきたいと思います

ありがとうございました

回答No.2

rabbit_cat

与えられた条件で、もちろん問題として成立してますし、最適な解は（一つとは限らないかしれませんが）存在します。

ただ、実際に解こうとなると、maxていうのはけっこう厄介な関数で（不連続点の塊なので）、なかなか上手い方法がありません。
y(1)=max{x(11)…x(16)}…(A)
が、２乗和
y(1)=x(11)^2 + x(12)^2 + … + x(16)^2
とかであれば、一般的な解法があるんですけど。

コンピュータを使って数値的に解を求めたいということであれば、適当なソルバを使えば解けるのでは。

お礼

お忙しい中ご検討ありがとうございます。
返信が遅れてしまい申し訳ありません。

問題として必ず解が求まるということが分かり
安心しました。

ソルバーというのを使ったことが無かったので
抵抗がありましたが、非常に有益なものとして
そのようなツールがあることを恥ずかしながら知りました。

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

回答No.1

noname#70519

残念ながら、お望みの方法はありえません。
余りにも自由度が大きすぎるからです。

何故なら、条件式は
1{x(11)-x(14)}+4{x(12)-x(15)}+16{x(13)-x(16)}=2
1{x(21)-x(24)}+4{x(22)-x(25)}+16{x(23)-x(26)}=5
1{x(31)-x(34)}+4{x(32)-x(35)}+16{x(33)-x(36)}=8

と書くことができて、それぞれの式は、x、y、z 軸方向成分が
1、4、16 の大きさを持つベクトルに直交する三次元の平面で、
それぞれ、x 軸と 2、5、8 において交差する平行な三つの平面
を表す式だからです。
この平面上のどの点も、条件式を満たし、例えば最初の式の
平面上の点が（x、y、z）であるとすると、x+4y+16z=2 という
条件はあるものの、これを満足する点は無数にあり、

x(11)-x(14)=x
x(12)-x(15)=y
x(13)-x(16)=z
を満たす六つの値も無数にあるからです。

お礼

お忙しい中ご検討ありがとうございます。
返信が遅れてしまい申し訳ありません。

式を変形させると違った見え方が
あることに気づかされました。

確かにx,y,zの解を全て出すとなると
無数にあるので出せませんね。

とある質問はとある問題に対して
定式化したものなのですが、もっと制約条件を
考慮してみて、解を出しやすくしたいと思っています

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