プロが教える店舗&オフィスのセキュリティ対策術

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

A 回答 (6件)

(条件1)ax+by=c


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

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

============================
[1] a=0, b=0の場合
 (条件1)は 0=c と書き直せます。
 [1-1] c=0の場合
  x,yとして任意の実数を持ってくると(条件1)は満たされます。
  だから(条件2)だけ考慮すればよく、minx = 0, miny = 0 です。
 [1-2] c≠0の場合
  x,yとしてどんな実数を持ってきても(条件1)は満たせません。従って
  minx, minyは存在しません。
[2] a≠0, b=0の場合
 (条件1)は ax=c と書き直せます。だから x=c/a が(条件1)を満たす唯一の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は存在しない」のこと
(00) とは「minx=0, miny=0」のこと
(0▼) とは「minx=0, miny=c/b」のこと
(▲0) とは「minx=c/a, miny=0」のこと
としてみると、

c>0
 b>0: a>0…(00)、a=0…(0▼)、a<0…(0▼)
 b=0: a>0…(▲0)、a=0…(××)、a<0…(××)
 b<0: a>0…(▲0)、a=0…(××)、a<0…(××)
c=0…(00)
 b>0: a>0…(00)、a=0…(00)、a<0…(00)
 b=0: a>0…(00)、a=0…(00)、a<0…(00)
 b<0: a>0…(00)、a=0…(00)、a<0…(00)
c<0
 b>0: a>0…(××)、a=0…(××)、a<0…(▲0)
 b=0: a>0…(××)、a=0…(××)、a<0…(▲0)
 b<0: a>0…(0▼)、a=0…(0▼)、a<0…(00)
となります。

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

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

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

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

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

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

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

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

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


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


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

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



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

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

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

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

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

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

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


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

ax+by=c ---(*)

(1)a ≠ 0、b≠0 のとき
 (*)すなわち、
 y=(-a/b)x+(c/b)
を満たす点(x,y)の集合は
 傾き(-a/b) の直線です。
(2)a=0 ,b≠0のとき
 (*)は
 y=(c/b)
となり、x軸に平行な直線です。
(3)b=0 ,a ≠ 0のとき、
 (*)は、
  X=(c/a)
となり、y軸に平行な直線です。
    • good
    • 0

NO1の方に賛成します。

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

1.数値代入
2.平方完成
3.微分

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

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

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


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

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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング