オペレーションズリサーチ 第 3 回

線形計画法 (1)(2)：生産計画問題と図解法

日本大学生産工学部 オペレーションズリサーチ（柿本・大前）

---

0. この資料の使い方

第 1 回で、数理モデルを読むための記法（集合、添字、$\sum$、$\forall$）を扱いました。今回から、その記法を使って実際の問題を 数理モデルとして書き（定式化）、解く ことを始めます。

題材は 生産計画問題 です。「何をどれだけ作れば利益が最大になるか」という、オペレーションズリサーチの最も基本的な問題です。今回は変数が 2 つの小さな問題を扱い、グラフを描いて解きます（図解法）。変数が増えたときの解き方（単体法）は第 4 回で扱います。

目的は次の 2 点です。

1. 文章で与えられた問題を、決定変数・目的関数・制約条件の 3 つに分けて数式で書ける。
2. 2 変数の線形計画問題を、グラフを描いて解ける。

第 1 回の記法で分からないものがあれば、第 1 回資料の記法早見表に戻ってください。

章立て

章	内容
1	最適化問題とは
2	生産計画問題の定式化
3	線形計画問題
4	図解法で解く
5	線形計画問題の性質と単体法への導入
6	演習

---

1. 最適化問題とは

1.1 定義

最適化問題 とは、与えられた 制約条件 のもとで 目的関数 を最大（または最小）にする問題の総称です。

用語	意味
決定変数	決めたい量。これの値を決めるのが問題の目的
目的関数	利益やコストなど、良し悪しを測る量。決定変数の式で書く
制約条件	決定変数が満たさなければならない条件。等式または不等式で書く

目的関数も制約条件も、決定変数の数式 として表現します。文章で書かれた問題をこの 3 つに分けて数式にすることを 定式化 と呼びます。

1.2 書き方（定型）

この授業では、最適化問題を次の形で書きます。

$$ \begin{aligned} & z = 3x_1 + 5x_2 \rightarrow \max, \\ \text{s.t.} \quad & x_1 + 7x_2 \le 140, \\ & 2x_1 + 4x_2 \le 100, \\ & 3x_1 + 2x_2 \le 120, \\ & x_1 \ge 0,\ x_2 \ge 0. \end{aligned} $$

• 1 行目が目的関数です。$\rightarrow \max$ は「この式を最大化する」という意味です。最小化なら $\rightarrow \min$ と書きます。
  • 読み方: 「$z = 3x_1 + 5x_2$ を最大化する」
• s.t. は subject to の略で、「次の条件のもとで」という意味です。s.t. 以下に並んだ式がすべて制約条件です。
• 本によっては目的関数を $\max\ 3x_1 + 5x_2$ や $\text{maximize}\ 3x_1 + 5x_2$ と書き、s.t. を「subject to」「制約条件:」と書きます。意味は同じです。

1.3 最適化問題の代表例

目的関数と制約条件の 式の形 と、決定変数の 型 によって、問題が分類されます。

種類	特徴	例
線形計画問題	目的関数と制約条件がすべて 1 次式	$z = x + 2y \rightarrow \max$, s.t. $3x + 2y \le 10$, $x, y \in \mathbb{R}_+$
非線形計画問題	目的関数か制約条件に 2 次以上の式を含む	$(x-4)^2 + (y-3)^2 \le 6$ のような制約
整数計画問題	決定変数が整数の値しかとらない	上の線形計画問題で $x, y \in \mathbb{Z}_+$ としたもの

この授業で扱うのは 線形計画問題（第 3〜4 回）と 整数計画問題（第 5 回）です。

1.4 読むときの手順

最適化問題の式を見たら、次の順で確認してください。

1. 決定変数はどれか: 決めたい量として定義された文字（多くは $x$）と、その個数・型
2. 目的関数は何か: $\rightarrow \max$（または $\min$）が付いた式。何の合計か
3. 制約は何本あるか: s.t. 以下の各行。$\forall$ が付いていれば、その集合の要素数が本数（第 1 回 §4.4）
4. 各制約は何を言っているか: 左辺が何の量で、右辺が何の上限（下限）か

---

2. 生産計画問題の定式化

2.1 問題

次のような問題を考えます。

ある会社は 2 種類の製品 $P_1$、$P_2$ を生産している。

• 製品 $P_1$、$P_2$ は 3 種類の材料 $M_1$、$M_2$、$M_3$ からできている。
• 製品 $P_1$、$P_2$ を 1 kg 生産したときの利益はそれぞれ 3 万円、5 万円。
• 製品 $P_1$、$P_2$ を 1 kg 生産するのに必要な材料 $M_1$〜$M_3$ の量は下の表のとおり。
• 材料 $M_1$〜$M_3$ の在庫はそれぞれ 140、100、120 kg。

利益を最大化するには、製品 $P_1$、$P_2$ をそれぞれ何 kg 生産すべきか。

	$P_1$	$P_2$	在庫
$M_1$ [kg]	1	7	140
$M_2$ [kg]	2	4	100
$M_3$ [kg]	3	2	120
利益 [万円/kg]	3	5	—

表の読み方: 「$P_1$ を 1 kg 作るには $M_1$ が 1 kg、$M_2$ が 2 kg、$M_3$ が 3 kg いる」「$P_2$ を 1 kg 作るには $M_1$ が 7 kg、…」です。第 1 回 §2.4 の $a_{ij}$ の表と同じ構造です。

2.2 目的と条件を言葉で整理する

定式化の前に、問題文を「目的」と「条件」に分けます。

	言葉で	数式にしたもの
この問題の 目的	製品 $P_1$、$P_2$ を生産して得られる利益を最大化する	目的関数
目的を達成するための 条件	製品を生産するとき、材料 $M_1$〜$M_3$ の使用量は在庫を超えてはいけない	制約条件

2.3 決定変数を定義する

まず「何を決めるのか」をはっきりさせ、文字を割り当てます。

$x_1$、$x_2$ を、それぞれ製品 $P_1$、$P_2$ の生産量 [kg] とする。

これが 決定変数 です。定式化は必ずこの一文から始めてください。文字が何を表すか（単位も含めて）を書かないと、以後の式が読めなくなります。

2.4 目的関数を書く

目的は「総利益の最大化」です。$P_1$ を 1 kg 作ると 3 万円、$P_2$ を 1 kg 作ると 5 万円の利益なので、総利益は

$$ z = 3x_1 + 5x_2 $$

です。これを最大化するので、$z = 3x_1 + 5x_2 \rightarrow \max$ と書きます。

2.5 制約条件を書く

条件は「各材料の使用量が在庫以下」です。材料ごとに 1 本ずつ不等式を作ります。

材料	使用量	在庫	制約条件
$M_1$	$P_1$ に 1 kg/kg、$P_2$ に 7 kg/kg	140	$x_1 + 7x_2 \le 140$
$M_2$	$P_1$ に 2 kg/kg、$P_2$ に 4 kg/kg	100	$2x_1 + 4x_2 \le 100$
$M_3$	$P_1$ に 3 kg/kg、$P_2$ に 2 kg/kg	120	$3x_1 + 2x_2 \le 120$

表の 行 を左から右へ読むと、そのまま 1 本の制約条件になります。表の行数（材料の数）だけ制約条件があります。

さらに、生産量は負になれないので

$$ x_1 \ge 0, \quad x_2 \ge 0 $$

を加えます。これを 非負条件 と呼びます。問題文に書かれていなくても、「量」を表す変数には必ず付けます。

2.6 定式化（まとめ）

$$ \begin{aligned} & z = 3x_1 + 5x_2 \rightarrow \max, \\ \text{s.t.} \quad & x_1 + 7x_2 \le 140, \\ & 2x_1 + 4x_2 \le 100, \\ & 3x_1 + 2x_2 \le 120, \\ & x_1 \ge 0,\ x_2 \ge 0. \end{aligned} $$

2.7 第 1 回の記法で書くと

材料の集合を $I = \{1, 2, 3\}$、製品の集合を $J = \{1, 2\}$ とし、製品 $j$ の利益を $c_j$、製品 $j$ を 1 kg 作るのに必要な材料 $i$ の量を $a_{ij}$、材料 $i$ の在庫を $b_i$ とすると、同じ問題は次のように書けます。$a_{ij}$ は §2.1 の表の $i$ 行 $j$ 列の値です（第 1 回 §2.4）。

$$ \begin{aligned} & z = \sum_{j \in J} c_j x_j \rightarrow \max, \\ \text{s.t.} \quad & \sum_{j \in J} a_{ij} x_j \le b_i, \quad \forall i \in I, \\ & x_j \ge 0, \quad \forall j \in J. \end{aligned} $$

製品が 2 種類でも 100 種類でも、この形は変わりません。$I = \{1, 2, 3\}$、$J = \{1, 2\}$ で展開すると §2.6 の式に戻ることを確かめてください（第 1 回 §4.3 の手順）。

2.8 よくある間違い

• 決定変数を定義せずに式を書き始める → 何の式か分からなくなります。必ず「$x_1$、$x_2$ を…とする」から始めてください。
• 表の 列 を読んで制約を作る → 制約は材料ごと（表の行ごと）です。列は製品ごとの「レシピ」であって、条件ではありません。
• 非負条件を忘れる → 重要な制約条件です。必ず付けてください。

---

3. 線形計画問題

3.1 定義

線形計画問題（Linear Programming problem、LP）とは、目的関数が決定変数の 1 次式 で、制約条件がすべて決定変数の 1 次式についての等式または不等式で表される最適化問題です。

ここで、決定変数 $x_1, \dots, x_n$ の 1 次式 とは、各変数に定数を掛けて足し合わせた式

$$ a_1 x_1 + a_2 x_2 + \cdots + a_n x_n $$

のことです（$a_1, \dots, a_n$ は定数）。

つまり、目的関数が $c_1 x_1 + \cdots + c_n x_n$ の形で、どの制約条件も $a_1 x_1 + \cdots + a_n x_n \le b$（$\ge b$、$= b$ でもよい）の形で書けていれば、線形計画問題です。

§2.6 の問題では、目的関数 $3x_1 + 5x_2$ も、制約条件の左辺 $x_1 + 7x_2$、$2x_1 + 4x_2$、$3x_1 + 2x_2$、$x_1$、$x_2$ もすべて 1 次式なので、線形計画問題です。

変数どうしの積（$x_1 x_2$）、2 乗（$x_1^2$）、変数の関数（$\sqrt{x_1}$ など）が 1 か所でもあれば 1 次式ではなく、線形計画問題ではありません（非線形計画問題。§1.3）。

2 変数なら、等式 $a_1 x_1 + a_2 x_2 = b$ は平面上の 直線 になります。これが「線形」の由来です。

3.2 線形計画問題の形

目的関数と制約条件がすべて 1 次式であれば、制約が等式でも不等式でも、$\rightarrow \max$ でも $\rightarrow \min$ でも、線形計画問題です。第 4 回で、これらを決まった形（標準形）にそろえる方法を扱います。

3.3 なぜ線形計画問題を学ぶのか

• 現実の問題の多くが、線形計画問題として書ける（生産計画、輸送計画、配合計画、人員配置など）
• 変数が多くても実用的に最適解を求められる方法（単体法、第 4 回）がある。
• 整数計画問題（第 5 回）やネットワークの問題（第 6 回）も、線形計画問題を土台にしている

---

4. 図解法で解く

変数が 2 つなら、$x_1$ を横軸、$x_2$ を縦軸にとったグラフで問題を解けます。手順は次の 4 つです。

1. 制約条件を等式にして直線を引く
2. 不等式が表す領域を塗り、共通部分（実行可能領域）を求める
3. 実行可能領域の頂点をすべて求める
4. 各頂点で目的関数の値を計算し、最大のものを選ぶ

4.1 制約条件を直線として描く

不等式のままでは描けないので、まず等号に変えて直線を引きます。

制約条件	直線
$x_1 + 7x_2 \le 140$	$x_1 + 7x_2 = 140$
$2x_1 + 4x_2 \le 100$	$2x_1 + 4x_2 = 100$
$3x_1 + 2x_2 \le 120$	$3x_1 + 2x_2 = 120$

直線は、両軸との交点を求めて引くのが簡単です。$x_1 + 7x_2 = 140$ なら、$x_2 = 0$ のとき $x_1 = 140$、$x_1 = 0$ のとき $x_2 = 20$ です。

4.2 不等式が表す領域

直線は平面を 2 つに分けます。不等式 $x_1 + 7x_2 \le 140$ はそのどちらか一方の側（直線上を含む）を表します。

どちら側かは、直線上にない点を 1 つ代入して確かめます。原点 $(0, 0)$ を入れると $0 \le 140$ で成り立つので、原点を含む側 が $x_1 + 7x_2 \le 140$ の領域です。

2 本目 $2x_1 + 4x_2 \le 100$ も、原点を入れると $0 \le 100$ で成り立つので原点側です。

3 本目 $3x_1 + 2x_2 \le 120$ も同じく原点側です。

3 つの領域を 1 つの図に重ねます。3 本の制約をすべて満たすのは、3 つの領域が 重なっている部分 だけです。

重なっている部分だけを取り出すと、次の図の黄色の領域になります。各直線に付けた矢印は、その不等式が表す側を示しています。

4.3 実行可能領域

§4.2 の共通部分に、非負条件（$x_1 \ge 0$ は縦軸の右側、$x_2 \ge 0$ は横軸の上側）を加えたものが 実行可能領域 です。上の図では最初から第 1 象限だけを描いているので、黄色の領域がそのまま実行可能領域です。

• 実行可能領域の中の点は、すべての制約条件を満たす $(x_1, x_2)$ の組です。これを 実行可能解 と呼びます。
• 実行可能領域の外の点は、少なくとも 1 本の制約を破っています。
• この領域は「へこみのない多角形」になります。これを 凸領域 と呼びます。線形計画問題の実行可能領域は必ず凸領域です。

領域の角を 頂点 と呼びます。図では O、A、B、C、D の 5 つです。

4.4 頂点の座標を求める

頂点は 2 本の直線の交点なので、連立方程式を解けば 座標が求まります。図から目分量で読まず、必ず計算してください。

頂点	交わる 2 本	連立方程式	座標
O	$x_1 = 0$、$x_2 = 0$	—	$(0, 0)$
A	$x_2 = 0$、$3x_1 + 2x_2 = 120$	$3x_1 = 120$	$(40, 0)$
B	$3x_1 + 2x_2 = 120$、$2x_1 + 4x_2 = 100$	下に示す	$(35, 7.5)$
C	$2x_1 + 4x_2 = 100$、$x_1 + 7x_2 = 140$	下に示す	$(14, 18)$
D	$x_1 = 0$、$x_1 + 7x_2 = 140$	$7x_2 = 140$	$(0, 20)$

頂点 B の計算: 1 本目を 2 倍して 2 本目を引き、$x_2$ を消します。

$$ \begin{aligned} 6x_1 + 4x_2 &= 240 \\ 2x_1 + 4x_2 &= 100 \\ \hline 4x_1 &= 140 \quad \Rightarrow \quad x_1 = 35,\ x_2 = 7.5 \end{aligned} $$

頂点 C の計算: 2 本目を 2 倍して 1 本目を引きます。

$$ \begin{aligned} 2x_1 + 14x_2 &= 280 \\ 2x_1 + 4x_2 &= 100 \\ \hline 10x_2 &= 180 \quad \Rightarrow \quad x_2 = 18,\ x_1 = 14 \end{aligned} $$

4.5 目的関数をグラフで見る

目的関数 $z = 3x_1 + 5x_2$ は、$z$ の値を 1 つ決めるごとに 1 本の直線になります（$z = 30$ なら $3x_1 + 5x_2 = 30$）。これを目的関数の 等高線 と呼びます。$z$ を大きくすると、等高線は右上に平行移動します。

したがって、実行可能領域と交わる範囲で等高線をできるだけ右上に動かしたときの位置が最適解になります。右上に動かしていくと、最後に領域に触れる位置には必ず 頂点 が含まれます。等高線が領域の辺と平行なときは辺全体で触れますが、その両端も頂点です。

4.6 各頂点で目的関数を計算する

したがって、頂点だけ調べれば最適解が分かります。

頂点	$x_1$	$x_2$	$z = 3x_1 + 5x_2$
O	0	0	0
A	40	0	120
B	35	7.5	142.5
C	14	18	132
D	0	20	100

最大は頂点 B です。

最適解: $x_1 = 35$、$x_2 = 7.5$、最適値: $z = 142.5$

製品 $P_1$ を 35 kg、$P_2$ を 7.5 kg 作れば、最大利益 142.5 万円が得られる。

• 最適解: 目的関数を最大（最小）にする決定変数の値の組
• 最適値: 最適解における目的関数の値

答えを書くときは、最適解（変数の値）と最適値（目的関数の値）を必ず両方書いてください。

4.7 よくある間違い

• 頂点の座標をグラフから目分量で読む → $(35, 7.5)$ と $(34, 8)$ は図では区別できません。連立方程式で求めてください。
• 軸との交点（A、D）を頂点に数え忘れる → 非負条件 $x_1 \ge 0$、$x_2 \ge 0$ も制約です。軸も「直線」として扱ってください。
• 直線どうしの交点をすべて頂点だと思う → 実行可能領域の 外 にある交点（たとえば $x_1 + 7x_2 = 140$ と $3x_1 + 2x_2 = 120$ の交点）は頂点ではありません。領域を塗ってから、その角だけを拾ってください。
• 最適値だけ、または最適解だけを答える → 両方が答えです。

---

5. 線形計画問題の性質と単体法への導入

5.1 線形計画問題の性質

§4 で確かめたことをまとめると、次の性質になります。

線形計画問題に最適解が存在するなら、実行可能領域（凸領域）の 頂点 の中に最適解がある。

したがって、最適解が存在する問題なら、「頂点をすべて列挙して目的関数を比べる」という方法で最適解が見つかります。最適解が存在しないのは、制約をすべて満たす点が無いときと、目的関数をいくらでも大きくできるときです。

5.2 この解き方の限界

今回の問題は変数 2 個、制約 3 本（非負条件を除く）でした。しかし現実の問題では、たとえば

• 作りたい製品が 100 種類 → 変数 $x_1, \dots, x_{100}$ の 100 個
• 材料や設備の条件が 50 本 → 制約 50 本

といった規模になります。100 次元の空間にグラフは描けませんし、頂点の数も膨大になるので、全部調べる方法は現実的ではありません。

5.3 単体法（次回）

そこで使うのが 単体法（シンプレックス法）です。考え方は次のとおりです。

1. どれか 1 つの頂点（たとえば原点 O）から出発する
2. 目的関数が増える方向へ、辺に沿って隣の頂点へ移動する
3. 目的関数がこれ以上増えない頂点に着いたら終了。そこが最適解

どちらへ移るかは、目的関数の係数で決めます。原点 O では、$z = 3x_1 + 5x_2$ の係数が大きい $x_2$ を増やす方向、つまり縦軸に沿って D へ移ります（D から先の計算は第 4 回）。

図では O（$z = 0$）→ D（$z = 100$）→ C（$z = 132$）→ B（$z = 142.5$）と移動し、B の隣（A、C）はどちらも $z$ が小さいので B で終了します。頂点 A は調べていません。

単体法の特徴:

• 変数が増えても、同じ手順を機械的に繰り返せる（グラフは不要）
• 全部の頂点を調べなくてよい
• 最適解があれば、有限回の移動で到達する

第 4 回では、この「頂点から隣の頂点へ移る」操作を、グラフを使わずに式の変形だけで行う方法を学びます。

---

6. 演習

演習問題は問題用紙と解答用紙で配布します。生産計画問題を 2 題、§2 の手順で定式化し、§4 の手順で図解法により解いてください。解答は解答用紙に書いて提出してください（出席確認を兼ねます）。