直線と交点

平面上の直線がいくつか与えられた時、それらの交点をすべて求めるプログラムを作成します。

例として、次の４つの直線を考えます。 \[ x+y=4,\quad 3x+y=6,\quad x-y=2, \quad 2x-y=-1 \]

これらを図示すると、つぎのようになり、交点が４つ生じます。

プログラムは次のように書けます。

GetPoints(eqlist):=block([result:[]],
    for i:1 thru length(eqlist) do(
        for k:i+1 thru length(eqlist) do(
            result: endcons(solve([ eqlist[i],eqlist[k] ])[1], result)
        )    
    ),
    unique(result)
)$
GetPoints([x+y=4,3*x+y=6,x-y=2,2*x-y=-1]);

実行結果.

[[y=-5,x=-3],[y=0,x=2],[y=1,x=3],[y=3,x=1]]

線形計画問題では、これらの交点での関数fの値を知りたいということがありますが、 このようなときは、関数に指定した値を代入した値を計算する「subst」を用いることができます。

LP(f,clist):=block([result:[]],
    for i:1 thru length(clist) do(
        for k:i+1 thru length(clist) do(
            result: endcons(solve([ clist[i],clist[k] ])[1], result)
        )    
    ),
    result:unique(result),
    result:append([result],[map(lambda([w],subst(w,f)),result)])
)$
LP(2*x+y,[x+y=4,3*x+y=6,x-y=2,2*x-y=-1]);

実行結果.

[[[y=-5,x=-3],[y=0,x=2],[y=1,x=3],[y=3,x=1]],[-11,4,7,5]]

実行結果で得られたリストの、後半の要素[-11,4,7,5]が、各点における $f(x,y)=2x+y$ の値となっています。

substの使用法

関数 $f(x,y)=x+y$ に $x=1,y=2$ を代入するときは、次のようになります。

subst([x=1,y=2],x+y);

実行結果.

3