跳到主要内容

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

标签：

Author​

Casablanca

Description​

日本語版​

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

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

(P1):Minimizec⊤xsubject toAx=b x≧0\begin{aligned} \text{(P1)}: &\text{Minimize} &\boldsymbol{c}^{\top} \boldsymbol{x} \\ &\text{subject to} &\boldsymbol{A}\boldsymbol{x} = \boldsymbol{b} \\ &\text{ } &\boldsymbol{x} \geqq \boldsymbol{0} \end{aligned}
(D1):Maximizeb⊤wsubject toA⊤w≦c\begin{aligned} \text{(D1)}: &\text{Maximize} &\boldsymbol{b}^{\top} \boldsymbol{w} \\ &\text{subject to} &\boldsymbol{A}^{\top} \boldsymbol{w} \leqq \boldsymbol{c} \end{aligned}

ここで、A\boldsymbol{A} は m×nm \times n 定数行列、b\boldsymbol{b} は mm 次元定数ベクトル、c\boldsymbol{c} は nn 次元定数ベクトル、x\boldsymbol{x} は nn 次元変数ベクトル、w\boldsymbol{w} は mm 次元変数ベクトルであり、⊤\top は転置記号を表す。 問題 (P1) と (D1) は最適解 x∗\boldsymbol{x}^* と w∗\boldsymbol{w}^* を持つとする。 さらに y∗=c−A⊤w∗\boldsymbol{y}^* = \boldsymbol{c} - \boldsymbol{A}^{\top} \boldsymbol{w}^* とする。 このとき、xi∗>0x_i^* > 0 であれば、yi∗=0y_i^* = 0 が成り立つことを示せ。

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

(P2):Maximizex5subject to∑i=14xi≦1 ∑i=k+14xi≦kxk (k=1,2,3) x5≦4x4\begin{aligned} \text{(P2)}: &\text{Maximize} &x_5 \\ &\text{subject to} &\sum_{i=1}^4 x_i \leqq 1 \\ &\text{ } &\sum_{i=k+1}^4 x_i \leqq kx_k \ (k=1,2,3) \\ &\text{ } &x_5 \leqq 4x_4 \end{aligned}

問題 (P2) の最適解を x∗\boldsymbol{x}^* とする。問題 (P2) の双対問題の最適解を求めよ。さらに、

∑i=14xi∗=1\sum_{i=1}^4 x_i^* = 1

が成り立つことを示せ。

English Version​

Kai​

(i)​

(x∗)⊤y∗=C⊤x∗−(Ax∗)⊤w∗=C⊤x∗−b⊤w∗=0\begin{aligned} (x^*)^{\top}y* &= C^\top x^* - (Ax^*)^\top w^* \\ &= C^\top x^* - b^\top w^* \\ & = 0 \end{aligned}

since x∗⪰0x^* \succeq \boldsymbol{0} and y∗=C−A⊤w∗⪰0y^* = C - A^\top w^* \succeq \boldsymbol{0}, hence if x∗≻0x^* \succ \boldsymbol{0},

y∗=0y^* = \boldsymbol{0}

(ii)​

Let x=[x1,x2,x3,x4,x5]⊤x = [x_1, x_2, x_3, x_4, x_5]^\top, the problem (P2) can be written as

Minimize−[0,0,0,0,1]xSubject to[11110−111100−211000−310000−41]x⪯[10000]\begin{aligned} &\text{Minimize} &- [0,0,0,0,1]x\\ &\text{Subject to} &\begin{bmatrix} 1 &1 &1 & 1 &0\\ -1&1 &1 &1 &0 \\ 0 &-2 &1 &1 &0 \\ 0 &0 &-3 &1 &0\\ 0 &0 &0 &-4 &1 \end{bmatrix} \boldsymbol{x} \preceq \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} \end{aligned}

Denote as

Minimize−c⊤xSubject toAx⪯b\begin{aligned} &\text{Minimize} &-c^\top x \\ &\text{Subject to} &A\boldsymbol{x} \preceq b \end{aligned}

Lagrangian:

L(x,λ)=−c⊤x+λ⊤(Ax−b)L(x, \lambda) = -c^\top x + \lambda ^\top (Ax - b)

Lagrange dual function:

d(λ)=−b⊤λd(\lambda) = -b^\top \lambda

An optimal solution of dual problem is λ⊤=[1,1,1,1,1]\lambda ^\top = [1,1,1,1,1]. Since

−c⊤x=−1,x5=1-c^\top x = -1, x_5 = 1

By solving Ax=bAx = b, we get

∑i=14xi∗=1\sum_{i=1}^{4}x_i^* = 1
本页目录