BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP HỒ CHÍ MINH Tống Thị Kim Oanh MỘT VÀI PHƯƠNG PHÁP SỐ GIẢI BÀI TOÁN TỐI ƯU LUẬN VĂN THẠC SĨ TỐN HỌC Thành phố Hồ Chí Minh – 2015 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP HỒ CHÍ MINH Tống Thị Kim Oanh MỘT VÀI PHƯƠNG PHÁP SỐ GIẢI BÀI TOÁN TỐI ƯU Chun ngành: Tốn Giải tích Mã số: 60 46 01 02 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS TRỊNH CÔNG DIỆU Thành phố Hồ Chí Minh – 2015 LỜI CAM ĐOAN Tơi xin cam đoan luận văn tơi thực hướng dẫn TS Trịnh Công Diệu Mọi tham khảo luận văn ghi rõ tên tác giả, tên cơng trình, thời gian, địa điểm cơng bố Mọi chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá, tơi xin chịu hồn toàn trách nhiệm Người thực Tống Thị Kim Oanh LỜI CẢM ƠN Trước trình bày nội dung Luận văn, em xin bày tỏ lòng biết ơn sâu sắc tới TS Trịnh Công Diệu, người tận tình hướng dẫn giúp đỡ em suốt trình nghiên cứu để em hồn chỉnh luận văn Em xin bày tỏ lòng biết ơn chân thành tới quý thầy, cô giáo Trường Đại học sư phạm TP Hồ Chí Minh giảng dạy giúp đỡ em hồn thành khóa học Mặc dù có nhiều cố gắng luận văn khó tránh khỏi thiếu sót Tác giả mong muốn nhận ý kiến đóng góp q thầy, bạn đọc để luận văn hoàn thiện MỤC LỤC Trang Trang phụ bìa Lời cam đoan Lời cảm ơn Mục lục Danh mục kí hiệu, chữ viết tắt MỞ ĐẦU CHƯƠNG KIẾN THỨC CHUẨN BỊ 1.1 Giới thiệu toán 1.2 Một số tính chất định tính tốn tối ưu phi tuyến .3 CHƯƠNG MỘT SỐ PHƯƠNG PHÁP SỐ GIẢI BÀI TỐN KHƠNG RÀNG BUỘC 13 2.1 Phương pháp Gradient 13 2.2 Phương pháp Newton với bước điều chỉnh 19 2.3 Phương pháp hướng đối ngẫu .23 2.4 Phương pháp tìm kiếm trực tiếp 29 CHƯƠNG MỘT SỐ PHƯƠNG PHÁP SỐ GIẢI BÀI TỐN CĨ RÀNG BUỘC 39 3.1 Bài toán quy hoạch toàn phương 39 3.2 Phương pháp Gradient có điều kiện 42 3.3 Phương pháp tuyến tính hóa 45 KẾT LUẬN 57 TÀI LIỆU THAM KHẢO 58 DANH MỤC CÁC KÍ HIỆU, CÁC CHỮ VIẾT TẮT  tập số thực n không gian Euclide n chiều xi biến thành phần thứ i x xk nghiệm xấp xỉ tối ưu thứ k x, y tích vơ hướng x y x chuẩn Euclide x x giá trị tuyệt đối x x∈D x thuộc tập D x∈D x không thuộc tập D D ⊂V tập D chứa tập V D ∩V giao tập D tập V int D phần D ∀x với x ∃x tồn x ∇f ( x ) vectơ gradient hàm f điểm x H ( x) ma trận Hesse hàm f điểm x AT ma trận chuyển vị ma trận A A−1 ma trận nghịch đảo ma trận A In ma trận đơn vị cấp n MỞ ĐẦU Lí chọn đề tài Trong thực tế, việc tìm giải pháp tối ưu cho vấn đề chiếm vai trị quan trọng, gần vấn đề gặp khắp nơi Từ năm 70 kỉ XX hình thành nhiều hướng nghiên cứu khác tối ưu không lồi, tối ưu phi tuyến, tối ưu rời rạc, tối ưu tổ hợp tối đa mục tiêu Khi đó, B.N.Pschenichny Yu.M.Danilin có nghiên cứu phương pháp số lí thuyết tối ưu phi tuyến trình bày Numerical methods in extremal problems lần xuất vào năm 1978 Có nhiều phương pháp giải lớp toán tối ưu phi tuyến chưa có phương pháp tỏ hữu hiệu cho toán Bởi lý thuyết thuật toán tối ưu phi tuyến khoa học phát triển ngày phong phú đa dạng Đối tượng nghiên cứu Xét toán quy hoạch phi tuyến mục tiêu Với tốn trình bày thuật tốn, sở lí thuyết thuật tốn cho ví dụ minh họa Áp dụng thuật tốn vào giải vài ví dụ thực tế Mục đích nghiên cứu Cung cấp phương pháp toán học để giải số vấn đề tối ưu hóa thực tế Phương pháp nghiên cứu Đọc tài liệu để tìm hiểu kết có tương ứng với tốn phi tuyến mục tiêu nêu vài ví dụ minh họa cho việc vận dụng vấn đề lí thuyết vào thực tế Chương KIẾN THỨC CHUẨN BỊ 1.1 Giới thiệu toán 1.1.1 Ý nghĩa thực tế vấn đề nghiên cứu Trong sống, vấn đề tối ưu hóa xuất khắp nơi, hầu hết lĩnh vực khoa học – công nghệ kinh tế - xã hội Ta có hai ví dụ cụ thể sau: Ví dụ (Bài tốn lợi nhuận sản xuất) Một công ty sản xuất hai loại mặt hàng Gọi Qi số lượng sản phẩm mặt hàng thứ i, i = 1, Pi đơn giá mặt hàng thứ i, i = 1, Hàm lợi nhuận công ty ∏= R − C= PQ 1 + P2Q2 − C Biết = P1 400, = P2 600 hàm tổng chi phí C =Q12 + 2Q22 + 2Q1 + 4Q2 + 300 Tìm Q1 Q2 để ∏ đạt max? Ví dụ (Bài tốn hiệu suất xử lí nước thải) Một cơng ty thực phẩm chọn phương pháp xử lí nước thải cơng nghệ Aeroten Xét trường hợp hiệu suất xử lí nước thải phụ thuộc vào hai yếu tố nồng độ bùn hoạt tính thời gian lưu nước bể Gọi x1 nồng độ bùn hoạt tính (kg/m3), x2 thời gian lưu nước bể (giờ), hiệu suất xử lí tính hàm mục tiêu: F = − x12 − x22 + x1 + 10 x2 + 44 Tìm nồng độ bùn hoạt tính thời gian lưu nước thích hợp để hiệu suất đạt tối ưu, biết nồng độ bùn từ 1.6 – kg / m3 thời gian lưu nước từ 2.5 – Do việc tìm giải pháp tối ưu cho vấn đề quan trọng Hơn nữa, vấn đề cần có phương pháp giải thích hợp Trong đó, bao gồm phương pháp như: xét tất trường hợp, sử dụng kinh nghiệm, hay sử dụng phương pháp khoa học Như việc nghiên cứu lí thuyết tối ưu vơ cần thiết 1.1.2 Đặc điểm kết có Từ tốn thực tế, người ta mơ hình hóa tốn học chúng thành dạng toán tối ưu biết giải phương pháp tối ưu thích hợp Phương pháp đơn hình tốn quy hoạch tuyến tính cho ta thuật tốn đơn giản Tuy nhiên, gặp trường hợp ràng buộc nhiều tính tốn có phần khó khăn Đối với trường hợp phi tuyến có nhiều kết định tính, qua xem xét tính chất tập nghiệm tối ưu Tuy nhiên, phương pháp gặp khó khăn dùng vào thực tế Do ta cần phương pháp thích hợp cho phép xác định giá trị số nghiệm, phương pháp số 1.1.3 Mơ hình tốn phi tuyến Cho hàm số f : D ⊂  n →  Bài toán tối ưu tổng quát có dạng f ( x ) → ( max ) (1.1) g i ( x )( ≤, =, ≥ ) bi , i = 1, , m (1.2) với điều kiện Trong đó: • Hàm f ( x ) gọi hàm mục tiêu • Các hàm gi ( x ) , i = 1, , m gọi hàm ràng buộc Nếu hàm mục tiêu f ( x ) hàm ràng buộc gi ( x ) , i = 1, , m hàm tuyến tính ta có tốn tối ưu tuyến tính Mơ hình tối ưu tốn học khơng phải lúc mơ hình tuyến tính ta gọi tốn khơng phải tuyến tính tốn tối ưu phi tuyến { Tập D = x ∈  n | gi ( x )( ≤, =, ≥ ) bi , i = 1, , m} gọi miền chấp nhận hay miền ràng buộc Nếu D =  n ta gọi tốn tối ưu khơng ràng buộc, ngươc lại tập D tập thực  n ta gọi tốn tối ưu có ràng buộc 1.2 Một số tính chất định tính toán tối ưu phi tuyến 1.2.1 Nhắc lại 1.2.1.1 Hàm nhiều biến khả vi cấp cấp hai Định nghĩa 1.1 (Đạo hàm riêng) Cho hàm số f xác định tập mở D ⊂  n x = ( x1 , , xn ) điểm thuộc D Khi với số h ∈  đủ nhỏ, điểm T ( x1 , , xi −1 , xi + h, xi +1 , , xn ) T nằm D Giới hạn f ( x1 , , xi −1 , xi + h, xi +1 , , xn ) − f ( x1 , , xi −1 , xi , xi +1 , , xn ) lim h →0 h T tồn tại, gọi đạo hàm riêng f theo biến xi , điểm x , kí hiệu ∂f ( x ) hay f x′ ( x ) ∂xi i Đối với hàm biến f :  →  , kí hiệu ∂ thay d Giả sử đạo hàm riêng x ∂f ( x ) tồn với x ∈ D Khi đó, phép tương ứng ∂xi ∂f ( x ) ∂f xác định hàm : D →  Nếu x, đạo hàm riêng theo biến x j ∂xi ∂xi hàm ∂f tồn ta gọi đạo hàm riêng cấp hai theo biến xi x j ∂xi hàm f x kí hiệu ∂2 f ( x) f x′′x ( x ) ∂xi ∂x j i j Một cách tương tự ta định nghĩa đạo hàm riêng cấp k ∂k f ( x) theo biến ∂xi1 ∂xik xi1 , , xik hàm f điểm x Định nghĩa 1.2 (Gradient ma trận Hesse) Cho hàm số f xác định tập mở D ⊂  n Giả sử x∗ , đạo hàm riêng hàm f theo biến tồn Khi đó, vectơ  ∂f ( x∗ ) ∂f ( x∗ )    , ,  ∂x1 ∂xn    T ( ) Được gọi gradient hàm f x∗ kí hiệu ∇f x∗ Nếu đạo hàm riêng cấp hai theo biến f x∗ tồn ma trận 44 Do m −1 ∑η k =1 k ≤ LC  f ( x1 ) − f ( x m )  ≤ LC  f ( x1 ) − f ∗  Như suy chuỗi ∞ ∑η k =1 hội tụ Điều xảy η k → k Mệnh đề chứng minh 3.2.2 Thuật toán Bước khởi tạo Chọn điểm x ∈ D làm điểm khởi đầu Đặt k := chuyển sang bước lặp Các bước lặp (bước lặp thứ k) Bước Tìm điểm cực tiểu z k hàm ∇f ( x k ) , z D tính pk = z k − x k , ηk = ∇f ( x k ) , p k Bước Tính x k += x k + α k p k α k = 2− q cho q số tự nhiên thỏa mãn bất đẳng thức f ( x k + 2− q p k ) ≤ f ( x k ) + 2− q Thay ηk k =: k + chuyển bước Bước kết thúc Nếu η k ≈ 3.2.3 Ví dụ Tìm f ( x ) = x12 + x22 − x1 − 4= x2 , x ( x1 , x2 ) ∈  với ràng buộc  x1 + x2 ≤  x x ≥ ,  Giải  x1 −  Chọn điểm khởi đầu Tính ∇f ( x ) = = x0    x2 −  T ( 0, ) T ∈D Bước lặp ∇f ( x ) =( −8, −4 ) Đặt ϕ ( z ) = ∇f ( x ) , z = −8 z1 − z2 , z = ( z1 , z2 ) T 45 Giải tốn quy hoạch tuyến tính ϕ ( z ) → min, z ∈ D ta nghiệm tối ưu z − x0 = z = ( 2,0 ) Tính p = ( 2,0 ) , T T η0 =∇f ( x ) , p = −16 Tính x1 = x0 + α p0 = ( 2α , ) α chọn theo quy tắc Armijo T T Ta chọn q = hay α = , suy x1 = ( 2,0 ) x1 ∈ D Bước lặp Tính ∇f ( x1 ) =( −4, −4 ) Đặt ϕ ( z ) = ∇f ( x1 ) , z = −4z1 − z2 , T z= ( z1 , z2 ) Giải tốn quy hoạch tuyến tính ϕ ( z ) → min, z ∈ D ta nghiệm tối ưu 1 z1 = ( 2, ) Tính p =z − x =( 0,0 ) , T T η1 =∇f ( x1 ) , p1 =0 Dừng thuật toán Vậy x1 = ( 2,0 ) nghiệm tối ưu toán f ( x1 ) = −12 T 3.3 Phương pháp tuyến tính hóa Xét toán quy hoạch lồi tổng quát  f ( x ) →  n  x ∈ D = { x ∈  | g i ( x ) ≤ 0, i = 1, , m} (3.13) n gi hàm lồi khả vi  D tập lồi, compact Mục đích phương pháp biến đổi hàm mục tiêu hàm ràng buộc phi tuyến thành hàm tuyến tính áp dụng phương pháp giải tốn quy hoạch tuyến tính để giải 3.3 Thuật tốn tuyến tính hóa ràng buộc Xét tốn (3.13) với trường hợp hàm mục tiêu hàm tuyến tính, tức f ( x ) = c, x Khi ta áp dụng thuật tốn tuyến tính hóa ràng buộc (còn gọi phương pháp siêu phẳng cắt Kelley đề xuất năm 1960) để giải toán Thuật toán trình bày sau: Bước khởi tạo Chọn tùy ý p điểm x1 , x , , x p (thường chọn p= n + ) dựng điểm chọn siêu phẳng tiếp xúc với mặt cong y = g i ( x ) , tức lập hàm tuyến tính 46 j hi , = g i ( x j ) + ∇g i ( x j ) x − x = , j 1, ,= p; i 1, , m j ( x) Do hàm gi lồi nên n hi , = g i ( x j ) + ∇g i ( x j ) x − x j ≤ g i ( x j ) , ∀x ∈ = p; i 1, , m , j 1, ,= j ( x) (3.14) Đặt D1 ={ x ∈  n | hi , j ≤ 0, j =1, , p; i =1, , m} Với x ∈ D g i ( x ) ≤ với i , theo (3.12) hi , j ≤ nên D1 ⊇ D Các bước lặp (bước lặp k) Bước Tìm điểm x k + p ∈ Dk nghiệm tối ưu toán quy hoạch tuyến tính = c, x k + p { c, x | x ∈ Dk } Bước Nếu x k + p ∈ D x k + p nghiệm tối ưu toán (3.13) dừng thuật tốn, D ⊂ Dk { } = c, x k + p { c, x | x ∈ Dk } ≤ { c, x | x ∈ D} ≤ c, x k + p Bước Nếu x k+ p ∈ D x k + p vi phạm ràng buộc gi ( x ) ≤ Kí { } hiệu I k := i ∈ {1, 2, , m} | g i ( x k + p ) ≤ { } n k+ p Đặt D= ) , x − x k + p + gi ( x k + p ) ≤ 0, i ∈ I k k +1 : Dk  x ∈  | ∇g i ( x Thay k =: k + quay lại bước Nhận xét • Vì ∇g i ( x k + p ) , x k + p − x k + p + g i= ( x k + p ) gi ( x k + p ) > 0, ∀i ∈ I k x k + p ∈ Dk +1 Các siêu phẳng {x ∈  n nên ta có } | ∇g i ( x k + p ) , x − x k + p + g i ( x k + p ) =0 , i ∈ I k gọi siêu phẳng cắt chúng tách tập lồi Dk +1 với điểm x k + p ∈ Dk +1 • Ở bước k ta ln có ∇g i ( x k + p ) ≠ 0, ∀i ∈ I k , tồn i ∈ I k cho ∇g i ( x k + p ) = gi hàm lồi nên với i ta có g i ( x ) ≥ g i ( x k + p ) + ∇g i ( x k + p ) , x k + p − = xk + p gi ( x k + p ) , ∀x ∈  n Điều mâu thuẫn với giả thiết tập D ≠ ∅ 47 Mệnh đề 3.1 Giả sử tập phương án chấp nhận D (3.13) khác rỗng Khi Dk +1 đa diện chứa D không chứa x k + p Chứng minh [2, tr 57] Nếu x ∈ D g i ( x ) ≤ 0, i = 1, , m theo hệ 1.1 [2, tr 11] ta có: ∇g i ( x k + p ) , x − x k + p + g i ( x k + p ) ≤ g i ( x k + p ) ≤ 0, i ∈ I k Điều chứng tỏ x ∈ Dk +1 } { Từ g i ( x k + p ) > 0, i ∈ I k ta suy x k + p ∈ x | ∇g i ( x k + p ) , x − x k + p + g i ( x k + p ) ≤ 0, i ∈ I k Suy x k + p ∈ Dk +1 Định lí 3.3 Giả sử g1 , , g m hàm lồi, khả vi liên tục tập chấp nhận { } D cuả tốn (3.13) tập compact Khi đó, dãy x k sinh thuật tốn 3.3 có dãy hội tụ đến nghiệm cực tiểu tốn Chứng minh [2, tr 58-59] { } Ta có g1 , , g m hàm lồi nên lồi compact Mà D1 ⊃ D2 ⊃ ⊃ D nên dãy x k { } nằm D1 Do ln có dãy x k j hội tụ đến phần tử thuộc D1 { } { } k →∞ → x∗ Giả sử x k j dãy x k x j  k Đặt = gik ( x ) max { gi ( x ) |1 ≤ i ≤ m} ( ) Ta x∗ ∈ D tức gik x∗ ≤ Từ hệ 1.1 [2, tr 11] ta có với j′ > j Ta khẳng định ( ) ≤ ∇g ( x ) x gik x kj kj k j′ ik −x kj Thật vậy, x j ′ ∈ Dk j ′ ⊂ Dk j nên k ( ), x − x + g ( x ) ≤ ⇒ g ( x ) ≤ − ∇g ( x ) , x − x ∇gik x kj k j′ kj kj ik kj ik kj ik k j′ kj ( ), x ≤ ∇gik x kj k j′ −x kj ( ).x ≤ ∇gik x kj k j′ −x kj 48 ( ) Vì g i khả vi liên tục, x j → x∗ , ∇gik x k k kj bị chặn nên ta suy ( )≤0 = gik ( x∗ ) lim gik x j →∞ kj Hơn tập chấp nhận D nằm Dk với k ta có c, x kj ≤ c, x Với x chấp nhận j = 1, 2, Điều khẳng định rằng, với phương án chấp nhận x, c, x ∗ ≤ c, x Đó điều cần chứng minh 3.3.1 Phương pháp tuyến tính hóa giải tốn quy hoạch lồi tổng quát Xét toán quy hoạch lồi tổng quát (3.13) Ta đưa toán toán với hàm mục tiêu tuyến tính nhờ thêm biến xn +1 ràng buộc xn+1 ≥ f ( x ) , toán xn +1 → min, ( x, xn +1 ) ∈ D′ D′= {( x, x ) ∈  n +1 n +1 | g i ( x ) ≤ 0, i= 1, , m; g m +1 =: f ( x ) − xn +1 ≤ 0} (3.15) tương đương với toán (3.13) Chứng minh: [2, tr 54-55] ( ⇒ ) Giả sử (3.13) có nghiệm x∗ , ta có f ( x∗ ) ≤ f ( x ) , ∀x ∈ D = {x ∈  n | gi ( x ) ≤ 0, i = 1, , m} gi ( x∗ ) ≤ 0, ∀i =1, , m ( ) Đặt xn∗+1 = f x∗ ( ) x∗ , xn∗+1 nghiệm (3.15)  gi ( x∗ ) ≤ 0, ∀i =1, , m  ⇒ ( x∗ , xn∗+1 ) ∈ D′  ∗ ∗  f ( x ) − xn +1 = xn∗+1 = f ( x∗ ) ≤ f ( x ) ≤ xn +1 , ∀ ( x, xn +1 ) ∈ D=′ {( x, x ) ∈  n +1 n +1 i 1, , m; g m+1=: f ( x ) − xn+1 ≤ 0} | gi ( x ) ≤ 0,= 49 ( ⇐ ) Giả sử (3.13) có nghiệm ( x∗ , xn∗+1 ) , ta có ( x∗ , xn∗+1 ) ∈ D′ hay gi ( x∗ ) ≤ 0, ∀i =1, , m f ( x∗ ) ≤ xn∗+1 (1) xn∗+1 ≤ xn +1 , ∀ ( x, xn +1 ) ∈ D′ ( 2) Mặt khác ( x, f ( x ) ) ∈ D′ với x ∈ { x ∈  n | gi ( x ) ≤= m} D 0, i 1, ,= ( 3) ( ) Từ (1), (2), (3) suy f x∗ ≤ xn∗+1 ≤ f ( x ) , ∀x ∈ D Tức x∗ nghiệm (3.13) Sau ta áp dụng thuật tốn tuyến tính hóa ràng buộc phần trước để giải tốn (3.15) 3.3.2 Ví dụ x2 , x Tìm f ( x ) = x12 + x22 − x1 − 4= ( x1 , x2 ) ∈  với ràng buộc  x1 + x2 ≤  x , x ≥  Giải Ta đưa toán toán x3 → với ràng buộc  g1 ( x ) = x1 + x2 − ≤  − x1 ≤  g2 ( x ) =  − x2 ≤  g3 ( x ) = 2   g ( x ) = x1 + x2 − x1 − x2 − x3 ≤ Đặt x = ( x1 , x2 , x3 ) ∈ 3 1  −1 0  x1 −          ∇g1 ( x ) = , ∇ g x = , ∇ g x = − , ∇ g x = x − ( ) ( ) ( )         0 0 0  −1          Xây dựng đa diện lồi D1 : 50 Chọn 4= điểm x1 = = 2, ) , x ( 3,3,3) ) , x3 ( 2,= ( 0,0,0 ) , x (1,1,1 T T T T • Với x1 : h11 =x1 + x2 − ≤ 0, h12 =− x1 ≤ 0, h13 = − x2 ≤ 0, h14 = −8 x1 − x2 − x3 ≤ • Với x : h21 =x1 + x2 − ≤ 0, h23 =− x2 ≤ 0, h22 =− x1 ≤ 0, h24 =−6 x1 − x2 − x3 − ≤ • Với x : h31 =x1 + x2 − ≤ 0, h32 =− x1 ≤ 0, h33 =− x2 ≤ 0, h34 =−4 x1 − x3 − ≤ • Với x : h41 =x1 + x2 − ≤ 0, h42 =− x1 ≤ 0, h43 = − x2 ≤ 0, h44 = −2 x1 + x2 − x3 − 18 ≤ Đa diện D1 = { x ∈ 3 | hki ≤ 0}  x ∈  | x1 + x2 − ≤ 0, x1 ≥ 0, x2 ≥ 0, −8 x1 − x2 − x3 ≤ 0,  =  −6 x1 − x2 − x3 − ≤ 0, −4 x1 − x3 − ≤ 0, −2 x1 + x2 − x3 − 18 ≤   Các bước lặp Bước lặp Giải toán x3 → min, x ∈ D1 nghiệm tối ưu= x5 ( 2,0, −14 ) T D2 D1  { x ∈  | −4 x1 − x2 − x3 − ≤ 0} g ( x5 ) = > ⇒ I1 = {4} = Giải toán x3 → min, x ∈ D2 nghiệm tối= ưu x Tiếp tục trình ta có dãy nghiệm xấp xỉ sau: = x7 = x8 = x9 x9 ∈ D ⇒ dừng thuật toán (1.75,0.25, −12 ) , T (1.875,0.125, −12 ) , T ( 2,0, −12 ) T (1.5,0.5, −12 ) T 51 Vậy nghiệm tối ưu toán ban đầu x∗ = ( 2,0 ) giá trị tối ưu hàm mục tiêu T f ( 2, ) = −12 Nhận xét Ta khảo sát ba phương pháp số giải toán tối ưu phi tuyến có ràng buộc Bây ta xem xét ví dụ tốn hiệu suất xử lí nước thải đưa chương Nhắc lại tốn: Một cơng ty thực phẩm chọn phương pháp xử lí nước thải cơng nghệ Aeroten Xét trường hợp hiệu suất sử lí nước thải phụ thuộc vào hai yếu tố nồng độ bùn hoạt tính thời gian lưu nước bể Gọi x1 nồng độ bùn hoạt tính (kg/m3), x2 thời gian lưu nước bể (giờ), hiệu suất xử lí tính hàm mục tiêu: F = − x12 − x22 + x1 + 10 x2 + 44 Tìm nồng độ bùn hoạt tính thời gian lưu nước thích hợp để hiệu suất đạt tối ưu, biết nồng độ bùn từ 1.6 – kg / m3 thời gian lưu nước từ 2.5 – Ta có mơ hình tốn học toán: F ( x1 , x2 ) = − x12 − x22 + x1 + 10 x2 + 44 → max (3.16) với ràng buộc 1.6 ≤ x1 ≤  2.5 ≤ x2 ≤ (3.17) Bài toán (3.16), (3.17) toán phi tuyến có ràng buộc Ta xét mơ hình tốn cực tiểu hóa tương ứng với tốn (3.16), (3.17): f ( x1 , x2 ) = x12 + x22 − x1 − 10 x2 − 44 → (3.18) với ràng buộc (3.17) Bài toán (3.16), (3.17) có tập nghiệm với tốn (3.18), (3.17) Ta thấy toán (3.18), (3.17) toán tối ưu phi tuyến có ràng buộc, đồng thời tốn quy hoạch tồn phương, ta áp dụng phương pháp vừa khảo sát chương để giải toán (3.18), (3.17)  Phương pháp Hildreth – D’Esopo f ( x ) = x12 + x22 − x1 − 10 x2 − 44 → min, x = ( x1 , x2 ) ∈  52 với ràng buộc  x1 ≤  − x1 ≤ −1.6   x2 ≤ − x2 ≤ −2.5 Ta có d =( −8, −10 ) , T b =( 6, −1.6,8, −2.5 ) , T 1 0 −  0 1 0 1 0 −1  = = C = , A , C    0 1 0 1 0 1    −1 Tính AC −1= d +b = h ( 2, 2.4,3,7.5) T ,  −1 0    1  −1 0  −1 T = G = AC A 4  0 −1    0 −1  Ta tính điểm xấp xỉ: u k +1 = ( u1k +1 , u2k +1 , u3k +1 , u4k +1 ) thỏa mãn T = u1k +1 max {0, −4 + u2k } , = u2k +1 max {0, u1k − 4.8} , = u3k +1 max {0, −6 + u4k } , = u4k +1 max {0, u3k − 15} Xuất phát từ u = ( 0,0,0,0 ) ta nhận thấy bước lặp sau u khơng thay đổi nên T lời giải toán đối ngẫu Trở lại toán tìm ta tính x theo cơng thức: T x= − C −1 ( AT u1 + d ) = ( 4,5) với giá trị tối ưu hàm mục tiêu f = −85 Từ suy nghiệm tối ưu toán (3.16), (3.17) ( x1 , x2 ) = ( 4,5 ) gái trị hàm mục tiêu Fmax = 85% Như vậy, trở lại toán thực tế ta nhận kết cần tìm: o Nồng độ bùn hoạt tính: kg/m3 53 o Thời gian lưu nước bể: hiệu suất đạt tối đa 85%  Phương pháp Gradient có điều kiện f ( x ) = x12 + x22 − x1 − 10 x2 − 44 → min, x = ( x1 , x2 ) ∈  với ràng buộc  x1 ≤ − x ≤ −1.6    x2 ≤ − x2 ≤ −2.5  x1 −  Tính ∇f ( x ) = = x0   Chọn x − 10   ( 3,3) T ∈ D làm điểm xuất phát ∇f ( x ) =− ( 2, −4 ) , ϕ ( z ) =∇f ( x0 ) , z =−2 z1 − z2 T Giải tốn quy hoạch tuyến tính ϕ ( z ) → min, z ∈ D ta nghiệm tối ưu z − x0 = z = ( 6,8 ) , p = ( 3,5) , T T η0 =∇f ( x ) , p = −14 x1 = x + α p =+ ( 3α ,3 + 5α ) α = 2− q cho q số tự nhiên đầu T ( ) ( ) −q 0 −q tiên thỏa mãn bất đẳng thức f x + p ≤ f x + η0 Ta chọn q = hay α = 0.5 , suy x1 = ( 4.5,5.5 ) T ∇f ( x1 ) = (1,1) , ϕ ( z) = ∇f ( x1 ) , z = z1 + z2 T Giải tốn quy hoạch tuyến tính ϕ ( z ) → min, z ∈ D ta nghiệm tối ưu ( ) z1 − x1 = −5.9 z1 = (1.6, 2.5 ) p1 = ( −2.9, −3) , η1 =∇f x1 , p1 = T T Ta chọn α1 = 0.125 , suy x = ( 4.14,5.13) T ∇f ( x ) = ( 0.28,0.26 ) , T z2 = (1.6, 2.6 ) , T ϕ ( z) = ∇f ( x ) , z = 0.28 z1 + 0.26 z2 p2 = z − x2 = ( −2.54, −2.53) , T Ta chọn α = 0.0625 , suy x3 = ( 4,5 ) T η2 =∇f ( x ) , p = −1.369 54 ∇f ( x ) = ( 0,0 ) T ( ) Vậy x3 = ( 4,5 ) nghiệm tối ưu toán f x3 = −85 T  Phương pháp tuyến tính hóa f ( x ) = x12 + x22 − x1 − 10 x2 − 44 → min, x = ( x1 , x2 ) ∈  với ràng buộc  x1 ≤ − x ≤ −1.6    x2 ≤ − x2 ≤ −2.5 Ta đưa toán toán x3 → với ràng buộc  g1 ( x ) = x1 − ≤  − x1 + 1.6 ≤  g2 ( x ) =   g3 ( x ) = x2 − ≤  − x2 + 2.5 ≤  g4 ( x ) =  g ( x ) = x + x − x − 10 x − x − 44 ≤ 2  Áp dụng thuật toán tuyến tính hóa ràng buộc 1  −1 0 0  x1 −          ∇g1 ( x ) =  , ∇g ( x ) =  , ∇g3 ( x ) =  , ∇g ( x ) = −1 , ∇g5 ( x ) = x2 − 10  0 0 0 0  −1            Xây dựng đa diện lồi D1 Chọn = điểm x1 0, ) , x (1,1,1 = 2, ) , x ( 3,3,3) ( 0,= ) , x3 ( 2,= T T T • Với x1 : h11 =x1 − ≤ 0, h12 =− x1 + 1.6 ≤ 0, h13 =x2 − ≤ 0, h14 = − x2 + 2.5 ≤ 0, h15 = −8 x1 − 10 x2 − x3 − 44 ≤ • Với x : T 55 h21 =x1 − ≤ 0, h22 =− x1 + 1.6 ≤ 0, h24 = − x2 + 2.5 ≤ 0, h23 =x2 − ≤ 0, h25 = −6 x1 − x2 − x3 − 46 ≤ • Với x : h31 =x1 − ≤ 0, h32 =− x1 + 1.6 ≤ 0, h33 =x2 − ≤ 0, h34 = − x2 + 2.5 ≤ 0, h35 = −4 x1 − x2 − x3 − 50 ≤ • Với x : h41 =x1 − ≤ h42 =− x1 + 1.6 ≤ 0, h43 =x2 − ≤ 0, h44 = − x2 + 2.5 ≤ 0, h45 = −2 x1 − x2 − x3 − 59 ≤ Đa diện D1 = { x ∈ 3 | hki ≤ 0}  x ∈  | −8 x1 − 10 x2 − x3 − 44 ≤ 0, −6 x1 − x2 − x3 − 46 ≤ 0, −4 x1 − x2 − x3 − 50 ≤ 0,  =  −2 x1 − x2 − x3 − 59 ≤ 0, 1.6 ≤ x1 ≤ 6, 2.5 ≤ x2 ≤   Các bước lặp Bước lặp Giải toán x3 → min, g5 ( x5 ) = 31 > ⇒ I1 = x ∈ D1 nghiệm tối ưu= x5 {5} Giải toán x3 → min, ( 6,8, −103) T = D2 D1  { x ∈  | x1 + x2 − x3 − 144 ≤ 0} x ∈ D2 nghiệm tối ưu x (1.6, 6.94, −89.96 ) = T Tiếp tục q trình ta có dãy nghiệm xấp xỉ sau: = x7 = x8 = x9 = x10 = x11 (1.6,7.54, −92.36 ) , T ( 3.97,6.12, −91.41) , T ( 6, 4.25, −88) , T ( 4.55, 4.71, −86.93) , T ( 3.41,5.05, −85.07 ) , T 56 = x12 = x13 = x14 = x15 = x16 = x17 = x18 ( 4.12,5.36, −85.46 ) , T ( 3.94, 4.78, −85.32 ) , T ( 3.79,5.14, −85.09 ) , T ( 4.09,5.05, −85.09 ) , T ( 3.91, 4.97, −85.03) , T ( 4.04, 4.9, −85.01) , T ( 4,5, −85) T x18 ∈ D ⇒ dừng thuật toán Vậy nghiệm tối ưu toán ban đầu x∗ = ( 4,5 ) T f = −85 với giá trị hàm mục tiêu 57 KẾT LUẬN Luận văn tìm hiểu trình bày vài phương pháp số giải tốn cực tiểu hóa hàm tối ưu phi tuyến Bao gồm phương pháp: phương pháp Gradient (tham khảo [4]), phương pháp Newton với bước điều chỉnh (tham khảo [4]), phương pháp hướng đối ngẫu (tham khảo [4]) phương pháp tìm kiếm trực tiếp (tham khảo [1]) để giải số tốn phi tuyến khơng ràng buộc Phương pháp Hildreth – D’Esopo (tham khảo [3]) để giải số tốn quy hoạch tồn phương Các phương pháp: phương pháp Gradient có điều kiện (tham khảo [4]) phương pháp tuyến tính hóa (tham khảo [2]) để giải số tốn phi tuyến có ràng buộc Cụ thể, với phương pháp luận văn trình bày sở lí thuyết, thuật tốn thơng qua việc tìm hiểu, tổng hợp từ tài liệu tham khảo Sau phương pháp, luận văn cho ví dụ minh họa áp dụng thuật tốn phương pháp Ngồi ra, luận văn áp dụng vài phương pháp trình bày luận văn để giải toán thực tế đưa chương Do điều kiện có hạn trình độ người làm luận văn cịn hạn chế nên luận văn trình bày số phương pháp Các phương pháp trình bày luận văn phần nhỏ nhiều phương pháp số giải toán quy hoạch phi tuyến Do đó, có điều kiện tơi tiếp tục tìm hiểu trình bày dịp khác 58 TÀI LIỆU THAM KHẢO Tiếng Việt Nguyễn Thị Bạch Kim (2008), Giáo trình Các Phương pháp Tối ưu Lý thuyết Thuật toán, Nxb Bách khoa, Hà Nội Lê Đại Phước (2013), Phương pháp số lí thuyết tối ưu, Luận văn tốt nghiệp cao học chuyên ngành Tốn giải tích, Đại học sư phạm thành phố Hồ Chí Minh, Hồ Chí Minh Bùi Thế Tâm Trần Vũ Thiệu (1998), Các phương pháp Tối ưu hóa, Nxb Giao thơng vận tải, Hà Nội Tiếng Anh B.N.Pshenichy and Yu.M.Danilin (1982), Numerical methods in extremal problems, Mir Publishers, Moscow ... 1.1 Giới thiệu toán 1.2 Một số tính chất định tính toán tối ưu phi tuyến .3 CHƯƠNG MỘT SỐ PHƯƠNG PHÁP SỐ GIẢI BÀI TOÁN KHÔNG RÀNG BUỘC 13 2.1 Phương pháp Gradient ... x∈D 13 Chương MỘT SỐ PHƯƠNG PHÁP SỐ GIẢI BÀI TỐN KHƠNG RÀNG BUỘC Các phương pháp số giải toán phi tuyến không ràng buộc chia thành hai lớp : phương pháp sử dụng đạo hàm phương pháp không sử dụng... nghiên cứu số phương pháp sử dụng đạo hàm phương pháp gradient, phương pháp Newton, phương pháp hướng đối ngẫu phương pháp không dùng đạo hàm phương pháp tìm kiếm trực tiếp Điểm chung phương pháp thông