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

Author

Casablanca

Description

日本語版

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

ここで、決定変数は であり、 は転置記号を表す。

問題 の最適解の集合を とする。 さらに、 を空集合、 を整数全体の集合、

とする。以下の問いに答えよ。

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

(ii) 任意の に対して であることを示せ。

(iii) 任意の に対して であることを示せ。

(iv) 次の命題 (A) について、真であれば証明を、偽であれば反例を与えよ。

• (A) 任意の に対して である。

English Version

Kai

(i)

Let

Lagrangian:

Lagrange dual function:

Dual problem:

(ii)

The extreme point is , , , , and there is no extreme direction. Hence the domain is bounded, thus

(iii)

Suppose that is an optimal solution, then we have

where , , is extreme point shown in (ii).

First we have , else is not a optimal solution. If for , then

But according to

a contradiction.

Thus there is at least one extreme point such that .

Therefore

(iv)

Let , then is also a solution.