なんとなく答えてみる

http://el.jibun.atmarkit.co.jp/g1sys/2009/10/post-a55b.html
上記トピックのコメント欄に投稿した解き方で実際解いてみる。

以下の問題を3通りの方法で解きなさい。
かず子さんは、1本40円と1本60円のえん筆をあわせて30本買って、
1440円はらったそうです。40円と60円のえん筆をそれぞれ何本買ったのでしょう。

連立方程式

$\left{\begin{array}{rlcrlcr}&x&+&&y&=&30\\ 40&x&+&60&y&=&1440\\ \end{array}\right.$

ガウスの消去法

行列にして
$\left[\begin{array}{rr|r}1&1&30\\ 40&60&1440\\ \end{array}\right]$
前進消去して
$\left[\begin{array}{rr|r}1&1&30\\ 0&20&240\\ \end{array}\right]$
後退代入していく
$\left[\begin{array}{rr|r}1&1&30\\ 0&1&12\\ \end{array}\right]$
$\left[\begin{array}{rr|r}1&0&18\\ 0&1&12\\ \end{array}\right]$
解けた。

ガウス･ザイデル法

$\left[\begin{array}{rr|r}1&1&30\\ 40&60&1440\\ \end{array}\right]$
において $x^{(k)}$ をk回目の試行におけるxとすると
$x^{(k+1)}=\frac{30-y^{(k)}}{1}$
$y^{(k+1)}=\frac{1440-40x^{(k+1)}}{60}$
となるので初期値を適当にゼロにしてやると
$x^{(1)}=30$
$y^{(1)}=\frac{1440-1200}{60}=4$
$x^{(2)}=30-4=26$
$y^{(2)}=\frac{1440-1040}{60}=\frac{20}{3}$
$x^{(3)}=30-\frac{20}{3}=\frac{70}{3}$
$y^{(3)}=\frac{1440-\frac{280}{3}}{60}=\frac{202}{9}$
$x^{(4)}=30-\frac{202}{9}=\frac{68}{9}$
$y^{(4)}=\frac{1440-\frac{2720}{9}}{60}=\frac{512}{27}$
書くのが面倒になってきたのでだいぶ飛ばして
$x^{(9)}=\frac{40390}{2187}=18.46822130772748$
$y^{(9)}=\frac{76684}{6561}=11.68785246151501$
$x^{(10)}=\frac{120146}{6561}=18.31214753848499$
$y^{(10)}=\frac{232100}{19683}=11.79190164101001$
と収束してくるので
$x^{(\infty)}=18$
$y^{(\infty)}=12$
であると予想できる。

線形計画法

$x_1$ と $x_2$ をそれぞれ40円と60円の鉛筆の本数にして目的関数Zを
$Z=x_2$
とし、制約条件を
$\left{\begin{array}{l}x_1+x_2=30\\ 40x_1+60x_2\le1440 \\x_1\ge0\\x_2\ge0\\\end{array}\right.$
とする。

シンプレックスタブロー

まず問題を線形計画問題の標準形にする。
$Z-x_2=0$
$x_1+x_2+=30$
$40x_1+60x_2+x_3=1440$
よってシンプレックスタブローは

$x_1$	$x_2$	$x_3$	定数
0	-1	0	0	0
1	1	0	30
40	60	1	1440

となる。
目的関数の列において最小の要素はを含む列として $x_2$ であるので、この列の要素でそれぞれの行の定数項を割ったものの中で最小となるのは60の要素の列である。よってその要素をピボットとして掃き出しを行うと

$x_1$	$x_2$	$x_3$	定数
2/3	0	1/60	24
1/3	0	0	6
2/3	1	1/60	24

よって $x_1=18$ と決まるのであとは制約式に代入して解が求まる。

図形的解法

制約条件より $x_2=30-x_1$ の線上かつ $x_2=24-\frac{2}{3}x_1$ の下側。グラフを書いてみると一点で交わる。よって評価点はグラフの交点と $x_1=30$ の点。目的関数が $x_2$ なので最適解は交点。

探索問題

ルートノードが何も買っていない状態で常に右側のノードが40円の鉛筆を左側のノードが60円の鉛筆を買った状態となる2分木を考える。
右に進んだ場合はR、左に進んだ場合はLとして探索ルートを表す。続けて同じ文字が続く場合は数字を用いて省略する。続けてその場所での値段を示す。
e.g.)(LLR:160),(LLRL:220),(LLRL3R:380)
探索目標はルートから距離30で1440円のノード。

深さ優先探索

(L:60),(LL:120),(LLL:180),(L4:240),(L5:300),(L6:360),(L7:420),省略,(L24:1440),(L25:1500)
(L23R:1420)(L23RL:1480)
(L23RR:1460)
(L22R:1360),(L22RL:1420)(L22RLL:1480)
(L22RLR:1460)
(L22RRR:1440)
省略
(L12R17L:1460)
(L12R18:1440)探索成功。

幅優先探索

(L:60),(R:40),(LL:120),(LR:100),(RL:100),(RR:80),省略