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

Author

Casablanca

Description

日本語版

パラメータ をもつ次の線形計画問題 を考える．

ただし， の決定変数は であり， は転置記号を表す．

以下の問 (i) と (ii) に答えよ．

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

(ii) 任意の に対して，問題 が最適解をもつことを示せ．

与えられた に対して，問題 の最適値 (最大値) を とする．

以下の問 (iii) と (iv) に答えよ．

(iii) 任意の と に対して，次の不等式が成り立つことを示せ．

(iv) 次の最適化問題 Q を考える．

ただし，Q の決定変数は である．問題 Q の最適値 (最小値) は であることを示せ．

English Version

Kai

(i)

The dual problem:

(ii)

From (D), we have . Thus for any , .

Hence (D) has an optimal solution. Hence (P) also has an optimal solution according to duality.

(iii)

(iv)

We write Q as:

And further, let , we get

Obviously,

and when , .