Giải bài toán sắp xếp tối ưu các hình chữ nhật?

[cong]

Chào các bạn, tui có 1 ý tưởng này, tui nghĩ là phù hợp với đề tài này. Tui làm trong ngành cơ khí, gặp 1 vấn đề phải khai triển tôn, vấn đề là sắp xếp những mảnh hình chữ nhật trên 1 tấm tôn sao cho khi cắt sẽ hợp lý nhất, sau khi bấm nút Add thì Autoshape 1 sẽ được Add vào Autoshape 2 với kích thước đã định (Tất nhiên là Size của Autoshape sẽ thay đổi theo chiều dài, chiều rộng đã định), sau đó ta sẽ điều chỉnh vị trí của Autoshape 1 cho hợp lý bằng 4 nút Up, Down, Right, Left. Sau đó tiếp tục Add các Autoshape khác.....Các bạn xem file đính kèm nhé!!!....

 

[SoiBien]

Chào các bạn, tui có 1 ý tưởng này, tui nghĩ là phù hợp với đề tài này. Tui làm trong ngành cơ khí, gặp 1 vấn đề phải khai triển tôn, vấn đề là sắp xếp những mảnh hình chữ nhật trên 1 tấm tôn sao cho khi cắt sẽ hợp lý nhất, sau khi bấm nút Add thì Autoshape 1 sẽ được Add vào Autoshape 2 với kích thước đã định (Tất nhiên là Size của Autoshape sẽ thay đổi theo chiều dài, chiều rộng đã định), sau đó ta sẽ điều chỉnh vị trí của Autoshape 1 cho hợp lý bằng 4 nút Up, Down, Right, Left. Sau đó tiếp tục Add các Autoshape khác.....Các bạn xem file đính kèm nhé!!!....

Cám ơn bạn đã chia sẻ, nhưng tiếc quá, hình như marcro trong file này hình như là bị "BKAV" ăn hết rồi, bạn có file nào khác không?

 

[cong]

Hi SoiBien,
File đính kèm của tui chỉ là ý tưởng thôi! Mong mọi người cùng chia sẻ kinh nghiệm...

 

[SoiBien]

Hi SoiBien,
File đính kèm của tui chỉ là ý tưởng thôi! Mong mọi người cùng chia sẻ kinh nghiệm...

à, nếu vậy thì bài này nên là một bài toán tối ưu, chứ còn dùng 4 nút đó thì... lôi bằng tay nhanh hơn bạn ạ. Còn tối ưu như thế nào thì nhờ các bác nào có cách giải hay thì cho một chút ý kiến.

P.s : tối ưu này chắc là tối ưu diện tích phải không bác? độ dày mỗi nhát cắt là bao nhiêu đơn vị hả bác?

 

[anhtuan1066]

Đúng vậy, tôi cũng nghĩ đây là bài toán tối ưu thôi.. dựa vào chiều dài rông cho trước đễ tính ra số tấm tôn nhiều nhất có thể cắt dc... Tuy nhiên, kết quả báo "có thể cắt dc 5 tấm tôn" chẳng hạn.. nhưng cắt như thế nào mới là điều mình cần biết... Nên bài bạn Cong đưa ra cũng khá thực tế... Nhìn trực tiếp vào hình ta sẽ biết dc "CÁCH CẮT TÔN"

 

[SoiBien]

Một tấm lớn cắt ra nhiều tấm nhỏ có cùng kích thước thì còn dễ, đằng này yêu cầu là nhiều tấm nhỏ có kích thước khác nhau mới khó, cái này chắc phải nhờ các chuyên gia về giải thuật mới được.

 

[anhtuan1066]

Một tấm lớn cắt ra nhiều tấm nhỏ có cùng kích thước thì còn dễ, đằng này yêu cầu là nhiều tấm nhỏ có kích thước khác nhau mới khó, cái này chắc phải nhờ các chuyên gia về giải thuật mới được.

vậy bây giờ mình làm đơn giản hơn 1 chút: 1 tấm tôn có kích thước xác định trước, dc cắt ra thành nhiều mảnh, mỗi mảnh có kích thước giống nhau... Vậy số mảnh lớn nhất có thể cắt là bao nhiêu? Và cắt như thế nào?
Trong cty tôi cũng có làm việc với bài toán này, chuyên dùng cắt vật liệu, có điều họ ko làm bằng Excel... Họ có 1 phần mềm riêng, đặt vật liệu vào bàn, máy tính tự động dò tìm và ra dc kết quả tối ưu nhất đồng thời tự động cắt luôn... Tôi đễ ý là việc sắp xếp các mảnh dc hiển thị ngay trên máy tính và việc sắp xếp này ko theo trật tự nhất định.. Chỉ với 1 tiêu chí là làm sao cho phần vật liệu thừa đạt nhỏ nhất
Ko biết với Excel thì làm thế nào? E rằng hơi căng

 

[cong]

Hi anhtuan1066, SoiBien
Thật ra chương trình anhtuan1066 đề cập đến tui chưa gặp lần nào, ngoài thực tế tui đã gặp trường hợp như vậy nè: hình dạng cần cắt rất nhiều (tam giác, chữ nhật, đa giác, ...) tất cả hình dạng này đều được sắp xếp lên 1 tấm tôn bằng tay sao cho tối ưu nhất (ở đây tui thấy người ta sắp xếp bằng Autocad), sau đó xuất hình đó sang máy cắt tôn CNC (cắt bằng Oxy-Acetylen). Ý tưởng của tui ban đầu là làm cho hình chữ nhật thôi, sau đó có thể phát triển thêm cho hình dạng khác. Tui đang bí vấn đề sau:
- Add được nhiều autoshape và các autoshape đó không bị lấp bởi autoshape đại diện cho tấm tôn.
- lập trình cho nút Up, Down, Right, Left để điều chỉnh autoshape vừa mới add.
Mong các bạn giúp đỡ! thanks

 

[anhtuan1066]

Đúng rồi... cty tôi cũng dùng CNC đễ cắt vật liệu, có điều ko dùng Acad đễ làm việc sắp xếp đâu... người ta có 1 chương trình hẳn hoi, tự động hoàn toàn từ A tới Z... Tất cả nhiệm vụ của mình là cho chương trình biết các kích thước...
Có điều nếu làm việc này bằng Excel thì tôi ko biết có làm dc ko?

 

[SA_DQ]

Chỉ là di chuyển, thì tham khảo:

Hi anhtuan1066, SoiBien
thực tế đã gặp trường hợp như vậy nè: hình dạng cần cắt rất nhiều (tam giác, chữ nhật, đa giác, ...) tất cả hình dạng này đều được sắp xếp lên 1 tấm tôn bằng tay sao cho tối ưu nhất (ở đây tui thấy người ta sắp xếp bằng Autocad), sau đó xuất hình đó sang máy cắt tôn CNC (cắt bằng Oxy-Acetylen). Ý tưởng của tui ban đầu là làm cho hình chữ nhật thôi, sau đó có thể phát triển thêm cho hình dạng khác. Tui đang bí vấn đề sau:
- Add được nhiều autoshape và các autoshape đó không bị lấp bởi autoshape đại diện cho tấm tôn.
- lập trình cho nút Up, Down, Right, Left để điều chỉnh autoshape vừa mới add.
Mong các bạn giúp đỡ! thanks

Bạn đến mục trò chơi, xem file http://giaiphapexcel.com/forum/showthread.php?t=1604 của mình thử, chưa chắc giúp được bạn gì đâu!

/)/hưng vẫn mạnh dạn gợi í!

 

[SoiBien]

Hi anhtuan1066, SoiBien
Thật ra chương trình anhtuan1066 đề cập đến tui chưa gặp lần nào, ngoài thực tế tui đã gặp trường hợp như vậy nè: hình dạng cần cắt rất nhiều (tam giác, chữ nhật, đa giác, ...) tất cả hình dạng này đều được sắp xếp lên 1 tấm tôn bằng tay sao cho tối ưu nhất (ở đây tui thấy người ta sắp xếp bằng Autocad), sau đó xuất hình đó sang máy cắt tôn CNC (cắt bằng Oxy-Acetylen). Ý tưởng của tui ban đầu là làm cho hình chữ nhật thôi, sau đó có thể phát triển thêm cho hình dạng khác. Tui đang bí vấn đề sau:
- Add được nhiều autoshape và các autoshape đó không bị lấp bởi autoshape đại diện cho tấm tôn.
- lập trình cho nút Up, Down, Right, Left để điều chỉnh autoshape vừa mới add.
Mong các bạn giúp đỡ! thanks

Tìm được cái này cho bạn dùng thử trong 30 ngày.
http://astrokettle.com/y2dlp.zip

cho ý kiến xem nhé bạn.
Bác AnhTuan cho ý kiến luôn nhé.

 

[cong]

Hi SoiBien,
Ý tưởng làm chương trình sắp xếp Box rất hay, áp dụng vô Excel thì quá tuyệt!! Hiện giờ tui đang lập trình cho ý tưởng của mình. Khi hoàn thành mình sẽ post lên cho các bạn tham khảo!

 

[SoiBien]

Obtain Stock Sheet Dimensions
Obtain List of n Rectangles
Rotate each Rectangle so that Width >= Height
Sort Rectangle List by Decreasing Width (resolving equal widths by decreasing heights)
Initialize Skyline Array of n Elements
for Each Placement Policy (Leftmost, Tallest Neighbour, Smallest Neighbour) do
    while Rectangles [COLOR=darkblue]Not[/COLOR] Packed do
        Find Lowest Gap
        if (Find Best-Fitting Rectangle == true) then
            Place Best-Fitting Rectangle Using Placement Policy
            Raise Array to Appropriately Reflect Skyline
        Else
            Raise Gap to Lowest Neighbour
        [COLOR=darkblue]End[/COLOR] If
    end while
 
    while Optimisation [COLOR=darkblue]Not[/COLOR] Finished do
        Find Highest Shape
        if (Shape Width >= Shape Height) then
            Optimisation Finished
        [COLOR=darkblue]End[/COLOR] If
 
        Remove Highest Shape
        Reduce Array to Reflect Skyline
        Rotate Shape by 90 Degrees
 
        if (Shape Fits) then
            Place Best-Fitting Rectangle Using Placement Policy
            Raise Array to Appropriately Reflect Skyline
        Else
            Raise Gap to Lowest Neighbour
        [COLOR=darkblue]End[/COLOR] If
        if (Packing Better == [COLOR=darkblue]False[/COLOR]) then
            Optimisation Finished
        [COLOR=darkblue]End[/COLOR] If
    end while
end for
Return Best Solution

Thế thì Hay quá, đọc được cái "Tong hop" giải thuật này của Glenn Whitwell.

BÁc tham khảo thêm nhé.