Các dạng bài toán tối ưu

CHƯƠNG 1 : CÁC BÀI TOÁN TỐI ƯU 1.1 Định nghĩa: một bài toán tối ưu là một bài toán có dạng: min{ ( ) | }f x x C∈ (1.1) Trong đó: X là một không gian nào đó. C X⊂ là tập chấp nhận được (tập ràng buộc). :f C → R là một hàm mục tiêu. Mỗi vectơ x C∈ gọi là một phương án (lời giải) chấp nhận được. Một lời giải x* gọi là tối ưu (hay chính xác hơn, tối ưu toàn cục) nếu *x C∈ sao cho: *( ) ( ), f x f x x C≤ ∀ ∈ . Một lời giải x C∈ gọi là tối ưu địa phương (cục bộ) nếu có một lân cận W của x (tập mở chứa x ) sao cho: ( ) ( ), f x f x x W≤ ∀ ∈ ∩C . Nhiều khi C được cho bởi: { }| ( ) 0, ( 1,.., )n iC x g x i m= ∈ ≤ =\ (1.2) với . Khi ấy các hệ thức : nig →\ \ ( ) 0 ( 1,.., )ig x i m≤ = gọi là các ràng buộc bất đẳng thức. Thí dụ 1.1: Một xưởng mộc sản xuất 2 loại bộ cờ bằng gỗ. Trên mỗi dây chuyền sản xuất bộ cờ nhỏ cần sử dụng máy móc là 3 giờ, và sản xuất bộ cờ lớn cần 2 giờ. Trong nhà xưởng có 4 dây chuyền và hoạt động 40 giờ một tuần. Bộ cờ loại nhỏ cần 1kg khối gỗ, và bộ cờ loại lớn cần 3kg. Nhưng lượng gỗ trong xưởng gỗ lại có hạn và chỉ có 200kg mỗi tuần. Khi bán mỗi bộ cờ loại lớn lời 20$ và mỗi bộ cờ loại nhỏ lãi 5$. Bài toán là quyết định sản xuất bao nhiêu mỗi loại để thu được lợi nhuận cao nhất? 1 Gọi : x1 : là số bộ cờ loại nhỏ. x2 : là số bộ cờ loại lớn. Mục tiêu bài toán: 1 2max 5. 20.z x x= + Ràng buộc về số giờ sản xuất trên các máy: 1 23. 2. 160x x+ ≤ Ràng buộc về khối lượng gỗ: 1 21. 3. 200x x+ ≤ Số lượng bộ cờ loại nhỏ, bộ cờ loại lớn là không âm: 1 2 0 0 x x ≥ ≥ Mô hình hoàn chỉnh: 1 2 1 2 1 2 1 2 max 5. 20. 3. 2. 160 1. 3. 200 0 0 z x x x x x x x x= + + ≤ + ≤ ≥ ≥ (1.3) 1.2 Các loại bài toán tối ưu 1.2.1 Tối ưu trong không gian hữu hạn chiều (X là không gian tuyến tính hữu hạn chiều) bao gồm: - Tối ưu tuyến tính: hàm mục tiêu f(x) là hàm tuyến tính và C là một tập đa diện, tức là được cho bởi (1.1) trong đó afin. ( )ig x - Tối ưu phi tuyến: lồi, không lồi, trơn, không trơn, địa phương, toàn cục. - Tối ưu rời rạc (tổ hợp): C là một cấu trúc rời rạc. - Tối ưu đa mục tiêu: không phải chỉ có một hàm mục tiêu duy nhất như trong bài toán (1.1) mà có một số mục tiêu không tương thích với nhau (nghĩa là không có 2 lời giải nào tối ưu theo mọi mục tiêu), cho nên cần dung hòa các mục tiêu theo cách nào hợp lý, hữu hiệu nhất. - Tối ưu nhiều cấp: bài toán gặp trong một hệ thống phân cấp, mà hàm mục tiêu cấp cao là f(x,y) phụ thuộc hai nhóm biến: và . Cấp cao chỉ trực tiếp kiểm soát x, còn y do cấp dưới quyết định. Khi cấp cao quyết định một trị cụ thể của x thì cấp dưới căn cứ theo trị đó để lựa chọn phương án tối ưu cho bản thân họ. Cấp cao biết bài toán tối ưu của cấp dưới, tức là biết rằng khi cho x thì y là lời giải tối ưu của bài toán này. Vấn đề đặt ra là cấp cao phải tìm x để đạt tối ưu mục tiêu của mình. px∈\ qy∈\ 1.2.2 Tối ưu trong không gian vô số chiều (X là một không gian tuyến tính định chuẩn) bao gồm: - Các bài toán biến phân: X là không gian các hàm liên tục [ ]: 0,x T →\ , 0 ( ) ( , ( ), ( )) T f x L t x t x t dt= ∫  , { }0| (0) , ( ) TC x X x x x T x= ∈ = = . (Tìm một hàm liên tục x(t), , sao cho x(0), x(T) có giá trị cho trước và tích phân 0 t T≤ ≤ 0 ( ) ( , ( ), ( )) T f x L t x t x t= ∫  dt nhỏ nhất có thể được). - Các bài toán điều khiển tối ưu: Tìm (hàm điều khiển) sao cho [ ]: 0, nu T → \ ( )u t U∈ h.k.n trên [0,T] và quỹ đạo tương ứng điều khiển ấy, tức là nghiệm x(t) của phương trình vi phân [ ]: 0, nx T →\ ( ) ( , ( ), ( ))x t g t x t u t= đạt cực tiểu của hàm phí tổn (ở đây U, , và 0 ( (0), ( )) ( , ( ), ( )) T h x x T J t x t u t dt+ ∫ ( , ( ), ( ))g t x t u t (.,.)h 0 ( , ( ), ( )) T J t x t u t dt∫ cho trước). Như vậy, 0 ( ) ( (0), ( )) ( , ( ), ( )) T f u h x x T J t x t u t d= + ∫ t và C là tập các hàm sao cho h.k.n trên [0,T] và [ ]: 0,u T U→ ( )u t U∈ ( ) ( , ( ), ( ))x t g t x t u t= . 3 1.3 Các bước của quá trình ra quyết định Người giải toán có hai hướng để giải quyết hoặc là dùng phương pháp định tính hoặc là dùng phương pháp định lượng. Chỉ sử dụng phương pháp định tính để ra quyết định, khi người giải tin tưởng vào quyết định của mình hoặc kinh nghiệm giải quyết các bài toán tương tự trong quá khứ. Trong vài trường hợp thì phương pháp này là thích hợp, tuy nhiên trong nhiều trường hợp ta dùng phương pháp định lượng để phục vụ cho quá trình quyết định. Người ra quyết định dùng phương pháp định lượng khi họ cảm thấy các bài toán đó có thể được giải quyết bởi các kỹ thuật có sẵn đã được xây dựng và áp dụng cho các bài toán tương tự, khi một bài toán lặp lại hoặc khi bài toán rất phức tạp liên quan đến nhiều biến. Kỹ năng phân tích định lượng thường phải dùng công cụ toán học, cả lý thuyết lẫn ứng dụng, và kinh nghiệm nghề nghiệp. Kỹ thuật tối ưu được ứng dụng trong đời sống thực và thường thấy trong các bài toán quản lý phức tạp. Một bài toán có nhiều kết quả khác nhau và quá trình tìm kết quả tốt nhất hay được gọi là tối ưu. Các bước của quát trình ra quyết định theo sơ đồ sau: Hình 1.1 Sơ đồ quá trình ra quyết định. Các bài toán trong thực tế thường có số biến và số ràng buộc là xác định và hầu hết được đưa về mô hình bài toán tối ưu tuyến tính, phi tuyến, rời rạc và nhiều mục tiêu. 4 Bài toán tối ưu phi tuyến với kích thước lớn (hoặc là hàm mục tiêu hoặc là một số ràng buộc là hàm phi tuyến hoặc hàm mục tiêu và một số ràng buộc là hàm phi tuyến) thường khó giải và thời gian giải chậm. Do đó bài toán phi tuyến thường được đưa về bài toán tuyến tính bằng phương pháp nội suy (hay còn gọi là phương pháp xấp xỉ tuyến tính hóa từng khúc) hoặc đưa bài toán quy hoạch phi tuyến về bài toán quy hoạch toàn phương. Bài toán tối ưu nhiều mục tiêu có thể đưa về bài toán một mục tiêu (thí dụ: như dùng phương pháp tổng trọng lượng, …). Bài toán tối ưu rời rạc là một dạng khác của bài toán quy hoạch nguyên. Cho nên, trong luận văn này chúng tôi chỉ tập trung xét các mô hình sau: - Mô hình quy hoạch tuyến tính. - Mô hình quy hoạch nguyên. - Mô hình quy hoạch toàn phương. 1.4 Các bài toán mô hình quy hoạch toán học 1.4.1 Quy hoạch tuyến tính Bài toán quy hoạch tuyến tính tổng quát: 1 2 3 1 2 min , , , 0, 0, T T i i T i i T i i j j z c x a x b i M a x b i M a x b i M x j N x j N = ≥ ∈ ≤ ∈ = ∈ ≥ ∈ ≤ ∈ jx dấu tùy ý, 3j N∈ (1.4) Ở đây M1, M2, M3, N1, N2, N3 là tập hợp chỉ số nào đó, cT là chuyển vị của vectơ c, x, ai và c là các vectơ n thành phần. bi là các số thực. Ta luôn quy ước vectơ là vectơ cột, và cT là vectơ hàng. 5 thí dụ 1.1 có mô hình toán (1.3) như sau : 1 2 1 2 1 2 1 2 max 5. 20. 3. 2. 160 1. 3. 200 0 0 z x x x x x x x x= + + ≤ + ≤ ≥ ≥ Bài toán quy hoạch tuyến tính tổng quát (1.4) có dạng ma trận là min Tz c x Ax b = ≤ (1.5) Ở đây bất đẳng thức vectơ Ax b≤ được hiểu là m bất đẳng thức theo thành phần, tức là , i = 1,..,m. Vậy quy hoạch tuyến tính có dạng tổng quát là (1.4) hoặc ở dạng ma trận (1.5). Trong nghiên cứu quy hoạch tuyến tính cũng như khi khi áp dụng nó, người ta thường dùng hai dạng đặc thù : ia x b≤ i Dạng chính tắc: min 0 Tz c x Ax b x = ≤ ≥ (1.6) Dạng chuẩn: min 0 Tz c x Ax b x = = ≥ (1.7) với: A : ma trận cấp m x n với các hàng là ai, i = 1,...,m và các cột Aj, j = 1,…,n. c, x : các vectơ n chiều. b : vectơ m chiều. 6 Chúng ta có thể đưa mô hình bài toán (1.3) về dạng chính tắc như sau: min 0 Tz c x Ax b x = ≤ ≥ (1.8) với : ( )5,20c = , 3 2 1 3 A ⎛ ⎞= ⎜ ⎟⎝ ⎠ , ( )160,200b = , ( )1 2,x x x= . Một số phương pháp giải bài toán quy hoạch tuyến tính: - Phương pháp Fourier – Motzkin. - Phương pháp đơn hình: + Thuật toán đơn hình. + Thuật toán đơn hình đối ngẫu. - Phương pháp Ellipsoid. - Phương pháp tỉ lệ Affine. - Thuật toán giảm thế. - Thuật toán theo đường trung tâm. Giải bài toán (1.8) bằng phương pháp đơn hình chúng ta có kết quả: - Nghiệm x1 = 0, x2=66.6667 - Mục tiêu lợi nhuận nhiều nhất z =1333.33. 1.4.2 Quy hoạch nguyên Bài toán quy hoạch nguyên là quy hoạch tuyến tính với các biến quyết định là số nguyên. Bài toán quy hoạch nguyên có dạng: 7 min T n z c x Ax b x = ≤ ∈] (1.9) Một số phương pháp giải bài toán quy hoạch nguyên: - Phương pháp nhánh và cận cho quy hoạch nguyên. - Phương pháp mặt phẳng cắt. Thí dụ 1.2: xét thí dụ 1.1, số lượng bộ cờ loại lớn, bộ cờ loại nhỏ phải có giá trị nguyên. Chúng ta có mô hình quy hoạch nguyên như sau: 1 2 1 2 1 2 1 2 max 5. 20. 3. 2. 160 1. 3. 200 0 0 , 1..2i z x x x x x x x x i x= + + ≤ + ≤ ≥ ≥ ∈ =] (1.10) Giải bài toán (1.10) bằng phương pháp nhánh và cận cho bài toán quy hoạch nguyên chúng ta có kết quả: - Nghiệm: x1 = 2, x2 = 66. - Mục tiêu lợi nhuận nhiều nhất z = 1330. Nếu nghiệm x chỉ nhận giá trị nhị phân thì bài toán quy hoạch nguyên được gọi là quy hoạch nhị phân, và có dạng: min {0,1} T n z c x Ax b x = ≤ ∈ (1.11) Các phương pháp giải cho bài toán quy hoạch nguyên đều đúng cho bài toán quy hoạch nhị phân, ngoài ra có một số phương pháp khác để giải bài toán quy hoạch nhị phân: 8 - Phương pháp nhánh và cận cho quy hoạch nhị phân. - Phương pháp mặt phẳng cắt. - Thuật toán cộng giải quy hoạch nhị phân. Thí dụ 1.3: một kẻ trộm thấy 8 đồ vật, có giá trị và trọng lượng khác nhau theo bảng sau: Đồ vật Giá trị Khối lượng Máy quay phim 15 2 Dây chuyền 100 20 Cái bình 90 20 Bức hình 60 30 TV 40 40 Đầu Video 15 30 Bàn cờ 10 60 Gạch 1 10 Anh ta muốn lấy đồ vật sao cho giá trị lớn nhất và tổng khối lượng không lớn hơn KLMAX = 102 mà anh ta có thể mang đi được. Mô hình toán: 8 1 8 1 min . {0,1}, 1..8 i i i i i i i z GIATRI x KHOILUONG x KLMAX x i = = = ≤ ∈ = ∑ ∑ (1.12) Giải bài toán (1.12) bằng phương pháp nhánh và cận cho bài toán quy hoạch nhị phân chúng ta có kết quả: - Nghiệm x1 = 1, x2 = 1, x3 = 1, x4 = 1, x5 = 0, x6 = 1, x7 = 0, x8 = 0. - Mục tiêu tổng giá trị lớn nhất = 280. 9 Nếu biến quyết định vừa nhận giá trị thực vừa nhận giá trị nguyên thì bài toán quy hoạch nguyên được gọi là quy hoạch nguyên hỗn hợp, và có dạng: min , T T n l z c x d y Ax By b x y = + + ≤ ∈ ∈\ ] (1.13) Các phương pháp giải bài toán quy nguyên hỗn hợp: - Phương pháp nhánh và cận cho quy hoạch nguyên hỗn hợp. Thí dụ 1.4: xét thí dụ 1.1 Tại một thời điểm nhất định xưởng chỉ có thế sản xuất bộ cờ loại lớn hoặc nằm trong khoảng [10, 30] hoặc không sản xuất. 1 2 1 2 1 2 1 2 2 max 5. 20. 3. 2. 160 1. 3. 200 0 0 or [10,30] z x x x x x x x x x = + + ≤ + ≤ ≥ = ∈ (1.14) Đưa bài toán (1.14) về dạng quy hoạch nguyên hỗn hợp như (1.15) 1 2 1 2 1 2 1 2 2 max 5. 20. 3. 2. 160 1. 3. 200 1. 0 10. 0 30. 0 {0,1} z x x x x x x x d x d d x= + + ≤ + ≤ − ≤ − + ≤ − ≤ ∈ (1.15) Giải bài toán (1.15) bằng phương pháp nhánh và cận cho bài toán quy hoạch hỗn hợp chúng ta có: - Nghiệm x1 = 33.3333, x2 = 30. - Mục tiêu lợi nhuận nhiều nhất z = 766.667. 10 1.4.3 Quy hoạch toàn phương Xét bài toán: 1min ( ) 2 T Tf x x Qx c Ax b = − ≤ x (1.16) c : là vectơ n chiều mô tả hệ số của hàm mục tiêu. Q : là ma trận đối xứng, (n x n). A : là ma trận (m x n). b : là vectơ m chiều x : là vectơ biến quyết định. Tùy thuộc vào giá trị của biến quyết định chúng ta có quy hoặc toàn phương tương ứng: - Nếu biến quyết định thì ta gọi là quy hoạch toàn phương. nx∈\ - Nếu biến quyết định nx∈] thì ta gọi là quy hoạch toàn phương nguyên. + Đặc biệt biến quyết định thì ta gọi là quy hoạch toàn phương nhị phân. {0,1}nx∈ - Nếu biến quyết định ix ∈\ , jx ∈] thì ta gọi là quy hoạch toàn phương hỗn hợp. Nếu Q là ma trận xác định dương thì bài toán quy hoạch toàn phương được gọi là bài toán quy hoạch toàn phương lồi. Một số phương pháp giải bài toán quy hoạch toàn phương: - Điều kiện Kuhn – Tucker. - Phương pháp Wolfe. Bài toán quy hoạch toàn phương lồi có một số phương pháp sau: - Phương pháp điểm trong cho bài toán quy hoạch toàn phương lồi. - Phương pháp mặt phẳng cắt cho bài toán lồi. - Phương pháp Ellipsoid. - Phương pháp Active-Set. 11 Thí dụ 1.5: Tìm khoảng cách giữa hai tam giác R và S có dạng như Hình 1.2 và khoảng cách nhỏ nhất là đường thẳng nối hai điểm *r R∈ và . *s S∈ Hình 1.2 Tam giác R, S Giải bài toán: Cho và . Bình phương khoảng cách giữa r và s có dạng: ( 1 2[ , ] Tr x x R= ∈ 3 4[ , ]Ts x x S= ∈ ) ( )2 21 3 2 4 Tx x x x x− + − = Hx với và 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 H −⎡ ⎤⎢ ⎥−⎢ ⎥= ⎢ ⎥−⎢ ⎥−⎣ ⎦ 12 1 2 3 4[ , , , ] Tx x x x x= thỏa các bất đẳng thức sau: 1 2 1 2 4 3 4 3 4 0 0 2 2 2 3 2 6 x x x x x x x x x ≥ ≥ + ≤ ≥ + ≥ + ≤ Bài toán có thể đưa về dạng bài toán QP 1min ( ) 2 Tf x x Q Ax b = ≤ x (1.17) với Q = 2.H 1 0 0 0 0 1 0 0 1 2 0 0 0 0 0 1 0 0 1 1 0 0 1 2 A −⎡ ⎤⎢ ⎥−⎢ ⎥⎢ ⎥= ⎢ ⎥−⎢ ⎥⎢ ⎥− −⎢ ⎥⎣ ⎦ , 0 0 2 2 3 6 b ⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥= ⎢ ⎥−⎢ ⎥⎢ ⎥−⎢ ⎥⎣ ⎦ Giải bài toán (1.17) bằng phương pháp Active-Set chúng ta có: - Nghiệm , . * [0.4,0.8]Tr = * [1,2]Ts = - Mục tiêu khoảng cách ngắn nhất giữa hai tam giác R, S là 1.34. 13