東京工業大学 情報理工学院 数理・計算科学系 2018年度 午前 問4
Author
Description
実数 \(\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\) の関数として表せ．
Kai
(1)
初期辞書
\[
\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)
\]
(2)
\[
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\)。
(3)
\[
\begin{aligned}
z^*(\theta) &= 6x_1^*(0) + (-3 + \theta)x_2^*(0) + (4+\theta)x_3^*(0) \\
&= 7 + \theta
\end{aligned}
\]