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

Author

Casablanca

Description

日本語版

と を 行列とする。さらに の第 成分を とする。

  以下のパラメータ をもつ線形計画問題 とパラメータ をもつ線形計画問題 を考える。

ただし, の決定変数は であり, の決定変数は である。また, は転置記号を表す。

  問題 のすべての最適解の集合を とし, 問題 のすべての最適解の集合を とする。さらに, とする。

  以下の問いに答えよ。

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

(ii) を であるベクトルとする。このとき, であることを示せ。

(iii) とする。このとき, すべての に対して となることを示せ。

(iv) を かつ であるベクトルとする。このとき, を求めよ。

(v) とする。このとき, を求めよ。

English Version

Kai

(i)

Lagrangian:

Lagrange dual function:

Dual proble :

(ii)

from (i) we know , for , obviously , from strong duality, ,

(iii)

according to the constraint, , from .

If , then .

If , then , otherwise , which is conflict with .

Thus always holds.

(iv)

Let . Then we have

The KKT_conditions:

And satisfies the KKT-conditions, thus , and

hence .

(v)

Consider and .

For , if , then . Similarly, when . Thus .

Then, we consider the case when .

Therefore, .