東京工業大学 情報理工学院 数理・計算科学系 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{最大化}\quad&\boldsymbol c^{\mathsf T}\boldsymbol x\\ \mathcal P:\quad\text{满足}\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$ 表示 $\boldsymbol x$ 的每个分量均非负。

1. 写出 $\mathcal P$ 的对偶问题 $\mathcal D$，并以 $\boldsymbol y\in\mathbb R^m$ 作为其变量。

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. 对下列输入，求 $\mathcal P$ 的最优解和最优值：

   $$\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}.$$

考点

• 线性规划对偶：由标准最大化形式写出对偶变量符号、约束方向和目标函数。
• 弱对偶定理：把原、对偶可行性不等式与非负性组合，比较任意一对可行解的目标值。
• 单纯形法：对给定矩阵数据引入松弛变量并换基，求出最优基本可行解及目标值。

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}} \leq \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}$$

を得る。最適値は $33$ である。