Luận văn Bài toán vận tải có vận chuyển ngược

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC - - - - - - - - - - - - - - - - - - TRỊNH THỊ THANH HẢO BÀI TOÁN VẬN TẢI CÓ VẬN CHUYỂN NGƯỢC LUẬN VĂN THẠC SỸ TOÁN HỌC Chuyên ngành : TOÁN ỨNG DỤNG Mã số : 60.46.36 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 Mục lục Lời cảm ơn 3 Lời nói đầu 4 1 Bài toán qui hoạch tuyến tính dạng chính tắc 7 1.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Sự tồn tại nghiệm . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Phương án cực biên . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Bài toán đối ngẫu . . . . . . . . . . . . . . . . . . . . . . . 9 2 Bài toán vận tải với biến không âm 13 2.1 Bài toán vận tải và tính chất . . . . . . . . . . . . . . . . . 13 2.2 Tìm phương án cực biên ban đầu . . . . . . . . . . . . . . . 18 2.3 Tiêu chuẩn tối ưu . . . . . . . . . . . . . . . . . . . . . . . 21 2.4 Thuật toán thế vị . . . . . . . . . . . . . . . . . . . . . . . 26 2.5 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . 28 3 Bài toán vận tải có vận chuyển ngược 32 3.1 Vận chuyển ngược có lợi ích gì? . . . . . . . . . . . . . . . 32 3.2 Mô hình bài toán vận tải có vận chuyển ngược . . . . . . . 33 3.3 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . . 36 3.4 Thuật toán giải bài toán (P) . . . . . . . . . . . . . . . . . 38 3.5 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . 40 Kết luận 45 Tài liệu tham khảo 46 2 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Lời cảm ơn Luận văn này được hoàn thành tại Trường Đại học Khoa học, Đại học Thái Nguyên dưới sự hướng dẫn của GS.TS. Trần Vũ Thiệu. Tác giả xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới thầy về sự tận tình hướng dẫn trong suốt thời gian tác giả làm luận văn. Trong quá trình học tập và làm luận văn, thông qua các bài giảng và xêmina, tác giả thường xuyên nhận được sự quan tâm giúp đỡ và đóng góp những ý kiến quý báu của các GS,TS trong Viện Toán học đã không quản ngại đường sá xa xôi lên Thái Nguyên giảng dạy cho chúng em. Tác giả cũng xin gửi tới TS. Nguyễn Thị Thu Thủy và các thầy các cô trong trường Đại học Khoa học - Đại học Thái Nguyên. Từ đáy lòng mình, tác giả xin bày tỏ lòng biết ơn sâu sắc đến các thầy các cô. Tác giả xin bày tỏ lòng biết ơn tới các thầy, các cô, Ban giám hiệu nhà trường, Ban chấp hành Đoàn, các đồng nghiệp cùng công tác trong cơ quan đã luôn tạo điều kiện thuận lợi nhất giúp đỡ tác giả trong thời gian học tập và làm luận văn cao học. Xin chân thành cảm ơn anh chị em học viên cao học Toán K4A và bạn bè đồng nghiệp gần xa đã trao đổi, động viên và khích lệ tác giả trong quá trình học tập, nghiên cứu và làm luận văn. Luận văn sẽ không hoàn thành được nếu không có sự thông cảm, giúp đỡ của những người thân trong gia đình tác giả. Đây là món quà tinh thần, tác giả xin kính tặng gia đình thân yêu của mình với tấm lòng biết ơn chân thành và sâu sắc. 3 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Lời nói đầu Bài toán vận tải (Transportation problem) của qui hoạch tuyến tính đã khá quen thuộc trong toán học ứng dụng. Trong bài toán vận tải dạng bảng chỉ cho phép vận chuyển hàng từ các trạm phát tới các trạm thu, không vận chuyển theo chiều ngược lại (từ các trạm thu tới các trạm phát). Lời giải thu được đôi khi không cho chi phí vận chuyển nhỏ nhất. Đó là vì lời giải này chỉ đúng khi đã xác định được chi phí nhỏ nhất cần để vận chuyển một đơn vị hàng từ mỗi trạm phát tới mỗi trạm thu. Muốn vậy, cần giải các bài toán phụ trợ: tìm đường đi ngắn nhất giữa mỗi cặp trạm thu - phát. Có thể mở rộng bài toán vận tải bằng cách cho phép vận chuyển hàng theo cả chiều ngược lại từ các trạm thu tới các trạm phát. Từ đó dẫn đến mô hình bài toán vận tải có vận chuyển ngược (Transportation problem with reshipments). Mô hình mới chỉ khác cũ ở chỗ: các biến biểu thị lượng hàng vận chuyển bây giờ có thể lấy giá trị âm và trong hàm mục tiêu sử dụng dấu giá trị tuyệt đối. Trong nhiều trường hợp, vận chuyển ngược có thể làm giảm chi phí vận chuyển. Luận văn này nghiên cứu đề xuất thuật toán giải cho bài toán vận tải có vận chuyển ngược, dựa trên cơ sở trả lời một số câu hỏi như: những tính chất nào đúng cho bài toán vận tải thông thường vẫn còn đúng cho bài toán vận tải có vận chuyển ngược, tiêu chuẩn tối ưu bây giờ thay đổi như thế nào và có thể mở rộng thuật toán thế vị cho bài toán mới được không. Nội dung luận văn được chia thành ba chương. 4 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Chương 1 với tiêu đề "Bài toán qui hoạch tuyến tính dạng chính tắc" nhắc lại những kiến thức cơ bản về bài toán qui hoạch tuyến tính chính tắc: điều kiện tồn tại nghiệm của bài toán, tính chất của phương án cực biên, bài toán đối ngẫu và các quan hệ đối ngẫu trong qui hoạch tuyến tính. Do bài toán vận tải cũng có dạng một bài toán qui hoạch tuyến tính chính tắc nên có thể áp dụng các kiến thức này cho bài toán vận tải. Chương 2 với tiêu đề "Bài toán vận tải với biến không âm" 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 với các biến lấy giá trị không âm. Tiếp đó, luận văn 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. Để áp dụng thuật toán, đòi hỏi biết một phương án cực biên ban đầu của bài toán. Vì thế cách tìm phương án cực biên ban đầu (theo min cước hoặc phương pháp góc Tây - Bắc) cũng được nêu đầy đủ. Cuối chương xây dựng 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 có vận chuyển ngược. Chương 3 với tiêu đề "Bài toán vận tải có vận chuyển ngược" đề cập tới một mở rộng bài toán vận tải với biến không âm, cho phép vận chuyển hàng theo cả chiều ngược lại từ trạm thu tới trạm phát. Mô hình bài toán vận tải có vận chuyển ngược có dạng một bài toán qui hoạch lồi ràng buộc tuyến tính với các biến lấy giá trị tùy ý (dương, âm hay bằng 0) và trong hàm mục tiêu sử dụng dấu giá trị tuyệt đối. Dựa vào cấu trúc đặc biệt của mô hình, chương này nêu cách đưa bài toán vận tải có vận chuyển ngược về một bài toán qui hoạch tuyến tính chính tắc với cấu trúc gần giống như bài toán vận tải thông thường. Từ đó nêu ra điều kiện tối ưu và đề xuất thuật toán thế vị mở rộng giải bài toán. Cuối chương xây dựng ví dụ số minh họa cho thuật toán giải. Nội dung của chương này được hình thành dựa trên ý tướng nêu ra ở tài liệu [5] và đã được tác giả luận văn trình bày chi tiết trong bài báo 5 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên đăng ở Tạp chí Khoa học và Công nghệ của Đại học Thấi Nguyên, Tập 90, số 02, 2012, trang 107 - 112. Do thời gian và kiến thức còn hạn nên luận văn mới chỉ dừng lại ở vịêc tìm hiểu, tập hợp tài liệu, sắp xếp và trình bày các kết quả nghiên cứu đã có theo chủ đề đặt ra. Trong quá trình viết luận văn cũng như trong quá trình xử lý văn bản chắc chắn không thể tránh khỏi sai sót, rất mong nhận được những ý kiến đóng góp của Thầy cô và bạn đọc. Tác giả Trịnh Thị Thanh Hảo 6 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Chương 1 Bài toán qui hoạch tuyến tính dạng chính tắc Chương này nhắc lại một số khái niệm và các tính chất cơ bản của bài toán qui hoạch tuyến tính dạng chính tắc. Cụ thể xét sự tồn tại nghiệm của bài toán, tính chất của phương án cực biên và vấn đề đối ngẫu trong qui hoạch tuyến tính. Các kiến thức này cần đến cho các chương sau. Nội dung chương này tham khảo chủ yếu từ các tài liệu [1], [2] và [6]. 1.1 Phát biểu bài toán Bài toán chính tắc có dạng: f(x) ≡ n∑ j=1 cjxj → min, n∑ j=1 aijxj = bi, i = 1, 2, ...,m, xj ≥ 0, j = 1, 2, ..., n. Trong bài toán trên aij, bi, cj là các hằng số thực cho trước, f(x) gọi là hàm mục tiêu. Mỗi đẳng thức n∑ j=1 aijxj = bi gọi là một ràng buộc chính, mỗi bất đẳng thức xj ≥ 0 gọi là một ràng buộc về dấu. (Đặc điểm của bài toán chính tắc là mọi ràng buộc chính chỉ là các đẳng thức và mọi biến đều không âm). Điểm thỏa mãn mọi ràng buộc gọi là một điểm chấp nhận được, hay một phương án. Tập hợp tất cả các phương án, ký hiệu là D, gọi là miền 7 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ràng buộc hay miền chấp nhận được. Một phương án đạt cực tiểu của hàm mục tiêu gọi là một phương án tối ưu hay một lời giải của bài toán đã cho. 1.2 Sự tồn tại nghiệm Đinh lý sau cho một điều kiện cần và đủ để bài toán qui hoạch tuyến tính có lời giải. Định lý 1.1. (Về sự tồn tại lời giải của bài toán qui hoạch tuyến tính). Nếu một qui hoạch tuyến tính có ít nhất một phương án và hàm mục tiêu bị chặn dưới trong miền ràng buộc (đối với bài toán min) thì bài toán chắc chắn có phương án tối ưu. Nhận xét 1.1. Kết luận của định lý nói chung không còn đúng với các bài toán không phải là một qui hoạch tuyến tính (hàm mục tiêu không phải là tuyến tính hoặc miền ràng buộc không phải là một tập lồi đa diện). Để rõ hơn ta xét ví dụ cụ thể sau: Ví dụ 1.1. f = x2 → min , với điều kiện x1x2 ≥ 1, x1 ≥ 0. Miền chấp nhận được D = { x ∈ R2 : x1x2 ≥ 1, x1 ≥ 0 } là một tập lồi khác rỗng và hàm mục tiêu bị chặn dưới trong miền này: x2 ≥ 0 với mọi x = (x1, x2) ∈ D. Điểm (1/ε, ε) ∈ D với mọi ε > 0, nhưng không có (x1, 0) ∈ D.Vì thế cận dưới của x2 không đạt tại bất cứ điểm nào thuộc D. Cũng có thể lấy ví dụ với hàm mục tiêu phi tuyến và miền ràng buộc là một tập lồi đa diện cho thấy định lý trên không đúng. Ví dụ 1.2. Cho hàm f(x) = 11+x2 , x ∈ R. Ta thấy f(x) ≥ 0, ∀x ∈ R và inf x∈R f(x) = 0. Hàm này không đạt cực tiểu trên R. 1.3 Phương án cực biên Một phương án x ∈ D mà đồng thời là một đỉnh của D gọi là một phương án cực biên, nghĩa là x không thể biểu diễn được dưới dạng một tổ hợp lồi của bất cứ hai phương án bất kỳ nào khác của D. Nói một cách khác, hễ x = λx1 + (1 − λ)x2 với 0 < λ < 1 và x1, x2 ∈ D thì phải có x0 = x1 = x2. 8 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Định lý sau nêu một tính chất đặc trưng của phương án cực biên của bài toán qui hoạch tuyến tính chính tắc. Định lý 1.2. Để một phương án x0 = { x01, x 0 2, ..., x 0 n } của bài toán qui hoạch dạng chính tắc là phương án cực biên, thì cần và đủ là các véctơ cột Aj của ma trận A ứng với các thành phần x 0 j > 0 là độc lập tuyến tính. Hệ quả 1.1. Số phương án cực biên của bài toán qui hoạch tuyến tính dạng chính tắc là hữu hạn. Hệ quả 1.2. Số thành phần dương trong mỗi phương án cực biên của bài toán qui hoạch tuyến tính dạng chính tắc tối đa bằng m (m là số hàng của ma trận A). Người ta phân ra hai loại phương án cực biên: nếu phương án cực biên có số thành phần dương đúng bằng m, nó được gọi là phương án cực biên không suy biến. Trái lại, nó gọi là phương án cực biên suy biến. Định lý 1.3. Nếu bài toán qui hoạch tuyến tính dạng chính tắc có ít nhất một phương án thì nó cũng có phương án cực biên (miền ràng buộc D có đỉnh). Định lý 1.4. Nếu bài toán qui hoạch tuyến tính dạng chính tắc có phương án tối ưu thì cũng có phương án cực biên tối ưu. 1.4 Bài toán đối ngẫu Đối ngẫu là một phương pháp mà ứng với mỗi bài toán qui hoạch tuyến tính đã cho (gọi là bài toán gốc), ta có thể thiết lập một bài toán qui hoạch tuyến tính khác (gọi là bài toán đối ngẫu) sao cho từ lời giải của bài toán này ta sẽ thu được thông tin về lời giải của bài toán kia. Vì thế, đôi khi để có được những hiểu biết cần thiết về một bài toán thì việc nghiên cứu bài toán đối ngẫu của nó lại tỏ ra thuận tiện hơn. Hơn nữa, khi phân tích đồng thời cả hai bài toán gốc và đối ngẫu ta có thể rút ra kết luận sâu sắc cả về mặt toán học lẫn về ý nghĩa thực tiễn. Ta định nghĩa đối ngẫu của bài toán qui hoạch tuyến tính chính tắc, ký hiệu bài toán (P): f(x) = c1x1 + c2x2 + ...+ cnxn → min, 9 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ai1x1 + ai2x2 + ...+ ainxn = bi, i = 1, 2, ...,m, xj ≥ 0, j = 1, 2, ..., n, là bài toán, ký hiệu bài toán (Q): g(y) = b1y1 + b2y2 + ...+ bmym → max, a1jy1 + a2jy2 + ...+ amjym ≤ cj, j = 1, 2, ..., n. Ở đây, do các ràng buộc chính có dấu "=" nên các biến đối ngẫu tương ứng không có ràng buộc về dấu (các biến yi có dấu tùy ý). Dưới dạng véctơ -ma trận, ta có thể viết. Bài toán gốc: f(x) =→ min Ax = b, x ≥ 0. Bài toán đối ngẫu: g(y) =→ max ATy ≤ c. Định lý 1.5. (Đối ngẫu yếu) Nếu x là một phương án bất kỳ của bài toán gốc (P ) và y là một phương án bất kỳ của bài toán đối ngẫu (Q) thì f(x) = c1x1 + ...+ cnxn ≥ g(y) = b1y1 + ...+ bmym. Thật vậy, do x là phương án của bài toán (P ) và y là phương án của bài toán (Q) nên Ax = b, ATy ≤ c, x ≥ 0. Từ đó ta có f(x) = 〈c, x〉 ≥ 〈ATy, x〉 = 〈y,Ax〉 = 〈y, b〉 = g(y). 10 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Định lý 1.6. (Đối ngẫu mạnh) Nếu một qui hoạch có phương án tối ưu thì qui hoạch đối ngẫu của nó cũng có phương án tối ưu và giá trị tối ưu của chúng là bằng nhau. Định lý 1.7. (Định lý yếu về độ lệch bù) Một cặp phương án x, y của hai qui hoạch đối ngẫu (P) và (Q) là những phương án tối ưu khi và chỉ khi chúng nghiệm đúng các hệ thức: yi  n∑ j=1 aijxj − bi  = 0 với mọi i = 1, 2, ...,m, (1.1) xj ( cj − m∑ i=1 aijyi ) = 0 với mọi j = 1, 2, ..., n. (1.2) Ta thấy n∑ j=1 aijxj − bi là độ lệch (mức chênh lệch giữa vế trái và vế phải) ở ràng buộc i trong bài toán gốc (P ), yi là biến đối ngẫu tương ứng với ràng buộc này. Tương tự, cj − m∑ i=1 aijyi là độ lệch ở ràng buộc j trong bài toán đối ngẫu (Q) và xj là biến gốc tương ứng với ràng buộc này. Các hệ thức (1.1), (1.2) nói rằng với mỗi ràng buộc gốc hay đối ngẫu thì tích của độ lệch ở ràng buộc này và biến đối ngẫu (hay biến gốc) tương ứng với ràng buộc đó phải bằng không. Nói cách khác, nếu một ràng buộc có độ lệch dương thì biến (gốc hay đối ngẫu) tương ứng với ràng buộc đó phải bằng không; ngược lại, nếu một biến gốc hay đối ngẫu có giá trị dương thì phương án của bài toán đối ngẫu phải thỏa mãn ràng buộc tương ứng với dấu "=" (thỏa mãn như một đẳng thức). Như vậy, hệ thức (1.1) có nghĩa là n∑ j=1 aijxj > bi ⇒ yi = 0 và yi > 0⇒ n∑ j=1 aijxj = bi, i = 1, 2, ...,m. Hệ thức (1.2) cũng có nghĩa tương tự m∑ i=1 aijyi 0⇒ m∑ i=1 aijyi = cj, j = 1, 2, ..., n. 11 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Các đẳng thức (1.1), (1.2) không loại trừ khả năng là với một i nào đó ta có đồng thời yi = 0 và n∑ j=1 aijxj = bi. Tuy nhiên định lý sau cho thấy khả năng này không thể xảy ra đối với tất cả các cặp phương án tối ưu đối ngẫu. Định lý 1.8. (Định lý mạnh về độ lệch bù) Nếu cặp bài toán đối ngẫu (P) và (Q) có phương án thì tồn tại một cặp phương án tối ưu x∗, y∗ nghiệm đúng y∗ + (Ax∗ − b) > 0 và x∗ + (c− ATy∗) > 0. Tóm lại, chương này đã điểm lại những tính chất cơ bản của bài toán qui hoạch tuyến tính chính tắc, nêu điều kiện để bài toán có lời giải (phương án tối ưu) và điều kiện để một phương án của bài toán là phương án tối ưu. Bài toán vận tải xét ở các chương sau là một bài toán qui hoạch tuyến tính chính tắc và vì thế các kiến thức nêu ở chương này sẽ được áp dụng cho bài toán vận tải nói riêng. 12 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Chương 2 Bài toán vận tải với biến không âm Chương này đề cập tới bài toán vận tải dạng bảng, nó có dạng bài toán qui hoạch tuyến tính chính tắc. Do bài toán vận tải có cấu trúc đặc biệt nên nó có các tính chất riêng. Có thể khai thác các tính chất đó để xây dựng thuật toán giải hiệu quả. Chương gồm 5 mục. Trong mục 2.1, chúng tôi giới thiệu về bài toán vận tải và tính chất. Mục 2.2, trình bày cách tìm phương án cực biên ban đầu. Mục 2.3, nêu tiêu chuẩn tối ưu và mục 2.4, giới thiệu thuật toán thế vị. Trong mục 2.5, chúng tôi đưa ra ví dụ số để minh họa. Các khái niệm và kết quả trình bày trong chương này được tham khảo từ các tài liệu [1], [2] và [4]. 2.1 Bài toán vận tải và tính chất Giả sử cóm kho hàng A1, ..., Am (điểm phát) cùng chứa một loại hàng. Cần vận chuyển số hàng trên đến n cửa hàng B1, ..., Bn (điểm thu). Cước phí vận chuyển một đơn vị hàng từ điểm phát Ai đến điểm thu Bj là Cij. Vấn đề đặt ra là cần xác định nê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? Mô hình bài toán vận tải có dạng: m∑ i=1 n∑ j=1 cijxij → min (cực tiểu tổng chi phí vận chuyển), (2.1) với điều kiện 13 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên n∑ j=1 xij = ai, i = 1, 2, ...,m (mọi điểm phát giao hết hàng), (2.2) m∑ i=1 xij = bj, j = 1, 2, ..., n (mọi điểm thu nhận đủ hàng), (2.3) xij ≥ 0, i = 1, ...,m; j = 1, ..., n (lượng hàng vận chuyển không âm). (2.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 thứ i (i = 1, 2, ..., m). bj là lượng hàng cần (cầu) ở điểm thu thứ 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 đến đ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 (2.1) - (2.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. (2.5) Bài toán vận tải (2.1) - (2.4) là một dạng đặc biệt của bài toán qui hoạch tuyến tính. Để thấy rõ điều này ta sắp xếp các biến theo thứ tự x11, ..., x1n, x21, ..., x2n, ..., xm1, ..., xmn. Và viết lại hệ ràng buộc (2.2) - (2.3) dưới dạng hệ m + n phương trình của m x n biến số xij như sau: 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ộtm×n thành phần, 14 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên c = (c11, ..., c1n, c21, ..., c2n, ..., cm1, ..., cmn) T - véctơ cột m×n thành phần, b = (a1, ..., am, b1, ...bn) T - véctơ cột vế phải (m+ n thành phần). Bài toán vận tải (2.1) - (2.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 =→ min, (2.6) Ax = b, x ≥ 0. (2.7) 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 (2.2) - (2.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 của (2.1) gọi là một 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 ma trận A ứng với các véctơ xij > 0 là độc lập tuyến tính (xem Định lý 1.2). Sau đây ta sẽ giả thiết có điều kiện cân bằng thu phát (2.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ế chỉ có nhiều nhất m + n − 1 thành phần dương, vì trong số các ràng buộc chính của bài toán 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. Với điều kiện (2.5) bài toán vận tải (2.1) - (2.4) có các tính chất sau: 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 (bị chặn). 2. Một trong các ràng buộc (2.4) - (2.5) 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. 15 Số hóa bởi Trung tâm Học liệu – Đại học Thá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ả. Trong số đó có thuật toán thế vị mà ta sẽ đề cập tới ở trong muc 2.4 dưới đây. 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 bao gồm: m hàng (i = 1, 2, ..., m) và n cột