東京工業大学 情報理工学院 数理・計算科学系 2019年度 午前 問4

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} \]

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\) である。