Tài liệu Khắc phục hiện tượng suy biến trong bài toán vận tải (2)

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRỊNH XUÂN BÁCH KHẮC PHỤC HIỆN TƯỢNG SUY BIẾN TRONG BÀI TOÁN VẬN TẢI Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60.46.01.12 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: GS.TS. TRẦN VŨ THIỆU THÁI NGUYÊN - NĂM 2013 1Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn i Mục lục Mục lục i Lời cảm ơn ii Mở đầu 1 1 Bài toán vận tải tuyến tính 4 1.1 Bài toán và tính chất . . . . . . . . . . . . . . . . . . . . . 4 1.2 Phương pháp tìm phương án cực biên ban đầu . . . . . . . 9 1.2.1 Phương pháp min cước . . . . . . . . . . . . . . . . 9 1.2.2 Phương pháp góc tây bắc . . . . . . . . . . . . . . . 11 1.3 Tiêu chuẩn tối ưu . . . . . . . . . . . . . . . . . . . . . . . 13 1.4 Thuật toán thế vị . . . . . . . . . . . . . . . . . . . . . . . 14 1.5 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . 17 2 Bài toán vận tải suy biến và cách khắc phục 20 2.1 Thế nào là suy biến . . . . . . . . . . . . . . . . . . . . . . 20 2.2 Ví dụ xoay vòng . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3 Bài toán nhiễu . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.4 Cách khắc phục xoay vòng . . . . . . . . . . . . . . . . . . 32 2.5 Ví dụ minh họa tránh xoay vòng . . . . . . . . . . . . . . . 33 Kết luận. 42 Tài liệu tham khảo 43 2Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ii Lời cảm ơn Trong suốt quá trình làm luận văn, tôi luôn nhận được sự hướng dẫn và giúp đỡ của GS.TS Trần Vũ Thiệu (Viện Hàn lâm Khoa học và Công nghệ Việt Nam). Tôi xin chân thành bày tỏ lòng biết ơn sâu sắc đến thầy. Tôi xin cảm ơn quý thầy, cô giảng dạy lớp cao học khóa 5 (2011 − 2013) đã mang đến cho tôi nhiều kiến thức bổ ích trong khoa học và cuộc sống. Mặc dù đã có nhiều cố gắng nhưng luận văn khó tránh khỏi những thiếu sót. Tác giả mong nhận được những ý kiến đóng góp của quý thầy, cô và bạn đọc để luận văn được hoàn thiện hơn. Xin trân trọng cảm ơn! Hải Phòng, tháng 01 năm 2013. Người viết Luận văn Trịnh Xuân Bách 3Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 Mở đầu Tối ưu hoá (Optimization) là một môn toán học ứng dụng đã và đang được nghiên cứu, giảng dạy và học tập ở rất nhiều trường đại học, cao đẳng trong nước cho sinh viên các ngành toán học, tin học, kinh tế và kĩ thuật. Trong các bài toán tối ưu thì quan trọng nhất và đáng chú ý nhất là các bài toán tối ưu tuyến tính. Qui hoạch tuyến tính là bài toán tối ưu đơn giản nhất, được ứng dụng rộng rãi nhất trong nhiều lĩnh vực khác nhau của kinh tế, đời sống và quốc phòng. Chính vì vậy đây cũng là bài toán được nghiên cứu đầy đủ và hoàn chỉnh nhất, cả về mặt lí thuyết và tính toán, cũng đã có nhiều sách và giáo trình viết về vấn đề này, ở đây tôi xin trình bày một phần nhỏ của bài toán tối ưu. Bài toán vận tải (Transportation Problem) của qui hoạch tuyến tính là bài toán tối ưu được ứng dụng rộng rãi trong thực tiễn. Trong bài toán này hàm mục tiêu là tuyến tính (nghĩa là chi phí vận chuyển tỉ lê thuận với lượng hàng vận chuyển) và các ràng buộc của bài toán có dạng đặc biệt. Nhờ khai thác cấu trúc đặc biệt này, người ta đã đề ra các phương pháp riêng, hiệu quả hơn hẳn so với việc áp dụng phương pháp đơn hình tổng quát vào bài toán. Đáng chú ý là phương pháp thế vị (xem [1]), phương pháp qui không chọn ô (xem [2] ), phương pháp thu hẹp chính tắc,... Mô hình toán học của bài toán vận tải có dạng một bài toán qui hoạch tuyến tính chính tắc:  min cT x : Ax = b, x ≥ 0 với A ∈ Rm×n , b ∈ Rm , c ∈ Rn cho trước. Ta thường giả thiết rank (A) = m và m ≤ n. Với bài toán này, các phương án cực biên (còn gọi là lời giải cơ sở) thường hay "suy biến", tức là có số thành phần dương nhỏ hơn 4Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 m. Suy biến có thể dẫn đến hiện tượng xoay vòng, khi giải bài toán theo thuật toán đơn hình, hậu quả là quá trình giải không thể kết thúc. Để tránh gặp xoay vòng, người ta đã đề ra nhiều biện pháp khắc phục khác nhau. Chẳng hạn, khi giải qui hoạch tuyến tính theo thuật toán đơn hình người ta thường áp dụng qui tắc từ vựng, qui tắc Wolfe, qui tắc Bland hay qui tắc cột phụ Srishna, ... (xem[3]). Bài toán vận tải tuyến tính có dạng một qui hoạch tuyến tính chính tắc, vì thế nó cũng thường gặp hiện tượng suy biến và do đó nguy cơ xoay vòng cũng có thể xảy ra, khi giải bài toán theo qui luật thế vị. Mặc dù thực tế giải bài toán cho thấy xoay vòng trong bài toán vận tải rất hiếm khi xảy ra. Tuy nhiên, về lý thuyết nghiên cứu hiện tượng xoay vòng và tìm cách khắc phục nó là một việc làm cần thiết và có ích. Đối với bài toán vận tải vấn đề khắc phục suy biến và xoay vòng đơn giản hơn nhiều so với bài toán qui hoạch tuyến tính tổng quát. Luận văn này nhằm mục đích tìm hiểu và giới thiệu nội dung và phương pháp giải bài toán vận tải với hàm mục tiêu tuyến tính: nêu mô hình và các tính chất cơ bản của bài toán, giới thiệu thuật toán thế vị giải bài toán. Vấn đề đối ngẫu và quan hệ đối ngẫu trong bài toán vận tải cũng được đề cập tới. Luận văn còn đề cập tới bài toán vận tải suy biến, hiện tượng xoay vòng và phương pháp khắc phục xoay vòng trong bài toán vận tải. Luận văn bao gồm lời nói đầu, hai chương, kết luận và danh mục tài liệu tham khảo: Chương 1 với tiêu đề "Bài toán vận tải tuyến tính" trình bày nội dung và các tính chất cơ bản của bài toán vận tải tuyến tính. Tiếp đó, đề cập tới phương pháp tìm phương án cực biên ban đầu của bài toán. Sau đó, trình bày cơ sở lý luận và nội dung thuật toán thế vị (một biến thể của thuật toán đơn hình) giải bài toán vận tải. Cuối chương, nêu ra ví dụ số để minh họa cho thuật toán giải đã trình bày. Chương 2 với tiêu đề "Bài toán vận tải suy biến và cách khắc phục" trình bày bài toán vận tải suy biến và ví dụ dẫn đến xoay vòng trong bài toán vận tải. Sau đó, để khắc phục xoay vòng ta xét bài toán nhiễu, tức là bài toán với số liệu đầu vào thay đổi đôi chút so với các số liệu ban đầu. 5Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 Chứng minh mọi phương án cực biên trong bài toán nhiễu đều không suy biến, do đó không xảy ra hiện tượng xoay vòng khi giải nó theo thuật toán thế vị. 6Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 Chương 1 Bài toán vận tải tuyến tính Chương này đề cập tới bài toán vận tải tuyến tính (chi phí vận chuyển tỉ lệ thuận với lượng hàng vận chuyển), đó là dạng bài toán qui hoạch tuyến tính đơn giản nhất và được ứng dụng rộng rãi nhất trong thực tiễn. Phần đầu của chương trình bày nội dung và các tính chất cơ bản của bài toán. Tiếp đó đề cập tới phương pháp tìm phương án cực biên ban đầu của bài toán. Sau đó trình bày cơ sở lý luận và nội dung thuật toán thế vị (một biến thể của thuật toán đơn hình) giải bài toán vận tải. Cuối chương nêu ví dụ số minh họa cho thuật toán giải. Nội dung của chương được tham khảo chủ yếu từ các tài liệu [1], [2] và [3]. 1.1 Bài toán và tính chất Bài toán vận tải 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. 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. 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 . 7Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 Khi đó mô hình toán học của bài toán vận tải có dạng như sau: f (x) = m X n X cij xij → min (cực tiểu tổng chi phí vận chuyển) (1.1) i=1 j=1 với các điều kiện n X xij = ai , i = 1, 2, ..., m (mọi điểm phát giao hết hàng), (1.2) xij = bj , j = 1, 2, ..., n (1.3) j=1 m X (mọi điểm thu nhận đủ hàng), i=1 xij ≥ 0, i = 1, ..., m, j = 1, ..., n (lượng hàng vận chuyển không âm). (1.4) Ở đây, m là số kho chứa hàng (điểm phát), n là số nơi tiêu thụ hàng (điểm thu), ai là lượng hàng có (cung) ở điểm phát i (i = 1, 2, ..., m), bj là lượng hàng cần (cầu) ở điểm thu j (j = 1, 2, ...n), cij là chi phí vận chuyển một đơn vị hàng từ điểm phát i tới điểm thu j, xij biểu thị lượng hàng vận chuyển cần tìm từ điểm phát i tới điểm thu j. Đ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 thu phát, nghĩa là tổng cung bằng tổng cầu: α1 + a2 + ... + am = b1 + b2 + ... + bn . (1.5) Bài toán vận tải (1.1)-(1.4) là một dạng đặc biệt của qui hoạch tuyến tính. Để thấy rõ điều này ta sắp xếp các biến số theo thứ tự x11 , x12 , ..., x1n , x21 , x22 , ..., x2n , ..., xm1 , xm2 , ..., xmn và viết lại hệ ràng buộc chính (1.2)-(1.3) dưới dạng hệ m + n phương trình 8Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 của m × n biến số xij như sau:  x11 + ... + x1n    x21 + ... + x2n      x11    x12     ...  x1n ...... = a1 = a2 xm1 + ... + xmn = am +x21 ...... +x11 = b1 +x22 ...... = b2 ... ...... ... ... +x21 ...... + xmn = bn Ký hiệu A là ma trận hệ số của hệ phương trình trên (m + n hàng và m × n cột ), x = (x11 , ..., x1n , x21 , ..., x2n , ..., xm1 , ..., xmn )T -véctơ cột m×n thành phần, c = (c11 , ..., c1n , x21 , ..., c2n , ..., cm1 , ..., cmn )T -véctơ cột m × n thành phần, b = (a1 , a2 , ..., am , b1 , b2 , ..., bn )T -véctơ cột vế phải (m + n thành phần). Bài toán vận tải (1.1)-(1.4) được viết lại thành bài toán qui hoạch tuyến tính dạng chính tắc: f = hc, xi → min, (1.6) Ax = b, x ≥ 0. (1.7) Ta gọi Aij là véctơ cột của ma trận A tương ứng với biến xij . Dễ thấy véctơ này có hai thành phần bằng 1 tại dòng thứ i và dòng thứ m + j , còn các thành phần khác bằng 0. Véctơ x thỏa mãn (1.2)-(1.4) gọi là một phương án của bài toán vận tải. Một phương án đạt cực tiểu (1.1) gọi là phương án tối ưu hay lời giải. 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 ma trận A tương ứng với các xij > 0 là độc lập tuyến tính. Sau đây ta sẽ giả thiết điều kiện cân bằng thu phát (1.5). Do bài toán vận tải có m + n ràng buộc chính, nên ta nghĩ rằng mỗi phương án cực biên cũng có m + n thành phần dương, nhưng thực tế nó chỉ có nhiều nhất m + n − 1 thành phần dương, vì trong số các ràng buộc này có một ràng buộc là thừa (có thể bỏ đi mà không làm ảnh hưởng tới lời giải của bài toán). Một phương án cực biê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 = {(j; j) : xij > 0} bằng m+n−1, gọi là suy biến nếu số phần tử của tập hợp G nhỏ hơn m + n − 1. 9Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 Với điều kiện (1.5) bài toán vận tải (1.1)-(1.4) có các tính chất sau đây: 1. Bài toán luôn có phương án và tập hợp các phương án của bài toán là giới nội. 2. Một trong các ràng buộc (1.2)-(1.3) là thừa và hạng của hệ ràng buộc này bằng m + n − 1. 3. Nếu các lượng cung và cầu ai , bj là các số nguyên thì bài toán sẽ có lời giải nguyên. Có thể dùng các phương pháp của qui hoạch tuyến tính để giải bài toán vận tải. Tuy nhiên do bài toán này có dạng đặc biệt nên người ta đã đề ra nhiều thuật toán giải hiệu quả. Một trong số đó là thuật toán thế vị. Thuật toán này được ta xem xét ở phần sau. Thông thường khi giải bài toán vận tải 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). Bảng 1.1. Bảng vận tải Hình 1.1: Trong đó c = (c11 , ..., c1n , x21 , ..., c2n , ..., cm1 , ..., cmn )T là véctơ hệ số mục tiêu của bài toán vận tải. Bảng gồm m hàng (i = 1, 2, ..., m) và n cột j = (1, 2, ..., n). Chỗ giao nhau ở hàng i, cột j kí hiệu là ô (i; j). Mỗi 10Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 hàng tương ứng với một trạm phát, mỗi cột tương ứng với một trạ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) biểu thị tuyến đường vận chuyển từ trạm phát i đến trạm thu j . (Đặt cij = ∞ nếu không thể chuyển hàng từ i đến j ). Định nghĩa 1.1. Ta gọi dây chuyền là 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 trong dây chuyền ở trên cùng một hàng hay cùng một cột, và số ô trên mỗi dây chuyền có thể chẵn hay lẻ. Một chu trình bao giờ cũng gồm một số chẵn các ô. Ví dụ 1.1. Chu trình. Hình 1.2: Ta có một số định lý và hệ quả quan trọng sau. Đị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 tạo thành chu trình. 11Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 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ử T là một tập hợp gồm m + n − 1 ô của bảng vận tải, không tạo thành chu trình. Khi đó, mỗi ô (p; q) ∈ / T sẽ tạo với các ô thuộc T một chu trình duy nhất. 1.2 Phương pháp tìm phương án cực biên ban đầu Để giải bài toán vận tải (1.1)-(1.4) với điều kiện (1.5) theo phương pháp thế vị, trước hết ta cần biết một phương án cực biên không suy biến của bài toán. Có nhiều cách để tìm một phương án như thế. Sau đây là hai phương pháp thông dụng và có hiệu quả nhất, thường được sử dụng để tìm phương án cực biên ban đầu cho bài toán vận tải thỏa mãn điều kiện cân bằng thu phát. 1.2.1 Phương pháp min cước Trong bảng vận tải (Bảng 1.1), ta chọn ô (p; q) sao cho cpq = min {cij : ∀(i; j)}. Nếu cực tiểu đạt tại nhiều ô thì ta chọn một ô 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át vào khả năng thu, phát của hàng p và cột q . Tiếp đó, ta xóa hàng p nếu điểm phát p đã 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 đồng thời cả hai. Trong bảng còn lại, ta lại tìm ô 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 này có thể bằng 0). Phương án x thu được có đúng m + n − 1 ô đã phân hàng, 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. Ví dụ 1.2. Tìm phương án cực biên của bài toán vận tải. 12Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 Bài toán: "Cần vận chuyển xi măng từ 3 kho K1 , K2 , K3 tới 4 công trường xây dựng T1 , T2 , T3 , T4 . Cho biết lượng xi măng có ở mỗi kho, lượng xi măng cần ở mỗi công trường va giá cước vận chuyển (ngàn đồng) một tấn xi măng từ mỗi kho tới mỗi công trường như sau: Bảng 1.2. Vấn đề là tìm kế hoạch vận chuyển xi măng từ các kho tới các công trường sao cho mọi kho phát hết lượng xi măng có, mọi công trường nhận đủ lượng xi măng cần và tổng chi phí vận chuyển là nhỏ nhất?" Cước phí nhỏ nhất trong bảng là 15 đạt tại hai ô (2; 1) và (2; 4). Ta chọn ô thứ nhất và phân vào ô này lượng hàng x21 = min {200, 130} = 130. Cột 1 đã nhận đủ hàng nên bị loại (không phân hàng vào ô đó nữa). Hàng 2 chỉ còn lại lượng phát a02 = 200 − 130 = 70. Trong bảng còn lại (ba cột cuối), ta chọn ô (2; 4) có cước phí nhỏ nhất (bằng 15) và phân vào ô này lượng hàng x24 = min {70, 140} = 70. Lúc này hàng 2 đã hết hàng nên bị loại. Cột 4 còn thiếu lượng hàng b04 = 140 − 70 = 70. Trong bảng còn lại (ba cột cuối hàng 1 và 3), ta chọn ô có cước phí nhỏ nhất (bằng 18) và phân vào ô này lượng hàng x12 = min {170, 160} = 160. Cột 2 đã nhận đủ hàng nên bị loại. Hàng 1 còn lại lượng phát a01 = 170 − 160 = 10. 13Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11 Tiếp đó, ta phân vào ô (1; 3) lượng hàng x13 = min {10, 120} = 10. Đến đây hàng 1 cũng hết hàng, chỉ có hàng 3 là còn hàng. Cuối cùng, ta phân vào hai ô cuối của hàng này lượng hàng x13 = 120 − 10 = 110 và x34 = 180 − 110 = 70. Đến đây mọi hàng (cột) đã phát hết (nhận đủ) hàng, ta đặt xij = 0 đối với mọi ô (i, j) còn lại. Kết quả ta nhận được phương án cực biên cho ở bảng (1.2). Giá trị hàm mục tiêu tương ứng bằng 12950. Sau này ta sẽ thấy giá trị cực tiểu fmin = 12140. 1.2.2 Phương pháp góc tây bắc Trước hết ta lập bảng vận tải T với các số liệu ai , bj , cij , i = 1, ..., m, j = 1, ..., n. Bắt đầu từ ô ở vị trí góc tây bắc của bảng vận tải T (ô (1; 1)), ta điền lượng hàng x11 lớn nhất có thể vào đó, tức là chuyển một lượng hàng lớn nhất có thể từ điểm xuất phát 1 đến điểm thu 1. Dễ thấy x11 = min {a1 , b1 } . Có một trong ba khả năng sau có thể xảy ra: • If x11 = a1 < b1 Then (điểm phát 1 đã hết hàng, điểm thu 1 còn cần b1 − a1 đơn vị hàng) Xóa hàng thứ nhất của bảng T ta thu được bảng T 0 gồm (m − 1) hàng và n cột với lượng phát, thu tương ứng: a0i = ai i = 2, 3, ..., m, b01 = b1 − x11 = b1 − a1 ; b0j = bj j = 2, 3, ..., n; • If x11 = b1 < a1 Then (điểm phát 1 còn dư a1 − b1 đơn vị hàng, điểm thu 1 đã thỏa mãn nhu cầu) Xóa cột thứ nhất của bảng T ta thu được bảng T 0 gồm m hàng và (n − 1) cột với lượng phát, thu tương ứng: a01 = a1 − x11 = a1 − b1 ; a0i = ai i = 2, 3, ..., m, b0j = bj j = 2, 3, ..., n, 14Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 12 • If x11 = b1 = a1 Then (điểm phát 1 đã hết hàng, điểm thu 1 đã thỏa mãn nhu cầu ) Ta quy ước chỉ xóa cột thứ nhất của bảng T ta thu được bảng T 0 gồm m hàng và (n − 1) cột với lượng phát, thu tương ứng: a01 = 0 a01 = ai i = 2, 3, ..., m, b0j = bj , j = 2, 3, .., n; Đối với bảng T 0 , ta lại thực hiện thủ tục chuyển hàng như đã áp dụng đối với bảng T : Bắt đầu từ ô ở góc tây bắc của bảng T 0 , xác định khối lượng vận chuyển lớn nhất có thể (khối lượng hàng có thể bằng 0) từ điểm phát đến điểm thu tương ứng, tức điền lượng hàng vận chuyển lớn nhất có thể vào ô này... Cứ tiếp tụ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 phương án cực biên gồm m + n − 1 ô được chọn, không tạo thành chu trình. Những ô (i; j) không được phân phối hàng có xij = 0. Ví dụ 1.3. Xét bài toán vận tải với véctơ lượng phát a, lượng thu b và ma trận chi phí C như sau a = (50, 70, 80)T , b = (60, 30, 40, 70)T ,    2 4 5 1 50 0 0 0   0   , x =  10 30 30 0 3 6 4 8 C=    1 2 5 3 0     0 10 70 Kết quả tìm phương án cực biên ban đầu x0 theo phương pháp góc tây bắc được trình bày ở bảng trên. Các thành phần dương của phương án x0 được ghi vào góc dưới bên phải mỗi ô tương ứng(các thành phần bằng 0 bỏ qua không ghi). Trình tự phân phối hàng theo chiều mũi tên (đường nét đứt). Ta thấy rằng, phương án x0 này chính là phương án cực biên của bài toán. Nhận xét 1.1. Theo phương pháp góc tây bắc, sau mỗi lần phân phối hàng, ta sẽ xóa đi được 1 hàng (hoặc 1 cột) của bảng. Do đó, đúng sau m + n − 1 lần phân phối thủ tục trên phải kết thúc (do ở lần cuối ta xóa 15Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 13 được cả hàng lẫn cột) và phương án xây dựng theo phương pháp góc tây bắc sẽ có không quá m + n − 1 thành phần dương. 1.3 Tiêu chuẩn tối ưu Đối ngẫu của bài toán vận tải ban đầu (bài toán (1.1)-(1.4)) là g(y) = m X ai ui + i=1 n X bj vj → max (1.8) j=1 với điều kiện ui + vj ≤ cij , i = 1, ..., m, j = 1, ..., n, (1.9) trong đó y = (u1 , ..., um , v1 , ..., vn )T . Để đơn giản việc trình bày, giả sử rằng bài toán vận tải ban đầu là không suy biến, tức các phương án cực biên của nó đều không suy biến. Cách nhận biết và khắc phục khi gặp phương án cực biên suy biến sẽ được trình bày chi tiết trong phần bên dưới đây.
 Cho phương án x0 . Như thường lệ, kí hiệu G x0 = (i; j) ∈ T |x0ij > 0 . Sau đây là điều kiện cần và đủ để phương án x = (x0ij ) là phương án tối ưu. Định lí 1.3. Phương án x0 = (x0ij ) của bài toán vận tải là phương án tối ưu khi và chỉ khi tồn tại các số ui , i = 1, ..., m và vj , j = 1, ..., n thỏa mãn đồng thời ui + vj ≤ cij , ∀(i; j) ∈ T (1.10) .ui + vj = cij , ∀(i; j) ∈ G(x0 ). (1.11) Giả sử x0 là phương án cực biên không suy biến. Ta có các véctơ    Aij | (i; j) ∈ G(x0 ) độc lập tuyến tính và G(x0 ) = m + n − 1. Do đó hệ (1.11) tương ứng ui + vj = cij , (i; j) ∈ G(x0 ) có m + n − 1 phương trình độc lập tuyến tính với nhau và m + n biến ui , i = 1, ..., m, và vj , j = 1, ..., n. Do đó để giải hệ này, có thể cho một 16Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 14 biến giá trị tùy ý (thông thường cho u1 = 0) và các ẩn còn lại được xác định duy nhất bằng phương pháp thế. Như vậy, mỗi phương án cực biên không suy biến x0 = (x0ij ) tương ứng với một bộ số ui , i = 1, ..., m và vj , j = 1, ..., n (sai khác một hằng số) thỏa mãn (1.11). Ta gọi các số ui , vj này là các thế vị. Các đại lượng ∆ := ui + vj − cij được gọi là các ước lượng. Khi đó, điều kiện (1.10) được viết lại là ∆ij ≤ 0, ∀(i; j) ∈ T. Định lý sau đây cho ta biết dấu hiệu nhận biết phương án cực biên không suy biến x0 chưa phải tối ưu và từ đó chuyển sang một phương án cực biên x1 mà tại đó giá trị hàm mục tiêu tốt hơn tại x0 . Định lí 1.4. Giả sử x0 là phươ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à bộ các thế vị tương ứng của nó. Nếu tồn tại ô (ik ; jk ) ∈ / G(x0 )sao cho ∆ik ik > 0 (1.12) thì x0 không là phương án tối ưu và từ x0 ta chuyển đến được một phương án cực biên x1 tốt hơn x0 , tức

f x1 < f x0 . 1.4 Thuật toán thế vị Như đã trình bày ở trên, thuật toán thế vị giải bài toán vận tải xuất phát từ một phương án cực biên. Việc xác định một phương án cực biên của bài toán vận tải đơn giản hơn rất nhiều so với việc tìm phương án cực biên của một bài toán quy hoạch tuyến tính tổng quát và việc đó được trình bày ở trên. Ở đây ta giới thiệu thuật toán thế vị giải bài toán vận tải không suy biến, tức là các phương án cực biên ban đều có đúng (m+n−1) thành phần dương, với giả thiết đã biết trước một phương án cực biên. Thuật toán thế vị Bước khởi tạo: 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 không suy biến x0 = (x0ij ). Tập ô chọn tương 17Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 15
 ứng với x0 là G x0 = (i; j) ∈ T |x0ij > 0 gồm đúng (m + n − 1) ô không chứa chu trình và. Đặ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 với xk−1 bằng cách giải hệ phương trình dạng tam giác (1.11): u1 = 0, ui + vj = cij , ∀(i; j) ∈ G(xk−1 ) Bước 2:Tính các ước lượng: ∆ij = ui + vj − cij , ∀(i; j) ∈ / G(xk−1 ). (Để ý là ta luôn có ∆ij = ui + vj − cij = 0, ∀(i; j) ∈ G(xk−1 ) ) Điền ước lượng ∆ij với (i; j) ∈ / G(xk−1 ) vào góc bên phải của ô (i; j). Bước 3: Kiểm tra tối ưu: If ∆ij ≤ 0, ∀(i; j) ∈ / G(xk−1 ). Then dừng thuật toán (x0 là phương án tối ưu theo Định lý(1.3)). Else Chuyển bước 4. Bước 4: Điều chỉnh phương án (nếu cần)  4a) Xác định ô điều chỉnh (is ; js ) với ∆r;s = max ∆ij > 0|∀(i; j) ∈ / G(xk−1 ) . 4b) Tìm chu trình duy nhất K trong tập G(x0 ) ∪ (r; s). 4c) Chia các ô thuộc K thành ô lẻ K1 và ô chẵn K2 với qui ước (r; s) ∈ K1 . n o k−1 k−1 4d) Xác định lượng điều chỉnh h = min xij : (i; j) ∈ K2 = xpq 4e) Xây dựng phương án       k−1 xij =      cực biên mới xk với k−1 xij , khi (i; j) ∈ / K, k−1 xij + h, khi (i; j) ∈ K1 , k−1 xij − h, khi (i; j) ∈ K2 .
Ta có G(xk ) := G(xk−1 )\ {(p; q)} ∪ {(r; s)} và G(xk ) không chứa chu trình, tức là xk là phương án cực biên. 4f) Gán 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. 18Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 16 Mệnh đề 1.1. Nếu các lượng phát ai , i = 1, ..., m và các lượng thu bj , j = 1, ..., n đều là các số nguyên thì bài toán vận tải ban đầu sẽ có nghiệm tối ưu với các thành phần đều nguyên. Chú ý 1.1. Trong trường hợp bài toán vận tải suy biến, có hai dấu hiệu để nhận biết: • 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 xk và xkrs = 0 còn ô (p; q) ∈ K2 ứng k với xk−1 pq = 0 sẽ trở thành ô loại đối với phương án x . Tuy nhiên, kết quả điều chỉnh không làm thay đổi phương án cực biên (xk − 1 = xk ) mà chỉ làm thay đổi tập véctơ cơ sở của phương án đó. • 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. Chú ý 1.2. (Dấu hiệu bài toán có phương án tối ưu duy nhất và không duy nhất) • Nếu phương án cực biên không suy biến x0 thỏa mãn tiêu chuẩn ∆ij = ui + vj − cij < 0, ∀(i; j) ∈ / G(x0 ) thì đó là phương án tối ưu duy nhất của bài toán vận tải. • Ngược lại, nếu phương án cực biên không suy biến x0 là phương án tối ưu và tồn tại ô (r; s) ∈ / G(x0 ) có ∆rs = 0 thì x0 không phải phương án tối ưu duy nhất của bài toán vận tải. Tương tự thuật toán đơn hình giải bài toán quy hoạch tuyến tính, muốn tìm một phương án cực biên tối ưu khác x0 , ta chọn (r; s) làm ô điều chỉnh và thực hiện tiếp một số bước lặp theo thuật toán thế vị. Sau đây là một số ví dụ minh họa cho thuật toán thế vị. 19Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 17 1.5 Ví dụ minh họa Ví dụ 1.4. Giải bài toán vận tải bằng thuật toán thế vị với véctơ cung a, véctơ cầu b và ma trận cước phí C như sau: a = ( 170 180 200 ) , b = ( 120 130 140 160 )    22 20 25 18 10 0 0 160   0   , x =  110 0 70 0 40 45 35 30 C=    30 15 15 25 0 130 70     0 Giải: Bài toán này có m = 3 điểm phát và n = 4 điểm thu và thỏa mãn điều kiện cân bằng thu phát (1.5). Phương án cực biên ban đầu x0 được tìm theo phương pháp min cước có tập ô chọn là
G x0 = {(1; 1) , (1; 4) , (2; 1) , (2; 3) , (3; 2) , (3; 3)} , gồm 6 = m + n − 1 ô không chứa chu trình và giá trị hàm mục tiêu f (x0 ) = 12950. Vòng lặp thứ nhất. Bước 1. Các thế vị tương ứng với x0 : u0 = ( 0 18 −2 ) , v 0 = ( 22 17 17 18 ) . Các ước lượng ∆ij = ui + vj − c ghi trong ma trận ∆0 dưới đây.   0 −3 −8 0    0 −10 0 6 ∆0 =    −10 0 0 −9 Bước 3. Phương án x0 chưa tối ưu vì còn ∆24 = 6 > 0 và (2; 4) ∈ / G(x0 ). Bước 4. Điều chỉnh phương án: 4a) Ô điều chỉnh (r; s) = (2; 4) vì  ∆24 = max ∆ij > 0 : (i; j) ∈ / G(x0 ) = 6 > 0 20Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn