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

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

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

4 個のデータ点
$(x_{i}, y_{i}) = (0, 1), (1, 2), (2, 1), (3, 5) (i = 1, 2, 3, 4)$
に直線 $y = a + b x$ を当てはめる。残差 $r_{i} = y_{i} - (a + b x_{i})$ の絶対値の最大値 $max_{i} ∣ r_{i} ∣$ を最小にしたい。これは、実数 $a, b, t$ を変数とする次の線形計画問題として書ける。
$minimize subject to t - t \leq y_{i} - (a + b x_{i}) \leq t (i = 1, 2, 3, 4)$
この線形計画問題の最適解はただ 1 つである。その最適解 $(a, b, t)$ を求めよ。

この問題で使うもの

線形計画問題の定式化と標準形（説明と入口の問題）
双対問題と双対定理（説明と入口の問題）
端点（基底解）の列挙による最適解（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$t$ の下界を作るために、残差 $r_{i}$ の一次結合で $a, b$ が消えるもの（双対問題の実行可能解）を探そう。3 点を選ぶと係数が決まる。

ヒント 2

$x = 0, 2, 3$ の 3 点を使うと $r_{1} - 3 r_{3} + 2 r_{4}$ は $a, b$ によらない定数になる。 $∣ r_{i} ∣ \leq t$ と三角不等式を組み合わせよう。

ヒント 3

$r_{1} - 3 r_{3} + 2 r_{4} = 8 \leq 6 t$ より $t \geq \frac{4}{3}$ 。等号成立には $r_{1} = t, r_{3} = - t, r_{4} = t$ が必要なので、これを $a, b$ について解き、残りの点の残差が $t$ 以下であることを確認しよう。

答えと解説

答えを見る

(- \frac{1}{3}, \frac{4}{3}, \frac{4}{3})

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

解説を読む

残差を $r_{1} = 1 - a, r_{2} = 2 - a - b, r_{3} = 1 - a - 2 b, r_{4} = 5 - a - 3 b$ とおく。制約は $∣ r_{i} ∣ \leq t (i = 1, 2, 3, 4)$ と同値である。

下界の導出（双対の考え方） 残差の一次結合で $a, b$ が消えるものを探す。点 $x = 0, 2, 3$ に対応する $r_{1}, r_{3}, r_{4}$ に係数 $λ_{1}, λ_{3}, λ_{4}$ を掛けて足したとき、 $a$ の係数 $- (λ_{1} + λ_{3} + λ_{4})$ と $b$ の係数 $- (2 λ_{3} + 3 λ_{4})$ がともに $0$ になるようにすると、 $λ_{4} = 2$ として $λ_{3} = - 3, λ_{1} = 1$ を得る。実際
$r_{1} - 3 r_{3} + 2 r_{4} = (1 - a) - 3 (1 - a - 2 b) + 2 (5 - a - 3 b) = 1 - 3 + 10 = 8$
であり、 $a, b$ によらず一定である。したがって、任意の実行可能解について
$8 = r_{1} - 3 r_{3} + 2 r_{4} \leq ∣ r_{1} ∣ + 3∣ r_{3} ∣ + 2∣ r_{4} ∣ \leq t + 3 t + 2 t = 6 t$
となり、 $t \geq \frac{4}{3}$ がわかる。（これは双対問題の実行可能解 $(1, - 3, 2)$ による下界であり、弱双対定理に相当する。）

下界が達成される条件 $t = \frac{4}{3}$ となるには、上の不等式がすべて等号で成り立つこと、すなわち
$r_{1} = \frac{4}{3}, r_{3} = - \frac{4}{3}, r_{4} = \frac{4}{3}$
が必要である。これを解く。 $1 - a = \frac{4}{3}$ より $a = - \frac{1}{3}$ 。 $1 - a - 2 b = - \frac{4}{3}$ より $\frac{4}{3} - 2 b = - \frac{4}{3}$ 、よって $b = \frac{4}{3}$ 。このとき $r_{4} = 5 + \frac{1}{3} - 4 = \frac{4}{3}$ となり条件を満たす。さらに $r_{2} = 2 + \frac{1}{3} - \frac{4}{3} = 1$ で、 $∣ r_{2} ∣ = 1 \leq \frac{4}{3}$ だから、 $(a, b, t) = (- \frac{1}{3}, \frac{4}{3}, \frac{4}{3})$ は実行可能である。

下界 $\frac{4}{3}$ を達成する実行可能解が存在するので、最適値は $\frac{4}{3}$ である。また、 $t = \frac{4}{3}$ となる解では上の 3 つの等式が必ず成り立ち、それらから $a, b$ がただ 1 通りに決まるので、最適解は一意である。

よって最適解は $(a, b, t) = (- \frac{1}{3}, \frac{4}{3}, \frac{4}{3})$ 。

別解

最大残差を最小にする直線は、チェビシェフの等振動定理により、3 点で残差が $+ t, - t, + t$ と交互の符号で絶対値 $t$ になる。

点 $x = 0, 2, 3$ を選ぶ。
- $1 - a = t$
- $1 - a - 2 b = - t$
- $5 - a - 3 b = t$

1 つ目から $a = 1 - t$ 。これを 2 つ目に代入すると $t - 2 b = - t$ より $b = t$ 。3 つ目に代入すると $4 + t - 3 t = t$ より $t = 4/3$ 。よって $a = - 1/3, b = 4/3$ 。

残りの点 $x = 1$ の残差は $2 - (- 1/3 + 4/3) = 1$ で、 $∣1∣ \leq 4/3$ を満たす。

検算として、各点の残差は次のとおり。
- $x = 0$ : $1 + 1/3 = 4/3$
- $x = 1$ : $1$
- $x = 2$ : $1 - (- 1/3 + 8/3) = - 4/3$
- $x = 3$ : $5 - (- 1/3 + 4) = 4/3$

符号が交互に $+, -, +$ となり、絶対値が $4/3$ に揃う 3 点があるので、これが最適解である。

答え: $(a, b, t) = (- 1/3, 4/3, 4/3)$

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題