離散最適化基礎論 (5) 演習問題 2014 年 11 月 7 日岡本吉央提出締切： 2014 年 11 月 14 日この凸多面体 C3∗ における次の面の法錐の V 表現を与えよ．復習問題 5.1 次の H 表現を持つ凸多面体 P を考える．   −x ≤ −2,    1        −x ≤ −1, 2 2 P = x∈R .   x1 + x2 ≤ 7,        x + 4x ≤ 16  1 1. 頂点 (1, 0, 0)> 2. 2 頂点 (0, 1, 0)> と (0, 0, 1)> を結ぶ線分 2 追加問題 5.6 任意の自然数 m, n と任意の ai ∈ Rn , bi ∈ この凸多面体 P の法扇を R に図示せよ． 2 R, c ∈ Rn に対して (ただし，i ∈ {1, . . . , m})，次の線形計復習問題 5.2 任意の自然数 m, n と任意の ai ∈ R , bi ∈ n 画問題 (P’) R, c ∈ R に対して (ただし，i ∈ {1, . . . , m})，次の線形計画問題 (P) n maximize c> x subject to a> i x ≤ bi subject to c> x subject to a> i x ≤ bi ∀ i ∈ {1, . . . , m}, x≥0 ∀ i ∈ {1, . . . , m} とその双対問題 (D’) とその双対問題 (D) minimize maximize b> y m ∑ minimize subject to yi ai = c, b> y m ∑ yi ai ≥ c, i=1 i=1 y≥0 y≥0 を考える．ただし，b> = (b1 , b2 , . . . , bm )> ∈ Rm である．を考える．ただし，b> = (b1 , b2 , . . . , bm )> ∈ Rm である．そして，x∗ ∈ Rn が (P) の最適解であり，かつ，y ∗ ∈ Rm (P’) の許容解 x∗ ∈ Rn と (D’) の許容解 y ∗ ∈ Rm に対して，が (D) の最適解であることを仮定する．このとき，任意の次の 2 条件が同値であることを証明せよ． ∗ i ∈ {1, . . . , m} に対して，yi∗ > 0 ならば a> i x = bi となることを証明せよ．ヒント：強双対定理を用いてよい． 1. x∗ は (P’) の最適解であり，y ∗ は (D’) の最適解である． 2. 任意の i ∈ {1, . . . , m} に対して，yi∗ > 0 ならば ∗ a> j) ∈ {1, . . . , n} に i x = bi であり，かつ，任意の (m ∑ yi ai = cj である．対して，x∗j > 0 ならば補足問題 5.3 任意の凸多面体 P ⊆ Rn とその任意の面 F ⊆ P (ただし，F 6= ∅) に対して，F の法錐 NF が凸錐であることを証明せよ． ( 補足問題 5.4 演習問題 5.2 で定義した問題 (P) と (D) を考える．任意の i ∈ {1, . . . , m} に対して，yi∗ > 0 ならば ( ∗ ∗ n a> i x = bi となることを仮定する．このとき，x ∈ R は ∗ m (P) の最適解であり，かつ，y ∈ R は (D) の最適解であ m ∑ ) はベクトル yi ai i=1 j ( i=1 m ∑ )j yi ai の第 j 成分とい i=1 う意味．) ることを証明せよ．ヒント：弱双対定理を用いてよい．ヒント：第 1 回講義の演習問題 1.7 にある弱双対定理と強追加問題 5.5 次の H 表現を持つ 3 次元凸多面体 C3∗ を考双対定理を利用してみよ．える (これは正八面体である) ．  x + x + x ≤ 1,   1 2 3     x − x + x  2 3 ≤ 1,  1     x1 + x2 − x3 ≤ 1,    ∗ 3 x1 − x2 − x3 ≤ 1, C3 = x ∈ R   −x1 + x2 + x3 ≤ 1,     −x1 − x2 + x3 ≤ 1,     −x + x − x ≤ 1,   1 2 3    −x1 − x2 − x3 ≤ 1                                . 1