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

Author

Casablanca

Description

日本語版

を 行列、 を 次元ベクトルとする。 を満たす 次元ベクトル が存在するとする。 このとき、次の線形計画問題 (P) を考える。

ただし、決定変数は である。

以下の問いに答えよ。

(i) 問題 (P) の双対問題を書け。

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

(iii) とし、

とする。このとき、問題 (P) の最適解を求めよ。

English Version

Kai

(i)

Lagrangina:

(ii)

For a given , , is bounded, thus (P) is bounded, and therefore has an optimal solution.

(iii)