2014 年度最適化論レポート課題 #2 (飯塚秀明担当) 注意 1. LATEX でレポートを作成した場合は、加点をします。LATEX のテンプレートは http://www.mo.cs.meiji.ac.jp/t/2014/opt にあるので、参考にして下さい。注意 2. 下記の問題 1., 2. は必須課題です。レポートは 12/3(水) の授業内に集めるので、注意して下さい。注意 3. 下記の問題 3. は任意課題です。レポートは 12/10(水) の授業後に集めます。注意 4. 問題 3. について、何らかのプログラムを作成して問題を解いた場合は、必ずその実行環境、ソースコード、および、用いたプログラミング言語の名称を明記すること。 1. 以下の組合せ計画問題に関する問 (i)–(ii) について答えなさい。目的関数: 3x1 + 4x2 + x3 + 2x4 → 最大制約条件: 2x1 + 3x2 + x3 + 3x4 ≤ 4 (1) xi = 0, 1 (i = 1, 2, 3, 4) (i) 問題 (1) に対する連続緩和問題を与え、その問題の解（実数最適解）を求めなさい。 (ii) (i) の結果を用いて、問題 (1) を分枝限定法で解きなさい（ただし、各反復における暫定解、暫定値、活性部分問題を必ず明記すること）。また、問題 (1) に対する分枝限定法の探索木を図示しなさい。 2. 授業に関する感想があれば書いて下さい。 3. 【任意課題】以下について提出しなさい。 (i) http://www.mo.cs.meiji.ac.jp/t/2014/opt にて配布する数列 1 について、その数列の増加部分列のうち最長のものの長さを求めなさい。ただし、数列 {an } が増加列であるとは、任意の自然数 i, j ∈ N について、i ≤ j ならば ai ≤ aj を満たすものをいう。 (ii) N を自然数とする。このとき、大きさ 1 × 2 の長方形を、大きさ 2 × N の長方形内に、 90◦ 回転を許して隙間なく敷き詰める敷き詰め方の総数を FN とする。N = 1 のとき、敷き詰め先の長方形は、大きさ 1 × 2 の長方形 1 つとちょうど同じ形であるので、F1 = 1 であることが分かる。同様に N = 2 のとき、大きさ 1 × 2 の長方形 2 つを、横方向または縦方向の 2 通りで並べることができるので、F2 = 2 となることが分かる。この FN は、 2 × 2 正方行列 A ∈ Z2×2 を用いて、 ) ) ( ( FN +1 FN +2 =A FN FN +1 と表せる。この行列 A を示し、その理由を論じなさい。 (iii) (ii) の FN について、F98765432123450693 の下 4 桁 2 を求めよ。 1 2 長さ N = 25000、各要素の値 an ≤ 10000 (n = 1, 2, . . . , N ) なる数列 {an }N n=1 ⊂ N が与えられる。数 98765432123450693 は、32bit 符号付き整数の上限 231 − 1 に収まらないことに注意せよ。 2014 年度最適化論レポート課題 #2（1/1）