Tài liệu môn Toán học - Chương 3: Bài toán vận tải

ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 1 Ths. Nguyễn Công Trí Copyright 2001 Ths. Nguyễn Công Trí Copyright 2001 BÀI TOÁN VẬN TẢI 1. BÀI TOÁN VẬN TẢI DẠNG TỔNG QUÁT (Xem) 2. CÁC TÍNH CHẤT VÀ TIÊU CHUẨN TỐI ƯU CỦA BÀI TOÁ VẬN TẢI (Xem) 3. CÁC PHƯƠNG PHÁP TÌM PHƯƠNG ÁN CỰC BIÊN ĐẦU TIÊN CỦA BÀI TOÁN VẬN TẢI (Xem) 4. THUẬT GIẢI THẾ VỊ CHO BÀI TOÁN VẬN TẢI (Xem) 5. CÁC DẠNG KHÁC CỦA BÀI TOÁN VẬN TẢI (Xem) 6. BÀI TẬP (Xem) CHƯƠNG 3 BÀI TOÁN VẬN TẢI DẠNG TỔNG QUÁT NỘI DUNG BÀI TOÁN VẬN TẢI Giả sử cần vận chuyển một loại hàng hóa (xi măng, sắt thép, ...) từ m điểm cung cấp (trạm phát), ký hiệu là A1, A2, ..., Am đến n điểm tiêu thụ (trạm thu), ký hiệu là B1, B2, ..., Bn, biết rằng (1) Số lượng hàng có ở các trạm phát A1, A2, ..., Am lần lượt là a1, a2,..., am (2) Số lượng hàng cần ở các trạm thu B1, B2, ..., Bn lần lượt là b1, b2,..., bn. (3) Chi phí vận chuyển một đơn vị hàng hóa từ trạm phát Ai đến trạm thu Bj là cij. Hãy lập kế hoạch vận tải hàng hóa sao cho tổng chi phí vận tải thấp nhất và thỏa mãn yêu cầu thu – phát. BÀI TOÁN VẬN TẢI DẠNG TỔNG QUÁT MÔ HÌNH BÀI TOÁN VẬN TẢI Đặt xij là số lượng hàng cần vận chuyển từ trạm phát Ai đến trạm thu Bj. Ta có tổng chi phí vận tải: (1) Trạm phát, phát hết hàng: (2) Trạm thu, thu đủ hàng: (3) Yêu cầu trạm phát, trạm thu được thỏa (đk cân bằng thu – phát). 1 1 min     m n ij ij i j Z c x 1 , 1,    n ij i j x a i m 1 , 1,    m ij j i x b j n 1 1    m n i j i j a b BÀI TOÁN VẬN TẢI DẠNG TỔNG QUÁT Vậy, mô hình toán của bài toán vận tải (BTVT) dạng tổng quát như sau: Tìm {xij} sao cho: 1 1 1 1 1 1 min , 1, , 1, 0; 0; 0; 0; m n ij ij i j n ij i j m ij j i m n ij ij i j i j i j Z c x x a i m x b j n x c a b a b                       ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 2 BÀI TOÁN VẬN TẢI DẠNG TỔNG QUÁT BÀI TOÁN VẬN TẢI DƯỚI DẠNG BÀI TOÁN QHTT khai triển BTVT và xếp hệ ràng buộc dưới dạng hệ m + n phương trình của m n biến như sau Ký hiệu Am+n,mn ma trận hệ số của hpt trên. XT = (x11 x12 ...x1n x21 x22 ... x2n ... xm1 xm2... xmn) là vectơ cột gồm mn thành phần; C = (c11 c12 ...c1n c21 c22 ... c2n cm1 cm2 ...cmn) là vectơ dòng gồm mn thành phần; bT = (a1 a2 ...am b1 b2 ...bn) là vectơ cột gồm m+ n thành phần. 11 12 1 1 21 22 2 2 1 2 11 21 1 1 12 22 2 2 1 2 n n m m mn m m m n n mn n x x x a x x x a x x x a x x x b x x x b x x x b                                 BÀI TOÁN VẬN TẢI DẠNG TỔNG QUÁT BTVT viết dưới dạng vectơ và ma trận như sau  Một vectơ X thỏa (*) và (**) gọi là phương án. Một P.A đạt cực tiểu thì gọi là P.A.T.Ư của BTVT. Một phương án X được gọi là P.A.C.B khi các vectơ cột Aj của ma trận hệ số A ứng với các thành phần xij > 0 là độc lập tuyến tính.  Một P.A.C.B của BTVT có nhiều nhất là m + n – 1 thành phần dương. Nếu một P.A.C.B của BTVT có đúng m + n – 1 thành phần dương thì được gọi là không suy biến. Ngược lại, được gọi là phương án cực biên suy biến.     min * 0 ** Tz C X AX b X        B1 B2  Bn Trạïm thu Bj Trạïm pháùt Ai b1 b2  bn A1 c11 c12  c1n a1 x11 x12  x1n A2 c21 c22  c2n a2 x21 x22  x2n           Am cm1 cm2  cmn am xm1 xm2  xmn MÔ TẢ BÀI TOÁN DƯỚI DẠNG BẢNG VẬN TẢI (1) Ký hiệu (i, j) là ô trên dòng i và cột j. (2) Chi phí vận chuyển cij được ghi ở góc trên bên trái của ô (i, j), lượng hàng cần vận chuyển xij được ghi ở góc dưới bên phải của ô (i, j) biểu diễn tuyến đường vận chuyển từ trạm phát Ai đến trạm thu Bj. (3) Trong BẢNG VẬN TẢI, một ô được gọi là ô treo nếu nó là ô duy nhất trên dòng hay trên cột. (4) Những ô ứng với xij > 0 trong BẢNG VẬN TẢI được gọi là ô chọn, những ô khác gọi là ô loại. (5) Một dãy các ô chọn, trong đó 3 ô liên tiếp không nằm trên cùng một dòng hay một cột thì được gọi là một dây chuyền. MÔ TẢ BÀI TOÁN DƯỚI DẠNG BẢNG VẬN TẢI ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 3 (6) Một dây chuyền khép kín được gọi là một chu trình hay một vòng. (7) Một ma trận (xij) là một P.A của BTVT nếu nó thoả hệ ràng buộc. Một P.A (xij) làm cực tiểu hàm mục tiêu thì (xij) là P.A.T.Ư. của bài toán. (8) Một P.A của BTVT không tạo thành chu trình (vòng) thì được gọi là Phương án cực biên. (9) Một P.A.C.B của BTVT có đủ m+n-1 ô chọn thì được gọi là P.A.C.B không suy biến, nếu có ít hơn m+n-1 ô chọn được gọi là P.A.C.B suy biến. MÔ TẢ BÀI TOÁN DƯỚI DẠNG BẢNG VẬN TẢI VÍ DỤ 3.1. Hình 2.1. Hình 2.2. Hình 2.3. Hình 2.4. Hình 2.5.  Hình 2.1. các ô chọn, có dấu “”, tạo thành dây chuyền, các ô (1,1) và (4,3) là các ô treo.  Hình 2.2. các ô chọn tạo thành dây chuyền, các ô (4,1) và (3,3) là các ô treo.  Hình 2.3., Hình 2.4 và Hình 2.5. các ô chọn tạo thành chu trình, không có ô treo. MÔ TẢ BÀI TOÁN DƯỚI DẠNG BẢNG VẬN TẢI                             CÁC TÍNH CHẤT CỦA BÀI TOÁN VẬN TẢI TÍNH CHẤT 1: Bài toán vận tải luôn luôn có phương án tối ưu. TÍNH CHẤT 2: Với một phương án bất kỳ, số ô chọn của phương án không vượt quá tổng số trạm phát và trạm thu.  ≤ m + n –1 (với  là số ô chọn của P.A) TÍNH CHẤT 3: Với một phương án có đủ m+n–1 ô chọn thì với một ô loại bất kỳ được đưa vào phương án sẽ tạo thành chu trình và chu trình này là duy nhất. TÍNH CHẤT 4: Nếu lượng cung ai và lượng cầu bj là số nguyên thì bài toán có lời giải nguyên. TIÊU CHUẨN TỐI ƯU CỦA BÀI TOÁN VẬN TẢI Xét bài toán vận tải sau 1 1 min     m n ij ij i j Z c x 1 1 , 1, , 1,         n ij i j m ij j i x a i m x b j n 1 1 0; 0; 0; 0;ij ij i j m n i j i j x c a b a b         Viết lại bài toán 1 1 min     m n ij ij i j Z c x 1 1 , 1, , 1, m ij j i n ij i j x b j n x a i m           1 1 0; 0; 0; 0;ij ij i j m n i j i j x c a b a b         ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 4 TIÊU CHUẨN TỐI ƯU CỦA BÀI TOÁN VẬN TẢI Bài toán đối ngẫu của BTVT Tìm {ui,vj} sao cho: Với các cặp đối ngẫu: xij  0 và vj – ui ≤ cij, i,j Theo định lý độ lệch bù thì phương án {xij} của BTVT có P.A.T.Ư là tồn tại hệ thống {ui, vj} sao cho: Nếu xij > 0 thì vj – ui = cij, Nếu vj – ui < cij thì xij = 0. Vậy tiêu chuẩn tối ưu của BTVT: vj – ui  cij, i,j ui: được gọi là thế vị dòng. vj: được gọi là thế vị cột. * 1 1 max n m j j i i j i Z b v a u       PHƯƠNG PHÁP CHI PHÍ BÉ NHẤT Trên bảng vận tải, chọn ô đầu tiên có cước phí vận chuyển bé nhất và chọn xij như sau: Lặp lại quá trình trên cho ô tiếp theo cho đến đến khi yêu cầu trạm phát và trạm thu được thoả mãn. Bảng thu được với các xij > 0 là phương án cực biên của bài toán.  in ,m j i i j i j b a a b a b           i j j i i j ij a : loại dòng i, b b : loại cột j, a a b : loại dòng i và cột j x PHƯƠNG PHÁP CHI PHÍ BÉ NHẤT Ví dụ 3.2. Dùng phương pháp chi phí bé nhất, tìm phương án cực biên của bài toán vận tải có dạng bảng sau đây Kiểm tra ai = bj = 175 T P 30 40 25 35 45 42 13 8 7 2 13 28 5 1 10 5 11 45 16 5 3 7 16 60 6 3 4 14 10 28 35 25 1230 18 7 20 PHƯƠNG PHÁP CHI PHÍ BÉ NHẤT P.A.C.B trên không suy biến, với giá trị Z = 980. T P 30 40 25 35 45 42 13 8 7 2 13 28 5 1 10 5 11 45 16 5 3 7 16 60 6 3 4 14 10 ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 5 PHƯƠNG PHÁP VOGELS Phương pháp Vogels (1958) cho P.A.C.B khá tốt theo nghĩa giá trị hàm mục tiêu của nó khá gần với P.A.T.Ư. Phương pháp được mô tả như sau (1) Trên bảng vận tải, tính hiệu số giữa chi phí bé thứ hai với chi phí bé thứ nhất. (2) Chọn số lớn nhất trong các hiệu trên và phân phối tối đa cho ô có chi phí bé nhất một lượng xij = min(ai, bj), sau đó tính lại hiệu số dòng (cột). (3) Quá trình trên được lặp lại cho đến khi chỉ còn lại một dòng hay một cột duy nhất. (4) Bảng thu được với các {xij} là phương án cực biên của bài toán. PHƯƠNG PHÁP VOGELS Ví dụ 3.3: Dùng phương pháp Vogels, tìm phương án cực biên của bài toán vận tải có dạng bảng sau Kiểm tra ai = bj = 175 T P 30 40 25 35 45 42 13 8 7 2 13 28 5 1 10 5 11 45 16 5 3 7 16 60 6 3 4 14 10 5 35 4 2 1 1 2 1 3 1 K ,1 28 K 7 3 30 K 30 K 3 4 25 K ,11 ,5 12 K 8 K 7 K K PHƯƠNG PHÁP VOGELS Z = 932 T P 30 40 25 35 45 42 13 8 7 2 13 28 5 1 10 5 11 45 16 5 3 7 16 60 6 3 4 14 10 HƯỚNG GIẢI BÀI TOÁN (1) Tìm P.A.C.B không suy biến đầu tiên bằng phương pháp chi phí bé nhất hoặc Vogels. (2) Dùng tiêu chuẩn tối ưu vi – uj ≤ cij, i,j để kiểm tra P.A.C.B vừa tìm được. (3) Nếu P.A.C.B thoả mãn tiêu chuẩn tối ưu thì P.A.C.B đó là P.A.T.Ư. (4) Nếu P.A.C.B vừa tìm chưa thoả mãn tiêu chuẩn tối ưu thì tìm cách sửa đổi P.A.C.B cũ để có P.A.C.B mới. (5) trở về bước (2), sau một số bước lặp hữu hạn, ta sẽ có P.A.T.Ư. Phương pháp trên gọi là thuật toán thế vị ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 6 không Có không Suy biến? XÁC ĐỊNH P.A.C.B ĐẦU TIÊN (phương pháp chi phí bé nhất hoặc Vogels) Chọn ô vào: Maxij Xác định vòng điều chỉnh và đánh dấu (+); dấu (–). q = min{xij/ (i, j) dấu (–)} Có Thêm ô xij=0 Kết thúc thuật giải Bài toán có P.A.T.Ư LẬP BẢNG VẬN TẢI Tính: Vj = Ui + Cij Ui = Vj – Cij Xác định P.A mới ij  0? ij ij ij x q dấu ( ). x q dấu ( ). x không dấu.           ijx SƠ ĐỒ THUẬT GIẢI THẾ VỊ CỦA BÀI TOÁN VẬN TẢI SỐ BƯỚC LẶP LÀ HỮU HẠN THUẬT TOÁN THẾ VỊ Bước 1. Lập bảng vận tải (1) Kiểm tra điều kiện cân bằng thu – phát. (2) Xác định P.A.C.B (bằng phương pháp chi phí bé nhất). (3) Kiểm tra P.A.C.B có suy biến hay không  Nếu P.A.C.B. suy biến: thêm vào ô (i,j) bất kỳ với xij = 0, không tạo thành chu trình.  Nếu P.A.C.B không suy biến, chuyển sang [2] Bước 2. Kiểm tra tính tối ưu của bài toán (1) Tính vj = ui + cij ui = vj – cij, trong đó ô (i,j) là ô chọn. THUẬT TOÁN THẾ VỊ Chọn ui = 0 tại dòng bất kỳ. (2) Đặt ij = vj – ui – cij  Nếu ij ≤ 0: ta có P.A.T.Ư.  Nếu ij > 0: chuyển sang [3] Bước 3. Xác định vòng điều chỉnh (1) Chọn ô vào: Maxij (ij > 0) (2) Chọn ô ra  xác định vòng điều chỉnh  ô vào sẽ được đánh dấu (+). Xen kẻ dấu (-) và dấu (+) trên vòng điều chỉnh.  lượng điều chỉnh q = min{xij/ (i,j) có dấu (-)} THUẬT TOÁN THẾ VỊ Bước 4. Xác định P.A.C.B mới Quay về bước [2]. Sau một số bước lặp hữu hạn, bài toán có phương án tối ưu. ijx           ij ij ij x q dấu ( ); x q dấu ( ); x không dấu. ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 7 THUẬT TOÁN THẾ VỊ CHÚ Ý. (1) Trong thuật giải bài toán vận tải, nếu Maxij đạt tại nhiều ô, ta chọn một ô tùy ý trong số các ô đó làm ô điều chỉnh. (2) Trong P.A.T.Ư tìm được Xopt, nếu có ij = 0, mà (i,j) là ô loại thì đó là dấu hiệu bài toán có nhiều P.A.T.Ư khác. Để tìm P.A.C.B.T.Ư khác, ta chọn ô (i, j) đó làm ô điều chỉnh, rồi áp dụng thuật toán thế vị để xác định P.A.C.B.T.Ư khác X/opt. (3) Tập phương án tối ưu là X = {Xopt + (1 – )X / opt, 0, 1} THUẬT TOÁN THẾ VỊ Ví dụ 3.4. Giải bài toán vận tải Kiểm tra điều kiện cân bằng thu phát ai = 40 + 75 + 60 + 70 + 45 = 290 bj = 45 + 55 + 30 + 70 + 50 + 40 = 290 T P 45 55 30 70 50 40 40 12 8 9 10 7 6 75 12 13 10 11 13 9 60 3 9 5 6 7 1 70 9 8 2 7 6 2 45 11 9 6 10 10 8 40 30 20 40 1030 25 20 5025 0 78 1 3 -1 9 -2 10 7 8 +2 +1 +1 +5 +1 + -+ - + -+ - + - q= 20 Bảng 1 T P 45 55 30 70 50 40 40 12 8 9 10 7 6 75 12 13 10 11 13 9 60 3 9 5 6 7 1 70 9 8 2 7 6 2 45 11 9 6 10 10 8 10 30 705 2040 30 20 20 45 0 78 1 3 -1 4 -7 5 2 3 +2 +1 +1+ - + - + -+ - q= 5 Bảng 2 T P 45 55 30 70 50 40 40 12 8 9 10 7 6 75 12 13 10 11 13 9 60 3 9 5 6 7 1 70 9 8 2 7 6 2 45 11 9 6 10 10 8 ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 8 5 35 5 70 45 15 30 15 25 45 0 62 2 1 4 -1 7 -6 5 -2 Bảng 3 T P 45 55 30 70 50 40 40 12 8 9 10 7 6 75 12 13 10 11 13 9 60 3 9 5 6 7 1 70 9 8 2 7 6 2 45 11 9 6 10 10 8 THUẬT TOÁN THẾ VỊ •Do các ij  0 i,j nên P.A.T.Ư của bài toán là Và Zmin = 1.875 đơn vị tiền tệ. Ngoài ra, bài toán không có P.A.T.Ư khác vì không có ij = 0, với (i, j) là ô loại 0 5 0 0 35 0 0 5 0 70 0 0 45 0 0 0 0 15 0 0 30 0 15 25 0 45 0 0 0 0                  optx THUẬT TOÁN THẾ VỊ Ví dụ 3.5. Giải bài toán vận tải Kiểm tra điều kiện cân bằng thu phát ai = 79 + 102 + 70 + 60 = 311 bj = 76 + 62 + 88 + 45 + 40 = 311 T P 76 62 88 45 40 79 10 19 15 6 7 102 13 11 8 7 4 70 12 17 10 5 3 60 12 18 18 10 9 + -+ -+ - + - q=30 Bảng 1 4030 15 88 64 14 12 48 0 10 6 -2 16 5 13 1 4 +2 T P 76 62 88 45 40 79 10 19 15 6 7 102 13 11 8 7 4 70 12 17 10 5 3 60 12 18 18 10 9 ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 9 Bảng 2 4030 45 58 34 44 42 18 0 10 6 -2 16 5 13 3 6 T P 76 62 88 45 40 79 10 19 15 6 7 102 13 11 8 7 4 70 12 17 10 5 3 60 12 18 18 10 9 THUẬT GIẢI THẾ VỊ •Do các ij  0 i,j nên P.A.T.Ư của bài toán vận tải Và Zmin = 2.806 đơn vị tiền tệ. Bài toán không có P.A.T.Ư nào khác vì không có ij = 0, với (i, j) là ô loại. 34 0 0 45 0 0 44 58 0 0 0 0 30 0 40 42 18 0 0 0             optx CÁC DẠNG KHÁC CỦA BÀI TOÁN VẬN TẢI 1. BÀI TOÁN VẬN TẢI KHÔNG CÂN BẰNG THU – PHÁT (Xem) 2. BÀI TOÁN VẬN TẢI CÓ DẠNG HÀM MỤC TIÊU LÀ MAX (Xem) 3. BÀI TOÁN VẬN TẢI CÓ Ô CẤM (Xem) 4. BÀI TOÁN VẬN TẢI XE KHÔNG (Xem) BÀI TOÁN VẬN TẢI KHÔNG CÂN BẰNG THU-PHÁT 1. TRƯỜNG HỢP 1. ai > bj  Thêm trạm thu giả thứ Bn+1  Với nhu cầu thu bn+1 = ai – bj  Cước phí vận tải ci,n+1 = 0, i = 1, 2, ..., m. 2. TRƯỜNG HỢP 2. ai < bj  Thêm trạm phát giả thứ Am+1  Với nhu cầu phát am+1 = bj – ai  Cước phí vận tải cm+1,j = 0, j = 1, 2, ..., n. Với các ô có cước phí vận tải bằng không được gọi là ô giả. Lưu ý khi dùng thuật toán thế vị để giải bài toán trên, với P.A.C.B đầu tiên, ta ưu tiên phân phối vào các ô thực. ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 10 BÀI TOÁN VẬN TẢI KHÔNG CÂN BẰNG THU-PHÁT Ví dụ 3.6. Giải bài toán vận tải sau Kiểm tra điều kiện cân bằng thu – phát ai= 165 < bj= 190 Thêm một trạm phát giả A4, với a4 = 190 – 165 = 25 và c4j = 0, j=1, 2, 3, 4 T P 65 45 50 30 60 10 9 12 7 55 9 11 10 15 50 8 7 14 12 T P 65 45 50 30 60 10 9 12 7 55 9 11 10 15 50 8 7 14 12 25 0 0 0 0 + -+ - 5 25 30 55 5 45 25 0 1 2 12 10 9 12 7 +1 q = 25 Bảng 1 + - + - q = 30 Có P.A.T.Ư khác Bảng 2 30 25 30 30 5 45 25 0 1 2 11 10 9 11 7 0 T P 65 45 50 30 60 10 9 12 7 55 9 11 10 15 50 8 7 14 12 25 0 0 0 0 BÀI TOÁN VẬN TẢI KHÔNG CÂN BẰNG THU-PHÁT •Phương án cực biên tối ưu của bài toán vận tải là •và Zmin = 1.385 30 0 0 30 30 0 25 0 5 45 0 0 optx            ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 11 T P 65 45 50 30 60 10 9 12 7 55 9 11 10 15 50 8 7 14 12 25 0 0 0 0 30 25 30 30 35 15 25 0 1 2 11 10 9 11 7 BÀI TOÁN VẬN TẢI KHÔNG CÂN BẰNG THU-PHÁT •P.A.C.B.T.Ư khác của bài toán •Và Z’min =1.385 •Tập P.A.T.Ư của bài toán •Zopt = Xopt + (1 – ) X / opt •Hay            0 30 0 30 30 0 25 0 35 15 0 0 optx                30 30 30 0 30 30 0 25 0 35 30 15 30 0 0 optZ MÔ HÌNH BÀI TOÁN VẬN TẢI CÓ HÀM MỤC TIÊU LÀ MAX Tìm {xij} sao cho: 1 1 1 1 1 1 max , 1, , 1, 0; 0; 0; 0; 1, ; 1, . m n ij ij i j n ij i j m ij j i m n ij ij i j i j i j Z c x x a i m x b j n x c a b a b i m j n                         THUẬT GIẢI BÀI TOÁN VẬN TẢI CÓ HÀM MỤC TIÊU LÀ MAX Giống như bài toán QHTT có hàm mục tiêu là max, chúng ta có thể đưa bài toán vận tải có hàm mục tiêu Z  max về Z/ = – Z  min, sau đó dùng thuật toán thế vị để giải. Tuy nhiên, chúng ta cũng có thể giải trực tiếp bài toán này bằng thuật toán thế vị với một vài thay đổi trong thuật giải như sau: 1. Khi xây dựng P.A.C.B đầu tiên, ta phân phối tối đa vào ô có cước phí lớn nhất. 2.Tiêu chuẩn tối ưu là vj – ui  cij, i,j 3.Ô điều chỉnh là ô có {minij, với ij < 0} ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 12 THUẬT GIẢI THẾ VỊ VỚI HÀM MỤC TIÊU Z  Max Ví dụ 3.7. Một công ty có 3 xí nghiệp cùng sản xuất một loại bóng đèn. Năng suất trong tháng của 3 xí nghiệp lần lượt là Ai = (650, 1.000, 350) bóng. Hợp đồng công ty phải giao cho 4 nhà phân phối là Bj = (200, 400, 600, 800) bóng. Đơn giá bán của mỗi bóng đèn tương ứng với các nhà phân phối được cho bởi ma trận sau: Đvt: 1.000 đồng Hãy tìm kế hoạch phân phối hàng sao cho công ty đạt doanh số lớn nhất 22 25 20 18 30 32 25 28 29 28 25 23           ijc T P 200 400 600 800 650 22 25 20 18 1000 30 32 25 28 350 29 28 25 23 THUẬT GIẢI THẾ VỊ VỚI HÀM MỤC TIÊU Z  Max 250 200 400 400 400 350 0 283230 5 30 10 -2 -3 -4 -1+ – + – +– q = 200 T P 200 400 600 800 650 22 25 20 18 1000 30 32 25 28 350 29 28 25 23 THUẬT GIẢI THẾ VỊ VỚI HÀM MỤC TIÊU Z  Max 450 200 400 600 200 150 0 283234 5 30 10 -3 -1 + – +– q = 200 T P 200 400 600 800 650 22 25 20 18 1000 30 32 25 28 350 29 28 25 23 THUẬT GIẢI THẾ VỊ VỚI HÀM MỤC TIÊU Z  Max 450 200 200 800 200 150 0 283231 2 27 7 Z = 52.350 ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 13 THUẬT GIẢI BÀI TOÁN VẬN TẢI CÓ HÀM MỤC TIÊU LÀ MAX •Do các ij  0, i, j •P.A.T.Ư CỦA BÀI TOÁN •Và ZMax = 52.350 0 200 450 0 0 200 0 800 200 0 150 0 optx            BÀI TOÁN VẬN TẢI CÓ Ô CẤM Bài toán vận tải có ô cấm là bài toán vận tải với P.A.T.Ư của nó phải thỏa điều kiện cho trước. Để giải bài toán này, ta lập bài toán vận tải mở rộng VTM bằng cách cho giá cước vận chuyển ở các ô cấm bằng M, với M > 0 lớn tùy ý rồi dùng thuật toán thế vị. Có 2 trường hợp xảy ra 1.Trong P.A.T.Ư của bài toán VTM, nếu các ô cấm có xij = 0 thì P.A.T.Ư của bài toán VTM cũng chính là P.A.T.Ư của bài toán gốc. 2.Trong P.A.T.Ư của bài toán VTM, nếu các ô cấm có xij  0 thì bài toán gốc không có P.A.T.Ư. BÀI TOÁN VẬN TẢI CÓ Ô CẤM Ví dụ 3.8. Giải bài toán vận tải sau đây với Nhu cầu trạm phát a = (150, 100, 145, 100) Nhu cầu trạm thu b = (140, 150, 180) Ma trận cước vận chuyển với điều kiện trạm A3, A4 phải phát hết hàng.  Kiểm tra điều kiện cân bằng thu – phát ai = 150 + 100 + 145 + 100 = 495 bj = 140 + 150 + 180 = 470  Lập trạm thu giả, với b4= 25 và M > 0 tùy ý. 5 4 6 8 5 9 11 6 12 9 7 13             ijc T P 140 150 180 25 150 5 4 6 0 100 8 5 9 0 145 11 6 12 M 100 9 7 13 M + –+ – 0 150 100 145 40 35 25 +3 M-4 +2 +3 M-1 +1 +1 4 1 1 0 9 8 13 M q = 25 Bảng 1 ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 14 T P 140 150 180 25 150 5 4 6 0 100 8 5 9 0 145 11 6 12 M 100 9 7 13 M + + – – +3 +2 +3 +1 +1 q = 35 Bảng 2 0 150 75 25 145 65 35 4 1 1 0 9 8 13 1 T P 140 150 180 25 150 5 4 6 0 100 8 5 9 0 145 11 6 12 M 100 9 7 13 M + – +– + – +2 +4 +1 q = 40 Bảng 3 0 150 40 25 145 100 35 3 0 -3 -1 8 7 9 0 T P 140 150 180 25 150 5 4 6 0 100 8 5 9 0 145 11 6 12 M 100 9 7 13 M – + + – +4 +1 +1 +1 q =105 Bảng 4 40 110 40 25 105 100 75 0 1 -2 -4 5 4 10 1 T P 140 150 180 25 150 5 4 6 0 100 8 5 9 0 145 11 6 12 M 100 9 7 13 M +2 +1 + – + – q = 5 Bảng 5 40 5 145 25 100 75 105 0 -3 -2 -4 5 4 6 -3 ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 15 T P 140 150 180 25 150 5 4 6 0 100 8 5 9 0 145 11 6 12 M 100 9 7 13 M Bảng 6 40 5 145 25 100 70 110 3 0 -1 -1 8 5 9 0 Z =3.285 0+ – + – q = 40P.A.T.Ư khác BÀI TOÁN VẬN TẢI CÓ Ô CẤM •Do các ij  0 i,j nên •P.A.C.B.T.Ư của bài toán vận tải trên là •và Zmin= 3.285 40 0 110 0 5 70 0 145 0 100 0 0             optx T P 140 150 180 25 150 5 4 6 0 100 8 5 9 0 145 11 6 12 M 100 9 7 13 M Bảng 7 40 5 145 25 100 30 150 3 0 -1 -1 8 5 9 0 Z =3.285 0 BÀI TOÁN VẬN TẢI CÓ Ô CẤM •P.A.C.B.T.Ư khác của bài toán vận tải trên là •và Zmin= 3.285 •Tập phương án tối ưu •Zopt = Xopt + (1 – ) X / opt •Hay 0 0 150 40 5 30 0 145 0 100 0 0 optx              40 0 150 40 40 40 5 30 40 0 145 0 100 0 0 op tZ                  ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 16 MÔ HÌNH BÀI TOÁN VẬN TẢI XE KHÔNG  Điều kiện ràng buộc của bài toán vận tải xe không là một số trạm phát Ai phải phát đủ hàng cho trạm Bj (được chỉ định). Xác định lộ trình xe chạy không tải từ Bj đến Ai là ít nhất.  Khi đó trạm phát Ai trở thành trạm thu xe không, trạm thu Bj trở thành trạm phát xe không và khi đó ma trận (cij) là ma trận khoảng cách tương ứng giữa Ai và Bj. Qui ước sử dụng các ký hiệu như sau:  : lượng hàng hóa có vận tải.  : lượng hàng của xe không tải.  : tuyến xe chạy có tải.  : tuyến xe chạy không tải ijx xij THUẬT GIẢI BÀI TOÁN XE KHÔNG TẢI 1. Lập bảng vận tải tương ứng với ma trận khoảng cách. Dùng thuật toán thế vị tìm P.A.T.Ư của bài toán xe không tải. 2. Tạo bảng phối hợp P.A.T.Ư của bài toán xe không tải với kế hoạch vận tải đã cho trước. Lập tuyến điều động tương ứng. 3. Giảm lượng chênh lệch giữa “ô tròn” và “ô vuông” để có bảng mới thu gọn. 4. Lập vòng điều động gồm các ô có tải và ô không tải liên tiếp nhau, lượng điều động q= min{xij}, với xij có tải và xij không tải. Trở về [3]. Sau một số bước lặp hữu hạn [3] và [4], ta sẽ thu được kế hoạch điều động hàng hóa tối ưu. Ví dụ 3.9. Một công ty vận tải có kế hoạch vận chuyển hàng hóa theo hợp đồng, được thể hiện qua bảng yêu cầu như sau THUẬT GIẢI BÀI TOÁN XE KHÔNG TẢI Địa điểm cấp hàng Ai Loại hàng Lượng (tấn) Nơi nhận hàng Bj Ký hiệu A1 Cam 20 Công ty rau quả B2 30 Cửa hàng số 3 B3 A2 Dưa hấu 25 Cửa hàng số 1 B1 15 Công ty rau quả B2 10 Cửa hàng số 3 B3 A3 Sầu riêng 50 Cửa hàng số 4 B4 20 Công ty rau quả B2 Cho biết khoảng cách giữa địa điểm cung cấp hàng và địa điểm nhận hàng (km) được thể hiện qua ma trận như sau: Hãy xác định lộ trình vận chuyển hàng hóa thỏa yêu cầu hợp đồng và tổng tấn – km xe chạy không tải nhỏ nhất. THUẬT GIẢI BÀI TOÁN XE KHÔNG TẢI            5243 4625 3412 L ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 17 Bj Ai 25 55 40 50 50 2 1 4 3 50 5 2 6 4 70 3 4 2 5 Bước 1 (tìm P.A.T.Ư của bài toán xe không tải) Zmin= 420 tấn – km 50 5 40 2 1 0 3 3 2 5 Bảng 1 45 25 5 Bước 2 (tạo bảng phối hợp) A1 B2 A1: 20 T X 1km = 20T – km A2 B2 A2: 5 T X 2km = 10T – km A3 B4 A3: 5 T X 5km = 25T – km Bj Ai 25 55 40 50 50 2 1 4 3 50 5 2 6 4 70 3 4 2 5 50 5 40 Bảng 2 45 25 5 20 30 25 15 10 5020 1km 2km 5km Bước 3 (lập tuyến điều động) A2 B1 A3 B2 A1 B3 A3 B4 A2:20Tx10km=200T-km Bj Ai 25 55 40 50 50 2 1 4 3 50 5 2 6 4 70 3 4 2 5 30 40 Bảng 3 45 25 30 25 10 10 4520 q=20 3km 1km 2km 4km Bước 3 (lập tuyến điều động) A2 B1 A3 B4 A2: 5T x 7km = 35T–km. Bj Ai 25 55 40 50 50 2 1 4 3 50 5 2 6 4 70 3 4 2 5 10 20 Bảng 4 25 5 10 5 10 10 25 q=5 3km 4km ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 18 Bước 3 (lập tuyến điều động) A2 B2 A1 B3 A3 B4 A2: 10T x 7km = 70T–km Bj Ai 25 55 40 50 50 2 1 4 3 50 5 2 6 4 70 3 4 2 5 10 20 Bảng 5 20 10 10 10 20 q=101km 2km 4km Bước 3 (lập tuyến điều động) A2 B3 A3 B4 A2 : 10 T x 6km = 60T–km Bj Ai 25 55 40 50 50 2 1 4 3 50 5 2 6 4 70 3 4 2 5 10 Bảng 6 10 10 10 q=10 2km 4km BẢNG ĐIỀU ĐỘNG XE A1 B2 A1: 20 T A2 B2 A2: 5 T A3 B4 A3: 5 T A2 B1 A3 B2 A1 B3 A3 B4 A2: 20 T A2 B1 A3 B4 A2: 5 T A2 B2 A1 B3 A3 B4 A2: 10 T A2 B3 A3 B4 A2: 10 T THUẬT GIẢI BÀI TOÁN XE KHÔNG TẢI 1km 2km 5km 3km 1km 2km 4km 3km 4km 1km 2km 4km 2km 4km Ths. Nguyễn Công Trí Copyright 2001 BÀI TẬP CHƯƠNG 3 LẬP MÔ HÌNH CỦA BÀI TOÁN VẬN TẢI [1] [2] TÌM PHƯƠNG ÁN CỰC BIÊN ĐẦU TIÊN [3a] [3b] [3c*] [3d] [3e] GIẢI BÀI TOÁN VẬN TẢI CÂN BẰNG THU - PHÁT [4] [5] [6] [7] [8] [9] CÁC DẠNG KHÁC CỦA BÀI TOÁN VẬN TẢI [10a] [10b] [10c] [11a] [11b] [11c] [11d] ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 19 BÀI TẬP CHƯƠNG 3 1. Một công ty vận tải biển cần 110 người để bố trí vào các nhiệm vụ: 10 máy trưởng; 25 thợ máy 1; 30 thợ máy 2; 45 thợ máy 3. Phòng tổ chức nhân sự tuyển được 90 người, trong đó gồm 25 kỹ sư máy; 20 kỹ thuật viên trung cấp và 45 công nhân có kinh nghiệm. Hãy bố trí nhân lực sao cho công việc tối ưu. Nhiệm vụ Trình độ Điểm đánh giá năng lực (aij) Máy trưởng Máy 1 Máy 2 Máy 3 Kỹ sư 5 4 0 0 Trung cấp 3 5 4 0 Công nhân 0 1 5 4 BÀI TẬP CHƯƠNG 3 Gọi xij là số lao động trình độ i (i = kỹ sư, trung cấp, công nhân) được bố trí vào nhiệm vụ j (j = máy trưởng, máy 1, máy 2, máy 3). 11 12 21 22 23 32 33 34 11 12 13 14 21 22 23 24 31 32 33 34 11 21 31 12 22 32 13 23 33 14 24 34 5 4 3 5 4 5 4 max 25 20 45 10 25 30 45 0, 1,3, 1,4ij z x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x i j                                     BÀI TẬP CHƯƠNG 3 2. Hai đội tuyển bóng bàn, mỗi đội có 5 người. Qua thống kê nhiều trận đấu trong quá khứ, người ta dự đoán xác suất thắng cuộc mỗi đấu thủ của mỗi đội được thể hiện qua bảng sau Hãy sắp xếp các đấu thủ của đội I sao cho xác suất thắng toàn đoàn của đội I cao nhất. Đội II Đội I Đấu Thủ 1 Đấu Thủ 2 Đấu Thủ 3 Đấu thủ 4 Đấu Thủ 5 Đấu thủ 1 0,4 0,5 0,6 0,7 0,8 Đấu thủ 2 0 0,3 0,4 0,4 0,7 Đấu thủ 3 0,2 0,6 0,4 0,3 0,5 Đấu thủ 4 0,6 0,3 0,4 0,7 0,6 Đấu thủ 5 0 0,2 0,3 0,4 0,6 BÀI TẬP CHƯƠNG 3 Gọi xij là đấu thủ i của đội I được xếp thi đấu với đấu thủ j của đội II (i, j = 1, 2, ..., 5). 11 12 13 14 15 22 23 24 25 31 32 33 34 35 41 42 43 44 45 52 53 54 55 5 1 5 1 0, 4 0,5 0,6 0,7 0,8 0,3 0,4 0,4 0,7 0,2 0,6 0,4 0,3 0,5 0,6 0,3 0,4 0,7 0,6 0,2 0,3 0,4 0,6 max 1, 1,5 1, 1,5 ij j ij i ij z x x x x x x x x x x x x x x x x x x x x x x x x i x j x                                0,1 , 1,5i j  ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 20 BÀI TẬP CHƯƠNG 3 3.a) Tìm phương án cực biên bằng hai phương pháp chi phí bé nhất và phương pháp Vogels Kiểm tra điều kiện cân bằng thu phát ai = 40 + 20 + 30 = 90 bj = 20 + 25 + 30 + 15 = 90 Bj Ai 20 25 30 15 40 4 5 1 2 20 3 4 7 8 30 2 6 9 3 BÀI TẬP CHƯƠNG 3 3.b) Tìm phương án cực biên bằng hai phương pháp chi phí bé nhất và phương pháp Vogels Bj Ai 3 5 10 14 10 1 3 7 1 15 2 4 2 3 7 6 5 4 1 BÀI TẬP CHƯƠNG 3 3.c*) Tìm phương án cực biên bằng hai phương pháp chi phí bé nhất và phương pháp Vogels Kiểm tra điều kiện cân bằng thu phát ai = 25 + 10 + 45 = 80 bj = 10 + 30 + 50 = 90 Thêm trạm phát giả thứ 4, với a4 = bj - ai = 10, c4j = 0, j = 1, 2, 3. Bj Ai 10 30 50 25 7 6 5 10 2 1 4 45 3 5 2 BÀI TẬP CHƯƠNG 3 3.d) Tìm phương án cực biên bằng hai phương pháp chi phí bé nhất và phương pháp Vogels Bj Ai 40 30 20 50 30 3 7 4 6 40 4 6 2 5 70 1 5 7 8 ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 21 BÀI TẬP CHƯƠNG 3 3.e) Tìm phương án cực biên bằng hai phương pháp chi phí bé nhất và phương pháp Vogels Bj Ai 30 20 25 35 40 30 13 7 6 2 12 20 5 1 10 5 11 40 10 5 3 7 14 60 6 3 2 11 10 BÀI TẬP CHƯƠNG 3 4. Giải bài tập [3], với a)Phương án cực biên đầu tiên thu được bằng phương pháp chi phí bé nhất, b)Phương án cực biên đầu tiên thu được bằng phương pháp Vogels. BÀI TẬP CHƯƠNG 3 5. a) Giải bài toán vận tải b) Bài toán có phương án tối ưu khác hay không? Nếu có, chỉ ra phương án tối ưu đó. Bj Ai 50 160 120 80 220 5 4 3 10 100 5 9 7 12 90 10 6 8 15 BÀI TẬP CHƯƠNG 3 6. a) Giải bài toán vận tải b) Bài toán có phương án tối ưu khác hay không? Nếu có, chỉ ra tập phương án tối ưu. Bj Ai 20 100 45 15 90 10 6 4 1 40 3 4 2 5 50 9 4 3 7 ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 22 BÀI TẬP CHƯƠNG 3 7. Cho bài toán vận tải có dạng a) Tìm P.A.T.Ư của bài toán trên. b) Theo bạn dấu hiệu nào cho ta biết BTVT có nhiều P.A.T.Ư? P.A.C.B.T.Ư tìm được ở câu a) có duy nhất không? Nếu có, hãy chỉ ra P.A.C.B.T.Ư khác? c) Tìm tập các P.A.T.Ư và chỉ ra 3 P.A.T.Ư?   20, 110, 120ia   70,40,30,60,50jb 4 2 5 7 6 5 8 3 4 5 2 1 4 3 2 ijc            BÀI TẬP CHƯƠNG 3 8. Cho bài toán vận tải có dạng a) Tìm P.A.T.Ư của bài toán trên. b) Phương án tối ưu vừa tìm được có duy nhất không? (có giải thích). Chỉ ra một phương án tối ưu khác? (nếu có).   38, 45, 66, 45ia   52, 45, 38, 59jb             9 5 6 14 10 7 9 15 10 10 6 7 4 8 13 14 ijc BÀI TẬP CHƯƠNG 3 9. Giải bài tập [1], [2]. BÀI TẬP CHƯƠNG 3 10. a) Giải bài toán vận tải sau đây và tìm phương án tối ưu khác (nếu có). Bj Ai 60 60 80 100 80 4 5 6 12 70 10 3 9 5 100 6 4 7 9 ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 23 BÀI TẬP CHƯƠNG 3 10. b) Giải bài toán vận tải sau đây và tìm phương án tối ưu khác (nếu có). Trạm phát Trạm thu Ma trận cước phí vận tải   100, 20, 30, 50ia   70, 60, 25, 50jb             10 14 24 8 30 20 18 14 2 12 6 7 8 16 14 36 ijc BÀI TẬP CHƯƠNG 3 10. c) Giải bài toán vận tải sau đây và tìm phương án tối ưu khác (nếu có). Trạm phát Trạm thu Ma trận cước phí vận tải   79, 50, 60, 50ia   46, 45, 76, 20, 52jb             10 1 5 13 8 5 6 10 8 13 3 2 8 9 6 13 5 7 10 13 ijc BÀI TẬP CHƯƠNG 3 11. a) Giải bài toán vận tải có ô cấm sau đây và tìm phương án tối ưu khác (nếu có). Trạm phát Trạm thu Ma trận cước phí vận tải Điều kiện A3 phải phát hết hàng.   90, 40, 50ia   20, 100, 45jb            10 6 4 3 4 2 9 4 3 ijc BÀI TẬP CHƯƠNG 3 11. b) Giải bài toán vận tải có ô cấm sau đây và tìm phương án tối ưu khác (nếu có). Trạm phát Trạm thu Ma trận cước phí vận tải Điều kiện B2 phải thu đủ hàng.   100, 80, 50ia   65, 90, 50, 30jb            10 9 12 7 9 11 10 15 8 7 14 12 ijc ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 3 24 BÀI TẬP CHƯƠNG 3 11. c) Giải bài toán vận tải có ô cấm sau đây và tìm phương án tối ưu khác (nếu có). Trạm phát Trạm thu Ma trận cước phí vận tải Điều kiện trạm phát A3 không được phát cho trạm thu B2.   220, 100, 90ia   50, 160, 120, 80jb            5 4 3 10 5 9 7 12 10 6 8 15 ijc BÀI TẬP CHƯƠNG 3 11. d) Giải bài toán vận tải có ô cấm sau đây và tìm phương án tối ưu khác (nếu có). Trạm phát Trạm thu Ma trận cước phí vận tải Điều kiện trạm thu B2 không được thu của trạm phát A1.   90, 40, 50ia   20, 100, 45jb            10 6 4 3 4 2 9 4 3 ijc