線形計画問題の定式化と標準形

文章題から変数・不等式制約・目的関数を立てて線形計画問題 $max c^{⊤} x$ , $A x \leq b$ , $x \geq 0$ の形に書ける。スラック変数を加えて等式制約の標準形に直し、係数行列 $A$ ・右辺 $b$ ・係数 $c$ を読み取れる

前提

領域における最大・最小（数学II 図形と方程式）
行列の和・積と 2 次の逆行列（大学数学線形代数）

この技能までの道筋（47 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
乗法公式による展開（中学数学数と式）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
最大公約数と最小公倍数（算数整数の性質）
比の性質と簡単な比（算数割合と比）
相似な三角形と長さの比（算数平面図形）
三角形の相似条件と対応する辺の長さ（中学数学相似と三平方の定理）
平行線と線分の比（中学数学相似と三平方の定理）
2点間の距離と内分点・外分点（数学II 図形と方程式）
比例・反比例の式とグラフ（中学数学関数）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
因数分解（中学数学数と式）
平方完成と 2 次関数のグラフ（数学I 2次関数）
円の方程式（数学II 図形と方程式）
連立方程式の解き方（加減法・代入法）（中学数学方程式）
1 次関数の式の求め方（中学数学関数）
直線の方程式（数学II 図形と方程式）
不等式の表す領域（数学II 図形と方程式）
点と直線の距離（数学II 図形と方程式）
2 次不等式（数学I 2次関数）
円と直線の位置関係と弦の長さ（数学II 図形と方程式）
2直線の平行・垂直（数学II 図形と方程式）
円の接線（数学II 図形と方程式）
領域における最大・最小（数学II 図形と方程式）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）

説明

「何をどれだけ作れば利益が最大になるか」のような文章題を、変数・1 次の不等式・1 次の目的関数で表し、 $max c^{⊤} x, A x \leq b, x \geq 0$ という決まった形に書き直す技能です。この形にそろえておくと、問題の中身に関係なく、同じ手順（図や計算機のアルゴリズム）で扱えます。さらにスラック変数を加えて不等式を等式に直した「標準形」にすると、係数行列・右辺・目的関数の係数を機械的に読み取れます。生産計画・配合・輸送など、資源に上限がある最適化の場面で使います。

なぜそうしてよいのか

文章題の条件は、多くの場合「(1 個あたりの使用量)×(個数) の合計が上限以下」という形をしています。決めたい量を $x_{1}, \dots, x_{n}$ とおくと、各条件は $a_{i 1} x_{1} + \dots + a_{in} x_{n} \leq b_{i}$ という 1 次不等式になります。条件が $m$ 個あれば、 $a_{ij}$ を並べた $m \times n$ 行列 $A$ と縦ベクトル $x = (x_{1}, \dots, x_{n})^{⊤}$ の積 $A x$ の第 $i$ 成分がちょうど第 $i$ 条件の左辺になるので、 $m$ 本の不等式をまとめて $A x \leq b$ （成分ごとの不等号）と書けます。利益も $c_{1} x_{1} + \dots + c_{n} x_{n} = c^{⊤} x$ と 1 次式です。変数が 2 個なら、これは「領域における最大・最小」で学んだ、多角形の領域上で $a x + b y = k$ の $k$ の最大を調べる問題そのものです。

次に、不等式を等式に直す理由です。 $a_{i}^{⊤} x \leq b_{i}$ は「 $s_{i} = b_{i} - a_{i}^{⊤} x$ とおくと $s_{i} \geq 0$ 」と同じ意味です。つまり
$a_{i}^{⊤} x \leq b_{i} ⟺ a_{i}^{⊤} x + s_{i} = b_{i} を満たす s_{i} \geq 0 が存在する$
が成り立ちます。この $s_{i}$ をスラック変数といい、意味は「資源の余り」です。余りは利益に関係しないので、目的関数での係数は $0$ です。すべての条件にスラック変数を入れると、 $A x + s = b$ は行列 $[A I]$ （ $I$ は $m$ 次の単位行列）を使って $[A I] (x s) = b$ と書けます。

不等号の向きや最大・最小の違いは符号で吸収できます。 $a^{⊤} x \geq b$ は両辺に $- 1$ を掛けて $(- a)^{⊤} x \leq - b$ とし、 $min c^{⊤} x$ は $max (- c)^{⊤} x$ に直します（最適な $x$ は同じで、最適値は符号が逆になります）。なお「標準形」という語は本によって指す形が少し異なり（例えば $min$ と等式制約の組を標準形とよぶ本もあります）、ここでは「 $max c^{⊤} x, A x + s = b, x \geq 0, s \geq 0$ 」を標準形とよびます。

手順

決めたい量を変数 $x_{1}, \dots, x_{n}$ とおき、単位を確認する。個数や量は負にならないので $x_{j} \geq 0$ を書く。
各条件を 1 次不等式 $a_{i 1} x_{1} + \dots + a_{in} x_{n} \leq b_{i}$ に直す。 $\geq$ の条件は両辺に $- 1$ を掛けて $\leq$ にそろえる。
目的関数 $c_{1} x_{1} + \dots + c_{n} x_{n}$ を立てる。最小化なら係数の符号を変えて $max (- c)^{⊤} x$ にする。
係数を読み取る： $A$ の第 $i$ 行は第 $i$ 条件、第 $j$ 列は変数 $x_{j}$ に対応させ、 $A = (a_{ij})$ （ $m \times n$ ）、 $b = (b_{1}, \dots, b_{m})^{⊤}$ 、 $c = (c_{1}, \dots, c_{n})^{⊤}$ とする。
各条件にスラック変数 $s_{i} = b_{i} - (A x)_{i} (\geq 0)$ を加えて等式にする： $max c^{⊤} x + 0^{⊤} s$ 、 $[A I] (x s) = b$ 、 $x \geq 0, s \geq 0$ 。

例題

ある工場で製品 P, Q を作る。1 個あたり、P は材料 2 kg・作業 1 時間・機械 1 時間、Q は材料 1 kg・作業 3 時間・機械 1 時間を使う。使える量は材料 100 kg・作業 90 時間・機械 60 時間までで、利益は P が 1 個 3 万円、Q が 1 個 2 万円である。利益を最大にする問題を $max c^{⊤} x, A x \leq b, x \geq 0$ の形に定式化し、材料・作業・機械の順にスラック変数 $s_{1}, s_{2}, s_{3}$ を加えて標準形にせよ。そのうえで、P, Q を 20 個ずつ作る計画における $(s_{1}, s_{2}, s_{3})$ の値を求めよ。

例題の解答

手順 1：P の個数を $x_{1}$ 、Q の個数を $x_{2}$ とおく。 $x_{1} \geq 0, x_{2} \geq 0$ 。

手順 2：材料 $2 x_{1} + x_{2} \leq 100$ 、作業 $x_{1} + 3 x_{2} \leq 90$ 、機械 $x_{1} + x_{2} \leq 60$ 。すべて $\leq$ の形なので符号の調整は不要。

手順 3：利益（万円）は $3 x_{1} + 2 x_{2}$ で、これを最大化する。

手順 4：行が条件（材料・作業・機械）、列が変数（ $x_{1}, x_{2}$ ）に対応するように並べて
$A = 211131, b = 1009060, c = (32) .$
実際に $A x = 2 x_{1} + x_{2} x_{1} + 3 x_{2} x_{1} + x_{2}$ となり、各成分が各条件の左辺に一致する。

手順 5：スラック変数を加えると
$max 3 x_{1} + 2 x_{2} + 0 s_{1} + 0 s_{2} + 0 s_{3}$
$2 x_{1} + x_{2} + s_{1} = 100, x_{1} + 3 x_{2} + s_{2} = 90, x_{1} + x_{2} + s_{3} = 60,$
$x_{1}, x_{2}, s_{1}, s_{2}, s_{3} \geq 0.$
係数行列は $3 \times 5$ の $[A I] = 211131100010001$ である。

$x_{1} = x_{2} = 20$ のとき、 $s_{i} = b_{i} - (A x)_{i}$ より
$s_{1} = 100 - (40 + 20) = 40$ 、 $s_{2} = 90 - (20 + 60) = 10$ 、 $s_{3} = 60 - (20 + 20) = 20$ 。
すべて $0$ 以上なので、この計画は条件を満たしている。 $s_{i}$ は材料 40 kg・作業 10 時間・機械 20 時間の余りを表す。

答え: $(40, 10, 20)$

よくある誤り

スラック変数の条件 $s_{i} \geq 0$ を書き落とす誤り。 $2 x_{1} + x_{2} + s_{1} = 100$ だけでは $s_{1}$ が負の値もとれてしまい、元の $2 x_{1} + x_{2} \leq 100$ と同じ意味になりません。正しくは $s_{1} \geq 0$ を必ず付けます。
$\geq$ の条件にもそのままスラック変数を足してしまう誤り。 $x_{1} + x_{2} \geq 10$ を $x_{1} + x_{2} + s = 10, s \geq 0$ とすると、逆に $x_{1} + x_{2} \leq 10$ を表してしまいます。正しくは $x_{1} + x_{2} - s = 10, s \geq 0$ とするか、先に $- x_{1} - x_{2} \leq - 10$ と $\leq$ にそろえてから $- x_{1} - x_{2} + s = - 10$ とします。
最小化の目的関数の係数をそのまま $c$ にしてしまう誤り。 $min 2 x_{1} + 3 x_{2}$ を $c = (2, 3)^{⊤}$ の $max$ 問題にすると別の問題になります。正しくは $max - 2 x_{1} - 3 x_{2}$ 、つまり $c = (- 2, - 3)^{⊤}$ とし、得られた最適値の符号を戻して元の最小値とします。
$A$ の行と列を取り違える誤り。例題で製品ごとに $(211311)$ と並べると $A x$ の計算がかみ合いません（ $2 \times 3$ 行列と 2 成分ベクトルの積は定義されない）。正しくは行が条件、列が変数に対応する $3 \times 2$ 行列 $211131$ です。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

	$P$	$Q$	$R$
$A$	$4$	$6$	$9$
$B$	$5$	$3$	$7$

この技能の次に学べること

端点（基底解）の列挙による最適解（大学数学最適化・線形計画法）
双対問題と双対定理（大学数学最適化・線形計画法）