2015 東京工業大学 第3類AO総合問題MathJax

Mathematics

Examination

Test

Archives

2015 東京工業大学 第3類AO総合問題

易□ 並□ 難□

【1】 次のような問題を考える.

A1 A2 An という名前の商品がそれぞれ 1 個ずつあり,これらを 1 台のトラックで運びたい.ただし,商品 A i i=1 2 n の重量は wi kg 売れた時の利益は p i 万円である.また,トラックには W kg という制限重量を超えて荷物を詰め込むことはできない.このとき運んだ商品の利益の合計をできるだけ大きくするには,どの商品を運べばよいだろうか.

 この問題を含んだ問題群として,運べる商品を A1 A 2 Ak k 個に制限し,制限重量が x kg である場合を考える.この問題に対して,運んだ商品の利益の合計の最大値(以下では最大利益と呼ぶ)を関数 fk (x ) で表現する(ただし, x0 で定義されているものとする).例えば, f3 ( 100) は, 3 個の商品 A1 A 2 A 3 の中から制限重量 100 kg を超えないように幾つか選んで運んだときの最大利益を意味している.このとき,次の問(1)〜(3)に答えよ.

(1)  w1 =300 w 2=500 p1 =45 p2 =75 とする. x の範囲で場合分けして考えることにより,関数 f1 (x ) f2 (x ) のグラフを図示せよ.また,各場合での関数値の計算法を簡潔に説明せよ.

(2) 上記で定義した関数 fk (x ) には以下の関係が成り立つ.

f1 (x )={ 0 w 1>x の時) p1 w1 x の時)

k=2 3 n に対し,

fk (x )={ fk- 1 (x ) wk >x の時) max{ fk- 1( x),f k-1 (x- wk) +pk } wk x の時)

ただし, max{ a,b } a b でより大きな方の数を意味する.このとき, k=2 3 n w k>x の場合では, fk (x) =fk -1 (x ) という関係が成り立っているが,これは次のように説明することができる.

fk (x ) A1 A 2 Ak の商品から制限重量 x を超えないように運ぶ時の最大利益であるが, wk> x であるため商品 A k を運ぶことはできない.ということは, A1 A2 Ak の商品から制限重量 x を超えないように運ぶということは, A1 A2 A k-1 の商品から制限重量 x を超えないように運ぶことに他ならない.このときの最大利益は fk-1 ( x) であるので, fk ( x)= fk- 1 (x ) となる.

この説明を踏まえて, k=2 3 n n kx の場合において, max{ fk- 1 (x ), fk- 1 (x- wk) +pk } という関係が成り立つことを証明せよ.

(3) 冒頭の枠内に記述した問題に対する最大利益は fn (W ) に相当する.いま, wi i= 1 2 n W は自然数であることを仮定する.このとき,次の手順によって fn (W ) を計算することができる.

ステップ1.

  wi i= 1 2 n W の最大公約数を求め t とする.

ステップ2.

まず, x=0 t 2 t 3 t W に対し,次式より f1 (x ) を計算する.

f1 (x )={ 0 w1> x の時) p1 w1 x の時)

ステップ3.

次に, x=0 t 2 t 3 t W に対し,次式より f2 (x ) を計算する.

f2 (x )={ f 1( x) w2> x の時) max{ f1 (x) ,f1 (x -w2 )+ p2 } w 2x の時)

ステップ4.

以下, k=3 4 n に関して同様の手順を実行する.

すなわち, x=0 t 2 t 3 t W に対し, fk- 1 (x ) が計算されていれば,次式より fk (x ) を計算できる.

fk (x )={ fk- 1 (x) wk> x の時) max{ fk- 1( x), fk- 1 (x- wk) +pk } w kx の時)

これを繰り返すと,最終的に fn (W ) の値が得られる.

上記の手順を実行することにより,表1で与えられているような 5 個の商品を制限重量が 1000 kg のトラックで運ぶ時の最大利益を求める.

表1 商品の重量と利益

商品 A1 A2 A3 A4 A5
重量 300 kg 500 kg 400 kg 200 kg 300 kg
利益 45 万円 75 万円 70 万円 35 万円 50 万円

解答では計算法は述べなくてよいので,上記の手順に基づいて fk (x ) の値を順番に計算し,その結果を答案用紙の表中に記入せよ.

inserted by FC2 system