Tài liệu Phương pháp giải một lớp bài toán quy hoạch nguyên phi tuyến

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN DUY LONG PHƯƠNG PHÁP GIẢI MỘT LỚP BÀI TOÁN QUY HOẠCH NGUYÊN PHI TUYẾN LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - Năm 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN DUY LONG PHƯƠNG PHÁP GIẢI MỘT LỚP BÀI TOÁN QUY HOẠCH NGUYÊN PHI TUYẾN 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 2012 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 4 1 MỘT SỐ KIẾN THỨC CHUẨN BỊ 4 1.1 Tập lồi, hàm lồi và một số tính chất . . . . . . . . . . . . . 4 1.1.1 Tập hợp lồi. . . . . . . . . . . . . . . . . . . . . . . 4 1.1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Thuật toán đa thức . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Bài toán quy hoạch nguyên phi tuyến . . . . . . . . . . . . 10 2 PHƯƠNG PHÁP TRỰC TIẾP GIẢI BÀI TOÁN (P) 13 2.1 Tính chất nghiệm của bài toán(P). . . . . . . . . . . . . . 13 2.2 Cơ sở phương pháp giải 2.3 Thuật toán đa thức giải bài toán . . . . . . . . . . . . . . . 21 2.3.1 2.3.2 Thuật toán A. . . . . . . . . . . . . . . . . . . . 16 . . . . . . . . . . . . . . . . . . . . 21 Đánh giá độ phức tạp của thuật toán. . . . . . . . . 22 3 MỘT SỐ HƯỚNG MỞ RỘNG BÀI TOÁN (P) 28 3.1 Giảm kích thước bài toán (P) . . . . . . . . . . . . . . . . . 28 3.2 Thay đổi ràng buộc . . . . . . . . . . . . . . . . . . . . . . 33 3.2.1 Thêm, bớt sinh viên. . . . . . . . . . . . . . . . . . 33 3.2.2 Thêm, bớt chuyên đề. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên . . . . . . . . . . . . . . . . 34 http://www.lrc-tnu.edu.vn i 3.2.3 3.3 Thêm điều kiện phụ vào bài toán (P) . . . . . . . . 35 Thay đổi hàm mục tiêu của bài toán (P) . . . . . . . . . . . 37 3.3.1 Bài toán với hàm mục tiêu mở rộng . . . . . . . . . 37 3.3.2 Bài toán với hàm mục tiêu lõm . . . . . . . . . . . . 40 3.3.3 Bài toán vận tải với điều kiện phụ. . . . . . . . . . . 42 KẾT LUẬN 44 Tài liệu tham khảo 45 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 Tối ưu tổ hợp (Combinatorial Optimization) hay còn gọi là tối ưu rời rạc là một bộ phận quan trọng của tối ưu hoá. Nó bao gồm nhiều bài toán tối ưu với biến số nhận các giá trị rời rạc (không liên tục) và nhiều phương pháp giải khác nhau cho các lớp bài toán tổng quát và riêng lẻ. Các bài toán tối ưu tổ hợp rất phong phú, đa dạng và có nhiều ứng đụng rộng rãi trong thực tiễn. Một số mô hình tối ưu tổ hợp thuộc loại các bài toán "dễ giải" (có thuật toán đa thức để giải), nhưng phần lớn là các bài toán "khó giải" (chưa có thuật toán đa thức để giải). Nhiều vấn đề lý thuyết và thực tiễn có thể diễn đạt dưới dạng một bài toán tối ưu rời rạc. Những bài toán như vậy thường có các cấu trúc riêng nào đó. Nếu biết khai thác cấu trúc riêng đó thì có thể tìm ra cách giải hiệu qủa. Luận văn đề cập tới một lớp bài toán tối ưu rời rạc, cụ thể là bài toán qui hoạch nguyên phi tuyến (biến số nhận các giá trị nguyên, hàm mục tiêu phi tuyến), có thể giải được bằng thuật toán đa thức nhờ khai thác đặc điểm cấu trúc của bài toán. Bài toán được xét trong luận văn có cấu trúc khá đặc biệt và có nội dung thực tiễn thiết thực. Có thể xem nó như mô hình toán học cho một số bài toán thường gặp trong thực tế (mô hình xếp lịch học tập trong các trường học) và hoàn toàn có thể áp dụng được trong thực tiễn. Việc phân tích lớp bài toán này giúp ích cho việc đi sâu tìm hiểu sau này về các bài toán tối ưu rời rạc nói chung và những ứng dụng của chúng nói riêng. Nội dung luận văn được chia thành ba chươ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 2 Chương 1 với tiêu đề "Một số kiến thức chuẩn bị" trình bày những kiến thức cơ bản cần thiết về tập lồi và hàm lồi làm cơ sở lý thuyết cho việc phân tích cấu trúc và xây dựng các thuật toán ở những chương sau. Tiếp theo, chương này trình bày vắn tắt khái niệm thuật toán thời gian đa thức. Cuối chương giới thiệu khái quát mô hình và ý nghĩa thực tế của lớp bài toán qui hoạch nguyên phi tuyến được xét trong luận văn. Chương 2 với tiêu đề "Phương pháp trực tiếp giải bài toán (P)" phân tích cấu trúc đặc biệt và nêu ra những tính chất nghiệm đáng chú ý của bài toán qui hoạch nguyên phi tuyến xét trong luận văn, các tính chất này giúp ích cho việc xây dựng thuật toán giải. Mục tiếp theo của chương trình bày thuật toán thời gian đa thức giải bài toán, bằng cách sử dụng kỹ thuật điều chỉnh dần phương án và kỹ thuật gán số cho các hàng và cột, tương tự như trong các phương pháp giải bài toán vận tải thông thường của qui hoạch tuyến tính. Thuật toán được minh hoạ qua một ví dụ số đơn giản và trực quan. Chương 3 với tiêu đề "Một số hướng mở rộng bài toán" xét vấn đề xử lý sơ bộ (tiền xử lý) các dữ kiện ban đầu của bài toán nhằm giảm bớt kích thước của bài toán cần giải (nếu có thể). Sau đó, xét sự mở rộng bài toán theo hai hướng: thay đổi điều kiện ràng buộc (thêm hay bớt sinh viên, thêm hay bớt chuyên đề, thêm điều kiện phụ ...) và thay đổi hàm mục tiêu (bài toán với hàm mục tiêu đơn điệu tăng và bài toán với hàm mục tiêu lõm). Do thời gian và kiến thức còn hạn chế nên chắc chắn luận văn còn có những thiếu sót nhất định, kính mong quý thầy cô và các bạn đóng góp để tác giả tiếp tục hoàn thiện luận văn này. Nhân dịp này, tác giả xin bày tỏ lòng biết ơn sâu sắc tới thầy hướng dẫn GS.TS Trần Vũ Thiệu đã tận tình hướng dẫn, giúp đỡ trong suốt quá trình làm luận văn. Tác giả xin trân trọng cảm ơn tập thể thầy cô giáo trường Đại họ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 3 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 giúp đỡ tác giả trong quá trình 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 số 1 huyện Bát Xát – Lào Cai và tập thể bạn bè, đồng nghiệp và 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 7 năm 2012 Người thực hiện Nguyễn Duy Long 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 Chương 1 MỘT SỐ KIẾN THỨC CHUẨN BỊ Chương này sẽ trình bày một số khái niệm và kiến thức cơ bản về giải tích lồi, cần thiết cho việc phân tích lý thuyết và xây dựng thuật toán trong các chương sau. Tiếp đó trình bày khái niệm thuật toán đa thức và cuối cùng giới thiệu bài toán qui hoạch nguyên phi tuyến được xét trong luận văn. Nội dung của chương được tham khảo từ các tài liệu [2], [3] và [6]. 1.1 1.1.1 Tập lồi, hàm lồi và một số tính chất Tập hợp lồi. Khái niệm về tập hợp lồi là một khái niệm cơ bản của giải tích lồi và quy hoạch lồi. Nhiều tính chất quan trọng và thú vị của bài toán quy hoạch có được trên miền ràng buộc là một tập hợp lồi. Định nghĩa 1.1. Một tập X trong không gian Euclide Rn được gọi là một tập lồi nếu ∀x1 , x2 ∈ X và ∀λ ∈ [0; 1] ta có λx1 + (1 − λ2 )x ∈ X . Như vậy nếu X là một tập lồi thì nó chứa trọn đoạn thẳng nối hai điểm bất kỳ của nó. Ví dụ 1.1: • Các tập afin nói chung đều là tập lồi. • Các nửa không gian đóng: {x :< a, x >6 α}, {x :< a, x >> α} . 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 • Các nửa không gian mở: {x :< a, x >< α}, {x :< a, x >> α} . • Siêu phẳng H = {x :< a, x >= b} trong Rn . Bao lồi của một tập A là một tập lồi nhỏ nhất chứa A, ký hiệu là coA. Đây chính là giao của tất cả các tập lồi chứa A. Nếu X là một tập lồi thì nó chứa bao lồi của mọi tập con của nó. Cho A, B là hai tập bất kỳ trong Rn , tổ hợp lồi của A và B là tập hợp tất cả các điểm thuộc Rn có dạng: x = λa+(1−λ)b, a ∈ A, b ∈ B, 0 6 λ 6 1. Định lý 1.1. Tập lồi là đóng với phép giao, phép cộng, phép nhân với một số và phép lấy tổ hợp tuyến tính, tức là nếu A và B là hai tập lồi trong Rn thì các tập hợp sau cũng là lồi: 1. A ∩ B := {x : x ∈ A, x ∈ B} . 2. λA + βB := {x = λa + βb : a ∈ A, b ∈ B, 0 6 λ, β 6 1} . Hệ quả. Miền chứa nghiệm của hệ bất phương trình tuyến tính dạng:    a11 x1 + a12 x2 + ... + a1n xn 6 b1 a21 x1 + a22 x2 + ... + a2n xn 6 b2   ............................................. am1 x1 + am2 x2 + ... + amn xn 6 bm là một tập lồi. Người ta còn gọi đó là tập lồi đa diện hoặc còn gọi là một khúc lồi. Một khúc lồi giới nội gọi là một đa diện lồi. Định lý 1.2. Một tập lồi đa diện X (có thể không giới nội) có ít nhất một đỉnh được biểu diễn bởi tập hợp tât cả những điểm có dạng: P P P x= λi di + µj g j , trong đó λi = 1, λi , µj > 0 với mọi i, j còn i∈I i∈I i∈I các di với i ∈ I là đỉnh của X, với j ∈ J là phương các cạnh vô hạn của X. Chú ý rằng nếu X giới nội thì nó không có các cạnh vô hạn, do đó trong biểu diễn trên chỉ còn lại tổng thứ nhất. Trong trường hợp này, mọi điểm của X đều biểu diễn qua tổ hợp lồi của các đỉnh của X. 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 1.1.2 Hàm lồi Định nghĩa 1.2. Hàm số f (x) xác định trên tập lồi X ⊂ Rn được gọi là hàm lồi trên X, nếu với mọi x, y ∈ X, 0 6 λ 6 1 ta có: f (λx + (1 − λ)y) 6 λf (x) + (1 − λ)f (y). Hàm f (x) được gọi là hàm lồi chặt trên X nếu với ∀x1 , x2 ∈ X, x1 6=  

x2 , 0 < λ < 1 ta có f (1 − λ) x1 + λx2 < (1 − λ) f x1 + λf x2 . Hiển nhiên hàm lồi chặt là hàm lồi, nhưng điều ngược lại chưa chắc đúng. Hàm f (x) gọi là hàm tựa lồi trên tập lồi X nếu f (λx + (1 − λ) y) 6 max {f (x) , f (y)} ∀x, y ∈ X, 0 6 λ 6 1. Hàm f (x) được gọi là lõm (tựa lõm) trên tập lồi X nếu hàm −f (x) là lồi (tựa lồi) trên X. Như thường lệ, các hàm λf, f + g, max (f, g) được định nghĩa như sau: (λf ) (x) := λf (x) , (f + g) (x) := f (x) + g (x) , max (f, g) (x) := max (f (x) , g (x)) . Các hàm lồi là đóng đối với phép tổ hợp tuyến tính không âm và phép lấy max. Cụ thể ta có định lý như sau: Định lý 1.3. Cho f là một hàm lồi trên tập lồi X và g là hàm lồi trên tập lồi Y. Lúc đó các hàm sau là lồi trên X ∩ Y : 1. λf + βg ∀λ, β > 0, 2. max (f, g) . Định nghĩa 1.3. Cho X ⊂ Rn khác rỗng và hàm f : X → R (không nhất thiết lồi). Một điểm x∗ ∈ X được gọi là cực tiểu địa phương của f trên X, nếu tồn tại lân cận mở U của x∗ sao cho f (x∗ ) 6 f (x) với mọ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 7 x ∈ X ∩ U . Điểm x∗ ∈ X được gọi là cực tiểu tuyệt đối của f trên X nếu f (x∗ ) 6 f (x) với ∀x ∈ X . Dưới đây là một số tính chất cơ bản về cực trị của hàm lồi và hàm lõm. Định lý 1.4. Bất kỳ cực tiểu địa phương nào của hàm lồi trên tập lồi cũng là cực tiểu tuyệt đối. Hệ quả. Bất kỳ cực đại địa phương nào của hàm lõm trên tập lồi cũng là cực đại tuyệt đối. Định lý 1.5. Cực tiểu của một hàm lõm (nếu có) trên một tập lồi có điểm cực biên bao giờ cũng đạt tại một điểm cực biên. 1.2 Thuật toán đa thức • Xét một bài toán X gồm một tập các ca (dữ kiện) của nó. Cỡ của một ca dữ kiện d ∈ X của bài toán là độ dài l(d) (đo bằng tổng số bit) của dãy ký tự 0-1 biểu diễn nhị phân dữ kiện đầu vào đó. Giả sử có một thuật toán A có thể giải mỗi ca của X trong một số hữu hạn phép toán sơ cấp (cộng, trừ, so sánh, v.v ...). Nếu xem như mỗi phép toán sơ cấp tốn một đơn vị thời gian để thực hiện thì thời gian chạy thuật toán bằng tổng số các phép toán sơ cấp cần thực hiện. Thời gian ấy là một hàm tA : X → R+ . Với mỗi số s, ta xét tất cả các ca có cỡ bằng s và lấy thời gian tối đa để giải một ca cỡ s, tức là số fA (s) = max{tA (d) : d ∈ X, l(d) = s} làm thời gian chạy của thuật toán A. Thuật toán A được gọi là thuật toán có thời gian đa thức, hay nói tắt, thuật toán thời gian đa thức hay nói gọn hơn, thuật toán đa thức, nếu fA (s) = O(sk ) với một k nào đó, nghĩa là có một hằng số c và một số tự nhiên s’ sao cho fA (s) 6 csk với mọi s > s0 . • Trong lý thuyết độ phức tạp tính toán, lớp các bài toán có thể giải được trong thời gian đa thức gọi là lớp P, còn NP là lớp các bài toán 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 8 khi cho một lời giải đúng thì có thể kiểm tra xác nhận tính đúng đắn của lời giải đó trong thời gian đa thức (chú ý đây không nói gì về lời giải sai); nói cách khác, NP là lớp các bài toán có thể giải được trong thời gian đa thức bằng một thuật toán "phi tất định" (non-deterministic) (một thuật toán phi tất định gồm hai giai đoạn: 1) đoán một lời giải tối ưu; 2) kiểm tra xác nhận đó đúng là lời giải tối ưu). Đương nhiên P ⊂ NP, nhưng không rõ liệu có P = NP không. Có nhiều bài toán tối ưu thuộc lớp P (chẳng hạn, bài toán qui hoạch tuyến tính) nhưng cũng có rất nhiều bài toán mà cho đến nay mặc dù những cố gắng của nhiều nhà toán học, chưa ai tìm ra được một thuật toán đa thức để giải nó, mà cũng chưa ai chứng minh được không thể có một thuật toán đa thức cho bài toán ấy, nghĩa là không ai biết bài toán ấy có thuộc P không (bài toán người du lịch là một trong số rất nhiều bài toán như thế). Giả thuyết P 6= NP cho đến nay vẫn chưa có ai chứng minh hay bác bỏ được. Đó là một câu hỏi lớn của toán học có lẽ còn tồn tại lâu dài trong thế kỷ XXI. • Một bài toán X1 gọi là qui dẫn đa thức được về một bài toán X2 nếu ứng với mỗi ca dữ kiện d ∈ X1 có một thuật toán đa thức để qui d về một ca dữ kiện g(d) ∈ X2 . Như vậy, hễ X2 giải được trong thời gian đa thức thì X1 cũng giải được trong thời gian đa thức. Ta nói một bài toán X là NP - đầy đủ (NP - complete) nếu X ∈ NP và mọi bài toán thuộc lớp NP đều qui dẫn đa thức được về X. Như vậy, hễ X giải được trong thời gian đa thức thì mọi bài toán thuộc NP cũng đều giải được trong thời gian đa thức, có nghĩa là NP = P. Một bài toán NP - đầy đủ nổi tiếng là bài toán tìm chu trình Hamilton của một đồ hình (graph). Một bài toán NP - đầy đủ khác là bài toán cái túi (knapsack problem): tìm x ∈ Rn nghiệm đú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 9 n X aj xj = b, xj ∈ {0, 1}(j = 1, 2, ..., n)và đạt cực đại của j=1 n X cj xj . j=1 Ta nói một bài toán X là NP -khó (NP - hard) nếu mọi bài toán thuộc NP đều qui dẫn đa thức được về X. Như vậy, mọi bài toán NP - đầy đủ đều là NP - khó. Vì thế, lớp bài toán NP - khó rộng hơn lớp bài toán NP - đầy đủ, vì nó bao gồm các bài toán thuộc lớp NP, cũng như các bài toán không thuộc NP . Bài toán cái túi được xem như "dễ nhất" trong số các bài toán NP - khó. Bài toán sau là NP - khó, nhưng không biết có thuộc lớp NP không: Cho các số tự nhiên c1 , c2 , ..., cn , k và L. Có chăng k tập con khác nhau S1 , S2 , ..., Sk ⊂ {1, 2, ..., n} sao cho tổng số các phần tử của mỗi tập con này đều không nhỏ hơn L, nghĩa là: X (Si ) = X (cj ) > L với mọi i = 1, 2, ..., k? ci ∈Si Không có thuật toán đa thức cho bất kỳ bài toán NP - khó nào, trừ khi P = NP. Khi nghiên cứu giải quyết các bài toán thực tế, việc xác định nó thuộc lớp nào trong số các lớp kể trên không chỉ có ý nghĩa lý thuyết mà còn có ý nghĩa thực tế quan trọng. Nếu bài toán đang xét được xác nhận là thuộc một trong các lớp NP, NP - đầy đủ hay NP - khó thì ít có hy vọng tìm được thuật toán hiệu quả để giải nó. Vì vậy, tốt hơn hết là hãy hướng tới việc xây dựng những thuật toán gần đúng cho các bài toán như thế. 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 1.3 Bài toán quy hoạch nguyên phi tuyến Cho trước ma trận A = aij
mxn với aij ∈ {0, 1} và cho trước các số nguyên dương pi (0 < pi 6 n) , i = 1, 2, ..., m. Xét bài toán tối ưu sau đây: (P ) f (x) = max 16j 6n n X m X xij → min, (1.1) i=1 xij = pi , i = 1, 2, ..., m, (1.2) j=1 0 6 xij 6 aij , xij nguyên, i = 1, 2, ..., m, j = 1, 2, ..., n. (1.3)  Hệ thống số x = xij thỏa mãn các điều kiện (1.2), (1.3) được gọi là một phương án của bài toán (P). Một phương án đạt cực tiểu của (1.1) gọi là phương án tối ưu hay lời giải của bài toán (P). Một số nhận xét: - Hàm mục tiêu (1.1) là hàm lồi, các ràng buộc (1.2), (1.3) là ràng buộc nguyên, tuyến tính. Vì thế (P) thuộc lớp bài toán quy hoạch nguyên phi tuyến (nếu bỏ điều kiện xij nguyên thì lời giải của bài toán nói chung sẽ khác). Tuy nhiên như dưới đây sẽ thấy, bài toán (P) có thể quy về bài toán quy hoạch nguyên tuyến tính có cấu trúc đặc biệt. - Ràng buộc (1.2) có thể thay bằng ràng buộc nới lỏng (1.2’) mà không làm ảnh hưởng tới lời giải của (P): n P xij > pi , i = 1, 2, ..., m. (1.2’) i=1 Có thể thấy bài toán (P) tương đương với bài toán quy hoạch nguyên phi tuyến tính sau đây: (  n ) m X X  (P 0 ) min t  xij > pi , ∀i; xij 6 t, ∀j; 0 6 xij 6 aij , ∀i, j; t nguyên  i=1 i=1 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 11 Lưu ý rằng, bài toán (P’) rất giống với bài toán vận tải thông thường, nhưng ở đây có thêm biến số t và biến số t đòi hỏi phải có điều kiện nguyên. Vì t nguyên nên (P’) sẽ có lời giải nguyên. Bài toán (P) là mô hình toán học cho một số bài toán lập lịch thường gặp trong thực tiễn. Dưới đây là hai ví dụ điển hình. Bài toán xếp lịch học tập: Có m sinh viên và n chuyên đề cho các sinh viên này. Với mỗi sinh viên i cho biết:  1 nếu sinh viên i ưa thích chuyên đề j, aij = 0 nếu ngược lại. với i = 1, 2, ..., m; j = 1, 2, ..., n và pi nguyên dương là số chuyên đề mà sinh viên i cần học, i=1,2,. . . , m. Hãy tìm cách bố trí sinh viên học các chuyên đề phù hợp với họ sao cho mỗi sinh viên học đủ số chuyên đề cần học và số người trong các chuyên đề có nhiều sinh viên tham dự nhất là nhỏ nhất có thể được? Đặt các biến số:  1 nếu sinh viên i tham gia chuyên đề j, xij = 0 nếu ngược lại. với i = 1, 2, ..., m; j = 1, 2, ..., n. Rõ ràng các xij phải thỏa mãn điều kiện 0 6 xij 6 aij (mỗi sinh viên chỉ tham dự những chuyên đề mà họ ưa thích) và xi1 + xi2 + ... + xin = pi (tổng số chuyên đề sinh viên i tham dự vừa đủ yêu cầu). Khi đó, số lượng sinh viên tham dự nhóm chuyên đề j là x1j + x2j + ... + xmj và dễ thấy mô hình toán học cho bài toán đặt ra chính là bài toán (P). Bài toán lập lịch cho hội nghị: Một hội nghị có m tiểu ban, mỗi tiểu ban cần sinh hoạt trong một ngày tại phòng họp phù hợp với nó. Có n phòng họp dành cho việc sinh hoạt của các tiểu ban. Cho biết:  aij = 1 nếu phòng họp j thích hợp với tiểu ban i, 0 nếu ngược lại. với i = 1, 2, ..., m; j = 1, 2, ..., 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 12 Hãy bố trí các phòng họp cho các tiểu ban sao cho hội nghị kết thúc sau ít ngày làm việc nhất? Đặt các biến số:  1 nếu tiểu ban i làm việc tại phòng họp j, xij = 0 nếu ngược lại. với i = 1, 2, ..., m; j = 1, 2, ..., n. Khi đó, dễ dàng thấy mô hình toán học cho bài toán đặt ra chính là bài toán (P), trong đó pi = 1 với mọi i = 1, 2, . . . , m (trong trường hợp này hàm mục tiêu (1.1) biểu thị số ngày làm việc của hội nghị). Tóm lại, chương này đã nhắc lại ngắn gọn một số kiến thức cơ bản về tập lồi vầ hàm lồi (có thể xem chứng minh đầy đủ các kết quả nêu ở chương này trong [2]). Khái niệm thuật toán đa thức giải bài toán cũng được trình bày ngắn gọn và dễ hiểu ở chương này. Cuối chương đề cập tới lớp bài toán qui hoạch nguyên phi tuyến, có cấu trúc đặc biệt, được xét trong luận văn: nêu mô hình và ý nghĩa thực tế của bài toán này. 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 Chương 2 PHƯƠNG PHÁP TRỰC TIẾP GIẢI BÀI TOÁN (P) Chương này phân tích cấu trúc của bài toán qui hoạch nguyên phi tuyến được xét trong luận văn và nêu các tính chất đáng chú ý về nghiệm của bài toán. Sau đó, trình bày thuật toán đa thức giải bài toán, nhờ sử dụng kỹ thuật điều chỉnh dần phương án và kỹ thuật đánh số các hàng, cột trong bài toán. Nội dung của chương được tham khảo từ các tài liệu [1], [4] và [5]. 2.1 Tính chất nghiệm của bài toán(P). Trong mục này sẽ nêu điều kiện để bài toán (P) có nghiệm và nêu ra ước lượng khoảng cho giá trị tối ưu (1.1) của bài toán. Bổ đề 2.1. Bài toán (P) có phương án khi và chỉ khi: n X aij > pi , i = 1, 2, ..., m (2.1) j=1 Chứng minh. Điều kiện cần của Bổ đề là hiển nhiên, vì từ các điều kiện (1.2) và (1.3) ta suy ra các bất đẳng thức trong (2.1). Để chứng minh điều kiện đủ, ta chỉ cần chỉ ra rằng, nếu điều kiện (2.1) được thực hiện thì bài toán (P) luôn có phương án. Thực vậy, giả sử điều kiện (2.1) đượ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 14 thực hiện. Khi đó, nếu đặt:  Ii = j : aij = 1, 1 6 j 6 n thì |Ii | > pi , i = 1, 2, ..., m. Do đó, nếu chọn tùy ý các tập Ii+ ⊂ Ii thỏa
mãn |Ii | = pi , i = 1, 2, ..., m, thì X ∗ = x∗ij với các thành phần được xác định theo công thức x∗ij = 1, j ∈ Ii+ , x∗ij = 0, j ∈ / Ii∗ , i = 1, 2, ..., m, là phương án của bài toán (P). Bổ đề được chứng minh.  Điều kiện (1.3) cho thấy tập phương án của bài toán (P) là bị chặn, vì thế (2.1) cũng là điều kiện cần và đủ để bài toán (P) có nghiệm (phương án tối ưu). Để tìm khoảng ước lượng cho giá trị tối ưu (1.1) ta đưa vào các ký hiệu: ai = n X aij , i = 1, 2, ..., m, j=1 bj = m X aij , j = 1, 2, ..., n, i=1 p= m X pi i=1 (ai biểu thị số chuyên đề mà sinh viên i ưa thích, bj biểu thị số sinh viên ưa thích chuyên đề j, còn p là tổng số chuyên đề mà mọi sinh viên cần tham dự). Ta giả thiết ai > pi , ∀i = 1, 2, ..., m, và bj > 0 với mọi j = 1, 2, . . . , n, nghĩa là mỗi chuyên đề phải có ít nhất một sinh viên muốn tham dự. Rõ ràng, ta có bj 6 m, ∀j . Ký hiệu k ∗ là trị tối ưu của hàm mục tiêu (1.1). Khi đó, ta có:   Bổ đề 2.2.Ký hiệu k = np , trong đó ]x[ biểu thị số nguyên nhỏ nhất lớn hơn hay bằng x và k = max bj . Khi đó ta có ước lượng sau đây: 16j 6n k 6 k ∗ 6 k. 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 Chứng minh. Tổng số chuyên đề mà mọi sinh viên cần tham dự là p, mà mỗi chuyên đề có tối đa k ∗ sinh viên tham dự nên k ∗ .n > p hay k ∗ > np . Vì k* nguyên nên k ∗ > k . Mặt khác, do xij 6 aij nên m X xij 6 i=1 m X aij = b, ∀j = 1, 2, ..., n. i=1 Từ đó suy ra: max 16j 6n m X xij 6 max bj = k 16j 6n i=1 và do đó k ∗ 6 k . Bổ đề được chứng minh.  Không giảm tính tổng quát, ta có thể giả thiết 0 < b1 6 b2 6 ... 6 bn 6 m. (2.2) Nếu k được xác định như trong bổ đề 2.2 thỏa mãn k > b1 thì có thể cải tiến cận dưới của k ∗ như sau: Bổ đề 2.3.Với các giả thiết đã nêu trên, nếu k > b1 thì k ∗ > k 0 > k, 0 trong đó k là số nguyên nhỏ nhất thỏa mãn 0 bs < k 6 bs+1 và p 6 s X 0 bi + k . (n − s) , 1 6 s 6 n − 1. (2.3) i=1 Chứng minh. Từ Bổ đề 2.3 và giả thiết k > b1 ta có k ∗ > b1 . Theo cách sắp xếp (2.2) nên tìm được chỉ số t, 1 6 t 6 n−1, thỏa mãn bt < k ∗ 6 bt+1 . Vì các chuyên đề j với j 6 t có tối đa bj < k ∗ sinh viên tham dự, nên k* phải thỏa mãn điều kiện t X bj + k ∗ (n − t) > p. j=1 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.4) 16 Vì thế, nếu k 0 là một cận dưới của k ∗ , nghĩa là k 0 6 k ∗ , thì k 0 cũng phải thỏa mãn bất đẳng thức có dạng (2.4) với t thay bởi s, trong đó s là chỉ số thỏa mãn bs < k 0 6 bs+1 . Bổ đề được chứng minh.  Chú ý. Ví dụ sau đây cho thấy cận dưới k 0 tính theo (2.3) tốt hơn cận dưới k trong bổ đề 2.2. Xét bài toán (P) với các số liệu: m = 4, n = 6, p1 = 5, p2 = 4, p3 = 3, p4 = 3. Bảng 2.1 4 P Rõ ràng ai > pi , (i = 1, 2, 3, 4) , p = pi = 15. i=1   Theo bổ đề 1.2, k = 15 6 = 3, k = 4. 2.2 Cơ sở phương pháp giải Xét bài toán (P) ở chương 1: (P ) f (x) = max 16j 6n m X m X xij → min, i=1 xij = pi , i = 1, 2, ..., m, i=1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên (2.5) http://www.lrc-tnu.edu.vn (2.6)