1 頁数理計画 2015年度中間試験問題平成27年8月6日

1頁
数理計画２０１５年度中間試験問題
平成２７年８月６日
注意事項:
(i) 問題用紙はこの頁を含めて４枚，８頁, ３題, 100 点満点です.
(ii) 解答はこの用紙に書き入れてください．どの問題の解答であるか，わかるように記入してください．
(iii) この用紙（１頁，２頁）を外して下書き用紙として利用できます。その他のホッチキスは外さないでください．もし
外してしまった場合は，必ず解答用紙に学籍番号，氏名を記入してください．
2 頁学籍番号：
3頁
氏名：
問１ (40 点) 以下の線形計画問題について,
最大化
条件
x1 + 2x2
x1 + x2 ≤ 2,
x1 + x2 ≥ 1,
x1 , x2 ≥ 0.
(i)(10 点) この問題を，等価な基準型の線形計画問題に変換せよ．
(ii)(20 点) この問題に人工変数 x0 を導入し，最小添え字規則の二相シンプレックス法で解け. 各過程の辞書とピボット
を明記すること. (単なる数字の羅列は評価しない．)
(iii)(10 点) (x1 , x2 , x0 ) 座標のグラフを用いて,
(a) もとの問題の実行可能領域と,
(b) (ii) で算出した実行可能基底解を算出した順序にしたがって，
すべて図示せよ.
4頁
学籍番号：
5頁
氏名：
問２（40 点）A を m × n 行列であるとする．次の２つの命題を考える．
(I)
(II)
Ax = 0, x ≥ 0, cT x < 0 をみたす x が存在する．
AT y ≤ c をみたす y が存在する．
(i)(15 点) 命題 (I), (II) の一方のみが常に成り立つことを，
「双対定理」を用いて証明せよ．
（ヒント：
（I) と（II) が同時に
成り立つと仮定すると矛盾が生じること，
（I) が成り立たなかったとすると（II) が成り立つことを示せばよい．
）
以下では，m = 1, n = 2 であり，行列 A = aT , ベクトル a は Figure 1 のように与えられているとする．
(ii)(5 点) 集合 S1 = {x | Ax = 0, x ≥ 0} を Figure 2 に図示せよ．
(iii)(5 点) 集合 S2 = {AT y | y ∈ ℜm } を Figure 3 に図示せよ．
(iv)(5 点) 集合 S3 = {z | ∃y, z ≥ AT y} を Figure 4 に図示せよ．
(v)(5 点) 集合 S4 = {z | ∀x ∈ S1 , z T x ≥ 0} を Figure 5 に図示せよ．
(vi)(5 点) 一般に，S3 = S4 であることを示せ．
（ヒント：(i) の結果を用いよ．
）
6頁
x
2
a
0
x1
Figure 1: ベクトル a
x
x
2
2
a
a
0
x1
Figure 2: (ii) 集合 S1
0
x1
Figure 3: (iii) 集合 S2
x2
x2
a
a
0
Figure 4: (iv) 集合 S3
x1
0
Figure 5: (v) 集合 S4
x1
学籍番号：
氏名：
7頁
8頁
問３（20 点）以下に答えよ. ただし記述が明らかに誤っている場合は減点の対象とするので注意すること.
(i)(5 点) 一般の最適化問題 inf{f (x) : x ∈ X} に対しては，線形計画問題の基本定理「問題が実行可能で有界であるな
らば最適解をもつ」は必ずしも成り立たない．基本定理が成り立たない最適化問題の例を１つ示せ．
(ii)(5 点) 主問題，双対問題ともに実行可能解をもたない線形計画問題の例を記せ．
(iii)(5 点) シンプレックス法における基底解について知ることを記せ．
(iv)(5 点) シンプレックス法における「巡回」について知ることを記せ．

Download Report