Mẹo về Phương pháp góc tây-bắc trong bài toán vận tải lối đi bộ Mới Nhất
Bạn đang tìm kiếm từ khóa Phương pháp góc tây-bắc trong bài toán vận tải lối đi bộ được Update vào lúc : 2022-06-26 11:00:08 . Với phương châm chia sẻ Kinh Nghiệm về trong nội dung bài viết một cách Chi Tiết Mới Nhất. Nếu sau khi Read nội dung bài viết vẫn ko hiểu thì hoàn toàn có thể lại Comments ở cuối bài để Admin lý giải và hướng dẫn lại nha.
Loading Preview
Sorry, preview is currently unavailable. You can tải về the paper by clicking the button above.
với những ràng buộc:
n
∑
j =1
m
∑
i =1
xij = ai ; i = 1,2,…, m
xij = b j ; j = 1,2,…, n
và :
xij ≥ 0 (i = 1,2,…, m ; j = 1, 2,…, n )
– Ngoài ra trong trường hợp đơn thuần và giản dị thường giả thiết là tổng dung tích hàng phát đi cân riêng với
tổng dung tích nơi nhận, nghĩa là:
m
n
∑ a = ∑b
i =1
i
j =1
j
2. Phương pháp góc tây-bắc
4.3.2.Xác định phương án cơ bản ban đầu
* Phương pháp góc tây-bắc xác lập giá trị (m+n-1) ẩn cơ bản của phương án ban đầu.
– Xuất phát từ góc bên trái trên cùng (x11) ta điền những giá trị của ẩn cơ bản và đi dần xuống góc
phải dưới cùng, đồng thời luôn luôn thoả mãn những ràng buộc ở mục trên.
Nơi
phát
A1
A2
Dung
lượng
bi
Nơi nhận
B1
B2
5
150
50
2
0
200
150
250
2
Dung lượng
ai
200
6
300
B3
3
0
4
100
100
500
Có hai nơi phát A1, A2 với những lượng hàng tương ứng a1 = 200; a2 = 300 và 3 nơi nhận với nhu
cầu tương ứng b1 = 150; b2 = 250; b3 = 100. Cước phí vận tải lối đi bộ cij được ghi ở góc cạnh phải phía trên
trong từng ngăn ở bảng. Xuất phát từ góc tây-bắc ta có x11 = 150 (vì b1
42
1.2. Tạo phương án vận tải lối đi bộ xuất phátKhái niệm bảng vận tải lối đi bộ Bảng vận tải lối đi bộ có m hàng, n cột gồm m×n ơ, m là số điểm cung, n là số điểm cầu với cước phí cijđược ghi trong ô i, j cho cung đường i, j. Khi m =3, n = 4 như trong ví dụ trên, ta có bảng vận tải lối đi bộ II.2.Bảng II.2. Bảng vận tải3 27 6Cung 1: 5000 7 5 2 3Cung 2: 60002 5 4 5Cung 3: 2500 Cầu1: 6000 Cầu 2: 4000Cầu 3: 2000 Cầu 4: 1500 Tổng: 13500Ta cần tìm phương án phân hàng vào những ô i, j sao cho tổng theo hàng hay cột đều khớp với những lượng cung, cầu và tổng ngân sách vận tải lối đi bộ là nhỏ nhất. Mỗi ơ i, j biểu diễnmột cung đường vận chuyển hàng từ điểm cung i về điểm cầu j.Các phương pháp tạo phương án xuất phát Có một số trong những phương pháp tạo phương án xuất phát. Ta nghiên cứu và phân tích hai phương phápsau đây.− Phân phát hàng tối đa vào góc tây-bắc của bảng vận tải lối đi bộ. − Sau khi hàng cung hoặc cột cầu đã thoả mãn thì ta thu gọn bảng vận tải lối đi bộ bằngcách bỏ bớt hàng cung hoặc cột cầu đó đi chỉ bỏ một trong hai thứ hoặc hàng hoặc cột, ở đấy là toán tử hoặc loại trừ,OR exlusive. − Tiếp tục lặp lại hai bước trên đây cho tới khi hàng được phân phối hết vào những ôcác ô được phân hàng được gọi là ơ sử dụng. Bằng phương pháp “góc tây-bắc” ta tạo nên phương án A trong bảng II.3 với sáuô sử dụng 1, 1, 2, 1, 2, 2, 2, 3, 3, 3 và 3, 4.Bảng II.3. Phương án xuất phát với phương pháp “góc tây-bắc”3 27 65000 71000 54000 21000 32 54 10005 150043Tổng ngân sách vận tải lối đi bộ: ΣCPVT = 3×5 + 7 × 1 + 5 × 4 +2 × 1 + 4 × 1 + 5 × 1,5 × 1000 = 55500.b. Phương pháp cước phí tối thiểu Phương pháp này được phát biểu tương tự phương pháp góc tây-bắc nhưng ưutiên phân phát hàng vào ơ có cước phí nhỏ nhất nếu có nhiều ơ như vậy thì chọn ơ bất kì trong số đó. Lúc này ta có phương án xuất phát là phương án B cho trong bảng II.4.Bảng II.4. Phương án xuất phát với phương pháp cước phí tối thiểu3 27 61000 4000 72500 52 20003 15002 25005 45Tổng ngân sách vận tải lối đi bộ: ΣCPVT = 3 × 1 +2 × 4 + 7 × 2,5 + 2 × 2 + 3 × 1,5 + 2 × 2,5 × 1000 = 42000Nhận xét − Phương pháp cước phí tối thiểu thường cho phương án xuất phát tốt hơn phươngpháp “góc tây-bắc”. − Bảng vận tải lối đi bộ có số ơ sử dụng là 3 + 4 − 1 = 7 – 1 = 6. Một cách tổng quát bảngvận tải m hàng, n cột có số ơ sử dụng là m + n – 1. − Bài toán vận tải lối đi bộ cũng là BTQHTT. Trong ví dụ đang xét, nếu kí hiệu xijlà lượng hàng vận chuyển trên cung đường i, j thì toàn bộ chúng ta BTQHTT sau:z = c11x11+ c12x12+… + c34x34→ Min với những ràng buộc:11 1213 1421 2223 2431 3233 3411 2131 1222 3213 2333 1424 34ijx xx x5000 xx xx 6000x xx x2500 xx x6000 xx x4000 xx x2000 xx x1500 xi 1, 2,3; j 1, 2,3, 4 ++ += ⎧⎪ ++ += ⎪⎪ ++ += ⎪+ += ⎪⎨ ++ =⎪ ⎪+ += ⎪+ += ⎪⎪ ≥ ∀ = =⎩44Hệ những ràng buộc có 12 biến với 7 phương trình. Nếu lấy tổng 3 phương trình đầu trừ đi tổng 3 phương trình tiếp theo thì được phương trình cuối. Có thể kiểm nghiệm dễdàng, số phương trình độc lập tuyến tính của hệ là 7 – 1 = 6. − Mỗi phương án xuất phát A hay B tìm kiếm được của bài tốn vận tải lối đi bộ đó đó là mộtphương án cực biên xuất phát khi giải BTQHTT. Bài tốn vận tải lối đi bộ hoàn toàn có thể hồn tồn giải được bằng phương pháp đơn hình. Tuy nhiên do cấu trúc đặc biệt quan trọng của tớ, bài tốn vậntải hoàn toàn có thể giải bằng phương pháp đặc biệt quan trọng với thuật toán chuyên được sử dụng.
Reply
6
0
Chia sẻ
Share Link Download Phương pháp góc tây-bắc trong bài toán vận tải lối đi bộ miễn phí
Bạn vừa Read Post Với Một số hướng dẫn một cách rõ ràng hơn về Video Phương pháp góc tây-bắc trong bài toán vận tải lối đi bộ tiên tiến và phát triển nhất và Chia Sẻ Link Cập nhật Phương pháp góc tây-bắc trong bài toán vận tải lối đi bộ Free.
Hỏi đáp vướng mắc về Phương pháp góc tây-bắc trong bài toán vận tải lối đi bộ
Nếu sau khi đọc nội dung bài viết Phương pháp góc tây-bắc trong bài toán vận tải lối đi bộ vẫn chưa hiểu thì hoàn toàn có thể lại Comments ở cuối bài để Mình lý giải và hướng dẫn lại nha
#Phương #pháp #góc #tây #bắc #trong #bài #toán #vận #tải