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

标签：

Author

実数 $\theta$ をパラメータとする次の線形計画問題 $\mathcal{P}(\theta)$ を考える：

\mathcal{P}(\theta) \ : \ \begin{cases} &\max \ : \ 6x_1 + (-3 + \theta)x_2 + (4+\theta)x_3 \\ &\text{constraints} \ : \\ &-3x_1 + 2x_2 - 4x_3 \leq 5 \\ &2x_1 + 2x_2 + x_3 \leq 2 \\ &4x_1 + 2x_2 + 3x_3 \leq 5 \\ & x_1, x_2, x_3 \geq 0 \end{cases}

$\mathcal{P}(\theta)$ の最適解と最適値をそれぞれ $(x_1^*(\theta), x_2^*(\theta), x_3^*(\theta))$ と $z^*(\theta)$ とする．以下の問に答えよ．

(1) $\theta = 0$ のときの最適解 $(x_1^*(0), x_2^*(0), x_3^*(0))$ と $z^*(0)$ を求めよ．

(2) $(x_1^*(0), x_2^*(0), x_3^*(0))$ が $\mathcal{P}(\theta)$ の最適解でもあるような $\theta$ の範囲を求めよ．

(3) (2) で求めた $\theta$ の範囲において， $z^∗(\theta)$ を $\theta$ の関数として表せ．

初期辞書

\begin{aligned} &z = 6x_1 - 3x_2 + 4x_3 \\ &x_4 = 5 + 3x_1 - 2x_2 + 4x_3 \\ &x_5 = 2 - 2x_1 -2x_2 -x_3 \\ &x_6 = 5 - 4x_1 -2x_2 -3x_3 \end{aligned}

最適辞書

\begin{aligned} &z = 7 - 7x_2 -x_5 - x_6 \\ &x_1 = \frac{1}{2} - 2x_2 - \frac{3}{2}x_5 + \frac{1}{2}x_6 \\ &x_3 = 1 + 2x_2 + 2x_5 - x_6 \\ &x_4 = \frac{21}{2} + \frac{7}{2}x_5 - \frac{5}{2}x_6 \end{aligned}

よって、

z^* = 7, (x_1^*(0), x_2^*(0), x_3^*(0)) = (\frac{1}{2}, 0, 1)

b = \begin{pmatrix} 5 \\ 2 \\ 5 \end{pmatrix}, x_B = \begin{pmatrix} x_1 \\ x_3 \\ x_4 \end{pmatrix}, x_N = \begin{pmatrix} x_2 \\ x_5 \\ x_6 \end{pmatrix}, c_B = \begin{pmatrix} 6 \\ 4 + \theta \\ 0 \end{pmatrix}, c_N = \begin{pmatrix} -3 + \theta \\ 0 \\ 0 \end{pmatrix}

B = \begin{pmatrix} -3 & -4 & 1 \\ 2 & 1 & 0 \\ 4 & 3 & 0 \end{pmatrix}, N = \begin{pmatrix} 2 & 0 & 0 \\ 2 & 1 & 0 \\ 2 & 0 & 1 \end{pmatrix}

とすると、最適辞書

\begin{aligned} z &= c_B^T B^{-1}b + (c_N^T - c_B^T B^{-1} N) x_N \\ x_B &= B^{-1}b - B^{-1}N x_N \end{aligned}

題意より、 $B^{-1}b \geq 0$ かつ $c_N^T - c_B^TB^{-1}N \leq 0$ 。よって、 $-1 \leq \theta \leq 1/2$ 。

\begin{aligned} z^*(\theta) &= 6x_1^*(0) + (-3 + \theta)x_2^*(0) + (4+\theta)x_3^*(0) \\ &= 7 + \theta \end{aligned}