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

Author

Casablanca

Description

日本語版

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

ただし, は 定数行列, は 次元定数ベクトル, は 次元定数ベクトル, は 次元定数ベクトルであり, は転置記号を表す。さらに, 問題 に関連して, 非負パラメータ を含む次の条件 を考える。

ただし, である。各 に対して, 条件 を満たすベクトル は唯一存在すると仮定し, それらを と表す。

  以下の問いに答えよ。

(i) 問題 の双対問題をかけ。

(ii) 関数 を と定義する。関数 は 上で線形関数となることを示せ。

(iii) は問題 の最適解となることを示せ。

(iv) とし,

とする。このとき, 任意の非負パラメータ に対して, 条件 を満たすベクトル は唯一存在する。 を求めよ。さらに, 問 (i) で与えた双対問題の最適解を求めよ。

English Version

Kai

(i)

Lagrangian:

Lagrange dual function

The dual problem

(ii)

thus is linear on .

(iii)

Consider , get .

Since

satisfies the constraint of (D). Thus is an optimal solution to P.

(iv)

and we get

for

then we get an optimal solution .