Luận văn Phương pháp giải bài toán tối ưu đa mục tiêu tuyến tính

Toán ứng dụng Mã số: 60 46 01 12 LUẬN VĂN THẠC SĨ KHOA HỌC Người hướng dẫn khoa học: PGS. TS. Tạ Duy Phượng Hà Nội - 2016 LỜI CẢM ƠN Trước khi trình bày nội dung của luận văn, tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc tới PGS. TS. Tạ Duy Phượng, người đã tận tình hướng dẫn, chỉ bảo tôi hoàn thành luận văn này. Tôi cũng xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy giáo, cô giáo công tác tại trường Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội, đã truyền đạt kiến thức cho tôi trong suốt quá trình học tập tại trường. Cuối cùng, tôi xin gửi lời cảm ơn tới các bạn đồng nghiệp và gia đình đã tạo mọi điều kiện thuận lợi nhất để tôi hoàn thành luận văn này. Xin chân thành cảm ơn! Hà Nội, ngày 04 tháng 12 năm 2016 Học viên Hồ Thị Thu Thủy 2 Mục lục Lời mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Chương 1. Kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1. Một số kết quả của giải tích lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.1. Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.2. Tập lồi đa diện . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2. Bài toán quy hoạch tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2.1. Bài toán quy hoạch tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2.2. Phương pháp đơn hình giải bài toán QHTT . . . . . . . . . . . . . . . . . . . . . . . . . 16 Chương 2. Bài toán tối ưu đa mục tiêu tuyến tính . . . . . . . . . . . . . . . . . . . . 23 2.1. Khái niệm và định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2. Phương pháp đơn hình giải bài toán tối ưu đa mục tiêu tuyến tính 28 2.2.1. Kiểm tra tính hữu hiệu của cơ sở hiện tại . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.2. Di chuyển của các đỉnh kề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Chương 3. Phương pháp đơn hình giải bài toán tối ưu đa mục tiêu tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.1. Bảng đơn hình đa mục tiêu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.1.1. Tìm nghiệm hữu hiệu cơ sở . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.1.2. Chuyển từ một đỉnh hữu hiệu sang các đỉnh kề hữu hiệu . . . . . . . . . . . . . 40 3.1.3. Tạo ra tất cả các đỉnh nghiệm hữu hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.1.4. Thuật toán đơn hình đối với bài toán đa mục tiêu . . . . . . . . . . . . . . . . . . . . 45 3.2. Phương pháp trọng số giải bài toán tối ưu đa mục tiêu tuyến tính 50 3.2.1. Thuật toán trọng số giải bài toán tối ưu đa mục tiêu tuyến tính . . . . . . . . 50 3.2.2. Thuật toán đơn hình chứa tham số của bài toán tối ưu hai mục tiêu tuyến tính. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3 3.2.3. Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4 LỜI MỞ ĐẦU Trong mọi lĩnh vực của cuộc sống, ta luôn quan tâm tới bài toán tìm ra phương án tốt nhất để đạt mục tiêu mong muốn trong những điều kiện ràng buộc nhất định. Các phương pháp tối ưu là công cụ đắc lực giúp người làm quyết định có những giải pháp tốt nhất về định lượng và định tính. Trong những năm gần đây, các phương pháp tối ưu hóa ngày càng được áp dụng sâu rộng và hiệu quả vào kinh tế, kỹ thuật, công nghệ thông tin và các ngành khoa học khác. Một trong những lớp bài toán tối ưu đầu tiên được nghiên cứu trọn vẹn cả về lý thuyết lẫn thuật toán là bài toán quy hoạch tuyến tính (QHTT). Quy hoạch tuyến tính ngay từ khi ra đời (vào cuối năm 30 - 40 của thế kỷ XX) đã chiếm vị trí quan trọng trong tối ưu hoá. Mô hình tuyến tính là mô hình rất phổ biến trong thực tế, đồng thời phụ phuộc tuyến tính là sự phụ thuộc đơn giản và dễ nghiên cứu về mặt toán học. Hơn nữa, về mặt lý thuyết, chúng ta có thể xấp xỉ với độ chính xác cao của bài toán phi tuyến bởi dãy các bài toán quy hoạch tuyến tính. Nói cách khác, các thuật toán giải QHTT là công cụ quan trọng trong việc nghiên cứu giải các bài toán phức tạp hơn. Bài toán quy hoạch đa mục tiêu cũng đã được phát triển thành một chuyên ngành toán học, bắt đầu từ những năm 1980. Nhằm giải đáp những câu hỏi đặt ra mà quy hoạch tuyến tính không giải được, chẳng hạn như trong một công ty ngoài mục tiêu nâng cao chất lượng sản phẩm thì công ty cũng chú trọng tới các mục tiêu khác như đa dạng hoá sản phẩm, già thành rẻ, doanh thu lớn,. . . Khách hàng khi chọn mua hàng thì muốn hàng rẻ, vừa có chất lượng cao, vừa có hình thức đẹp. Tóm lại, mục đích của bài toán quy hoạch tuyến tính đa mục tiêu là tối ưu đồng thời nhiều hàm mục tiêu độc lập với nhau trên một miền chấp nhận được. Trong quy hoạch đa mục tiêu, ta phải có khái niệm nghiệm tương ứng. Một phương án chấp nhận, được gọi là nghiệm hữu hiệu nếu không tồn tại một phương án chấp nhận được khác tốt hơn nó, ít nhất là theo một mục tiêu, còn các mục tiêu khác không tồi hơn. Đầu thế kỷ XX, Pareto đã sử dụng khái niệm này khi ông nghiên cứu phúc lợi và thu nhập của dân chúng. Ông đã lập luận như sau: "Nếu thu nhập của một nhóm dân cư tăng lên, nhưng thu nhập của một nhóm khác giảm xuống thì khi đó không thể so sánh "phúc lợi" của toàn xã hội. Đó là trường hợp không so sánh được. Nhưng có thể thấy rằng, phúc lợi xã hội sẽ tăng lên nếu thu nhập của ít nhất một nhóm người nào đó lớn lên, còn thu nhập của những nhóm khác không thấp xuống". Khái niệm nghiệm hữu hiệu do Pareto nêu ra đã được trình bày dưới ngôn ngữ toán học và sử 5 dụng trong quy hoạch đa mục tiêu. Khi k (k ≥ 2) , các hàm mục tiêu đều là hàm tuyến tính và miền ràng buộc là tập lồi đa diện khác rỗng trong Rk, ta nhận được bài toán quy hoạch tuyến tính đa mục tiêu. Cho tới nay, có rất nhiều thuật toán đưa ra để xác định một phần hoặc toàn bộ tập nghiệm hữu hiệu của bài toán, chẳng hạn: phương pháp vô hướng hoá, phương pháp tham số, phương pháp đơn hình đa mục tiêu và các dạng cải biên, phương pháp nón pháp tuyến,... Tuy nhiên, khối lượng tính toán của các thuật toán này tăng nhanh khi kích thước của bài toán quy hoạch tuyến tính đa mục tiêu (tức số ràng buộc của miền chấp nhận, số chiều của không gian quyết định và số hàm mục tiêu) tăng. Trong những năm gần đây nhiều nhà toán học đó chuyển sang nghiên cứu giải quyết bài toán quy hoạch tuyến tính đa mục tiêu. Luận văn này chủ yếu trình bày phương pháp đơn hình giải bài toán quy hoạch tuyến tính đa mục tiêu trong không gianRk, dựa trên giáo trình "Multiobjective Linear Programming: An Introduction" của GS. Đinh Thế Lục, Springer International Publishing Switzerland (2016); và bài giảng "Multiobjective Linear Programming Theory" của Matthias Ehrgott, The University of Auckland, New Zealand (2007). Nội dung chính của luận văn là trình bày các phương pháp đơn hình để giải bài toán quy hoạch tuyến tính, một trong những phương pháp phổ biến nhất trong toán học tính toán. Ngoài phần Mục lục, Mở đầu và Tài liệu trích dẫn nội dung chính của luận văn gồm ba chương. • Chương 1 dành cho việc giới thiệu một số khái niệm cơ bản về giải tích lồi, trình bày bài toán quy hoạch tuyến tính (QHTT) và phương pháp đơn hình giải bài toán quy hoạch tuyến tính một mục tiêu. • Chương 2 trình bày bài toán tối ưu đa mục tiêu tuyến tính. • Chương 3 trình bày phương pháp đơn hình và thuật toán giải bài toán tối ưu đa mục tiêu tuyến tính; phương pháp trọng số giải bài toán tối ưu đa mục tiêu tuyến tính và thuật toán đơn hình chứa tham số của bài toán tối ưu tuyến tính hai mục tiêu. Hà Nội, ngày 24 tháng 12 năm 2016 Học viên Hồ Thị Thu Thủy 6 Chương 1 Kiến thức chuẩn bị Chương này trình bày một số kiến thức cơ bản về giải tích lồi, giới thiệu về bài toán quy hoạch tuyến tính một mục tiêu. Các kiến thức được tham khảo từ các tài liệu [1], [2] và [4]. 1.1. Một số kết quả của giải tích lồi 1.1.1. Tập lồi Trong suốt luận văn này,Rn biểu thị không gian Euclide n-chiều của cột n -véctơ thực. Một phần tử x= (x1, . . . ,xn)T ∈ Rn là một véctơ cột của Rn. Cho hai điểm a= (a1, . . . ,an)T và b= (b1, . . . ,bn)T ∈ Rn. Đường thẳng đi qua hai điểm a và b là tập có dạng {x ∈ Rn : x= λa+(1−λ )b,λ ∈ R} . Tập [a,b] := {x ∈ Rn : x= λa+(1−λ )b,λ ∈ [0,1]} gọi là đoạn thẳng nối hai điểm a và b. Trong Rn siêu phẳng H = {x : 〈a,x〉= α} với a ∈ Rn\{0} và α ∈ R chia Rn thành hai nửa không gian đóng H− = {x : 〈a,x〉 5 α} , H+ = {x : 〈a,x〉 = α} , mỗi nửa không gian này ở về một phía của siêu phẳng và phần chung của chúng chính là siêu phẳng H. Tương tự, siêu phẳng H cũng chia Rn thành hai nửa không gian mở {x : 〈a,x〉 α} . 7 Định nghĩa 1.1.1. • Tập Q⊆Rn được gọi là tập afin nếu Q chứa trọn cả đường thẳng đi qua hai điểm bất kỳ của Q, tức là ∀a,b ∈ Q,λ ∈⇒ (1−λ )a+λb ∈ Q. • Bao afin (affine hull) của một Q ⊆ Rn tập là giao của tất cả các tập afin chứa Q. Đó là tập afin nhỏ nhất chứa Q, ký hiệu là a f f (Q). Định nghĩa 1.1.2. Giả sử Q⊆ Rn là một tập hợp khác rỗng. • Tập Q được gọi là tập lồi (convex set) nếu nó chứa trọn đoạn thẳng nối hai điểm bất kỳ thuộc Q, tức là với mọi x,y ∈ Q và mỗi số thực λ ∈ [0,1], thì ta có λx+(1−λ )y ∈ Q. (Hình 1.1) Hình 1.1: Tập lồi. • Giả sử x1, . . . ,xk ∈ Rn là k điểm của Q. Khi đó x= k ∑ i=1 λixi, với λi ≥ 0,∀i= 1, . . . ,k, k ∑ i=1 λi = 1, được gọi là một tổ hợp lồi của hệ véctơ {x1, . . . ,xk}. • Cho Q ⊂ Rn là một tập bất kỳ. Bao lồi (convex hull) của Q, ký hiệu là conv(Q) (Hình 1.2), là giao của tất cả các tập lồi chứa Q. Rõ ràng bao lồi của Q là tập lồi nhỏ nhất chứa Q. Một tập Q là lồi khi và chỉ khi nó chứa mọi tổ hợp lồi hữu hạn các điểm của Q, tức là co(Q) := k { ∑ i=1 λixi : xi ∈ Q,λi ≥ 0, i= 1, . . . ,k , k ∑ i=1 λi = 1 và k ∈ N} . 8 Hình 1.2: Bao lồi của Q. Định nghĩa 1.1.3. Giả sử Q⊆ Rn là một tập hợp khác rỗng. • Tập Q được gọi là một nón (cone) nếu với mọi x ∈ Q và mọi λ ≥ 0 ta có λx ∈ Q (Hình 1.3). • Một nón Q được gọi là nón lồi nếu Q đồng thời là một tập lồi. Hình 1.3: Nón lồi Nón không lồi • Bao nón (conic hull) của một tập Q, ký hiệu là cone(Q) là cone(Q) := {ta : a ∈ Q, t ∈ R, t = 0} . • Bao lồi dương của một tập Q, ký hiệu là pos(Q) , là pos(Q) := { k ∑ i=1 tiai : ai ∈ Q, ti ∈ R, ti = 0, i= 1, . . . ,k, k ∈ N } Định nghĩa 1.1.4. • Cho tập Q bất kỳ, một điểm x gọi là điểm trong của Q, nếu ∃ε > 0 : B(x,ε) := {x ∈ Rn : ‖x− x0‖< ε} ⊂ Q. Tập hợp các điểm trong của tập Q được ký hiệu là intQ. 9 • Cho một tập con lồi khác rỗng Q⊆ Rn, điểm x ∈ Q được gọi là điểm trong tương đối (relative interior point) của Q, nếu ri(Q) := {x ∈ Q : (x+ εBn)∩aff(Q)⊆ Q,∃ε > 0} . • Phần trong tương đối của tập Q, ký hiệu riQ, là tập chứa tất cả các điểm trong tương đối của Q. 1.1.2. Tập lồi đa diện Định nghĩa 1.1.5. • Một tập được gọi là tập lồi đa diện (convex polyhedron set), nếu nó là giao của một số hữu hạn các nửa không gian đóng. • Một tập lồi đa diện bị chặn được gọi là đa diện lồi hay gọi tắt là đa diện (polytope). • Theo định nghĩa của nửa không gian đóng, một tập lồi đa diện là tập nghiệm của hệ hữu hạn của bất phương trình〈 ai,x 〉 5 bi, i= 1, . . . , k, (1.1.1) trong đó a1, . . . , ak là véctơ cột n-chiều và b1, . . . , bk là các số thực. Khi bi = 0, i = 1, . . . , k, tập nghiệm của (1.1.1) là một nón và gọi là một nón lồi đa diện (convex polyhedral cone). Định nghĩa 1.1.6. • Giả sử P là một tập lồi đa diện và giả sử H = {x ∈ Rn : 〈v,x〉= α} , là một siêu phẳng với v khác không. Ta nói H là một siêu phẳng tựa (sup- porting hyperplane) của P tại một điểm x ∈ P nếu giao của H với P chứa x và P được chứa hoàn toàn trong một nửa không gian đóng xác định bởi H. (Hình 1.4). • Tập khác rỗngH∩P được gọi là một diện (hay mặt) của P.Một tập con khác rỗng F của P là một mặt nếu có một véctơ khác không v ∈ Rn mà 〈v,y〉 ≤ 〈v,x〉 với mọi x ∈ F,y ∈ P. 10 Hình 1.4: Siêu phẳng tựa Theo quy ước P cũng là một mặt của chính nó và được gọi là mặt chính thường. Định nghĩa 1.1.7. • Một điểm x ∈ Q được gọi là điểm cực biên (hay là đỉnh) của Q, nếu không tồn tại a,b ∈ Q, a 6= b, λ ∈ (0,1) sao cho x= λa+(1−λ )b. • Mặt có chiều bằng 1 được gọi là cạnh biên. Hai đỉnh kề nhau nếu chúng là điểm cuối của cạnh biên. • Một cạnh vô hạn được gọi là một tia cực biên (hay là một diện nửa đường thẳng). Phương của tia cực biên được gọi là phương cực biên (extreme di- rections). Nhận xét 1.1.1. Đỉnh của tập lồi đa diện P là một diện có thứ nguyên bằng 0. Số điểm cực biên của một tập lồi có thể hữu hạn hoặc vô hạn. Khi tập lồi có hữu hạn điểm cực biên thì chúng thường được gọi là các đỉnh. Nếu P là một đa diện lồi thì tập các phương cực biên bằng rỗng. Định nghĩa 1.1.8. • Cho Q là một tập lồi khác rỗng trong Rn. Một véctơ v 6= 0 được gọi là một tiệm cận (asymptotic) hoặc hướng lùi xa (recession direction) của Q, nếu mọi tia xuất phát từ một điểm bất kỳ của Q theo phương v đều nằm trọn trong Q, tức là v là phương lùi xa khi và chỉ khi x+ tv ∈ Q với mọi x ∈ Q, t = 0. • Tập tất cả các phương tiệm cận (asymptotic direction) của Q cùng với điểm gốc được gọi là nón tiệm cận (asymptotic cone) của Q, ký hiệu là Q∞ (Hình 1.6). 11 Hình 1.5: Nón tiệm cận Nón tiệm cận là một nón lồi. Hiển nhiện nếu Q là một tập bị chặn, thì nón tiệm cận của Q chỉ gồm duy nhất điểm gốc. Định nghĩa 1.1.9. • Cho tập lồi đa diện P xác định bởi hệ bất phương trình (1.1.1) và điểm x của P. Ta nói rằng véctơ v là véctơ pháp tuyến (normal vector) của p tại x nếu 〈v,y− x〉5 0 với mọi y ∈ P. • Tập tất cả các vectơ pháp tuyến của P tại x tạo thành nón lồi, được gọi nón pháp tuyến (normal cone) của P tại x và ký hiệu NP (x) . Khi x là điểm trong của P, nón pháp tuyến tại điểm đó là không. Hình 1.6: Nón pháp tuyến 12 1.2. Bài toán quy hoạch tuyến tính 1.2.1. Bài toán quy hoạch tuyến tính Bài toán quy hoạch tuyến tính (QHTT) (Linear Programming) có thể được phát biểu dưới dạng: Tìm cực đại 〈c,x〉 với điều kiện Ax= b, x= 0, (1.2.2) trong đó A = (ai j)m×n được gọi là ma trận hệ số ràng buộc, b ∈ Rm hay b = (b1, . . . ,bm)T được gọi là véc tơ vế phải và điểm x ∈ Rn hay x= (x1, . . . ,xn)T được gọi là các biến cần tối ưu. Hàm tuyến tính x 7→ 〈c,x〉 là hàm mục tiêu hay hàm giá (cost function). • Bài toán (LP) được cho bởi ràng buộc (1.2.2) được gọi là chuẩn tắc (standard form). Nó được gọi là chính tắc (canonical form) khi ràng buộc (1.2.2) thay bằng bất đẳng thức Ax≤ b. • Vì phương trình tuyến tính có thể được chuyển thành bất phương trình tuyến tính và ngược lại, nên bất kỳ bài toán quy hoạch tuyến tính đều có thể đưa về dạng (LP) ở trên. • Điểm x ∈ Rn thỏa mãn mọi ràng buộc của bài toán được gọi là điểm chấp nhận được hay là một phương án. Tập hợp tất cả các phương án, ký hiệu là X , được gọi là tập ràng buộc hay tập chấp nhận được của bài toán (LP), tức là, X tập nghiệm của hệ (1.2.2). • Nghiệm x¯ ∈ X gọi là tối ưu (optimal) của bài toán (LP) nếu 〈c, x¯〉 = 〈c,x〉 với mọi x ∈ X . • Một ma trận con B cấp k× k gồm các cột của A được gọi là một cơ sở (basis) nếu nó là khả nghịch. Giả sử B là một cơ sở. Bằng cách sử dụng một hoán vị ta có thể giả sử rằng B gồm k cột đầu tiên của A và các cột còn lại k× (n− k)-ma trận N, được gọi là phần phi cơ sở (non-basis part) của A. 13 • Giả sử x là một véctơ với thành phần xB và xN , trong đó xB là một véctơ k-chiều và xN là một véctơ (n− k)-chiều thoả mãn BxB = b, xN = 0. • Nếu xB là một véctơ dương, khi đó x là một nghiệm của (1.2.2) và được gọi là một nghiệm cơ sở chấp nhận được (feasible basic solution) (gắn với cơ sở B). Nếu ngoài xB không có thành phần bằng không, thì nó được gọi là không suy biến (non-degenerate); nếu ngược lại thì gọi là suy biến (degenerate). • Cho B là cơ sở chấp nhận được, ta gọi nó là cơ sở tối ưu (optimal basic) nếu nghiệm cơ sở tương ứng là nghiệm tối ưu của bài toán (LP). Ta sẽ phân rã véctơ giá c thành véctơ cơ sở cB và véctơ phi cơ sở cN . Véctơ c¯N = cN− ( B−1N )T cB, được gọi là véctơ giá rút gọn (reduced cost vector). Định lý 1.2.1. (Định lí 3.1.1 [4] trang 48-49) Cho X khác rỗng. Bốn điều kiện sau là tương đương. (i) (LP) có nghiệm tối ưu. (ii) (LP) có nghiệm tối ưu đạt tại đỉnh. (iii) Hàm giá là không dương trên mỗi phương tiệm cận của X . (iv) Hàm giá là bị chặn trên trên X . Chứng minh. (i)⇒ (iv). Hiển nhiên. (iv)⇒ (iii). Giả sử α là cận trên của hàm giá trên X và giả sử u là phương tiệm cận không bằng 0 của X nếu nó tồn tại. Vì X 6=6 0, nên có thể chọn điểm x bất kỳ. Do u là phương tiệm cận nên với mỗi số dương t, điểm x+ tu thuộc X . Do đó 〈c,x+ tu〉= 〈c,x〉+ t 〈c,u〉5 α. Bất đẳng thức này đúng với mọi dương t, suy ra 〈c,u〉5 0. (iii)⇒ (ii). Giả sử {v1, ..., vp} là tập các đỉnh và giả sử {u1, ..., uq} là tập hợp các tia cực biên của đa diện X . Chú ý răng, tập hợp các tia cực biên có thể là rỗng. Chọn đỉnh vi0 sao cho 〈 c,vi0 〉 =max {〈 c,v1 〉 , ..., 〈c,vp〉} . 14 Giả sử x là điểm bất kỳ trong X . Theo Định lý 2.4.9 [4], có các số không âm ti và s j với p ∑ i=1 ti = 1, sao cho x= p ∑ i=1 tivi+ q ∑ j=1 s ju j. Do đó 〈c,x〉= p ∑ i=1 ti 〈 c,vi 〉 + q ∑ j=1 s j 〈 c,u j 〉≤ 〈c,vi0〉 , trong đó đỉnh vi0 là nghiệm tối ưu. Ta có điều phải chứng minh. 2 Định lý 1.2.2. (Định lý 3.1.4 [4] trang 52-53) Giả sử B là cơ sở chấp nhận được và x¯ nghiệm cơ sở chấp nhận được tương ứng với B. Khi đó ta có các khẳng định sau (i) Nếu véctơ giá rút gọn c¯N là âm, thì B là tối ưu. (ii) Khi B là không suy biến, nó là tối ưu nếu và chỉ nếu véctơ giá rút gọn c¯N là âm. Chứng minh.Bằng cách đổi biến thích hợp, ta có ma trận A là được phân rã thành( B N ) , tập chỉ số cơ sở là {1, ...., m} và tập chỉ số phi cơ sở là {m+1, ..., n} . (i) Giả sử x là nghiệm chấp nhận được bất kỳ của bài toán. Khi đó x là nghiệm của hệ Ax= b, cơ sở xB của x tương ứng với cột cơ sở của B là các tọa độ phi cơ sở của nó qua xB = B−1b−B−1NxN = x¯B−B−1NxN . (1.2.3) Giá trị của hàm giá tại x là 〈c,x〉= 〈cB,xB〉+ 〈cN ,xN〉 = 〈 cB,B−1b−B−1NxN 〉 + 〈cN ,xN〉 = 〈cB, x¯B〉+ 〈c¯N ,xN〉 = 〈c, x¯〉+ 〈c¯N ,xN〉 . Vì xN là dương và giả thiết c¯N là âm, nên 〈c,x〉5 〈c, x¯〉 . Vì x là nghiệm chấp nhận được tùy ý của bài toán, ta suy ra x¯ là nghiệm tối ưu và B là một cơ sở tối ưu. (ii) Giả sử ngược lại, véctơ giá không âm, tức là tồn tại c¯ j > 0, với một chỉ số phi cơ sở j. Ta tìm nghiệm xˆ ở dạng đặc biệt: xˆ= ( xˆB xˆN ) với xˆN = x¯N+ te j = te j, trong đó e j là tọa độ phi cơ sở của véctơ đơn vị thứ j trong Rn và t là số dương được chọn sao cho xˆ là tối ưu. 15 Vì xˆN là dương, theo (1.2.3), xˆ là tối ưu, tức là xˆB = x¯B− tB−1Ne j ≥ 0. Cơ sở B không suy biến, véctơ x¯B luôn dương, do đó xˆB là dương, trong đó t > 0 đủ nhỏ. Cố định giá trị t và tính hàm giá tại điểm đó bằng cách sử dụng (1.2.3): 〈c, xˆ〉= 〈cB, xˆB〉+ 〈cN , xˆN〉 = 〈cB,xB〉− t 〈 cB,B−1Ne j 〉 + t 〈 cN ,e j 〉 = 〈cB, x¯B〉+ tc¯ j > 〈cB, x¯B〉 , mâu thuẫn với tính tối ưu của x¯. 2 1.2.2. Phương pháp đơn hình giải bài toán QHTT Ý tưởng của thuật toán đơn hình mô tả như sau: Giả thiết rằng B0 là cơ sở chấp nhận được. Bước 1. Xuất phát từ một đỉnh chấp nhận được x0 của miền ràng buộc, ta có các tọa độ là x0B = (B0) −1b và x0N = 0. Bước 2. Đặt k := k+1. Giả sử Bk là cơ sở chấp nhận được hiện tại và tương ứng với đỉnh cơ sở xk với hai tọa độ xkB và x k N . Tính b¯= B−1k b, c¯N = cN − ( B−1k N )T cB. Bước 3. Nếu c¯N 5 0, thì dừng lại. Đỉnh hiện tại xk là tối ưu. Ngược lại đến Bước 4. Bước 4. Giả sử s là chỉ số mà c¯s > 0. Chọn cột as của ma trận A và tính a¯s = B−1k as. Nếu véctơ này là âm, thì dừng lại. Bài toán là có giá trị bằng +∞. Ngược lại tìm chỉ số l sao cho xˆs := b¯l a¯ls =min { b¯i a¯is : a¯is > 0 } . Bước 5. Lập một cơ sở chấp nhận được mới Bk+1 từ Bk bằng cách gạch đi cột al và thay vào cột as. Đỉnh tương ứng với xk+1 nhận được từ xk bằng cách đặt biến xs = xˆs > 0 và biến xl = 0. Bước 6. Tính ma trận nghịch đảo B−1k+1 của cơ sở mới Bk+1 và quay về Bước 2. 16 Phần tử a¯ls nhận được ở trên từ ma trận A được gọi là phần tử xoay (pivot), cột a¯s = (a¯1s, ..., a¯ms) T và hàng a¯l = (a¯l1, ..., a¯ln) được gọi là hàng xoay (pivotal column) và cột xoay (pivotal row) của thuật toán. Do số đỉnh của miền ràng buộc là hữu hạn, nên nếu bài toán có nghiệm, sau hữu hạn bước ta sẽ tìm được đỉnh tối ưu. Tìm cơ sở chấp nhận được Ta xét ràng buộc của bài toán (LP) Ax= b và x= 0. Bằng cách nhân cả hai vế của đẳng thức với (−1) khi vế bên phải là véctơ b chỉ có tọa độ không âm. Hơn nữa, khi ta thấy tập ràng buộc khác rỗng, ta có thể bỏ đi một số phương trình sao cho ràng buộc còn lại không có phương trình thừa và ta có cùng tập nghiệm. Từ đó, ta giả sử có hai điều kiện đặt làm hạn chế sau: (1) véctơ b là dương, và (2) không có đẳng thức thừa. Vì việc chọn cơ sở chấp nhận được để bắt đầu thuật toán đơn hình là không rõ ràng, ta đưa vào một véctơ của biến giả y= (y1, ..., ym) T và xét bài toán tuyến tính Tìm cực đại y1+ ... + ym (1.2.4) với điều kiện Ax+ y= b và x= 0,y= 0. Mệnh đề 1.2.1. (Mệnh đề 3.3.2 [4] trang 69) Bài toán (LP) có nghiệm chấp nhận được nếu và chỉ nếu bài toán (1.2.4) có giá trị cực tiểu bằng 0 với y= 0. Chứng minh. Giả sử rằng x là nghiệm chấp nhận được của (LP). Khi đó (x,y) với y = 0 là nghiệm chấp nhận được của (1.2.4), và giá trị cực tiểu là bằng không. Ngược lại, nếu giá trị tối ưu của (1.2.4) là bằng không, thì tại nghiệm tối ưu (x,y) ta có y= 0 suy ra x là nghiệm chấp nhận được của (LP). 2 Tìm ma trận ngược Ta thấy ma trận cơ sở Bk và Bk+1 khác nhau duy nhất tại một cột, nghĩa là chúng kề nhau. Điều này giúp ta tính ma trận nghịch đảo của Bk+1 từ ma trận nghịch đảo 17 của Bk. Kí hiệu D là m×m-ma trận, gọi là ma trận đổi cơ sở (matrix for change of basic), là ma trận đơn vị trừ cột thứ l bằng véctơ( − a¯1s a¯ls , ..., 1 a¯ls , ...,− a¯ms a¯ls )T . Cụ thể là D=  1 ... −a¯1s/a¯ls ... 00 ... 1/a¯ls ... 0 0 ... −a¯ms/a¯ls ... 1  . Mệnh đề 1.2.2. Với ma trận D ở trên, ta có B−1k+1 = DB −1 k . Đặc biệt, nếu cơ sở thứ nhất là ma trận đơn vị, thì B−1k =Dk ... D1 trong đó D là ma trận biến đổi. Chứng minh. Giả sử β1, ..., βm là các cột của ma trận Bk. Khi đó các cột của Bk+1 là như nhau, với cột thứ l thay bằng cột as của ma trận A. Bằng cách nhân Bk+1 với D ta được ma trận có các cột đúng với Bk ngoại trừ cột thứ l bằng 1 a¯ls (Bk (−a¯s)+as)+βl . Theo định nghĩa, a¯s = B−1k as, ta suy ra Bk (−a¯s)+as = 0 và cột thứ l của tích Bk+1D bằng βl . Vì vậy, Bk+1D= Bk và suy ra điều phải chứng minh. 2 Bảng đơn hình Để giải bài toán (LP): Tìm cực đại 〈c,x〉 với điều kiện Ax= b và x= 0, ta giả sử rằng b là véctơ dương và ma trận A được viết dưới dạng (B N) , trong đó B là cơ sở chấp nhận được. Để rút gọn, véctơ giá c được đặt hàng đầu của bảng. Bảng đơn hình ban đầu có dạng, kí hiệu T cT = ( cTB c T N ) 0 A= ( B N ) b Bằng cách nhân vào bên phải bảng T bởi ma trận mở rộng S 18 1 −cTBB−1 0 B−1 ta có bảng mới T ∗ như sau 0 c¯TN = c T N − cTBB−1N −cTBB−1b I N¯ = B−1N B−1b Bảng T ∗ chứa toàn bộ thông tin cần thiết cho thuật toán đơn hình. • Nghiệm cơ sở tương ứng được tính là: x= ( xB xN ) với xB = B−1b, xN = 0. • Giá trị của hàm mục tiêu tại nghiệm cơ sở này bằng 〈c,x〉= (cB)TB−1b, trái dấu với giá trị đã cho trong cột cuối ở góc trên bên phải. • Véctơ giá rút gọn c¯N được tính nằm phía trên ở giữa bảng. Nếu toàn bộ tọa độ véctơ này là âm, thì đỉnh cơ sở hiện tại là tối ưu. • Nếu một vài tọa độ của véctơ giá rút gọn là dương, chọn chỉ số s với c¯s lớn nhất. Biến xs sẽ là cơ sở. Một biến xl với chỉ số l thoả mãn b¯l a¯ls =min { b¯i a¯is : a¯is > 0 } sẽ là cơ sở. Bảng đơn hình T ∗ thu được bằng cách nhân vào bên phải ma trận T với ma trận S 1 0 1 −c¯s/a¯ls 0 0 0 1 · · · −a¯1s/a¯ls · · · 0 ... ... · · · 1/a¯ls · · · ... 0 0 · · · −a¯ms/a¯ls · · · 1 Ta tìm ma trận biến đổi D với phần dưới của bảng trên. Phần tử xoay của thuật toán đơn hình là phần tử a¯ls. 19 Sử dụng bảng đơn hình ta có véctơ giá rút gọn c¯1 và c¯2. Cơ sở tối ưu đối với λ = 1 là B= {3,4} , nghiệm cơ sở tối ưu chấp nhận được là x= (0,0,3,6) . Bắt đầu với giai đoạn 3 Lặp 1: c¯1 −3 −1 0 0 0 c¯2 1 2 0 0 0 x3 0 1 1 0 3 x4 3 −1 0 1 6 Khi đó λ = 1, c¯(λ ) = (3,1,0,0) , B1 = {3,4} , x1 = (0,0,3,6) . I = {1,2} , λ ′ =max{ 13+1 , 21+2}= 23 s= 2, r = 3. Lặp 2: c¯1 −3 −1 0 0 0 c¯2 1 2 0 0 0 x3 0 1 1 0 3 x4 3 −1 0 1 6