東京工業大学 情報理工学院 数理・計算科学系 2021年8月実施 运筹学

标签：

• TITech
• Simplex-Method
• Linear-Programming-Problem

Author

思齐塾, 祭音Myyura

Description

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

$$(P) \quad \begin{matrix} \text{最大化} & : & \boldsymbol{c}^T \boldsymbol{x} \\ \text{制約} & : & \boldsymbol{Ax} \le \boldsymbol{b} \\ & & \boldsymbol{x} \ge \mathbf{0} \end{matrix}$$

ただし， $\boldsymbol{A} \in \mathbb{R}^{m \times n}, \boldsymbol{b} \in \mathbb{R}^m, \boldsymbol{c} \in \mathbb{R}^n$ は入力データであり， $\boldsymbol{x} \in \mathbb{R}^n$ は変数ベクトルである．また， $\mathbf{0}$ はゼロベクトルである．上付き添え字の $T$ はベクトルの転置を表し，ベクトル $\boldsymbol{u}, \boldsymbol{v}$ に対して $\boldsymbol{u} \le \boldsymbol{v}$ は成分ごとの不等式を表す． 以下の問いに答えよ．

(1) $\boldsymbol{b} = \mathbf{0}$ のとき， $(P)$ が実行可能解を持つことを示せ．

(2) $\boldsymbol{b} = \mathbf{0}$ のとき， $(P)$ に最適解が存在すれば，最適値は 0 であることを示せ．

(3) 入力データが

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

で与えられているときに， $(P)$ の最適解を求めよ．

题目描述

考虑线性规划

$$(P)\quad \begin{array}{lll} \text{最大化}&:&\boldsymbol c^\top\boldsymbol x,\\ \text{约束条件}&:&\boldsymbol A\boldsymbol x\leq\boldsymbol b,\\ &&\boldsymbol x\geq\boldsymbol0. \end{array}$$

其中 $\boldsymbol A\in\mathbb R^{m\times n}$、$\boldsymbol b\in\mathbb R^m$、$\boldsymbol c\in\mathbb R^n$ 是输入，$\boldsymbol x\in\mathbb R^n$ 是变量，$\boldsymbol0$ 是零向量，上标 $\top$ 表示转置；向量不等式按分量理解。

1. 当 $\boldsymbol b=\boldsymbol0$ 时，证明 $(P)$ 至少有一个可行解。
2. 当 $\boldsymbol b=\boldsymbol0$ 时，证明只要 $(P)$ 存在最优解，其最优值必为 $0$。
3. 对输入

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

求 $(P)$ 的最优解。

Kai

(1)

$\boldsymbol{b}=\mathbf0$ のとき $\boldsymbol{x}=\mathbf0$ と取れば

$$A\boldsymbol{x}=\mathbf0\le\mathbf0=\boldsymbol b,\qquad \boldsymbol{x}=\mathbf0\ge\mathbf0.$$

したがって $\boldsymbol{x}=\mathbf0$ は実行可能解であり， $(P)$ は必ず実行可能解を持つ。

(2)

零ベクトルが実行可能なので，最適値が存在すればそれは少なくとも0である。最適解を $\boldsymbol{x}^*$ とし，仮に $\boldsymbol{c}^T\boldsymbol{x}^*>0$ とする。任意の $t>1$ に対して

$$A(t\boldsymbol{x}^*)=tA\boldsymbol{x}^*\le\mathbf0,\qquad t\boldsymbol{x}^*\ge\mathbf0$$

だから $t\boldsymbol{x}^*$ も実行可能であり，その目的値 $t\boldsymbol{c}^T\boldsymbol{x}^*$ はより大きい。これは最適性に反する。目的値が負なら零ベクトルの方が良いので，結局

$$\boxed{\text{最適値は }0}$$

でなければならない。

(3)

目的関数は

$$3x_1-2x_2-2x_3-2x_4$$

である。任意の実行可能解から $x_2,x_4$ だけを0にすると，二つの制約の左辺はいずれも増加せず，目的値は増加する。従って最適解では $x_2=x_4=0$ としてよい。

残る問題は

$$\max\ 3x_1-2x_3,\qquad x_1+x_3\le7,\quad x_1-x_3\le4,\quad x_1,x_3\ge0.$$

固定した $x_3$ に対して目的値は $x_1$ とともに増えるので

$$x_1=\min\{7-x_3,\,4+x_3\}.$$

二つの上界の交点は

$$7-x_3=4+x_3 \quad\Longrightarrow\quad x_3=\frac32,\quad x_1=\frac{11}{2}.$$

$0\le x_3\le3/2$ では目的値は $12+x_3$ と増加し， $x_3\ge3/2$ では $21-5x_3$ と減少するので，この交点が大域的最適点である。したがって

$$\boxed{\boldsymbol{x}^*=\begin{pmatrix}11/2\\0\\3/2\\0\end{pmatrix}}, \qquad \boxed{\boldsymbol{c}^T\boldsymbol{x}^*=\frac{27}{2}}.$$

両制約はこの点で等号となるので，実行可能性も直接確認できる。