Luận văn Thạc sĩ Toán học: Bài toán vận tải dạng chi phí - nút thắt với nhiều mục tiêu

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:43

Thêm vào BST

Báo xấu

40
lượt xem 7
download

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

Luận văn có mục đích tìm hiểu và trình bày một số mô hình bài toán vận tải nhiều hàm mục tiêu và các thuật toán tìm nghiệm hữu hiệu của bài toán. Mời các bạn tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Bài toán vận tải dạng chi phí - nút thắt với nhiều mục tiêu

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VŨ THU HUỆ BÀI TOÁN VẬN TẢI DẠNG CHI PHÍ NÚT THẮT VỚI NHIỀU MỤC TIÊU LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2015
i Mục lục Danh sách ký hiệu iii Danh sách bảng iv Mở đầu 1 1 Bài toán vận tải theo mục tiêu cước phí 4 1.1 Nội dung bài toán và tính chất . . . . . . . . . . . . . . . . . . . 4 1.2 Phương án cực biên ban đầu . . . . . . . . . . . . . . . . . . . . 7 1.2.1 Phương pháp min cước. . . . . . . . . . . . . . . . . . . 7 1.2.2 Phương pháp góc tây bắc. . . . . . . . . . . . . . . . . . 8 1.3 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Thuật toán thế vị . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2 Bài toán vận tải với hai mục tiêu 14 2.1 Bài toán vận tải theo mục tiêu thời gian . . . . . . . . . . . . . . 14 2.1.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . 14 2.1.2 Thuật toán chắn (Blocking Method). . . . . . . . . . . . 16 2.2 Bài toán vận tải với hai mục tiêu . . . . . . . . . . . . . . . . . . 19 2.2.1 Mô tả bài toán . . . . . . . . . . . . . . . . . . . . . . . 19 2.2.2 Tìm các nghiệm cơ sở hữu hiệu của (MP) . . . . . . . . . 20
ii 3 Bài toán vận tải với ba mục tiêu 25 3.1 Nội dung bài toán . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Tìm tập nghiệm cơ sở hữu hiệu . . . . . . . . . . . . . . . . . . 29 3.3 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Kết luận 36 Tài liệu tham khảo 37
iii Danh sách ký hiệu Trong luận văn này ta dùng những ký hiệu với các ý nghĩa xác định trong bảng dưới đây: x∈D x thuộc tập D x 6∈ D x không thuộc tập D |G(X)| số phần tử của tập G ∪ phép hợp các tập hợp +∞ dương vô cùng P hàm tổng ∆ij được gọi là ước lượng của biến xij τ chỉ thời hạn về thời gian L danh sách ghi nghiệm hữu hiệu tìm được
iv Danh sách bảng Bảng 1.1. Bảng vận tải T Bảng 2.1. Dữ liệu bài toán trong ví dụ 2.2 Bảng 2.2. Bảng vận tải theo mục tiêu thời gian Bảng 2.3. Bảng vận tải theo mục tiêu cước phí Bảng 2.4. Bảng vận tải theo mục tiêu cước phí với τ = 73 Bảng 2.5. Bảng vận tải theo mục tiêu cước phí với τ = 68 Bảng 2.6. Bảng vận tải theo mục tiêu cước phí với τ = 66 Bảng 2.7. Các nghiệm cơ sở hữu hiệu của bài toán vận tải hai mục tiêu Bảng 3.1. Bảng vận tải theo mục tiêu cước phí với τ = 63 Bảng 3.2. Nghiệm cơ sở hữu hiệu S2 kề S1 Bảng 3.3. Bảng vận tải theo mục tiêu cước phí với τ = 66 Bảng 3.4. Tập nghiệm cơ sở hữu hiệu của bài toán trong Ví dụ 3.1
1 Mở đầu Bài toán vận tải theo mục tiêu cước phí (Cost Transportation Problem) là bài . toán cổ điển, quen thuộc trong lý thuyết tối ưu và trong các ứng dụng. Đó là bài toán tìm phương án vận chuyển hàng từ các nơi cung cấp (gọi là điểm phát) đến các nơi tiêu thụ (gọi là điểm thu) sao cho tổng chi phí vận chuyển là nhỏ nhất. Bài toán này đã được nghiên cứu khá chi tiết và đầy đủ, cả về lý thuyết lẫn phương pháp giải. Bài toán vận tải theo mục tiêu thời gian hay còn gọi bài toán vận tải dạng nút thắt (Bottleneck Transportation Problem) là một dạng khác của bài toán vận tải, trong đó có tính đến thời gian đi trên các tuyến đường có vận chuyển hàng. Thay vì tìm cực tiểu tổng chi phí, mục tiêu bây giờ là hoàn thành vận chuyển hàng trong thời gian sớm nhất có thể. Trong bài toán này hàm mục tiêu là phi tuyến. Nhiều dạng khác nhau của bài toán vận tải theo mục tiêu thời gian đã được đặt ra và nhiều thuật toán giải đã được đề xuất. Trong các ứng dụng thực tiễn, để đánh giá hiệu quả hoạt động kinh tế vận tải và đề ra các quyết định quản lý có căn cứ khoa học, người ta còn gặp các mô hình bài toán vận tải với hai hay nhiều hàm mục tiêu. Chẳng hạn, bài toán vận tải cực tiểu cả chi phí lẫn thời gian vận chuyển, gọi là bài toán vận tải dạng chi phí - nút thắt (Bottleneck - Cost Transportation Problem) và bài toán vận tải dạng nút thắt với nhiều mục tiêu, trong đó có hàm mục tiêu phân thức. Đã có một số phương pháp sử dụng cấu trúc đặc thù của bài toán trong tìm nghiệm hữu hiệu của bài toán vận tải hai hay nhiều mục tiêu.
2 Sau khi được học về Giải tích lồi và các kiến thức toán học có liên quan, với mong muốn tìm hiểu sâu hơn về những kiến thức đã học, các kiến thức mở rộng và ứng dụng của những kiến thức này, chúng tôi chọn đề tài luận văn "Bài toán vận tải dạng chi phí - nút thắt với nhiều mục tiêu" Luận văn có mục đích tìm hiểu và trình bày một số mô hình bài toán vận tải nhiều hàm mục tiêu và các thuật toán tìm nghiệm hữu hiệu của bài toán. Luận văn được viết thành ba chương. Chương 1 "Bài toán vận tải theo mục tiêu cước phí" trình bày những kiến thức cơ bản về bài toán vận tải theo mục tiêu cước phí: nội dung và tính chất nghiệm của bài toán, điều kiện tối ưu và thuật toán thế vị giải bài toán. Chương 2 "Bài toán vận tải với hai mục tiêu" đề cập tới bài toán vận tải theo mục tiêu thời gian và bài toán vận tải với hai mục tiêu: cực tiểu cả cước phí lẫn thời gian vận chuyển và trình bày các thuật toán giải, nhờ đưa về các bài toán vận tải theo mục tiêu cước phí. Ý tưởng chính của các thuật toán là sử dụng phương pháp chắn: cấm vận chuyển hàng trên các tuyến có thời gian vượt quá một mức nào đó và sau đó mở rộng dần các mức thời gian này. Chương 3 "Bài toán vận tải với ba mục tiêu" trình bày mô hình bài toán vận tải ba mục tiêu dạng nút thắt, trong đó hai mục tiêu đầu là tỉ số giữa cước phí vận chuyển và thiệt hại do vận chuyển với thời gian vận chuyển. Bài toán này được đưa về dạng bài toán ba mục tiêu đơn giản hơn và có thể giải bằng thuật toán tìm nghiệm cơ sở hữu hiệu của một số bài toán vận tải hai mục tiêu. Do thời gian và kiến thức còn hạn chế nên chắc chắn luận văn này còn có những thiếu sót nhất định, kính mong quí thầy cô và các bạn đóng góp ý kiến để tác giả tiếp tục hoàn thiện luận văn sau này. Nhân dịp này tác giả luận văn xin bày tỏ lòng biết ơn sâu sắc tới GS. TS. Trần Vũ Thiệu, người đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Tác giả trân
3 trọng cảm ơn các giảng viên Trường Đại học Khoa học – Đại học Thái Nguyên, Viện Toán học – Viện Hàn lâm Khoa học và Công nghệ Việt Nam tạo mọi điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu. Thái Nguyên, tháng 05 năm 2015 Tác giả Vũ Thu Huệ
4 Chương 1 Bài toán vận tải theo mục tiêu cước phí Chương này trình bày vắn tắt bài toán vận tải theo mục tiêu cước phí, điều kiện tối ưu và thuật toán thế vị giải bài toán. Cuối chương, nêu ví dụ số minh họa thuật toán giải. Nội dung của chương cần cho các chương ở sau và được tham khảo chủ yếu từ các tài liệu [1], [2] và [3]. 1.1 Nội dung bài toán và tính chất Bài toán vận tải theo mục tiêu cước phí có nội dung như sau: Giả sử có m kho chứa một loại hàng (xi măng chẳng hạn) K1 , . . . , Km (gọi là các điểm phát), kho i = 1, . . . , m có ai > 0 đơn vị hàng (lượng cung). Cần vận chuyển số hàng này tới n hộ tiêu thụ H1 , . . . , Hn (gọi là các điểm thu), hộ j = 1, . . . , n cần bj > 0 đơn vị hàng (lượng cầu). Cước phí vận chuyển một đơn vị hàng từ điểm phát Ki tới điểm thu Hj là cij ≥ 0. Vấn đề đặt ra là cần vận chuyển từ mỗi điểm phát tới mỗi điểm thu bao nhiêu đơn vị hàng sao cho thỏa mãn nhu cầu của mọi điểm thu và tổng chi phí vận chuyển toàn bộ số hàng là nhỏ nhất? Ký hiệu xij là lượng hàng cần vận chuyển từ điểm phát i tới điểm thu j . Khi đó, mô hình toán học của bài toán vận tải theo mục tiêu cước phí có dạng: m X X n f (x) = cij xij → min (cực tiểu tổng chi phí vận chuyển) (1.1) i=1 j=1
5 với các điều kiện n X xij = ai , i = 1, . . . , m (mọi điểm phát giao hết hàng), (1.2) j=1 m X xij = bj , j = 1, . . . , n (mọi điểm thu nhận đủ hàng), (1.3) i=1 xij ≥ 0, i = 1, . . . , m, j = 1, . . . , n (lượng hàng vận chuyển không âm). (1.4) Điều kiện cần và đủ để bài toán (1.1) - (1.4) giải được là phải có điều kiện cân bằng cung cầu (nghĩa là tổng cung bằng tổng cầu): a1 + a2 + · · · + am = b1 + b2 + · · · + bn . (1.5) Ký hiệu A là ma trận hệ số ở vế trái ràng buộc (1.2), (1.3), Aij là véctơ cột của A tương ứng với biến xij . Dễ thấy rằng véctơ này có hai thành phần bằng + 1 (ở hàng thứ i và hàng thứ m + j ), còn mọi thành phần khác bằng 0. Định nghĩa 1.1. Ma trận X = {xij }m×n gọi là một phương án của bài toán vận tải. Phương án đạt cực tiểu của (1.1) gọi là phương án tối ưu hay lời giải của bài toán. Phương án X là phương án cực biên khi và chỉ khi các véctơ cột Aij của A tương ứng với biến xij > 0 là độc lập tuyến tính (hay tập hợp ô {(i, j) : xij > 0} không chứa chu trình). Một phương án cực biên X = {xij }m×n của bài toán gọi là không suy biến nếu số phần tử của tập hợp G(X) = {(i, j) : xij > 0} bằng m + n − 1, gọi là suy biến nếu |G(X)| < m + n − 1. Với điều kiện (1.5) bài toán (1.1) - (1.4) có các tính chất sau: 1. Tập hợp các phương án của bài toán khác rỗng và bị chặn (giới nội). 2. Hạng của hệ ràng buộc (1.2) - (1.3) bằng m + n − 1. 3. Nếu lượng cung ai và lượng cầu bj là các số nguyên thì bài toán sẽ có lời giải nguyên (mọi biến xij có giá trị nguyên).
6 Ta ghi lại dữ liệu của bài toán dưới dạng một bảng chữ nhật, gọi là bảng vận tải (Bảng 1.1). Không kể hàng và cột tiêu đề, bảng bao gồm m hàng (i = 1, . . . , m) và n cột (j = 1, . . . , n). Chỗ giao nhau ở hàng i cột j gọi là ô (i, j). Mỗi hàng tương ứng với một điểm phát, mỗi cột tương ứng với một điểm thu. Số ghi ở đầu mỗi hàng là lượng cung, số ghi ở đầu mỗi cột là lượng cầu. Chi phí vận chuyển cij ghi ở góc trên bên trái của ô (i, j), lượng hàng vận chuyển xij sẽ ghi ở góc dưới bên phải của ô (i, j). Ô (i, j) biểu thị tuyến đường vận chuyển từ điểm phát i tới điểm thu j . Định nghĩa 1.2. Ta gọi dây chuyền là một tập hợp các ô có dạng (i1 , j1 ), (i1 , j2 ), (i2 , j2 ), (i2 , j3 ), . . . , (is , js ), (is , js+1 ) hoặc (i1 , j1 ), (i2 , j1 ), (i2 , j2 ), (i3 , j2 ), . . . , (is , js ), (is+1 , js ). Một dây chuyền khép kín (js+1 = j1 hoặc is+1 = i1 ) gọi là một chu trình. Như vậy, mỗi cặp ô liền nhau trên dây chuyền ở trên cùng một hàng hay trên cùng một cột và số ô trên dây chuyền có thể là chẵn hay lẻ. Một chu trình bao giờ cũng gồm một số chẵn các ô. Ta có mối liên hệ đáng chú ý sau.
7 Định lý 1.1. Hệ véctơ Aij của bài toán vận tải là độc lập tuyến tính khi và chỉ khi các ô tương ứng với các véctơ này không chứa chu trình. Hệ quả 1.1. Ma trận X = (xij )m×n là phương án cực biên của bài toán vận tải khi và chỉ khi tập hợp ô (i, j) mà xij > 0 không chứa chu trình. Định lý 1.2. Giả sử G là một tập hợp gồm m + n − 1 ô của bảng vận tải không chứa chu trình. Khi đó, một ô (r, s) 6∈ G sẽ tạo với các ô thuộc G một chu trình duy nhất. 1.2 Phương án cực biên ban đầu Sau đây là hai phương pháp thông dụng và thuận tiện nhất. 1.2.1 Phương pháp min cước. Trong bảng vận tải, ta chọn ô (p, q) sao cho cpq = min {cij : ∀ (i, j) ∈ T }. Nếu cực tiểu đạt tại nhiều ô thì ta chọn ô bất kỳ trong số các ô đó. Sau đó phân phối hàng nhiều nhất có thể theo tuyến p → q , nghĩa là đặt xpq = min {ap , bq }. Trừ lượng hàng vừa phân phối vào lượng phát, thu của hàng p và cột q . Tiếp đó, ta "xóa" (tức không xét tới nữa) hàng p nếu điểm phát p đã giao hết hàng hoặc cột q nếu điểm thu q đã nhận đủ hàng. Khi cả hàng, cột đều hết và đủ hàng thì chỉ xóa hàng hoặc cột, không xóa cả hai. Trong bảng vận tải còn lại (bớt một hàng hoặc một cột), ta lại chọn ô có cước phí nhỏ nhất và phân phối tối đa lượng hàng còn lại vào ô này (lượng hàng này có thể bằng 0). Phương án X thu được có đúng m + n − 1 ô đã được phân hàng (gọi là ô chọn), nó là một phương án cực biên vì các ô đã chọn không tạo thành chu trình.
8 1.2.2 Phương pháp góc tây bắc. Khác với phương pháp min cước, các ô nằm ở góc tây bắc của bảng vận tải được ưu tiên chọn trước để phân phối hàng, bắt đầu từ ô (p, q) = (1, 1). Phân vào ô này lượng hàng tối đa x11 = min {a1 , b1 }. Có hai khả năng xảy ra: • a1 ≤ b1 (điểm phát 1 hết hàng, điểm thu 1 còn cần b1 − a1 đơn vị hàng). "Xoá" hàng 1 của bảng T. Trong bảng gồm m − 1 hàng còn lại, ta lại chọn ô nằm ở góc tây bắc, cụ thể là ô (2, 1) của bảng T để tiếp tục phân phối hàng. • a1 > b1 (điểm phát 1 còn a1 − b1 đơn vị hàng, điểm thu 1 đủ hàng). "Xoá" cột 1 của bảng T. Trong bảng gồm n − 1 cột còn lại, ta lại chọn ô nằm ở góc tây bắc, cụ thể là ô (1, 2) của bảng T để tiếp tục phân phối hàng. Cứ phân phối hàng như vậy cho đến khi mọi hàng (cột) đã phát hết (nhận đủ) hàng. Khi đó, ta sẽ nhận được một phương án cực biên gồm m + n − 1 ô được phân hàng (gọi là ô chọn), không tạo thành chu trình. 1.3 Điều kiện tối ưu Đối ngẫu của bài toán vận tải (1.1) - (1.4) là bài toán m X n X g(u, v) = ai ui + bj vj → max (1.6) i=1 j=1 với các điều kiện ui + vj ≤ cij , i = 1, . . . , m, j = 1, . . . , n. (1.7) Giả sử X 0 = {x0ij } là một phương án cực biên không suy biến. Ký hiệu G0 = {(i, j) : x0ij > 0}. Sau đây là điều kiện để cho X 0 là phương án tối ưu.
9 Định lý 1.3. Phương án cực biên không suy biến X 0 = {x0ij } của bài toán vận tải (1.1) - (1.4) với điều kiện (1.5) là một phương án tối ưu khi và chỉ khi tìm được các số ui (i = 1, . . . , m) và vj (j = 1, . . . , n) thỏa mãn: ( ui + vj ≤ cij , ∀(i, j) ∈ T, (1.8) ui + vj = cij , ∀(i, j) ∈ G0 . (1.9) Do hệ véctơ {Aij : (i, j) ∈ G0 } độc lập tuyến tính nên mỗi phương án cực biên không suy biến X 0 của bài toán (1.1) - (1.4) sẽ tương ứng với một bộ số ui (i = 1, . . . , m) và vj (j = 1, . . . , n) (xác định sai khác một hằng số khác 0) thỏa mãn (1.9). Ta gọi các số ui và vj này là các thế vị hàng và thế vị cột. Các số ∆ij = ui + vj − cij được gọi là ước lượng của biến xij . Theo Định lý 1.3, phương án X 0 là tối ưu khi và chỉ khi các thế vị này thỏa mãn thêm điều kiện (1.8), tức là ∆ij ≤ 0, ∀ (i, j). Định lý sau đây khẳng định có tồn tại phương án cực biên mới tốt hơn, nếu các thế vị xác định theo (1.9) không thỏa mãn (1.8). Định lý 1.4. Giả sử X 0 = {x0ij } là pương án cực biên không suy biến của bài toán vận tải và ui (i = 1, . . . , m) và vj (j = 1, . . . , n) là các thế vị tương ứng với X 0 . Nếu có ô (r, s) ∈ G0 sao cho ∆rs > 0 thì X 0 không phải là phương án tối ưu và có thể tìm được phương án cực biên mới X 1 tốt hơn X 0 theo nghĩa f (X 1 ) < f (X 0 ). 1.4 Thuật toán thế vị Bước 0. Dùng phương pháp min cước (hay phương pháp góc tây bắc) tìm phương án cực biên ban đầu X 0 = {x0ij } với tập ô chọn G0 gồm đúng m + n − 1 ô không chứa chu trình và G0 = {(i, j) : x0ij > 0}. Đặt chỉ số vòng lặp k = 1. Bước 1. Xác định các thế vị ui (i = 1, . . . , m) và vj (j = 1, . . . , n) tương ứng
10 với X k−1 bằng cách giải hệ phương trình dạng tam giác (1.9): u1 = 0, ui + vj = cij , ∀ (i, j) ∈ Gk−1 . Bước 2. Tính các ước lượng ∆ij = ui + vj − cij , ∀ (i, j) ∈ Gk−1 . (Để ý là ta luôn có ∆ij = ui + vj − cij = 0, ∀ (i, j) ∈ Gk−1 ). Bước 3. Kiểm tra tối ưu: Nếu ∆ij ≤ 0, ∀ (i, j) 6∈ Gk−1 thì dừng thuật toán. Khi đó, X k−1 là phương án tối ưu (Định lý 1.3). Trái lại, chuyển sang Bước 4. Bước 4. Điều chỉnh phương án: 4a) Xác định ô điều chỉnh (r, s) với ∆rs = max {∆ij > 0 : (i, j) ∈ Gk−1 }. 4b) Tìm chu trình duy nhất K trong Gk−1 ∪ {(r, s)}. 4c) Chia các ô thuộc K thành ô lẻ K1 , ô chẵn K2 với qui ước (r, s) ∈ K1 . 4d) Xác định lượng điều chỉnh h = min {xk−1 ij : (i, j) ∈ K2 } = xk−1 pq . 4e) Xây dựng phương án cực biên mới X k với ( xk−1 ij , khi (i, j) 6∈ K, Xijk = k−1 xij + h, khi (i, j) ∈ K1 , xk−1 ij − h, khi (i, j) ∈ K2 . Ta có Gk = Gk−1 \{(p, q)} ∪ {(r, s)} và Gk không chứa chu trình, tức X k là phương án cực biên. 4f) Tăng k ← k + 1, quay lại Bước 1 để thực hiện vòng lặp k mới. Định lý 1.5. Nếu bài toán vận tải không suy biến thì thuật toán thế vị là hữu hạn, tức là sau hữu hạn bước ta sẽ nhận được phương án tối ưu. Chú ý 1.1. Có hai dấu hiệu giúp nhận biết phương án cực biên suy biến:
11 (i) Lượng điều chỉnh h = 0 (Bước 4d). Khi đó ta vẫn thực hiện thuật toán một cách bình thường, nghĩa là ô điều chỉnh (r, s) sẽ trở thành ô chọn của phương án cực biên mới X k và Xrs k k−1 = 0, còn ô (p, q) ∈ K2 ứng với Xpq = 0 sẽ trở thành ô loại đối với phương án X k . Tuy nhiên, kết quả điều chỉnh không làm thay đổi phương án cực biên (X k−1 = X k ) mà chỉ làm thay đổi tập véctơ cơ sở của phương án đó. (ii) Lượng điều chỉnh h đạt tại nhiều ô khác nhau thuộc K2 . Khi đó ta sẽ loại một trong những ô này theo qui tắc ngẫu nhiên. 1.5 Ví dụ minh họa Ví dụ 1.1. Áp dụng thuật toán thế vị giải bài toán vận tải theo mục tiêu cước phí với véctơ cung a, véctơ cầu b và ma trận cước phí C như sau: a = (10 12 8), b = (5 6 4 15),     13 12 14 10 0 0 0 10 0     C= 13 15 12 14 , X = 5 2  0 5.     14 9 7 10 0 4 4 0 Ví dụ này có m = 3 điểm phát, n = 4 điểm thu và thỏa mãn điều kiện cân bằng cung cầu (1.5). Phương án cực biên ban đầu X 0 được tìm theo phương pháp min cước có tập ô chọn G0 = {(1, 4), (2, 1), (2, 2), (2, 4), (3, 2), (3, 3)}, gồm 6 = m + n − 1 ô không chứa chu trình và giá trị mục tiêu f (X 0 ) = 329. Vòng lặp 1. Bước 1. Các thế vị tương ứng với X 0 : u0 = (0 4 − 2), v 0 = (9 11 9 10).
12 Bước 2. Các ước lượng ∆ij = ui + vj − cij ghi trong ma trận ∆0 dưới đây.   −4 −1 −5 0  ∆0 =     0 0 1 0 .   −7 0 0 −2 Bước 3. Phương án X 0 chưa tối ưu vì còn ∆23 = 1 > 0 và (2, 3) 6∈ G0 . Bước 4. Điều chỉnh phương án: 4a) Ô điều chỉnh (r, s) = (2, 3) vì ∆23 = max {∆ij > 0 : (i, j) 6∈ G0 } = 1 > 0. 4b) Chu trình điều chỉnh K gồm 4 ô (2, 3), (3, 3), (3, 2), (2, 2). 4c) Các ô lẻ K1 = {(2, 3), (3, 2)} và các ô chẵn K2 = {(3, 3), (2, 2)}. 4d) Lượng điều chỉnh h = min {x033 = 4, x022 = 2} = x022 = 2. Ô điều chỉnh (p, q) = (2, 2). 4e) Phương án cực biên mới:   0 0 0 10 X1 =    5 0 2 5  .    0 6 2 0 tương ứng với tập ô chọn G1 = {(1, 4), (2, 1), (2, 3), (2, 4), (3, 2), (3, 3)}, gồm 6 ô không chứa chu trình và giá trị mục tiêu f (X 1 ) = 327 < f (X 0 ) = 329. Vòng lặp 2. Bước 1. Các thế vị tương ứng với X 1 : u1 = (0 4 − 1), v 1 = (9 10 8 10).
13 Bước 2. Các ước lượng ∆ij = ui + vj − cij ghi trong ma trận ∆1 dưới đây.   −4 −2 −6 0  ∆1 =     0 −1 0 0.   −6 0 0 −1 Bước 3. Phương án X 1 là tối ưu vì ∆1 ≤ 0. Cước phí vận chuyển nhỏ nhất fmin = 327. Kết thúc thuật toán giải. Tóm lại, chương này đã đề cập tới bài toán vận tải theo mục tiêu cước phí, trình bày điều kiện tối ưu và thuật toán thế vị giải bài toán. Thuật toán thế vị nhắc lại ở chương này sẽ được sử dụng ở các chương sau để giải bài toán vận tải theo mục tiêu thời gian và các bài toán vận tải với hai hay ba mục tiêu.
14 Chương 2 Bài toán vận tải với hai mục tiêu Chương này đề cập tới bài toán vận tải theo mục tiêu thời gian và bài toán vận tải với hai mục tiêu: cực tiểu chi phí lẫn thời gian vận chuyển. Trình bày các thuật toán giải và nêu các ví dụ minh họa thuật toán. Nội dung của chương được xây dựng dựa trên các tài liệu tham khảo [4], [5] và [6]. 2.1 Bài toán vận tải theo mục tiêu thời gian 2.1.1 Phát biểu bài toán Trong việc lập kế hoạch vận tải, yếu tố thời gian đôi khi cũng cần được tính đến. Chẳng hạn, khi cần vận chuyển nhanh chóng một mặt hàng nào đó (hoa quả, rau tươi, thịt cá ...) từ nơi sản xuất đến nơi tiêu thụ hay khi cần tiếp tế gấp lương thực, vũ khí, đạn dược ... từ hậu phương ra tiền tuyến thì mục tiêu cực tiểu thời gian vận chuyển thường được đặt lên hàng đầu. Mục này xét mô hình bài toán vận tải theo mục tiêu thời gian như sau: (P ) tX = max {tij : xij > 0} → min (2.1) i,j với các điều kiện n X xij = ai , i = 1, . . . , m, (2.2) j=1 m X xij = bj , j = 1, . . . , n, (2.3) i=1 xij ≥ 0, i = 1, . . . , m, j = 1, . . . , n. (2.4)
15 trong đó m là số điểm phát, n là số điểm thu, xij là lượg hàng cần chuyển từ điểm phát i tới điểm thu j , tij là thời gian đi từ điểm phát i tới điểm thu j , ai là lượng cung của điểm phát i và bj là lượng cầu của điểm thu j . Ta giả thiết (P) thỏa mãn điều kiện cân bằng cung cầu: m X n X ai = bj . (2.5) i=1 j=1 Một số tác giả nước ngoài gọi mô hình (2.1) - (2.5) là bài toán vận tải dạng nút thắt (Bottleneck Transportation Problem - viết tắt là BTP). Cũng như trong bài toán vận tải theo mục tiêu cước phí xét ở chương 1, hệ thống số {xij }m×n thỏa mãn (2.2) - (2.4) được gọi là một phương án của (P ). Phương án đạt cực tiểu của (2.1) được gọi là một phương án tối ưu của (P ). Trong bài toán vận tải theo mục tiêu thời gian, ma trận thời gian T = [tij ]m×n được cho trước. Thời gian vận chuyển của mỗi phương án X = {xij }m×n được hiểu theo nghĩa như sau. Định nghĩa 2.1. Thời gian vận chuyển tX của phương án X là giá trị lớn nhất của các số tij trên các tuyến (i, j) có vận chuyển hàng, tức xij > 0 (không phụ thuộc độ lớn xij ), nghĩa là thời gian của tuyến đường (từ một điểm phát tới một điểm thu) dài nhất mà trên tuyến đường đó có vận chuyển hàng. Dễ dàng kiểm tra tính đúng đắn của nhận xét sau. Bổ đề 2.1. Thời gian vận chuyển tối thiểu của mọi phương án X là số tmin xác định bởi tmin = max { max min tij , max min tij }, (2.6) 1≤i≤m 1≤j≤n 1≤j≤n 1≤i≤m (tức tmin bằng số lớn nhất trong các số nhỏ nhất ở mỗi hàng và mỗi cột của T).