線形計画の応用例: 線形計画入門 4

この章では、世の中の様々な問題を線形計画として定式化します。直面している問題をどのようにして線形計画に落とし込むかは、線形計画のユーザーにとっては非常に重要な技術です。

ここでは具体例をいくつか見ていくことで定式化に慣れていきます。

工場の生産量

あなたは薬品工場のオーナーだとします。この工場では薬品 A, B を生産しており、それぞれの薬品をどれだけ生産するかを決定したいと考えています。それぞれの薬品は、過去の経験から、1g 作るごとに 80, 50 円の利益が見込めます。ただし、これらの薬品を作るには希少材料 X, Y を消費してしまいます。材料の消費量は以下の表で表されます。

いま、工場には材料 X は 100 mg、材料 Y は 120 mgあります。材料が不足しないように利益を最大化するには、薬品をそれぞれ何gずつ作ればよいでしょう。

これは典型的な線形計画問題です。薬品を作る量が決定変数、材料の上限が制約条件になります。具体的には以下のように定式化できます。

$$\begin{align*}&\underset{(x_A, x_B) \in \mathbb{R}^2}{\text{maximize}} \quad 80 x_A + 50 x_B \\ &\quad \text{s.t.} \qquad 20 x_A + 20 x_B \le 100 \\ &\qquad \qquad 40 x_A + 20 x_B \le 120 \\ &\qquad \qquad (x_A, x_B) \ge 0\end{align*}$$

輸送問題

あなたは複数の製鉄工場のオーナーだとします。工場 A, B, C には鉄の在庫がそれぞれ 80 トン、40トン、50トンあります。取引先 X, Y, Z は鉄をそれぞれ 20 トン、60 トン、70 トン要求しています。各工場から各取引先に薬品を輸送するには 1g あたり以下のコストがかかります。

どの工場からどの取引先にそれぞれどれだけの量の鉄を送るのが最もコストを抑えられるでしょうか。

決定変数は各工場から各取引に輸送する量の 9 次元、制約条件は各工場の在庫が不足しない条件と、各取引先の要求を満たす条件になります。これは以下のように定式化できます。

$$\begin{align*}&\text{minimize} \quad 200 x_{AX} + 600 x_{AY} + 900 x_{AZ} \\ &\qquad \qquad \qquad + 800 x_{BX} + 400 x_{BY} + 600 x_{BZ} \\ &\qquad \qquad \qquad + 1200 x_{CX} + 800 x_{CY} + 100 x_{CZ} \\ &\quad \text{s.t.} \qquad x_{AX} + x_{AY} + x_{AZ} \le 80 \\ &\qquad \qquad x_{BX} + x_{BY} + x_{BZ} \le 40 \\ &\qquad \qquad x_{CX} + x_{CY} + x_{CZ} \le 50 \\ &\qquad \qquad x_{AX} + x_{BX} + x_{CX} = 20 \\ &\qquad \qquad x_{AY} + x_{BY} + x_{CY} = 60 \\ &\qquad \qquad x_{AZ} + x_{BZ} + x_{CZ} = 70 \\ &\qquad \qquad x \ge 0\end{align*}$$

制約条件の最初の三行が各工場の在庫の条件、次の三行が取引先の条件を表しています。

金融ポートフォリオ（平均・絶対偏差モデル）

再び金融資産の投資方法について考えましょう。

第一章では単に利益を最大化することだけを考えましたが、例えば、同じ期待利益が 100 万円の投資方法であっても、実現値が 110, 90, 80, 120, … というようにほぼ確実に利益が得られる方法と、210, -10, -50, 250, … というように、大きく勝てる場合もあれば大きく損をする場合もあるリスクの大きい方法があります。いくら利益が高くてもリスクが大きければ良い投資方法とはいえません。ここでは利益を高くしつつ、リスクを抑えるような定式化を考えます。

簡単のため、株式 A と B のみを考えます。これらの株を 1 株買った時の過去の利益は以下のようであったとします。

これらの平均をとり、株式 A に投資すると期待利益は 50 円、株式 B に投資すると期待利益は 30 円と推定できます。

株式 A, B をそれぞれ \(x, y\) 株ずつ買うとします。このときの期待利益は \(50 x + 30 y\) です。このように購入していた場合の各年における期待利益からのずれは

です。これらの平均値が低くなるように投資プランを考えたいです。ここではシンプルに、（期待利益）-（期待値からのずれの平均値）が最大になるような投資プランを求めましょう。このようなモデルを平均・絶対偏差モデルといいます。予算制約は以前と同様に \(100 x + 300 y \le 50000\) とします。これは以下のように定式化できます。 $$\begin{align}&\underset{(x, y) \in \mathbb{R}^2}{\text{maximize}} \quad 50 x + 30 y – \frac{1}{3} |40x – 10y| – \frac{1}{3} |40x + 20y| – \frac{1}{3} |10y| \\ &\quad \text{s.t.} \qquad 100 x + 300 y \le 50000 \\ &\qquad \qquad (x, y) \ge 0\end{align}$$

目的関数に絶対値関数が含まれているのでこれは線形計画とはいえません。しかし、以下のような工夫をすることで等価な線形計画に変形することができます。\(s_1 = |40 x – 10y|, s_2 = |40x + 20y|, s_3 = |10y|\) と置きます。\(|40 x – 10 y| \le s_1\) は \(40 x – 10 y \le s_1\) かつ \(-(40 x – 10 y) \le s_1\) と等価であることおよび \(s_1\) は小さい方が目的関数が大きくなるので最適解は不等式の下限において達成されることを考えると、上記の最適化問題は以下の線形計画と等価であることが分かります。

$$\begin{align}&\underset{(x, y, s_1, s_2, s_3) \in \mathbb{R}^5}{\text{maximize}} \quad 50 x + 30 y – \frac{1}{3} s_1 – \frac{1}{3} s_2 – \frac{1}{3} s_3 \\ &\quad \text{s.t.} \qquad 100 x + 300 y \le 50000\\ &\qquad \qquad \hspace{0.4in} 40x – 10y \le s_1 \\ &\qquad \qquad -(40x – 10y) \le s_1 \\ &\qquad \qquad \hspace{0.4in} 40x + 20y \le s_2 \\ &\qquad \qquad -(40x + 20y) \le s_2 \\ &\qquad \qquad \hspace{0.25in} 10y \le s_3 \\ &\qquad \qquad -10y \le s_3 \\ &\qquad \qquad (x, y, s_1, s_2, s_3) \ge 0\end{align}$$

このように、最大化問題の目的関数に含まれるマイナス絶対値および、最小化問題における絶対値は等価な線形関数に置き換えることができます。一方で、最大化問題の絶対値および最小化問題のマイナス絶対値は置き換えることができないことに注意してください。そのような場合は最適化が下限において達成されず、むしろ \(s_i\) 不等式制約から離れていく方向に動いていくからです。発展的な議論ですが、絶対値関数は凸、マイナス絶対値関数は凹だからということでも説明されます。

直線あてはめ（チェビシェフ近似）

あなたは製鉄所のオーナーで、鉄鉱石の重量と鉄の含有量の関係を調べています。いくつかの標本について測定してみると、以下のようになりました。

どうやら重量と含有量には一次式の関係が成り立ちそうなので、含有量 = \(\alpha \cdot\) 重量 + \(\beta\) という予測モデルで当てはめてみることにしました。予測モデルの当てはまりの良さを残差の最大値とします。予測モデルのパラメータ \(\alpha, \beta\) を求める問題は以下のように定式化できます。

$$\begin{align}&\underset{(\alpha, \beta) \in \mathbb{R}^2}{\text{minimize}} \quad \max \begin{Bmatrix} |3.8 \alpha + \beta – 22.1| \\ |4.0 \alpha + \beta – 23.2| \\ |3.5 \alpha + \beta – 21.3| \\ |3.9 \alpha + \beta – 21.9| \end{Bmatrix}\end{align}$$

この問題も目的関数が線形ではありませんが、絶対偏差モデルの時と同様の考え方で、以下の等価な線形計画に変形することができます。補助変数として、\(t = \)上記の目的関数と置きます。\(\max(a, b, c) \le t\) は \(a \le t\) かつ \(b \le t\) かつ \(c \le t\) と等価であること、\(|a| \le t\) は \(-t \le a \le t\) と等価であること、\(t\) は小さい方が目的関数が小さくなるので最適解が不等式の下限において達成されることを考えると、上記の最適化問題は以下の線形計画と等価であることが分かります。

$$\begin{align}&\underset{(\alpha, \beta, t) \in \mathbb{R}^3}{\text{minimize}} \quad t \\ &\quad \text{s.t.} \qquad -t \le 3.8 \alpha + \beta – 22.1 \le t \\ &\qquad \qquad -t \le 4.0 \alpha + \beta – 23.2 \le t \\ &\qquad \qquad -t \le 3.5 \alpha + \beta – 21.3 \le t \\ &\qquad \qquad -t \le 3.9 \alpha + \beta – 21.9 \le t\end{align}$$

予測モデルの当てはまりの良さとして考えられるのは残差の最大値だけではありあません。残差の話とすると絶対値の和を最小化する問題なので、絶対偏差モデルの時と同様のテクニックで線形計画として定式化できます。また、一番典型的なのは残差の二乗和とすることですが、これは目的関数が決定変数の二次関数になるので線形計画では定式化できません。そのようなモデルの最適化には線形計画以外の最適化手法を使う必要があります。一般に、モデリングしたい問題の性質とデータの規模を考えて適切なモデルと最適化手法を選ぶことになります。

まとめ

次章では、線形計画の解き方について考察を進めていきます。

前章へもどる 第一章へもどる 次章へすすむ