Tài liệu Phương pháp điểm trong giải quy hoạch tuyến tính

ĐẠ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Ĩ TOÁN HỌC Thái Nguyên - Năm 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN 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 bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn i Mục lục Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i LỜI NÓI ĐẦU 1 Nội dung 5 1 KIẾN THỨC CHUẨN BỊ 5 2 3 1.1 Qui hoạch tuyến tính và qui hoạch đối ngẫu . . . . . . . . 5 1.2 Phương pháp đơn hình và đơn hình đối ngẫu . . . . . . . . 9 1.3 Độ phức tạp của thuật toán . . . . . . . . . . . . . . . . . 12 1.4 Ví dụ Klee-Minty về độ 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 bởi 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 thế gốc- đối ngẫu . . . . . . . . . 48 3.3.4 Độ phức tạp của mỗi vòng lặp . . . . . . . . . . . . 51 Vấn đề khởi sự và kết thúc thuật toán . . . . . . . . . . . . 52 3.4.1 Khởi sự 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 bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 LỜI NÓI ĐẦU Nhiều bài toán thực tế trong kinh tế, tài chính, công nghiệp và kỹ thuật có thể diễn đạt như bài toán qui hoạch tuyến tính, tức là dưới dạng bài toán tìm cực đại (hay cực tiểu) của một hàm tuyến tính với các ràng buộc đẳng thức hay bất đẳng thức tuyến tính. Phương pháp đơn hình do Dantzig đề xuất từ năm 1947, đến nay vẫn còn được sử dụng rộng rãi để giải các bài toán qui hoạch tuyến tính. Cách tiếp này chỉ cần xét các đỉnh của tập đa diện ràng buộc và mỗi lần lặp đi từ một đỉnh tới một đỉnh kề với nó, thường là tốt hơn đỉnh trước đó (cải tiến được giá trị của hàm mục tiêu). Cuối cùng, nó đạt tới đỉnh mà từ đó không thể cải tiến hàm mục tiêu được nữa, đỉnh đó chính là lời giải cần tìm của bài toán. Mặc dầu nó rất hiệu quả trong thực tiễn (số lần lặp thường nhỏ hơn m + n, trong đó m là số ràng buộc tuyến tính và n là số biến của bài toán). Tuy nhiên, V.Klee và G.Minty(1972) đã đưa ra một bài toán qui hoạch tuyến tính đặc biệt mà để giải nó cần một thời gian tỉ lệ với hàm mũ của n. Điều này chứng tỏ về mặt lý thuyết thuật toán đơn hình không phải là một thuật toán thời gian đa thức. Vào những năm 1950, người ta đã đề cao tới các phương pháp điểm trong (đi từ phía trong miền ràng buộc). Tuy nhiên, chúng chưa thành đạt như phương pháp đơn hình. Năm 1979 [4] Khachian là người đầu tiên đã chứng minh được rằng có thể giải bài toán qui hoạch tuyến tính trong thời gian đa thức, bằng cách sử dụng thuật toán điểm trong thích hợp. Mặc dầu thuật toán Khachian chưa đủ hiệu quả trong thực tiễn, nhưng thành Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 tựu này của Khachian đã làm khởi sắc sự quan tâm trở lại tới các phương pháp điểm trong giải qui hoạch tuyến tính. Tiếp đó, năm 1984 [3] Karmarkar đã đề xuất một phương pháp điểm trong mới giải qui hoạch tuyến tính. Phương pháp này có độ phức tạp đa thức và nó có hiệu năng thực tiễn cao, đặc biệt đối với các bài toán tuyến tính cỡ lớn. Các công trình nghiên cứu của Khachian và Karmarkar là điểm khởi đầu cho nhiều nghiên cứu về các phương pháp điểm trong giải qui hoạch tuyến tính. Đó cũng là chủ đề chính của luận văn này. Cách tiếp cận mới khác cơ bản với phương pháp đơn hình . Thay cho đi trên các cạnh của tập ràng buộc từ đỉnh này tới đỉnh khác, các điểm lặp (xấp xỉ) đi 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 trong , tiêu biểu nhất là phương pháp chắn gốc, phương pháp bám đường gốc-đối ngẫu tạo ra lời giải cho cả hai bài toán gốc và đối ngẫu của qui hoạch tuyến tính, phương pháp hàm thế ,...Trong nhiều năm kể từ 1984, các thuật toán và phần mềm giải qui hoạch tuyến tính đã trở nên hoàn toàn tinh xảo và có thể nói rằng đến nay các phương pháp điểm trong đã thực sự chiếm ưu thế. Cũng đã có nhiều mở rộng của phương pháp điểm trong để giải các bài toán tối ưu phi tuyến; qui hoạch lồi toàn phương, qui hoạch nón. . . Chẳng hạn, Nesterov và Nemirovsky (1994) [6] đã xây dựng cơ sở lý thuyết các phương pháp điểm trong cho tối ưu hóa lồi. Luận văn này đề cập tới các phương pháp điểm trong giải qui hoạch tuyến tính do Khachian và Karmarkar đề xuất. Việc tìm hiểu và nghiên cứu chủ đề này là rất cần thiết và hữu ích giúp hiểu được các mở rộng và ứng dụng của phương pháp điểm trong vào các bài toán tối ưu khác. Nội dung luận văn được chia thành ba chương: Chương 1“ Kiến thức chuẩn bị” nhắc lại tóm tắt một số kiến thức cơ bản cần thiết về bài toán qui hoạch tuyến tính và lý thuyết đối ngẫu trong Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 qui hoạch tuyến tính, về phương pháp đơn hình và đơn hình đối ngẫu giải bài toán qui hoạch tuyến tính .Tiếp đó nêu khái niệm độ phức tạp của thuật toán, thuật toán thời gian đa thức và nêu ví dụ của Klee- Minty về phương pháp đơn hình có độ phức tạp mũ. Các kiến thức này sẽ cần đến ở các chương sau . Chương 2 “Phương pháp Khachian” giới thiệu thuật toán ellipsoid do Khachian đề xuất. Về thực chất, thuật toán Khachian qui việc tìm nghiệm tối ưu của cặp bài toán đối ngẫu của qui hoạch tuyến tính về việc tìm nghiệm của một hệ bất phương trình tuyến tính.Nhiều khái niệm và sự kiện trình bày ở chương này được minh họa qua các ví dụ và hình vẽ cụ thể. Chương 3 “ Phương pháp điểm trong ” trình bày các khái niệm cơ bản về tâm giải tích, đường trung tâm gốc và đối ngẫu; những nội dung chính của 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 này được đánh giá là phương pháp điểm trong hiệu quả nhất 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 và thuật toán hiệu chỉnh. Vấn đề khởi sự và kết thúc thuật toán cũng được đề cập tới. Do thời gian và kiến thức còn hạn chế nên luận văn này mới chỉ đề cập tới những nội dung cơ bản của phương pháp điểm trong giải qui hoạch tuyến tính, chưa đi sâu vào các chi tiết thực thi thuật toán. Trong quá trình viết luận văn cũng như trong xử lý văn bản chắc chắn không tránh khỏi những sai sót nhất định. Tác giả luận văn rất mong nhận được sự góp ý của các thầy cô và các bạn đồng nghiệp để luận văn được hoàn thiện hơn. Nhân dịp này, tác giả xin bày tỏ lòng biết ơn sâu sắc đến thầy hướng dẫn GS-TS Trần Vũ Thiệu đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 Tác giả xin trân trọng cảm ơn các thầy, cô giáo Trường Đại học Khoa học- Đại học Thái Nguyên, Viện Toán học-Viện Khoa học và Công nghệ Việt Nam, đã giảng dạy và tạo mọi điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu. Tác giả cũng xin chân thành cảm ơn Ban giám hiệu, tổ toán –tin Trường THPT Ngô Quyền –Thái Nguyên và tập thể bạn bè đồng nghiệp cùng gia đình đã quan tâm giúp đỡ, động viên tác giả hoàn thành tốt luận văn này. Thái Nguyên, tháng 09 năm 2011. Người thực hiện Nguyễn Thị Hồng Lê Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 Chương 1 KIẾN THỨC CHUẨN BỊ Chương này nhắc lại các kết quả cơ bản về lý thuyết qui hoạch tuyến tính và 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 của thuật toán và dẫn ra ví dụ của V. Klee và G. Minty cho thấy thuật toán đơn hình là thuật toán thời gian mũ (chứ không phải thuật toán thời gian đa thức!). Nội dung của chương chủ yếu dựa trên các tài liệu [1], [2], [5] và [7]. 1.1 Qui hoạch tuyến tính và qui hoạch đối ngẫu Qui hoạch tuyến tính là bài toán tìm cực tiểu (cực đại) của một hàm tuyến tính f (x) trên một tập lồi đa diện D ⊂ Rn . Bài toán thường được 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 là x ∈ Rn+ . T là ký hiệu chuyển vị véctơ, D = {x ∈ Rn : Ax ≥ b, x ≥ 0} là một tập lồi đa diện. • Dạng chính tắc (canonical form): Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6  min f (x) = cT x : Ax = b, x ≥ 0 , trong đó các ký hiệu A ∈ Rm×n , b ∈ Rm , c, x ∈ Rn như ở trên. Trong bài toán này, tập D = {x ∈ Rn : Ax = b, x ≥ 0} cũng là một tập lồi đa diện. Trong hai dạng trên, f gọi là hàm mục tiêu, D gọi là tập ràng buộc hay miền chấp nhận được. Điểm x = (x1 , . . . , xn )T ∈ D gọi là một lời giải (điểm, nghiệm)chấp nhận được hay một phương án của bài toán. Một phương án đạt cực tiểu (cực đại) của hàm mục tiêu gọi là một lời giải (điểm, nghiệm) tối ưu hay một phương án tối ưu. Bài toán   max cT x : x ∈ D = − min −cT x : x ∈ D . Với mỗi bài toán qui hoạch tuyến tính, chỉ xảy ra một trong ba khả năng: a) Bài toán không có lời giải chấp nhận được (tập ràng buộc D rỗng). b) Bài toán có lời giải chấp nhận được, nhưng không có lời giải tối ưu. c) Bài toán có lời giải tối ưu (hữu hạn). Định lý sau nêu điều kiện để một qui hoạch tuyến tính có lời giải tối ưu. Định lý 1.1. Nếu một qui hoạch tuyến tính có lời giải chấp nhận được và hàm mục tiêu bị chặn dưới trong miền chấp nhận được (đối với bài toán  min) thì qui hoạch đó chắc 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 được x ∈ D mà đồng thời là đỉnh của D gọi là một lời giải cơ sở, nghĩa là x không thể biểu diễn dưới dạng một tổ hợp lồi của bất cứ hai lời giải chấp nhận được 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ó x = x1 = x2 . Định lý sau nêu một tính chất đặc trưng cho lời giải cơ sở của qui hoạch tuyến tính chính tắc với giả thiết m ≤ n và rank(A) = m. Định lý 1.2. Để một lời giải chấp nhận được x = {x1 , x2 , . . . , xn } của qui hoạch tuyến tính chính tắc là lời giải cơ sở, thì cần và đủ là các véctơ cột Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 Aj của ma trận A ứng với các thành phần xj > 0 là độc lập tuyến tính.  Từ định lý 1.2 dễ dàng suy ra các hệ quả sau đây: Hệ quả 1.1. Số lời giải cơ sở của qui hoạch tuyến tính chính tắc là hữu hạn. Hệ quả 1.2. Số thành phần dương trong mỗi lời giải cơ sở của qui hoạch tuyến tính chính tắc tối đa bằng m (m là số hàng của ma trận A). Mỗi qui hoạch tuyến tính đã cho (qui hoạch gốc) được gắn với một qui hoạch tuyến tính khác (qui hoạch đối ngẫu) và hai qui hoạch này có quan hệ chặt chẽ với nhau. Sau đây là hai dạng cặp bài toán đối ngẫu thường gặp. • Đối ngẫu của qui hoạch tuyến tính dạng chuẩn (qui hoạch gốc): (P )  min f (x) = cT x : Ax ≥ b, x ≥ 0 là qui hoạch tuyến tính (qui hoạch đối ngẫu): (Q)  max g (y) = bT y : AT y ≤ c, y ≥ 0 (AT là ma trận chuyển vị của ma trận A). • Đối ngẫu của qui hoạch tuyến tính dạng chính tắc  min f (x) = cT x : Ax = b, x ≥ 0  là quy hoạch tuyến tính max g (y) = bT y : AT y ≤ c (biến đối ngẫu y dấu tùy ý). Định lý 1.3. (Đối ngẫu yếu). Nếu x là một lời giải chấp nhận được của bài toán gốc (P) và y là một lời giải chấp nhận được của bài toán đối ngẫu (Q) thì f (x) = c1 x1 + c2 x2 + . . . + cn xn ≥ g (y) = b1 y1 + b2 y2 + . . . + bm ym .  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 Từ định lý đối ngẫu yếu ta suy ra ngay các kết luận trong hệ quả sau. Hệ quả 1.3. a) Giá trị mục tiêu của một lời giải đối ngẫu chấp nhận được là một cận dưới cho giá trị mục tiêu đối với mọi lời giải của bài toán gốc. b) Nếu hàm mục tiêu của bài toán gốc không bị chặn dưới trên tập ràng buộc của nó thì bài toán đối ngẫu không có bất kỳ lời giải chấp nhận được nào. c) Nếu hàm mục tiêu của bài toán đối ngẫu không bị chặn trên trên tập ràng buộc của nó thì bài toán gốc không có bất kỳ lời giải chấp nhận được nào. d) Nếu x∗ là một lời giải chấp nhận được của bài toán gốc, y ∗ là một lời giải chấp nhận được của bài toán đối ngẫu và f(x*) = g(y*) thì x∗ là lời giải tối ưu của bài toán gốc và y ∗ là lời giải tối ưu của bài toán đối ngẫu. Định lý 1.4. (Đối ngẫu mạnh). Nếu một qui hoạch có lời giải tối ưu thì qui hoạch đối ngẫu của nó cũng có lời giải tối ưu và các trị tối ưu bằng  nhau. Các kết quả trên cho thấy quan hệ sau giữa hai qui hoạch gốc và đối ngẫu. Định lý 1.5. (Định lý đối ngẫu cơ bản). Đối với mỗi cặp qui hoạch tuyến tính đối ngẫu nhau chỉ có một trong ba khả năng loại trừ nhau sau đây: a) Cả hai bài toán đều không có lời giải chấp nhận được. b) Cả hai bài toán đều có lời giải chấp nhận được. Khi đó, cả hai đều có lời giải tối ưu và giá trị tối ưu của hai hàm mục tiêu bằng nhau. c) Một bài toán có lời giải chấp nhận được và bài toán kia không có lời giải chấp nhận được. Khi đó, bài toán có lời giải chấp nhận được sẽ có giá trị tối ưu vô cực (+∞ hay −∞ tuỳ theo bài toán max hay min ).  Định lý 1.6. (Định lý độ lệch bù). Một cặp lời giải chấp nhận được x, y của hai qui hoạch đối ngẫu (P) và (Q) là cặp lời giải tối ưu khi và chỉ khi chúng nghiệm đúng các hệ thức: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9  yi  n X  aij xj − bi  = 0 với mọi i = 1, 2, . . . , m, j=1 xj cj − m X ! aij yi = 0 với mọi j = 1, 2, . . . , n. i=1 Định lý 1.7. (Định lý độ lệch bù chặt). Nếu cặp bài toán đối ngẫu (P) và (Q) có lời giải chấp nhận được thì tồn tại cặp lời giải tối ưu x∗ , y ∗ nghiệm đúng
y ∗ + (Ax∗ − b) > 0và x∗ + c − AT y ∗ > 0. 1.2 Phương pháp đơn hình và đơn hình đối ngẫu Bằng cách thực hiện một số phép biến đổi đơn giản, ta có thể đưa bài toán qui hoạch tuyến tính từ dạng này sang dạng khác. Vì thế khi giải ta chỉ cần chọn một dạng thuận tiện để xét mà không làm giảm tính tổng quát của phương pháp. Xét qui hoạch tuyến tính chính tắc (m ràng buộc đẳng thức, n biến):  min cT x : Ax = b, x ≥ 0 với A là ma trận m × n, b ∈ Rm ,cvà x ∈ Rn . Ta giả thiết : m ≤ n và rank (A) = m. Bài toán qui hoạch tuyến tính được gọi là không suy biến nếu tất cả các lời giải cơ sở của nó đều không suy biến, tức là đều có số thành phần dương bằng m. Bài toán gọi là suy biến nếu có dù chỉ một lời giải cơ sở suy biến. • Thuật toán đơn hình gốc Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 Giả thiết đã biết một lời giải cơ sở chấp nhận được không suy biến x. Không giảm tổng quát, có thể giả thiết x có dạng (đánh số lại các biến nếu cần): x = (x1 , x2 , . . . , xm , 0, . . . , 0) với xj > 0 (j = 1, 2, . . . , m) . Ký hiệu J = {j : xj > 0} = {1, 2, . . . , m} . Các vectơ {Aj , j ∈ J} là độc lập tuyến tính (Định lý 1.2) và |J| = m (do x không suy biến). Hệ vectơ {Aj , j ∈ J} gọi là cơ sở của lời giải x. Để cho tiện, đôi khi ta cũng gọi J (với các tính chất trên) là cơ sở của x. Các vectơ Aj và các biến xj với j ∈ J được gọi là các vectơ cơ sở và biến cơ sở tương ứng với x . Còn các vectơ Aj và các biến xj với j ∈ /J gọi là các vectơ và biến ngoài cơ sở. Ký hiệu B là ma trận lập nên từ các vectơ cơ sở đang xét: B = {A1 , A2 , . . . , Am } và đặt N ≡ {Ak : k ∈ / J}. Khi đó, rank (B) = m và tồn tại ma trận nghịch đảo B −1 . Mỗi vectơ cột Ak (k = 1, 2, . . . , n) của ma trận A được biểu diễn qua các vectơ cơ sở Aj , j ∈ J như sau: Ak = X zjk Aj = z1k A1 + z2k A2 + . . . + zmk Am vớik = 1, . . . , n (1.1) j∈J Ký hiệu các vectơ cột zk = (z1k , z2k , . . . , zmk )T , xB = (x1 , x2 , . . . , xm )T , vectơ hàng cB = (c1 , c2 , . . . , cm ). Hệ thức (1.1) viết lại thành Ak = Bzk . Từ đó zk = B −1 Ak . Mặt khác, ta có Ax = BxB = b ⇒ xB = B −1 b. Giá trị hàm mục tiêu tại x bằng cT x = cB xB = c1 x1 + c2 x2 + . . . + cm xm = cB B −1 b. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn (1.2) 11 Với mỗi k = 1, 2, . . . , n ta tính số sau đây, gọi là ước lượng của biến xk : ∆k = cB zk − ck = c1 z1k + c2 z2k + . . . + cm zmk − ck , k = 1, . . . , n (1.3) Theo phương trình Ax = b, tức là BxB +N xN = b với xB = (xj : j ∈ J)T và xN = (xj : j ∈ / J)T , ta có xB = B −1 (b − N xN ) ( nói riêng xB = B −1 b do xN = 0 ) , suy ra công thức biểu diễn các biến ngoài cơ sở theo các biến cơ sở: xB = xB − B −1 N xN . Từ đó, giá trị hàm mục tiêu tại x bằng cT x = cB xB + cN xN = cB xB − cB B −1 N xN + cN xN
= cB xB − cB B −1 N − cN xN (1.4) Chú ý là  B −1 N = B −1 Ak : k ∈ / J = {zk , k ∈ / J} thì vectơ ∆N = cB B −1 N − cN = {cB zk − ck , k ∈ / J}. Theo (1.2)-(1.3), công thức (1.4) viết lại thành cT x = cT x − X ∆k xk (1.5) k ∈J / Công thức này cho thấy x là lời giải tối ưu nếu ∆k ≤ 0 với mọi k ∈ / J. Còn nếu ∆N có các thành phần âm, chẳng hạn ∆s < 0 với một s ∈ / J nào đó, thì công thức (1.5) cho thấy rằng có thể giảm cT x , nghĩa là đưa biến ngoài cơ sở mới ứng với cơ sở mới J’ ( thay cho cơ sở cũ J) nói chung tốt hơn (hay ít ra không kém). Đó là ý tưởng chính của phương pháp đơn hình để giải qui hoạch tuyến tính. Ta có Định lý 1.8. (Dấu hiệu tối ưu). Nếu với lời giải cơ sở x của bài toán ta có các hệ thức ∆k ≤ 0 với mọi k ∈ / J thì x là một lời giải (cơ sở) tối ưu của bài toán. Định lý 1.9. (Dấu hiệu bài toán có trị tối ưu vô cực). Nếu đối với lời giải cơ sở x tồn tại chỉ số k ∈ / J sao cho ước lượng ∆k > 0 và zjk ≤ 0 với Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 12 mọi j ∈ J thì bài toán đã cho có trị tối ưu vô cực (−∞ đối với bài toán min). Có thể chứng minh được rằng nếu bài toán qui hoạch tuyến tính có lời giải chấp nhận được và không suy biến thì thuật toán đơn hình sẽ cho lời giải tối ưu (hữu hạn hay vô cực) sau một số hữu hạn lần thay đổi lời giải cơ sở. • Thuật toán đơn hình đối ngẫu. Như đã thấy thuật toán đơn hình gốc xuất phát từ một lời giải cơ sở chấp nhận được tương ứng với ma trận cơ sở B và luôn giữ cho B −1 b ≥ 0. Cơ sở B được biến đổi cho tới khi đạt lời giải tối ưu (∆k ≤ 0 với mọi k = 1, 2, . . . , n) hoặc khi phát hiện bài toán có giá trị tối ưu vô cực (có ∆k > 0 và mọi zjk ≤ 0,j = 1, 2, . . . , m). Khác với thuật toán đơn hình gốc, thuật toán đơn hình đối ngẫu bắt đầu từ một lời giải cơ sở đối ngẫu chấp nhận được, tức là một lời giải tương ứng với ma trận cơ sở B gồm m vectơ độc lập tuyến tính của A sao cho ∆ = cB B −1 A − c ≤ 0 và luôn giữ cho ∆ ≤ 0. Cơ sở B được biến đổi cho tới khi đạt lời giải tối ưu (B −1 b ≥ 0)
hoặc phát hiện bài toán không có phương án (có B −1 b i < 0 và mọi zik ≥ 0, k = 1, 2, . . . , n ). 1.3 Độ phức tạp của thuật toán Lý thuyết độ phức tạp là cơ sở để phân tích các thuật toán máy tính. Lý thuyết này nhằm hai mục đích: xây dựng các tiêu chuẩn để đo hiệu quả của các thuật toán khác nhau (do đó có thể so sánh các thuật toán dựa vào những tiêu chuẩn này) và đánh giá khó khăn vốn có của các loại bài toán khác nhau. Từ ngữ độ phức tạp ám chỉ số lượng nguồn lực (bộ nhớ, thời gian) mà máy tính đòi hỏi. Mục này tập trung vào nguồn lực đặc biệt, đó là thời gian tính toán. Tuy nhiên trong lý thuyết độ phức tạp, người ta không Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 13 quan tâm tới thời gian thực hiện một chương trình máy tính viết bằng một ngôn ngữ chương trình cụ thể, chạy trên một máy tính cụ thể với một bộ dữ liệu đầu vào cụ thể. Thời gian tính toán phụ thuộc nhiều yếu tố ngẫu nhiên. Thay vào đó, ta muốn gắn kết thuật toán với thước đo phản ánh được bản chất của những đòi hỏi về thời gian tính. Nói nôm na, để làm việc này ta cần xác định: • Khái niệm kích thước đầu vào (input size), • Tập các phép toán cơ bản (basic operations) và • Chi phí cho mỗi phép toán cơ bản. Hai đại lượng sau cho phép gắn kết với chi phí của một tính toán (cost of a computation). Nếu x là một bộ dữ liệu đầu vào bất kỳ thì chi phí C(x) của tính toán với đầu vào x là tổng các chi phí của mọi phép toán cơ bản cần thực hiện trong tính toán đó. Giả sử A là một thuật toán và In là tập tất cả các đầu vào kích thước n. Hàm chi phí trong trường hợp xấu nhất (worst-case cost function) của thuật toán A là hàm TAw (n) xác định bởi TAw (n) = sup C (x) x∈In Nếu biết phân bố xác suất trên tập In thì có thể xác định được hàm chi phí trung bình TAtb (n) theo TAtb (n) = En (C (x)) , trong đó En là kỳ vọng tính trên tập In . Tuy nhiên, tìm chi phí trung bình thường khó hơn chi phí xấu nhất, nên tất nhiên nảy ra câu hỏi là dùng phân bố xác suất nào. Bây giờ ta bàn cách chọn các đối tượng trong ba mục kể trên. Việc chọn tập các phép toán cơ bản nói chung là dễ. Đối với các thuật toán ta thường Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 14 chọn tập {+, −, ×, /, ≤} của bốn phép toán số học và phép so sánh. Lựa chọn khái niệm về kích thước đầu vào và chi phí của các phép toán số học cơ bản phụ thuộc vào loại dữ liệu thuật toán cần xử lý. Có loại dữ liệu được miêu tả không quá số lượng cố định về bộ nhớ của máy tính; một số loại khác lại đòi hỏi một số lượng thay đổi. Ví dụ về loại thứ nhất là các số thực dấu phẩy động có độ chính xác cố định được lưu trữ trong một lượng bộ nhớ cố định (thường là 32 hoặc 64 bit). Với loại dữ liệu này kích thước của mỗi số được lấy là 1 và do đó mỗi số có kích thước đơn vị (unit size). Ví dụ về loại thứ hai là các số nguyên đòi hỏi một số bít xấp xỉ bằng logarit (cơ số 2) của giá trị tuyệt đối của chúng. Số logarit này thường được gọi là kích thước bit (bit size) của số nguyên. Ý tưởng tương tự cũng được áp dụng cho các số hữu tỉ. Giả sử B là một loại dữ liệu nào đó và x = (x1 , . . . , xn ) ∈ B n . Nếu B thuộc loại thứ nhất kể trên thì ta định nghĩa size (x) = n. Trái lại, size(x)=tổng kích thước bit của các xi (i = 1, . . . , n) . Chi phí của mỗi phép toán trên hai số kích thước đơn vị được lấy là 1 và được gọi chi phí đơn vị (unit cost). Trong trường hợp kích thước bit, chi phí của phép toán trên hai số là tích hai kích thước bit của chúng (đối với phép nhân và phép chia) hoặc bằng số lớn nhất trong hai kích thước ấy (đối với phép cộng, phép trừ và phép so sánh). Việc xét các dữ liệu nguyên và hữu tỉ với kích thước bit của chúng và xét chi phí bit cho các phép toán số học thường được gọi là mô hình tính toán Turing (Turing model of computation). Việc xét các số thực lý tưởng hóa với kích thước đơn vị và chi phí đơn vị được gọi là mô hình số học các số thực (real number arithmetic model). Khi so sánh các thuật toán ta cần làm rõ mô hình tính toán nào được dùng để nhận được đánh giá về độ phức tạp. Khái niệm cơ bản liên quan tới cả hai mô hình tính toán là khái niệm Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 15 thời gian đa thức(polynomial time). Một thuật toán A được gọi là thuật toán thời gian đa thức nếu TAw (n) bị chặn trên bởi một đa thức. Một bài toán có thể giải trong thời gian đa thức nếu có một thuật toán thời gian đa thức để giải bài toán đó. Khái niệm thời gian đa thức trung bình (average polynomial time) được hiểu theo nghĩa tương tự, bằng cách thay TAw (n) bởi TAtb (n). Khái niệm thời gian đa thức thường được dùng để hình thức hóa hiệu quả của thuật toán trong lý thuyết độ phức tạp. 1.4 Ví dụ Klee-Minty về độ phức tạp mũ Khi dùng phương pháp đơn hình giải qui hoạch tuyến tính chính tắc với ma trận hệ số A ∈ Rm×n , b ∈ Rm , c ∈ Rn , số lần lặp đơn hình để giải bài toán, bắt đầu từ một lời giải cơ sở chấp nhận được, là một bội số nhỏ của m, thường là giữa 2m và 3m. Trên thực tế, Dantzig đã quan sát thấy rằng đối với các bài toán có số ràng buộc m ≤ 50, số biến n ≤ 200 thì số lần lặp đơn hình nói chung nhỏ hơn 1, 5m. Có lúc các nhà nghiên cứu đã tin và thử tìm chứng minh rằng thuật toán đơn hình (hay biến thể nào đó của nó) luôn đòi hỏi số lần lặp bị chặn bởi một đa thức theo kích thước bài toán. Mãi cho đến khi Victor Klee và George Minty đưa ra lớp bài toán qui hoạch tuyến tính mà mỗi bài trong số đó đòi hỏi số lần lặp là hàm mũ, khi bài toán được giải theo phương pháp đơn hình quen thuộc. Để tiện tham khảo, sau đây nêu một dạng ví dụ của V.Klee và G.Minty. n X 10n−j xj → max (KM ) j=1 với điều kiện 2 i−1 X 10i−j xj + xi ≤ 100i−1 , i = 1, . . . , n, j=1 xj ≥ 0, j = 1, . . . , n. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 16 Dễ dàng đưa bài toán trên về dạng bài toán qui hoạch tuyến tính chính tắc. Trường hợp riêng khi n = 3 là bài toán: 100x1 + 10x2 + x3 → max với điều kiện x1 ≤ 1, 20x1 + x2 ≤ 100, 200x1 + 20x2 + x3 ≤ 10000, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 Trong trường hợp này bài toán có ba ràng buộc bất đẳng thức và ba biến (với các biến có ràng buộc không âm). Sau khi thêm vào các biến bù (để đưa các ràng buộc bất đẳng thức về ràng buộc đẳng thức) bài toán có dạng chính tắc. Hệ ràng buộc có m = 3 phương trình và n = 6 biến không âm. Có thể kiểm tra lại rằng (bằng cách lập bảng đơn hình và giải theo thuật toán đơn hình) cần 23 −1 = 7 lần biến đổi bảng đơn hình để giải bài toán (ở mỗi lần lặp ta chọn cột xoay là cột có ước lượng âm nhỏ nhất, vì đây là bài toán tìm cực đại). Kết quả giải ví dụ này được ghi lại ở bảng 1.1 với phương án tối ưu tìm được là: xopt = (0, 0, 10000, 1, 100, 0)T , fmax = 10000. Bài toán (KM) tổng quát cần 2n − 1 lần lặp theo đơn hình gốc và thực tế đó là số đỉnh của đa thức ràng buộc trừ đi một. Để hình dung điều này tồi tệ như thế nào, ta xét trường hợp n = 50. Ta có 250 − 1 ≈ 1015 . Trong một năm với 365 ngày, có khoảng 3 × 107 giây. Nếu một máy tính chạy liên tục và thực hiện được một triệu phép lặp đơn hình trong một giây thì cũng phải cần một thời gian khoảng 1015 ≈ 33năm(!) 3 × 107 × 106 để giải bài toán thuộc lớp (KM) này, nhờ dùng qui tắc chọn cột xoay "tham Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn