基本情報の線形計画法を制約式と頂点の例題で理解する

基本情報の線形計画法は、文章から「何を決めるか」「何を最大にするか」「どこまで使えるか」を分けると解きやすくなります。生産量を変数に置き、利益を目的関数、材料や時間の上限を制約式にします。2変数なら、条件を満たす領域の頂点で利益を比べるのが基本です。

この記事では、2種類の製品を作るオリジナル例題を、定式化から最適生産量の決定まで一続きで解きます。不等号の向き、非負条件、軸上の頂点まで確かめるので、式は選べても最後の計算で迷う方にも役立つ内容です。

基本情報の線形計画法を式にする

線形計画法で決めるのは制約内で最もよい組合せ

線形計画法は、一次式で表した条件のもとで、一次式の目的関数を最大化または最小化する方法です。限られた設備時間で利益を最大にする生産量、必要量を満たしながら費用を最小にする調達量などを考えます。LPはLinear Programmingの略称です。

ここで大切なのは、「何となくよさそうな案」ではなく、条件を全部守った案の中で最もよいものを選ぶことです。利益が高くても必要な設備時間が足りなければ採用できません。先に使える範囲を決め、その範囲の中で比較する、と考えると整理できます。

問題を数式へ置き換える作業を定式化といいます。定式化には、決めたい数量である変数、評価したい利益などの目的関数、守るべき制約条件が必要です。生産量の問題では、負の数量を認めない非負条件も忘れずに加えます。

基本情報の学習でも、用語だけでなく式にする過程を押さえたいところです。IPAの基本情報技術者試験シラバスVer.9.2は、線形計画法について基本的な手法、問題の定式化、事例などの理解を挙げています。

変数には何をどれだけ作るかを置く

次の工場を考えます。製品Aと製品Bはkg単位で生産し、量は小数でも調整できるものとします。どちらも設備Pと設備Qで処理します。1kg当たりの必要時間と利益、1日に利用できる設備時間は次のとおりです。これは解き方を確認するための架空の例題です。

項目	製品Aを1kg	製品Bを1kg	1日の利用上限
設備Pの処理時間	2時間	1時間	18時間
設備Qの処理時間	1時間	2時間	15時間
販売利益	400円	500円	最大にしたい

生産した分はすべて販売でき、表以外の材料不足や販売数量の上限はないものとします。設備時間は生産量に比例し、途中で段取り替えの固定時間などは発生しない前提です。現実の工場を細部まで再現するのではなく、この条件の中で最適な組合せを求めます。

問われているのはそれぞれの生産量なので、xを製品Aの生産量［kg］、yを製品Bの生産量［kg］と置きます。xとyは利益でも設備時間でもありません。たとえばx=3、y=2は「Aを3kg、Bを2kg作る」という意味です。

先に変数の意味を書くと、表を読む方向が固定できます。Aの列にある係数をxへ、Bの列にある係数をyへ掛けます。途中でxとyを入れ替えると、連立方程式の計算が合っていても、最後に答える製品の数量が逆になります。

目的関数は1単位の利益と生産量を掛けて足す

Aをxkg作る利益は400x円、Bをykg作る利益は500y円です。合計利益をZと置けば、Z=400x+500yを最大化します。「最大化」は式の一部というより、この式の値をどうしたいのかを表す指示です。

式を作るときは、利益の行を横に読みます。設備Pの2時間や設備Qの15時間は、この目的関数の係数には入りません。目的関数は案のよしあしを比べる物差しで、設備時間は案を実行できるかどうかを判定する物差しだからです。

Bのほうが1kg当たりの利益は高くても、Bだけを作るのが最適とは限りません。Bは設備Qを多く使うためです。設備PとQの使い方が製品ごとに違うので、両方を組み合わせたほうが、残っている時間を活用できることがあります。

単位も確認してみましょう。400［円/kg］×x［kg］は円になり、500yも円です。同じ単位の量を足した結果が合計利益になります。目的関数へ400x+2yと書いた場合は、利益と時間を混ぜており、意味の通る合計になりません。

制約式は資源ごとに使用量を足す

設備Pでは、Aを1kg作るのに2時間、Bを1kg作るのに1時間必要です。Aをxkg、Bをykg作る合計使用時間は2x+y時間になります。使えるのは18時間までなので、制約式は2x+y≤18です。

同様に設備Qは、Aにx時間、Bに2y時間を使います。利用上限15時間を超えられないので、x+2y≤15となります。表の列を製品ごとに足すのではなく、行を資源ごとに読んで、同じ設備を使う時間を足すのがコツです。

たとえばAを3kg、Bを2kg作る案なら、Pは2×3+2=8時間、Qは3+2×2=7時間です。両方とも上限以下なので実行できます。一方、Aを9kg、Bを1kg作る案は、Pに19時間必要となり、Qに余裕があっても実行できません。

制約は一つでも破れば不適合です。複数の式のどれかを満たせばよいのではなく、全部の制約を同時に満たす必要があります。設備ごとに合否を付けると、この違いを見失いにくくなります。

また、上限は「使い切る量」ではありません。Pを8時間だけ使う案も許されるので、最初から2x+y=18とは書きません。等号に置き換えるのは、あとでグラフの境界線や交点を調べる場面です。条件そのものの不等号は残しておきます。

非負条件と単位まで書いて定式化を完成させる

生産量は負にできないので、x≥0、y≥0を加えます。これが非負条件です。「正の数」とは違い、0も含みます。Aを作らずBだけ作る案も比較対象にできるため、理由がなければx>0、y>0に狭めないようにします。

役割	この例題の式	文章へ戻した意味
目的関数	Z=400x+500yを最大化	合計利益を最大にする
設備Pの制約	2x+y≤18	Pの使用時間は18時間以下
設備Qの制約	x+2y≤15	Qの使用時間は15時間以下
非負条件	x≥0、y≥0	各製品の生産量は0kg以上

これで定式化は完成です。制約式の左辺も右辺も時間、目的関数の値は円、変数はkgになっています。もし問題の上限が分で示されていれば、必要時間か上限を換算して単位をそろえます。数字だけを見て式を作ると、この換算を落としやすいですね。

ここでいう「線形」は、xやyの一次式で表せるということです。2x+yは線形ですが、xyやxの2乗を含む式は、そのままでは線形計画の式になりません。製造量が倍なら必要時間も倍になる、という比例関係をこの例題では前提にしています。

数量と単位の対応が苦手なら、基本情報の計算問題を式と単位から整理する学習法も参考になります。本記事では、その整理を線形計画の定式化と最適化へ具体的に当てはめていきます。

以下と以上の不等号を文章へ戻して確認する

今回の設備時間は「上限」「まで」「以下」なので≤です。一方、「Bを最低2kg作る」という条件が追加されたらy≥2になります。「合計で少なくとも10kg納品する」ならx+y≥10です。同じ生産問題でも、すべての不等号が同じ向きになるとは限りません。

「必ず合計10kgにする」と指定された場合はx+y=10です。このように、資源の上限、最低限の需要、数量の指定では式の意味が違います。「生産計画だから≤」と暗記せず、式を一度日本語へ読み戻して、問題文の条件と一致するか確認しましょう。

負の数で両辺を割る変形では、不等号の向きが逆になる点にも注意が必要です。たとえば−y≤−2はy≥2です。原式を残しておけば、変形後に向きが不安になったとき、具体的な数値を元の式へ代入して確かめられます。

基本情報の線形計画法を例題で解く

不等式から実行可能領域を決める

ここからは、先ほどの例題を最後まで解きます。横軸をx、縦軸をyに取り、x≥0、y≥0なので第1象限と軸上だけを考えます。そこからPとQの条件をどちらも満たす部分を残します。この共通部分を実行可能領域と呼びます。

まずPの境界線2x+y=18を描くには、y=0としてx=9、x=0としてy=18を求めます。点（9,0）と（0,18）を結ぶ直線です。Qの境界線x+2y=15は、同様に（15,0）と（0,7.5）を通ります。境界を描くときだけ不等号を等号へ置き換えます。

境界線	x軸との交点	y軸との交点	条件を満たす側
2x+y=18	（9,0）	（0,18）	原点を含む側
x+2y=15	（15,0）	（0,7.5）	原点を含む側

どちら側を残すか迷ったら、境界線上にない点を一つ代入します。今回は原点（0,0）で、0≤18、0≤15がどちらも成立します。そのため両方とも原点側です。原点が境界線上にある問題では、別の点を選んで同じように判定します。

≤や≥には等号も含まれるため、今回の境界線上も実行可能領域に入ります。2本の直線、x軸、y軸で囲まれた部分のうち、両方の設備時間を守る側が残ります。片方の直線だけで塗った領域の全体を、そのまま答えに使わないようにしましょう。

境界線の交点と軸上の頂点をそろえる

実行可能領域の角に当たる点を頂点といいます。2本の設備の境界線だけでなく、非負条件の境界であるx軸とy軸も確認します。まず2x+y=18とx+2y=15を連立して、斜めの境界線同士の交点を求めましょう。

x軸上ではy=0なので、Pの条件からx≤9、Qの条件からx≤15です。同時に守れるのは厳しいほうのx≤9となります。したがって頂点は（9,0）であり、Qの切片（15,0）は領域の外です。

y軸上でも同様です。x=0ならPからy≤18、Qからy≤7.5なので、頂点は（0,7.5）になります。Pの切片（0,18）はQの条件を破ります。切片を求めただけでは頂点候補の確認は終わらず、残りの制約へ照合する必要があります。

今回そろえる頂点は、領域の周囲をたどる順に（0,0）、（9,0）、（7,4）、（0,7.5）の4点です。原点を落とさず書いておくと、最小化の問題などへ進んだときも同じ手順を使えます。頂点に限らず、候補を採用する前には全条件を確認しましょう。

各頂点の利益を比較して最適生産量を出す

この例題のように実行可能領域が空でなく、境界を含む有限の多角形になる場合、線形の目的関数の最大値は少なくとも一つの頂点で得られます。そこで、4点の座標をZ=400x+500yへ順に代入して比較します。

頂点（x,y）	利益の計算	合計利益
（0,0）	400×0+500×0	0円
（9,0）	400×9+500×0	3,600円
（7,4）	400×7+500×4	4,800円
（0,7.5）	400×0+500×7.5	3,750円

最大は4,800円なので、製品Aを7kg、製品Bを4kg生産するのが最適です。（7,4）が最適解、4,800円が目的関数の最適値です。問われているのが生産量なのか最大利益なのかで、解答すべきものが違います。数量だけ、金額だけで終わらないように読み直します。

答えの検算では、Pが2×7+4=18時間、Qが7+2×4=15時間で、上限を超えないことを確認します。さらに利益はAが2,800円、Bが2,000円なので合計4,800円です。式を解く計算と、元の条件に戻す確認を分けるとミスに気づきやすくなります。

式だけで上限を確かめる方法もあります。目的関数は400x+500y=100（2x+y）+200（x+2y）と分けられます。制約から100×18+200×15=4,800円以下であり、（7,4）はこの上限に達します。頂点の代入結果が最大だと、別の計算でも確認できます。

頂点を比べる理由を図で考えるなら、400x+500y=一定の利益となる直線を思い浮かべます。利益を大きくする方向へ平行移動すると、領域に触れられる最後の位置に最適解があります。北陸先端科学技術大学院大学の線形計画法講義資料でも、実行可能領域と頂点から解を探す考え方を確認できます。

交点だけや単価だけで選ぶと間違う理由

今回たまたま2本の設備条件の交点が最適でしたが、交点を求めた時点ではまだ結論ではありません。同じ設備時間のまま、利益だけAが700円/kg、Bが200円/kgへ変わったとします。領域は変わらず、比べる物差しだけがZ=700x+200yへ変わります。

このとき（9,0）の利益は6,300円、（7,4）は5,700円、（0,7.5）は1,500円です。最適なのはAだけを9kg作る案になります。設備Qには6時間余りますが、設備Pが上限なので、Bを追加する余裕はありません。資源を全部使い切る案が常に最適というわけではないのです。

逆に、元の利益ではBの単価が高いという理由だけでBのみを作ると、3,750円にとどまりました。単価だけでなく、設備の消費量と生産可能な数量が利益を左右します。実行できる頂点をそろえて、問題文の目的関数で比較するところまでが一組です。

選択肢から案を選ぶ形式でも、まず各案を制約式へ代入します。条件違反の案を除いたあとで利益を比べると、実行不可能な高利益案に引っ張られにくくなります。ただし、選択肢だけの比較が最適性の証明になるのは、問題がその形式で答えを選ばせている場合です。

練習問題でも定式化から頂点比較までつなげる

今度は製品Cをxkg、製品Dをykg作るとします。1kg当たり、どちらも原料を1kg使い、原料は合計12kgまでです。加工時間はCが2時間、Dが1時間で、合計18時間まで。利益はCが300円/kg、Dが200円/kgで、小数の生産量も認めます。最適な生産量と最大利益を求めてみましょう。

変数の意味は指定済みなので、目的関数はZ=300x+200yの最大化です。原料の制約はx+y≤12、加工時間の制約は2x+y≤18、非負条件はx≥0、y≥0です。「原料」「時間」「利益」をそれぞれ一行ずつに対応させます。

2本の境界線x+y=12と2x+y=18を引き算するとx=6、したがってy=6です。x軸上ではx≤12とx≤9から（9,0）、y軸上ではy≤12とy≤18から（0,12）が頂点になります。原点も加えた4点で利益を比べます。

頂点	合計利益	確認
（0,0）	0円	生産しない案
（9,0）	2,700円	Cだけを生産
（6,6）	3,000円	原料12kg、時間18時間
（0,12）	2,400円	Dだけを生産

答えはCを6kg、Dを6kg、最大利益3,000円です。計算を見ずに解けなかった場合は、「式が作れなかった」「軸上の上限を選び間違えた」「利益への代入を間違えた」のどこで止まったかを分けましょう。次に練習する箇所が具体的になります。

整数条件と最適解が一つでない場合に注意する

ここまでの例題はkg単位の連続量でした。個数や人数を整数で扱う指定がある場合は、その条件も必要です。連続量として求めた最適解が小数だからといって、各成分を四捨五入して終わりにはできません。丸めた結果が制約を破ったり、別の整数の組合せのほうがよかったりします。

たとえばx≥0、y≥0、2x+y≤5、x+2y≤5でx+yを最大にすると、連続量の最適解は（5/3,5/3）です。両方を2へ丸めた（2,2）は6≤5となって不適合です。両方を1へ切り捨てると合計2ですが、整数の（2,1）なら両条件を守って合計3にできます。整数条件の有無を先に確認する理由が分かりますね。

また、最適解が一つとは限りません。元の設備条件で目的関数をZ=x+2yに変えると、Qの上限からZ≤15です。（7,4）と（0,7.5）はともに15となり、この2点を結ぶ辺上の点も同じ値になります。最適な頂点を見つけても、それ以外に最適解がないとまでは言えません。

最適値そのものが存在しない場合もあります。x≥2とx≤1を同時に要求されれば実行可能な案がありません。一方、x≥0しか条件がなくxを最大にする問題は、いくらでも増やせるため有限の最大値を持ちません。「解なし」と「上限なし」は意味が異なります。

こうした理論の背景は、福知山公立大学・前田一貴氏の講義用テキスト『線形計画法』の実行可能解・基本定理・最適解が存在しない場合の説明で確認できます。この記事の生産例題と数値は、手順を練習するために独自に設定しています。

変数が増えた問題では、平面に図を描いて全頂点を数える方法は扱いにくくなります。代表的な解法にシンプレックス法があり、頂点に対応する解を更新して目的関数を改善していきます。まずは2変数で「条件を守る案」と「その中で最もよい案」の違いを理解してから、用語をつなげると学びやすくなります。

基本情報の線形計画法のまとめ

基本情報の線形計画法では、まず決めたい生産量を変数へ置き、利益の行から目的関数、資源ごとの行から制約式を作ります。最後に非負条件と単位を確かめれば、文章の条件を数式へ整理できます。上限を使い切ると決めつけず、不等号の意味を残すことが大切です。

• 変数の意味と単位を最初に書く
• 目的関数とすべての制約式、非負条件をそろえる
• 実行可能領域の交点と軸上の頂点を確認する
• 各頂点の目的関数値を比べ、元の条件へ戻して検算する

主例題の結論は、Aを7kg、Bを4kg作ると、設備Pを18時間、Qを15時間使い、利益が最大4,800円になるというものでした。交点だけ、単価だけで決めず、実行できる候補の比較まで進める。この手順を、数値を変えた問題でも再現できるように練習してみてください。

解説を読んだら、基本情報の過去問アプリで無料演習に進み、答えだけでなく選んだ理由も確かめてみてください。