線形計画を1から — 最適化の王道

限られた在庫・予算・時間の中で最善を選ぶ、いちばん古くていちばん使われている最適化の道具。定式化の3点セットから、答えが必ず「角」にある理由、シンプレックス法の歩き方、双対が教える「材料1kgの値打ち」まで、前提知識ゼロで積み上げます。

比喩: 限られた材料で、いちばん儲かる作り方

小さなパン屋を想像してください。今日の在庫は小麦粉10kg、バター3kg、オーブンを使える時間が8時間。作れるのは食パンとクロワッサンの2種類です。それぞれ何個作れば、今日の利益がいちばん大きくなるでしょうか。

「クロワッサンのほうが材料あたりの利益がいい」と全部クロワッサンにすると、今度はバターが先に尽きます。逆に食パンばかり焼けばオーブン時間が足りない。何が先に尽きるかが、作る組み合わせによって入れ替わる。だから、どれか1つの指標を見て決めることができません。

一方でこの問題に出てくる計算は、足し算と定数倍しかありません。食パンを2倍作れば小麦粉の消費も利益もちょうど2倍。両方作ったときの消費は、それぞれの単純な合計です。この形の問題を線形計画問題（Linear Programming, LP）と呼びます。世界中の工場・物流・広告配信が、いまもこの枠組みの上で回っています。

「線形」とは、何が線形なのか

定式化はいつでも3点セットです。決定変数（こちらが決められる数）、目的関数（大きく、または小さくしたい値）、制約条件（守るべき不等式）。そして「線形」とは、目的関数も制約も変数の定数倍の足し算だけで書けている、という意味です。$x^2$ も $\sin x$ も $x_1x_2$ も出てきません。

これは強い仮定です。現実には、まとめ買いで単価が下がる（規模の経済）、食パンとクロワッサンの間でオーブンの温度を変えるのに20分かかる（段取り替え）、クロワッサンを3.7個は作れない（整数）といった形で崩れます。だから最初の仕事は「線形で書けるか」の見極めです。書けるなら、変数が数万本あっても解ける道具が丸ごと使えます。書けないなら別の枠組みに移るしかありません。

定式化してみる: 広告予算の配分

現代的な例に置き換えます。今月の予算100万円を、検索・SNS・動画の3チャネルに配る。1万円あたりの獲得件数が順に12件・8件・5件、消化できる上限が40・60・80万円、さらにブランド認知の都合で動画には最低10万円出したい。

決定変数を各チャネルへの金額 $x_1,x_2,x_3$（万円）とすれば、目的関数は $12x_1+8x_2+5x_3$、制約は $x_1+x_2+x_3\le100$ と各チャネルの上限、$x_3\ge10$、そして全部 $\ge0$。定式化はこれで終わりです。一般形はいつでもこの1行に収まります。

記号を1つずつ読みます。$x$ は決定変数を縦に並べたベクトル。$c$ は各変数の「1単位あたりの価値」（12, 8, 5）。$c^\top x$ はそれらを掛けて足した合計、つまり獲得件数の総和です。$A$ は制約の左辺の係数表、$b$ は各制約の上限値で、$Ax\le b$ は「全部の制約を同時に満たす」を1本にまとめた書き方。$x\ge0$ は「マイナスの予算は出せない」という当たり前の条件です。つまりこの式は、「上限を全部守りながら、合計の価値がいちばん大きくなる配り方を選べ」としか言っていません。

目的関数 $c^\top x$ は内積そのものです。内積は2本のベクトルの向きの一致度を測る道具でした。だから線形計画は「許された範囲の中で、$c$ といちばん向きの揃った点を探す」問題だと言い換えられます。この見方が、次に出てくるシンプレックス法でそのまま効いてきます。

幾何: 答えは必ず「角」にある

変数が2つの場合を紙に描いてください。制約 $x_1+x_2\le100$ は「直線より下側」という半平面。制約を全部重ねた領域は直線で囲まれた多角形（3変数なら多面体）で、これを実行可能領域と呼びます。

一方 $c^\top x=$ 一定 という等高線は直線で、値を変えても傾きは変わらず平行移動するだけ。だから最適化は、平行な定規を、多角形からはみ出さないぎりぎりまで $c$ の方向へ押していく作業になります。平行な直線が凸多角形と最後に触れる場所は、必ず頂点か辺全体です。

つまり最適解があるなら頂点にも最適解がある（線形計画の基本定理）。無限にある点を調べる問題が、有限個の頂点を調べる問題に落ちた — 解ける理由はこれで全部です。

ただし全列挙は無理です。変数 $n$ 本・制約 $m$ 本なら、頂点（基底解）の候補は最大 $\binom{n}{m}$ 通り。変数40本・制約20本という小さめの問題でも $\binom{40}{20}\approx1.4\times10^{11}$、需給計画なら変数は数万〜数百万本になります。

オーダー記法の読み方は計算量を1から理解するに譲ります。ここで要る結論は1つ、賢く歩く方法が必要ということです。