数学の問題です。

今仕事で仕分け作業をしています。小箱を大箱に要領よく詰めるのですが、考えるのに時間がかかります。そこで数学で解けないかと思い質問しました。

小箱はAからLまでの12種類です。
サイズは  縦*横*高さ
大箱 300*400*350
A~Iまでは縦*横が同じで150*200です。
高さがA30B50C60D90E110F120G150H200I230です。
J~Kは、縦*横=300*200です。
高さがJ30K90L120です。

知りたい答えは
・全部で何箱必要か?
・1箱目に何がいくつ入り2箱目には何がいくつ・・・

それをプリントアウトしアルバイトに詰めてもらおうと思っています。

文章が下手で申し訳ないのですが、どなたか教えてください。お願いいたします。
ポイントは最高500ポイントを考えています。

回答の条件
  • URL必須
  • 1人5回まで
  • 登録:2006/06/23 17:14:56
  • 終了:2006/06/26 14:48:54

回答(8件)

id:kioh No.1

kioh回答回数80ベストアンサー獲得回数42006/06/23 17:29:13

id:kouryukai

すいません書いてませんでしたね。

仕分ける店舗によって各数量が違うので数式とか知りたかったのです。

例えば10店舗あり、A店舗では小箱Aが10Bが20・・・・B店舗では小箱Aが0Bが20・・・

といった感じです。

2006/06/23 17:36:14
id:taknt No.2

きゃづみぃ回答回数13539ベストアンサー獲得回数11982006/06/23 17:31:32

ポイント100pt

2つの大箱に AからLの小箱 すべて入りそうですが・・・。

まず、A~Iは、1/4の面積を占めますね。

J~Lは 1/2

JKLと縦に重ねていくと 高さ 240となります。

その上は、E、BとCで 埋めます。

で、その横に FとI、GとHで すべて埋まります。

残り AとDが 2つめの大箱になります。

http://ja.wikipedia.org/wiki/%E7%AE%B1%E8%A9%B0%E3%82%81%E3%83%9...

id:kouryukai

申し訳ないです。

数量を書いてませんでした。

2006/06/23 17:37:02
id:apple-eater No.3

apple-eater回答回数420ベストアンサー獲得回数82006/06/23 19:23:43

ポイント100pt

おおざっぱな戦略ですが:

まず、全ての小箱の容積を計算します。

この容積を大箱一つの容積で割って切り上げた値が

「どんなに切り詰めても、少なくとも必要な大箱の数」

になります。

---

小箱を数の多い順に詰めてゆくことになると思いますが、

「A~Iを組み合わせてJ~Lのサイズに出来るときには、J~Lのカタチにします。」

(A二つでJ、D2つでK、F2つでL)

A~Iは4個単位で大箱の底を埋めます。

J~Lは2個単位で大箱の底を埋めます。

J~L(A~Iを組み合わせたものも含む)から詰めていったほうが、楽そうです。

J~Lでつめて入って大箱を埋めていきます。

あまった隙間にA~Iをいれてゆくという感じでしょうか。

A~IのグループとJ~Lのグループと比較してどちらが多いかで戦略も変わるかもしれません。

URLはダミー(http://www.hatena.ne.jp/

id:dungeon-master No.4

dungeon-master回答回数571ベストアンサー獲得回数402006/06/23 19:30:40

ポイント100pt

数ある組合わせの中から最適な解を求めるという問題ということになりますが

おそらく数学の世界で言うところのNP完全問題と呼ばれる類に相当するため、

単純な数式で答えが出せるものではないでしょう。

http://www.is.titech.ac.jp/~sassa/keisankikagaku-gairon03/keisan...

ここのPage121にあるトラックの荷積み問題が本件とかなり似た性質のものです。


このケースで数式を使って求められるのは、せいぜい最低限必要となる大箱の個数です。

(
  (
    (Aの個数*Aの高さ+Bの個数*Bの高さ+…Hの個数*Hの高さ)
    +
    (Jの個数*Jの高さ+Kの個数*Kの高さ+Lの個数*Lの高さ)*2
  ) 
  /大箱の高さ
)
の整数に切り上げた値

これより少ない個数の大箱には(単純に体積的な問題として)入りきらない。

だからと言って、この個数の大箱で十分というわけではないことに注意。


ご質問のケースでは小箱の底面が2種類でどちらも大箱の底面を正分割できますので、

小箱を立てたり向きを変えたりしないなら大箱半分を基本単位として計算可能です。

JKLの組合わせのパターンを求めて、それに対してA~Hを付け込んでいき、大箱の

個数が一番少なくなる解を求めるのが、プログラムとして組み込むのも比較的

やりやすいと思われます。

(ただこれを、まともに総当りでやると相当な計算量になということです)


そこそこの精度の解を得られれば十分という条件で、適当な計算量で終らすための

方法が幾つか考えられています。

遺伝的アルゴリズム(GA)もその一つ。

http://www.personal-media.co.jp/book/comp/173/04.html


物流系のパッケージソフトにこういう問題を解いてくれるものがありますが、

安いものでも数十万円から掛かります。

id:Z9M9Z No.5

Z9M9Z回答回数343ベストアンサー獲得回数112006/06/23 21:22:47

ポイント100pt

http://web.yl.is.s.u-tokyo.ac.jp/pl/abclf/ipa-final/reports/html...

まあ一般論としては↑面倒な話もあるんですけど、数値が簡単そうなので‥。

こういうのは大きい順に入れるべきです。

(1)まず、Lを入れます。空の大箱1つに4個入ります。

(2)次に、Kを入れます。

  2-1 空箱1つには6個入ります。

  2-2 (1)で4個入れてても2個入ります

  2-3 (1)で3個入っていると、3個入ります

  2-4 (1)で2個入っていると、4個入ります

  2-5 (1)で1個入っていると、5個入ります

(3)次に、Jを入れます。

‥これを全部についてプログラムすると、A~Lの個数をもらったら大箱何個でそれぞれの入れ方はこう、というのがさっと出るようになります。ここまで数値とかが具体的で、さらに2個とか4個とか、縦横ベースでブロック化できているような関係ですので、プログラムの経験ある人なら、たいがい2~3日ももらえれば書けると思います。(と大きく出る^o^)

でもまあ、L→Aの順に、それぞれまとめておいて、入るところに入れる、という作戦で、実際上は十分ではないでしょうか。A~Lが数百個とか大量で、大箱の数を事前に見積もりたいなら、話は別ですけど。

id:masutaka47 No.6

masutaka47回答回数2ベストアンサー獲得回数02006/06/23 22:39:39

ポイント100pt

URLはダミーです。↓

http://q.hatena.ne.jp/1151050494

サイズを見た感じだと、高さがネックになっていると思われます。

そこで、小箱の高さ別に2つのグループに分けます。

A,C,D,F,G,J,K,L,以下(グループ1)

B,E,H,I         以下(グループ2)

グループ1は30の倍数です。

グロープ2はそれ以外です。

高さが350なのでグループ1だけではきれいに箱詰めできません。

そこで、最初にグループ2を入れ、そのあとにグループ1を入れます。

具体的にいうと、グループ2だけを使って高さを50、110、200、230、260にしてその後、グループ1をいれます。

これで、きれいに箱詰めしやすくなりますし、いろんな状況に対応できると思います。

なお、状況によりグループ2だけで、きれいに箱詰めすることもできます。

    

id:mitou73 No.7

mitou73回答回数67ベストアンサー獲得回数52006/06/23 23:35:12

ポイント100pt

線形計画法(LP)で解けそうな気がするんですが、自信ないです。

以下のような定式化をしてやって、mを適当に大きい数字にして、解いてみる。

mが大きすぎると、Mは0になるので、mを1つずつ小さくして、Mが1以上になったときが、大箱の個数が最も少なくて済む。

もっとうまい定式化の方法があると思うんですが・・・。

ちなみに、線形計画法を解くには、EXCELのソルバーがありますが、実行できるかどうかは不明。(使ったことないです)

http://www.kogures.com/hitoshi/webtext/lp-solver/index.html

目的関数

 M = nam + nbm + … + nlm → 最小化

制約条件

   na1*xa + nb1*xb + … ≦ 300 (縦の制約条件)

   na1*ya + nb1*yb + … ≦ 400 (横の制約条件)

   na1*za + nb1*zb + … ≦ 350 (高さの制約条件)

    :

   nam*xa + nbm*xb + … ≦ 300 (縦の制約条件)

   nam*ya + nbm*yb + … ≦ 400 (横の制約条件)

   nam*za + nbm*zb + … ≦ 350 (高さの制約条件)

   na1 + na2 + … + nam ≧ Aの個数

   nb1 + nb2 + … + nbm ≧ Bの個数

    :

   nl1 + nl2 + … + nlm ≧ Iの個数

xa:Aの縦サイズ(定数)

ya:Aの横サイズ(定数)

za:Aの高さ(定数)

(以下Lまで同じ)

na1:1箱目に入るAの個数(変数)

nam:m箱目に入るAの個数(変数)

(以下Lまで同じ)

id:sami624 No.8

sami624回答回数5245ベストアンサー獲得回数432006/06/24 11:34:37

ポイント100pt

先ずA~IとJ~Lは別の箱に入れると考えたほうが分かりやすいでしょう。

でっ、A~Iは、底に4箱入れることができ、それぞれ高さの合計が350となる方程式を解けばいいこととなります。

10A+1B=8A+1B+1C=7A+1B+D=6A+1B+1F=6A+1C+1E=5A+1B+1G=5A+1H=4A+1B+1C+1F=4A+2C+1E=4A+1E+1F=4A+1I=3A+1C+1H=3A+1C+1D+1E=3A+1B+1C+1G=2A+1D+1H=2A+1B+1D+1G=2A+1C+1I=2A+1C+1E+1F=2A+2D+1E=1A+1F+1H=1A+2C+1H=1A+1F+1H=1A+1B+1F+1G=7B=4B+1G=4B+1C+1D=3B+1D+1E=3B+1H=1B+1C+2F=1B+5C=1B+2C+2D=1C+1D+1H=2C+1I=2C+1E+1F=6C+1E=1D+1E+1G=1E+2F=1G+1Hの場合に無駄なく入りますから、各係数の合計を4種類足した数が、納品数となります。

J~Lは隙間無しでの納品が困難であるため、隙間を考慮して効率的に入れた場合、

11J=8J+1K=7J+1L=5J+2K=6J+1L+1K=3J+2L=1K+2Lとなります。

よって、Aを10個Bを1個の組み合わせが最も効率よく44個入り…というように入れる個数を算出できます。

http://homepage3.nifty.com/sami624/index.html~030915

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません