この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

最適化・線形計画法の問題

難易度 1教科書の例題レベル大学数学最適化・線形計画法

$c$ を実数の定数とし、次の線形計画問題 $(Q_{c})$ を考える。
$(Q_{c}) maximize subject to c x_{1} + 2 x_{2} x_{1} + x_{2} \leq 4 x_{1} + 3 x_{2} \leq 6 x_{1} \geq 0, x_{2} \geq 0$
点 $(x_{1}, x_{2}) = (3, 1)$ が $(Q_{c})$ の最適解となるような $c$ の範囲は $α \leq c \leq β$ の形に表される。 $α, β$ を求め、組 $(α, β)$ の形で答えよ。

この問題で使うもの

最適性が保たれる係数の範囲（感度分析）（説明と入口の問題）

この問題を解けるようになるまで（51 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

双対問題を書き、与えられた点 $(3, 1)$ と相補性条件をみたす双対解 $y$ を求める。その $y$ が双対実行可能になる $c$ の条件を調べる。

ヒント 2

$x_{1}^{*}, x_{2}^{*} > 0$ なので双対制約は等号： $y_{1} + y_{2} = c$ , $y_{1} + 3 y_{2} = 2$ 。十分性は弱双対性、必要性は強双対定理（最適なら最適な双対解が存在する）で示せる。

ヒント 3

連立方程式を解くと $y_{1} = \frac{3 c - 2}{2}$ , $y_{2} = \frac{2 - c}{2}$ 。あとはこれらが $0$ 以上となる $c$ の範囲を求める。

答えと解説

答えを見る

(\frac{2}{3}, 2)

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

手順1：与えられた点が実行可能であることと、等号になる制約を調べる。
$x^{*} = (3, 1)$ を代入すると $3 + 1 = 4$ 、 $3 + 3 \cdot 1 = 6$ となり、2 つの制約はどちらも等号で成り立つ。また $x_{1}^{*} = 3 > 0$ , $x_{2}^{*} = 1 > 0$ なので、 $x^{*}$ は実行可能解である。目的関数値は $3 c + 2$ である。

手順2：双対問題と、 $x^{*}$ に対応する双対解を求める。
$(Q_{c})$ の双対問題は
$minimize 4 y_{1} + 6 y_{2}, y_{1} + y_{2} \geq c, y_{1} + 3 y_{2} \geq 2, y_{1} \geq 0, y_{2} \geq 0$
である。 $x^{*}$ と組になる双対解 $y$ は相補性条件をみたす必要があり、 $x_{1}^{*} > 0$ , $x_{2}^{*} > 0$ なので双対の 2 つの制約はどちらも等号になる：
$y_{1} + y_{2} = c, y_{1} + 3 y_{2} = 2.$
2 式目から 1 式目を引くと $2 y_{2} = 2 - c$ より $y_{2} = \frac{2 - c}{2}$ 、これを代入して $y_{1} = c - \frac{2 - c}{2} = \frac{3 c - 2}{2}$ 。この連立方程式の解はただ一つなので、 $x^{*}$ と相補性条件をみたす $y$ はこれに限られる。

手順3（十分性）： $\frac{2}{3} \leq c \leq 2$ なら $x^{*}$ は最適解である。
このとき $y_{1} = \frac{3 c - 2}{2} \geq 0$ , $y_{2} = \frac{2 - c}{2} \geq 0$ であり、双対制約も等号で成り立つので $y$ は双対実行可能である。双対の目的関数値は
$4 y_{1} + 6 y_{2} = 2 (3 c - 2) + 3 (2 - c) = 3 c + 2$
で主の目的関数値と一致する。弱双対性より、任意の主実行可能解 $x$ について $c x_{1} + 2 x_{2} \leq 4 y_{1} + 6 y_{2} = 3 c + 2$ が成り立つので、 $x^{*}$ は最適解である。

手順4（必要性）： $x^{*}$ が最適解なら $\frac{2}{3} \leq c \leq 2$ である。
$x^{*}$ が最適解ならば、強双対定理により双対問題にも最適解 $y ˉ$ が存在し、目的関数値は等しい（ $3 c + 2 = 4 y ˉ_{1} + 6 y ˉ_{2}$ ）。最適な主解と双対解の組は相補性条件をみたすから、 $x_{1}^{*}, x_{2}^{*} > 0$ より $y ˉ$ は手順2の連立方程式の解であり、 $y ˉ = (\frac{3 c - 2}{2}, \frac{2 - c}{2})$ と一意に決まる。 $y ˉ$ は双対実行可能なので $y ˉ_{1} \geq 0$ , $y ˉ_{2} \geq 0$ 、すなわち
$\frac{3 c - 2}{2} \geq 0 ⟺ c \geq \frac{2}{3}, \frac{2 - c}{2} \geq 0 ⟺ c \leq 2.$

（直接確かめることもできる。 $c > 2$ なら実行可能点 $(4, 0)$ の値 $4 c$ が $3 c + 2$ より大きく、 $c < \frac{2}{3}$ なら実行可能点 $(0, 2)$ の値 $4$ が $3 c + 2$ より大きいので、 $x^{*}$ は最適でない。図では、等高線 $c x_{1} + 2 x_{2} = k$ の傾き $- \frac{c}{2}$ が 2 本の制約直線の傾き $- 1$ と $- \frac{1}{3}$ の間にあるという条件 $\frac{1}{3} \leq \frac{c}{2} \leq 1$ に対応する。）

以上より、求める範囲は $\frac{2}{3} \leq c \leq 2$ である。

答え： $(α, β) = (\frac{2}{3}, 2)$

別解

実行可能領域の頂点は (0,0), (4,0), (3,1), (0,2) である。ここで (3,1) は x1+x2=4 と x1+3x2=6 の交点である（3+1=4、3+3=6 で確認できる）。

(3,1) で有効な制約は x1+x2≤4 と x1+3x2≤6 の 2 本である。目的関数の勾配 (c,2) が、これらの制約の法線ベクトル (1,1) と (1,3) が張る錐に入ることが、(3,1) が最適となる条件である。

(c,2)=λ(1,1)+μ(1,3), λ,μ≥0 とおく。
λ+3μ=2, λ+μ=c
辺々を引いて 2μ=2-c, よって μ=(2-c)/2。
λ=c-μ=c-(2-c)/2=(3c-2)/2。
μ≥0 より c≤2、λ≥0 より c≥2/3 となる。

頂点での値による検算を行う。
(3,1): 3c+2
(0,0): 0
(4,0): 4c
(0,2): 4
3c+2≥4 より c≥2/3。
3c+2≥4c より c≤2。
3c+2≥0 より c≥-2/3（上の条件に含まれる）。
したがって 2/3≤c≤2 で、両端でも (3,1) は最適解の 1 つである。

c=2 での確認: (3,1) で 8、(4,0) で 8 となり等しい。
c=2/3 での確認: (3,1) で 4、(0,2) で 4 となり等しい。

よって (α,β)=(2/3, 2) である。

最適化・線形計画法の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題