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

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

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

実数 $x_{1}, x_{2}, x_{3}$ についての次の線形計画問題 $(P)$ を考える。
$(P) maximize subject to 3 x_{1} + 5 x_{2} + 4 x_{3} x_{1} + x_{2} + x_{3} ≦ 5 x_{1} + 2 x_{2} + 3 x_{3} ≦ 8 x_{1} ≧ 0, x_{2} ≧ 0, x_{3} ≧ 0$
$(P)$ の双対問題 $(D)$ を作ると、変数は 2 つになる。 $(D)$ を座標平面上の図を使って解き、強双対定理を用いて $(P)$ の最適値（目的関数の最大値）を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

「双対問題と双対定理」を使う。制約が 2 本なので双対問題の変数は 2 つになり、図で解ける。

ヒント 2

双対問題は $min 5 y_{1} + 8 y_{2}$ 、制約は $A^{⊤} y ≧ c$ すなわち $y_{1} + y_{2} ≧ 3, y_{1} + 2 y_{2} ≧ 5, y_{1} + 3 y_{2} ≧ 4, y ≧ 0$ 。実行可能領域の頂点で $5 y_{1} + 8 y_{2}$ を比べる。

ヒント 3

頂点は $(0, 3), (1, 2), (5, 0)$ の 3 つ。それぞれで $5 y_{1} + 8 y_{2}$ を計算し、最小のものを選んで強双対定理を使う。

答えと解説

答えを見る

21

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

解説を読む

手順 1：双対問題を作る。
$(P)$ は $max c^{⊤} x, A x ≦ b, x ≧ 0$ の形で
$A = (111213), b = (58), c = 354$
である。制約が 2 本なので双対変数は $y_{1}, y_{2}$ の 2 つで、双対問題 $min b^{⊤} y, A^{⊤} y ≧ c, y ≧ 0$ は
$(D) minimize subject to 5 y_{1} + 8 y_{2} y_{1} + y_{2} ≧ 3 y_{1} + 2 y_{2} ≧ 5 y_{1} + 3 y_{2} ≧ 4 y_{1} ≧ 0, y_{2} ≧ 0$
となる（ $A^{⊤}$ の各行が $x_{1}, x_{2}, x_{3}$ の係数の列に対応する）。

手順 2： $(D)$ を図で解く。
$y_{1} y_{2}$ 平面で実行可能領域の頂点を求める。
- $y_{1} = 0$ 上： $y_{2} ≧ 3, y_{2} ≧ \frac{5}{2}, y_{2} ≧ \frac{4}{3}$ より頂点 $(0, 3)$ 。
- $y_{1} + y_{2} = 3$ と $y_{1} + 2 y_{2} = 5$ の交点：引き算して $y_{2} = 2$ 、 $y_{1} = 1$ 。 $y_{1} + 3 y_{2} = 7 ≧ 4$ も満たすので頂点 $(1, 2)$ 。
- $y_{2} = 0$ 上： $y_{1} ≧ 3, y_{1} ≧ 5, y_{1} ≧ 4$ より頂点 $(5, 0)$ 。
（ $y_{1} + 3 y_{2} ≧ 4$ はこの領域では自動的に成り立ち、境界にはならない。）
領域は右上に広がる非有界な領域だが、 $5 y_{1} + 8 y_{2} = k$ とおくと係数が正なので、 $k$ を小さくして直線を原点側へ動かしたとき最後に領域に触れるのは頂点である。各頂点での値は
$(0, 3) : 24, (1, 2) : 5 + 16 = 21, (5, 0) : 25$
よって $(D)$ の最適値は $21$ （ $(y_{1}, y_{2}) = (1, 2)$ のとき）。

手順 3：強双対定理を使う。
$(D)$ に最適解があるので、強双対定理より $(P)$ にも最適解があり、最適値は一致する。したがって $(P)$ の最適値は $21$ 。

確かめ（弱双対性）： $(x_{1}, x_{2}, x_{3}) = (2, 3, 0)$ は $2 + 3 + 0 = 5 ≦ 5$ 、 $2 + 6 + 0 = 8 ≦ 8$ を満たす $(P)$ の実行可能解で、目的関数の値は $6 + 15 = 21$ 。弱双対性より $(P)$ のどの実行可能解の値も $(D)$ の値 $21$ 以下なので、 $21$ が最大値であることが上下から確かめられる。

答え： $21$

別解

(P) の双対問題 (D) は、変数を $y_{1}, y_{2} ≧ 0$ として
$minimize 5 y_{1} + 8 y_{2} subject to y_{1} + y_{2} ≧ 3, y_{1} + 2 y_{2} ≧ 5, y_{1} + 3 y_{2} ≧ 4, y_{1}, y_{2} ≧ 0$
である。

$(y_{1}, y_{2})$ 平面で実行可能領域を考える。各条件は $y_{1} ≧ 3 - y_{2}$ 、 $y_{1} ≧ 5 - 2 y_{2}$ 、 $y_{1} ≧ 4 - 3 y_{2}$ 、 $y_{1} ≧ 0$ と書ける。
- $0 ≦ y_{2} ≦ 2$ では $5 - 2 y_{2}$ が最大なので、境界は $y_{1} = 5 - 2 y_{2}$ である。
- $2 ≦ y_{2} ≦ 3$ では $3 - y_{2}$ が最大なので、境界は $y_{1} = 3 - y_{2}$ である。
- $y_{2} ≧ 3$ では $y_{1} = 0$ が境界である。
- 第3式 $y_{1} + 3 y_{2} ≧ 4$ は、これらの境界上ではつねに成り立つ。

領域は下側がこの折れ線で囲まれた、 $y_{1}$ 方向に開いた凸な領域である。頂点は次の3つである。
- $(5, 0)$ ：目的関数の値は $25$
- $(1, 2)$ ： $y_{1} + y_{2} = 3$ と $y_{1} + 2 y_{2} = 5$ の交点で、値は $5 + 16 = 21$
- $(0, 3)$ ：値は $24$

目的関数の係数は正なので、領域の無限に延びる方向では値が増加する。したがって最小値は頂点のうち最小の $21$ で、 $(y_{1}, y_{2}) = (1, 2)$ で達成される。

強双対定理より、(P) の最適値は (D) の最適値に等しく $21$ である。

検算： $(1, 2)$ では第3式が $7 > 4$ で余裕があるので、相補性より $x_{3} = 0$ である。 $y_{1}, y_{2} > 0$ より (P) の2つの制約は等号になる。
$x_{1} + x_{2} = 5$ 、 $x_{1} + 2 x_{2} = 8$ を解くと $x_{2} = 3$ 、 $x_{1} = 2$ である。このとき目的関数は $3 \cdot 2 + 5 \cdot 3 = 21$ となり、双対の値と一致する。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題