OR・線形計画法とは（全体像）
OR（オペレーションズリサーチ）は、「限られた条件のもとで、いちばん良い選び方を数学で見つける」ための手法のまとまり。工場で「どの製品をいくつ作れば利益が最大か」「人をどう配置すればムダがないか」を決めるのに使う。
その代表が線形計画法（LP）。次の2つで問題を表す。
- 目的 … 最大化したいもの（利益など）、または最小化したいもの（コストなど）。
- 制約 … 守らなければならない条件（材料の上限、時間の上限など）。
目的も制約もまっすぐな式（一次式）で書けるとき、これを線形計画問題といい、効率よく解く方法がシンプレックス法だ。
詳しく：LPとシンプレックス・整数計画だけ覚えれば戦える
ここが記事の心臓部。まずは線形計画法（LP）のイメージ。
線形計画法（LP）の中身
| 要素 | 内容 |
|---|---|
| 目的関数 | 最大化（利益）または最小化（コスト）したい式 |
| 制約条件 | 材料・時間などの上限を表す式（守るべき条件） |
| 解き方 | シンプレックス法で最適な組み合わせを求める |
たとえば「製品Aと製品Bを、材料と時間の上限を守りながら、利益が最大になるように作る数を決める」のがLP。条件を満たす範囲のなかで、いちばん得する点を探す問題だ。つまり、守るべき条件の内側で、目的がいちばん良くなる組み合わせを見つける、というわけだ。
その点を探すのがシンプレックス法。条件を満たす範囲の「角（頂点）」を渡り歩いて、最も得する角にたどり着く。理論上は時間がかかる場合もあるが、実際にはとても速く解けることが多い。
次に、よく問われる整数計画法（IP）との違い。
線形計画法（LP）と整数計画法（IP）
| 線形計画法（LP） | 整数計画法（IP） | |
|---|---|---|
| 変数 | 連続（小数もOK） | 整数だけ（1個、2個…） |
| 難しさ | 効率よく解ける | 難しくなりやすい（NP困難） |
LPは「2.5個」のような小数の答えも許すが、IPは「人を2.5人」のように小数にできないもの（個数・人数）を扱うため、変数を整数に限る。そのぶんIPは一気に難しくなる、と押さえておく。
わかりやすく言い換えると
要するに、線形計画法は「条件を守りながら、いちばん得する組み合わせを探す」ことだ。
イメージは「限られた予算で、いちばん満足度が高い買い物の組み合わせを選ぶ」感じ。予算（制約）を超えないなかで、満足度（目的）が最大になる組み合わせを探す。
シンプレックス法は「選べる範囲の角を順に見て回り、いちばん得する角で止まる」やり方。整数計画法は、これに「個数は小数にできない」という縛りが加わったもので、ぐっと難しくなる、というわけだ。
試験のツボ
🔴 一番出る：線形計画法（LP）の中身
①目的（最大化・最小化）と制約（守る条件）で表す
②目的も制約もまっすぐな式（一次式）
③解き方はシンプレックス法
🔴 次に出る：LPとIPの違い
①LP＝変数が連続（小数もOK）
②IP＝変数が整数だけ（だから難しくなりやすい）
🟡 押さえると安定：シンプレックス法の性質
①条件を満たす範囲の角（頂点）を渡り歩く
②理論上は時間がかかる場合もあるが実際は高速
よくある間違い
①「線形計画法と整数計画法は同じものである」→ ✗ LPは変数が連続（小数OK）、IPは変数が整数だけ。別もの。
②「シンプレックス法はつねに一瞬で必ず最速に解ける」→ ✗ 理論上は時間がかかる場合もある。ただし実際はとても速いことが多い。
③「線形計画法では制約条件を無視して目的だけを最大化する」→ ✗ 制約（条件）を守ったうえで目的を最大化する。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（LPの中身）
線形計画法（LP）に関する次の記述のうち、正しいものはどれか。
- 制約条件を一切考えず、目的の値をひたすら大きくするだけの手法である
- 目的（最大化や最小化）を、制約条件を守りながら求める最適化の手法だ
- 目的関数も制約条件も曲線でなければならず、直線では表せない手法である
- 数値の計算とは関係がなく、文章の意味を解析するために使う手法である
解答は 2 だぜ。
線形計画法は目的（最大化・最小化）を、制約条件を守りながら求める最適化の手法だ。「制約を超えない範囲で、いちばん得する点」を探すんだな。
選択肢1は「制約を考えない」が誤り。選択肢3は「曲線でなければならない」が誤り（まっすぐな一次式）。選択肢4は「文章解析に使う」が誤りだぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 制約条件を守る必要がある |
| 2 | ✓ | 目的を制約のもとで最適化する |
| 3 | ✗ | 一次式（まっすぐな式）で表す |
| 4 | ✗ | 数値の最適化手法である |
オリジナル問題2（シンプレックス法）
シンプレックス法に関する次の記述のうち、正しいものはどれか。
- シンプレックス法は線形計画問題ではなく、文字列の検索に使われる手法である
- シンプレックス法は乱数を投げるだけで、最適解とは無関係な答えを返す手法だ
- シンプレックス法は理論上どんな問題でも一瞬で必ず解ける、万能の手法である
- シンプレックス法は条件を満たす範囲の角を渡り歩き、最も得する点を見つける
解答は 4 だぜ。
シンプレックス法は条件を満たす範囲の角（頂点）を渡り歩いて、最も得する点を求める。線形計画問題を解く代表的な方法だ。実際にはとても速く解けることが多いぜ。
選択肢1は「文字列検索」が誤り。選択肢2は「乱数で無関係な答え」が誤り。選択肢3は「一瞬で必ず・万能」が誤りで、理論上は時間がかかる場合もあるぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 線形計画問題を解く手法 |
| 2 | ✗ | 最適解を求める手法 |
| 3 | ✗ | 理論上は時間がかかる場合もある |
| 4 | ✓ | 角を渡り歩いて最適点を求める |
オリジナル問題3（LPとIPの違い）
線形計画法（LP）と整数計画法（IP）の違いに関する次の記述のうち、正しいものはどれか。
- LPは変数が連続で小数もよく、IPは変数が整数だけで難しくなりやすい
- LPもIPも変数は整数だけに限られ、扱える問題にまったく違いはない
- IPは変数が小数でもよく、LPよりつねに簡単に解ける手法のことである
- LPは文章の解析、IPは画像の解析に使う、用途のまったく異なる手法だ
解答は 1 だぜ。
LPは変数が連続（小数もOK）、IPは変数が整数だけだ。IPは「人を2.5人」みたいにできないものを扱うので、そのぶん難しく（NP困難に）なりやすいんだ。
選択肢2は「どちらも整数だけ・違いがない」が誤り。選択肢3はLPとIPが逆。選択肢4は「文章・画像解析」が誤りだぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | LPは連続・IPは整数だけで難しい |
| 2 | ✗ | LPは連続変数を扱える |
| 3 | ✗ | IPは整数だけで難しくなりやすい |
| 4 | ✗ | どちらも数値の最適化手法 |
まとめ
押さえどころ
- 🔴 線形計画法（LP） ＝ 目的（最大化・最小化）を制約のもとで求める。解き方はシンプレックス法。
- 🔴 LPとIPの違い ＝ LPは変数が連続（小数OK）、IPは変数が整数だけ（だから難しい）。
- 🟡 シンプレックス法 ＝ 条件を満たす範囲の角を渡り歩く。理論上は時間がかかる場合もあるが実際は高速。
次に学ぶ
- グラフ理論（最小全域木・最短経路） ── ORで扱うネットワークフローの土台。点と線で最適化を考える発想がつながる。
- 動的計画法（DP） ── 問題を小さく分けて答えを再利用する最適化の手法。ORのもう一つの柱として押さえたい。
執筆: SikakuQuest編集部