数学の問題？ 板を効率よく切り分けたいです。

180センチ×90センチの板をカットして、希望の寸法に切り分けたいです。

カットしたい寸法は7種類あります。

a. 47.6 * 44 ・・・16枚
b. 49 * 16 ・・・16枚
c. 46.4 * 16 ・・・16枚
d. 47.6 * 16 ・・・32枚
e. 150 * 60 ・・・4枚
f. 150 * 49.1 ・・・2枚
g. 58.8 * 49.1 ・・・18枚

(単位は全てセンチメートル)

余り(端材)を可能な限り少なくなるように切るには、どのような組み合わせが最も効率がいいでしょうか？
求め方の計算式がありましたら教えてください。
なお、切りしろは5mmとします。

No.5 ベストアンサー 回答者： maiko0318 回答日時： 2014/02/16 22:01

作ってみました。

１４枚ですね。

添付できないのでHPにアップしました。

http://www.eonet.ne.jp/~fhm07425/shuu_01.pdf

１／１０スケールで作っています。
作業に掛かる前に大きさと枚数を確認して下さいね。

この回答へのお礼

14枚で済むのですね。
作って下さったファイル、有難く頂戴致します。
大変感謝です！

お礼日時：2014/02/17 10:39

No.18 回答者： okormazd 回答日時： 2014/02/18 00:55

いわゆるナップザックのような問題で、計算式は無いでしょう。

工夫して効率よく組み合わせを調べていくというやり方です。部材の形と数からそれほど難しいことは無いと思いますが、下記でどうでしょう。

e、f、gは、いずれも90cm巾方向で2枚はとれません。したがって、180cm方向でとるしかない。したがって、これらを指定枚数とるのに180cmが何枚必要かというのが最低枚数です。VBAでExcelソルバーを使って解く(試行錯誤のプログラムです)と、最低12枚は必要です。b、c、dはこのうちにとれるでしょう。たぶん、66枚とれる。あとは、aをとればいい。

e1-4枚
f1-2枚
g3-6枚

a6-2枚
a4-1枚

計15枚か。これより少なくは無理でしょう。

この回答へのお礼

やはり計算式はないのでしょうか。
VBAやEXCELなどで試行錯誤してみようと思います。
回答をありがとうございました。

お礼日時：2014/02/22 18:11

No.17 回答者： shuu_01 回答日時： 2014/02/17 21:26

No.5、No.16 さん、回答ありがとうございます

やはり、ケアレスミスはあったけど、No.5 さんの回答すごいです

僕も最初なんで 18枚となったか再検討するとケアレスミスでした

No.5 さんの描かれた図をじっと見ると、

大きな部材　　　　　　　：　e、f
（母材から１つしか取れない）
次に大きな部材　　　　：　g
（母材から３つしか取れない）
その次に大きな部材　：　a
（母材から６つしか取れない）
小さな部材　　　　　　　：　b、c、ｄ
（上記の余りから取れる）

に分けられ、

e を ４枚とるのに　母材 ４枚
f を ４枚とるのに　母材 ２枚
g を １８枚とるのに　母材 ６枚
a を １６枚とるのに　母材 ３枚

の合計 最低 １５枚は必要で ＝ １４枚以下はありえず、

その余りから 小さな部材 b、c、d は十分 取れちゃうようです

この回答へのお礼

とても論理的な分析をして下さり、ありがとうございます。
この考えを基に検討すれば効率的に取ることができそうで、大変助かっております。
この度はご教示を下さいまして、本当にありがとうございました！！！

お礼日時：2014/02/17 22:42

No.16 回答者： maiko0318 回答日時： 2014/02/17 16:30

no.10さん、

＞そこで確認してみましたが、g が本来 18枚 なのですが、15枚しかないのでは？

間違っているようです。ごめんなさい。＞NO10さん、質問者さん。

この回答へのお礼

とんでもないことです。
回答を下さいまして、大変助かっております。
この度は本当にありがとうございました。
感謝、感謝です！！！

お礼日時：2014/02/17 22:34

No.15 回答者： shuu_01 回答日時： 2014/02/17 16:11

No.12 で書き忘れましたが、180 X 90cm の板、15 枚必要と思います

この回答へのお礼

必要枚数は15枚なのですね。
回答を下さいまして大変ありがたいです。
この度はご親切にありがとうございました。
感謝です！！！

お礼日時：2014/02/17 22:32

No.14 回答者： shuu_01 回答日時： 2014/02/17 16:09

No.6 さんの教えてくださったシェアウェア「板取君2」 でも試してみました

まず　「システム設計」　で

部材の切取順序の設定：総当たり　（低速）
部材の回転方式の設定：総当たり　（低速）

を選ぶと、「計算量が多すぎます」 とアラートが出て、
部材を減らすか、システム設計を変更するよう
言われました

そこで、

部材の切取順序の設定：同一部材は連続して切り取る　（中低速）
部材の回転方式の設定：総当たり　（低速）

を設定して計算すると、１時間以上かかって計算し、
なんと １８枚になってしまいました

僕の最初のトライと偶然にも同じ数字です

今回のデータ量は板前君には大きすぎたようです

この回答へのお礼

データ量が大きかったようで、設定を限定することになったのですね。
であれば18枚という結果も頷ける気がします。
総当たりにすると全ての組み合わせが何通りあるのか、数学に疎くてあまり良く分からないのですが、仮に全ての数を掛け合わせると700万を超えるようです。
計算量が大きすぎたのでしょうか。
回答ありがとうございました。

お礼日時：2014/02/17 22:29

No.13 回答者： shuu_01 回答日時： 2014/02/17 15:58

No.12 の続きです

この回答へのお礼

大変わかりやすいです。
回答ありがとうございました。

お礼日時：2014/02/17 22:19

No.12 回答者： shuu_01 回答日時： 2014/02/17 15:57

No.10 が僕の勘違いでないとして、g を 18枚に増やしてみました

No.11 回答者： shuu_01 回答日時： 2014/02/17 15:54

No.10 の２枚目の画像です

この回答へのお礼

ありがとうございます。

お礼日時：2014/02/17 22:18

No.10 回答者： shuu_01 回答日時： 2014/02/17 15:53

No.5 さん、14枚はすごいです！

そこで確認してみましたが、g が本来 18枚 なのですが、15枚しかないのでは？
僕の勘違いでしょうか？
１つだと見にくいので、次の回答と合わせて２枚の画像で貼ります

この回答へのお礼

大変分かりやすいです。
回答ありがとうございました。

お礼日時：2014/02/17 22:18