逆像法　第２講【座標変換への応用】【線形計画法の考え方の素】

(1) について

\((x \ , \ y)\) という座標から \((x+y \ , \ xy)\) という座標への変換を考える問題です。

1954年に東大が出題したのが元祖で、通称「エンマさまの唇問題」と呼ばれているそうです。

例えば \((s \ , \ t)\) は \((1 \ , \ 0)\) になれる？

例えば

\((s \ , \ t)\) は \((1 \ , \ 0)\) になれる？

ということについて検証したければ

\(x^{2}+y^{2} \leq 1\) を満たしつつ、\(\begin{eqnarray}
\left\{
\begin{array}{l}
x + y = 1 \\
xy= 0
\end{array}
\right.
\end{eqnarray}\)  になれるかどうかを検証すればよいわけです。

これについては解と係数の関係から \(x\) ,  \(y\) は２次方程式

\(X^{2}-X=0\)

の解であるため、\((x \ , \ y)=(1 \ , \ 0) \ , \ (0 \ , \ 1)\) が得られ、これらは \(x^{2}+y^{2} \leq 1\) も満たしています。

つまり、

\((s \ , \ t)\) は \((1 \ , \ 0)\) になれる

と言えます。

\((s \ , \ t)\) は \((1 \ , \ 2)\) になれる？

考え方自体は先ほど同様です。

\(x^{2}+y^{2} \leq 1\) を満たしつつ、\(\begin{eqnarray}
\left\{
\begin{array}{l}
x + y = 1 \\
xy= 2
\end{array}
\right.
\end{eqnarray}\)  になれるかどうかを検証すればよいわけです。

解と係数の関係から \(x\) , \(y\) は

\(X^{2}-X+2=0\)

の解であり、これを解くと \(X=\displaystyle \frac{1\pm\sqrt{7}i}{2}\)と、実数として \(x\) , \(y\) が存在しないことになります。

つまり、\((s \ , \ t)\) は \((1 \ , \ 2)\) になれないと言えますね。

\((s \ , \ t)\) は \((1 \ , \ -2)\) になれる？

途中議論で出てくる解と係数の関係で現れる２次方程式が実数解をもてばよいことだけを考えるわけにもいきません。

例えば

\((s \ , \ t)\) は \((1 \ , \ -2)\) になれる？

について検証します。

\(x^{2}+y^{2} \leq 1\) を満たしつつ、\(\begin{eqnarray}
\left\{
\begin{array}{l}
x + y = 1 \\
xy=-2
\end{array}
\right.
\end{eqnarray}\)  になれるかどうかを見ます。

解と係数の関係から \(x\) ,  \(y\) は２次方程式

\(X^{2}-X-2=0\)

の解であるため、\((x \ , \ y)=(2 \ , \ -1) \ , \ (-1 \ , \ 2)\) と実数として得られることになります。

しかし、肝心の \(x^{2}+y^{2} \leq 1\) を満たしていません。

しらみつぶそう

\((s \ , \ t)\) が

\((1 \ , \ 0)\) になれる？

\((2 \ , \ 3)\) になれる？

\((-1 \ , \ \displaystyle \frac{1}{3})\) になれる？

\(\vdots\)

と、しらみつぶしできれば、「なれる」点たちの集合である題意の領域が得られます。

そこで、

と文字の力を借りてしらみつぶします。

少しレベルアップ

\((s \ , \ t)\) は \((u \ , \ v)\) になれる？

と、しらみつぶすわけですが、別に文字は \(u\) ,  \(v\)  でなくてもかまいません。

\((a \ , \ b)\) になれる？

\((\alpha \ , \ \beta)\) になれる？

でも構わないわけです。

なので、【解答】では \((s \ , \ t)\) のままで考えてあります。

自学自習する際に疑問に思いやすい部分だと思います。

(2)について

与えられた \(xy+m(x+y)\) は \(ms+t\) と表せます。

よって  \((s \ , \ t)\) が (1) で得た領域内を動くときの \(ms+t\) の最大値と最小値を求めればよいことになります。

\(ms+t=1\) になれる？

例えば \(ms+t=1\) になれるかどうかを検証したければ、

\(ms+t=1\) を満たす \((s \ , \ t)\) 集まれ

と呼びかけます。

この呼びかけに対して集まってくる \((s \ , \ t)\) は \(t=-ms+1\) という直線です。

一方 \((s \ , \ t)\) は (1) の領域内にいないといけません。

つまり、この直線と (1) の領域が共有点をもっているかどうかが \(ms+t=1\) になれるかどうかに直結します。

しらみつぶそう

\(ms+t=1\) になれる？

\(ms+t=2\) になれる？

\(ms+t=3\) になれる？

\(\vdots\)

という気持ちで

としらみつぶそうという気持ちで考えましょう。

線形計画法の考え方は逆像法が息づいている

恐らく線形計画法を

「\(=k\) とおいてバーっとズラしていくやつ」

とぶっきらぼうに覚えていたかもしれませんが、こうしてみると線形計画法には逆像法の考え方が息づいているのが分かると思います。

言ってみれば

\(=1\) になるかな？　\(=2\) になるかな？　\(\cdots\)

というしらみつぶしの考え方を「視覚的」に考えているのが線形計画法と言えましょう。

解答はコチラ