a,b,c,d,e,fはすべて0または正の整数とします。

質問

a,b,c,d,e,fはすべて0または正の整数とします。
a+b+d=10 a+e=9 b+f=6 c+d=5のとき
5a+3b+11c+８d+12e+4ｆの最小値はいくらですか

回答No.5

naniwacchi · ベストアンサー

こんにちわ。

一見手のつけようがないように見えますね。
一度、条件を大きな視点でとらえると、道筋が見えてきそうです。

まず、6つの変数に対して条件が 4つあります。
ということは、これらの条件は 2つの文字だけに置き換えることができるはずです。
（もし条件が 6つあれば、連立方程式として解けてしまいますね。）
そこで、そのターゲットを aと bとしてみます。

すると、
・1番目の式から d＝ 10- a- b
・上の式と 4番目の式を組み合わせて、c＝ a+ b- 5
・2番目の式から e＝ 9- a
・3番目の式から f＝ 6- b

と b～fの変数を aと bに置き換えることができました。

これらを最小値を求める式に代入します。
(与式)
＝(中略、自分で計算してみてください)
＝ -4a+ 2b+ 157

となります。

ここで上の d～fの式に注目すると
5≦ a+ b≦ 10
0≦ a≦ 9
0≦ b≦ 6

という条件式が得られます。
これらの条件のもとで、-4a+ 2bの最小値を求めるわけですが、
「線形計画法」で計算するのが一番わかりやすいかもしれません。
-4a+ 2b＝ kより、直線：b＝ 2a+ k/2の y切片が最小となるときを考えます。
すると、a＝ 9、b＝ 0で最小値をとることがわかります。
そして、求める最小値は 121となります。
（他の変数は、c＝ 4, d＝ 1, e＝ 0, f＝ 6）

お礼

詳しく教えていただきありがとうございました。

回答No.4

GeorgeWin7

計算ミスはあるかも知れませんが…

　変数6個（a,b,c,d,e,f）に対して、関係式が４個なので、

変数が2個の式に変換できます。
（例えば「a」と「f」の式に変換すると）

　5a+3b+11c+８d+12e+4ｆ
　⇒-4a-2f+169　　　　　　………(1)

a+e=9およびb+f=6より
a=9-e
f=6-b

変数は「0または正の整数」なので、
0≦a≦9，0≦f≦6

(1)の式が最小となるのはa=9,f=6のときなので、
　最小値は『121』

　…ハッキリ言って自信ありません＾＾

回答No.3

info22_

>a+b+d=10 a+e=9 b+f=6 c+d=5のとき
これから
c=b+a-5,d=-b-a+10,e=9-a,f=6-b…(A)
非負条件から
c=b+a-5≧0,d=-b-a+10≧0,e=9-a≧0,f=6-b≧0…(B)
これを
g=5a+3b+11c+８d+12e+4f
に代入すると
g=f=6-b≧0
これより
gの最小値は0
このときb=6,f=0
(B)から　c=1+a≧0,d=4-a≧0,e=9-a≧0,f=0
∴0≦a≦4
従って最小値0を与える(a,b,c,d,e,f)は
(a,b,c,d,e,f)=(0,6,1,3,9,0),(1,6,2,2,8,0),(2,6,3,1,7,0),(3,6,4,0,6,0)
の4組のみ。

回答No.2

Barcelona1988

記載が間違っていたりしないですか？

ちょっと手元の紙で計算してみました。
6つの変数による式で4つの方程式があるので5a+3b+11c.....は2つの変数に
よる式に変形できます。

ためしにaとbだけの式にしてみましたら
-4a+2b+158
となりました。（計算ミスしているかもしれません）

aとbは互いに完全に独立した数字とみなせるはずです。

-4aがあるため最小値は－無限大となる気がします。
問題もしくは私の計算が間違っている可能性が高いですが、2つの変数にすれば
回答が簡単にでます。

回答No.1

k_kota

a,b,d以外の変数を条件式を使って消去して整理する。
また、消去に使った式よりa,b,dの範囲を定める。

その後、係数の小さい変数から可能な限り値が大きくなるように値を決めてけばOK