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

标签：

Author

思齐塾, 祭音Myyura

パラメータ $s \in \mathbb{R}$ を含んだ線形計画問題

\begin{aligned} \text{最大化} \quad & : (7 + 6s)x_1 - 4x_2 + (4 - 3s)x_3 \\ \text{制約} \quad & : \begin{aligned} x_4 & = 1 - 3s - x_1 - 5x_2 - x_3 \\ x_5 & = 1 + 6s - 2x_1 + 4x_2 + 4x_3 \\ x_1, x_2, x_3, x_4, x_5 & \ge 0 \end{aligned} \end{aligned}

に対して，以下の問に答えよ．

(1) $s = 0$ のとき，最適解が $x_2 = x_4 = x_5 = 0$ を満たすことを示せ．

(2) $x_2 = x_4 = x_5 = 0$ を満たす最適解が存在する $s$ の範囲を示せ．

考虑含实参数 $s$ 的线性规划问题

\begin{aligned} \text{最大化}\quad &(7+6s)x_1-4x_2+(4-3s)x_3,\\ \text{约束条件}\quad &x_4=1-3s-x_1-5x_2-x_3,\\ &x_5=1+6s-2x_1+4x_2+4x_3,\\ &x_1,x_2,x_3,x_4,x_5\geq0. \end{aligned}

2本の等式を $x_1,x_3$ について解くと、任意の実行可能解に対して

\begin{aligned} x_1&=\frac56-s-\frac83x_2-\frac23x_4-\frac16x_5,\\ x_3&=\frac16-2s-\frac73x_2-\frac13x_4+\frac16x_5 \end{aligned}

が成り立つ。

$s=0$ で目的関数を上の式へ代入すると

7x_1-4x_2+4x_3 =\frac{13}{2}-32x_2-6x_4-\frac12x_5.

$x_2,x_4,x_5\ge0$ なので、目的値は高々 $13/2$ である。 $x_2=x_4=x_5=0$ と置くと

x_1=\frac56,\qquad x_3=\frac16

となり、これは非負で目的値 $13/2$ を達成する。したがって

\boxed{(x_1,x_2,x_3,x_4,x_5)=\left(\frac56,0,\frac16,0,0\right)}

は最適解であり、確かに $x_2=x_4=x_5=0$ を満たす。

$x_2=x_4=x_5=0$ と置いた候補解は

x_1=\frac56-s,\qquad x_3=\frac16-2s.

その実行可能性は $x_1,x_3\ge0$ 、すなわち $s\le1/12$ と同値である。一方、一般の $s$ について目的関数は

\begin{aligned} &(7+6s)x_1-4x_2+(4-3s)x_3\\ &=\frac{13}{2}-\frac{21}{2}s +(-32-9s)x_2+(-6-3s)x_4-\frac{1+3s}{2}x_5. \end{aligned}

したがって、この候補解が最大値を与えるための還元費用条件は

-32-9s\le0,\qquad -6-3s\le0,\qquad -\frac{1+3s}{2}\le0,

すなわち $s\ge-1/3$ である。実行可能性と合わせると

\boxed{-\frac13\le s\le\frac1{12}}.

なお $s<-1/3$ では $x_5$ の係数が正であり、候補解から $x_5$ を微小に増やしても $x_1,x_3$ の非負性を保ちながら目的値を改善できる。また $s>1/12$ では候補解自体が実行可能でない。よって上の範囲は必要十分である。