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

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

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

実数 $y_{1}, y_{2}, y_{3}$ についての次の線形計画問題 $(D)$ を考える。
$(D) minimize subject to 5 y_{1} + 8 y_{2} + 8 y_{3} y_{1} + y_{2} + 2 y_{3} ≧ 3 y_{1} + 2 y_{2} + y_{3} ≧ 2 y_{1} ≧ 0, y_{2} ≧ 0, y_{3} ≧ 0$
$(D)$ の最小値を求めよ。

この問題で使うもの

双対問題と双対定理（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

双対問題と双対定理を使う。 $(D)$ を「 $min b^{⊤} y$ , $A^{⊤} y ≧ c$ , $y ≧ 0$ 」と見て、これを双対にもつ変数 2 個の主問題 $(P)$ を作ろう。

ヒント 2

$b = (5, 8, 8)^{⊤}$ , $c = (3, 2)^{⊤}$ なので、 $(P)$ は $max 3 x_{1} + 2 x_{2}$ , $x_{1} + x_{2} ≦ 5$ , $x_{1} + 2 x_{2} ≦ 8$ , $2 x_{1} + x_{2} ≦ 8$ , $x ≧ 0$ となる。これを領域の頂点で調べ、強双対定理で最適値が一致することを使う。

ヒント 3

$(P)$ の頂点は $(0, 0), (4, 0), (3, 2), (2, 3), (0, 4)$ 。それぞれで $3 x_{1} + 2 x_{2}$ を計算して最大値を求め、 $(D)$ でその値を実現する $y$ （たとえば $y_{2} = 0$ として残りを決める）が実行可能か確かめよう。

答えと解説

答えを見る

13

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

解説を読む

方針 $(D)$ は変数が 3 個あるので図で解きにくい。そこで $(D)$ を双対問題とする主問題 $(P)$ （変数 2 個）を作り、それを図で解いてから双対定理を使う。

手順 1：形を読み取る。 $(D)$ は $min b^{⊤} y$ , $A^{⊤} y ≧ c$ , $y ≧ 0$ の形で
$b = 588, A^{⊤} = (111221), c = (32)$
である。したがって $A = 112121$ で、主問題 $max c^{⊤} x$ , $A x ≦ b$ , $x ≧ 0$ は
$(P) maximize subject to 3 x_{1} + 2 x_{2} x_{1} + x_{2} ≦ 5 x_{1} + 2 x_{2} ≦ 8 2 x_{1} + x_{2} ≦ 8 x_{1} ≧ 0, x_{2} ≧ 0$
となる。

手順 2： $(P)$ を図で解く。 実行可能領域の頂点を求める。
- $x_{1} + x_{2} = 5$ と $2 x_{1} + x_{2} = 8$ の交点：引くと $x_{1} = 3$ , $x_{2} = 2$ 。 $x_{1} + 2 x_{2} = 7 ≦ 8$ なので領域内。
- $x_{1} + x_{2} = 5$ と $x_{1} + 2 x_{2} = 8$ の交点：引くと $x_{2} = 3$ , $x_{1} = 2$ 。 $2 x_{1} + x_{2} = 7 ≦ 8$ なので領域内。
- 軸上の頂点は $(0, 0)$ , $(4, 0)$ （ $2 x_{1} + x_{2} ≦ 8$ より）, $(0, 4)$ （ $x_{1} + 2 x_{2} ≦ 8$ より）。

各頂点での $3 x_{1} + 2 x_{2}$ の値は
$(0, 0) \to 0$ , $(4, 0) \to 12$ , $(3, 2) \to 13$ , $(2, 3) \to 12$ , $(0, 4) \to 8$ 。
よって $(P)$ の最大値は $13$ （ $x = (3, 2)$ のとき）。

手順 3：双対定理を使う。 弱双対性より、 $(P)$ の実行可能解 $x$ と $(D)$ の実行可能解 $y$ について常に
$3 x_{1} + 2 x_{2} ≦ 5 y_{1} + 8 y_{2} + 8 y_{3}$
が成り立つ。 $x = (3, 2)$ を代入すると、 $(D)$ の目的関数はつねに $13$ 以上である。
一方、 $y = (1, 0, 1)$ は $1 + 0 + 2 = 3 ≧ 3$ , $1 + 0 + 1 = 2 ≧ 2$ , $y ≧ 0$ を満たすので $(D)$ の実行可能解で、目的関数の値は $5 \cdot 1 + 8 \cdot 0 + 8 \cdot 1 = 13$ である。
したがって $(D)$ の最小値は $13$ と挟み込める。（強双対定理により、 $(P)$ に最適解があれば $(D)$ の最適値はそれと一致する、という結論とも合っている。）

答え： $13$

別解

双対問題（主問題）を考える。 $x_{1}, x_{2} \geq 0$ について、 $3 x_{1} + 2 x_{2}$ を最大化する。制約は $x_{1} + x_{2} \leq 5$ 、 $x_{1} + 2 x_{2} \leq 8$ 、 $2 x_{1} + x_{2} \leq 8$ である。

実行可能領域の頂点は次のとおり。
- $(0, 0)$ のとき値は $0$
- $(4, 0)$ のとき値は $12$
- $(3, 2)$ のとき値は $13$ 。これは $x_{1} + x_{2} = 5$ と $2 x_{1} + x_{2} = 8$ の交点で、 $x_{1} + 2 x_{2} = 7 \leq 8$ を満たす。
- $(2, 3)$ のとき値は $12$ 。これは $x_{1} + x_{2} = 5$ と $x_{1} + 2 x_{2} = 8$ の交点で、 $2 x_{1} + x_{2} = 7 \leq 8$ を満たす。
- $(0, 4)$ のとき値は $8$

よって双対問題の最大値は $13$ である。

$(D)$ の実行可能解を直接求めて確かめる。 $(3, 2)$ では $x_{1} + 2 x_{2} = 7 < 8$ なので、相補性より $y_{2} = 0$ となる。また $x_{1}, x_{2} > 0$ なので、 $(D)$ の2本の制約式は等号になる。すなわち $y_{1} + 2 y_{3} = 3$ 、 $y_{1} + y_{3} = 2$ より $y_{3} = 1$ 、 $y_{1} = 1$ である。

このとき $y = (1, 0, 1)$ は実行可能で、目的関数の値は $5 + 8 = 13$ となり、双対の最大値と一致する。強双対性より $(D)$ の最小値は $13$ である。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題