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

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

難易度 4大学院入試の標準レベル大学数学最適化・線形計画法

実数 $x_{1}, x_{2}, x_{3}, x_{4}$ についての次の線形計画問題 $(P)$ を考える。
$(P) maximize subject to 3 x_{1} + 4 x_{2} + 5 x_{3} + 2 x_{4} x_{1} + 2 x_{2} + x_{3} + x_{4} \leq 5 2 x_{1} + x_{2} + 3 x_{3} + x_{4} \leq 5 x_{1} + x_{2} + 2 x_{3} + 3 x_{4} \leq 8 x_{1}, x_{2}, x_{3}, x_{4} \geq 0$
$(P)$ の第 $i$ 番目の不等式制約 $(i = 1, 2, 3)$ に対応する双対変数を $y_{i}$ とし、 $(P)$ の双対問題 $(D)$ を、制約の係数行列を $A$ 、右辺を $b = (5, 5, 8)^{⊤}$ 、目的関数の係数を $c = (3, 4, 5, 2)^{⊤}$ として
$(D) minimize b^{⊤} y subject to A^{⊤} y \geq c, y \geq 0$
で定める。 $x^{*} = (0, 2, 1, 0)$ が $(P)$ の最適解であることが知られているとき、 $(D)$ の最適解 $(y_{1}, y_{2}, y_{3})$ を求めよ。

この問題で使うもの

相補性条件（説明と入口の問題）
双対問題と双対定理（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

まず双対問題 (D) の制約 $A^{⊤} y \geq c$ を 4 本の不等式として書き下し、相補性条件を使って $x^{*}$ から $y$ の満たすべき等式を取り出しましょう。

ヒント 2

相補性条件: (P) の第 $i$ 制約に余裕があれば $y_{i} = 0$ 、 $x_{j}^{*} > 0$ ならば (D) の第 $j$ 制約は等号で成り立ちます。 $x^{*}$ を (P) の各制約に代入して余裕のある制約を調べましょう。

ヒント 3

第 3 制約は $4 < 8$ で余裕があるので $y_{3} = 0$ 。また $x_{2}^{*}, x_{3}^{*} > 0$ より $2 y_{1} + y_{2} + y_{3} = 4$ と $y_{1} + 3 y_{2} + 2 y_{3} = 5$ が等号で成り立ちます。この連立方程式を解き、得られた $y$ が (D) のほかの制約も満たすか確認しましょう。

答えと解説

答えを見る

(\frac{7}{5}, \frac{6}{5}, 0)

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

解説を読む

双対問題 $(D)$ を書き下すと
$(D) minimize subject to 5 y_{1} + 5 y_{2} + 8 y_{3} y_{1} + 2 y_{2} + y_{3} \geq 3 (1) 2 y_{1} + y_{2} + y_{3} \geq 4 (2) y_{1} + 3 y_{2} + 2 y_{3} \geq 5 (3) y_{1} + y_{2} + 3 y_{3} \geq 2 (4) y_{1}, y_{2}, y_{3} \geq 0$
となる。

相補性条件　 $x$ が $(P)$ の実行可能解、 $y$ が $(D)$ の実行可能解のとき、両方が最適解であるための必要十分条件は
- $y_{i} > 0$ ならば $(P)$ の第 $i$ 制約は等号で成り立つ（同値な言い方: 第 $i$ 制約に余裕があれば $y_{i} = 0$ ）
- $x_{j} > 0$ ならば $(D)$ の第 $j$ 制約は等号で成り立つ

である（双対定理より最適値が一致することと同値）。 $(P)$ は $x^{*}$ という最適解をもつので、強双対定理により $(D)$ にも最適解があり、 $(D)$ のどの最適解も $x^{*}$ と相補性条件を満たす。

主問題の制約の確認　 $x^{*} = (0, 2, 1, 0)$ を代入すると
$第 1 制約 : 0 + 4 + 1 + 0 = 5, 第 2 制約 : 0 + 2 + 3 + 0 = 5, 第 3 制約 : 0 + 2 + 2 + 0 = 4 < 8$
第 3 制約には余裕があるので $y_{3} = 0$ である。

双対の制約の確認　 $x_{2}^{*} = 2 > 0, x_{3}^{*} = 1 > 0$ なので、 $(2)$ と $(3)$ は等号で成り立つ。 $y_{3} = 0$ を代入して
$2 y_{1} + y_{2} = 4, y_{1} + 3 y_{2} = 5$
第 1 式から $y_{2} = 4 - 2 y_{1}$ 。第 2 式に代入して $y_{1} + 12 - 6 y_{1} = 5$ 、よって $y_{1} = \frac{7}{5}$ 、 $y_{2} = 4 - \frac{14}{5} = \frac{6}{5}$ 。

したがって、 $(D)$ の最適解の候補は $y = (\frac{7}{5}, \frac{6}{5}, 0)$ ただ 1 つである。

実行可能性の確認　 $y \geq 0$ であり、
$(1) : \frac{7}{5} + \frac{12}{5} = \frac{19}{5} \geq 3, (2) : \frac{14}{5} + \frac{6}{5} = 4, (3) : \frac{7}{5} + \frac{18}{5} = 5, (4) : \frac{7}{5} + \frac{6}{5} = \frac{13}{5} \geq 2$
ですべて満たす。さらに目的関数値は
$(P) : 4 \cdot 2 + 5 \cdot 1 = 13, (D) : 5 \cdot \frac{7}{5} + 5 \cdot \frac{6}{5} + 8 \cdot 0 = 7 + 6 = 13$
で一致するので、弱双対定理より $y$ は $(D)$ の最適解である（同時に $x^{*}$ の最適性も確かめられる）。

よって求める最適解は $(y_{1}, y_{2}, y_{3}) = (\frac{7}{5}, \frac{6}{5}, 0)$ である。

別解

まず $x^{*} = (0, 2, 1, 0)$ が実行可能であることを確かめる。制約 1: $0 + 4 + 1 + 0 = 5$ （等号）、制約 2: $0 + 2 + 3 + 0 = 5$ （等号）、制約 3: $0 + 2 + 2 + 0 = 4 < 8$ （余裕あり）。目的関数値は $4 \cdot 2 + 5 \cdot 1 = 13$ 。

相補性条件（相補スラック）より、(i) 制約 3 が $x^{*}$ で等号でないので $y_{3} = 0$ 。(ii) $x_{2}^{*} = 2 > 0$ , $x_{3}^{*} = 1 > 0$ なので、双対制約の第 2, 第 3 式は等号で成り立つ。
$2 y_{1} + y_{2} + y_{3} = 4, y_{1} + 3 y_{2} + 2 y_{3} = 5.$
$y_{3} = 0$ を代入して $2 y_{1} + y_{2} = 4$ , $y_{1} + 3 y_{2} = 5$ 。第 1 式から $y_{2} = 4 - 2 y_{1}$ 、これを第 2 式に代入して $y_{1} + 12 - 6 y_{1} = 5$ 、よって $y_{1} = \frac{7}{5}$ 、 $y_{2} = 4 - \frac{14}{5} = \frac{6}{5}$ 。

双対実行可能性の確認: $y \geq 0$ は成り立つ。第 1 式 $y_{1} + 2 y_{2} + y_{3} = \frac{7}{5} + \frac{12}{5} = \frac{19}{5} \geq 3$ 、第 4 式 $y_{1} + y_{2} + 3 y_{3} = \frac{13}{5} \geq 2$ 。ともに成り立つ。

検算: 双対目的関数値 $b^{⊤} y = 5 \cdot \frac{7}{5} + 5 \cdot \frac{6}{5} + 8 \cdot 0 = 7 + 6 = 13$ で、主問題の値 13 と一致する（強双対性より $y$ は最適）。また $x_{1}^{*} = 0$ , $x_{4}^{*} = 0$ に対応する双対制約は等号でなくてよく、相補性も満たされる。

なお第 2, 3 式の係数行列は正則なので、 $y$ は一意に定まる。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題