ax-by=c

質問

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

回答No.6

stomachman

（条件１）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点満点といきたいところですが、ポイントつけられる人数に限りがございますので、ここはあえてポイントをつけません。ご了承下さい。

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