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

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

難易度 3期末試験の応用レベル大学数学最適化・線形計画法

実数 $x_{1}, x_{2}, x_{3}$ についての次の線形計画問題 $(P)$ を考える。
$(P) minimize subject to 6 x_{1} + 8 x_{2} + 4 x_{3} x_{1} + 2 x_{2} + x_{3} \geq 3, 2 x_{1} + x_{2} + x_{3} \geq 4, x_{1} \geq 0, x_{2} \geq 0, x_{3} \geq 0$
$(P)$ の最適解はただ 1 つである。双対問題を利用して、その最適解 $(x_{1}, x_{2}, x_{3})$ をこの順に求めよ。

この問題で使うもの

双対問題と双対定理（説明と入口の問題）
端点（基底解）の列挙による最適解（説明と入口の問題）
相補性条件（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

主問題は 3 変数ですが、双対問題は 2 変数になります。双対問題を図で解き、その結果から主問題の解を復元しましょう。

ヒント 2

双対問題は $max 3 u + 4 v$ , $u + 2 v \leq 6, 2 u + v \leq 8, u + v \leq 4, u, v \geq 0$ です。最適解が求まったら相補性条件（双対の制約が等号でなければ対応する主変数は $0$ 、双対変数が正なら対応する主制約は等号）を使います。

ヒント 3

双対問題の最適解は $(u, v) = (2, 2)$ で最適値は $14$ です。第 2 制約 $2 u + v \leq 8$ が等号でないことと、 $u, v > 0$ であることから、主問題の連立方程式を立てましょう。

答えと解説

答えを見る

(1, 0, 2)

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

解説を読む

双対問題をつくる。 2 つの不等式制約に双対変数 $u, v$ を対応させると、 $(P)$ の双対問題 $(D)$ は
$(D) maximize subject to 3 u + 4 v u + 2 v \leq 6, 2 u + v \leq 8, u + v \leq 4, u \geq 0, v \geq 0$
である（ $(P)$ は $min c^{T} x, A x \geq b, x \geq 0$ の形なので、双対は $max b^{T} y, A^{T} y \leq c, y \geq 0$ ）。

双対問題を図で解く。 $(D)$ は 2 変数なので実行可能領域の頂点を調べる。境界の交点を求めると
- $u + 2 v = 6$ と $u + v = 4$ の交点は $(u, v) = (2, 2)$ で、 $2 u + v = 6 \leq 8$ を満たす。
- $2 u + v = 8$ と $u + v = 4$ の交点は $(4, 0)$ で、 $u + 2 v = 4 \leq 6$ を満たす。
- $u + 2 v = 6$ と $2 u + v = 8$ の交点は $(\frac{10}{3}, \frac{4}{3})$ で、 $u + v = \frac{14}{3} > 4$ となり実行不可能。

よって頂点は $(0, 0), (4, 0), (2, 2), (0, 3)$ で、目的関数 $3 u + 4 v$ の値はそれぞれ $0, 12, 14, 12$ 。実行可能領域は有界なので最大値は頂点でとり、最適解は $(u, v) = (2, 2)$ 、最適値は $14$ である。（目的関数の係数ベクトル $(3, 4)$ は、 $(2, 2)$ で等号が成り立つ制約の法線 $(1, 2), (1, 1)$ を用いて $(3, 4) = 1 \cdot (1, 2) + 2 \cdot (1, 1)$ と正の係数で表されるので、最適解は $(2, 2)$ だけである。）

相補性条件で主問題の解を求める。 $(D)$ に最適解があるので、双対定理より $(P)$ にも最適解があり、最適値は等しく $14$ である。さらに $(P)$ の任意の最適解 $x$ と $(D)$ の最適解 $(2, 2)$ の間には相補性条件が成り立つ。
- $(D)$ の第 2 制約は $2 \cdot 2 + 2 = 6 < 8$ で等号が成り立たないので、対応する主変数は $x_{2} = 0$ 。
- $u = 2 > 0, v = 2 > 0$ なので、 $(P)$ の 2 つの制約はともに等号で成り立つ:
$x_{1} + 2 x_{2} + x_{3} = 3, 2 x_{1} + x_{2} + x_{3} = 4.$

$x_{2} = 0$ を代入すると $x_{1} + x_{3} = 3, 2 x_{1} + x_{3} = 4$ より $x_{1} = 1, x_{3} = 2$ 。

確認: $(1, 0, 2)$ は $1 + 0 + 2 = 3 \geq 3$ 、 $2 + 0 + 2 = 4 \geq 4$ 、各成分 $\geq 0$ で実行可能であり、目的関数の値は $6 \cdot 1 + 8 \cdot 0 + 4 \cdot 2 = 14$ で双対の最適値と一致するので最適である。

したがって最適解は $(x_{1}, x_{2}, x_{3}) = (1, 0, 2)$ である。

別解

双対問題: $max 3 y_{1} + 4 y_{2}$ s.t. $y_{1} + 2 y_{2} \leq 6$ （ $x_{1}$ ）、 $2 y_{1} + y_{2} \leq 8$ （ $x_{2}$ ）、 $y_{1} + y_{2} \leq 4$ （ $x_{3}$ ）、 $y_{1}, y_{2} \geq 0$ 。

実行可能領域の頂点: $(0, 0)$ : 0、 $(4, 0)$ : 12（ $y_{1} + y_{2} = 4$ と $y_{2} = 0$ 。 $y_{1} + 2 y_{2} = 4 \leq 6$ 、 $2 y_{1} + y_{2} = 8 \leq 8$ も成立）、 $(0, 3)$ : 12、 $(2, 2)$ （ $y_{1} + 2 y_{2} = 6$ と $y_{1} + y_{2} = 4$ の交点）: $6 + 8 = 14$ 。 $(2, 2)$ で $2 y_{1} + y_{2} = 6 \leq 8$ を満たす。最大値は 14、最適解は $(y_{1}, y_{2}) = (2, 2)$ 。

このとき双対制約のうち $x_{2}$ 用 ( $2 y_{1} + y_{2} = 6 < 8$ ) は不等号が厳密に成立しているので、相補性から $x_{2} = 0$ 。 $y_{1}, y_{2} > 0$ なので主問題の 2 制約は等号: $x_{1} + x_{3} = 3$ 、 $2 x_{1} + x_{3} = 4$ 。差を取って $x_{1} = 1$ 、 $x_{3} = 2$ 。

検算: 主問題の目的関数値は $6 \cdot 1 + 8 \cdot 0 + 4 \cdot 2 = 14$ で双対値に一致する。制約: $1 + 0 + 2 = 3 \geq 3$ 、 $2 + 0 + 2 = 4 \geq 4$ で実行可能。答えは $(1, 0, 2)$ 。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題