東京工業大学情報理工学院数理・計算科学系 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$ の関数として表せ．

考虑下列含实参数 $\theta$ 的线性规划：

\mathcal P(\theta):\quad \begin{cases} \max:\ &6x_1+(-3+\theta)x_2+(4+\theta)x_3,\\ \text{约束条件：} &-3x_1+2x_2-4x_3\leq5,\\ &2x_1+2x_2+x_3\leq2,\\ &4x_1+2x_2+3x_3\leq5,\\ &x_1,x_2,x_3\geq0. \end{cases}

分别用

(x_1^*(\theta),x_2^*(\theta),x_3^*(\theta)) \quad\text{和}\quad z^*(\theta)

表示 $\mathcal P(\theta)$ 的最优解和最优值。回答：

在 $\theta=0$ 时，求 $(x_1^*(0),x_2^*(0),x_3^*(0))$ 以及 $z^*(0)$ 。
求所有使第 1 问所得解 $(x_1^*(0),x_2^*(0),x_3^*(0))$ 对 $\mathcal P(\theta)$ 仍然最优的 $\theta$ 。
对第 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}