PHƯƠNG PHÁP PHÂN PHỐI

Bài toán vận tải là bài toán Qui hoạch tuyến tính dạng chính tắc nên có thể giải bằng phương pháp đơn hình ( Chương I ) .Tuy nhiên , bài toán vận tải thường có số ẩn rất lớn ( mxn ) và có cấu trúc đặc biệt : ma trận các hệ số hầu hết bằng 0 ,do đó , chúng ta sẽ không giải bài toán
Nội dung trích xuất từ tài liệu:
PHƯƠNG PHÁP PHÂN PHỐICHƯƠNG 3 : BÀI TOÁN VẬN TẢI VÀ PHƯƠNG PHÁP PHÂN PHỐI BÀI 3: PHƯƠNG PHÁP PHÂN PHỐI I. XÂY DỰNG PHƯƠNG ÁN CỰC BIÊN II. QUI O Ô CHỌNIII. ĐÁNH GIÁ PHƯƠNG ÁN CỰC BIÊNIV. XÂY DỰNG PHƯƠNG ÁN CỰC BIÊN MỚI Bài toán vận tải là bài toán Qui hoạch tuyến tính dạng chính tắc nên có thể giảibằng phương pháp đơn hình ( Chương I ) .Tuy nhiên , bài toán vận tải thường có số ẩn rấtlớn ( mxn ) và có cấu trúc đặc biệt : ma trận các hệ số hầu hết bằng 0 ,do đó , chúng ta sẽkhông giải bài toán theo phương pháp đơn hình đã biết mà xây dựng một phương phápgiải đơn giản hơn , đó là phương pháp (thuật toán ) phân phối . Nội dung chính của phương pháp phân phối gồm các bước như sau : TOPI. XÂY DỰNG PHƯƠNG ÁN CỰC BIÊN Có 3 phương pháp xây dựng phương án cực biên thường sử dụng là phương phápgóc Tây - Bắc , phương pháp ưu tiên cước phí nhỏ nhất và phương pháp xấp xỉ Fogen .1 - Phương pháp góc Tây - Bắc a) - Phân phối tối đa vào ô góc Tây - Bắc của bảng ( góc trên bên trái ) . b) - Tính lại lượng hàng ở dòng và cột vừa tham gia phân phối . Tạm thời loại dòng hoặc cột có lượng hàng còn lại bằng 0 ra khỏi quá trình phân phối . Quay lại bước a)- ở trên và tiếp tục phân phối cho đến hết . Sau đây là ví dụ minh họa phương pháp xây dựng phương án cực biên.Ví dụ Cho bài toán vận tải dạng bảng kích thước 4 x 5 Các số ai được viết ở cột đầu tiên , các số bj được viết ở dòng đầu tiên . Các dòngvà cột này không tính vào kích thước bài toán . Ma trận cước phí [ ci j ] đưọc viết nhỏhơn ở phía dưới mỗi ô .2 - Phương pháp ưu tiên cước phí nhỏ nhất a) - Phân phối tối đa vào ô có cước phí nhỏ nhất của toàn bảng . b) - Tính lại lượng hàng ở dòng và cột vừa tham gia phân phối . Tạm thời loại dòng hoặc cộtcó lượng hàng còn lại bằng 0 ra khỏi quá trình phân phối . Quay lại bước a)- ở trên và tiếp tục phânphối cho đến hết .3 - Phương pháp xấp xỉ Fogen a)- Tính độ lệch của các dòng [ cột ] bằng hiệu số giữa cước phí nhỏ thứ nhì và cước phí nhỏ nhất trong dòng [ cột ] đó . b)- Xác định ô trũng : ô có cước phí nhỏ nhất ở trên dòng và cột cùng có độ lệch lớn nhất . Phân phối tối đa vào ô trũng nếu có và chuyển sang bước d). c)- Phân phối tối đa vào ô có cước phí nhỏ nhất ở trên dòng [ cột ] có độ lệch lớn nhất . d)- Tính lại lượng hàng trên dòng và cột vừa phân phối . Loại bỏ dòng hoặc cột có lượng hàng bằng 0 khỏi quá trình phân phối . Quay lại bước a) và tiếp tục quá trình cho đến hết . Trở lại bài toán ( 3-2 ) , ta xây dựng phương án theo phương pháp xấp xỉ Fogen . Về mặt lí thuyết , có thể đưa ra các ví dụ cho thấy rằng một phương án được xâydựng theo một phương pháp nào đó ( góc Tây - Bắc , ưu tiên cước phí nhỏ nhất , xấp xỉFogen ) tốt hơn là phương án û được xây dựng theo các phương pháp còn lại . Như đã nói ở trên , phương pháp góc Tây - Bắc thường được sử dụng khi lập trìnhgiải trên máy tính , vì sự đơn giản trong việc xác định ô phân phối và quá trình điềuchỉnh phương án để có phương án tối ưu được máy tính thực hiện tự động với thời giankhông đáng kể . Các bài toán kích thước không lớn được giải bằng tay thường sử dụng hai phươngpháp còn lại khi xây dựng phương án ban đầu .Ðịnh lí 5 Phương án thu được theo nguyên tắc phân phối tối đa là phương án cực biên . Ðộc giả có thể tự chứng minh chi tiết bằng phản chứng rằng nếu phương án thuđược không phải là cực biên thì tập các ô chọn sẽ chứa một chu trình (Ðịnh lí 4 ) , suy ratồn tại ít nhất một ô ( thực ra là tất cả các ô ) thuộc chu trình không được phân phối tốiđa , mâu thuẫn . TOPII. QUI O Ô CHỌN TOPIII. ĐÁNH GIÁ PHƯƠNG ÁN CỰC BIÊN (Dấu hiệu tối ưu) TOPIV. XÂY DỰNG PHƯƠNG ÁN CỰC BIÊN MỚI