Tài liệu Bài toán vận tải phân tuyến tính.

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN TRÀ GIANG BÀI TOÁN VẬN TẢI PHÂN TUYẾN TÍNH LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - Năm 2012 Số 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 HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN TRÀ GIANG BÀI TOÁN VẬN TẢI PHÂN TUYẾN TÍNH Chuyên ngành: TOÁN ỨNG DỤNG Mã số : 60.46.36 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 2012 Số 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 NÓI ĐẦU 1 Nội dung 4 1 BÀI TOÁN VẬN TẢI VỚI HÀM MỤC TIÊU TUYẾN TÍNH 4 1.1 Bài toán và các tính chất . . . . . . . . . . . . . . . . . . . 4 1.2 Tìm phương án cực biên ban đầu 9 1.3 Tiêu chuẩn tối ưu . . . . . . . . . . . . . . . . . . . . . . . 13 1.4 Phương pháp thế vị . . . . . . . . . . . . . . . . . . . . . . 17 1.5 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . 19 . . . . . . . . . . . . . . 2 BÀI TOÁN VẬN TẢI VỚI HÀM MỤC TIÊU PHÂN TUYẾN TÍNH 25 2.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . 25 2.2 Phương pháp giải . . . . . . . . . . . . . . . . . . . . . . . 28 2.3 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . 38 2.4 Bài toán đối ngẫu . . . . . . . . . . . . . . . . . . . . . . . 45 Kết luận 50 Tài liệu tham khảo 52 Số 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 LỜI NÓI ĐẦU Bài toán vận tải đã khá quen thuộc trong lý thuyết qui hoạch tuyến tính. 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 giải 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ị, phương pháp qui không ô chọn, phương pháp thu hẹp chính tắc. Có thể xét mở rộng bài toán vận tải theo nhiều hướng khác nhau, như thay đổi điều kiện ràng buộc: vận tải khi không có cân bằng cung cầu (cung vượt quá cầu hoặc cầu vượt quá cung), vận tải có trung chuyển, vận tải có hạn chế năng lực thông qua, vận tải có vận chuyển ngược; hoặc thay đổi dạng của hàm mục tiêu: vận tải với hàm mục tiêu phân tuyến tính (tỉ số của hai hàm tuyến tính), vận tải với hàm mục tiêu lồi hay lõm, v.v ... Chẳng hạn, bài toán vận tải phân tuyến tính tìm phương án vận chuyển làm cực tiểu tỉ số của chi phí vận chuyển hàng hoá trên tổng lợi nhuận thu được khi vận chuyển toàn bộ số hàng đó. Tuy hàm mục tiêu của bài toán là phi tuyến, nhưng các ràng buộc của bài toán vẫn có cùng cấu trúc như của bài toán vận tải thông thường, vì thế có thể vận dụng các phương pháp giải bài toán vận tải đã biết cho bài toán vận tải mở rộng. 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ế các kiến thức về qui hoạch tuyến tính chính tắc nói chung đều có thể áp dụng vào bài toán vận tải tuyến tính nói riêng. Ràng buộc của bài toán vận tải tuyến tính và phân tuyến tính có cấu trúc vận tải nên Số 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 miền ràng buộc của các bài toán này có các tính chất đặc biệt. Có thể khâi thác các tính chất đó để xây dựng thuật toán giẩi riêng, hiệu quả. Luận văn này đề cập tới bài toán vận tải với hàm mục tiêu tuyến tính và phân tuyến tính: giới thiệu nội dung, 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 tải tuyến tính và dạng mở rộng của nó để giải bài toán vận tải phân tuyến tính. Vấn đề đối ngẫu và các quan hệ đối ngẫu của bài toán vận tải tuyến tính và phân tuyến tính cũng được đề cập tới. Nội dung luận văn được chia thành hai chương. Chương 1 với tiêu đề "Bài toán vận tải với hàm mục tiêu 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 "min cước" và phương pháp "góc Tây - Bắc" để 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 hiệu quả 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. Các kiến thức về bài toán vận tải nói chung và thuật toán thế vị nói riêng sẽ cần đến ở chương sau, khi xét bài toán vận tải phân tuyến tính. Chương 2 với tiêu đề "Bài toán vận tải với hàm mục tiêu phân tuyến tính" đề cập tới một mở rộng bài toán vận tải tuyến tính, bằng cách thay hàm mục tiêu tuyến tính bằng hàm mục tiêu phân tuyến tính (tỉ số của hai hâm tuyến tính), hàm này có tính chất đơn điệu theo từng phương. Dựa vào cấu trúc đặc biệt của bài toán, chương này nêu ra điều kiện để phương án của bài toán là tối ưu và nêu thuật toán thế vị mở rộng giải bài toán. Thuật toán có kèm theo ví dụ số để minh họa. Cuối chương đề cập tới bài toán đối ngẫu của bài toán vận tải phân tuyến tính và nêu các quan hệ đối ngẫu giữa hai bài toán gốc và đối ngẫu, tương tự như lý thuyết đối ngẫu trong qui hoạch tuyến tính. Do thời gian và kiến thức còn hạn chế nên luận văn này mới chỉ đề cập Số 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 tới những nội dung cơ bản của bài toán vận tải phân tuyến tính, chưa đi sâu vào các chi tiết thực thi thuật toán. Trong quá trình viết luận văn cũng như trong xử lý văn bản chắc chắn không tránh khỏi những sai sót nhất định. Tác giả luận văn rất mong nhận được sự góp ý của các thầy cô và các bạn đồng nghiệp để luận văn được hoàn thiện hơn. Nhân dịp này, tác giả xin bày tỏ lòng biết ơn sâu sắc đến thầy hướng dẫn GS-TS Trần Vũ Thiệu đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Tác giả xin trân trọng cảm ơn các thầy, cô giáo Trường Đại học Khoa học- Đại học Thái Nguyên, Viện Toán học-Viện Khoa học và Công nghệ Việt Nam, đã giảng dạy và 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 07 năm 2012. Người thực hiện Nguyễn Trà Giang Số 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 VỚI HÀM MỤC TIÊU TUYẾN TÍNH Chương này xét bài toán vận tải với hàm mục tiêu 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 áp dụng rộng rãi trong thực tiễn. Mục 1.1 giới thiệu mô hình bài toán và các tính chất cơ bản. Mục 1.2 nêu phương pháp min cước và phương pháp góc Tây-Bắc tìm phương án cực biên ban đầu của bài toán. Điều kiện tối ưu được đưa ra ở Mục 1.3 và thuật toán thế vị cùng cơ sở lý luận của thuật toán được trình bày ở Mục 1.4. Ví dụ số được xây dựng ở Mục 1.5. Nội dung của chương chủ yếu tham khảo từ các tài liệu [1] , [2] và [4]. 1.1 Bài toán và các tính chất Mô hình toán học của bài toán vận tải có dạng như sau: m X n X cij xij → min (cực tiểu tổng chi phí vận chuyển) i=1 j=1 với các điều kiện: Số 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.1) 5 n X xij = ai , i = 1, 2, ..., m (mọi điểm phát giao hết hàng) (1.2) j=1 m X xij = bj , j = 1, 2, ..., 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) Ở đây m là kho hàng (điểm phát), n là 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 đến đ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: a1 + 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 của m × n biến số xij như sau: Số 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  x11 + x12 + ... + x1n    x21 + x22 + ... + x2n    ... ...   xm1 + xm2 + ... + xmn x11 + x21 ... + xm1    x12 + x22 ... + xm2     ... ... ... ...  x1n + x2n ... + xmn = a1 , = a2 , = am , = b1 , = b2 , = bn . Ký hiệu A là ma trận hệ số của hệ phương trình trên (gồm m + n hàng và m × n cột). x = (x11 , x12 , ..., x1n , x21 , x22 , ..., x2n , ..., xm1 , xm2 , ..., xmn )T là véctơ cột m × n thành phần, c = (c11 , c12 , ..., c1n , c21 , c22 , ..., c2n , ..., cm1 , cm2 , ..., cmn )T là véc tơ cột m × n thành phần, b = (a1 , a2 , ..., am , b1 , b2 , ..., bn )T là 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 quy hoạch tuyến tính dạng chính tắc: f = < c, x > → min, Ax = b, x ≥ 0. Ta gọi Aij là véctơ cột của ma trận A ứng với biến xij . Dễ thấy rằng 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 ứng với các xij > 0 là độc lập tuyến tính.Sau đây ta sẽ giả thiết là có điều kiện cân bằng thu phát (1.5). Số 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 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 = {(i, j) : xij > 0} bằng m+n-1, gọi là suy biến nếu |G| < m+n-1. Để cho gọn, 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 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 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. Bảng 1.1. Bảng vận tải Thu b1 ··· bj ··· bn Phat a1 c11 .. . ··· .. . .. . ··· cin xij .. . ··· cm1 x1n ··· cij xi1 .. . c1n x1j ··· ci1 .. . am ··· x11 .. . ai ··· c1j ··· Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên .. . ··· cmj xm1 xin ··· xmj cmn xmn http://www.lrc-tnu.edu.vn 8 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 quan trọng sau đây. Định lý 1.1. a)Bài toán vận tải luôn luôn có phương án tối ưu. b) Hạng của hệ phương trình (1.2) - (1.3) của bài toán bằng m + n 1. c) Nếu lượng cung cầu ai , bj là các số nguyên thì bài toán này sẽ có lời giải nguyên. Có thể dùng các phương pháp của quy 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ả. Trong số đó có thuật toán thế vị sẽ xét ở mục 1.4 dưới đây. Đị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. Dãy ô đánh dấu "•" trong Hình 1.1 a) và b) lập thành các dây chuyền, còn các ô với dấu • trong Hình 1.1 c) - e) lập thành các chu trình. a) b) c) d) Hình 1.1 Dây chuyền: a) - b).Chu trình: c) - e). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn e) 9 Cho G là một tập hợp ô bất kỳ của bảng vận tải. Một ô thuộc G gọi là ô treo nếu nó là ô duy nhất của G trên hàng hay trên cột của ô đó. Với tập hợp ô cho ở Hình 1.1 a) thì ô (1,1) và ô (4,3) là các ô treo. Nếu loại khỏi G ô treo (1,1) thì ô (1,2) sẽ trở thành ô treo của tập hợp ô còn lại. Ta có mối liên hệ quan trọng sau đây. Định lý 1.2. Hệ véctơ {Aij : (i, j) ∈ G} của bài toán vận tải (1.1) - (1.4) là độc lập tuyến khi và chỉ khi tập hợp các ô thuộc G không tạo thành chu trình. Hệ quả 1.1. Véctơ x = {xij }m×n là một phương án cực biên của bài toán khi và chỉ khi tập hợp các ô (i, j) mà xij > 0 không lập thành chu trình. Hệ quả 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. Chu trình nói tới trong hệ quả trên có thể tìm bằng cách loại dần các ô treo của tập hợp ô G = T ∪ {(p, q)}. Ví dụ, tập hợp ô T ở Hình 1.1 b) gồm m + n -1 = 7 ô, không tạo thành chu trình. Bổ sung vào T ô (4, 2) ∈ /T (ô đánh dấu ? ) ta được G = T ∪ {(4, 2)}. Khi đó, bằng cách loại khỏi G ô treo (3,3) (ô duy nhất của G trên cột 3), rồi ô treo (3,2) đối với tập ô G0 = G\{3, 3} (ô duy nhất của G’ trên hàng 3), ta nhận được chu trình (gồm 6 ô): C = {(4, 2), (4, 1), (2, 1), (2, 4), (1, 4), (1, 2)} 1.2 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 của bài toán. Có nhiều cách để tìm một phương án như thế. Sau đây là một vài phương pháp thông dụng và có hiệu quả. a) Phương pháp min cước Số 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 Trong bảng vận tải 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ân phối 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 đã phát hết hàng, hoặc cột thu 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 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 này có thể bằng 0). Phương án x thu được có đúng m + n - 1 ô đã được 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. Tìm phương án cực biên ban đầu của bài toán vận tải với các số liệu cho ở bảng 1.2. Bảng 1.2. Phương án cực biên xây dựng theo phương pháp min cước Thu 130 160 120 140 Phát 20 18 22 25 170 160 15 25 10 30 15 200 130 45 70 30 40 35 180 110 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 70 http://www.lrc-tnu.edu.vn 11 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ỉ 0 còn lại lượng phát a1 = 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 đã phát hết hàng nên bị loại. Cột 4 chỉ còn thiếu lượng hàng 0 b4 = 140 − 70 = 70. Trong bảng còn lại (ba cột cuối hàng 1 và 3), ta chọn ô (1,2) 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 chỉ còn lại lượng phát 0 a1 = 170 − 160 = 10. 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 x33 = 120 − 10 = 110 và x34 = 180 − 110 = 140 − 70 = 70. Đến đây mọi hàng (cột) đã phát hết (nhận đủ) hàng, ta dặt xij = 0 đối với mọi ô (i,j) còn lại. Kết quả ta được phương án cực biên cho ở bảng trên. 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. b) 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 T (ô(1,1)), ta điền lượng hàng x11 lớn nhất có thể vào đó, tức cho chuyển một lượng hàng lớn nhất có thể từ điểm 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: Số 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 ♦ Nếu x11 = a1 < b1 thì đ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’ gồm (m - 1) hàng và n cột với lượng phát, thu tương ứng: 0 ai = ai ; i = 2, 3, ..., m, 0 0 b1 = b1 − x11 = b1 − a1 ; bj = bj , j = 2, 3, ..., n; ♦ Nếu x11 = b1 < a1 thì điểm phát 1 còn 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’ gồm m hàng và n-1 cột với lượng phát, thu tương ứng: 0 0 a1 = a1 − x11 = a1 − b1 ; ai = ai , i = 2, 3, ..., m, 0 bj = bj ; j = 2, 3, ..., n; ♦ Nếu x11 = b1 = a1 thì đ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’ gồm m hàng và n - 1 cột với lượng phát, thu tương ứng: 0 0 a1 = 0; ai = ai ; i = 2, 3, ..., m, 0 b1 = bj , j = 2, 3, ..., n; • Đới với bảng T’, 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’, xác định khối lượng vận chuyển lớn nhất có thể (khối lượng hàng này 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 đến khi loại hết được tất cả các hàng và các cột của bảng vận tải. Những ô (i, j) không được phân phối hàng có xij = 0 Ví dụ: Xét lại bài toán vận tải cho ở Ví dụ 1.2 Bảng 1.3 Số 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 bj 130 ai 160 20 120 18 140 22 25 30 15 170 130 15 40 25 200 120 45 30 80 40 35 180 40 140 Kết quả tìm phương án cực biên xuất phát x0 theo phương pháp góc tây bắc được trình bày ở bảng 1.3. 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 đứt nét). Giá trị hàm mục tiêu tương ứng bằng 15200. 1.3 Tiêu chuẩn tối ưu Xét bài toán vận tải min f (x) = m P n P cij xij (P T ) i=1 j=1 v.đ.k n P xij = ai , i = 1, ..., m j=1 m P xij = bj , j = 1, ..., n i=1 xij ≥ 0, i = 1, ..., m, j = Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1, ..., n. http://www.lrc-tnu.edu.vn 14 Bài toán đối ngẫu của bài toán này là max g(y) = m P i=1 ai ui + n P bj vj (DT ) j=1 với điều kiện ui + vj ≤ cij , i = 1, ..., m, j = 1, ..., n, trong đó y = (u1 , ..., um , v1 , ..., vn )T . Để đơn giản việc trình bày, giả sử rằng bài toán (1.1) - (1.4) không suy biến, tức mọi 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ẽ trình bày ở phần sau  Cho phương án x0 . Ký hiệu G(x0 ) = {(i, j) ∈ T x0ij > 0}. Sau đây là điều kiện cần và đủ để phương án x0 = (x0ij ) là phương án tối ưu. Phương án x0 = (xij 0 ) 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 ui + vj ≤ cij , ∀(i, j) ∈ T (1.6) ui + vj = cij , ∀(i, j) ∈ G(x0 ) (1.7) Chứng minh. (⇒) Giả sử phương án x0 = (x0ii ) là phương án tối ưu của bài toán vận tải (1.1) - (1.4). Theo định lý đối ngẫu mạnh, bài toán đối ngẫu có phương án tối ưu y 0 = (u1 , ..., um , v1 , ..., vn )T . Do y 0 là phương án chấp nhận được của bài toán đối ngẫu nên nó thỏa mãn mọi ràng buộc của bài toán, tức ui + vj ≤ cij ; i = 1, ..., m; j = 1, ..., n. Đây chính là điều kiện (1.6). Hơn nữa, vì x0 là phương án tối ưu của bài toán gốc và y 0 là phương án tối ưu của bài toán đối ngẫu nên theo định lý về độ lệch bù ta có  c − AT y 0 , x0 = 0 ⇒ nếu x0ij > 0 thì ui + vj = cij Số 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 hay điều kiện (1.7) được thỏa mãn. (⇐) Cho phương án x0 = (x0ii ). Giả sử tồn tại các số ui ; i = 1, ..., m và vj ; j = 1, ..., n thỏa mãn (1.6) và (1.7). Ta phải chứng minh x0 là phương án tối ưu. Thật vậy, do có (1.7) và do x0ij = 0 với (i, j) ∈ / G(x0 ) nên giá trị hàm mục tiêu tại x0 là 0 f (x ) = m X n X cij x0ij = i=1 j=1 m X n X (ui + vj )x0ij (1.8) i=1 j=1 Giả sử x = (xij ) là một phương án bất kỳ của bài toán vận tải. Ta có f (x) = m P n P = cij xij i=1 j=1 m n P P = i=1 m P = i=1 m P = i=1 ≥ xij + ui i=1 m (1.8) P m P n 1.6 P vj j=1 j=1 ui ai + n P (ui + vj )xij i=1 j=1 n m P P xij i=1 vj bj (vì x là một phương án) j=1 ui n P j=1 x0ij + n P j=1 vj m P i=1 x0ij (vì x0 là một phương án) (ui + vj )x0ij = f (x0 ) Vậy x0 là phương án tối ưu của bài toán vận tải đang xét. Chú ý 1.1 : Giả sử x0 là phương án cực biên không suy biến. Ta có các    véc tơ {Aij (i, j) ∈ G(x0 ) } độc lập tuyến tính và G(x0 ) = m + n − 1. Do đó hệ (1.8) 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 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 các bộ số ui , i = 1, ..., m và vj , j = 1, ..., n. (sai khác một hằng số) thỏa mãn (1.8). Ta gọi các số ui , vj Số 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 này là các thế vị. Các đại lượng ∆ij := ui + vj − cij được gọi là các ước lượng. Khi đó, điều kiện (1.4) được viết lại là ∆ij ≤ 0, ∀(i, j) ∈ T Định lý 1.3. 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 , vj , i = 1, ..., m, j = 1, ..., n là bộ các thế vị tương ứng với nó. Nếu ∃ ô (ik , jk ) ∈ / G(x0 ) sao cho ∆ik jk > 0 (1.9) thì x0 không phải 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 ) Cách xây dựng x1 như sau:   Do x0 là phương án cực biên không suy biến nên G(x0 ) = m + n − 1 và G(x0 ) không chứa chu trình. Tập G(x0 ) ∪ {(ik , jk )} chứa một chu trình K duy nhất đi qua (ik , jk ). Lần lượt đánh dấu các ô trong K bởi các dấu + và -, xuất phát từ ô (ik , jk ) với dấu +, sao cho không có hai ô nào cạnh nhau trong K lại dược đánh dấu bởi cùng một dấu. Ký hiệu K + := {các ô trong K được đánh dấu +}, K − := {các ô trong K được đánh dấu -}, Xây dựng x1 = (x1ij ) theo công thức  0 +  xij + θ nếu (i, j) ∈ K x1ij = x0ij − θ nếu (i, j) ∈ K −  0 xij , nếu (i, j) ∈ /K (1.10) với θ = min{x0ij |(i, j) ∈ K − } = x0ir jr . Số 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.11) 17 Vì x0 là phương án cực biên không suy biến nên θ > 0. Có thể thấy x1 là một phương án cực biên của bài toán với x1ir jr = θ > 0 và G(x1 ) = (G(x0 )\{(ir ,jr )}) ∪ {(ik ,jk )} Hơn nữa, f (x1 ) = f (x0 ) − θ∆ik jk < f (x0 ). Ô (ik , jk ) được gọi là ô điều chỉnh và K được gọi là chu trình điều chỉnh. 1.4 Phương pháp thế vị Mục này giới thiệu phương pháp thế vị giải bài toán vận tải. Thuật toán xuất phát từ một phương án cực biên ban đầu không suy biến x0 . Do bài toán vận tải luôn có nghiệm nên từ x0 chỉ có một trong hai trường hợp sau xảy ra: i) Nếu x0 thỏa mãn tiêu chuẩn tối ưu thì dừng thuật toán: x0 là phương án tối ưu của bài toán. ii) Ngược lại, ta chuyển đến phương án cực biên x1 thỏa mãn f (x1 ) ≤ f (x0 ); Gán x0 := x1 và lặp lại quá trình tính toán với x0 mới. Thuật toán thế vị Bước khởi tạo. Giả sử đã biết phương án cực biên không suy biến x0 =  (x0 ). Tập ô chọn tương ứng với x0 là G(x0 ) = {(i, j)  x0 > 0 } gồm m+nij ij 1 phần tử và không chứa chu trình. Bước 1. Xác định các thế vị ui , i = 1, ..., m, và vj , j = 1, ..., n tương ứng với phương án cực biên x0 bằng việc giải hệ phương trình. ui + vj = cij ∀(i, j) ∈ G(x0 ). Bước 2. Tính các ước lượng ∆ij = ui + vj − cij ∀(i, j) ∈ / G(x0 ) (Luôn có ∆ij = 0∀(i, j) ∈ G(x0 )) Điền ước lượng ∆ij với (i, j) ∈ / G(x0 ) vào góc dưới bên phải của ô (i,j). Bước 3. (Kiểm tra điều kiện tối ưu) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn