ĐẠ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 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 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 MỘT SỐ KIẾN THỨC CHUẨN BỊ 1.1 Tập lồi, hàm lồi số tính chất 1.1.1 Tập hợp lồi 1.1.2 Hàm lồi 1.2 Thuật toán đa thức 1.3 Bài toán quy hoạch nguyên phi tuyến 10 PHƯƠNG PHÁP TRỰC TIẾP GIẢI BÀI TỐN (P) 13 2.1 Tính chất nghiệm 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 toán 21 2.3.1 2.3.2 Thuật toán A 16 21 Đánh giá độ phức tạp thuật toán 22 MỘT SỐ HƯỚNG MỞ RỘNG BÀI TOÁN (P) 28 3.1 Giảm kích thước tố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 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 toán (P) 35 Thay đổi hàm mục tiêu 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 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 Tối ưu tổ hợp (Combinatorial Optimization) hay gọi tối ưu rời rạc phận quan trọng tối ưu hoá Nó bao gồm nhiều tốn tối ưu với biến số nhận giá trị rời rạc (không liên tục) nhiều phương pháp giải khác cho lớp toán tổng quát riêng lẻ Các toán tối ưu tổ hợp phong phú, đa dạng có nhiều ứng đụng rộng rãi thực tiễn Một số mơ hình tối ưu tổ hợp thuộc loại tốn "dễ giải" (có thuật tốn đa thức để giải), phần lớn tốn "khó giải" (chưa có thuật tốn đa thức để giải) Nhiều vấn đề lý thuyết thực tiễn diễn đạt dạng toán tối ưu rời rạc Những tốn thường có cấu trúc riêng Nếu biết khai thác cấu trúc riêng tìm cách giải hiệu qủa Luận văn đề cập tới lớp toán tối ưu rời rạc, cụ thể toán qui hoạch nguyên phi tuyến (biến số nhận giá trị nguyên, hàm mục tiêu phi tuyến), giải thuật toán đa thức nhờ khai thác đặc điểm cấu trúc toán Bài toán xét luận văn có cấu trúc đặc biệt có nội dung thực tiễn thiết thực Có thể xem mơ hình tốn học cho số tốn thường gặp thực tế (mơ hình xếp lịch học tập trường học) hồn tồn áp dụng thực tiễn Việc phân tích lớp tốn giúp ích cho việc sâu tìm hiểu sau tốn tối ưu rời rạc nói chung ứng dụng chúng nói riêng Nội dung luận văn chia thành ba chương Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chương với tiêu đề "Một số kiến thức chuẩn bị" trình bày kiến thức cần thiết tập lồi hàm lồi làm sở lý thuyết cho việc phân tích cấu trúc xây dựng thuật toán chương sau Tiếp theo, chương 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 qt mơ hình ý nghĩa thực tế lớp toán qui hoạch nguyên phi tuyến xét luận văn Chương với tiêu đề "Phương pháp trực tiếp giải tốn (P)" phân tích cấu trúc đặc biệt nêu tính chất nghiệm đáng ý toán qui hoạch nguyên phi tuyến xét luận văn, tính chất giúp ích cho việc xây dựng thuật toán giải Mục chương trình bày thuật tốn thời gian đa thức giải toán, cách sử dụng kỹ thuật điều chỉnh dần phương án kỹ thuật gán số cho hàng cột, tương tự phương pháp giải tốn vận tải thơng thường qui hoạch tuyến tính Thuật tốn minh hoạ qua ví dụ số đơn giản trực quan Chương với tiêu đề "Một số hướng mở rộng toán" xét vấn đề xử lý sơ (tiền xử lý) kiện ban đầu toán nhằm giảm bớt kích thước tốn cần giải (nếu có thể) Sau đó, xét mở rộng tố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ụ ) 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 toán với hàm mục tiêu lõm) Do thời gian kiến thức hạn chế nên chắn luận văn có thiếu sót định, kính mong q thầy bạn đóng góp để tác giả tiếp tục hoàn thiện luận văn 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 đỡ suốt trình làm luận văn Tác giả xin trân trọng cảm ơn tập thể thầy giáo trường Đại học Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Khoa học – Đại học Thái Nguyên, Viện Toá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 giúp đỡ tác giả trình 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ổ Toán – Tin trường THPT số huyện Bát Xát – Lào Cai 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 năm 2012 Người thực Nguyễn Duy Long 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 MỘT SỐ KIẾN THỨC CHUẨN BỊ Chương trình bày số khái niệm kiến thức giải tích lồi, cần thiết cho việc phân tích lý thuyết xây dựng thuật toán chương sau Tiếp trình bày khái niệm thuật tốn đa thức cuối giới thiệu toán qui hoạch nguyên phi tuyến xét luận văn Nội dung chương tham khảo từ tài liệu [2], [3] [6] 1.1 1.1.1 Tập lồi, hàm lồi số tính chất Tập hợp lồi Khái niệm tập hợp lồi khái niệm giải tích lồi quy hoạch lồi Nhiều tính chất quan trọng thú vị tốn quy hoạch có miền ràng buộc tập hợp lồi Định nghĩa 1.1 Một tập X không gian Euclide Rn gọi tập lồi ∀x1 , x2 ∈ X ∀λ ∈ [0; 1] ta có λx1 + (1 − λ2 )x ∈ X Như X tập lồi chứa trọn đoạn thẳng nối hai điểm Ví dụ 1.1: • Các tập afin nói chung tập lồi • Các nửa khơng gian đóng: {x :< a, x > α}, {x :< a, x > Số hóa Trung tâm Học liệu – Đại học Thái Ngun http://www.lrc-tnu.edu.vn α} • Các nửa khơng gian mở: {x :< a, x >< α}, {x :< a, x >> α} • Siêu phẳng H = {x :< a, x >= b} Rn Bao lồi tập A tập lồi nhỏ chứa A, ký hiệu coA Đây giao tất tập lồi chứa A Nếu X tập lồi chứa bao lồi tập Cho A, B hai tập Rn , tổ hợp lồi A B tập hợp tất điểm thuộc Rn có dạng: x = λa+(1−λ)b, a ∈ A, b ∈ B, λ Định lý 1.1 Tập lồi đóng với phép giao, phép cộng, phép nhân với số phép lấy tổ hợp tuyến tính, tức A B hai tập lồi Rn tập hợp sau lồi: A ∩ B := {x : x ∈ A, x ∈ B} λA + βB := {x = λa + βb : a ∈ A, b ∈ B, λ, β 1} Hệ Miền chứa nghiệm hệ bất phương trình tuyến tính dạng:    a11 x1 + a12 x2 + + a1n xn b1 a21 x1 + a22 x2 + + a2n xn b2   am1 x1 + am2 x2 + + amn xn bm tập lồi Người ta cịn gọi tập lồi đa diện cịn gọi khúc lồi Một khúc lồi giới nội gọi đ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ó đỉnh biểu diễn tập hợp tât điểm có dạng: λi di + x= i∈I µj g j , i∈I λi = 1, λi , µj với i, j i∈I di với i ∈ I đỉnh X, với j ∈ J phương cạnh vô hạn X Chú ý X giới nội khơng có cạnh vơ hạn, biểu diễn cịn lại tổng thứ Trong trường hợp này, điểm X biểu diễn qua tổ hợp lồi đỉnh X Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1.1.2 Hàm lồi Định nghĩa 1.2 Hàm số f (x) xác định tập lồi X ⊂ Rn gọi hàm lồi X, với x, y ∈ X, f (λx + (1 − λ)y) λ ta có: λf (x) + (1 − λ)f (y) Hàm f (x) gọi hàm lồi chặt X với ∀x1 , x2 ∈ X, x1 = x2 , < λ < ta có f (1 − λ) x1 + λx2 < (1 − λ) f x1 + λf x2 Hiển nhiên hàm lồi chặt hàm lồi, điều ngược lại chưa Hàm f (x) gọi hàm tựa lồi tập lồi X f (λx + (1 − λ) y) max {f (x) , f (y)} ∀x, y ∈ X, λ Hàm f (x) gọi lõm (tựa lõm) tập lồi X hàm −f (x) lồi (tựa lồi) X Như thường lệ, hàm λf, f + g, max (f, g) định nghĩa 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 đóng phép tổ hợp tuyến tính khơng âm phép lấy max Cụ thể ta có định lý sau: Định lý 1.3 Cho f hàm lồi tập lồi X g hàm lồi tập lồi Y Lúc hàm sau lồi X ∩ Y : λf + βg ∀λ, β 0, max (f, g) Định nghĩa 1.3 Cho X ⊂ Rn khác rỗng hàm f : X → R (không thiết lồi) Một điểm x∗ ∈ X gọi cực tiểu địa phương f X, tồn lân cận mở U x∗ cho f (x∗ ) Số hóa Trung tâm Học liệu – Đại học Thái Nguyên f (x) với http://www.lrc-tnu.edu.vn 31 toán A, có điểm khác số tkj bước tính sau: m tkj ≡ k txj xkij + qj , j = 1, 2, , n = i=1 Bây giờ, giả sử chuyên đề xét có số chuyên đề bắt buộc sinh viên phải học Ký hiệu J ⊂ {1, 2, , n} tập hợp chuyên đề Ta phân biệt hai trường hợp: Mọi sinh viên bắt buộc phải học chuyên đề j ∈ J Khi đó, ta bố trí sinh viên học chuyên đề bắt buộc (xij = 1, i = 1, 2, , m; j ∈ J) Tiếp đó, tính lại số chun đề mà sinh viên phải học   pi = pi − xij , i = 1, 2, , m j∈J Sau loại bỏ chuyên đề j ∈ J , ta đưa toán dạng (P) Chỉ có sinh viên i ∈ Ij ⊂ {1, 2, , m} bắt buộc học chuyên đề j ∈ J Khi đó, ta bố trí sinh viên học chuyên đề bắt buộc họ (xij = 1, i ∈ Ij ; j ∈ J) Tiếp tính số sinh viên phân học chuyên đề j ∈ J số chuyên đề mà sinh viên phải học: qj = xij 0, j ∈ J, pi = pi − i∈Ij |{i} ∩ Ij |, ∀i = 1, 2, , m j∈J Sau đó, thay ma trận A = aij mxn bới ma trận A = aij mxn aij = ứng với ô (i, j) , i ∈ Ij , j ∈ J; aij = aij ứng với cịn lại Ta đưa tốn dạng (Q) xét Ví dụ 3.1 Giải toán (P) với số liệu: m = 5, n = 6, p1 = p2 = p3 = 2, p4 = p5 = Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 32 Và ma trận ưa thích có dạng: Bảng 3.1 Trong ví dụ ta có: a1 = 3, a2 = 4, a3 = 5, a4 = a5 = 4; b1 = 5, b2 = b3 = 4, b4 = 3, b5 = b6 = 2; p = 14, k = 14 =3 Theo (2.18) ta có I = {4, 5} , J = {4, 5, 6} Vì ta đặt: xij = aij với i = 4, 5; j = 1, 2, , với i = 1, 2, 3; j = 4, 5, (các số tô đậm bảng 3.1) Do pi = pi − aij = 0, i = 2, nên I = I ∪{2, 3} = {2, 3, 4, 5} j∈J Lại b3 = b3 − ai3 = a13 = nên J = J ∪ {3} = {3, 4, 5, 6} i∈I Cuối cùng, toán (P) thu hẹp thành toán (Q) với: m = 1, n = 2, p1 = p1 − a1j = − = 1, a1 = + = 2, b1 = b2 = 1; j∈J q1 = q2 = Nhìn bảng sau, rõ ràng (Q) có lời giải (1,0) (0,1) Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 33 Bảng 3.2 Kết ta phương án xếp lịch học tối ưu cho toán (P) sau: Bảng 3.3 Chun đề đơng có sinh viên 3.2 Thay đổi ràng buộc 3.2.1 Thêm, bớt sinh viên Thêm sinh viên: bảng m hàng n cột tương ứng với toán cũ (bài toán (P)), ta bổ sung vào hàng thứ m+1 ứng với sinh viên Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 34 thêm vào Cũng trước đây, để tốn có lời giải ta phải có am+1 pm+1 Sau đó, từ phương án tối ưu x∗ toán cũ, ta phân sinh viên ∗ ∗ học chuyên đề j có am+1j = txj < tx (nghĩa cột j cột đầy ứng với x∗ toán cũ) - Nếu phân đủ pm+1 chuyên đề phương án phương án tối ưu cần tìm - Nếu trái lại, ta buộc phải phân sinh viên học chuyên đề ưa thích ứng với cột đầy thu phương án toán Xuất phát từ phương án này, ta áp dụng thuật toán A (bước bước 3) để kiểm tra điều chỉnh cần Có thể thấy rằng, thêm sinh viên, giá trị tối ưu hàm mục tiêu cũ tăng thêm Trường hợp thêm nhiều sinh viên lúc, ta thêm dần sinh viên thêm lần nhiều sinh viên theo cách làm Giá trị tối ưu tăng nhiều số sinh viên thêm vào Bớt nhiều sinh viên: từ bảng m hàng n cột ứng với phương án tối ưu toán cũ, ta bỏ hàng ứng với sinh viên bớt đi, phương án thu phương án toán Xuất phát từ phương án này, ta lại áp dụng thuật toán A (bước bước 3) để kiểm tra điều chỉnh cần Cũng trên, thấy lần bớt sinh viên, giá trị tối ưu hàm mục tiêu cũ giảm 1, bớt nhiều sinh viên giá tối ưu giảm nhiều số sinh viên bớt 3.2.2 Thêm, bớt chuyên đề Thêm nhiều chuyên đề: Trong bảng m hàng n cột tương ứng với toán cũ, ta thêm vào cột thứ n + 1, n + 2, ứng với chuyên đề thêm vào Trong trường hợp này, phương án tối Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 35 ưu tốn cũ cịn phương án toán mới, áp dụng thuật toán A (bước bước 3) để kiểm tra điều chỉnh cần Bớt chuyên đề j0 : Trước hết, kiểm tra điều kiện pi , ∀i (3.6) toán Nếu điều kiện (3.6) thõa mãn tốn có lời giải Khi i, phương án tối ưu tốn cũ có xij0 = (3.1) nên ∃j1 để aij1 = ta đặt xij1 = Kết ta thu phương án toán mới, áp dụng thuật toán A (bước bước 3) để kiểm tra điều chỉnh cần Trường hợp bớt nhiều chuyên đề lúc, ta bớt dần chuyên đề bớt lần nhiều chuyên đề theo cách làm 3.2.3 Thêm điều kiện phụ vào tốn (P) Có thể thêm vào tốn (P) điều kiện sau: số sinh viên học chuyên đề phải nằm khoảng cho trước: [qmin , qmax ] với qmin qmax m Khi đó, ta có mơ hình toán sau: (P ”) max yj → min, (3.7) j n n xij = pi , i = 1, 2, , m, (3.8) xij = yj , j = 1, 2, , n, (3.9) j=1 m i=1 xij aij , qmin yj qmax , yj nguyên ∀i, j (3.10) với aij ∈ {0, 1} , qmin , qmax , pi ∈ {1, 2, , n} số nguyên cho trước Điều kiện cần để (P”) có phương án là: n m yj = j=1 pi = p n.qmin p n.qmax i=1 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 36 hay n yj = p j=1 p p , qmax =k (3.11) n n [x] phần nguyên số x ]x[ số nguyên nhỏ lớn qmin hay x Hơn nữa, để (P”) có phương án ta cịn phải có: qmin bj (3.12) j n • Xử lý qmax : Giải toán (P) theo thuật toán A, giả sử giá trị tối ưu thu k ∗ : - Nếu k ∗ qmax ta chuyển sang xử lý qmin - Nếu k ∗ > qmax tốn (P”) khơng có phương án Thật vậy, (P”) qmax < k ∗ , ∀j {xij } phương có phương án {xij , yj } với yj án (P) với hàm mục tiêu max yj < k ∗ Vô lý! j n •Xử lý qmin : Giả sử sau giải toán (P) ta thu phương án tối ưu x∗ = x∗ij mxn ứng với giá trị tối ưu k ∗ ∗ qmax Tính tổng tjx , ∀j ∗ trước (mục 2.2) đặt yj∗ = txj , ∀j Ta quy ước gọi cột j cao, thấp hay vừa tùy theo yj∗ > qmin , yj∗ < qmin hay yj∗ = qmin Lập luận tương tự mục 2.2 chứng minh rằng: - Nếu khơng có cột thấp (mọi yj∗ qmin ) x∗ij , y ∗ phương án tối ưu toán (P”) - Trái lại, ta tiến hành gán số cho hàng cột tương tự trước (mục 2.2) thay khái niệm đầy, gần đầy vơi thành khái niệm cao, vừa thấp Nếu có dây chuyền ô xanh trắng xen kẽ nối cột cao với cột thấp, ta tiến hành điều chỉnh “phương án” dây chuyền này, không tồn dây chuyền tốn (P”) khơng có phương án Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 37 Cũng xét tới điều kiện phụ tổng quát hơn, chuyên đề có hạn chế riêng số người học: uj yj vj , j = 1, 2, , n với uj vj số nguyên cho trước Bài toán lúc phức tạp nhiều Có thể thấy điều kiện cần để tốn có lời giải là: bj , ∀j n m n vj j=1 j=1 j=1 vj yj = p uj Điều kiện tổng quát hóa điều kiện (3.11) (3.12) Nó có phải điều kiện đủ hay khơng cịn vấn đề phải xem xét 3.3 3.3.1 Thay đổi hàm mục tiêu toán (P) Bài toán với hàm mục tiêu mở rộng Bài toán (P) xét trước diễn đạt lại dạng: f = max yj → min, (3.13) xij = pi , i = 1, 2, , m, (3.14) xij = yj , j = 1, 2, , n, (3.15) j n n j=1 m i=1 xij ∈ {0, 1} xij aij , ∀i = 1, 2, , m; ∀j = 1, 2, , n, (3.16) với aij ∈ {0, 1} , pi ∈ {1, 2, , n} số ngun cho trước Ta xét tốn mở rộng (P) cách thay hàm mục tiêu (3.13) hàm mục tiêu có dạng tổng quát sau: g = max gj (yj ) → min, j n (3.17) gj (.) hàm tùy ý biến số Dưới rằng, thuật toán A nêu chương áp dụng để giải tốn mở rộng (3.14) – (3.17) với giả thiết: gj (y1 ) < gj (y2 ) với y1 , y2 nguyên thỏa mãn y1 < y2 m, ∀j = 1, 2, , n Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn (3.18) 38 Điều kiện (3.18) thỏa mãn chẳng hạn gj (.) hàm đơn điệu tăng đoạn [0, m] Do biến yj xác định theo (3.15) nhận giá trị 0, 1, 2, , m, nên hàm gj (yj ) lấy số hữu hạn giá trị sau: g1 (0) , g1 (1) , , g1 (m) , g2 (0) , g2 (1) , , g2 (m) , , gn (0) , gn (1) , , gn (m) (3.19) Giả sử dãy (3.19) có tất s giá trị khác biệt giá trị xếp theo thứ tự tăng dần có dạng: g1 < g2 < g3 < < gs (3.20) Như vậy, thấy giá trị tối ưu hàm mục tiêu (3.20) nhận s giá trị dãy (3.15) Để áp dụng thuật toán đa thức mục 1.3, chương việc tìmg ∗ ta tiến hành sau: Với j, k (1 j n, k s) ta đặt: djk = max {i : gj (i) gk , i = 0, 1, 2, , m} (3.21) Do có giả thiết (3.18) nên djk giá trị lớn đối số để cho giá trị hàm gj (djk ) không vượt giá trị gk cho trước Với k (1 k s) ta xây dựng mạng G (k) = (V, E) với tập đỉnh V = {s} ∪ {ui : i = 1, 2, , m} ∪ {wj : j = 1, 2, , n} ∪ {t} s điểm phát, t điểm thu với tập cung: E = {(s, ui ) : i = 1, 2, , m} ∪ {(ui , wj : i = 1, 2, , m, j = 1, 2, , n} ∪{(wj , t) : j = 1, 2, , n} Mỗi cung e ∈ E gắn với khả thông qua q(e) theo nguyên tắc sau: q(s, ui ) = pi , i = 1, 2, , m, Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 39 q(ui , wj ) = aij , i = 1, 2, , m; j = 1, 2, , n, q(wj , t) = k, j = 1, 2, , n Tuy nhiên, điều khác khả thông qua cung (wj , t) , j = 1, 2, , n cho sau: q (wj , t) = djk , j = 1, 2, , n (3.22) với djk xác định theo (3.2.1) Ta đến thuật toán sau giải toán (3.14) – (3.17) với giả thiết (3.18): Thuật tốn B: m Bước 1: Tính p = i=1 pi tính giá trị g1 , g2 , , gs theo (3.19), (3.20) Đặt k = 1, k = s Ký hiệu g (k) giá trị luồng cực đại mạng G (k) Bước 2: Nếu k − k 1, chuyển sang bước Trái lại, đặt: k=k+ k − k /2 Bước 3: Xây dựng mạng G (k) vừa mô tả tìm luồng cực đại G (k) Bước 4: Nếu q (k) < p ta đặt k = k + 1, q (k) = p ta đặt k = k Trở lại bước Bước 5: Tìm luồng cực đại mạng G (k) với k = k Nếu q (k) = p g ∗ = gk , cịn q (k) < p g ∗ = gk Dừng thuật tốn Có thể dễ dàng thấy rằng, sau số hữu hạn bước, thuật toán B cho ta phương án tối ưu toán (3.14) – (3.17) Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 40 3.3.2 Bài toán với hàm mục tiêu lõm Một hướng mở rộng khác tốn (P) xét hàm mục tiêu có dạng: n hj yj → min, h= j=1 hj (.) hàm lõm biến số đoạn [0, m] Giả thiết lõm phản ánh tính chất: chi phí tổ chức lớp học người học giảm số người học gia tăng Hàm mục tiêu nêu biểu thị tổng chi phí cho việc tổ chức tất chuyên đề có người học Chẳng hạn, hàm hj có dạng: hj (y) = y = 0, dj + cj y y > với cj , dj số dương cho trước ( dj biểu thị “chi phí cố định” cho việc tổ chức lớp học, chi phí không phụ thuộc số người theo học) Như vậy, ta xét tốn: Tìm cực tiểu hàm lõm n h (x) = hj j=1 với điều kiện m → xij (3.23) i=1 n xij = pi , i = 1, 2, , m, (3.24) aij , ∀i = 1, 2, , m; j = 1, 2, , n (3.25) j=1 xij ∈ {0, 1} , xij aij ∈ {0, 1} , pi ∈ {1, 2, , m} số cho trước m Có thể chứng minh hj (yj ) = hj xij hàm lõm theo i=1 biến xij (i = 1, 2, , m) Vì thế, tốn (3.23)-(3.25) xem tốn quy hoạch lõm với biến ngun 0, Bài tốn có dạng tương tự toán sản xuất - vận tải với cước phí lõm số tác giả xét tối ưu toàn cục Tuy nhiên, tốn xét phức tạp có ràng buộc cận xij Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 41 Ký hiệu D tập điểm x = {xij } thỏa mãn điều kiện (3.24), (3.25) xét tập ràng buộc nới lỏng:  n  M = x: xij = pi , ∀i, xij  1, xij aij , ∀i, j   (3.26)  j=1 Ta công nhận bổ đề sau: Bổ đề 3.1 D tập đỉnh đa diện M Giả sử x ∈ D, theo bổ đề x đỉnh M Với i = 1, 2, , m ta ký hiệu: Ji+ = j : xij = , Ji0 = {j : aij − xij = 1} ≡ {j : aij = 1, xij = 0} Dễ thấy Ji+ = pi Ji0 = − pi , ∀i = 1, 2, , m Khi đó, ta có bổ đề sau đây: Bổ đề 3.2 Với i0 ∈ {1, 2, , m} thỏa mãn Ji00 = ∅, ta chọn s ∈ Ji+0 , r ∈ Ji00 Khi y = {yij } với yij = xij , ∀i, j trừ yi0 s = yi0 r = đỉnh M kề x pi (ai − pi ) Bổ đề 3.3 Số đỉnh M kề x m (x) = >pi Như biết, cực tiểu hàm lõm đa diện lồi đạt đỉnh đa diện Vì thế, thay cho tốn (3.23) – (3.25) ta xét tốn nới lỏng: {h (x) : x ∈ M } (3.27) Hiện nay, có nhiều phương pháp khác để giải toán (3.27) Tuy nhiên cần nghiên cứu đề xuất phương pháp có hiệu để tìm cực tiểu toàn cục này, nhờ triệt để khai thác cấu trúc đặc thù tập M Sau đây, chúng tơi đề xuất phương pháp tìm cực tiểu địa phương tốn (3.27) theo nghĩa tìm đỉnh M giá trị hàm mục tiêu (3.25) không lớn giá trị hàm mục tiêu đỉnh M kề với đỉnh Một đỉnh thuộc D (bổ đề 3.1) lời giải “tốt” toán (3.23) – (3.25) Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 42 Thuật toán C: Bước 1: Xuất phát từ điểm x1 ∈ D Một điểm tìm chẳng hạn bước thuật toán A Đặt k = k Bước 2: Dùng bổ đề 3.2 tìm đỉnh M kề xk : y , y , , y m(x ) Bước 3: Tính giá trị hàm mục tiêu h y i γk = h y i : i = 1, 2, , m xk 3a Nếu h xk γk dừng: xk điểm cực tiểu địa phương cần tìm 3b Nếu trái lại, ta chọn y k = arg h y i : i = 1, 2, , m xk đặt xk+1 = y k Tăng k lên trở lại bước Do số đỉnh M hữu hạn nên thuật tốn nêu phải dừng tình 3a sau số hữu hạn bước lặp 3.3.3 Bài toán vận tải với điều kiện phụ Xét mơ hình tốn vận tải sau: m n cij xij → min, (3.28) i=1 j=1 n xij , i = 1, 2, , m, (3.29) xij = bj , j = 1, 2, , n, (3.30) j=1 m i=1 xij = bj , ∀i,j (3.31) , bj cij số cho trước Nếu điều kiện (3.31) có dạng xij 0, ∀i, j ta có tốn vận tải thơng thường Nhiều vấn đề thực tiễn diễn đạt dạng tốn (3.28) – (3.31) Sau nêu hai ví dụ a Bài toán phân phối điện Giả sử có m nguồn cung cấp điện năng, khả cung cấp nguồn thứ Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 43 i (i=1,2, ,m) Số điện dùng để cung cấp cho n hộ tiêu thụ, hộ thứ j có nhu cầu tiêu thụ điện bj (j=1,2, ,n) Ký hiệu cij chi phí cung cấp điện từ nguồn cung cấp thứ i tới hộ tiêu thụ thứ j Vấn đề đặt là: tìm phương án phân phối điện từ nguồn cung cấp tới hộ tiêu thụ cho đáp ứng nhu cầu hộ tiêu thụ mà không vượt khả nguồn cung cấp đạt cực tiểu tổng chi phí cung cấp điện từ nguồn cung cấp đến hộ tiêu thụ điện, với điều kiện hộ nhận điện từ nguồn cung cấp b Bài toán xếp hàng lên tầu Bài tốn sau quy việc tìm phương án chấp nhận toán vận tải với điều kiện phụ (3.28) – (3.31) nêu trên: Có n đồ vật, trọng lượng đồ vật j bj (j = 1, 2, , n) Có m contener chở hàng, contener i chở hàng (i = 1,2, ,m) Liệu xếp n đồ vật vào m contener cho không vượt q tải trọng contener khơng (dung tích xem không hạn chế)? Trường hợp riêng: ≡ a, ∀i có tên tốn Bin packing, tốn NP khó Một thuật tốn hữu hiệu cho tốn chưa biết rõ, việc tìm thuật tốn giải có hiệu cho tốn vận tải có điều kiện phụ nói vấn đề mở, đáng quan tâm nghiên cứu Tóm lại, chương xét vấn đề tiền xử lý kiện toán để giảm bớt (nếu có thể) kích thước tốn cần giải Sau xét mở rộng toán theo hai hướng: thay đổi điều kiện ràng buộc toán (thêm hay bớt sinh viên, thêm hay bớt chuyên đề, thêm điều kiện phụ) 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 toán với hàm mục tiêu lõm) Kỹ thuật tái tối ưu hoá sử dụng phải giải lại toán (sau thay đổi điều kiện ràng buộc) Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 44 KẾT LUẬN Luận văn đề cập tới lớp tốn tối ưu tổ hợp giải thời gian đa thức, nhờ triệt để khai thác cấu trúc đặc biết toán Bài tốn xét luận văn có nội dung thực tế thiết thực hồn tồn áp dụng thực tiễn Luận văn trình bày nội dung cụ thể sau: Một số kiến thức sở giải tích lồi thuật tốn thời gian đa thức, làm sở lý luận cho nghiên cứu xây dựng thuật toán giải toán Phân tích cấu trúc đặc thù tốn xét nêu tính chất đáng ý nghiệm toán (điều kiện cần đủ để tốn có nghiệm, đánh giá cận cận cho giá trị tối ưu toán) Trình bày thuật tốn đa thức giải tốn, dựa kỹ thuật cải tiến dần phương án kỹ thuật đánh số hàng cột Xây dựng ví dụ số minh hoạ cho thuật tốn trình bày Xét vấn đề xử lý sơ kiện tốn nhằm giảm bớt kích thước tốn cần giải, Xét số mở rộng mơ hình tốn theo hai hướng: thay đổi điều kiện ràng buộc thay đổi hàm mục tiêu tốn Có thể xem luận văn bước tìm hiểu tối ưu tổ hợp Việc phân tích lớp tốn xét giúp hiểu rõ thêm cách tiếp cận tối ưu tổ hợp Tác giả luận văn hy vọng có địp tìm hiểu sâu nội dung ý nghĩa thực tế toán tối ưu tổ hợp khác tương lai Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 45 Tài liệu tham khảo Tài liệu tiếng Việt [1] N Đ Nghĩa, V V T Dũng, Thuật toán đa thức giải lớp toán tối ưu rời rạc, Tạp chí Tin học Điều khiển học, Số 1/1999, - 13 [2] Trần Vũ Thiệu, Nguyễn Thị Thu Thủy (2011), Giáo trình tối ưu phi tuyến tính, NXB Đại học Quốc Gia Hà Nội [3] Hoàng Tụy (2003), Lý thuyết tối ưu (Bài giảng lớp cao học), Viện toán học Hà nội Tài liệu tiếng Anh [4] V.T.T Dung and T.V Thieu (1999), A Finite Algorithm for a Class of Nonlinear Optimization Problems, Journal of Sciences, Natural Sciences - VNU T XV, No (1999), - 15 [5] V Thieu and V V T Dung, A Polynomial Algorithm for a Class of Minimax Integer Monotonic Problems , Advancesd in Natural Science, 1999 [6] P Tseng (2008), Discrete Optimization of Math, Univ of Washington, 1999 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 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... Thuật toán đa thức 1.3 Bài toán quy hoạch nguyên phi tuyến 10 PHƯƠNG PHÁP TRỰC TIẾP GIẢI BÀI TỐN (P) 13 2.1 Tính chất nghiệm toán( P) 13 2.2 Cơ sở phương. .. riêng tìm cách giải hiệu qủa Luận văn đề cập tới lớp toán tối ưu rời rạc, cụ thể toán qui hoạch nguyên phi tuyến (biến số nhận giá trị nguyên, hàm mục tiêu phi tuyến) , giải thuật toán đa thức nhờ