Chương 3: Bài toán vận tải - bài 3

Tham khảo tài liệu chương 3: bài toán vận tải - bài 3, khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Chương 3: Bài toán vận tải - bài 3 CHƯƠNG 3- BÀI TOÁN VẬN TẢIBÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ1) Cơ sở toán họcVới bài toán vận tải dạng tổng quát (P): n m f ( x)   cij xij  min i 1 j 1 m x j 1 ij  ai n x i 1 ij  bj xij  0, (i  1, n, j  1, m) 1 CHƯƠNG 3- BÀI TOÁN VẬN TẢIBÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ1) Cơ sở toán họcTa có bài toán đối ngẫu (D) tương ứng như sau: n m g (u , v)   ai ui   b j v j  max i 1 j 1 ui  v j  cij i  1, n; j  1, mVà các cặp ràng buộc đối ngẫu của (P) & (D) có dạng:xij  0 và ui  v j  cij i  1, n; j  1, m 2 1 CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ   1) Cơ sở toán họcGiả sử, (P) có PACB không suy biến: x  x ij 0 0Khi đó, theo định lý độ lệch bù yếu, để x là PATU của bài 0toán (P) thì phải tồn tại một phương án u , v  của (D): i jui  v j  cij x ij  0 0  ui  v j  cij x 0ij  0 i  1, n; j  1, m Đây là tiêu chuẩn tối ưu của PA x0. 3 CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ   1) Cơ sở toán họcGiả sử, (P) có PACB không suy biến: x  x ij 0 0Khi đó, theo định lý độ lệch bù yếu, để x là PATU của bài 0toán (P) thì phải tồn tại một phương án u , v  của (D): i jui  v j  cij x ij  0 0  ui  v j  cij x 0ij  0 i  1, n; j  1, mĐây là tiêu chuẩn tối ưu của PA x0.ui, vj lần lượt được gọi là thế vị dòng & thế vị cột ij  ui  v j  cij : hệ số ước lượng. 4 2 CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 2) Nội dung thuật toán Với xij0  0 ta có đẳng thức ui  v j  cij ở các ô chọn, nếu biết ui thì sẽ xác định được vj;và ngược lại, nếu biết vj thì sẽ xác định được ui.Từ hệ u , v  vừa tìm được, nếu tất cả các cặp u , v  i j i jđều thoả mãn hệ ràng buộc (D) thì x0 là PATU của (P);Ngược lại, nếu tồn tại ít nhất 1 HSUL  ij  ui  v j  cij  0 thì x0 chưa là PATU. 5 CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 3) Điều chỉnh phương án khi tồn tại HSUL dươngTìm giá trị lớn nhất của  ij để xác định ô đượcđưa vào hệ thống ô chọn; giả sử là ô (i0,j0). Từ ô này, ta tìm vòng điều chỉnh. Trên vòng điều chỉnh, ta đánh vị trí chẵn/ lẻ của các ôchọn, xuất phát từ ô (i0,j0) được đánh vị trí lẻ. Ô chẵn với lượng hàng q nhỏ nhất là ô được chọnđưa ra khỏi hệ thống ô chọn và q lúc này được gọi làlượng hàng điều chỉnh. 6 3 CHƯƠNG 3- BÀI TOÁN VẬN TẢIBÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ3) Điều chỉnh phương án khi tồn tại HSUL dươngPACB mới   x*  xij* của bài toán được xác định theoqui tắc sau:+ Nếu ô (i,j) là ô chẵn trên vòng điều chỉnh: xij*  xij0  q+ Nếu ô (i,j) là ô lẻ trên vòng điều chỉnh: xij*  xij0  q+ Nếu ô (i,j) là ô không nằm trên vòng điều chỉnh: x ij*  x ij0 7 CHƯƠNG 3- BÀI TOÁN VẬN TẢIBÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ4) Các bước giải BTVT bằng thuật toán thế vị 8 4 CHƯƠNG 3- BÀI TOÁN VẬN TẢIBÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ5) Một số ví dụ5.1) Ví dụ 1: Ta xét lại ví dụ trong PP FOGELS và tiếnhành đánh giá tính tối ưu của PACB XP như sau: 9 CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 5) Một số ví dụTa nhận thấy rằng tất cả các HSUL của các ô loại đềuâm cho nên PACB xuất phát của BT là PATU. Và giá trịtối ưu của hàm mục tiêu đạt được là:f ( x 0 )  5  40  3  25  7  15  5  35   2  35  6  15  2  60  835 10 5 CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 5) Một số ví dụ5.2) Ví dụ 2: Giải bài toán vận tải sau: 11 CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 5) Một số ví dụTrước hết, ta lập PACBXP của BT bằng PP CP bé nhấtvà ta được bảng vận tải như sau: 12 6 CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 5) Một số ví dụTừ bảng VT này, ta có tổng cộng 8 ô chọn không tạo ...