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

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

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

$n$ を $2$ 以上の整数とし、正の実数 $a_{1}, \dots, a_{n}$ , $c_{1}, \dots, c_{n}$ , $B$ が
$\frac{c _{1}}{a _{1}} > \frac{c _{2}}{a _{2}} > \dots > \frac{c _{n}}{a _{n}}$
を満たすとする。さらに、ある整数 $k$ （ $1 \leq k \leq n$ ）について
$j = 1 \sum k - 1 a_{j} < B < j = 1 \sum k a_{j}$
が成り立つとする（ $k = 1$ のとき左辺の和は $0$ とする）。実数 $x_{1}, \dots, x_{n}$ を変数とする線形計画問題
$(P) 最大化 j = 1 \sum n c_{j} x_{j} 制約 j = 1 \sum n a_{j} x_{j} \leq B, 0 \leq x_{j} \leq 1 (j = 1, \dots, n)$
を考え、 $θ = \frac{1}{a _{k}} (B - j = 1 \sum k - 1 a_{j})$ とおく。

双対問題と相補性を用いて、点
$x^= (k - 1 個 1, \dots, 1, θ, n - k 個 0, \dots, 0)$
（すなわち $j < k$ で $x^_{j} = 1$ 、 $x^_{k} = θ$ 、 $j > k$ で $x^_{j} = 0$ ）が $(P)$ のただ 1 つの最適解であることを証明せよ。

この問題で使うもの

双対問題と双対定理（説明と入口の問題）
相補性条件（説明と入口の問題）
線形計画問題の定式化と標準形（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$(P)$ の双対問題を書き、 $x^$ と同じ目的関数値をもつ双対実行可能解を作れば最適性がわかる。一意性は、任意の最適解がその双対解と相補性条件を満たすことから導く。

ヒント 2

双対変数は、ナップサック制約に $λ$ 、上限制約 $x_{j} \leq 1$ に $u_{j}$ を対応させ、 $λ^{*} = c_{k} / a_{k}$ 、 $u_{j}^{*} = max (c_{j} - λ^{*} a_{j}, 0)$ と取るとよい。

ヒント 3

弱双対性の不等式を $\sum_{j} c_{j} x_{j} \leq \sum_{j} (a_{j} λ + u_{j}) x_{j} \leq λ B + \sum_{j} u_{j}$ の 2 段階に分けて書いておくと、最適解ではどちらも等号になり、各 $j$ ごとの条件（ $x_{j} = 0$ , $x_{j} = 1$ , 制約が等号）が取り出せる。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$0 < θ < 1$ を確かめ、 $x^$ が実行可能であることと、その目的関数値 $\sum_{j < k} c_{j} + c_{k} θ$ を示している（1 点）
双対問題（ナップサック制約と上限制約に対応する変数をもつ最小化問題）を正しく書き、弱双対性を導いている（2 点）
$λ^{*} = c_{k} / a_{k}$ , $u_{j}^{*} = max (c_{j} - λ^{*} a_{j}, 0)$ などの双対実行可能解を構成し、実行可能性と目的関数値が $x^$ の値に等しいことを示して最適性を結論している（3 点）
任意の最適解について弱双対性の不等式が等号になることから、 $j > k$ で $x_{j} = 0$ （双対制約が真に成り立つため）を導いている（2 点）
$j < k$ で $u_{j}^{*} > 0$ から $x_{j} = 1$ 、 $λ^{*} > 0$ から $\sum_{j} a_{j} x_{j} = B$ を導き、 $x_{k} = θ$ を得て一意性を結論している（2 点）

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

模範解答を読む

$x^$ の実行可能性 仮定 $\sum_{j < k} a_{j} < B < \sum_{j \leq k} a_{j}$ から $0 < B - \sum_{j < k} a_{j} < a_{k}$ 、よって $0 < θ < 1$ 。したがって $0 \leq x^_{j} \leq 1$ がすべての $j$ で成り立ち、
$j \sum a_{j} x^_{j} = j < k \sum a_{j} + a_{k} θ = B \leq B$
である。目的関数の値は $\sum_{j} c_{j} x^_{j} = \sum_{j < k} c_{j} + c_{k} θ$ 。

双対問題 制約 $\sum_{j} a_{j} x_{j} \leq B$ に乗数 $λ$ 、制約 $x_{j} \leq 1$ に乗数 $u_{j}$ を対応させると、 $(P)$ の双対問題は
$(D) 最小化 B λ + j = 1 \sum n u_{j} 制約 a_{j} λ + u_{j} \geq c_{j} (j = 1, \dots, n), λ \geq 0, u_{j} \geq 0$
である。

弱双対性 $x$ を $(P)$ の実行可能解、 $(λ, u)$ を $(D)$ の実行可能解とする。 $x_{j} \geq 0$ と $c_{j} \leq a_{j} λ + u_{j}$ より
$j \sum c_{j} x_{j} \leq j \sum (a_{j} λ + u_{j}) x_{j} = λ j \sum a_{j} x_{j} + j \sum u_{j} x_{j} . (1)$
さらに $λ \geq 0$ , $\sum_{j} a_{j} x_{j} \leq B$ と $u_{j} \geq 0$ , $x_{j} \leq 1$ より
$λ j \sum a_{j} x_{j} + j \sum u_{j} x_{j} \leq λ B + j \sum u_{j} . (2)$
よって $\sum_{j} c_{j} x_{j} \leq B λ + \sum_{j} u_{j}$ 。

双対実行可能解の構成 $λ^{*} = \frac{c _{k}}{a _{k}}$ 、 $u_{j}^{*} = max (c_{j} - λ^{*} a_{j}, 0)$ とおく。比の仮定から
- $j < k$ では $\frac{c _{j}}{a _{j}} > \frac{c _{k}}{a _{k}}$ なので $u_{j}^{*} = c_{j} - λ^{*} a_{j} > 0$ 、
- $j = k$ では $c_{k} - λ^{*} a_{k} = 0$ なので $u_{k}^{*} = 0$ 、
- $j > k$ では $\frac{c _{j}}{a _{j}} < \frac{c _{k}}{a _{k}}$ なので $c_{j} - λ^{*} a_{j} < 0$ 、 $u_{j}^{*} = 0$ 。

$λ^{*} > 0$ , $u_{j}^{*} \geq 0$ であり、 $a_{j} λ^{*} + u_{j}^{*} = max (c_{j}, a_{j} λ^{*}) \geq c_{j}$ なので $(λ^{*}, u^{*})$ は $(D)$ の実行可能解である。その目的関数値は
$B λ^{*} + j < k \sum (c_{j} - λ^{*} a_{j}) = λ^{*} (B - j < k \sum a_{j}) + j < k \sum c_{j} = \frac{c _{k}}{a _{k}} \cdot a_{k} θ + j < k \sum c_{j} = j < k \sum c_{j} + c_{k} θ$
で、 $x^$ の目的関数値と一致する。

$x^$ の最適性 弱双対性より、 $(P)$ の任意の実行可能解 $x$ について $\sum_{j} c_{j} x_{j} \leq B λ^{*} + \sum_{j} u_{j}^{*} = \sum_{j} c_{j} x^_{j}$ 。よって $x^$ は最適解である。

一意性（相補性条件） $x$ を $(P)$ の任意の最適解とすると $\sum_{j} c_{j} x_{j} = \sum_{j} c_{j} x^_{j} = B λ^{*} + \sum_{j} u_{j}^{*}$ なので、 $(λ, u) = (λ^{*}, u^{*})$ に対する不等式 $(1)$ , $(2)$ はともに等号で成り立つ。

$(1)$ の等号: $\sum_{j} (a_{j} λ^{*} + u_{j}^{*} - c_{j}) x_{j} = 0$ 。各項は $0$ 以上（ $a_{j} λ^{*} + u_{j}^{*} - c_{j} \geq 0$ , $x_{j} \geq 0$ ）なので、各項が $0$ である。 $j > k$ では $a_{j} λ^{*} + u_{j}^{*} - c_{j} = a_{j} (\frac{c _{k}}{a _{k}} - \frac{c _{j}}{a _{j}}) > 0$ なので $x_{j} = 0$ 。
$(2)$ の等号: $λ^{*} (B - \sum_{j} a_{j} x_{j}) + \sum_{j} u_{j}^{*} (1 - x_{j}) = 0$ 。各項は $0$ 以上なので、各項が $0$ である。 $j < k$ では $u_{j}^{*} > 0$ なので $x_{j} = 1$ 。また $λ^{*} > 0$ なので $\sum_{j} a_{j} x_{j} = B$ 。

以上から $\sum_{j < k} a_{j} + a_{k} x_{k} + 0 = B$ 、すなわち $x_{k} = \frac{1}{a _{k}} (B - \sum_{j < k} a_{j}) = θ$ 。よって $x = x^$ である。

したがって、 $x^$ は $(P)$ のただ 1 つの最適解である。

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

この問題で使うもの

ヒント

採点の観点と模範解答

次のおすすめ

この問題の確認

間違いを報告する

関連する問題