跳到主要内容

京都大学 情報学研究科 数理工学専攻 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​

题目描述​

回答下列两问。

  1. 考虑互为原、对偶的线性规划
    (P1):最小化c⊤x满足Ax=b,x≧0,\begin{aligned} (\mathrm{P1}):\quad&\text{最小化}\quad \boldsymbol c^\top\boldsymbol x\\ &\text{满足}\quad \boldsymbol A\boldsymbol x=\boldsymbol b,\quad \boldsymbol x\geqq\boldsymbol0, \end{aligned}
    (D1):最大化b⊤w满足A⊤w≦c.\begin{aligned} (\mathrm{D1}):\quad&\text{最大化}\quad \boldsymbol b^\top\boldsymbol w\\ &\text{满足}\quad \boldsymbol A^\top\boldsymbol w\leqq\boldsymbol c. \end{aligned}
    其中 A\boldsymbol A 为 m×nm\times n 常数矩阵，b,c\boldsymbol b,\boldsymbol c 分别为 mm 维、nn 维常向量，x,w\boldsymbol x,\boldsymbol w 分别为 nn 维、mm 维变量向量，⊤\top 表示转置。假设 P1、D1 分别有最优解 x∗,w∗\boldsymbol x^*,\boldsymbol w^*，并令 y∗=c−A⊤w∗\boldsymbol y^*=\boldsymbol c-\boldsymbol A^\top\boldsymbol w^*。证明：若 xi∗>0x_i^*>0，则 yi∗=0y_i^*=0。
  2. 考虑线性规划
    (P2):最大化x5满足∑i=14xi≦1,∑i=k+14xi≦kxk(k=1,2,3),x5≦4x4.\begin{aligned} (\mathrm{P2}):\quad&\text{最大化}\quad x_5\\ &\text{满足}\quad \sum_{i=1}^4x_i\leqq1,\\ &\hspace{2.8em}\sum_{i=k+1}^4x_i\leqq kx_k\quad(k=1,2,3),\\ &\hspace{2.8em}x_5\leqq4x_4. \end{aligned}
    设其最优解为 x∗\boldsymbol x^*。求 P2 的对偶问题的最优解，并证明 ∑i=14xi∗=1\sum_{i=1}^4x_i^*=1。

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
本页目录