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

Chia sẻ: Nguyễn Thị Giỏi | Ngày: | Loại File: PDF | Số trang:20

Thêm vào BST

Báo xấu

946
lượt xem 248
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: PHƯƠNG PHÁP PHÂN PHỐI

CHƯƠ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ỌN III. ĐÁNH GIÁ PHƯƠNG ÁN CỰC BIÊN IV. 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ả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 theo phương pháp đơn hình đã biết mà xây dựng một phương pháp giả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 :
TOP I. 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áp gó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òng và 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ộ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 .
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ây dự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ình giả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ều chỉ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 gian khô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ương phá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 ra
tồ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 . TOP II. QUI O Ô CHỌN
TOP III. ĐÁNH GIÁ PHƯƠNG ÁN CỰC BIÊN (Dấu hiệu tối ưu)
TOP IV. XÂY DỰNG PHƯƠNG ÁN CỰC BIÊN MỚI