Thuật toán bài toán tối ưu về xây dựng (6 người xem)

[VADaNang]

+ Mình có 1 bài toán tối ưu chưa tìm ra thuật toán. Mong được giúp đỡ.

Bài toán cụ thể như sau:
Đầu vào:
Ta có N1 cấu kiện có chiều dài L1 (real)
N2 cấu kiện có chiều dài L2 (real)
.....................................................
Nn cấu kiện có chiều dài Ln (real)
Trong đó N1, N2 ... Nn là số cấu kiện của cấu kiện có chiều dài tương ứng L1, L2 ..., Ln.

Đầu ra:

Phân tích tìm ra tổng số tổ hợp của tất cả các cấu kiện trên sao cho thoả mãn điều kiện :
N1x . L1 + N2x.L2 + + Nnx.Ln gần bằng 11,7(m) với sai số cho trước
Trong đó N1x, N2x ... Nnx là số cấu kiện ứng với từng chiều dài L1,L2....
để sao cho số thanh còn lại (không nằm trong các tổ hợp) là ít nhất.

Cụ thể các tổ hợp cần tìm thoả mãn điều kiện:
N11 . L1 + N21x.L2 + + Nn1x.Ln gần bằng 11,7(m) với sai số cho trước
N12 . L1 + N22x.L2 + + Nn2x.Ln gần bằng 11,7(m) với sai số cho trước
..................
v.v.v...........
Trong đó :
N11+N12+......= gần tiến tới N1 (gần bằng N1)
N21+N22+......= gần tiến tới N2 (gần bằng N2)
........................
Nn1+Nn2+......= gần tiến tới Nn (gần bằng Nn)

 

[Mr Okebab]

Mấy hôm nay bận quá nên không ngồi viết bài toán gửi cho bác NVSON được. Mong bác thông cảm.
Quả thực mấy vấn đề này phải nhờ các cao thủ về lập trình và giải thuật. Mong mọi người giúp đỡ.

 

[PMXD]

Đây là bài toán cắt thép tại công trường, thuật toán này trước đây tôi cũng đã va phải nhưng lâu rồi không để ý nữa.

 

[VADaNang]

Đúng vậy. Đối với vấn đề này đôi lúc mình làm tay (qua bảng tính excel), nhưng nghĩ để chuyển qua để viết chương trình thì chưa có giải pháp.

 

[htb]

Co ai giup minh voi!
Minh muon tach so tu 1 chuoi de cho ra gia trij kieu so
Vd: Khoi luong=(3*3+6*8+3.2*5)
ban co the giup minh tach chuoi tren tu dau "=" tro di va cho ra mot gia tri dung bang gia tri cua bieu thuc do

 

[anhtuan1066]

Bạn ttphong2007 có 1 bài viết về vấn đề này khá hay... Bạn Search tìm tên bạn ấy sẽ có đo..
Tôi ko nhớ nó nằm ở đâu... Phong giới thiệu cho bạn ấy đoạn code của bạn đi!
ANH TUẤN

 

[mai van tri]

VADaNang đã tối ưu được bài toán cắt thép chưa ?

Chúng ta hợp tác. Tôi đang có ý định viết chương trình đó đây.

Liên lạc với tôi theo SĐT : 0937271593
mail : trigialai@yahoo.com

 

[VADaNang]

Chào bạn .
Mình đã làm thực hiện nhưng thuật toán thấy chưa ổn và ngoài ra còn nhiều vấn đề chưa xử lý trong quá trình cắt sắt
Mình gởi file các bạn xem qua .

 

[SoiBien]

Chào bạn .
Mình đã làm thực hiện nhưng thuật toán thấy chưa ổn và ngoài ra còn nhiều vấn đề chưa xử lý trong quá trình cắt sắt
Mình gởi file các bạn xem qua .

Đây là phương pháp giải của mình, áp dụng solver cho nó tính.

Mình chưa áp dụng một lần solver cho tất cả được, vì thứ nhất là Change cells quá lớn, Solver chạy rất lâu (10 loại sắt yêu cầu là chạy ngày đêm luôn không ra được )

Mình giải quyết bằng cách loại trừ dần, tuy không phải là cách tối ưu nhất theo toán học, nhưng hình như có ít hơn số cây sắt phải sử dụng theo code cũ của bác VADaNang (theo cách diễn đạt của tôi trong file) cũng có thể không đúng, bác VADaNang và bác mai van tri cho ý kiến nhé.

 

[VADaNang]

Chào bạn.
Hiện tại mình thử qua một số trường hợp thấy được nhưng đúng với một số trường hợp khác như số liệu này thì chưa hiệu quả nên mình mới đưa ngay trường hợp này lên. (Nói chung như mình đã nói thuật toán còn xử lý thêm nhiều nữa mới tối ưu được)
Thân chào bạn.

 

[mai van tri]

Theo tôi nghĩ thì đầu tiên mình làm sao phải tìm ra được số cây thép sẽ dùng để cắt, nếu biết được điều này thì coi như đã làm xong tất cả. Theo tôi nghĩ nếu dùng quy tắc loại trừ thì ta vẫn để sót nghiệm. Bởi vì nều có nhiều tổ hợp nhiều cây thép cùng có chiều dài cắt là 11.7m thì chỉ chọn được 1 tổ hợp, Sau đó dùng quy tắc loại trừ ta sẽ có tổ hợp cắt thép tiếp theocũng có chiều dài là 11.7m. Nhưng nội trong những tổ hợp có chiều dài cắt thép là 11.7 thì cũng có thể sắp xếp thành những tổ hợp có chiều dài cắt thép tối ưu là 11.7m những tổ hợp này có thể kết hopự với những tổ hợp cắt thép chưa tối ưu ( <11.7m) để tạo ra những tổ hợp mà có chiều dài đoạn thép dư nhỏ hơn những quy tắc loại trừ.

Vấn đề bây giờ là tìm ra tổng số cây thép cần cắt sau đó sẽ tìm ra cách cắt như thế nào để lượng thép dư là nhỏ nhất. Tôi đang suy nghĩ vấn đề này.
Anh Em coi rồi cho ý tưởng với

Cảm ơn Anh Em vì tất cả.
Mong được học hỏi !

 

[KimNamCham]

File Cat Sat ToiUu cua ban SoiBien sửa lại khi chạy (click vào combo Toi Uu) thi báo lổi : "compile eror ; Can't find project or library" xin SoiBien cho biết lý do. Thanks

 

[SoiBien]

File Cat Sat ToiUu cua ban SoiBien sửa lại khi chạy (click vào combo Toi Uu) thi báo lổi : "compile eror ; Can't find project or library" xin SoiBien cho biết lý do. Thanks

File mình làm dùng công cụ Solver của Excel. Có lẽ là bạn chưa cài addin này. Bạn hãy vào menu tools, addin, click chọn addin solver trong list (có thể bạn sẽ cần đĩa source của bộ office bạn đang sử dụng trên máy tính)

Thân.

 

[mai van tri]

Goi cac Anh Em !

Toi moi viet duoc mot chuong trinh cat nhung thanh vat lieu co 1 chieu dai dinh hinh, Chi can nhap bang thong ke vat lieu vao va nhap them chieu dai dinh hinh la cac ban co the co duoc mot ket qua se phai cat thanh thep nhu the nao de luong du thep la nho nhat.


Anh Em kiem tra roi cho y kien ca noi dung va hinh thuc nhe !

 

[hppavilion]

Hay lắm Mai Văn Trí....Chương trình rât hữu ích cho thi công. Thank
mình ( Thanh _Chương mập ) có vài ý kiến như sau:
Chương trình cắt thép trên ứng dụng cắt thép cho thi công là chính, nhưng ưng với từng giai đoạn thi công ta mới tiến hành cắt thép ( ra thép ) tương ứng với giai đoạn thi công.... nếu chương trình có module import data từ file thống kê thép ứng với cấu kiện ví dụ : tk thép móng, khi đó tiến hành ra thép phần móng.

 

[hppavilion]

dữ liệu cột "số thanh" và "chiều dài 1 thanh" được nhập tự động từ file thống kê thép thì sẽ rất nhanh..... giảm số lần nhập số thanh và chiều dài thanh thép:
1 lần cho phần thống kê, và 1 lần nữa cho ra thép trong chương trình trên.

 

[nguyentuhp]

Thuật toán cho bài toán này quả là quá khó, Tôi đã Test với số liệu (file kèm theo) với files của các bạn gửi lên cho kết quả không theo mong muốn.
File này kèm theo cách giải thủ công, mọi người cố gắng tìm thuật toán nhé!
Chúc sớm thành công!

 

[tigertiger]

Quả thật gặp bài này và bài toán xếp hàng tối ưu thấy khó thật........

+ Bài này phải dùng thuật toán Vét cạn thôi
Vét tất cả các phương án rồi tìm ra -> phương án tối ưu,

+ hoặc là phương án quy hoạch tuyến tính - nhưng khó tìm được bằng solver

 

[SA_DQ]

Xin các bạn cho phản biện.

Trong xây dựng thì thép thanh được nối theo 2 cách thông dụng sau:
* Hàn nối
* Chập lên nhau & nối;
Với hàn nối thì độ dôi không đáng kể;
Với chập nối thì khoảng độ chập (chồng) lên nhau này có ghi trong TCVN;
Thép ngắn được các nhà cung cấp bán theo cấp chiều dài, thường gặp các loại sau: loại 3m, 4,5m , 6m & 9m; Một loại ngắn khác nữa là do ta tạo ra ngắn trong quá trình sử dụng;
Mình đề xuất cách giải theo hướng thép được nối chập lên nhau;
Xin các bạn xem file đính kèm & cho biết ý kiến!

Option Explicit
Const Chap As Double = 0.2
Sub ThepNgan()
 Dim lRow As Long, jZ As Long, lDem As Long, jW As Long
 Dim i20 As Double

1   'Tao Du Lieu Ngau Nhen'
    Range("A2:A201").Select
    Selection.FormulaR1C1 = "=2+INT(75*RAND())/10"
    Selection.Copy
    Range("A2").Select
    Selection.PasteSpecial Paste:=xlPasteValues, Operation:=xlNone, SkipBlanks _
        :=False, Transpose:=False
 
2   'Copy Du Lieu Sang Cot Ben De Lam Bang Chung'
    Selection.Copy:                 Range("B2").Select
    ActiveSheet.Paste:              Application.CutCopyMode = False
    Range("B1").Select:             Selection.Value = "Copy"
3   'Xep Cot Theo Chieu Giam Dan'
    SortCol Columns("B:B"), Range("B2")
5   'Tim Nhung Thanh Qua Ngan De Noi 3'
    lRow = Range("B65432").End(xlUp).Row
    Range("C2:D" & lRow + 9).Clear
    i20 = 11.7 + Chap - Cells(2, 2).Value
    For jZ = lRow To 2 Step -1
        If Cells(jZ, 2) >= i20 Then Exit For
    Next jZ
    i20 = (lRow - jZ) Mod 2
    Range("B2:B" & jZ + i20).Copy Destination:=Cells(2, 3)
    Range(Cells(jZ + i20 + 1, 2), Cells(lRow, 2)).Copy Destination:=Cells(jZ + i20 + 1, 4)
6   'Gop 2 Thanh Qua Ngan Mot Thanh'
    lDem = Range("C65432").End(xlUp).Row + 1
    For jZ = lDem To (lRow + lDem) \ 2
        With Range("C" & Range("C65432").End(xlUp).Row + 1)
            .Value = Cells(jZ, 4) + Cells(lRow - jW, 4) - Chap
            .Interior.ColorIndex = 38
        End With
        jW = 1 + jW
    Next jZ
7   'Nhu Dong (3)'
    SortCol Columns("C:C"), Range("C2")
8   'Chia Nhom Theo Dung Sai'
    i20 = Cells(2, 3) - Chap:                 lDem = 0
    For jZ = 2 To lRow
        With Cells(jZ, 3)
            If .Value < i20 Then
                .Offset(-1, 1) = lDem:            lDem = 1
                i20 = Cells(jZ, 3) - Chap
            Else
                lDem = lDem + 1
            End If
        End With
        If jZ > lRow / 2 And i20 < 5.7 Then Exit For
    Next jZ
End Sub

[B]Sub SortCol(Rng As Range, Clls As Range)[/B]
 Rng.Select
 Selection.Sort Key1:=Clls, Order1:=xlDescending, Header:=xlGuess, _
    OrderCustom:=1, MatchCase:=False, Orientation:=xlTopToBottom, _
    DataOption1:=xlSortNormal
[B]End Sub[/B]

http://www.nowupload.com/:EMQ

 

[tigertiger]

+ Góp ý một chút về code

đoạn này

1   'Tao Du Lieu Ngau Nhen' 
    Range("A2:A201").Select 
    Selection.FormulaR1C1 = "=2+INT(75*RAND())/10" 
    Selection.Copy 
    Range("A2").Select 
    Selection.PasteSpecial Paste:=xlPasteValues, Operation:=xlNone, SkipBlanks _ 
        :=False, Transpose:=False

Nên sửa thành:

1   'Tao Du Lieu Ngau Nhen' 
    Range("A2:A201").Select 
    Selection.FormulaR1C1 = "=2+INT(75*RAND())/10" 
    Selection.Value=Selection.Value

+ Có chưa được tối ưu bác SA ah, với cả thế này -> hóa ra là cắt ngẫu nhiên -> sau đó mới xét cái còn lại,..

+ Tuy vậy đây cũng là 1 cách làm rất hay -> có tính thực tế khi đã cắt ngẫu nhiên dở dang,
.