第 3 章

可行領域 — 制約の交わりを図で見る

切片・可行判定・交点を自力で計算し、可行領域の形を手で把握する。

各制約は「境界線と、その片側」を表します。全部を同時に満たす部分だけが可行領域です。

可行領域の形を言葉でつかむ

図が見えない環境のために、本講座の例題の可行領域を言葉で記しておきます。

制約が増えても基本構造は同じで、境界線が増えると角が増えた凸多角形になります。

2x + y ≤ 16 は、境界線 2x + y = 16 のうち「それ以下の側」を意味します。x + 2y ≤ 14 も同じです。

このように、1 本の不等式は平面を境界線で 2 つに分けたうち、片側だけを残します。この片側の領域を 半平面と呼びます。LP の可行領域は 複数の半平面の共通部分、つまりすべての制約が同時に許す領域です。

判定のコツ

どちら側かを判定する際に迷ったら、原点 (0, 0) を代入してみます。真になる側が可行側です。

境界線を描く最短ルートは、x 軸との交点と y 軸との交点を求めることです。

ただし実際の可行領域では、両方の制約を同時に満たす部分だけが残ります。

境界線を描くときは、まず軸との交点を取ると早くなります。

Q1. 境界線 2x + y = 16 で y = 0 とおくと、x はいくつでしょうか。

Q2. 境界線 x + 2y = 14 で x = 0 とおくと、y はいくつでしょうか。

ある点が可行かどうかは、すべての制約に代入して確認します。たとえば点 (5, 4) なら、

なので可行です。残量まで計算すると、どの制約が効き始めているかも見えてきます。

可行な点では残量を、不適な点では超過量を計算してみます。

Q1. 点 (x, y) = (5, 4) の切断工程の残り時間を入力してください。

時間

Q2. 同じ点 (5, 4) の仕上工程の残り時間を入力してください。

時間

Q3. 点 (7, 3) では、切断工程の制約 2x + y ≤ 16 を何時間超えるでしょうか。

時間

2 本の制約がちょうど等号でぶつかる点は、可行領域の頂点候補になります。

2x +  y = 16
x  + 2y = 14

この連立方程式を解くと、両制約の交点が求まります。

2 本の制約がちょうど等号でぶつかる点は、可行領域の頂点候補になります。

Q1. 連立 2x + y = 16、x + 2y = 14 の解の x を入力してください。

Q2. 同じ連立の解の y を入力してください。