動的計画法に関する問題です。
a1,a2,･･･,aNが正の整数であるとき、制約条件:x1,x2,･･･,xN≧0, x1＋x2＋･･･＋xN＝c>0の下で、a1√x1＋a2√x2＋･･･＋aN√xNの最大値を求めよ。
どなたかご教示よろしくお願いします！！
|
No.34498 - 2015/11/28(Sat) 20:40:54
| ☆ Re: / 水面に映る月 | | | 実数を成分とするn次元ベクトル（n個の成分を持つベクトルのこと）の内積と大きさを次のように定めます。
?@ベクトルp=(p[1],p[2],...,p[n]),q=(q[1],q[2],...,q[n])
について、内積(p|q)は、
(p|q)=p[1]q[1]+p[2]q[2]+...+p[n]q[n]
?Aベクトルpの大きさは、|p|=√(p|p)
本問において、ベクトルa,ベクトルxを次のように定めます。
a=(a[1],a[2],...,a[n])
x=(√(x[1]),√(x[2]),...,√(x[n]))
こうすると、本問は次のように言い換えることができます。
大きさ√cで、成分がすべて0以上のN次元ベクトルxと成分がすべて自然数であるN次元ベクトルaについて、内積(a|x)の最大値を求めよ。
N=1,2,3であれば、関係式(a|x)≦|a||x|（等号成立はxがaの実数倍の時）を使うことで簡単に答えが出ますが、実は、この関係式はN次元ベクトルでも成り立ちます。以下にその証明をして回答とさせていただきます。
以下、tは任意の実数であり、また、|a|≠0とする。
ベクトル y=x+ta を考える。
(N次元ベクトルの実数倍や和も、2次元ベクトルや3次元ベクトルの時と同じように、成分の実数倍、および、成分同士の和と考えてください。こうすると、ベクトルの演算は2次元ベクトルや3次元ベクトルの時と同じようにできます。)
|y|^2=(y|y)
=( x+ta | x+ta )
=|x|^2 + 2(a|x)t + |a|t^2
これはtについての２次式だが、tが実数の範囲でどのような値をとろうとも、|y|^2≧0だから、この２次式の値は任意の実数tに対して0以上である。つまり、この２次式の判別式をDとすれば、D/4≦0ということです。
D/4=(a|x)^2 - |a|^2 |x|^2 ≦ 0
したがって、 (a|x)^2 ≦ |a|^2 |x|^2
|a||x|≧0なので、 (a|x)≦|a||x| となります。
なお、等号成立はD/4=0の時、つまり、|x+ta|^2=0を満たすtが一つだけ存在するときであるが、
|x+ta|^2=0 は x+ta=0 に同値なので、これを満たす実数tが一つだけ存在するときとは、xがaの実数倍であるときである。
というわけで結局、求める最大値は|a|√cとなります。
長文失礼しました。
|
No.34530 - 2015/12/01(Tue) 18:48:13 |
| ☆ Re: / 水面に映る月 | | | ごめんなさい。訂正です。
「これはtについての２次式だが...」のすぐ上の数式です。次に示すものが正しいです。（t^2の係数が誤っていた）
|y|^2=(y|y)
=( x+ta | x+ta )
=|x|^2 + 2(a|x)t + (|a|^2)t^2
なお、以降の証明に影響はありません。失礼しました。
|
No.34531 - 2015/12/01(Tue) 19:03:32 |
|
