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

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

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

実数 $x_{1}, x_{2}, x_{3}$ についての線形計画問題 $(P)$ と、実数 $y_{1}, y_{2}, y_{3}, y_{4}$ についてのその双対問題 $(D)$ を考える。
$(P) maximize subject to 4 x_{1} + 3 x_{2} + 5 x_{3} x_{1} + x_{2} + x_{3} \leq 3, 2 x_{1} + x_{2} \leq 3, x_{1} + 2 x_{3} \leq 3, 2 x_{2} + x_{3} \leq 3, x_{1}, x_{2}, x_{3} \geq 0$
$(D) minimize subject to 3 y_{1} + 3 y_{2} + 3 y_{3} + 3 y_{4} y_{1} + 2 y_{2} + y_{3} \geq 4, y_{1} + y_{2} + 2 y_{4} \geq 3, y_{1} + 2 y_{3} + y_{4} \geq 5, y_{1}, y_{2}, y_{3}, y_{4} \geq 0$
$(D)$ の最適解は一つに定まらない。 $(D)$ の最適解 $(y_{1}, y_{2}, y_{3}, y_{4})$ 全体を動くときの $y_{1} + y_{3}$ の最小値と最大値を、この順に組で求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$(P)$ の 4 つの制約がすべて等号になる点を探し、その点と同じ目的関数値をもつ $(D)$ の実行可能解を見つけて、弱双対定理で両方の最適性を示しましょう。

ヒント 2

$(P)$ の最適解 $x^{*} = (1, 1, 1)$ の成分はすべて正なので、相補性条件より $(D)$ の最適解は 3 つの制約をすべて等号で満たします。逆に $y \geq 0$ で 3 つの等式を満たせば目的関数値は自動的に $12$ になります。

ヒント 3

$y_{1} = s$ とおいて 3 つの等式を解くと $y_{2} = 1 - \frac{s}{3}, y_{3} = 2 - \frac{s}{3}, y_{4} = 1 - \frac{s}{3}$ となります。あとは非負条件から $s$ の範囲を求め、 $y_{1} + y_{3}$ を $s$ で表しましょう。

答えと解説

答えを見る

(2, 4)

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

解説を読む

1. $(P)$ の最適値を求める。

$x^{*} = (1, 1, 1)$ を代入すると、4 つの制約の左辺はすべて $3$ となり、 $x^{*}$ は実行可能で目的関数値は $4 + 3 + 5 = 12$ である。

一方、 $y^{0} = (0, 1, 2, 1)$ は
$y_{1} + 2 y_{2} + y_{3} = 0 + 2 + 2 = 4, y_{1} + y_{2} + 2 y_{4} = 0 + 1 + 2 = 3, y_{1} + 2 y_{3} + y_{4} = 0 + 4 + 1 = 5$
より $(D)$ の実行可能解で、目的関数値は $3 (0 + 1 + 2 + 1) = 12$ である。弱双対定理より $(P)$ の任意の実行可能解の値は $12$ 以下、 $(D)$ の任意の実行可能解の値は $12$ 以上である。よって $x^{*}$ は $(P)$ の最適解、 $y^{0}$ は $(D)$ の最適解で、最適値はともに $12$ である。

2. 相補性条件で $(D)$ の最適解を特徴づける。

$x^{*}$ は $(P)$ の最適解なので、相補性条件（双対定理から従う）により、 $(D)$ の任意の最適解 $y$ について「 $x_{j}^{*} > 0$ ならば $(D)$ の第 $j$ 制約は等号」が成り立つ。 $x_{1}^{*}, x_{2}^{*}, x_{3}^{*}$ はすべて正なので、 $(D)$ の最適解は
$y_{1} + 2 y_{2} + y_{3} = 4 (1), y_{1} + y_{2} + 2 y_{4} = 3 (2), y_{1} + 2 y_{3} + y_{4} = 5 (3)$
と $y \geq 0$ を満たす。逆に、 $y \geq 0$ が $(1)$ 〜 $(3)$ を満たせば実行可能で、各式に $x_{j}^{*} = 1$ を掛けて足すと
$3 (y_{1} + y_{2} + y_{3} + y_{4}) = 4 + 3 + 5 = 12$
となるので（ $(1) + (2) + (3)$ の左辺は $3 y_{1} + 3 y_{2} + 3 y_{3} + 3 y_{4}$ ）、最適解である。よって $(D)$ の最適解全体は「 $y \geq 0$ かつ $(1)$ 〜 $(3)$ 」の解全体である。

3. 連立方程式を解く。

$y_{1} = s$ とおく。 $(1)$ より $y_{3} = 4 - s - 2 y_{2}$ 、 $(2)$ より $y_{4} = \frac{3 - s - y _{2}}{2}$ 。これらを $(3)$ に代入して
$s + 2 (4 - s - 2 y_{2}) + \frac{3 - s - y _{2}}{2} = 5$
両辺を $2$ 倍して整理すると $9 - 3 s - 9 y_{2} = 0$ 、すなわち $y_{2} = 1 - \frac{s}{3}$ 。したがって
$y = (y_{1}, y_{2}, y_{3}, y_{4}) = (s, 1 - \frac{s}{3}, 2 - \frac{s}{3}, 1 - \frac{s}{3}) .$
非負条件は $s \geq 0$ , $1 - \frac{s}{3} \geq 0$ , $2 - \frac{s}{3} \geq 0$ より $0 \leq s \leq 3$ 。

4. $y_{1} + y_{3}$ の範囲。

$y_{1} + y_{3} = s + 2 - \frac{s}{3} = 2 + \frac{2}{3} s$
は $0 \leq s \leq 3$ で単調増加なので、最小値は $s = 0$ のとき $2$ 、最大値は $s = 3$ のとき $4$ である。

答え： $(2, 4)$

別解

原問題 (P) の点 $x = (1, 1, 1)$ は 4 本の不等式制約をすべて等号で満たす。これは実行可能で、目的関数値は $4 + 3 + 5 = 12$ である。

双対実行可能解として $y = (3, 0, 1, 0)$ をとる。
- $y_{1} + 2 y_{2} + y_{3} = 3 + 0 + 1 = 4 \geq 4$
- $y_{1} + y_{2} + 2 y_{4} = 3 \geq 3$
- $y_{1} + 2 y_{3} + y_{4} = 3 + 2 = 5 \geq 5$

よって実行可能で、目的関数値は $3 (3 + 0 + 1 + 0) = 12$ である。弱双対性より、両問題の最適値はともに 12 である。

$x = (1, 1, 1)$ は (P) の最適解で、 $x_{1}, x_{2}, x_{3}$ はすべて正である。相補性条件より、(D) の最適解では 3 本の制約がすべて等号になる。
$y_{1} + 2 y_{2} + y_{3} = 4, y_{1} + y_{2} + 2 y_{4} = 3, y_{1} + 2 y_{3} + y_{4} = 5.$
さらに最適値が 12 であることから $y_{1} + y_{2} + y_{3} + y_{4} = 4$ である。

1 本目の式から $y_{1} + y_{2} + y_{3} + y_{4} = 4$ を引くと $y_{2} - y_{4} = 0$ 、すなわち $y_{2} = y_{4}$ となる。 $y_{2} = y_{4} = t$ とおく。
- 2 本目の式から $y_{1} = 3 - 3 t$
- 1 本目の式から $y_{3} = 4 - y_{1} - 2 t = 1 + t$
- 3 本目の式に代入すると $(3 - 3 t) + 2 (1 + t) + t = 5$ となり、恒等的に成り立つ。

非負条件は $y_{1} = 3 - 3 t \geq 0$ より $t \leq 1$ 、かつ $t \geq 0$ である。したがって最適解全体は
$(y_{1}, y_{2}, y_{3}, y_{4}) = (3 - 3 t, t, 1 + t, t), 0 \leq t \leq 1.$
逆に、この形の点は 3 本の制約を等号で満たし、和が 4 なので、すべて実行可能で最適である。

このとき $y_{1} + y_{3} = 4 - 2 t$ であり、 $t \in [0, 1]$ を動くので、最大値は $t = 0$ のとき 4、最小値は $t = 1$ のとき 2 である。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題