ax-by=c

ax+by=c(x≧0,y≧0)を満たすxの最小値とyの最小値を求める方法ってありますか？
しかも、C言語を使って計算したいので、出来る限り効率の良い計算方法が知りたいです。が、とりあえずC言語のことは抜きにして、どんな方法でも良いので数学に自身のある方ぜひご教授願います！！
(__)

No.6 回答者： stomachman 回答日時： 2002/04/20 17:26

（条件１）ax+by=c

（条件２）x≧0かつy≧0
において、（条件１）と（条件２）を共に満たすような<x,y>の集合のうちで
・xが最小であるような<x,y>のxの値 minx
・yが最小であるような<x,y>のyの値 miny
を求めたい、という問題と読みました。

　言い換えれば、x,y平面にax+by=cのグラフを描いて、その第一象限の部分（つまり条件２を満たす部分）だけを見たとき、
・xが最小であるような点においてそのときのxは幾らか。
・yが最小であるような点においてそのときのyは幾らか。
（無論、「xが最小であるような点」と「yが最小であるような点」とは必ずしも一致しません。）という問題です。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
[1] a=0, b=0の場合
　（条件１）は 0=c と書き直せます。
　[1-1] c=0の場合
　　x,yとして任意の実数を持ってくると（条件１）は満たされます。
　　だから（条件２）だけ考慮すればよく、minx = 0, miny = 0 です。
　[1-2] c≠0の場合
　　x,yとしてどんな実数を持ってきても（条件１）は満たせません。従って
　　minx, minyは存在しません。
[2] a≠0, b=0の場合
　（条件１）は ax=c と書き直せます。だから x=c/a が（条件１）を満たす唯一のxです。
　そして、yは何であっても良い。
　[2-1] c=0、またはaとcが同符号の場合（ac≧0と言っても同じ）
　　minx = c/a, miny=0です。
　[2-2] c≠0かつ、aとcが異符号の場合（ac＜0と言っても同じ）
　　minx,minyは存在しません。
[3] a=0, b≠0の場合
　[3-1] c=0、またはbとcが同符号の場合（bc≧0と言っても同じ）
　　minx = 0, miny=c/bです。
　[3-2] c≠0かつ、bとcが異符号の場合（bc＜0と言っても同じ）
　　minx,minyは存在しません。
[4] a≠0, b≠0の場合
　[4-1] c=0の場合
　　直線ax+by=cは必ず<0,0>を通るから、
　　minx=0, miny=0
　[4-2] c≠0の場合
　　直線ax+by=cとx軸との交点は<c/a,0>、
　　直線ax+by=cとy軸との交点は<0,c/b>です。
　　[4-2-1] aとbが同符号の場合（ab＞0と言っても同じ）
　　　c/aとc/bは同符号です。
　　　[4-2-1-1] aとcが同符号の場合（ac＞0と言っても同じ）
　　　　<minx,c/b>= <0,c/b>、<c/a,miny> = <c/a,0>
　　　　です。つまり、
　　　　minx=0, miny=0
　　　[4-2-1-2] aとcが異符号の場合（ac＜0と言っても同じ）
　　　　　直線ax+by=cは第一象限を通らない。だから、
　　　　　minx,minyは存在しません。
　　[4-2-2] aとbが異符号の場合（ab＜0と言っても同じ）
　　　<c/a,0>か<0,c/b>、このどちらかが<minx,miny>と等しい。
　　　そしてc/aとc/bはどちらかが正、どちらかが負です。従って、
　　　[4-2-2-1] aとcが同符号なら（ac＞0と言っても同じ）
　　　　c/a ＞ 0 だから minx = c/a, miny = 0
　　　[4-2-2-2] aとcが異符号なら（ac＜0と言っても同じ）
　　　　minx = 0, miny = c/b

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
さて、これを整理しなおしてみましょう。記号で表して
(××) とは「minx,minyは存在しない」のこと
(００) とは「minx=0, miny=0」のこと
(０▼) とは「minx=0, miny=c/b」のこと
(▲０) とは「minx=c/a, miny=0」のこと
としてみると、

c＞0
　b＞0：　a＞0…(００)、a＝0…(０▼)、a＜0…(０▼)
　b＝0：　a＞0…(▲０)、a＝0…(××)、a＜0…(××)
　b＜0：　a＞0…(▲０)、a＝0…(××)、a＜0…(××)
c＝0…(００)
　b＞0：　a＞0…(００)、a＝0…(００)、a＜0…(００)
　b＝0：　a＞0…(００)、a＝0…(００)、a＜0…(００)
　b＜0：　a＞0…(００)、a＝0…(００)、a＜0…(００)
c＜0
　b＞0：　a＞0…(××)、a＝0…(××)、a＜0…(▲０)
　b＝0：　a＞0…(××)、a＝0…(××)、a＜0…(▲０)
　b＜0：　a＞0…(０▼)、a＝0…(０▼)、a＜0…(００)
となります。

「効率が良い」というのを処理速度のことだとするなら、下手な条件分岐は却って処理速度を落とします。

　これをこのまま３次元配列にしておくのがひとつの方法でしょう。つまりたとえば、
a,b,cについて、負のときに0、０のときは1、正のときは2となる番号を付け、
また、(××) を0, (００)を1, (０▼) を2, (▲０)を3で表すことにする。そういう配列dをstaticとして作っておく。ですから、 d[0][1][2] は c＜0, b=0, a＞0 の場合を表すので、その値は3（(▲０)を表す）です。
　で、a,b,cが与えられたとき、それぞれの符号を符号関数で取り出して、
負のときは0
０のときは1
正のときは2
となるインデックスia, ib, icを作ります。この３つのインデックスを使って配列dを引く（つまりd[ic][ib][ia]を参照する）と、どんな処理をすべきかの番号(0～3)が取り出せますから、それに従ってswitchすれば良い。

この回答へのお礼

To:ご回答くださった皆様

4ヶ月半もの間、お礼の一つもしなかったとこを深くお詫び申し上げます。
そして、大変詳細な回答、心より感謝いたします。
ありがとうございました。

しかしながら・・・未だ問題解決には至っておりません。
ですがこのまま放っておくのも失礼なので、一旦〆させていただきます。

ポイントの方ですが、甲乙つけるのは無理なので、全員20点満点といきたいところですが、ポイントつけられる人数に限りがございますので、ここはあえてポイントをつけません。ご了承下さい。

それでは、またの機会に、よろしくお願い致します。
本当にありがとうございました！！

お礼日時：2002/09/04 12:58

No.5 回答者： shadoworks 回答日時： 2002/04/18 12:01

　まず、以下を具体的・明確にしてください。

１）計算処理の目的
２）与えられるデータの予想される特徴
３）求めるデータの想定可能な特徴
４）使用するＣ言語コンパイラの機能
　以上のどれが違っても最良の計算法は違います。
繰り返し処理する部分を軽くすると速くなります。
（機械内部の情報格納の都合により、ここを単純
化できるクイックソートはそのため高速です）。
　細かい事はコンパイラに任せ、精度を保つため
桁落ちに注意し、似たデータを使い回しましょう。
（時系列で見ると変化のみ再計算すれば良い等）


桁落ちについて
　精度＝計算する桁数を落とせば簡単に速くなる
でしょうし、処理量を増やさずに精度を高く維持
できれば、それは高速化につながるわけです。
　数値処理の過程で、絶対値の大きさが余りにも
違う２数を加減算すると、絶対値が小さい方の数
の有効数字の情報量が無駄に消えてしまいます。
　ほとんど同じ数値同士を減算したり、絶対値が
等しく符号が反対の数を加算するなど、きわめて
ゼロに近い数値が出ると計算精度が失われます。

No.4 回答者： hinebot 回答日時： 2002/04/18 09:43

mickel131さんの分類を利用させていただき、最小値についてアドバイスを。

ax+by=cが一次関数すなわち直線であることはいいですね。

(2)ｘ軸に平行なとき
ｙの値はｘの値に関係なく一定です。よって、ｘが最小のときつまりｘ＝０が求めるべき値になるでしょうか。

(3)ｙ軸に平行なとき
(2)の場合とｘとｙが入れ替わるだけです。すなわち、ｘの値はｙの値に関係なく一定です。（後略）

(1)傾きが -a/b (a≠0,b≠0のとき）
二つの場合があります。すなわち、 -a/b>0 のときと -a/b<0 のときです。

i)-a/b>0 のとき
グラフは右上がりになります。よって、xが増加（減少）すれば、ｙも増加（現象）します。よって、x=0のときか、y=0のときが、x,yどちらも最小値をとります。x=0のときをとるか、y=0のときをとるかは、y切片 (c/b)の符号によります。

ii)-a/b<0のとき
グラフは右下がりになります。よって、 xが増加（減少）すると、yは減少（増加）します。（よって、xが最小値のときｙが最大値となり、yが最小値のとき今度はxが最大値になります。）従って、何をもって最小値とするかが必要になります。
※単にxが最小値の場合と、yが最小値の場合を別々に求めればいいなら当然、x=0,y=0がそれぞれの最小値になります。

No.3 回答者： mickel131 回答日時： 2002/04/17 22:20

ここに図が書けないので、うまく表現できないのですが、

不等式を満たすｘとｙの値を組にした点（x,y)をとることを考えてください。
そうして取った点の集合は、平面上のある範囲になります。
これを、「領域」と言います。
領域を図示して、最小・最大を考えるタイプの問題は、
「線形計画法」と言います。
「言います」と言い切っておいて、何ですが、これは、ちょっと不正確な定義です。昔の高校の数(1)の受検参考書には出ていましたが、この頃のには載ってない気がします。今は数(2)の分野に入っています。
直接の答えにはなっていませんが、さらにちょっとだけ書きます。

ax+by=c　－－－（＊）

（１）a ≠ 0、ｂ≠0 のとき
　（＊）すなわち、
　y=(-a/b)x+(c/b)
を満たす点(x,y)の集合は
　傾き(-a/b)　の直線です。
(２）a=0 ,ｂ≠0のとき
　（＊）は
　y=(c/b)
となり、x軸に平行な直線です。
（３）b=0 ,a ≠ 0のとき、
　（＊）は、
　 X=(c/a)
となり、ｙ軸に平行な直線です。

No.2 回答者： KaitoTVGAMEKOZOU 回答日時： 2002/04/17 18:41

ＮＯ１の方に賛成します。

最大最小を求める問題は、方法３つあって、

１．数値代入
２．平方完成
３．微分

です。１は一次関数のとき、超絶的に威力を発揮します。２は、すべての２次関数は「相似」であることを利用する解法です。これも破壊的な威力を発揮します。このとき数値代入をして値を求めるので、やはり数値代入は超絶的に威力を発揮します。３はグラフの傾きを考えることによって、グラフの概形をつかみ、数値代入によって値を求める方法で、神がかり的な威力を発揮します。

どの方法も数値代入をしているので、最大最小を求める基本的な方法（最重要方法）は、数値代入であることをここに明記します。

No.1 回答者： may-may-jp 回答日時： 2002/04/17 13:53

一次関数はどんなときも直線です。

その直線がx≧0かつy≧0の範囲にある場合、描ける直線は3通りです。傾きが正の場合と負の場合、あとは0の場合です。

困ったら基本に立ち返ってみることだと思います。