京都大学 情報学研究科 数理工学専攻 2019年8月実施 線形計画

Author

Casablanca

Description

日本語版

と を 次元ベクトル， を 次元ベクトルする． ただし は転置記号を表す．さらに， を第 列が となる 行列，つまり とする．

次の線形計画問題 (P) とその双対問題 (D) を考える．

ただし，(P) の決定変数は ，(D) の決定変数は である．

問題 (P) は となる唯一の最適解 を持つとする．このとき，次の線形計画問題 (Q) を考える．

ただし，決定変数は と である．

以下の問いに答えよ．

(i) 問題 (Q) の双対問題を書け．

(ii) 問題 (Q) が最適解を持つことを示せ．

(iii) 問題 (Q) の最適値が となることを示せ．

(iv) 問題 (Q) は となる最適解 を持つとする． とする．このとき， は双対問題 (D) の最適解であることを示せ．

(v) 問題 (Q) は となる最適解 を持つとする．このとき， となる (D) の最適解 が存在することを示せ．

English Version

Kai

(i)

Lagrangian:

Lagrange dual function:

where

(ii)

For (D), , is feasible , hence (Q) has optimal value .

Hence (Q) is bounded, and therefore has an optimal value.

(iii)

For , we have . Since duality gap is zero, for , when and , is attained.

(iv)

we know

then

since

is an optimal solution to

(v)

we have

(D) has optimal solution , let , , then we have

i.e., is such an optimal solution