- 締切済み
数理計画問題について
以下の問題についてのアドバイスが欲しいのですが 下記の条件を持つとき 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)とする という問題が分からなくて質問しています。 私的に整数計画問題とも思いましたが、式の構造から 違うのではないかと思ったりもしています。 この問題を解くのに、似たような問題や もしくは解法を求める為の御意見、 これは解けるような問題なのかどうかなど を是非お聞かせ下さい。宜しくお願いします。
- daisuke30
- お礼率66% (6/9)
- 数学・算数
- 回答数4
- ありがとう数4
- みんなの回答 （4）
- 専門家の回答
みんなの回答
- mocapapa89
- ベストアンサー率16% (1/6)
No.3です。 >私もEXCELのソルバーを用いて解を得ることができました。 あのような拙い説明にも関わらず結果まで得ることができてよかったです。 >２，５，８の数値を変えてみると値が整数にならないことが >あるのですが、これは精度の設定の問題でしょうか 今回は正整数と仮定して解きましたが、目的が目的関数の最小化ですから、整数の制約をはずせばより良い最小値と解の値が出る可能性があります。例えばリンゴの個数として最適な値が2.5だったとして、リンゴの数は整数だから最も近い2(ないし3)とするか(最初から整数の制約で解いても良い)、リンゴをナイフで切って2個と半分とするかは問題の背景を見なければわかりません。また、ソルバが局所解を出した可能性も否定できません。 >いずれにせよ。ソルバーというツールを初めて使いましたので >これから少しずつ勉強していきたいと思います マイクロソフトの回し者ではありませんが、Excelソルバは無料のわりに簡単に非線形の最適化ができる優れものなので、いろいろと試されてみたらよろしいかと思います。なおExcelソルバで使用している(らしい)アルゴリズムを最近ネットで見つけたので参考URLを乗せておきました。
- mocapapa89
- ベストアンサー率16% (1/6)
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(非線形最適化)問題であり、数値計算で解くしかないかと思います。
- rabbit_cat
- ベストアンサー率40% (829/2062)
与えられた条件で、もちろん問題として成立してますし、最適な解は（一つとは限らないかしれませんが）存在します。 ただ、実際に解こうとなると、maxていうのはけっこう厄介な関数で（不連続点の塊なので）、なかなか上手い方法がありません。 y(1)=max{x(11)…x(16)}…(A) が、２乗和 y(1)=x(11)^2 + x(12)^2 + … + x(16)^2 とかであれば、一般的な解法があるんですけど。 コンピュータを使って数値的に解を求めたいということであれば、適当なソルバを使えば解けるのでは。
お礼
お忙しい中ご検討ありがとうございます。 返信が遅れてしまい申し訳ありません。 問題として必ず解が求まるということが分かり 安心しました。 ソルバーというのを使ったことが無かったので 抵抗がありましたが、非常に有益なものとして そのようなツールがあることを恥ずかしながら知りました。 ありがとうございました。
残念ながら、お望みの方法はありえません。 余りにも自由度が大きすぎるからです。 何故なら、条件式は 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の解を全て出すとなると 無数にあるので出せませんね。 とある質問はとある問題に対して 定式化したものなのですが、もっと制約条件を 考慮してみて、解を出しやすくしたいと思っています ありがとうございました。
関連するQ&A
- つぎの数理計画問題を解いてください。
つぎの数理計画問題を解いてください。 max ax + (1-a)y subject to 2x + y ≦ 3 x + y ≦ 2 x≧0, y≧0 (1) この問題に対するKuhn-Tucker条件を示せ。 (2) (x, y) = (1, 1) が最適解となるaの区間を示せ。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 数学の問題を教えてください！２
数学の問題を教えてください！２ 宜しくお願いします。解説もおねがいします。 １. （√２－√３＋√５）（√２＋√３－√５） ２. x＋y＝３、x－y＝２√２のときx＾２－２x－２xy＋y＾２－２y の値を求めよ。 ３. x＝√５－√３、y＝√５＋√３のとき、（１／x）＋（１/y）の値を求めよ。 ｛（１/x）、（１/y）は（x分の１）、（y分の１）です！間違って逆だったらすいません！！言ってください。｝ ４. a＝√３＋√２＋１、b＝√３－√２＋１のとき、つぎの式の値を求めよ。 （１） （１／２）ab （２） （a＾２－２a－４）/（b＾２－２b－４） ｛これも、（1/2）は２分の１、（a＾２－２a－４）/（b＾２－２b－４）はb＾２－２b－４分のa＾２－２a－４です｝ ５. ２（x－√３）＾２－３（x－√３）－２＝０ の解を求めよ。 ６. ２００・２０２・５１５などのように、０から９までの数字のうち２種類の数字を用いて３けたの整数を作る。したがって、１００が最小で９９８が最大の整数となる。このとき、次の問いに答えよ。 （１） ０と１の２種類の数字を用いて作られる３けたの整数は何個あるか。 （２） １と２の2種類の数字を用いて作られる３けたの整数は何個あるか。 （３） 作られる３けたの整数のうち、２００より小さい整数は何個あるか。 （４） 作られる３けたの整数は全部で何個あるか。 です！！分かりにくいとは思いますが、ぜひ宜しくお願いします！！！
- ベストアンサー
- 数学・算数
- 集合論の問題
次の条件が成り立つための定数a,b,cの必要十分条件を求めよ。 すべての整数ｘについてax^2+bx+cの値が偶数になる。 教えてほしいところ 解説ではx=-1,1,0からa+b=2(m+l),a-b=2(n-l),c=2lとしてこれを逆に代入して同値性を確保して必要十分条件と出していました。 しかし、それは、あくまでx=-1,1,0から出した条件であって果たしてそれ以外のｘの値に対して同様になるとは限りませんよね。 つまりa+b=2(m+l),a-b=2(n-l),c=2l→すべての整数ｘについてax^2+bx+cの値が偶数になるはなり立ちますが すべての整数ｘについてax^2+bx+cの値が偶数になる→a+b=2(m+l),a-b=2(n-l),c=2lが成り立つかx=1,-1,0だけではあやしい気がします。それならすべてでなく、x=1,-1,0についてax^2+bx+cの値が偶数になるという問題に対しての必要十分条件だとしか思えません。 集合論は難しくて複雑です。誰か、解説してください。
- ベストアンサー
- 数学・算数
- 「解きながら学ぶC言語」という本の問題8-3
２つの値の大きい方の値を返すマクロを以下のように定義! #define max(x, y) ((x) > (y) ? (x) : (y)) このマクロを利用してmax(max(max(a, b), c), d)を展開すると ((((((a) > (b) ? (a) : (b))) > (c) ? (((a) > (b) ? (a) : (b))) : (c))) > (d) ? (((((a) > (b) ? (a) : (b))) > (c) ? (((a) > (b) ? (a) : (b))) : (c))) > (d)) このようになる。 そこで質問ですが、展開後の最後の部分、 (c))) > (d))は、不等号(>)ではなくコンマ(:)ですよね？ これは参考書のミスということでよろしいんでしょうか？ 少々腑に落ちないので質問させていただきました。 長々と長文申し訳ございません。 ご回答宜しくお願いします！
- ベストアンサー
- C・C++・C#
- 問題がとけません
以下の問題が解けません。 わかる方、教えていただけないでしょうか？ ・キーボードから3整数を読み込み，小さい順に出力せよ。 ヒント------------------------------------------------- キーボードから読み込む変数をa,b,c，出力する変数をx,y,z(x<y<z)とするとよい かもしれない。 プログラムの構造は次のようになる。 #include <stdio.h> int main() { int a,b,c,x,y,z; scanf("%d%d%d",&a,&b,&c); ...//ここが本体 printf("%d %d %d\n",x,y,z); return 0; } もちろん，目的が達成されるなら，上の例のようにならなくても良い。
- ベストアンサー
- C・C++・C#
- 簡単な問題のようですが・・・
簡単な問題のようですが、最後の2次方程式から解けません。 それとも、この方法自体が間違っているのでしょうか。 指摘、および解法をよろしくお願いします。 ～～～問題～～～～～～～～～～～～～～ Ａ＋Ｂ＝１０ Ａ×Ｂ＝４０ Ａ，Ｂの値をそれぞれ求めなさい。 ～～～～～～～～～～～～～～～～～～～ 私がやってみた場合 ～～～解～～～～～～～～～～～～～～～ ＡをＸ，ＢをＹとする。 それぞれＸを右辺へ移項し、 Ｙ＝－Ｘ＋４０ Ｙ＝４０/Ｘ とする。Ｙ＝Ｙなので －Ｘ＋４０＝４０/Ｘ 式をまとめると、 Ｘ²－１０Ｘ＋４０＝０ となりますよね。ここからができないのです。 というか、ここまで計算があっているかどうかも分かりません。 江戸時代の人が、解いた問題と聞いて、その方法も知りたいと思います。どうぞ、よろしくおねがいします。
- ベストアンサー
- 数学・算数
- 線形計画法の解法について！
線形計画法の解き方が判らなくて困っています。 判らないこと 1.制約条件の式と計算値 2.目的関数の式と目的値 線形計画法は変数と制約条件と目的関数が与えられます。 制約条件を満足し、目的関数が最大（最小）となる変数を求めます。 線形計画法の例 変数 x y 制約条件 (A) 10x + 4y ≦ 360 (B) 4x + 5y ≦ 200 (C) 2x + 10y ≦ 300 (D) x ≧ 0 (E) y ≧ 0 目的関数 M = 7x+12y A,B,C,D,Eの条件を満足し目的関数(M)が最大となる変数x,yを求めます。
- ベストアンサー
- 数学・算数
- 数学の問題です。よい解法はないでしょうか
留学生試験 H25-6月実施の 数学コース１(基本コース）のIIIの問題です。 (5)の問題，しらみつぶしでやっていけば解けるのですが，もう少し気の利いた解答はないでしょうか。 ==================================================================================== 問題 III 設問(1)-(4)の[A]-[D]にはそれぞれ，各問の(0)－(3)の中から適するものを選びなさい。 また，設問(5）の[E]-[G]には適する数を入れなさい。 a, b, c は整数とし，a > 0 とする。また，2次関数 y= ax^2 -2bx + c のグラフはx軸と，共有点を持ち， それらはすべて区間 0 < x <1 の中にあるものとする。 (1) a と bの大小については[A]である。 (0) a > b (1) a < b (2) a = b (3)判定不可能 (2) b と c の条件については[B]である。 (0) b < 0, c < 0 (1) b < 0, c > 0 (2) b > 0, c < 0 (3) b > 0, c > 0 (3) 2b と a + c の大小については[c]である。 (0) 2b > a + c (1) 2b < a + c (2) 2b = a + c (3) 判定不可能 (4) b と cの大小については「D] である。 (0) b > c (1) b < c (2) b = c (3) 判定不可能 (5) a のとり得る最小の整数は[E]であり，そのときの b の値は[F], c の値は[G]である。 ========================================================================= (1)-(4)までは何とか解けました。 (5) a=1のとき，不可 a=2のとき不可 a=3のとき不可 とやって，最小値はa=4を得ますが，こんな方法でなく，鮮やかな解法はないでしょうか。 教えて下さい。 香深
- ベストアンサー
- その他（受験・進学）
お礼
ご検討のほど有難うございました。 私もEXCELのソルバーを用いて解を得ることができました。 ２，５，８の数値を変えてみると値が整数にならないことが あるのですが、これは精度の設定の問題でしょうか いずれにせよ。ソルバーというツールを初めて使いましたので これから少しずつ勉強していきたいと思います ありがとうございました