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

标签：

• TITech
• Linear-Programming-Duality
• Simplex-Method

Author

祭音Myyura

Description

次の線形計画問題 $\mathcal{P}$ を考える：

$$\begin{aligned} \text{maximize} &: &\boldsymbol{c}^T \boldsymbol{x} \\ \mathcal{P} : \quad \text{subject to} &: &\boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b} \\ &\ &\boldsymbol{x} \geq \boldsymbol{0}. \end{aligned}$$

ただし， $\mathcal{P}$ の変数は $\boldsymbol{x} \in \mathbb{R}^n$ であり，入力は $\boldsymbol{A} \in \mathbb{R}^{m \times n}, \boldsymbol{b} \in \mathbb{R}^m, \boldsymbol{c} \in \mathbb{R}^n$ である． また，上付き添え字 $T$ はベクトルまたは行列の転置を表し， $\boldsymbol{x} \geq \boldsymbol{0}$ はベクトル $\boldsymbol{x}$ の各要素が非負であることを示す．

(1) $\mathcal{P}$ の双対問題 $\mathcal{D}$ を書け．ただし， $\mathcal{D}$ の変数は $\boldsymbol{y} \in \mathbb{R}^m$ とする．

(2) $\mathcal{P}$ と $\mathcal{D}$ が実行可能であると仮定し， $\overline{\boldsymbol{x}}$ と $\overline{\boldsymbol{y}}$ をそれぞれ $\mathcal{P}$ と $\mathcal{D}$ の実行可能解とする． このとき， $\boldsymbol{c}^T \overline{\boldsymbol{x}} \leq \boldsymbol{b}^T \overline{\boldsymbol{y}}$ を示せ．（つまり，弱双対定理を示せ．）

(3) 以下の入力のときの $\mathcal{P}$ の最適解と最適値を求めよ．

$$\boldsymbol{A} = \begin{pmatrix} 1 & 1 & 8 & 4 \\ 4 & -3 & -2 & -3 \end{pmatrix}, \quad \boldsymbol{b} = \begin{pmatrix} 9 \\ 8 \end{pmatrix}, \quad \boldsymbol{c} = \begin{pmatrix} 5 \\ 2 \\ 3 \\ 1 \end{pmatrix}$$

题目描述

给定标准形式的线性规划

$$\begin{aligned} \text{maximize}\quad&\boldsymbol c^{\mathsf T}\boldsymbol x,\\ \mathcal P:\quad\text{subject to}\quad &\boldsymbol A\boldsymbol x\leq\boldsymbol b,\\ &\boldsymbol x\geq\boldsymbol0. \end{aligned}$$

其中决策变量 $\boldsymbol x\in\mathbb R^n$，输入数据为 $\boldsymbol A\in\mathbb R^{m\times n}$、$\boldsymbol b\in\mathbb R^m$ 和 $\boldsymbol c\in\mathbb R^n$。上标 $\mathsf T$ 表示转置；向量不等式 $\boldsymbol x\geq\boldsymbol0$ 表示每个分量都非负。

1. 以 $\boldsymbol y\in\mathbb R^m$ 为变量，写出 $\mathcal P$ 的对偶问题 $\mathcal D$。
2. 假设 $\mathcal P$ 和 $\mathcal D$ 均可行，且 $\overline{\boldsymbol x}$、$\overline{\boldsymbol y}$ 分别是它们的可行解。证明弱对偶关系

$$\boldsymbol c^{\mathsf T}\overline{\boldsymbol x} \leq\boldsymbol b^{\mathsf T}\overline{\boldsymbol y}.$$

3. 当输入具体为

$$\boldsymbol A= \begin{pmatrix} 1&1&8&4\\ 4&-3&-2&-3 \end{pmatrix}, \qquad \boldsymbol b=\begin{pmatrix}9\\8\end{pmatrix}, \qquad \boldsymbol c=\begin{pmatrix}5\\2\\3\\1\end{pmatrix},$$

求 $\mathcal P$ 的最优解和最优值。

Kai

(1)

$$\begin{aligned} \text{minimize} &: &\boldsymbol{b}^T \boldsymbol{y} \\ \mathcal{D} : \quad \text{subject to} &: &\boldsymbol{A}^T \boldsymbol{y} \geq \boldsymbol{c} \\ &\ &\boldsymbol{y} \geq \boldsymbol{0}. \end{aligned}$$

(2)

$\overline{\boldsymbol{x}}$ が $\mathcal{P}$ の実行可能解なので、 $\boldsymbol{A} \overline{\boldsymbol{x}} \leq \boldsymbol{b}$ 。

$\overline{\boldsymbol{y}}$ が $\mathcal{D}$ の実行可能解なので、 $\boldsymbol{A}^T \overline{\boldsymbol{y}} \geq \boldsymbol{c}$ 。

よって、

$$\begin{aligned} \boldsymbol{c}^T \overline{\boldsymbol{x}} \leq (\boldsymbol{A}^T \overline{\boldsymbol{y}})^T \overline{\boldsymbol{x}} = \overline{\boldsymbol{y}}^T \boldsymbol{A} \overline{\boldsymbol{x}} \leq \overline{\boldsymbol{y}}^T \boldsymbol{b} = \boldsymbol{b}^T \overline{\boldsymbol{y}} \end{aligned}$$

(3)

シンプレックス法で解くと、

$$\boldsymbol{x} = \begin{pmatrix} 5 \\ 4 \\ 0 \\ 0 \end{pmatrix}$$

を得る。実行可能な双対解

$$\boldsymbol{y}=\begin{pmatrix}23/7\\3/7\end{pmatrix}$$

に対して $\boldsymbol{A}^T\boldsymbol{y}\geq\boldsymbol{c}$ かつ $\boldsymbol{b}^T\boldsymbol{y}=33=\boldsymbol{c}^T\boldsymbol{x}$ であるから、弱双対性より最適値は $33$ である。