理系男子の独り善がり

仕事や生活に役立ちそうな(実際に役立つかは別として)数学・物理ネタをつらつらと書いていこうと思ってます.

線形計画法~「なんとなく kと置いて」ませんか?~

高校数学だけでなく,IT系や経済関連の資格試験などでも出てくる線形計画法(LP; Linear Programming)についてです.
まずは,例題を挙げておきます.

例題

 x, \ yが 4つの不等式  x \geqq 0, \ y \geqq 0, \ x+4y \leqq 16, \ 3x+2y \leqq 18を満たすとき,

  1.  x+yの最大値を求めよ.
  2.  2x-3y+2の最大値を求めよ.
  3.  x^2+yの最大値を求めよ.

厳密に「線形」計画法と呼べる問題は 1.と 2.だけですが,3.も似たような考え方を使うので入れてみました.
といっても,これを解くことがメインではなく,考え方に触れていく内容になります.

線形計画法の問題の構造と解き方の流れ

問題の構造(というとちょっと大げさ?)を簡単に書いてみると,

Q-1. 実数 x, \ yがある範囲(領域)を動くという条件があり,
Q-2. その条件下で x, \ yにより与えられる関数  f(x, y)の最大または最小を求める.

こんな感じになります.そして,解き方としては

A-1. Q-1.の領域を図示し,
A-2. f(x, y)=kと置いた式で表されるグラフが Q-1.の領域と共有点を持つように変化させて, kの値の変化を調べる.

という流れになります.
例題の場合には,

  1.  x+y=k \ \Rightarrow \ y=-x+k
  2.  \displaystyle{ 2x-3y+2=k \ \Rightarrow \ y= \frac{2}{3}x + \frac{2-k}{3} } *1
  3.  x^2+y=k \ \Rightarrow \ y=-x^2+k

のそれぞれのグラフと不等式で与えられた領域との位置関係を考えることになります.
「グラフと領域が共有点をもつように kの値を変化させる.」と書きましたが,今回はそこを掘り下げてみようという魂胆なのです.

ポイントは「領域もグラフも点の集まりである」こと

1.の x+y=kを例にすると,この式は,
  x+yの値が kとなるような点の集まりを表している.

と捉えることができます.もうちょっと丁寧に次のように言い換えることができます.
 点 (x,y)が与えられたとき,その点から傾き:-1の直線を引き,
 y軸との交点(y切片)を求めると,その点の y座標の値は x+yの値になっている.

そして,
 点 (x,y)はある領域内しか動くことができない.という制約がついています.

というのが線形計画法の本質ではないかと思っています.先に書いた「共有点をもつようにグラフを動かす」とは,ある意味逆の流れになっているのではと思います.
解法(上で書いた A-1と A-2)では,グラフという線と領域という面でしか考えてないイメージになります.それによって,点  (x,y)に対して値が与えられるという感覚が消えてしまっている.これがタイトルに書いた「なんとなく  kと置いて」となってしまう原因なのかなと思っています.まあ,解ければ OK!って話ではあるんですけどね.

整理すると,

  • 与えられた式の値が kとなるような点の集まりを考えると,
  • kは,その式で与えられるグラフの特徴的な値(y切片など)として現れる.
  • そして,点 (x,y)を決められた領域内で動かすことで,kの最大や最小が求まる.

ということです.
2.では y切片が  \displaystyle{ \frac{2-k}{3} }となり,直接 kを与えるものとはなりません.しかも, kが最大のとき,y切片の座標は最小になります.上のように,y切片が「特徴的な点」であると認識できていれば,そんなに違和感を持つこともなく,問題を処理できるのではと思います.

以前,1次変換の話の中でも書いていますが*2,直線や曲線の式やさらには領域についても「式や条件を満たす点の集まり」と考えなさいということです.この節の見出しは,このことを表したものになっています.

上の例題では  kの値を変えると,いずれも y軸方向への平行移動になっています.
f:id:miwotukusi:20170709225452p:plain

問題によっては,領域の方が円や楕円のような曲線で囲まれたものになっていることもあります.そのような場合は,接線の傾きを考えることもあります.

最後に

例題の答えだけ記しておきます.

  1.  7 \ (x=4, y=3)
  2.  14 \ (x=6, y=0)
  3.  36 \ (x=6, y=0)

*1:定数項である 2は一度無視して, 2x-3y = kで考えるという手もあり.

*2:ここの「1.1次変換が変換してるものは?」の箇所miwotukusi.hatenablog.jp