線形計画法の問題の解き方を詳しく解説！例題つき

線形計画法は線形計画問題を解く方法のうちの一つです。

線形計画問題は大学入試問題でも度々出題されます。

この記事では、線形計画法についてまとめます。

【PR】勉強を効率的に継続して、志望校に合格したい方必見！

↓無料ダウンロードはこちら↓

 

１．線形計画法とは

線形計画法という言葉は、高校の数学の教科書に載っている単語ではありません。

高校の教科書でよく使われる単語としては「領域における最大・最小」などと言うのが一般的でしょう。
どちらにせよ、問題の解き方が変わるわけではありませんが、実際に問題を解く前に、線形計画法についてもう少し詳しく説明しておきましょう。

線形計画法は、線形計画問題を解くための手法です。
さらに、線形計画問題は最適化問題のうちの一つで、多くの分野に応用されています。

最適化問題をしっかり理解するためには大学の知識が必要ですから、詳しくは大学の「線形代数学」や「解析学」を学習してください。
特に情報学科に進もうという方は、最適化問題は避けて通れない分野です。

最適化問題とは、簡単に言えば、ある特定の条件の下で、関数の最大値や最小値について調べるような問題です。
そして線形計画問題とはその条件と関数が一次式で表されるものです。

つまり「一次不等式で表される領域内で、一次式の値を最大化（あるいは最小化）するような問題」を、線形計画問題と言います。

そして、線形計画問題を解く方法を線形計画法と言います。

 

２．線形計画法の難しさについて

高校で扱う線形計画問題は、概ね1パターンしかありません。

解いたことがあれば、問題なく解けるのですが、まったく未知なら苦労するかもしれません。
大学入試における線形計画問題の難しさは、分野がわかりづらいことです。

線形計画問題は（この名前で紹介されていませんが）多くの教科書に載っています。
「領域における最大・最小」の分野ですので、数学Ⅱの軌跡と領域で扱います。

しかし、入試で線形計画問題がふいに出題されると、受験生はどの分野の知識を使って解けばよいか戸惑うようです。

例えば、sinやcosが問題に含まれていれば、三角関数の公式などを使えばよい、あるいはlogなどが問題で使われていれば指数対数の計算をすればよいと思うはずです。

しかし線形計画問題の問題では、ただ不等式と一次式が与えられ、一次式の最大値（あるいは最小値）を求めよ、と言われるだけです。

そのときに、不等式を必死で計算したり、2次関数の最大値・最小値の知識を使っても、ほとんど無意味です。

ですから、線形計画法の難しさは「線形計画法の問題だと気づけないこと」です。

逆に言えば、「この問題は線形計画法で解ける」とわかってしまえば、あとは自然に答えが出てくるのです。

 

３．線形計画法の例題

前置きがずいぶん長くなりましたが、線形計画問題とは以下のような問題です。

 

解答・解説

高校範囲における線形計画法では、与えられた不等式を満たすような領域を図で表しましょう。

x≧0、y≧0、y≦-3x+9、y≦-1/3x+2 とすれば、領域の作図ができるでしょう。

この x≧0、y≧0、3x+y≦9、x+3y≦6 で表される領域をDとおきます 。

求めるのは x+y の最大値と最小値です。

このとき、x+y を線形計画法における目的関数といいます。
面倒なのは変数が x と y の2つあることです。

 

これを、領域内の点が動く問題だと考えましょう。

例えば、点A( 1, 1 ) はこの領域Dに含まれる点です。
このとき、x + y の値は 1 + 1 = 2 となります。

しかし、これが求める最大値ではありません。

なぜなら、点B( 2, 1 ) という、領域D内に含まれるような点で、x + y がより大きくなるような点が存在するからです。

しかし、点C( 2, 2 )のような点は、領域Dに含まれていませんので、x + y = 4 を満たすようなxとyの組が領域D内にあるかどうかはわかりません。

ここで、x + y = k とおくと、 k を最大にするような変数x と変数 y の組を探せばよいことになります。

ただし、変数x と変数 y は、領域D内に入っていなければなりません。

x+y=k ⇔ y=-x+k

とすれば、先の図に直線を書き込めるはずです。

このとき、kの値によって直線の位置が変わりますね。

例えば、y=-x+2 であれば、先の点A( 1, 1 )を通るような直線になっていて、領域Dと交わっています。

また、 y=-x+3 であれば、先の点B( 1, 2 )を通るような直線になっていて、これも領域Dと交わるような直線です。

では、点C( 2, 2 )を通るような直線、 y=-x+4 であればどうでしょうか。
図に書き込めばわかりますが、直線 y=-x+4 と領域Dには共有する点がないことがわかります。

これは、「x+y=4 になるような点は領域D内には存在しない」ことを表しています。

つまり、x+y の最大値は4より小さいのです。

 

このように考えると x + y の最大値は、

「 k の値を変えることで動く直線 y=-x+k が、領域Dと共有点を持つうちで、kが最大になるもの」

を求めればよいことがわかります。

直線 y=-x+k の傾きは‐1で、y=-3x+9 の傾きより大きく、y=-1/3x+2 の傾きより小さいです。

そのため、領域D内で直線　y=-x+k と交わるような点で、直線が一番y軸の正方向に大きくなるのは、直線 y=-3x+9 と直線 y=-1/3x+2 の交点Pを通るときであることが、図から読み取れます。

ですから、点P (21/8,9/8) においてちょうど直線y=-x+k  と交わります。

このときのkの値は 21/8+9/8=15/4 ですので、求める x+y の最大値は 15/4 (x=21/8,y=9/8) となります。

 

４．【線形計画法の応用】目的関数と領域の一次不等式

先の問題では x + y を最大にする点は、領域の端点でした。

線形計画法では、このように領域の端点において最大値あるいは最小値を取ることになります。

しかし、先の問題のように「直線 y==3x+9 と直線 y=-1/3x+2 の交点」のような点で最大値を取るとは限りません。

どこで最大値（あるいは最小値）を取るかは、その問題の領域を規定する一次不等式と、目的関数によります。

領域には先の問題をそのまま使いましょう。

例えば、目的関数が x+y ではなく、4x+y であれば以下のような解答になります。

 

解答・解説

目的関数を 4x+y=k とおくと、y=-4x+k となります。

この直線が領域Dと共有点を持つような最大のkを探せばよいことになります。

先のように点P (21/8,9/8) でkが最大値をとると思ってしまいそうになりますが、そうではありません。

点P (21/8,9/8) では、k=93/8 となります。

しかし、目的関数が 4x+y の場合には、k がより大きくなるような点があります。

それは、点Q( 3, 0 )です。

この違いは、目的関数の傾きと、領域の境界を定める一次方程式の傾きによります。

領域Dの境界線は、y=-3x+9 、y=-1/3x+2 ですから、傾きは －3と-1/3 です。

今回の目的関数は 4x+y ですので傾きは －4 であり、境界線の傾きよりも小さい値です。

そのため、もしも点P (21/8,9/8) を通るように直線y=-4x+93/8  を引いたとしても、よりy軸の正方向に領域Dと共有点を持ちながら、直線を移動させることができます。

どこまで移動できるかというと、直線y=-3x+9  とx軸の交点である点Q ( 3, 0 ) です。

そのため、目的関数 4x+y の最大値は、x=3,y=0  のときで 12 となります。

 

５．線形計画法のまとめ

最後までご覧くださってありがとうございました。

この記事では、線形計画法についてまとめました。

高校における線形計画法の問題は、この記事でご紹介したパターンしかありません。
教科書では数学Ⅱの軌跡と領域の「領域と最大・最小」などの単元で載っているはずです。

線形計画法は、大学で学ぶ最適化問題の一つで、目的関数及び領域の境界が直線であるようなものを指します。

領域と最大・最小の応用問題としては、領域や目的関数が直線でないような問題が出題されますが、基本的な解き方は変わりません。

既に申し上げたように、「領域と最大・最小の問題であると気づく」ことが一番のハードルでしょう。

 

この記事の執筆者

ニックネーム：受験のミカタ編集部

「受験のミカタ」は、難関大学在学中の大学生ライターが中心となり運営している「受験応援メディア」です。