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

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

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

実数 $x_{1}, x_{2}, x_{3}, x_{4}$ についての次の線形計画問題 $(P)$ を考える。
$(P) minimize subject to 4 x_{1} + 3 x_{2} + 3 x_{3} + 6 x_{4} x_{1} + 2 x_{2} + x_{3} + 3 x_{4} \geq 8, 3 x_{1} + x_{2} + x_{3} + 2 x_{4} \geq 9, x_{1}, x_{2}, x_{3}, x_{4} \geq 0$
$(P)$ の双対問題を作って解き、相補性条件を用いることで、 $(P)$ の最適解 $(x_{1}, x_{2}, x_{3}, x_{4})$ を求めよ（最適解はただ 1 つに定まる）。答えは組 $(x_{1}, x_{2}, x_{3}, x_{4})$ の形で答えよ。

この問題で使うもの

双対問題と双対定理（説明と入口の問題）
端点（基底解）の列挙による最適解（説明と入口の問題）
相補性条件（説明と入口の問題）
掃き出し法と連立 1 次方程式（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

主問題は 4 変数なので直接図示できない。制約が 2 本であることに注目して双対問題（2 変数）を作り、図で解こう。

ヒント 2

双対問題は「maximize $8 y_{1} + 9 y_{2}$ , subject to $y_{1} + 3 y_{2} \leq 4, 2 y_{1} + y_{2} \leq 3, y_{1} + y_{2} \leq 3, 3 y_{1} + 2 y_{2} \leq 6, y \geq 0$ 」。双対最適解が求まったら、等号の成り立たない双対制約に対応する $x_{j}$ は 0、正の $y_{i}$ に対応する主制約は等号、という相補性条件を使う。

ヒント 3

双対最適解は $y^{*} = (1, 1)$ （最適値 $17$ ）。このとき第 3・第 4 の双対制約には余裕があるので $x_{3} = x_{4} = 0$ 、また $x_{1} + 2 x_{2} = 8, 3 x_{1} + x_{2} = 9$ が成り立つ。

答えと解説

答えを見る

(2, 3, 0, 0)

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

解説を読む

双対問題　 $(P)$ は「 $min c^{⊤} x, A x \geq b, x \geq 0$ 」の形なので、双対問題は「 $max b^{⊤} y, A^{⊤} y \leq c, y \geq 0$ 」である。具体的には
$(D) maximize subject to 8 y_{1} + 9 y_{2} y_{1} + 3 y_{2} \leq 4 (1) 2 y_{1} + y_{2} \leq 3 (2) y_{1} + y_{2} \leq 3 (3) 3 y_{1} + 2 y_{2} \leq 6 (4) y_{1}, y_{2} \geq 0$

双対問題を解く　まず $(1), (2)$ と $y_{1}, y_{2} \geq 0$ だけで定まる多角形を考える。 $(1), (2)$ をともに等号にすると、 $(2)$ より $y_{2} = 3 - 2 y_{1}$ を $(1)$ に代入して $y_{1} + 9 - 6 y_{1} = 4$ 、よって $y_{1} = 1, y_{2} = 1$ 。この多角形の頂点は
$(0, 0), (\frac{3}{2}, 0), (1, 1), (0, \frac{4}{3})$
である。各頂点で $(3)$ の左辺は $0, \frac{3}{2}, 2, \frac{4}{3}$ （いずれも $\leq 3$ ）、 $(4)$ の左辺は $0, \frac{9}{2}, 5, \frac{8}{3}$ （いずれも $\leq 6$ ）となる。多角形は凸で $(3), (4)$ の左辺は一次式なので、多角形全体で $(3), (4)$ は成り立つ。よって $(D)$ の実行可能領域はこの多角形そのものである。

目的関数 $8 y_{1} + 9 y_{2}$ の各頂点での値は $0, 12, 17, 12$ なので、 $(D)$ の最適解はただ 1 つで $y^{*} = (1, 1)$ 、最適値は $17$ である。

相補性条件　 $x$ が $(P)$ の最適解であるための必要十分条件は、 $x$ が実行可能で、双対最適解 $y^{*}$ との間に相補性条件が成り立つことである（線形計画の強双対定理より）。

- 双対制約の余裕： $(3)$ は $3 - (1 + 1) = 1 > 0$ 、 $(4)$ は $6 - (3 + 2) = 1 > 0$ で、どちらも等号が成り立たない。よって対応する主変数は $x_{3} = 0, x_{4} = 0$ 。
- $y_{1}^{*} = 1 > 0, y_{2}^{*} = 1 > 0$ なので、主問題の 2 つの制約はともに等号：
$x_{1} + 2 x_{2} = 8, 3 x_{1} + x_{2} = 9$

第 2 式から $x_{2} = 9 - 3 x_{1}$ 。第 1 式に代入して $x_{1} + 18 - 6 x_{1} = 8$ 、よって $x_{1} = 2$ 、 $x_{2} = 3$ 。これは $x \geq 0$ を満たし、実行可能である。

確認　主問題の目的関数値は $4 \cdot 2 + 3 \cdot 3 = 17$ で、双対最適値 $17$ と一致するので、弱双対定理より確かに最適である。また、双対最適解はただ 1 つで、どの主最適解もこの $y^{*}$ と相補性条件を満たすから、上の議論より最適解はこれ 1 つに限られる。

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

別解

双対問題は、 $y_{1}, y_{2} \geq 0$ のもとで $8 y_{1} + 9 y_{2}$ を最大化する問題で、制約は次の4本である。
$y_{1} + 3 y_{2} \leq 4, 2 y_{1} + y_{2} \leq 3, y_{1} + y_{2} \leq 3, 3 y_{1} + 2 y_{2} \leq 6$ 。

実行可能領域の頂点を調べる。
- 原点: 目的関数値は $0$ 。
- $y_{2} = 0$ のとき $y_{1} \leq min (4, 3/2, 3, 2) = 3/2$ なので、頂点 $(3/2, 0)$ で値は $12$ 。
- $y_{1} = 0$ のとき $y_{2} \leq min (4/3, 3, 3, 3) = 4/3$ なので、頂点 $(0, 4/3)$ で値は $12$ 。
- 第1式と第2式の交点: $y_{1} + 3 y_{2} = 4$ と $2 y_{1} + y_{2} = 3$ を解くと $(y_{1}, y_{2}) = (1, 1)$ 。第3式は $2 \leq 3$ 、第4式は $5 \leq 6$ を満たすので実行可能で、値は $8 + 9 = 17$ 。

よって双対の最適解は $(y_{1}, y_{2}) = (1, 1)$ 、最適値は $17$ である。

相補性条件を使う。双対の第3制約 $y_{1} + y_{2} = 2 < 3$ と第4制約 $3 y_{1} + 2 y_{2} = 5 < 6$ は等号でないので、 $x_{3} = x_{4} = 0$ 。また $y_{1}, y_{2} > 0$ なので主問題の2つの制約は等号になる。
$x_{1} + 2 x_{2} = 8, 3 x_{1} + x_{2} = 9$ 。
これを解くと $x_{2} = 9 - 3 x_{1}$ より $x_{1} + 18 - 6 x_{1} = 8$ 、 $x_{1} = 2$ 、 $x_{2} = 3$ 。

検算: 目的関数は $4 \cdot 2 + 3 \cdot 3 = 17$ で双対最適値と一致する。制約は $2 + 6 = 8$ 、 $6 + 3 = 9$ で成り立ち、 $x \geq 0$ も満たす。

答え: $(2, 3, 0, 0)$

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題