制約条件のある連立多元方程式の解法

連立多元１次方程式で制約条件がある場合にその近似解を求めたいのですが、どのように解けばよいのでしょうか？数値計算ソフト（Mathcad)では勝手に解いてくれるのですがそのアルゴリズムが知りたいのです。
例えば、未知数をx1,x2,x3、その他はある定数で、
a1・x1+b1・x2+c1・x3 = A
a2・x1+b2・x2+c2・x3 = B
a3・x1+b3・x2+c3・x3 = C
これに0<x1,x2,x3<1という制約条件があった場合などです。
よろしくお願いします。

No.1 回答者： sunasearch 回答日時： 2005/03/28 19:02

未知数と同じ数の式があると仮定すると、

まず方程式の解(x1=z1,x2=z2,x3=z3)を得ます。

制約条件を満たすもっとも近い解は、
距離の２乗＝
（z1-x1）^2 + (z2-x2)^2 + (z3-x2)^2を最小にする
x1,x2,x3を求める問題に帰着されます。

x1,x2,x3の間の関係式が存在しないのであれば、
それぞれの項を最小にする（z1,z2,z3に近い）x1,x2,x3を選べば求まると思います。

No.2 回答者： sunasearch 回答日時： 2005/03/28 19:09

#1です。

誤植がありましたので訂正します。

距離の２乗
＝（z1-x1)^2 + (z2-x2)^2 + (z3-x3)^2

実際の計算機レベルでは、
おそらく、参考URLのシンプレックス法の形に帰着した上で、
その高速解法が実装されているのではないでしょうか。

参考URL：http://www.kogures.com/hitoshi/webtext/lp-simplex/

この回答へのお礼

ご回答ありがとうございます。

早速シンプレックス法について見てみましたが、
まだ理解が浅いので実際の問題にどうやって使えばよいかまだピンと来ません。

なお、実際の問題をMathcadで行うと線形より非線形（準ニュートン）の方がいい値が出ています。これらの違いについても簡単に教えていただけると大変助かります。

お礼日時：2005/03/29 00:14

No.3 ベストアンサー 回答者： sunasearch 回答日時： 2005/03/29 01:07

＞早速シンプレックス法について見てみましたが、

まだ理解が浅いので実際の問題にどうやって使えばよいかまだピンと来ません。

線形計画問題の一般的な形
（目的関数と等式による制約条件）
に問題を変形して、後は機械的に解くだけです。

ネットで「シンプレックス法」で検索して、
いくつか例を見られると良いと思います。

＞なお、実際の問題をMathcadで行うと線形より非線形（準ニュートン）の方がいい値が出ています。これらの違いについても簡単に教えていただけると大変助かります。

上記のシンプレックス法は、最適解を求める方法です。しかし、次元が増加すると時間がかかるので高速解法においては準最適解を求めます。

非線形はもとから最適解を求めるのが困難なため、ニュートン法などにより準最適解を求めています。

Mathcadが実際に用いているアルゴリズムは存じてませんので、すみませんが何ともいえません。

参考URL：http://zeus.mech.kyushu-u.ac.jp/~tsuji/java_edu/ …

この回答へのお礼

道筋を教えていただき大変助かりました。
なんとなく解けそうな気がしてきました。

しばらくはこの辺を勉強して次の問題が出てきたら
また相談させてください。
ありがとうございました。

お礼日時：2005/03/29 09:25