ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ HỒNG LÊ PHƯƠNG PHÁP ĐIỂM TRONG GIẢI QUI HOẠCH TUYẾN TÍNH LUẬN VĂN THẠC SĨ TỐN HỌC Thái Nguyên - Năm 2011 Số hóa 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 THỊ HỒNG LÊ PHƯƠNG PHÁP ĐIỂM TRONG GIẢI QUI HOẠCH 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 2011 Số hóa 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 Nội dung KIẾN THỨC CHUẨN BỊ 1.1 Qui hoạch tuyến tính qui hoạch đối ngẫu 1.2 Phương pháp đơn hình đơn hình đối ngẫu 1.3 Độ phức tạp thuật toán 12 1.4 Ví dụ Klee-Minty độ phức tạp mũ 15 PHƯƠNG PHÁP ELLIPSOID 19 2.1 Về hệ bất phương trình đại số tuyến tính 20 2.2 Kỹ thuật ellipsoid 23 2.3 Thuật toán Khachian 26 2.4 Áp dụng vào giải qui hoạch tuyến tính 29 PHƯƠNG PHÁP ĐIỂM TRONG 30 3.1 Tâm giải tích 30 3.2 Đường trung tâm 34 3.3 3.2.1 Đường trung tâm đối ngẫu 37 3.2.2 Đường trung tâm gốc-đối ngẫu 40 Chiến thuật giải 41 3.3.1 Phương pháp hàm chắn gốc 43 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn i 3.4 3.3.2 Phương pháp bám đường gốc- đối ngẫu 45 3.3.3 Phương pháp hàm gốc- đối ngẫu 48 3.3.4 Độ phức tạp vòng lặp 51 Vấn đề khởi kết thúc thuật toán 52 3.4.1 Khởi thuật toán 53 3.4.2 Kết thúc thuật toán 3.4.3 Thuật toán HSD 54 56 Kết luận 61 Tài liệu tham khảo 64 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 NÓI ĐẦU Nhiều toán thực tế kinh tế, tài chính, cơng nghiệp kỹ thuật diễn đạt tốn qui hoạch tuyến tính, tức dạng tốn tìm cực đại (hay cực tiểu) hàm tuyến tính với ràng buộc đẳng thức hay bất đẳng thức tuyến tính Phương pháp đơn hình Dantzig đề xuất từ năm 1947, đến sử dụng rộng rãi để giải tốn qui hoạch tuyến tính Cách tiếp cần xét đỉnh tập đa diện ràng buộc lần lặp từ đỉnh tới đỉnh kề với nó, thường tốt đỉnh trước (cải tiến giá trị hàm mục tiêu) Cuối cùng, đạt tới đỉnh mà từ khơng thể cải tiến hàm mục tiêu nữa, đỉnh lời giải cần tìm tốn Mặc dầu hiệu thực tiễn (số lần lặp thường nhỏ m + n, m số ràng buộc tuyến tính n số biến toán) Tuy nhiên, V.Klee G.Minty(1972) đưa tốn qui hoạch tuyến tính đặc biệt mà để giải cần thời gian tỉ lệ với hàm mũ n Điều chứng tỏ mặt lý thuyết thuật tốn đơn hình khơng phải thuật toán thời gian đa thức Vào năm 1950, người ta đề cao tới phương pháp điểm (đi từ phía miền ràng buộc) Tuy nhiên, chúng chưa thành đạt phương pháp đơn hình Năm 1979 [4] Khachian người chứng minh giải tốn qui hoạch tuyến tính thời gian đa thức, cách sử dụng thuật tốn điểm thích hợp Mặc dầu thuật toán Khachian chưa đủ hiệu thực tiễn, thành Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn tựu Khachian làm khởi sắc quan tâm trở lại tới phương pháp điểm giải qui hoạch tuyến tính Tiếp đó, năm 1984 [3] Karmarkar đề xuất phương pháp điểm giải qui hoạch tuyến tính Phương pháp có độ phức tạp đa thức có hiệu thực tiễn cao, đặc biệt tốn tuyến tính cỡ lớn Các cơng trình nghiên cứu Khachian Karmarkar điểm khởi đầu cho nhiều nghiên cứu phương pháp điểm giải qui hoạch tuyến tính Đó chủ đề luận văn Cách tiếp cận khác với phương pháp đơn hình Thay cho cạnh tập ràng buộc từ đỉnh tới đỉnh khác, điểm lặp (xấp xỉ) men theo “ đường trung tâm” để tới tập lời giải Có nhiều dạng phương pháp điểm , tiêu biểu phương pháp chắn gốc, phương pháp bám đường gốc-đối ngẫu tạo lời giải cho hai toán gốc đối ngẫu qui hoạch tuyến tính, phương pháp hàm , Trong nhiều năm kể từ 1984, thuật toán phần mềm giải qui hoạch tuyến tính trở nên hồn tồn tinh xảo nói đến phương pháp điểm thực chiếm ưu Cũng có nhiều mở rộng phương pháp điểm để giải toán tối ưu phi tuyến; qui hoạch lồi tồn phương, qui hoạch nón Chẳng hạn, Nesterov Nemirovsky (1994) [6] xây dựng sở lý thuyết phương pháp điểm cho tối ưu hóa lồi Luận văn đề cập tới phương pháp điểm giải qui hoạch tuyến tính Khachian Karmarkar đề xuất Việc tìm hiểu nghiên cứu chủ đề cần thiết hữu ích giúp hiểu mở rộng ứng dụng phương pháp điểm vào toán tối ưu khác Nội dung luận văn chia thành ba chương: Chương 1“ Kiến thức chuẩn bị” nhắc lại tóm tắt số kiến thức cần thiết tốn qui hoạch tuyến tính lý thuyết đối ngẫu Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn qui hoạch tuyến tính, phương pháp đơn hình đơn hình đối ngẫu giải tốn qui hoạch tuyến tính Tiếp nêu khái niệm độ phức tạp thuật toán, thuật toán thời gian đa thức nêu ví dụ Klee- Minty phương pháp đơn hình có độ phức tạp mũ Các kiến thức cần đến chương sau Chương “Phương pháp Khachian” giới thiệu thuật toán ellipsoid Khachian đề xuất Về thực chất, thuật tốn Khachian qui việc tìm nghiệm tối ưu cặp tốn đối ngẫu qui hoạch tuyến tính việc tìm nghiệm hệ bất phương trình tuyến tính.Nhiều khái niệm kiện trình bày chương minh họa qua ví dụ hình vẽ cụ thể Chương “ Phương pháp điểm ” trình bày khái niệm tâm giải tích, đường trung tâm gốc đối ngẫu; nội dung phương pháp gốc-đối ngẫu, từ ý tưởng phương pháp (đi men theo đường trung tâm) đến thuật toán cụ thể (thuật toán bám đường) Phương pháp đánh giá phương pháp điểm hiệu giải qui hoạch tuyến tính Tiếp đó, giới thiệu hai thuật toán bám đường tiêu biểu: thuật toán dự báo thuật toán hiệu chỉnh Vấn đề khởi kết thúc thuật toán đề cập tới Do thời gian kiến thức hạn chế nên luận văn đề cập tới nội dung phương pháp điểm giải qui hoạch tuyến tính, chưa sâu vào chi tiết thực thi thuật tốn Trong q trình viết luận văn xử lý văn chắn khơng tránh khỏi sai sót định Tác giả luận văn mong nhận góp ý thầy cô bạn đồng nghiệp để luận văn hoàn thiệ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 đỡ suốt q trình làm luận văn Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Tác giả xin trân trọng cảm ơn thầy, cô giáo Trường Đại học Khoa học- Đại học Thái Ngun, Viện Tốn học-Viện Khoa học Cơng nghệ Việt Nam, giảng dạy tạo điều kiện thuận lợi trình tác giả học tập nghiên cứu Tác giả xin chân thành cảm ơn Ban giám hiệu, tổ tốn –tin Trường THPT Ngơ Quyền –Thái Nguyên tập thể bạn bè đồng nghiệp gia đình quan tâm giúp đỡ, động viên tác giả hoàn thành tốt luận văn Thái Nguyên, tháng 09 năm 2011 Người thực Nguyễn Thị Hồng Lê 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 KIẾN THỨC CHUẨN BỊ Chương nhắc lại kết lý thuyết qui hoạch tuyến tính phương pháp đơn hình giải qui hoạch tuyến tính, đồng thời nêu khái niệm độ phức tạp thuật toán dẫn ví dụ V Klee G Minty cho thấy thuật tốn đơn hình thuật tốn thời gian mũ (chứ khơng phải thuật tốn thời gian đa thức!) Nội dung chương chủ yếu dựa tài liệu [1], [2], [5] [7] 1.1 Qui hoạch tuyến tính qui hoạch đối ngẫu Qui hoạch tuyến tính tốn tìm cực tiểu (cực đại) hàm tuyến tính f (x) tập lồi đa diện D ⊂ Rn Bài toán thường viết hai dạng: • Dạng chuẩn (standard form): min{f (x) = cT x : Ax ≥ 0, x ≥ 0} với A ∈ Rm×n (ma trận m hàng, n cột),b ∈ Rm , c, x ∈ Rn , x ≥ 0, tức x ∈ Rn+ T ký hiệu chuyển vị véctơ, D = {x ∈ Rn : Ax ≥ b, x ≥ 0} tập lồi đa diện • Dạng tắc (canonical form): Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn f (x) = cT x : Ax = b, x ≥ , ký hiệu A ∈ Rm×n , b ∈ Rm , c, x ∈ Rn Trong toán này, tập D = {x ∈ Rn : Ax = b, x ≥ 0} tập lồi đa diện Trong hai dạng trên, f gọi hàm mục tiêu, D gọi tập ràng buộc hay miền chấp nhận Điểm x = (x1 , , xn )T ∈ D gọi lời giải (điểm, nghiệm)chấp nhận hay phương án toán Một phương án đạt cực tiểu (cực đại) hàm mục tiêu gọi lời giải (điểm, nghiệm) tối ưu hay phương án tối ưu Bài toán max cT x : x ∈ D = − −cT x : x ∈ D Với toán qui hoạch tuyến tính, xảy ba khả năng: a) Bài tốn khơng có lời giải chấp nhận (tập ràng buộc D rỗng) b) Bài tốn có lời giải chấp nhận được, khơng có lời giải tối ưu c) Bài tốn có lời giải tối ưu (hữu hạn) Định lý sau nêu điều kiện để qui hoạch tuyến tính có lời giải tối ưu Định lý 1.1 Nếu qui hoạch tuyến tính có lời giải chấp nhận hàm mục tiêu bị chặn miền chấp nhận (đối với toán min) qui hoạch chắn có lời giải tối ưu Định nghĩa 1.1 Một lời giải chấp nhận x ∈ D mà đồng thời đỉnh D gọi lời giải sở, nghĩa x biểu diễn dạng tổ hợp lồi hai lời giải chấp nhận khác D Nói cách khác, x = λx1 + (1 − λ) x2 với < λ < x1 , x2 ∈ D phải có x = x1 = x2 Định lý sau nêu tính chất đặc trưng cho lời giải sở qui hoạch tuyến tính tắc với giả thiết m ≤ n rank(A) = m Định lý 1.2 Để lời giải chấp nhận x = {x1 , x2 , , xn } qui hoạch tuyến tính tắc lời giải sở, cần đủ véctơ cột Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 50 Tuy nhiên, đạt thuật tốn nhanh nhờ dùng kỹ thuật tìm xác tia theo hướng d để giảm nhanh phương pháp hàm gốc - đối ngẫu vịng lặp Thuật tốn mơ tả sau Bước Xuất phát từ điểm x0 , y , s0 ∈ F với ψn+ρ x0 , s0 ≤ ρ log x0 T s √ + n log n + O n log n Điểm xác định theo thủ tục tìm điểm ban đầu (thuật toán √ n Chọn tham khởi mục (3.4.1)) Đặt ρ ≥ n Đặt k = γ = n+ρ số đo độ xác ε > Bước Đặt (x, s) = xk , sk tính (dx , dy , ds ) theo (3.7) Bước Đặt xk+1 = xk + αdx , yk+1 = y k + αdy , sk+1 = sk + αds với α = arg ψn+ρ (x + αdx , s + αds ) α≥0 Bước Đặt k ← k + Nếu T k xk s (x0 )T s0 ≤ ε dừng thuật toán Trái lại, quay lại thực bước n ε Định lí 3.1 Thuật tốn nêu kết thúc sau khơng q O ρ log vịng lặp để đạt xk T k s (x0 )T s0 ≤ ε Chứng minh Chú ý sau k vòng lặp, từ (17) ta có ψn+ρ xk , sk ≤ ψn+ρ x0 , s0 −kδ ≤ ρ log x0 T s +n log n+O √ n log n −kδ Như vậy, từ bất đẳng thức (3.8) ta nhận ρ log xk T k s x0 + n log n ≤ ρ log T s + n log n + O hay ρ log xk T k s − log x0 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên T s ≤ −kδ + O √ √ n log n − kδ n log n http://www.lrc-tnu.edu.vn 51 Do đó, k ≥ O (ρ log n) ta phải có ρ log xk T k s x0 − log T s ≤ −ρ log ε hay xk T k s ≤ ε (x0 )T s0 √ √ Định lý với ρ ≥ n Như vậy, cách chọn ρ = n ta √ n n log cận cho độ phức tạp vòng lặp O ε 3.3.4 Độ phức tạp vòng lặp Về bản, vòng lặp đòi hỏi giải hệ (3.7) để tìm hướng d Để ý phương trình đầu (3.7) viết sau: Sdx + Xds = γµI − XSI, X S hai ma trận đường chéo với phần tử đường chéo thành phần x > s > Nhân bên trái hai vế với S −1 ta dx + S −1 Xds = γµS −1 I − x Sau đó, nhân bên trái hai vế với A để ý Adx = ta nhận AS−1 Xds = γµAS−1 I − Ax = γµAS−1 I − b Sử dụng ds = −AT dy ta có AS−1 XAT dy = b − γµAS−1 I Như vậy, chi phí tính toán bước lặp phương pháp điểm đề cập tới mục lập lấy nghịch đảo ma trận AXS −1 AT , công việc cần địi hỏi O nm2 + m3 phép tốn số học Tuy nhiên, tính truy hồi lấy nghịch đảo ma trận xấp xỉ ma trận nhờ dùng phép tốn số học Trên thực tế, cách dùng " kỹ thuật Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 52 hạng một" (rank-one technique) để chỉnh sửa xấp xỉ nghịch đảo ma trận chuẩn trình lặp, người ta giảm số trung bình √ phép tốn số học o vịng lặp tới O nm Như vậy, xem dung sai tương đối ε biến ta có đánh giá sau cận độ phức tạp tính theo số lượng phép tốn số học để giải qui hoạch tuyến tính √ Hệ 3.1 Cho ρ = n Khi thuật tốn nêu kết thúc sau khơng n phép tốn số học q O nm2 log ε 3.4 Vấn đề khởi kết thúc thuật tốn Mục trình bày số vấn đề quan trọng có liên quan đến thuật tốn điểm giải qui hoạch tuyến tính Vấn đề thứ liên quan đên khởi thuật toán Hầu tất thuật toán điểm cần giả thiết quy, nghĩa địi hỏi F = ∅ Cần phải làm khơng có giả thiết này? Một vấn đề nũa thuật toán điểm cần phải xuất phát từ điểm chấp nhận chặt nằm gần đường trung tâm Vấn đề thứ hai liên quan đến kết thúc thuật toán Phương pháp đơn hình kết thúc lời giải xác, cịn thuật tốn điểm thuật tốn tối ưu liên tục, sinh dãy vô hạn lời giải hội tụ tới lời giải tối ưu Nếu liệu tốn ngun hay hữu tỷ sau đạt cận thời gian xấu nhất, liệu lời giải xác có thu cách làm trịn lời giải xấp xỉ cuối hay không? Nảy sinh thêm số câu hỏi: Thứ nhất, giả sử mô hình tính tốn với số thực (tức liệu số thực), làm kết thúc thuật tốn lời giải xác? Thứ hai, với trạng thái liệu nào, liệu q trình lặp kiểm tra thực tế chi phí tính tốn để nhận biết lời giải xác thuật tốn dừng trước đạt cận thời gian xấu nhất? Ở lời giải xác Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 53 hiểu lời giải tìm cách dùng phép tính số học xác Chẳng hạn, nghiệm hệ phương trình tuyến tính tìm sau số phép toán số học bị chặn đa thức phụ thuộc n 3.4.1 Khởi thuật toán Hầu hết thuật tốn điểm địi hỏi điểm chấp nhận chặt Độ phức tạp để nhận điểm ban đầu độ phức tạp giải thân qui hoạch tuyến tính Điều quan trọng thuật tốn hồn chỉnh cần thực hai việc: 1) Phát tốn khơng tương thích ( khơng có nghiệm chấp nhận được) tốn có nghiệm vơ hạn ( hàm mục tiêu tiến vơ cùng); 2) Tìm nghiệm tối ưu tốn tương thích có nghiệm hữu hạn Sau đề cập tới số cách tiếp cận nhằm thực hai mục tiêu • Bài tốn gốc đối ngẫu gộp lại thành tốn tìm nghiệm chấp nhận Về lý thuyết, cách tiếp cận đạt tới √ n log cận tốt cho độ phức tạp vòng lặp, nghĩa O ε Nhưng mặt thực hành, yếu điểm đáng kể cách tiếp cận làm tăng gấp đơi kích thước hệ phương trình cần giải vịng lặp • Có thể dùng phương pháp toán M cách thêm vào (một số) cột hay (một số) dòng giả tạo với tham số phạt M lớn để buộc nghiệm trở thành chấp nhận q trình thực thuật tốn.Yếu điểm cách tiếp cận gặp phải vấn đề tính tốn số, hệ số có biên độ q lớn gây nên • Phương pháp pha I, sau pha II tỏ hiệu Nhưng yếu điểm cách tiếp cận cần giải liên tiếp hai (hoặc ba) toán tuyến tính liên quan đến Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 54 • Phương pháp pha I- pha II cải biên cho phép tiến dần tới nghiệm chấp nhận nghiệm tối ưu lúc Theo cách tiếp cận này, √ n log cận tốt cho độ phức tạp phép lặp O , so ε √ n log ba cách tiếp cận Những yếu điểm với độ phức tạp O ε khác phương pháp giả thiết tập chấp nhận có phần khác rỗng cần cận hàm mục tiêu 3.4.2 Kết thúc thuật toán Cận cho độ phức tạp phương pháp điểm nói chung phụ thuộc ε ε = ta nhận lời giải xác Đơi có lợi sử dụng phương pháp kết thúc thuật toán sớm hay thuật toán làm tròn ε lớn vừa phải Sau luận văn giới thiệu cách tiếp cận • Thủ tục " tinh lọc " tìm lời giải sở chấp nhận với giá trị mục tiêu không tồi điểm có Việc thực thời gian đa thức mạnh (tức cận độ phức tạp đa thức phụ thuộc kích thước m n tốn, khơng phụ thuộc độ dài liệu) Tuy nhiên, khó khăn chỗ có nhiều đỉnh khơng tối ưu gần diện tối ưu thủ tục có phải tốn nhiều phép xoay (pivots) đơn hình tốn khó • Phương pháp thứ hai tìm cách nhận dạng sở tối ưu Người ta toán qui hoạch tuyến tính khơng thối hóa (mỗi đỉnh có n cạnh) sở tối ưu phát sớm Thủ tục tỏ làm việc tốt số tốn, gặp khó khăn tốn thối hóa Đáng tiếc hầu hết tốn qui hoạch tuyến tính từ thực tế thối hóa Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 55 • Cách tiếp cận thứ ba nhiễu đôi chút số liệu cho tốn khơng thối hóa sở tối ưu toán nhiễu cịn sở tối ưu tốn ban đầu Vấn đề làm nhiễu liệu trình lặp, việc làm ảnh hưởng đáng kể tới thành cơng thuật tốn • Cách tiếp cận thứ tư đốn nhận diện tối ưu tìm lời giải chấp nhận diện Cách gồm hai pha: pha đầu dùng thuật toán điểm để nhận biết phân hoạch bù (P ∗ ,Z ∗ ) pha sau dùng phương pháp đơn hình tìm lời giải sở tối ưu gốc (hay đối ngẫu) ta dùng (P ∗ ,Z ∗ ) làm sở xuất phát pha sau Phương pháp thường gọi phương pháp chéo.Nó đảm bảo làm việc thời gian hữu hạn cài đặt số phần mềm phổ biến qui hoạch tuyến tính • Cách tiếp cận thứ năm đoán nhận diện tối ưu chiếu điểm có lên phần diện tối ưu Xem hình 3.3 Tiêu chuẩn kết thúc bảo đảm làm việc thời gian hữu hạn Hình 3.3:Minh họa phép chiếu điểm lên diện tối ưu Các phương pháp nêu dựa vào kiện (quan sát từ thực tiễn sau chứng minh): nhiều thuật tốn điểm giải qui Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 56 hoạch tuyến tính sinh dãy nghiệm hội tụ tới nghiệm bù chặt hay tới điểm diện tối ưu 3.4.3 Thuật toán HSD Thuật toán tự đối ngẫu nhất, gọi tắt Thuật toán HSD (Homogeneuous Self-Dual Algorlthm) khắc phục khó khăn nêu Thuật √ n log độ phức tạp toán đạt cận lý thuyết tốt O ε phép lặp hay sử dụng gói phần mềm giải qui hoạch tuyến tính Thuật tốn dựa việc xây dựng qui hoạch tuyến tính tự đối ngẫu có quan hệ tới hai tốn ((LP) (LD) xem mục 3.2) Ta giải thích ngắn gọn hai khái niệm tính (homgeneity) tính tựu đối ngẫu (self-duality) cách xây dựng Nói chung, hệ phương trình hay bất phương trình tuyến tính gọi thành phần vế phải Khi tìm nghiệm nhân với số dương nghiệm hệ Trong cách xây dựng dùng ta cho phép ràng buộc không nhất, thường gọi ràng buộc chuẩn hóa Dạng tắc ban đầu Karmarkar xét toán qui hoạch tuyến tính Một qui hoạch tuyến tính gọi tự đối ngẫu tốn đối ngẫu tương đương (đơi trùng ) với tốn gốc Ưu điểm tính tự đối ngẫu ta áp dụng thuật toán điểm gốc- đối ngẫu để giải tốn tự đối ngẫu mà khơng cần gấp đơi số chiều hệ tuyến tính cần giải vịng lặp Bài tốn qui hoạch tuyến tính tự đối ngẫu (HSDP) xây dựng từ toán (LP) (LD) theo cách cho điểm x = 1, y = 0, τ = 1, z = 1,θ = nghiệm chấp nhận Xét toán qui hoạch gốc (HSDP) (n + 1) θ → Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 57 với điều kiện Ax − bτ + bθ = −AT y + cτ − cθ ≥ 0, bT y − cT x + zθ ≥ 0, T −b y + cT x + zτ = − (n + 1) , y tùy ý, x ≥ 0, τ ≥ 0, θ tùy ý, b = b − A1, c = c − 1, z = cT + Chú ý b, c z biểu thị "tính không chấp nhận được" điểm gốc, điểm đối ngẫu độ lệch đối ngẫu ban đầu Chúng chọn cho hệ chấp nhận Chẳng hạn, với điểm x = 1, y = 0, τ = 1, θ = phương trình cuối trở thành + cT x − 1T x − cT x + = −n − 1, Cũng ý hai ràng buộc (HSDP) với τ = θ = biểu thị tính chấp nhận gốc đối ngẫu (với x ≥ 0) Phương trình thứ ba biểu thị hệ thức đối ngẫu yếu ngược (bT y ≥ cT x ) đối ngẫu yếu thơng thường (cT x ≥ bT y) Vì ba điều kiện thỏa mãn với τ = θ = chúng xác định hai nghiệm tối ưu gốc đối ngẫu với x = 1, (y, s) = (0, 1) ta thêm biến giả tạo θ Ràng buộc thứ tư đưa vào để đạt tính tự đối ngẫu Bài tốn tự đối ngẫu tồn ma trận hệ số tốn có tính chất chuyển vị ma trận đối Đó ma trận đối xứng Ký hiệu s vectơ biến bù ràng buộc thứ hai κ biến bù ràng buộc thứ ba Ký hiệu Fh tập tất điểm (y, x, τ, θ, s, κ) chấp nhận toán (HSDP) Ký hiệu Fh tập điểm chấp nhận chặt với (x, τ, s, κ) > Fh Bằng cách kết hợp ràng Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 58 buộc lại ta viết lại ràng buộc đẳng thức cuối dạng 1T x + 1T s + τ + κ − (n + 1) θ = (n + 1) , đẳng thức dùng làm ràng buộc chuẩn hóa tốn (HSDP) Có thể thấy với ≤ θ ≤ biến phương trình bị chặn Định lý sau kết tốn (HSDP) Định lí 3.2 Xét tốn (HSDP) (i) (HSDP) có nghiệm tối ưu tập nghiệm tối ưu toán bị chặn (ii) Giá trị tối ưu toán (HSDP) (y, x, τ, θ, s, κ) ∈ Fh kéo theo (n + 1) θ = xT s + τ κ (iii) Tồn nghiệm tối ưu (y∗ , x∗ , τ ∗ , θ∗ = 0, s∗ , κ∗ ) ∈ Fh cho x ∗ + s∗ τ ∗ + κ∗ > Nghiệm gọi nghiệm bù chặt Kết luận (ii) định lý cho thấy θ dần tới nghiệm dần tới thỏa mãn điều kiện độ lệch bù x s, τ κ Kết luận (iii) nghiệm với θ = có độ lệch bù chặt theo nghĩa thành viên cặp bù phải dương Chẳng hạn, x1 s1 = điều kiện bù đòi hỏi, trường hợp xảy đồng thời x1 = 0, s1 = 0; mà chúng ((x1 s1 )) phải dương Mối liên hệ nghiệm tối ưu toán (HSDP) với nghiệm tối ưu toán (LP) (LD) nêu định lý sau Định lí 3.3 Giả sử (y∗ , x∗ , τ ∗ , θ∗ = 0, s∗ , κ∗ ) nghiệm tự bù chặt toán (HSDP) (i) (LP) có nghiệm (chấp nhận bị chặn) τ ∗ > y ∗ s∗ x∗ Trong trường hợp này, ∗ nghiệm tối ưu (LP) ∗ , ∗ nghiệm τ τ τ tối ưu của(LD) Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 59 (ii) (LP) khơng có nghiệm κ∗ > Trong trường hợp này, x∗ y∗ hoặc hai chứng tính khơng chấp nhận κ∗ κ∗ được: cT x∗ < (LD) khơng chấp nhận được; bT y∗ > (LP) khơng chấp nhận được; cịn hai cT x∗ < bT y∗ > hai tốn (LP) (LD) khơng chấp nhận Chứng minh Ta chứng minh mệnh đề thứ hai Trước hết ta giả thiết (LP) (LD) không chấp nhận , chẳng hạn (LP) Khi có x ≥ cho Ax = cT x = −1 Giả sử (y = 0, s = 0) α= n+1 >0 1T x + 1T s + Khi ta kiểm tra lại ∗ y ∗ = αy, x∗ = αx, τ ∗ = 0, θ = 0, s∗ = αs, κ∗ = α nghiệm tự bù (HSDP) Do tập tựa (tập thành phần dương) nghiệm bù chặt (HSDP) nhất, nên κ > nghiệm bù chặt (HSDP) Ngược lại, τ ∗ = κ∗ > 0, điều kéo theo cT x∗ − bT y∗ < 0, tức cT x∗ −bT y ∗ nhỏ Chẳng hạn giả sử cT x∗ < Hơn nữa, ta có Ax∗ = 0, AT y ∗ + s∗ = 0, (x∗ )T s∗ = 0, x∗ + s∗ > x∗ Theo bổ đề Farkas ∗ chứng cho thấy tính không chấp nhận κ đối ngẫu Các trường hợp khác chứng minh tương tự Để giải toán (HSDP) ta có định lý sau giống định lý đường trung tâm xét toán (LP)và (LD) Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 60 Định lí 3.4 Xét tốn (HSDP) Với µ > có nghiệm (y, x, τ, θ, s, κ) Fh cho x◦s τκ = µ1 Hơn nữa,(x, τ ) = (1, 1),(y, s, κ) = (0, 0, 1) θ = nghiệm với µ = Định lý 3.4 xác định đường nội sinh (endogenuos path) toán (HSDP): C= (y, x, τ, θ, s, κ) ∈ Fh : x◦s τκ xT s + τ κ = I n+1 Hơn nữa, hàm (HSDP) xác định sau: n T ψn+1+ρ (x, τ, s, κ) = (n + + ρ) log x s + τ κ − log (xj sj ) − log (τ κ) , j=1 ρ ≥ Khi ta áp dụng thuật tốn điểm mơ tả để giải (HSDP) xuất phát từ điểm ban đầu (x, τ ) = (1, 1) , (y, s, κ) = xT s + τ κ = (0, 1, 1) θ = với µ = n+1 Phương pháp HSDP trình bày có tính chất đáng ý sau: • Khơng địi hỏi giả thiết qui liên quan đến tồn nghiệm tối ưu, nghiệm chấp nhận hay nghiệm chấp nhận chặt • Có thể xuất phát từ x = 1, y = s = 1, chấp nhận hay không chấp nhận được, tia trung tâm gốc (orthant) dương khơng địi hỏi tham số phạt M lớn, không cần biết cận hàm mục tiêu • Mỗi vịng lặp giải hệ phương trình tuyến tính có kích thước gần ngang với hệ cần giải thuật toán điểm gốc- đối ngẫu Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 61 • Nếu tốn qui hoạch tuyến tính có nghiệm chấp nhận thuật tốn sinh dãy điểm hội tụ đến nghiệm chấp nhận nghiệm tối ưu lúc; cịn tốn khơng có nghiệm chấp nhận hay có nghiệm vơ hạn thuật tốn đưa chứng tính khơng chấp nhận tốn gốc đối ngẫu Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 62 Kết luận Luận văn trình bày khái quát phương pháp điểm giải qui hoạch tuyến tính Trong vịng 20 năm gần đây, phương pháp điểm có phát triển nhanh chóng Trên thực tế, qui hoạch tuyến tính cỡ lớn phương pháp điểm có hiệu tính tốn vượt trội so với phương pháp đơn hình quen thuộc Vì thế, phương pháp điểm công cụ quan trọng tối ưu hóa quan tâm nghiên cứu Tên gọi " phương pháp điểm trong" xuất từ ý tưởng di chuyển phần miền ràng buộc để tới lời giải tối ưu tốn, nhờ tránh qua số lớn điểm cực biên Phương pháp điểm sử dụng hàm chắn lơga với tham số µ, xác định tâm giải tích đường trung tâm dẫn tới nghiệm tối ưu tốn µ → Phần lớn phương pháp điểm dùng bước Newton để tìm điểm gần đường trung tâm, di chuyển từ giá trị µ tới giá trị µ khác Một cách tiếp cận đáng ý phương pháp dự báo hiệu chỉnh, theo lúc đầu thực bước theo hướng giảm giá trị µ, sau bước hiệu chỉnh để gần tới đường trung tâm Phương pháp khác dùng hàm mà giá trị giảm dần sau bước Trong số nhiều thuật tốn điểm thuật tốn gốc-đối ngẫu đánh giá cao hơn, có hiệu tốn qui hoạch tuyến tính thực tiễn Hơn nữa, nhờ triệt để khai thác tính chất Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 63 gốc đối ngẫu qui hoạch tuyến tính nên trình bày thuật tốn điểm dạng gốc-đối ngẫu cách đơn giản đẹp đẽ Hướng phát triển đề tài nghiên cứu mở rộng phương pháp điểm cho qui hoạch toàn phương qui hoạch lồi tổng quát Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 64 Tài liệu tham khảo Tài liệu tiếng Việt [1] Trần Vũ Thiệu(2004) Giáo trình tối ưu tuyến tính, NXB Đại học Quốc Gia Hà Nội [2] Hoàng Tụy, Trần Vũ Thiệu (3-1982)Thuật tốn Khachian giải quy hoạch tuyến tính thời gian đa thức Tạp chí Tốn học, tập X, số 1, tr.1-8 Tài liệu tiếng Anh [3] N.K Karmarkar(1984).A New Polynomial-Time Algorlthm for Linear Programming Combinatorica.4: 373-395 [4] L.G Khachian.Thuật tốn đa thức qui hoạch tuyến tính Báo cáo Viện Hàn lâm khoa học Liên Xô, 1979, 244, 5,1093-1096 (tiếng Nga) [5] D.G Luenberger and Y.Ye.Linear and Nonliner Programming, 3rd edition, Springer, 2008, pp.111-143 [6] Y.Nesterov and A.Nemirovski.Interrior-Point Polynomial Algorlthms in Convex Programming SIAM, Philadelphia, 1994 [7] J.J.Strodiot Numerical Methods in Optimization, Namur-Belgium, 2002 ,89-123 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ... khởi sắc quan tâm trở lại tới phương pháp điểm giải qui hoạch tuyến tính Tiếp đó, năm 1984 [3] Karmarkar đề xuất phương pháp điểm giải qui hoạch tuyến tính Phương pháp có độ phức tạp đa thức có... toán gốc đối ngẫu qui hoạch tuyến tính, phương pháp hàm , Trong nhiều năm kể từ 1984, thuật toán phần mềm giải qui hoạch tuyến tính trở nên hồn tồn tinh xảo nói đến phương pháp điểm thực chiếm ưu... dung phương pháp gốc-đối ngẫu, từ ý tưởng phương pháp (đi men theo đường trung tâm) đến thuật toán cụ thể (thuật toán bám đường) Phương pháp đánh giá phương pháp điểm hiệu giải qui hoạch tuyến tính