跳到主要内容

東京工業大学 情報理工学院 数理・計算科学系 2023年8月実施 午前 問4

标签：

Author​

思齐塾, 祭音Myyura

Description​

以下の線形計画問題 (P) を考える．

(P)maxcTxs.t.Ax≤b.\begin{aligned} \text{(P)} \quad \text{max} \quad & \boldsymbol{c}^T \boldsymbol{x} \\ \text{s.t.} \quad & \boldsymbol{Ax} \le \boldsymbol{b}. \end{aligned}

ただし， A∈Rm×n,b∈Rm,c∈Rn\boldsymbol{A} \in \mathbb{R}^{m \times n}, \boldsymbol{b} \in \mathbb{R}^m, \boldsymbol{c} \in \mathbb{R}^n は入力データであり， x∈Rn\boldsymbol{x} \in \mathbb{R}^n は変数ベクトルである．また，上付き添字の ⊤\top はベクトルの転置を表し，ベクトル y,z\boldsymbol{y}, \boldsymbol{z} に対して y≤z\boldsymbol{y} \le \boldsymbol{z} は成分ごとの不等式を表す．問題 (P) に最適解があると仮定し，以下の問いに答えよ．

(1) 入力データが

A=[−121110],b=[543],c=[22]\boldsymbol{A} = \begin{bmatrix} -1 & 2 \\ 1 & 1 \\ 1 & 0 \end{bmatrix}, \quad \boldsymbol{b} = \begin{bmatrix} 5 \\ 4 \\ 3 \end{bmatrix}, \quad \boldsymbol{c} = \begin{bmatrix} 2 \\ 2 \end{bmatrix}

のときの最適解の集合を図示し，全端点の座標も求めよ．ここで，凸集合 SS の端点とは， SS の点 p\boldsymbol{p} で，任意の q,r∈S\boldsymbol{q}, \boldsymbol{r} \in S に対して p=q+r2\boldsymbol{p} = \frac{\boldsymbol{q} + \boldsymbol{r}}{2} ならば p=q=r\boldsymbol{p} = \boldsymbol{q} = \boldsymbol{r} が成り立つ点のことである．

(2) 一般に (P) の最適解の集合は凸集合であることを示せ．

(3) (P) の最適解 x\boldsymbol{x} が (P) の実行可能解 y1,y2,…,yk\boldsymbol{y}_1, \boldsymbol{y}_2, \dots, \boldsymbol{y}_k を用いて x=∑i=1kλiyi\boldsymbol{x} = \sum_{i=1}^k \lambda_i \boldsymbol{y}_i と表されるとする．ただし kk は正の整数であり， λ1,λ2,…,λk\lambda_1, \lambda_2, \dots, \lambda_k は正の実数で ∑i=1kλi=1\sum_{i=1}^k \lambda_i = 1 を満たすとする．このとき， y1,y2,…,yk\boldsymbol{y}_1, \boldsymbol{y}_2, \dots, \boldsymbol{y}_k も (P) の最適解であることを示せ．

(4) (P) に最適解は存在するが最適解の集合が端点をもたない入力データ (A,b,c)(\boldsymbol{A}, \boldsymbol{b}, \boldsymbol{c}) の例をひとつ挙げて，そのような例になっている理由を説明せよ．ただし，例では n=2n=2 とし c\boldsymbol{c} は非ゼロベクトルとすること．

题目描述​

考虑线性规划

(P)max⁡c⊤x,s.t.Ax≤b,\begin{aligned} \text{(P)}\qquad \max\quad&\boldsymbol c^\top\boldsymbol x,\\ \text{s.t.}\quad&\boldsymbol A\boldsymbol x\leq\boldsymbol b, \end{aligned}

其中 A∈Rm×n\boldsymbol A\in\mathbb R^{m\times n}、b∈Rm\boldsymbol b\in\mathbb R^m、c∈Rn\boldsymbol c\in\mathbb R^n 为输入，x∈Rn\boldsymbol x\in\mathbb R^n 为变量；上标 ⊤\top 表示转置，向量不等式按分量理解。题目假设 (P) 存在最优解；变量没有另行给出非负约束。

  1. 当
A=[−121110],b=[543],c=[22]\boldsymbol A= \begin{bmatrix} -1&2\\ 1&1\\ 1&0 \end{bmatrix}, \qquad \boldsymbol b=\begin{bmatrix}5\\4\\3\end{bmatrix}, \qquad \boldsymbol c=\begin{bmatrix}2\\2\end{bmatrix}

时，画出最优解集合并求其全部端点。这里，凸集 SS 中的点 p\boldsymbol p 称为端点，是指对任意 q,r∈S\boldsymbol q,\boldsymbol r\in S，若

p=q+r2,\boldsymbol p=\frac{\boldsymbol q+\boldsymbol r}{2},

就必有 p=q=r\boldsymbol p=\boldsymbol q=\boldsymbol r。 2. 对一般的输入，证明 (P) 的最优解集合是凸集。 3. 设最优解 x\boldsymbol x 能写成可行解 y1,…,yk\boldsymbol y_1,\ldots,\boldsymbol y_k 的严格凸组合

x=∑i=1kλiyi,λi>0,∑i=1kλi=1,\boldsymbol x=\sum_{i=1}^k\lambda_i\boldsymbol y_i, \qquad \lambda_i>0,\quad \sum_{i=1}^k\lambda_i=1,

其中 kk 为正整数。证明每个 yi\boldsymbol y_i 也都是 (P) 的最优解。 4. 给出一组输入 (A,b,c)(\boldsymbol A,\boldsymbol b,\boldsymbol c)，使 (P) 有最优解，但最优解集合没有端点，并解释原因。例子必须满足 n=2n=2 且 c≠0\boldsymbol c\neq\boldsymbol0。

Kai​

解答​

(x1,x2)=(x,y)(x_1,x_2)=(x,y) と書く。

(1) 最適解集合​

制約と目的関数は

−x+2y≤5,x+y≤4,x≤3,cTx=2(x+y)-x+2y\le5, \qquad x+y\le4, \qquad x\le3, \qquad \boldsymbol c^T\boldsymbol x=2(x+y)

である。第2制約から目的値は高々8である。直線 x+y=4x+y=4 上では y=4−xy=4-x なので、第1・第3制約は

−x+2(4−x)≤5  ⟺  x≥1,x≤3-x+2(4-x)\le5\iff x\ge1, \qquad x\le3

となる。よって最大値は8で、最適解集合は

S∗={(x,4−x)∣1≤x≤3}\boxed{S^*=\{(x,4-x)\mid1\le x\le3\}}

という線分である。図では直線 x+y=4x+y=4 上の (1,3)(1,3) と (3,1)(3,1) を結ぶ閉線分となり、その全端点は

(1,3), (3,1).\boxed{(1,3),\ (3,1)}.

両端以外の点はこの2点の非自明な凸結合なので端点ではなく、両端は線分の端なので定義を満たす。

最適解集合の閉線分

(2) 凸性​

最適値を α\alpha とし、最適解 x,y\boldsymbol x,\boldsymbol y と 0≤λ≤10\le\lambda\le1 を取る。すると

A(λx+(1−λ)y)≤λb+(1−λ)b=bA(\lambda\boldsymbol x+(1-\lambda)\boldsymbol y) \le\lambda\boldsymbol b+(1-\lambda)\boldsymbol b=\boldsymbol b

だから凸結合も実行可能である。また

cT(λx+(1−λ)y)=λα+(1−λ)α=α.\boldsymbol c^T(\lambda\boldsymbol x+(1-\lambda)\boldsymbol y) =\lambda\alpha+(1-\lambda)\alpha=\alpha.

よって凸結合も最適解であり、最適解集合は凸集合である。

(3)​

各 yi\boldsymbol y_i は実行可能なので cTyi≤α\boldsymbol c^T\boldsymbol y_i\le\alpha である。一方

α=cTx=∑i=1kλicTyi.\alpha=\boldsymbol c^T\boldsymbol x =\sum_{i=1}^k\lambda_i\boldsymbol c^T\boldsymbol y_i.

正の重みによる、すべて α\alpha 以下の数の加重平均が α\alpha なので、各項が cTyi=α\boldsymbol c^T\boldsymbol y_i=\alpha でなければならない。従って y1,…,yk はすべて最適解\boxed{\boldsymbol y_1,\ldots,\boldsymbol y_k\text{ はすべて最適解}} である。

(4) 端点をもたない例​

n=2n=2 , m=1m=1 として

A=[10],b=0,c=[10]A=\begin{bmatrix}1&0\end{bmatrix}, \qquad b=0, \qquad \boldsymbol c=\begin{bmatrix}1\\0\end{bmatrix}

を取る。 x1≤0x_1\le0 の下で x1x_1 を最大化する問題なので、最適値は0、最適解集合は

S∗={(0,t)∣t∈R}S^*=\{(0,t)\mid t\in\mathbb R\}

という直線である。任意の (0,t)(0,t) は異なる2点 (0,t−1),(0,t+1)(0,t-1),(0,t+1) の中点なので端点ではない。従って最適解は存在するが最適解集合に端点はなく、 c≠0\boldsymbol c\ne\boldsymbol0 も満たす。

本页目录