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

Author

Casablanca

Description

日本語版

以下の (i), (ii) に答えよ。

(i) 次の線形計画問題 (P1) とその双対問題 (D1) を考える。

ここで、 は 定数行列、 は 次元定数ベクトル、 は 次元定数ベクトル、 は 次元変数ベクトル、 は 次元変数ベクトルであり、 は転置記号を表す。 問題 (P1) と (D1) は最適解 と を持つとする。 さらに とする。 このとき、 であれば、 が成り立つことを示せ。

(ii) 次の線形計画問題を考える。

問題 (P2) の最適解を とする。問題 (P2) の双対問題の最適解を求めよ。さらに、

が成り立つことを示せ。

English Version

Kai

(i)

since and , hence if ,

(ii)

Let , the problem (P2) can be written as

Denote as

Lagrangian:

d(\lambda) = -b^\top \lambda

-c^\top x = -1, x_5 = 1

\sum_{i=1}^{4}x_i^* = 1