ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRỊNH THỊ THANH HẢO BÀI TỐ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 Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mục lục Lời cảm ơn Lời nói đầu Bài 1.1 1.2 1.3 1.4 toán qui hoạch tuyến Phát biểu toán Sự tồn nghiệm Phương án cực biên Bài toán đối ngẫu tính dạng tắc Bài tốn vận tải với biến khơng âm 2.1 Bài tốn vận tải tính chất 2.2 Tìm phương án cực biên ban đầu 2.3 Tiêu chuẩn tối ưu 2.4 Thuật toán vị 2.5 Ví dụ minh họa Bài 3.1 3.2 3.3 3.4 3.5 tốn vận tải có vận chuyển ngược Vận chuyển ngược có lợi ích gì? Mơ hình tốn vận tải có vận chuyển ngược Điều kiện tối ưu Thuật toán giải toán (P) Ví dụ minh họa 7 8 13 13 18 21 26 28 32 32 33 36 38 40 Kết luận 45 Tài liệu tham khảo 46 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Lời cảm ơn Luận văn hoàn thành Trường Đại học Khoa học, Đại học Thái Nguyên hướng dẫn GS.TS Trần Vũ Thiệu Tác giả xin bày tỏ lịng kính trọng biết ơn sâu sắc tới thầy tận tình hướng dẫn suốt thời gian tác giả làm luận văn Trong trình học tập làm luận văn, thông qua giảng xêmina, tác giả thường xuyên nhận quan tâm giúp đỡ đóng góp ý kiến quý báu GS,TS 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ả xin gửi tới TS Nguyễn Thị Thu Thủy thầy cô trường Đại học Khoa học - Đại học Thái Ngun Từ đáy lịng mình, tác giả xin bày tỏ lòng biết ơn sâu sắc đến thầy Tác giả xin bày tỏ lịng biết ơn tới thầy, cô, Ban giám hiệu nhà trường, Ban chấp hành Đồn, đồng nghiệp cơng tác quan tạo điều kiện thuận lợi giúp đỡ tác giả thời gian học tập 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 bạn bè đồng nghiệp gần xa trao đổi, động viên khích lệ tác giả q trình học tập, nghiên cứu làm luận văn Luận văn khơng hồn thành khơng có thơng cảm, giúp đỡ người thân gia đình tác giả Đây quà tinh thần, tác giả xin kính tặng gia đình thân u với lòng biết ơn chân thành sâu sắc Số hóa Trung tâm Học liệu – Đại học Thái Ngun http://www.lrc-tnu.edu.vn Lời nói đầu Bài tốn vận tải (Transportation problem) qui hoạch tuyến tính quen thuộc toán học ứng dụng Trong toán vận tải dạng bảng cho phép vận chuyển hàng từ trạm phát tới trạm thu, không vận chuyển theo chiều ngược lại (từ trạm thu tới trạm phát) Lời giải thu không cho chi phí vận chuyển nhỏ Đó lời giải xác định chi phí nhỏ cần để vận chuyển đơn vị hàng từ trạm phát tới trạm thu Muốn vậy, cần giải tốn phụ trợ: tìm đường ngắn cặp trạm thu - phát Có thể mở rộng toán vận tải cách cho phép vận chuyển hàng theo chiều ngược lại từ trạm thu tới trạm phát Từ dẫn đến mơ hình tốn vận tải có vận chuyển ngược (Transportation problem with reshipments) Mơ hình khác cũ chỗ: biến biểu thị lượng hàng vận chuyển lấy giá trị âm 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 làm giảm chi phí vận chuyển Luận văn nghiên cứu đề xuất thuật toán giải cho toán vận tải có vận chuyển ngược, dựa sở trả lời số câu hỏi như: tính chất cho tốn vận tải thơng thường cịn cho tốn vận tải có vận chuyển ngược, tiêu chuẩn tối ưu thay đổi mở rộng thuật tốn vị cho tốn khơng Nội dung luận văn chia thành ba chương Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chương với tiêu đề "Bài tốn qui hoạch tuyến tính dạng tắc" nhắc lại kiến thức tốn qui hoạch tuyến tính tắc: điều kiện tồn nghiệm tốn, tính chất phương án cực biên, toán đối ngẫu quan hệ đối ngẫu qui hoạch tuyến tính Do tốn vận tải có dạng tốn qui hoạch tuyến tính tắc nên áp dụng kiến thức cho toán vận tải Chương 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 tính chất toán vận tải với biến lấy giá trị khơng âm Tiếp đó, luận văn trình bày sở lý luận nội dung thuật toán vị (một biến thể thuật toán đơn hình) giải hiệu tốn vận tải Để áp dụng thuật tốn, địi hỏi biết phương án cực biên ban đầu tốn Vì cách tìm phương án cực biên ban đầu (theo cước phương pháp góc Tây - Bắ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 tốn vận tải nói chung thuật tốn vị nói riêng cần đến chương sau, xét tốn vận tải có vận chuyển ngược Chương với tiêu đề "Bài tốn vận tải có vận chuyển ngược" đề cập tới mở rộng toán vận tải với biến không âm, cho phép vận chuyển hàng theo chiều ngược lại từ trạm thu tới trạm phát Mơ hình tốn vận tải có vận chuyển ngược có dạng tốn qui hoạch lồi ràng buộc tuyến tính với biến lấy giá trị tùy ý (dương, âm hay 0) 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 mơ hình, chương nêu cách đưa tốn vận tải có vận chuyển ngược tốn qui hoạch tuyến tính tắc với cấu trúc gần giống toán vận tải thơng thường Từ nêu điều kiện tối ưu đề xuất thuật toán vị mở rộng giải tố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 chương hình thành dựa ý tướng nêu tài liệu [5] tác giả luận văn trình bày chi tiết báo Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn đăng Tạp chí Khoa học Cơng nghệ Đại học Thấi Nguyên, Tập 90, số 02, 2012, trang 107 - 112 Do thời gian kiến thức hạn nên luận văn dừng lại vịêc tìm hiểu, tập hợp tài liệu, xếp trình bày kết nghiên cứu có theo chủ đề đặt Trong trình viết luận văn trình xử lý văn chắn khơng thể tránh khỏi sai sót, mong nhận ý kiến đóng góp Thầy bạn đọc Tác giả Trịnh Thị Thanh Hảo Số hóa Trung tâm Học liệu – Đại học Thái Ngun http://www.lrc-tnu.edu.vn Chương Bài tốn qui hoạch tuyến tính dạng tắc Chương nhắc lại số khái niệm tính chất tốn qui hoạch tuyến tính dạng tắc Cụ thể xét tồn nghiệm tốn, tính chất phương án cực biên vấn đề đối ngẫu qui hoạch tuyến tính Các kiến thức cần đến cho chương sau Nội dung chương tham khảo chủ yếu từ tài liệu [1], [2] [6] 1.1 Phát biểu tốn Bài tốn tắc có dạng:  n   f (x) ≡ cj xj → min,    j=1   n aij xj = bi , i = 1, 2, , m,    j=1     xj ≥ 0, j = 1, 2, , n Trong toán aij , bi , cj số thực cho trước, f (x) gọi n aij xj = bi gọi ràng buộc chính, hàm mục tiêu Mỗi đẳng thức j=1 bất đẳng thức xj ≥ gọi ràng buộc dấu (Đặc điểm tốn tắc ràng buộc đẳng thức biến không âm) Điểm thỏa mãn ràng buộc gọi điểm chấp nhận được, hay phương án Tập hợp tất phương án, ký hiệu D, gọi miền Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ràng buộc hay miền chấp nhận Một phương án đạt cực tiểu hàm mục tiêu gọi phương án tối ưu hay lời giải toán cho 1.2 Sự tồn nghiệm Đinh lý sau cho điều kiện cần đủ để toán qui hoạch tuyến tính có lời giải Định lý 1.1 (Về tồn lời giải toán qui hoạch tuyến tính) Nếu qui hoạch tuyến tính có phương án hàm mục tiêu bị chặn miền ràng buộc (đối với tốn min) tốn chắn có phương án tối ưu Nhận xét 1.1 Kết luận định lý nói chung khơng cịn với tốn khơng phải qui hoạch tuyến tính (hàm mục tiêu khơng phải tuyến tính miền ràng buộc khơng phải tập lồi đa diện) Để rõ ta xét ví dụ cụ thể sau: Ví dụ 1.1 f = x2 → , với điều kiện x1 x2 ≥ 1, x1 ≥ Miền chấp nhận D = x ∈ R2 : x1 x2 ≥ 1, x1 ≥ tập lồi khác rỗng hàm mục tiêu bị chặn miền này: x2 ≥ với x = (x1 , x2 ) ∈ D Điểm (1/ε, ε) ∈ D với ε > 0, khơng có (x1 , 0) ∈ D.Vì cận x2 không đạt điểm thuộc D Cũng lấy ví dụ với hàm mục tiêu phi tuyến miền ràng buộc tập lồi đa diện cho thấy định lý không Ví dụ 1.2 Cho hàm f (x) = 1+x2 , x ∈ R Ta thấy f (x) ≥ 0, ∀x ∈ R inf f (x) = Hàm không đạt cực x∈R tiểu R 1.3 Phương án cực biên Một phương án x ∈ D mà đồng thời đỉnh D gọi phương án cực biên, nghĩa x biểu diễn dạng tổ hợp lồi hai phương án khác D Nói cách khác, x = λx1 + (1 − λ)x2 với < λ < x1 , x2 ∈ D phải có x0 = x1 = x2 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Định lý sau nêu tính chất đặc trưng phương án cực biên tốn qui hoạch tuyến tính tắc Định lý 1.2 Để phương án x0 = x01 , x02 , , x0n toán qui hoạch dạng tắc phương án cực biên, cần đủ véctơ cột Aj ma trận A ứng với thành phần x0j > độc lập tuyến tính Hệ 1.1 Số phương án cực biên tốn qui hoạch tuyến tính dạng tắc hữu hạn Hệ 1.2 Số thành phần dương phương án cực biên tốn qui hoạch tuyến tính dạng tắc tối đa m (m số hàng ma trận A) Người ta phân hai loại phương án cực biên: phương án cực biên có số thành phần dương m, gọi phương án cực biên khơng suy biến Trái lại, gọi phương án cực biên suy biến Định lý 1.3 Nếu tốn qui hoạch tuyến tính dạng tắc có phương án có phương án cực biên (miền ràng buộc D có đỉnh) Định lý 1.4 Nếu tốn qui hoạch tuyến tính dạng tắc có phương án tối ưu có phương án cực biên tối ưu 1.4 Bài toán đối ngẫu Đối ngẫu phương pháp mà ứng với tốn qui hoạch tuyến tính cho (gọi tốn gốc), ta thiết lập tốn qui hoạch tuyến tính khác (gọi tốn đối ngẫu) cho từ lời giải toán ta thu thông tin lời giải tốn Vì thế, đơi để có hiểu biết cần thiết toán việc nghiên cứu tốn đối ngẫu lại tỏ thuận tiện Hơn nữa, phân tích đồng thời hai tốn gốc đối ngẫu ta rút kết luận sâu sắc mặt toán học lẫn ý nghĩa thực tiễn Ta định nghĩa đối ngẫu toán qui hoạch tuyến tính tắc, ký hiệu tốn (P): f (x) = c1 x1 + c2 x2 + + cn xn → min, Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ai1 x1 + ai2 x2 + + ain xn = bi , i = 1, 2, , m, xj ≥ 0, j = 1, 2, , n, toán, ký hiệu toán (Q): g(y) = b1 y1 + b2 y2 + + bm ym → max, a1j y1 + a2j y2 + + amj ym ≤ cj , j = 1, 2, , n Ở đây, ràng buộc có dấu "=" nên biến đối ngẫu tương ứng khơng có ràng buộc dấu (các biến yi có dấu tùy ý) Dưới dạng véctơ -ma trận, ta viết Bài tốn gốc: f (x) =< c, x >→ Ax = b, x ≥ Bài toán đối ngẫu: g(y) =< b, y >→ max AT y ≤ c Định lý 1.5 (Đối ngẫu yếu) Nếu x phương án toán gốc (P ) y phương án toán đối ngẫu (Q) f (x) = c1 x1 + + cn xn ≥ g(y) = b1 y1 + + bm ym Thật vậy, x phương án toán (P ) y phương án toán (Q) nên Ax = b, AT y ≤ c, x ≥ Từ ta có f (x) = c, x ≥ AT y, x = y, Ax = y, b = g(y) 10 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chương Bài tốn vận tải có vận chuyển ngược Chương xét mở rộng toán vận tải với biến khơng âm trình bày chương trước Bằng cách cho phép vận chuyển hàng theo chiều ngược lại từ trạm thu tới trạm phát dẫn đến mơ hình tốn có vận chuyển ngược Mục 3.1 nêu lý cần vận chuyển ngược Mục 3.2 nêu mơ hình tốn học tốn xét tính chất nghiệm tốn Mục 3.3 đưa điều kiện tối ưu Cuối chương Mục 3.4 đề xuất thuật toán giải sở mở rộng thuật toán vị quen thuộc ví dụ số xây dựng Mục 3.5 Nội dung chương hình thành dựa ý tướng nêu tài liệu tham khảo [5] tác giả luận văn trình bày chi tiết báo đăng Tạp chí Khoa học Đại học Thái Nguyên [7] 3.1 Vận chuyển ngược có lợi ích gì? Giả sử cần vận chuyển loại hàng (xi măng chẳng hạn) từ hai kho A B (gọi trạm phát), kho có 150 tấn, tới hai hộ tiêu thụ I II (gọi trạm thu) Hộ I cần 100 tấn, hộ II cần 200 Chi phí vận chuyển hàng từ trạm phát tới trạm thu cho ma trận C, hàng đại diện cho kho hàng cột đại diện cho hộ tiêu thụ (đơn vị qui ước: $1 / tấn): 32 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn C= ; X= 100 50 150 ; Y = 150 −50 200 X Y phương án tối ưu tốn khơng có vận chuyển ngược tốn có vận chuyển ngược Phương án Y cho thấy có vận chuyển ngược 50 hàng từ hộ I kho B Đáng ý chi phí vận chuyển theo phương án X $1000, theo phương án Y chi phí vận chuyển giảm cịn $950 Lý vì: Phương án X vận chuyển 50 hàng tuyến có cước phí vận chuyển đắt từ kho A tới hộ II (mỗi hàng tốn $7) Phương án Y không chuyển hàng tuyến (mỗi hàng tiết kiệm $7) mà chuyển thêm 50 từ kho A tới hộ I (mỗi hàng tốn thêm $2), sau chuyển ngược từ hộ I kho B (mỗi hàng tốn thêm $1) cuối chuyển 50 hàng từ kho B tới hộ II (mỗi hàng tốn thêm $3) Tổng cộng, tốn thêm $2 + $1 + $3 = $6 cho hàng Nếu so với số tiền tiết kiệm ($7 cho hàng) cịn tiết kiệm $7 - $6 = $1 cho hàng Có tất 50 hàng vận chuyển ngược theo cách nên tổng số tiền tiết kiệm $50 Điều giải thích chi phí vận chuyển giảm từ $1000 xuống cịn $950 Như vậy, $7 khơng phí vận chuyển rẻ cho đơn vị hàng từ kho A tới hộ II, mà $6 (đi từ kho A tới hộ I, qua kho B để tới hộ II) Tình trạng xảy chi phí bảng vận tải tạo ngẫu nhiên Chính cần xét tốn vận tải có vận chuyển ngược để giảm chi phí vận chuyển 3.2 Mơ hình tốn vận tải có vận chuyển ngược Nội dung tốn vận tải: Giả sử cần vận chuyển loại hàng từ m điểm cung cấp (gọi trạm phát), ký hiệu i = 1, 2, , m, đến n điểm tiêu thụ (gọi trạm thu), ký hiệu j = 1, 2, , n Cho biết khả cung cấp hàng trạm phát i > 0, nhu cầu tiêu thụ hàng trạm thu j bj > chi phí vận chuyển đơn vị hàng từ trạm phát i tới trạm thu j (và ngược lại) cij ≥ Để tốn có nghiệm ta giả thiết a1 + a2 + + am = b1 + b2 + + bn (điều kiện cân cung cầu) Với toán vận tải có vận chuyển ngược, ta cần xác định biến 33 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn xij (i = 1, , m; j = 1, , n), biểu thị số lượng hàng vận chuyển từ trạm phát i tới trạm thu j xij ≥ số lượng hàng chuyển ngược từ trạm thu j tới trạm phát i xij < Chi phí vận chuyển tương ứng cij |xij | Khi đó, mơ hình tốn học tốn vận tải có vận chuyển ngược có dạng: m n cij |xij | → (cực tiểu tổng chi phí vận chuyển) (P) f (x) = i=1 j=1 với điều kiện: n ∀ i = 1, ,m (trạm phát i giao hết hàng) xij = , j=1 m xij = bj , ∀ j = 1, ,n (trạm thu j nhận đủ hàng) i=1 xij ∈ R, ∀i = 1, , m; j = 1, , n Mơ hình khác mơ hình tốn vận tải dạng bảng biết chỗ: biến biểu thị lượng hàng vận chuyển lấy giá trị âm hàm mục tiêu sử dụng dấu giá trị tuyệt đối Dễ thấy (P) toán qui hoạch lồi với ràng buộc tuyến tính (xem [3]) Tuy nhiên, nhờ đặc điểm kể trên, ta đưa (P) dạng tốn qui hoạch tuyến tính tắc, nhờ dùng kỹ thuật đổi biến số Trước hết ta để ý số thực viết dạng hiệu hai số thực không âm, chọn cách viết cho hai số Chẳng hạn, số hiệu (5 = 0), số - hiệu (- = - 5) Vì thế, xij ∈ R viết thành xij = yij − zij với yij ≥ 0, zij ≥ yij zij = Cụ thể, xij ≥ yij = xij ≥ zij = 0, cịn xij < yij = zij = −xij > Trong hai trường hợp ta có cij |xij | = cij (yij + zij ) Vì viết lại tốn (P) dạng tốn qui hoạch tuyến tính tắc sau, gọi tắt tốn (Q): m n cij (yij + zij ) → (Q) i=1 j=1 34 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn (3.1) với điều kiện: n n yij − j=1 j=1 m m yij − i=1 zij = , ∀ i = 1, ,m (3.2) zij = bj , ∀ j = 1, ,n (3.3) i=1 yij ≥ 0, zij ≥ 0, ∀ i = 1, , m; j =1, , n (3.4) Giả thiết (P), (Q), thỏa mãn điều kiện cân cung cầu nêu Nhận xét 3.1 Khi cho zij = ràng buộc (Q) trở thành ràng buộc toán vận tải theo biến yij , tập ràng buộc (Q) khác rỗng Hàm mục tiêu (Q) bị chặn số (do cij ,yij ,zij ≥ 0) nên theo lý thuyết qui hoạch tuyến tính (xem Định lý 1.1), (Q) có nghiệm cực tiểu Hơn nữa, nghiệm cực tiểu đạt đỉnh tập lồi đa diện ràng buộc (Q) (tập có đỉnh (Q) có dạng tắc) Nhận xét 3.2 Trong tốn (Q) ký hiệu Aij ∈ Rm+n (Bij ∈ Rm+n ) véctơ hệ số biến yij (biến zij ) thấy Aij có thành phần i m + j 1, thành phần khác Bij = −Aij với i = 1, , m, j = 1, , n Do phương án cực biên (tức đỉnh tập ràng buộc) (Q) khơng thể có đồng thời yij > zij > (vì phương án cực biên toán tắc, véctơ hệ số Aij Bij , tương ứng với thành phần dương, phải độc lập tuyến tính) Chính tốn (Q) ta không cần viết điều kiện yij zij = Vậy hai toán (P) (Q) tương đương Nhận xét 3.3 Với phương án cực biên {yij , zij } (Q) xij = yij − zij có dạng:  yij = zij = 0,   yij yij > 0, zij = 0, xij = (3.5)   −zij yij = 0, zij > Để cho tiện, ta gọi x0 = x0ij xác định theo (3.5) phương án (Q) Giống tốn vận tải khơng có vận chuyển ngược, 35 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn tập hợp ô tương ứng với yij > zij > 0, tức xij = 0, gồm không m + n − khơng chứa chu trình 3.3 Điều kiện tối ưu Có thể thấy đối ngẫu (Q) toán sau (các biến ui vj gọi vị): n m bj vj → max ui + g (u, v) = (D) i=1 j=1 với điều kiện ui + vj ≤ cij và−ui − vj ≤ cij ∀i = 1, , m, j = 1, , n hay −cij ≤ ui + vj ≤ cij hay |ui + vj | ≤ cij ∀i = 1, , m, j = 1, , n (3.6) Từ lý thuyết đối ngẫu qui hoạch tuyến tính (xem [1]) suy điều kiện cần đủ để phương án cực biên x0 = yij0 , zij0 phương án tối ưu Định lý 3.1 (Điều kiện tối ưu) Phương án cực biên x0 = yij0 , zij0 (Q) tối ưu tìm số ui (i = 1, , m) vj (j = 1, , n) thỏa mãn: a) |ui + vj | ≤ cij b) ui +vj = cij ∀i = 1, , m, j = 1, , n (3.7) yij > ui +vj = −cij zij > (3.8) Chứng minh Điều kiện cần Giả sử x0 phương án cực biên tối ưu toán (Q) Theo định lý đối ngẫu mạnh (Định lý 1.6), toán đối ngẫu (D) có phương án tối ưu (u, v) = (u1 , , um , v1 , , )T Do (u, v) phương án chấp nhận tốn đối ngẫu (D) nên thỏa mãn (3.6), tức |ui + vj | ≤ cij ∀i = 1, , m, j = 1, , n Đây điều kiện (3.7) Hơn nữa, x0 ≡ y , z phương án tối ưu toán gốc (Q) (u, v) phương án tối ưu toán đối ngẫu (D) nên theo định lý yếu độ lệch bù (Định lý 1.7) ta có: yij0 > ui + vj = cij , cịn zij0 > −ui − vj = cij , tức điều kiện (3.8) thỏa mãn 36 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Điều kiện đủ Cho phương án cực biên x0 = yij0 , zij0 Giả sử tồn số ui (i = 1, , m) vj (j = 1, , n) thỏa mãn điều kiện (3.7) (3.8) Ta chứng minh x0 phương án tối ưu toán (Q) Thật vậy, theo (3.5) (3.8) ta có: + cij yij0 + zij0 = (ui + vj ) yij0 − zij0 = (ui + vj ) x0ij với yij0 = zij0 = + cij yij0 + zij0 = (ui + vj ) yij0 − zij0 = (ui + vj ) x0ij với yij0 > 0, zij0 = + cij yij0 + zij0 = − (ui + vj ) −yij0 + zij0 = (ui + vj ) x0ij với yij0 = 0, zij0 > Do theo (3.1) giá trị hàm mục tiêu (Q) x0 = yij0 , zij0 m n m cij yij0 f (x ) = + zij0 n (ui + vj ) x0ij = i=1 j=1 (3.7) i=1 j=1 Giả sử x ¯ = (¯ xij ) = (¯ yij , z¯ij ) phương án cực biên tốn (Q) Theo (3.6) ta có: + cij (¯ yij + z¯ij ) = (ui + vj ) (¯ yij − z¯ij ) = với y¯ij = z¯ij = + cij (¯ yij + z¯ij ) ≥ (ui + vj ) (¯ yij − z¯ij ) với y¯ij > 0, z¯ij = + cij (¯ yij + z¯ij ) ≥ − (ui + vj ) (−¯ yij + z¯ij ) = (ui + vj ) (¯ yij − z¯ij ) với y¯ij = 0, z¯ij > Do theo (3.1) giá trị hàm mục tiêu (Q) x ¯ = (¯ yij , z¯ij ) m m n n cij (¯ yij + z¯ij ) ≥ f (¯ x) = i=1 j=1 m = n n (¯ yij − z¯ij ) + ui i=1 (ui + vj ) (¯ yij − z¯ij ) i=1 j=1 j=1 m (¯ yij − z¯ij ) vj j=1 i=1 37 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn n m vj bj (vì x¯ = (¯ yij , z¯ij ) phương án (Q)) ui + = j=1 i=1 m n ui = i=1 m j=1 n = i=1 j=1 yij0 − zij0 n m vj + j=1 i=1 (ui + vj ) yij0 − zij0 = m yij0 − zij0 n i=1 j=1 theo (3.2)-(3.3) y , z (ui + vj )x0ij = f (x0 )(theo (3.9)) Vậy x0 = yij0 , zij0 phương án tối ưu toán (Q) 3.4 Thuật tốn giải tốn (P) Để tiện tính toán, ta ghi lại liệu (P) dạng bảng chữ nhật, gọi bảng vận tải (Bảng 3.1) Bảng gồm m hàng (i = 1, , m) n cột (j = 1, , n) Mỗi hàng tương ứng với trạm phát, cột tương ứng với trạm thu Số ghi đầu hàng lượng cung, số ghi đầu cột lượng cầu Chỗ giao hàng i, cột j bảng ký hiệu ô (i, j) Chi phí vận chuyển cij ghi góc bên trái ô (i, j), lượng hàng vận chuyển xij (có thể âm) ghi góc bên phải ô Ô (i, j) biểu thị tuyến đường vận chuyển từ trạm phát i tới trạm thu j xij ≥ từ j đến i xij < Sau ta nêu Thuật toán vị mở rộng giải toán (P), gồm bước: Bước Xây dựng phương án cực biên ban đầu x0 = {x0ij }, chẳng hạn theo phương pháp cước phương pháp góc Tây Bắc Đặt G0 = (i, j) : x0ij = Giả thiết x0 không suy biến, nghĩa G0 gồm m + n − G0 khơng chứa chu trình Các thuộc G0 gọi ô chọn, ô khác gọi ô loại Đặt số bước lặp k = Bước Tính vị ui , i = 1, ,m vj , j = 1, , n tương ứng với phương án cực biên xk nhờ giải hệ phương trình có dạng tam giác (đặt u1 = 0): ui + vj = cij với (i, j) ∈ Gk , xkij ≥ ui + vj = −cij với (i, j) ∈ Gk , xkij < 38 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Hình 3.1: Bảng vận tải Bước Tính ước lượng ∆ij = ui + vj − cij δij = ui + vj + cij với (i, j) Bước Nếu ∆ij ≤ δij ≥ với (i, j) dừng thuật tốn: xk phương án tối ưu (P) Trái lại, thực Bước Bước (Điều chỉnh phương án): a) Xác định ô điều chỉnh (r, s) thỏa mãn ∆rs = γ γ = ∆ δrs = γ γ = δ , γ = max(∆, δ) với ∆ = max{∆ij : ∀(i, j)} δ = max{−δij : ∀(i, j)} b) Tìm chu trình điều chỉnh C tạo ô (r, s) với ô thuộc Gk , chẳng hạn cách loại dần ô treo hàng cột c) Phân loại ô thuộc chu trình C thành lẻ C1 chẵn C2 xen kẽ theo qui tắc: (r, s) ô lẻ (∈ C1 ) γ = ∆rs ; (r, s) ô chẵn (∈ C2 ) γ = δrs d) Xác định lượng điều chỉnh h ≡ xkpq = xkij : (i, j) ∈ C1 \(r, s), xkij < 0, (i, j) ∈ C2 \(r, s), xkij ≥ ≥ e) Xây dựng phương án cực biên xk+1 với  xkij (i, j) ∈ / C,    k xk+1 = xij + h (i, j) ∈ C1 , ij    xkij − h (i, j) ∈ C2 Gk+1 = (Gk \(p, q)) ∪ (r, s) ⊃ (i, j) : xkij = 39 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Quay lại thực Bước Nhận xét 3.4 Nếu tốn (P) khơng suy biến thuật toán nêu hữu hạn, tức sau số hữu hạn phép tính ta nhận nghiệm tối ưu (P) Nhận xét 3.5 Nếu lượng phát , i = 1, , m lượng thu bj , j = 1, , n số ngun tốn (P) có nghiệm tối ưu với thành phần nguyên 3.5 Ví dụ minh họa Giải tốn (P) phương pháp vị mở rộng với véctơ cung a, véctơ cầu b, ma trận chi phí C = {cij } phương án cực biên xuất phát x0 = {x0ij } (xây dựng theo phương pháp cước) sau: a =( 50 40 60 )T , b = ( 25 30    10    C =  10 12  , x0 =  25 20 10 15 40 55 )T ,  30 20 0 15   20 40 Giải Ví dụ có m = trạm phát n = trạm thu thỏa mãn điều kiện cân cung cầu Phương án x0 có tập chọn tương ứng G0 = { (1, 2) , (1, 3) , (2, 1) , (2, 4) , (3, 3) , (3, 4) } gồm ô không chứa chu trình giá trị hàm mục tiêu f (x0 ) = 950 Vòng lặp Bước Các vị tương ứng với x0 : u0 = ( −5 )T , Bước Các số ∆ij = ui + vj trận ∆0 δ đây:  0 −3  ∆0 =  −14 −15 −5 0 v = ( 7 )T − cij δij = ui + vj + cij ghi ma   12 17   δ =   > 35 12 20 30   , 40 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Bước Phương án x0 chưa tối ưu cịn ∆11 = > ∆32 = > Bước a) ∆ = 6, δ = −2, γ = max(∆, δ) = ∆ = Ô điều chỉnh (r, s) = (3, 2) b) Chu trình điều chỉnh C gồm ô (3, 2), (1, 2), (1, 3), (3, 3) c) Các ô lẻ C1 gồm (3, 2) (1, 3) Các ô chẵn C2 gồm (1, 2) (3, 3) d) Lượng điều chỉnh h = min(x012 = 30, x033 = 20) = x033 = 20 Ô loại (p, q) = (3, e) Phương án cực biên mới:  10  x1 =  25 0 20 3)  40 0 15   40 G1 = {(1, 2) , (1, 3) , (2, 1) , (2, 4) , (3, 2) , (3, 4)} f (x1 ) = 830 < f (x0 ) = 950 Vòng lặp Bước Thế vị tương ứng với x1 : u1 = ( −11 )T , v = ( 13 13 )T Bước Các số ∆ij = ui + vj − cij δij = ui + vj + cij ghi ma trận ∆1 δ đây:  0   ∆1 =  −20 −21  , −5 −6   18 23   δ =  4  > 35 14 30  Bước Phương án x1 chưa tối ưu cịn ∆11 = > ∆14 = > Bước a) ∆ = 8, δ = −2, γ = max(∆, δ) = ∆ = Ô điều chỉnh (r, s) = (1, 1) b) Chu trình điều chỉnh C gồm ô (1, 1), (1, 2), (3, 2), (3, 4), (2, 4) (2, 1) c) Các ô lẻ C1 gồm (1, 1), (3, 2) (2, 4) Các ô chẵn C2 gồm (1, 2), (3, 4) (2, 1) 41 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn d) Lượng điều chỉnh h = min(10, 40, 25) = x112 = 10 Ô loại (p, q) = e) Phương án cực biên mới:  10  x2 =  15 (1, 2)  40 0 25   30 30 G2 = {(1, 1) , (1, 3) , (2, 1) , (2, 4) , (3, 2) , (3, 4)} f (x2 ) = 750 < f (x1 ) = 830 Vòng lặp Bước Thế vị tương ứng với x2 : u2 = ( −3 10 )T , v = ( −7 )T Bước Các số ∆ij = ui + vj − cij δij = ui + vj + cij ghi ma trận ∆2 δ đây:  −8 −5   ∆2 =  −20 −13  , −5   10 −6 15   δ =  11  35 22 30  Bước Phương án x2 chưa tối ưu cịn ∆33 = > δ12 = −6 < Bước a) ∆ = 2, δ = 6, γ = max(∆, δ) = δ = Ô điều chỉnh (r, s) = (1, 2) b) Chu trình điều chỉnh C gồm (1, 1), (1, 2), (3, 2), (3, 4), (2, 4) (2, 1) c) Các ô lẻ C1 gồm (1, 1), (3, 2) (2, 4) Các ô chẵn C2 gồm(1, 2), (3, 4) (2, 1) d) Lượng điều chỉnh h = min(x234 = 30, x221 = 15) = x221 = 15 Ô loại (p, q) = (2, 1) e) Phương án cực biên mới:   25 −15 40  0 40  x3 =   45 15 42 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn G3 = {(1, 1) , (1, 2) , (1, 3) , (2, 4) , (3, 2) , (3, 4)} , f (x3 ) = 660 < f (x2 ) = 750 Vòng lặp Bước Thế vị tương ứng với x3 : u3 = ( −9 )T , v = ( −1 11 )T Bước Các số ∆ij = ui + vj − cij δij = ui + vj + cij trận ∆3 δ đây:    −2 10    ∆3 =  −6 −20 −19  , δ =  −2 −11 −4 29 16 ghi ma  21   30 Bước Phương án x3 chưa tối ưu ∆14 = > δ21 = −2 < Bước a) ∆ = 1, δ = 2, γ = max(∆, δ) = δ = Ô điều chỉnh (r, s) = (2, 1) b) Chu trình điều chỉnh C gồm ô (1, 1), (1, 2), (3, 2), (3, 4), (2, 4) (2, 1) c) Các ô lẻ C1 gồm (1, 1), (3, 2) (2, 4) Các ô chẵn C2 gồm(1, 2), (3, 4) (2, 1) d) Lượng điều chỉnh h = min(x334 = 15) = x334 = 15 Ô loại (p, q) = (3, 4) e) Phương án cực biên mới:   40 −30 40  55  x4 =  −15  60 0 G4 = {(1, 1) , (1, 2) , (1, 3) , (2, 1), (2, 4) , (3, 2)} , f (x4 ) = 630 < f (x3 ) = 660 Vịng lặp 43 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Bước Thế vị tương ứng với x4 : u4 = ( −7 )T , v = ( −1 )T Bước Các số ∆ij = ui + vj − cij δij = ui + vj + cij ghi ma trận ∆4 δ đây:  −2 −1   ∆4 =  −4 −18 −17  , −11 −4 −2   10 19   δ4 =   29 16 28  Bước Phương án x4 tối ưu ∆4 ≤ δ ≥ (fmin = 630) Kết thúc thuật tốn Tóm lại, chương đề cập tới toán vận tải có vận chuyển ngược Mơ hình tốn học tốn khác mơ hình tốn vận tải thơng thường chỗ: biến có dấu tuỳ ý hàm mục tiêu có sử dụng dấu giá trị tuyệt đối Nhờ cấu trúc đặc biêt, tốn vận tải có vận chuyển ngược qui tốn qui hoạch tuyến tính tắc mà cấu trúc gần giống với tốn vận tải thơng thường Từ đưa điều kiện tối ưu đề xuất thuật toán giải, tương tự thuật toán vị giải toán vận tải Thuật tốn đề xuất có kèm theo ví dụ số minh hoạ 44 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Kết luận Bài toán vận tải dạng toán quen thuộc lý thuyết qui hoạch tuyến tính toán ứng dụng rộng rãi thực tiễn Bài tốn vận tải có nhiều dạng mở rộng khác Luân văn tập trung ý vào dạng mở rộng tốn vận tải có vận chuyển ngược, cho phép chuyển hàng ngược lại từ trạm thu tới trạm phát, nhờ làm giảm chi phí vận chuyển Luận văn trình bày nội dung cụ thể sau: Mơ hình tính chất tốn vận tải, quan hệ đối ngẫu, tiêu chuẩn tối ưu nghiệm thuật toán vị giải toán Mơ hình tốn vận tải có vận chuyển ngược, phân tích tính chất đặc thù tốn, nêu điều kiện tối ưu nghiệm toán đề xuất thuật toán giải toán sở mở rộng thuật tốn vị quen thuộc Có thể xem luận văn bước tìm hiểu toán vận tải thuật toán vị lý thuyết qui hoạch tuyến tính Thuật tốn đề xuất chương luận văn xem bước tập vận dụng kiến thức học vào giải tốn tối ưu đơn giản, có ý nghĩa thiết thực Tác giả luận văn hy vọng có dịp tìm hiểu sâu nội dung, thuật toán giải ý nghĩa thực tế nhiều toán tối ưu khác lý thuyết qui hoạch tốn học tương lai 45 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Tài liệu tham khảo [1] Trịnh Thị Thanh Hảo Bài toán vận tải có vận chuyển ngược Tạp chí Khoa hoc Công nghệ Đại hoc Thái Nguyên Tập 90, số 02, 2012, trang 107 - 112 [2] Nguyễn Thị Bạch Kim, Giáo trình phương pháp tối ưu - Lý thuyết thuật toán, Nxb Bách khoa, Hà Nội, 2008 [3] Trần Vũ Thiệu, Giáo trinh tối ưu tuyến tính Nxb Đại học Quốc gia Hà Nội, 2004 [4] Trần Vũ Thiệu, Nguyễn Thị Thu Thủy, Giáo trình tối ưu phi tuyến Nxb Đại học Quốc gia Hà Nội, 2011 [5] H A Eiselt, C L Sandblom Linear Programming and its Applications Springer, 2007 [6] S Gass Linear Programming and its Extensions 5th edi New York, 1988 [7] R J Vanderbei, Linear Programming - Foundations and Extensions 3rd edi Springer, 2008 46 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ... phí bảng vận tải tạo ngẫu nhiên Chính cần xét tốn vận tải có vận chuyển ngược để giảm chi phí vận chuyển 3.2 Mơ hình tốn vận tải có vận chuyển ngược Nội dung toán vận tải: Giả sử cần vận chuyển. .. toán vận tải có vận chuyển ngược Vận chuyển ngược có lợi ích gì? Mơ hình tốn vận tải có vận chuyển ngược Điều kiện tối ưu Thuật toán giải toán (P) ... tốn vận tải nói chung thuật tốn vị nói riêng cần đến chương sau, xét tốn vận tải có vận chuyển ngược Chương với tiêu đề "Bài toán vận tải có vận chuyển ngược" đề cập tới mở rộng tốn vận tải với