Giáo trình Tối ưu hoá ứng dụng

Nội dung text: Giáo trình Tối ưu hoá ứng dụng

1. TRƯỜNG Khoa . [\ [\ Giỏo trỡnh tối ưu hoỏ ứng dụng
2. Lời nói đầu Các bài toán tối −u nhằm nghiên cứu giải bài toán cực trị của một hàm d−ới những ràng buộc nào đó. Các ph−ơng pháp tối −u là một công cụ hữu hiệu giúp chúng ta có những giải pháp tốt nhất để giải quyết một vấn đề. Ngày nay, với sự phát triển của kỹ thuật tin học, phạm vi ứng dụng của tối −u hóa ngày càng mở rộng. Giáo trình Tối −u hóa ứng dụng nhằm mục đích giới thiệu cho ng−ời đọc những vấn đề cơ bản nhằm xác lập một vấn đề tối −u d−ới những ràng buộc nhất định và từ đó tìm kỹ thuật giải thích hợp. Nội dung giáo trình mô tả phần cơ sở lý thuyết ngắn gọn, đủ dùng cho ph−ơng pháp tính và thuật toán. Một số ví dụ minh họa cho ph−ơng pháp giải và các bài tập ứng dụng. Nguyễn Đắc Lực 1
3. Mục lục Lời nói đầu 1 Mục lục 2 Ch−ơng 1: Cơ sở của đại số tuyến tính 3 1.1. Ma trận và các phép tính ma trận 3 1.2. Định thức và các tính chất của chúng 4 1.3. Ma trận nghịch đảo và hạng của ma trận 5 1.4. Hệ ph−ơng trình tuyến tính 7 Ch−ơng 2: Khái niệm về các bài toán tối −u hóa 9 2.1. Bài toán tối −u hóa tổng quát 9 2.2. Các bài toán tối −u 9 Ch−ơng 3: Bài toán tối −u tuyến tính 11 3.1. Một số ví dụ về bài toán tối −u 11 3.2. Phát biểu bài toán 11 3.3. Tính đối ngẫu và định lý cơ bản của tối −u tuyến tính 12 3.4. Các ph−ơng pháp giải bài toán tối −u tuyến tính 13 3.5. Thuật toán đơn hình giải bài toán tối −u tổng quát 18 Ch−ơng 4: Bài toán tối −u nguyên tuyến tính 21 4.1. Bài toán tối −u nguyên tuyến tính 21 4.2. Một số mô hình thực tiễn 21 Ch−ong 5; Bài toán tối −u động 25 5.1. Bản chất bài toán tối −u động 25 5.2. Quá trình phân phối nhiều b−ớc 26 5.3. Cấu trúc quá trình tối −u động 33 5.4. Ph−ơng trình điều khiển tối −u các dự trữ 39 Ch−ơng 6: Bài toán tối −u phi tuyến không ràng buộc 41 6.1. Mở đầu 41 6.2. Điều kiện tối −u của bài toán không ràng buộc 41 6.3. Các ph−ong pháp dùng đạo hàm 42 6.4. Các ph−ơng pháp dùng đạo hàm 45 Ch−ơng 7: Bài toán tối −u phi tuyến có ràng buộc 49 7.1. Mở đầu 49 7.2. Ph−ơng pháp Gradient 50 7.3. Ph−ơng pháp hàm phạt 53 Ch−ơng 8: Quy hoạch thực nghiệm 55 8.1. Khái niệm về nhận dạng mô hình thống kê 55 8.2. Ph−ơng pháp bình ph−ơng bé nhất 55 8.3. Mô hình hồi quy tuyến tính bội 56 Tài liệu tham khảo 59 2
4. Ch−ơng 1: CƠ Sở ĐạI Số TUYếN TíNH Việc nghiên cứu các bài toán tối −u tuyến tính đòi hỏi phải sử dụng một phần của toán học, mà những phần đó ch−a đ−ợc nghiên cứu trong các giáo trình cơ sở. Trong đó tr−ớc hết phải nói đến đại số tuyến tính. Kiến thức quan trọng nhất để nghiên cứu các bài toán tối −u tuyến tính là các phép tính về ma trận, cách giải các hệ ph−ơng trình và bất ph−ơng trình tuyến tính. ở đây sẽ không chứng minh một số mệnh đề mà chỉ khẳng định. 1.1. Ma trận và các phép tính đối với ma trận 1.1.1. Ma trận: Ma trận là một bảng chữ nhật gồm m.n số sắp thành m hàng n cột d−ới dạng: a11 a12 a1n a21 a22 a2n am1 am2 amn Phần tử của ma trận ký hiệu aij, chỉ số thứ nhất ký hiệu chỉ số hàng, chỉ số thứ hai chỉ số cột của ma trận chứa phần tử aij. Số hàng (m) và số cột (n) của ma trận xác định kích thứơc của ma trận, ta nói ma trận có kích th−ớc m.n. Ma trận gồm các phần tử aij th−ờng đ−ợc ký hiệu bằng chữ in hoa: A. Ma trận có nhiều ký hiệu khác nhau. Ma trận A có thể đ−ợc viết d−ới dạng: ⎡a11 a12 a1n ⎤ ⎢a 21 a 22 a 2n ⎥ A= ⎢ ⎥ (1.1) ⎣⎢a m1 a m2 a mn ⎦⎥ Ma trận có số hàng bằng số cột (m=n) đ−ợc gọi là ma trận vuông. Lúc đó, ng−ời ta nói rằng ma trận vuông có cấp n. Ma trận mà các cột của nó là các hàng t−ơng ứng của ma trận ban đầu A thì đ−ợc gọi là ma trận chuyển vị của ma trận A và đ−ợc ký hiệu là AT, tức là: ⎡a11 a 21 a m1 ⎤ ⎢a12 a 22 a m2 ⎥ T A = ⎢ ⎥ (1.2) ⎣⎢a1n a 2n a mn ⎦⎥ 1.1.2. Các dạng ma trận: Ma trận chỉ có một cột đ−ợc gọi là vectơ cột, còn ma trận chỉ có một hàng gọi là vectơ hàng. Ma trận vuông có dạng: ⎡α1 0 ⎤ ⎢ 0 α 0 ⎥ ⎢ 2 ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ 0 0 α n ⎦ Đ−ợc gọi là ma trận đ−ờng chéo. Nếu ma trận đ−ờng chéo có tất cả αi= 1 thì đ−ợc gọi là ma trận đơn vị và th−ờng đ−ợc ký hiệu là E. Ví dụ: 3
5. ⎡1 0 0 0 ⎤ ⎢0 1 0 0 ⎥ E = ⎢ ⎥ ⎢0 0 1 0 ⎥ ⎢ ⎥ ⎣0 0 0 1 ⎦ Hai ma trận bằng nhau chỉ trong tr−ờng hợp chúng có cùng kích th−ớc và các phần tử t−ơng ứng bằng nhau. Nếu ma trận A có định thức khác không thì đ−ợc gọi là ma trận không kỳ dị (không suy biến). Trong tr−ờng hợp ng−ợc lại ma trận A đ−ợc gọi là ma trận kỳ dị hoặc là ma trận suy biến. 1.1.3. Phép tính đối với ma trận Muốn nhân ma trận với một hằng số (vô h−ớng) ta nhân mỗi phần tử của ma trận với số đó. ⎡αa11 αa12 αa1n ⎤ ⎢αa 21 αa 22 αa 2n ⎥ αA = ⎢ ⎥ (1.3) ⎢ ⎥ ⎣αa m1 αa m2 αa mn ⎦ Tổng của hai ma trận A và B có cùng kích th−ớc là ma trận C mới mà mỗi phần tử của nó bằng tổng các phần tử t−ơng ứng của ma trận A và B tức là: a + b a + b a + b ⎡a a a ⎤ ⎡ b b b ⎤ ⎡ 11 11 12 12 1n 1n ⎤ 11 12 1n 11 12 1n ⎢ a + b a + b a + b ⎥ ⎢ a 21 a 22 a 2n ⎥ ⎢ b 21 b 22 b 2n ⎥ 21 21 22 22 2n 2n A+B = ⎢ ⎥ + ⎢ ⎥ = ⎢ ⎥ = C (1.4) ⎢ ⎥ ⎢ ⎥ ⎢ a + b a + b a + b ⎥ ⎣ a m1 a m2 a mn ⎦ ⎣ b m1 b m2 b mn ⎦ ⎣ m1 m1 m2 m2 mn mn ⎦ Ma trận A nhân đ−ợc với ma trận B chỉ trong tr−ờng hợp số cột của ma trận A bằng số hàng của ma trận B. Nếu ma trận A có kích th−ớc m.n, còn ma trận B là n.l, thì kích th−ớc của ma trận C là tích ma trận Avà B sẽ là m.l. Và mỗi phần tử của ma trận C đ−ợc tính theo công thức: cij = ai1b1j +ai2b2j + + ain bnj (1.5) ở đây ai1, ai2 , ain là các phần tử hàng thứ i của ma trận A; còn b1j, b2j , bnj là các phần tử cột thứ j của ma trận B. 1/ Tích ma trận không có tính chất giao hoán, tức là nói chung: AB ≠ BA; 2/ (AB)C = A(BC) (luật kết hợp); 3/ (A+B)C = AC + BC; C (A+B) = CA + CB (luật phân bố); 4/ α(AB) = (αA)B = A(αB); 5/ AE = EA = A; Phép chuyển vị ma trận có tính chất sau: 1/ (A + B)T = AT + BT 2/ (AB)T = BT.AT Lũy thừa ma trận vuông A đ−ợc định nghĩa nh− sau: Ak = A.A A k lần và: Ak1Ak2 = Ak1+k2 1.2. Định thức và các tính chất của chúng 1.2.1. Khái niệm về hoán vị: Ta lấy n số đầu tiên: 1,2 , n. Mỗi cách sắp xếp các số ấy theo một thứ tự nào đó đ−ợc gọi là hoán vị của n số. Nh− ta đã biết số các hoán vị khác nhau sẽ bằng n!. 4
6. Số αi và αj tạo thành một nghịch thể trong hóan vị đã cho nếu αi > αj với i < j. Số các nghịch thế trong hoán vị I = (α1, α2 , , αn) bằng: k1 + k2 + + kn-1 ở đây ks là số tr−ờng hợp αs lớn hơn αs+1, αs+2 , αn (s = 1, 2, , n-1) trong hoán vị I. Hoán vị đ−ợc gọi là hoán vị chẵn nếu số nghịch thể trong hoán vị I là số chẵn, và đ−ợc gọi là hóan vị lẻ nếu số các nghịch thể là số lẻ. Ví dụ đối với hoán vị 5, 2, 3, 4,1 thì số tất cả các nghịch thế bằng: k1 + k2 + k3 + k4 = 4 +1 +1 +1 = 7. Vì vậy, hóan vị này là hóan vị lẻ. 1.2.2. Khái niệm về định thức và phép tính của chúng: Số bằng tổng đại số của tất cả các tích những phần tử ma trận vuông A mà trong đó mỗi tích chỉ gồm các phần tử khác hàng, khác cột của ma trận, tức là tổng các tích có dạng: a1j1 a2j2 anjn (1.6) đ−ợc gọi là định thức của ma trận A (Số tích đó bằng n!). Mỗi tích nh− thế lấy dấu cộng nếu hoán vị t−ơng ứng là chẵn, còn lấy dấu trừ, nếu lẻ. Khi tìm hạng của ma trận, ma trận nghịch đảo và giải hệ ph−ơng trình tuyến tính ta sẽ cần đến định thức. Định thức của ma trận A th−ờng đ−ợc ký hiệu là ∆n hoặc |A|. a11a12 a1n a a a n ∆ = |A| = 21 22 2n = | a (1.7) n ij 1 an1an2 ann Các phần tử, các hàng, các cột và cấp của ma trận A t−ơng ứng với các phần tử, các hàng, các cột và cấp của định thức |A|. Ví dụ: ta tính định thức cấp 3 theo quy tắc vừa nêu ra: a11a12a13 ∆3 = a21a22a23 = a11a22a33 + a12a23a31 + a13a21a32 - a13a22a31 - a12a21a33 - a11a23a32 a31a32a33 Ba số hạng đầu lấy dấu cộng, còn ba số hạng sau lấy dấu trừ, bởi vì hoán vị 1,2,3; 2,3,1 và 3,1,2 là chẵn (số nghịch thể t−ơng ứng là 0, 2 và 2) còn các hóan vị 3,2,1 ; 2,1,3 và 1,3,2 là hóan vị lẻ (số nghịch thể t−ơng ứng là 3,1 và 1). Ví dụ: 2 4 1 ∆3 = 3 0 -1 = 2.0.3 + 4(-1) .1 +1.3(-2) -[1.0.1+4.3.3+2(-1).(-2)] = -50. 1 - 2 3 1.2.2. Định thức con và phần phụ đại số: Định thức cấp (n-1) có từ định thức cấp n (∆n) bằng cách bỏ hàng i cột j đ−ợc gọi là định thức con ứng với phần tử aij của định thức ∆n và đ−ợc ký hiệu là Mij. Ta coi định thức cấp n: a11 a12 a1j a1n a 21 a 22 a 2j a 2n ∆n = a i1 a i2 a ij a in a n1 a n2 a nj a nn Khi đó định thức con của phần tử aij sẽ là định thức cấp (n-1): 5
7. a11 a12 a1j-1 a1j+1 a1n a 21 a 22 a 2j-1 a 2j+1 a 2n Mij = a i-11a i-12 a i-1, j-1 a i-1, j+1 a i-1,n a i-11a i-12 a i-1, j-1 a i-1, j+1 a i-1,n a n1 a n2 a nj-1 a nj+1 a nn Ví dụ: định thức con của phần tử a22 của định thức: 2 4 1 2 1 ∆ = 3 0 -1 sẽ là: M = = 2.3 -1.1 = 6-1 = 5 3 22 1 2 1 - 2 3 Định thức con của phần tử aij nhân với (-1) với số mũ bằng tổng các chỉ số của phần tử đó (i + j) đ−ợc gọi là phần phụ đại số của phần tử aij và đ−ợc ký hiệu là Aij. Vì vậy: i+j Aij = (-1) Mij (1.10) 2+2 Chẳng hạn, phần phụ đại số của phần tử a22 ở ví dụ vừa rồi sẽ là: A22=(-1) .5=5 1.3. Ma trận nghịch đảo và hạng của ma trận 1.3.1. Ma trận nghịch đảo: Đối với mỗi ma trận A không suy biến sẽ tồn tại một ma trận (ký hiệu A-1) thỏa mãn điều kiện: A-1A = AA-1 = E (1.17) Ma trận A-1 đ−ợc gọi là ma trận nghịch đảo của ma trận A và đ−ợc tính theo công thức: A* A-1 = (1.18) | A | Đôi khi ma trận A* đ−ợc gọi là ma trận phụ hợp của ma trận A. * Phần tử hàng i cột j của ma trận A là phần phụ đại số của phần tử aij của ma trận A. Từ đó: ⎡A A A ⎤ 11 21 n1 ⎢| A | | A | | A | ⎥ A-1 = ⎢ ⎥ (1.18a) ⎢ A A A ⎥ ⎢ 1n 2n nn ⎥ ⎣⎢ | A | | A | | A | ⎦⎥ ⎡2 3 2 ⎤ ⎢ ⎥ Ví dụ ta lấy ma trận cấp 3: A = ⎢ 1 2 1⎥ ⎣⎢ 3 1 ⎦⎥ Tr−ớc khi đi tính ma trận nghịch đảo, cần xác định ma trận A cho ở đây không phải là ma trận suy biến, tức là định thức của nó khác không. Định thức của ma trận đó sẽ bằng: | A | = 2.2.1 +3.1.3 +2.1.1 - 2.2.3 -3.1.1 - 2.1.1= -2 Sau đó ta tính các phần phụ đại số của các phần tử của ma trận 1+1 2 1 A11 = ( -1) 1 1 = 2.1-1.1 =1 1+2 1 1 A12 = ( -1) 3 1 = -(1.1-3.1) = 2 1+3 1 2 A13 = ( -1) 3 1 =1.1-2.3 = -5 T−ơng tự ta tìm đ−ợc các Aij còn lại: A21 = -1 ; A22 = - 4; A23 = 7; A31 = -1 ; A32 = 0; A33= 1. 6
8. ⎡-1/2 -1 5/2⎤ -1 ⎢ ⎥ Do đó ta có: A = ⎢ - 1 2 7/2⎥ ⎣⎢ 1/2 0 -1/2⎦⎥ áp dụng quy tắc nhân ma trận, đem nhân ma trận A với ma trận A-1 vừa tìm đ−ợc ta dễ dàng thấy đ−ợc kết quả là một ma trận đơn vị. Và có thể dùng cách này để kiểm tra việc tính ma trận nghịch đảo có đúng không. Ma trận nghịch đảo của ma trận đơn vị cũng là ma trận đơn vị. Điều này suy ra từ việc nhân ma trận bất kỳ với ma trận đơn vị đ−ợc đúng ma trận đó. Dùng các quy tắc đã nêu ở trên ta nhân hai ma trận đơn vị với nhau. ⎡ 1 0 0⎤ ⎡ 1 0 0⎤ ⎡ 1 0 0⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ EE = ⎢ 0 1 0⎥ ⎢ 0 1 0⎥ = ⎢ 0 1 0⎥ ⎣⎢ 0 0 0⎦⎥ ⎣⎢ 0 0 0⎦⎥ ⎣⎢ 0 0 0⎦⎥ Từ đó suy ra rằng E-1 = E Cũng có thể chứng minh điều đó bằng cách tính trực tiếp ma trận nghịch đảo theo công thức (1.18). 1.4. Hệ ph−ơng trình tuyến tính 1.4.1. Dạng của hệ ph−ơng trình tuyến tính: Dạng tổng quát của hệ ph−ơng trình tuyến tính đ−ợc viết nh− sau: a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 (1.20) am1x1 + am2x2 + amnxn = bm Hệ này đ−ợc viết d−ới dạng ma trận là: AX = B (1.20a) ở đây A là ma trận đ−ợc thành lập từ các hệ số của các biến: A = (aij) với i = 1,2, , m; j = 1, 2, , n. X - là véctơ cột của các biến ⎡x1 ⎤ ⎢x2 ⎥ X = ⎢ . ⎥ (1.21) ⎢ ⎥ ⎣xn ⎦ B - là véctơ cột các số hạng tự do ⎡b1 ⎤ ⎢b2 ⎥ B = ⎢ . ⎥ (1.22) ⎢ ⎥ ⎣bm ⎦ Hệ ph−ơng trình tuyến đ−ợc gọi là: Thuần nhất, nếu tất cả các bi = 0 (i = 1, 2 m) và không thuần nhất, nếu có ít nhất một bi ≠ 0. T−ơng thích, nếu hệ có ít nhất một nghiệm, tức là tồn tại một bộ số mà khi thay vào ph−ơng trình sẽ có một đồng nhất thức, và gọi là không t−ơng thích nếu không có một nghiệm nào; xác định nếu hệ chỉ có một nghiệm duy nhất, và bất định nếu tồn tại quá một nghiệm. Muốn giải hệ ph−ơng trình tuyến tính, thì tr−ớc hết phải xác định xem hệ đã cho t−ơng thích hay là không t−ơng thích. Nếu là hệ t−ơng thích thì lại phải xem hệ là xác định hay bất định. 7
9. Nếu hệ ph−ơng trình là xác định thì ta đi tìm nghiệm duy nhất của nó. 1.4.2. Giải hệ ph−ơng trình tuyến tính: Khi giải hệ ph−ơng trình tuyến tính có thể xảy ra hai tr−ờng hợp: n =m và n ≠m. Tr−ớc hết là ta xét tr−ờng hợp n = m. Lúc đó ma trận A sẽ có dạng: ⎡a11 a12 a1n ⎤ ⎢ a 21 a 22 a 2n ⎥ A = ⎢ ⎥ ⎣⎢ a n1 a n2 a nn ⎦⎥ Giả thiết ma trận A không suy biến, tức là | A| ≠ 0, khi đó sẽ tồn tại ma trận nghịch đảo A-1. Ta nhân vế trái và vế phải của đẳng thức (1.20a) với A-1 về bên trái. Ta sẽ đ−ợc: A-1AX = A-1B. Bởi vì A-1A = E mà nhân bất cứ ma trận nào với E sẽ đ−ợc đúng ma trận đó, nên: X = A-1B (1.23) Sau khi thế A-1 bởi biểu thức (1.18a) và thay các véctơ cột X và B ở (1.21) và (1.22) rồi nhân ma trận A-1 với B ta có: ⎡x1 ⎤ ⎡A11b1 + A21b2 + + An1bn ⎤ ⎢x ⎥ 1 ⎢A b + A b + + A b ⎥ 2 = 12 1 22 2 n2 n ⎢ . ⎥ | A | ⎢ . . . ⎥ ⎢ ⎥ ⎢ ⎥ ⎣xn ⎦ ⎣A1nb1 + A2nb2 + + Annbn ⎦ Vì hai ma trận chỉ bằng nhau khi các phần tử t−ơng ứng của chúng bằng nhau, nên 1 x = (A b + A b + A b ) 1 | A | 11 1 21 2 n1 n 1 x = (A b + A b + A b ) (1.23a) i | A | 1i 1 2i 2 ni n 1 x = (A b + A b + A b ) n | A | 1n 1 2n 2 nn n Ta xét tr−ờng hợp thứ hai (m ≠n). Ta gọi ma trận: ⎡a11 a12 a1n ⎤ A = ⎢ ⎥ là ma trận cơ sở của hệ. ⎣⎢ a m1 a m2 a mn ⎦⎥ Sau khi thêm cột các số hạng tự do vào ma trận A ta lập đ−ợc ma trận mở rộng B: ⎡a11 a12 a1nb1 ⎤ B = ⎢ ⎥ (1.26) ⎣⎢ a m1 a m2 a mnbm ⎦⎥ Từ đó, ta có định lý Crônecke - Capeli: Để hệ ph−ơng trình tuyến tính là t−ơng thích, điều kiện cần và đủ là hạng của ma trận cơ sở và ma trận mở rộng bằng nhau. Nếu hạng của chúng bằng nhau và số ẩn bằng hạng của ma trận cơ sở thì hệ có nghiệm duy nhất. Nếu hạng của ma trận A nhỏ hơn số ẩn thì hệ có vô số nghiệm. Hệ ph−ơng trình tuyến tính thuần nhất luôn luôn t−ơng thích, bởi vì luôn luôn có nghiệm không, đ−ợc gọi là nghiệm tầm th−ờng. Nếu hạng của ma trận bằng số ẩn thì hệ thuần nhất chỉ có duy nhất một nghiệm là không. Muốn hệ tồn tại nghiệm khác không thì hạng của ma trận cơ sở phải nhỏ hơn số ẩn. 8
10. Ch−ơng 2: Khái niệm về các bài toán tối −u hoá 2.1. Bài toán tối −u hoá tổng quát 2.1.1. Phát biểu: Tìm trạng thái tối −u của một hệ thống sao cho đạt đ−ợc mục tiêu mong muốn về chất l−ợng theo một nghĩa nào đó. 2.1.2. Các yếu tố của một bài toán tối −u hoá: Một bài toán tối −u hoá có ba yếu tố cơ bản sau: * Trạng thái: mô tả trạng thái của hệ thống cần tối −u hoá. * Mục tiêu: đặc tr−ng cho tiêu chuẩn hoặc hiệu quả mong muốn (chi phí ít nhất, hiệu suất cao nhất, trọng l−ợng nhỏ nhất, thời gian ngắn nhất, ). * Ràng buộc: thể hiện các điều kiện kinh tế, kỹ thuật mà hệ thống phải thỏa mãn. 2.2. Các bài toán tối −u 2.2.1. Bài toán quy hoạch tuyến tính: Hệ thống ở trạng thái tĩnh có các biến trạng thái là: T x = [ x1, x2 , , xn] (2.1) Mục tiêu đ−ợc diễn đạt bởi hàm mục tiêu có dạng tuyến tính: T Z = c.x; với c = [c1, c2, , cn] (2.2) Các ràng buộc đ−ợc diễn đạt bởi những ph−ơng trình, bất ph−ơng trình tuyến tính: A.x = b; A.x ≤ b (2.3) T A = (aij), i = 1, , m ; j = 1, , n ; b = [b1, b2, , bm] . Bài toán: * * * * T Tìm trạng thái tối −u x = [x 1 , x 2 , , x n ] của trạng thái (2.1) với các ràng buộc (2.3) sao cho hàm mục tiêu (2.2) đạt giá trị nhỏ nhất (Min) hoặc giá trị lớn nhất (Max). 2.2.2. Bài toán quy hoạch phi tuyến: Hệ thống ở trạng thái tĩnh. Tìm trạng thái tối −u x* khi hàm mục tiêu đ−ợc diễn đạt bởi một hàm phi tuyến f(x) hoặc có ít nhất một ràng buộc phi tuyến: gr (x) ≤ 0; r = 1, , m. 2.2.3. Bài toán cực trị phiếm hàm: Hệ thống ở trạng thái tĩnh hoặc trạng thái động. Biến trạng thái là z(x) với x là biến độc lập. Mục tiêu đ−ợc diễn đạt bởi phiếm hàm mục tiêu: x 1 . J(z) = ∫ L(z, z, x)dx xn . . . . . T T với z = [z1(x), z2(x), zn(x)] ; z = [z1 (x), z 2 (x), , z n (x)] ; z i (x) = dzi / dx Ràng buộc có thể là các hàm phi tuyến, các ph−ơng trình đại số hoặc các ph−ơng trình vi phân. 2.2.4. Bài toán điều khiển tối −u: * Đối với hệ liên tục: Hệ thống ở trạng thái động, trạng thái đ−ợc mô tả bởi hệ ph−ơng trình vi phân: x& = f(t,x,u); t - thời gian T trong đó x& = [ x&1 ,x&2 ,x&n ] ; x& i = dxi /dt; T u = [u1, , un] ; u - điều khiển Mục tiêu có dạng phiếm hàm: t1 J(u) = ∫ L (t, x, x&,u) dt tn * Đối với hệ rời rạc: 9
11. Hệ thống ở trạng thái động, trạng thái đ−ợc mô tả bởi ph−ơng trình: xk+1 = f(xk,uk); x(0) = x0, x(N,T0) = xN ∈ X Mục tiêu có dạng: N −1 J(u) = ∑ f 0 ( xk ,uk ) → min; uk∈Ω k =0 ƒ Bài toán đặt ra: Cần phải tìm điều khiển tối −u u* và trạng thái tối −u x* để hệ thống chuyển từ trạng thái đầu đến trạng thái cuối sao cho mục tiêu J(u) đạt Min hoặc Max. Các bài toán tối −u có trạng thái tĩnh đ−ợc gọi là bài toán tối −u hoá tĩnh, các bài toán có trạng thái phụ thuộc thời gian đ−ợc gọi là bài toán tối −u hoá động. Trạng thái của hệ thống có thể ở dạng liên tục hoặc gián đoạn. Trong bài toán tối −u có thể đặt ra một mục tiêu hoặc nhiều mục tiêu. 10
12. Ch−ơng 3: bài toán tối −u tuyến tính 3.1. Một số ví dụ về bài toán tối −u tuyến tính 3.1.1. Bài toán vận tải: Có m điểm sản xuất cùng 1 loại sản phẩm a và n điểm tiêu thụ b. Cho rằng trong 1 m n đơn vị thời gian l−ợng cung và cầu bằng nhau: ∑ ai = ∑b j i=1 j=1 Gọi xij ≥ 0 và cij lần l−ợt là l−ợng sản phẩm và chi phí vận chuyển từ điểm i đến j Tìm ph−ơng án chuyên chở sao cho chi phí chuyên chở là nhỏ nhất. m n Z = ∑ ∑ cijxij → Min i=1 j=1 3.1.2. Bài toán phân phối kế hoạch sản xuất: Có n xí nghiệp sản xuất m loại chi tiết. Gọi: ai: số chi tiết loại i; bj: quỹ thời gian giành cho sản xuất ở xí nghiệp j; xij: số chi tiết loại i của xí nghiệp j; cij: chi phí cho chi tiết i ở xí nghiệp j; λij: thời gian sản xuất 1 chi tiết loại i ở xí nghiệp j. Tìm xij, (i = 1 ữm; j = 1 ữ n) sao cho hoàn thành khối l−ợng trong quỹ thời gian cho phép với chi phí ít nhất, nghĩa là: m n Hàm mục tiêu Z = ∑ ∑ cij xij → min i=1 j=1 Các điều kiện ràng buộc: n m ∑∑xij = ai ; i = 1 ữ m ; λ ij ≤ b j ; xij ≥ 0. j==1 j 1 3.1.3. Bài toán thực đơn: Chất dinh d−ỡng Nhu cầu tối thiểu hàng ngày Loại thức ăn P1 P2 N1 b1 a11 a12 N2 b2 a21 a22 N3 b3 a31 a32 N4 b4 a41 a42 Giá tiền đơn vị thức ăn c1 c2 Tiền thức ăn hàng ngày: Z = c1x1 + c2x2. Tìm l−ợng x1, x2 của từng loại thức ăn sao cho Z → Min với các ràng buộc: a11 x1 + a12 x2 ≥ b1 a41 x1 + a42 x2 ≥ b4 xi ≥ 0 3.2. Phát biểu bài toán 3.2.1. Định nghĩa: Bài toán tối −u tuyến tính chuyên nghiên cứu ph−ơng pháp tìm giá trị nhỏ nhất (Min) hoặc giá trị lớn nhất (Max) của một hàm tuyến tính theo một số biến, thoả mãn một số hữu hạn ràng buộc đ−ợc biểu diễn bằng hệ ph−ơng trình và bất ph−ơng trình tuyến tính. 3.2.2. Hai dạng cơ bản của bài toán tối −u tuyến tính: 1. Dạng chính tắc: ràng buộc ở dạng đẳng thức. 11
13. ⎡a11 a1n ⎤ Đặt A = ⎢ ⎥ ⎣⎢am1 amn ⎦⎥ A đ−ợc gọi là ma trận hệ số của các ràng buộc. ⎡x1 ⎤ ⎡c1 ⎤ ⎡b1 ⎤ ⎢x ⎥ ⎢c ⎥ ⎢b ⎥ x = 2 ; x ≥ 0; c = 2 ; b = 2 ⎢. ⎥ j ⎢. ⎥ ⎢. ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣xn ⎦ ⎣cn ⎦ ⎣bm ⎦ * * * T Tìm các giá trị tối −u x = [x 1 , ,x n] sao cho hàm mục tiêu: n Z = cx = ∑c j x j → Max j=1 với các ràng buộc: Ax = b x ≥ 0 2. Dạng chuẩn: ràng buộc ở dạng bất đẳng thức. Tìm x sao cho Z = c.x → Max với các ràng buộc: Ax ≤ b x ≥ 0 3.2.3. Chuyển bài toán tối −u tuyến tính về dạng chuẩn hoặc dạng chính tắc T 1. Thêm vào các biến phụ: w = [xn +1, , xn+m] Khi đó A.x ≤ b → A.x + E.w = b ; E: ma trận đơn vị. Ví dụ: 2x1 + x2 ≤ 15 2x1 + x2 + x 3 = 15 0,5x1 + 3x2 ≤ 18 0,5x1 + 3x2 + x 4 = 18 x ≤ 12 x + x = 12 1 → 1 5 x 2 ≤ 9 x 2 + x 6 = 9 x1 ≥ 0 ; x 2 ≥ 0 x j ≥ 0 ; j = 1 ữ 6 Z = 4x1 + 7x2 Z = 4x1 + 7x2 + 0.x3 + + 0.x6 2. Nếu ràng buộc ở dạng A.x ≥ b: nhân hai vế với (-1): n - ∑ aij x j ≤ −bi khi đó ta có: A1.x ≤ B1 j=1 3. Nếu ràng buộc ở dạng đẳng thức: A.x = b có thể thay bằng hai ràng buộc bất đẳng thức A.x ≤ b và -A.x ≤ -b. 3.2.4. Quan hệ giữa bài toán Min và bài toán Max: Trong bài toán min: Z = c.x → Min Nếu đặt Z1 = - c.x → Max. * * Gọi x là trạng thái tối −u Z1 tức là - c.x = Max(Z1) khi đó: - c.x* ≥ - c.x hay c.x* ≤ c.x Chứng tỏ x cũng là trạng thái tối −u của bài toán Min. * Min (Z) = c.x = - Max (Z1) = - Max (-Z). 3.3. Tính đối ngẫu và định lý cơ bản của bài toán tối −u tuyến tính 3.3.1. Bài toán đối ngẫu: T Bài toán gốc (dạng chuẩn): tìm x = [x1, ,xn] để hàm mục tiêu: T T Z = c.x → Max; c = [c1, , cn) ; b = [b1, ,bm] 12
14. ⎧Ax ≤ b Với ràng buộc: ⎨ ⎩ x ≥ 0 Ta có bài toán đối ngẫu t−ơng đ−ơng với bài toán dạng chuẩn: T Tìm y = [y1, ,ym] để hàm mục tiêu V = b.y → Min ⎧AT .y ≥ c Với ràng buộc: ⎨ ⎩ y ≥ 0 Chuẩn Sơ đồ đối ngẫu: x1 x2 xn y1 a11 a12 a1n ≤ b1 y 2 a21 a22 a2n ≤ b2 đối ngẫu đối ym am1 am2 amn ≤ bm ≥ ≥ ≥ Min c1 c2 cn Max Ng−ời ta đã chứng minh đ−ợc: Giá trị tối −u của bài toán chuẩn cũng là giá trị tối −u của bài toán đối ngẫu, nghĩa là: c.x* = b.y*. 3.3.2. Định lý cơ bản của bài toán tối −u tuyến tính: Định lý: Ph−ơng án tối −u của bài toán tối −u tuyến tính chứa một số biến d−ơng đúng bằng số các ràng buộc dạng đẳng thức độc lập đ−ợc thoả mãn, các biến còn lại có giá trị không. T Ví dụ: x = [x1, x2, , x5] → n = 5 ⎧a11 x1 + + a15 x5 = b1 ⎪ Các ràng buộc: ⎨ → m = 3 ⎪ ⎩a 31 x1 + + a35 x5 = b3 do đó nghiệm tối −u có 3 biến khác không x* = [*, *, *, 0, 0]T. 3.4. Các ph−ơng pháp giải bài toán tối −u tuyến tính 3.4.1. Ph−ơng pháp đồ thị: Ph−ơng pháp này đ−ợc dùng khi số biến số ≤ 3. 1. Bài toán phẳng: * * * T Ví dụ: Tìm x = [x1 , x2 ] sao cho Z = c1x1 + c2x2 → Max Các ràng buộc: a11 x1 + a12 x2 ≤ b1 a21x1 + a22 x2 ≤ b2 x1 ≥ 0, x2 ≥ 0 Giải: ƒ Vẽ miền chấp nhận đ−ợc (miền D mà x thoả mãn các ràng buộc hình 3.1): + Nếu ràng buộc là đẳng thức thì miền chấp nhận đ−ợc là điểm A, giao điểm của đ−ờng N1M1 và N2M2. + Nếu là bất đẳng thức thì miền chấp nhận đ−ợc là hình AN1OM2, bao gồm cả biên AN1, AM2. ƒ Vẽ các đ−ờng cùng mục tiêu (đ−ờng mức): 13
15. z0 c1 + Cho một giá trị cụ thể Z = Z0. Vẽ đ−ờng x2 = − x1 c1 c2 Thay đổi giá trị Z0 ta đ−ợc các đ−ờng song song. Trên mỗi đ−ờng, hàm mục tiêu có cùng giá trị. Giá trị Z0 càng lớn thì đ−ờng x2 càng xa 0. ƒ Tìm nghiệm tối −u: + Nghiệm cực đại đ−ợc xác định bởi toạ độ điểm A. + Nếu đ−ờng cùng mục tiêu tiếp xúc một đỉnh thì nghiệm tối −u là đơn trị. + Nếu đ−ờng cùng mục tiêu tiếp xúc 2 đỉnh (1 cạnh) thì nghiệm là đa trị. + Nếu miền chấp nhận đ−ợc nh− hình 2.2 thì toạ độ điểm A xác định giá trị cực tiểu. x x =z /c - (c /c )x x2 x2=z9/c1 - (c1/c2)x1 2 2 9 1 1 2 1 N N2 2 D N N1 1 A A * x2 x2 D * O x * M M x O x * M M x 1 2 1 1 1 2 1 1 Hình 2.1 Hình 2.2 2. Mở rộng: Đối với bài toán có n biến x1, , xn, chịu m ràng buộc: 1/ Nghiệm tối −u là toạ độ của một đỉnh hay nhiều đỉnh của miền cho phép. Miền cho phép là một đa diện lồi (n - m) chiều. 2/ Nghiệm là đơn trị nếu 1 đỉnh của đa diện cho phép tiếp xúc với mặt cùng mục tiêu. 3/ Nghiệm là đa trị nếu tiếp xúc tại k đỉnh (k >1); k đỉnh này tạo nên 1 đơn hình (k-1) chiều. Do đó có thể lấy (k-1) giá trị các biến tuỳ ý, còn n - (k-1) biến khác là hàm tuyến tính của (k-1) biến tuỳ ý. Đó sẽ là cơ sở của ph−ơng pháp đơn hình. Chú ý: Đơn hình là 1 hình có số đỉnh nhiều hơn 1 so với số chiều của không gian. Thí dụ, trong không gian 2 chiều thì đơn hình là tam giác, trong không gian 3 chiều thì đơn hình là tứ diện. 3.4.2. Ph−ơng pháp đơn hình: Ph−ơng pháp này do nhà toán học Mỹ G.B. Dantzig đ−a ra năm 1948. Nội dung: Tìm đỉnh tối −u của đa diện các nghiệm cho phép bằng ph−ơng pháp lần l−ợt thử các đỉnh của đa diện. Để việc thử không phải mò mẫm, ng−ời ta đ−a ra thuật toán để đi từ nghiệm xấu hơn tới nghiệm tốt hơn tức đi dần tới nghiệm tối −u. 1. Nội dung ph−ơng pháp đơn hình: Giả sử có m ràng buộc độc lập đ−ợc cho ở dạng chính tắc: A.x = b (3.1) 1) Chọn biến cơ sở: đầu tiên ta chọn một điểm tuỳ ý của đa diện các nghiệm cho phép, đó là tập n số (x1, , xn). Theo định lý cơ bản của bài toán tối −u tuyến tính thì có m số d−ơng, còn những số khác bằng không; gọi các biến d−ơng của điểm xuất phát là biến cơ sở: (x1, x2, , xm, 0, 0, , 0). 2) Tìm nghiệm xuất phát (nghiệm thử thứ 1): Thay các biến cơ sở vào các ràng buộc (3.1) đ−ợc m ph−ơng trình chứa m ẩn: ar1 x1 + ar2 x2 + armxm = br; r = 1, 2 , , m. 14
16. ⎧a11 x1 + + a1m xm = b1 ⎪ hay: ⎨ (3.2) ⎪ ⎩am1 x1 + + amm xm = bm Từ đó tìm đ−ợc nghiệm xuất phát (hay nghiệm thử thứ 1): ( 0 ) ( 0 ) ( 0 ) ( x1 ,x2 , ,xm ) . 3) Chọn nghiệm thử thứ 2: a) Thử thêm vào biến xm+1, lúc này ràng buộc có dạng: {ar1 x1 + ar2 x2 + + arm xm + ar,m+1 xm+1 = br ; r = 1, 2, , m (3.3) Hệ (3.3) gồm m ph−ơng trình với m+1 biến, (3.3) có nghiệm đơn trị khi các ph−ơng trình tạo thành hệ phụ thuộc, do đó cột cuối cùng phụ thuộc tuyến tính vào các cột còn lại với hệ số yi: ar,m+1 = y1ar1 + + ymarm hay ar1y1 + + armym = ar,m+1 (3.4) ( 0 ) ( 0 ) ( 0 ) Hệ (3.4) có nghiệm duy nhất là: y1 , y2 , , ym . b) Lấy các số hạng t−ơng ứng của ph−ơng trình (3.3) trừ đi bội số của (3.4) ký hiệu bội số đó là λ > 0, ta có: ar1(x1 - λy1) + ar2 (x2 - λy2) + + arm (xm - λym) + ar,m+1λ = br (3.5) r = 1,2, m. Hệ (3.5) là biến thể của (3.4) chỉ có các ẩn là khác nhau. c) Chọn nghiệm thử thứ 2 cho (3.5) là: (0) (0) (0) (0) (0) (0) (x1 − λ.y1 ), (x 2 − λ.y2 ), ,(xm − λ.ym ),λ (3.6) Vì có m+1 biến, do đó một trong các biến phải nhận giá trị không. Ngoài ra các biến còn lại xm+2 , , xn cũng phải bằng không. Muốn biết biến nào trong (3.6) bằng không, cần phải: Tính giá trị của hàm mục tiêu với nghiệm thử thứ 1 và thử nghiệm thứ 2: (0) (0) (0) Z0 = c1x1 + c2x2 + , + cmxm (0) (0) (0) (0) (0) (0) Z1 = c1 (x1 − λ.y1 ) + c2 (x2 − λ.y2 ) + + cm (xm − λ.ym ) + cm+1λ Đặt số gia: ∆Z1 = Z1 - Z0 (0) (0) (0) ∆Z1 = λ[cm+1 − (c1 y1 + c2 y2 + + cm ym )]= λ[cm+1 − γ m+1 ] (0) (0) (0) trong đó: γm+1 = c1 y1 + c2 y2 + + cm ym []cm+1−ym+1 đ−ợc gọi là hiệu suất. (3.7) Có ba tr−ờng hợp xảy ra: * ∆Z1 = 0: nghiệm xuất phát và nghiệm mới tốt nh− nhau. Suy ra có hai đỉnh tiếp xúc giữa đa diện cho phép và mặt cùng mục tiêu. * ∆Z1 0: nghiệm mới tốt hơn nghiệm xuất phát. Khi đã chọn đ−ợc nghiệm mới bằng hoặc tốt hơn (∆Z1 ≥ 0) ta đ−a nó vào cơ sở và cần phải loại bỏ bớt một nghiệm trong biến xuất phát (theo định lý cơ bản), chỉ có m nghiệm d−ơng). Giả thiết đã đ−a biến mới thứ (m +1) vào cơ sở, khi đó có thể viết các biến mới của ph−ơng án theo (3.6). Một biến thứ i nào đó phải thoả mãn ph−ơng trình: ( 0 ) ( 0 ) (0) xi xi − λ yi = 0 từ đó λ = ( 0 ) (3.8) yi ( 0 ) (0) còn đối với các biến j ≠ i thì: x j − λ y j > 0 (3.9) Từ đó suy ra phải loại trừ biến nào ứng với λ > 0 và nhỏ nhất: 15
17. ( 0 ) xi 0 0 nh−ng ng−ời ta giả thiết tồn tại cả những biến “có hại” tức là hệ số c1 0, x2 > 0, x3 = x4 = 0: (x1, x2, 0, 0) 2. Tìm nghiệm xuất phát: thay biến cơ sở vào ph−ơng trình ràng buộc: ⎧x1 − x2 = 100 ⎨ ⎩2x1 + 3x2 = 800 (0) (0) giải đ−ợc: x1 = 220; x2 = 120 do đó nghiệm xuất phát là: (220, 120, 0, 0) và Z0 = 220 + 2x120 = 460 3. Thử đ−a x3 vào cơ sở: Ph−ơng trình ràng buộc: ⎧x1 − x2 +7 x3 = 100 ⎨ ⎩2x1 + 3x2 − x3 = 800 Đó là hệ ph−ơng trình phụ thuộc, nên hệ số của cột thứ ba phụ thuộc vào cột 1 và cột 2 với hệ số yi: ⎧y − y = 7 ⎨ 1 2 ⎩2y1 + 3y2 = −1 (0) (0) giải đ−ợc y1 = 4 ; y 2 = −3 (0) (0) ( 0 ) ( 0 ) Tính hiệu suất của x3: γ3 = c1 y1 + c2 y2 = y1 + 2y2 = −2 Hiệu xuất c3 - γ3 = -3 + 2 < 0 nên ∆Z1 = λ(c3 - γ3) = λ(-3 + 2) < 0 Nh− vậy nếu đ−a x3 vào cơ sở thì ph−ơng án xấu hơn ph−ơng án xuất phát. 16
18. 4. Thử đ−a x4 vào cơ sở: Ràng buộc: ⎧x1 − x2 + x4 = 100 ⎨ ⎩2x1 +3x2 +10x4 = 800 từ đó: ⎧y1 − y2 = 1 (0) (0) ⎨ → y1 = 2,6 ; y2 =1,6 ⎩2y1 + 3y2 = 10 Tính hiệu suất của x4: (0) (0) γ4 = c1 y1 +c2 y2 =2,6+2.1,6=5,8 Hiệu suất: (c4 - γ4) = 4 - 5,8 < 0 → ∆Z2 = λ(c4 - γ4) < 0 do đó nếu đ−a x4 vào cơ sở thì sẽ có ph−ơng án xấu hơn. Nh− vậy nghiệm tối −u chính là nghiệm xuất phát: * * * T T x = [x1 , x2 ,0,0] = [220,120,0,0] Hàm mục tiêu: Z* = 220 + 2.120 = 460 3.4.4. Ph−ơng pháp lập bảng: Dùng phép xoay (Pivotage) của đại số tuyến tính. Ví dụ: Tìm (x1, x2, x3, x4) sao cho hàm mục tiêu: Z = 500x1 + 300x2 + 200x3 + 280x4 → Max Các ràng buộc: ⎧10x1 + 5x2 + 4x3 + 2x4 ≤ 2000 ⎪ ⎨8x1 + 5x2 + 1,2x3 + 5,6x4 ≤ 1800 ⎪ ⎩5x1 + 8x2 + 2,5x5 + 10x4 ≤ 2000 Giải: Biến đổi về dạng chính tắc ⎧10x1 + 5x2 + 4x3 + 2x 4 + x5 = 2000 ⎪ ⎨8x1 + 5x2 + 1,2x 3 + 5,6x 4 + x 6 = 1800 ⎪ ⎩5x1 + 8x2 + 2,5x 5 +10x 4 + x 7 = 2000 Z - 500x1 - 300x2 - 200x3 - 280x4 + 0x5 + 0x6 + 0x7 = 0 Lập bảng 1: Chọn một biến khác để đ−a vào cơ sở: Bảng 1. s (cột xoay) Biến cơ x1 x2 x3 x4 x5 x6 x7 sở r→ x5 10 5 4 2 1 0 0 2000 (dòng xoay) ars x6 8 5 1,2 5,6 0 1 0 1800 x7 5 8 2,5 10 0 0 1 2000 ais Z -500 -300 -200 -280 0 0 0 0 Trên dòng Z, chọn một cột nào có giá trị < 0 và trị số lớn nhất, gọi là cột s (cột xoay). 17
19. 2000 1800 2000 Xét các tỷ số: = 200; = 225; = 400 dòng nào có tỷ số nhỏ nhất gọi là 10 8 5 dòng r (dòng xoay). ars = 10: gọi là phần tử xoay (pivot). Lập bảng 2: Đ−a biến x1 vào cơ sở thay cho x5. Tạo dòng chính: chia dòng r ở bảng I cho pivot ars Các yếu tố của các dòng khác đ−ợc tính theo công thức: aij(mới) = aij(cũ) - ais.arj, có nghĩa: yếu tố dòng mới = yếu tố dòng cũ - ais*yếu tố dòng chính (ứng với phần tử cần tìm) Ví dụ ở bảng 2: dòng chính là dòng chứa x1. Các phần tử của dòng 2 là: 0 = 8 - 8x1; 1 = 5 - 8 x 0,5; - 2 = 1,2 - 8x0,4 Bảng 2. Biến cơ x1 x2 x3 x4 x5 x6 x7 sở dòng chính x1 1 0,5 0,4 0,2 0,1 0 0 200 x6 0 1 -2 4 -0,8 1 0 200 x7 0 5,5 0,5 9 -0,5 0 1 1000 Z 0 -50 0 -180 50 0 0 100000 Lập bảng 3: Bảng 3. Biến cơ x1 x2 x3 x4 x5 x6 x7 sở x1 1 0,45 0,5 0 0,14 0,05 0 190 dòng chính x4 0 0,25 -0,5 1 -0,2 0,25 0 50 x7 0 3,25 5 0 -1,3 2,25 1 550 Z 0 -5 -90 0 1,4 4,5 0 109000 Lập bảng 4: Bảng 4. Biến cơ x1 x2 x3 x4 x5 x6 x7 sở x1 1 1,125 0 0 0,001 0,175 0,1 135 x4 0 0,575 0 1 -0,07 0,025 0,1 105 dòng chính x3 0 0,65 1 0 -0,26 0,45 0,2 110 Z 0 53,3 0 0 37,4 4,5 18 118900 ở bảng 4, các hệ số của Z đều ≥ 0, do đó dừng và không cần phải tiến hành bảng 5. Biến cơ sở là tối −u, các biến khác có giá trị 0, do đó: T T x* = [x1, x4, x3 ] = [135, 105, 110 ] ; Z* = 500x135 + 200x110 + 280x250 = 118900. 3.5. Thuật toán đơn hình giải bài toán tối −u tuyến tính tổng quát 3.5.1. Phát biểu bài toán: Hàm mục tiêu: 18
20. f (x) = ∑ci x j → Min; j = 1,2, ,n. j Các ràng buộc: ∑ aij x j ≤ bi ; i = 1,2, ,m1 . j ∑ aij x j ≥ bi ; i = m1 + 1,m1 + 2, ,m1 + m2 . j ∑ aij x j = bi ; i = m1 + m2 + 1,m1 + m2 + 2, m j xj ≥ 0 ; bi ≥ 0 ; i = 1,2 , , m. 3.5.2. Biến đổi các ràng buộc và hàm mục tiêu: Đối với các ràng buộc: ∑aijxj ≤ bi ta phải thêm biến bù xn+i ≥ 0 Đối với các ràng buộc: ∑aijxj = bi ta phải thêm biến giả tạo xn+i ≥ 0 Đối với các ràng buộc: ∑aijxj ≥ bi ta phải thêm biến giả tạo rồi biến bù. Biến bù ứng với ràng buộc: ≤ đ−ợc đánh từ số n+1 đến n+m1; các biến giả tạo ứng với ràng buộc ≥ và = đ−ợc đánh số từ n+m1+1 đến n+m; các biến bù ứng với ràng buộc ≥ đ−ợc đánh số từ n+m+1 đến n+m+m2. Trong hàm mục tiêu, các hệ số ứng với biến bù xj là cj = 0, các hệ số ứng với biến giả tạo xj là cj > 0 đủ lớn, có thể chọn cj = M = max {|aij,|bi,|cj|}. Ví dụ: Tìm (x1, x2) sao cho hàm mục tiêu: Z = 30x1 + 45x2 → Max Các ràng buộc: 1) x1 ≤ 6000 2) x2 ≤ 4000 3) 2,5x1 + 2x2 ≤ 24000 4) x1 ≥ 1000 5) x2 ≥ 1000 6) 3x1 - x2 ≥ 0 7) 2,5x1 + 2x2 ≥ 10000 Giải: Trong thuật toán, ta đ−a bài toán về dạng chính tắc bằng cách thêm các biến bù x3, x4, x5; các biến giả tạo x6, x7, x8 ,x9 và các biến bù x10, x12, x13. Các ràng buộc: 1) x1 + x3 = 6000 2) x2 +x4 = 4000 3) 2,5x1+2x2 +x5 = 24000 4) x1 -x6 +x10 = 1000 5) x2 -x7 +x11 = 1000 6) 3x1 - x2 -x8 +x12 = 0 7) 2,5x1+2x2 -x9 +x13 = 10000 Hàm mục tiêu: Z = 30x1+45x2+0x3+0x4+0x5-Mx6-Mx7 = Mx8-Mx9+0x10+0x1+0x12+0x13 chọn M ≥ 24000. Sau khi giải bài toán chính tắc ta đ−ợc: x1=6000, x2=4000, x5=1000, x10=5000, x11=3000, x12=14000, x13=13000, Z=360000. 19
21. Nh− vậy nghiệm tối −u của bài toán là: * * x1 = 6000; x 2 = 4000 * * * Z = 30x 1 + 45x 2 = 360000. Bài tập 1. 2. ⎧2x1 + x2 + x3 - x4 = 6 ⎧ x1 + x2 ≤ 18 ⎪ ⎪ ⎪ 3 ⎪0,5x1 + x2 ≤ 12 ⎪ x1 + x2 + x3 - x4 = 8 ⎨ ⎨ 2 0 ≤ x ≤ 12 ⎪ 1 ⎪3x + 4x + 2x - x = 12 ⎪ ⎪ 1 2 3 6 ⎩0 ≤ x2 ≤ 9 ⎩⎪x1 ≥ 0; i = 1,2, ,6 5 Z = 4x + 6x → max Z = 2x + 3x + x → min 1 2 1 2 2 10 8 28 2 Trả lời : x* = [12 ; 6]T ; Z* = 84 Trả lời : x* = [0; ; ; 0; 0; ]T Z* = 12 3 9 9 ; 9 3. 4. ⎧x1 + x2 − 3x4 _ + 2x6 = 5 ⎧1000 ≤ x1 ≤ 6000 ⎪ ⎪ ⎪ 2x2 − 3x3 + x4 + x5 = 4 ⎪1000 ≤ x2 ≤ 4000 ⎨ ⎨ ⎪− 3x1 − x2 + 2x3 - x5 = - 3 ⎪10000 ≤ 2,5x1 + 2x2 ≤ 24000 ⎪ ⎪ ⎩x I ≥ 0; i = 1,2, ,6 ⎩ 3x1 − x2 ≥ 0 Z = 2x1 - 3x4 + x5 + 2x6 → min Z = 30x1 + 45x2 → max Trả lời : không có nghiệm tối −u. Trả lời : x* = [6000,4000]T Z* = 360000. 20
22. Ch−ơng 4: Bài toán tối −u hóa nguyên tuyến tính 4.1. Bài toán tối −u nguyên tuyến tính Trong các bài toán đã xét ở ch−ơng 2, các biến có thể nhận các giá trị thực không âm. Trong thực tế th−ờng gặp nhiều bài toán ở đó các biến số chỉ có thể nhận một số hữu hạn hay đếm đ−ợc giá trị, th−ờng là các giá trị nguyên. Ví dụ, thực là không đúng nếu cần thuê 2,3 ng−ời thợ. Vì thế trong ch−ơng này đề cập đến các bài toán có các biến nguyên hay trên các tập rời rạc. bài toán có dạng sau: Tìm cực tiểu của hàm f(x,y) phụ thuộc vào 2 nhóm biến x và y với các ràng buộc có dạng: gi(x,y) ≤ 0, i =1,2, ,m; x, y ∈ D. Trong đó x = (x1, x2, , xp), y = (y1, y2, , yq), p >0 và q ≥ 0. D là tập hợp hữu hạn các vectơ; f, gi là những hàm cho tr−ớc của p+q = n biến số. Khi f, gi là các hàm tuyến tính và D là tập hợp các điểm nguyên thì ta có bài toán nguyên tuyến tính, còn nếu D là tập các vectơ p thành phần 0 hay 1 thì ta có bài toán nguyên 0 - 1 hay còn gọi là biến binary. Ta thấy bất kỳ bài toán với các biến số chỉ nhận một số hữu hạn các giá trịcho tr−ớc, đều có thể quy đ−ợc về bài toán trong đó các biến chỉ nhận các giá trị nguyên. Ví dụ, biến x biểu thị công suất của một nhà máy điện cần đ−ợc xây dựng chỉ có thể lấy đ−ợc một trong các giá trị cho sẵn N1, N2, , Nk. Khi đó bằng cách đặt: x = u1N1 + u2N2 + + ukNk, với u1 + u2 + + uk = 1, uj ∈ {0, 1}, j = 1, 2, , k Nh− vậy biến rời rạc x có thể đ−ợc thay thế bởi biến uj chỉ nhận giá trị 0 hay 1. T−ơng tự, nếu bất kỳ bài toán với các biến nguyên bị chặn tùy ý, đều có thể quy về bài toán với các biến 0 - 1. Điều này cho thấy bài toán có biến 0 - 1 giữ vai trò quan trọng trong bài toán tối −u với các biến rời rạc. 4.2. Một số mô hình thực tiễn 1. Bài toán cắt vật liệu: Trong thực tế ta th−ờng cắt những vật liệu có độ dài có sẵn nh− thanh thép, ống n−ớc, thành những đoạn ngắn hơn với số l−ợng nhất định để cho công việc tiếp theo. Vấn đề đặt ra là nên cắt thế nào để cho ít tốn vật liệu nhất. Ví dụ: Một phân x−ởng cơ khí có những thanh thép dài 6m, cần cắt thành 30 đoạn dài 2,5m và 50 đoạn dài 1,6m, nên cắt nh− thế nào cho tiết kiệm. Có 3 mẫu cắt nh− sau: Mẫu 1: 2 đoạn 2,5m còn thừa 1m Mẫu 2: 1 đoạn 2,5m và 2 đoạn 1,6m, còn thừa 0,3m Mẫu 3: 3 đoạn 1,6m, còn thừa 1,2m. Gọi x1, x2, x3 lần l−ợt là số thanh cần cắt theo mẫu 1, 2 và 3, ta có bài toán: x1 + 0,3x2 + 1,2x3 Min Thỏa mãn các ràng buộc: 2x1 + x2 = 30 2x2 + x3 = 50 xi≥ 0 và nguyên với i = 1, 2, 3. Tổng quát ta ký hiệu: aij là số đoạn loại i thu đ−ợc khi cắt theo mẫu j bi là số đoạn loại i cần có cj là rẻo thừa khi cắt theo mẫu j xj là số thanh cắt theo mẫu j. Ta có mô hình của bài toán nh− sau: n Z= ∑c j x j → Min , (4.1) j=1 21
23. Thỏa mãn các ràng buộc: n ∑ aij x j = bi, i = 1, 2, , n (4.2) j=i xij ≥ 0 và nguyên, j = 1, 2, , n. 2. Bài toán lập thứ tự gia công các chi tiết máy: Giả sử cần gia công n. trên m, mỗi chi tiết đều đ−ợc gia công trên các máy theo thứ tự: 1, 2, , m. Cho biết thời gian gia công chi tiết tứ j trên máy thứ i là tij. Bài toán đặt ra là lập thứ tự gia công các chi tiết trên các máy để thời gian gia công các chi tiết là ngắn nhất với điều kiện các chi tiết đ−ợc gia công liên tục, không có khoảng thời gian gián đoạn khi chuyển từ máy này sang máy khác. Sau đây ta xét bài toán Sau đây ta xét bài toán: có n chi tiết gia công trên hai máy A và B (giả sử gia công trên A tr−ớc rồi tới B). Mỗi máy chỉ có thể gia công từng chi tiết một. Cho biết thời gian gia công chi tiết j trên máy A là aj và trên máy B là bj. Tìm thứ tự gia công các chi tiết để việc gia công tất cả các chi tiết trên 2 máy là ngắn nhất. Mỗi một thứ tự gia công sẽ t−ơng ứng với một hoán vị π = (s1, s2, , sn) của n số tự nhiên 1, 2, , n. Ký hiệu P là tập hợp tất cả các hoán vị của {1, 2, , n}. Thời gian gia công theo thứ tự π bằng: n n t(π) = x + b (4.3) ∑ s j ∑ j j=1 j=1 Trong đó x là thời gian máy B chờ kể từ khi máy B gia công xong chi tiết tr−ớc đó s j để gia công chi tiết thứ j, vì chi tiết này còn đang gia công trên máy A. Ký hiệu tổng thứ nhất trong (4.3) là tB(π) là tổng thời gian chờ của máy B. Tổng thứ 2 trong (4.3) là hằng số đối với mọi thứ tự π. Đây là bài toán tối −u rời rạc: tìm hoán vị π để tổng tB(π) đạt cực tiểu: Min{ tB(π): π∈ P}. Để giải bài toán này ta có thể dùng thuật toán Johnson với định lý sau: Dịnh lý Johnson: tB(π) đạt giá trị nhỏ nhất khi thứ tự gia công π = (s1, s2, , sn) thỏa mãn: Min( a ,b ) ≤ Min( a ,b ) (4.4) sk sk +1 sk +1 sk +1 Với mọi k = 1, 2, , n-1. Dựa vào định lý trên ta có thuật toán để tìm thứ tự gia công theo yêu cầu: 1) Ghi lại thời gian công các chi tiết trên mỗi máy vào bảng thời gian gia công: Chi tiết 1 2 n Máy A a1 a2 an Máy B b1 b2 bn 2) Chọn số nhỏ nhất trong tất cả các số ghi ở bảng nếu số đó nằm trong hàng máy A, thì chi tiết t−ơng ứng đ−ợc xếp gia công đầu tiên; nếu số đó nằm trong hàng máy B, thì chi tiết t−ơng ứng xếp gia công sau cùng. 3) Trong bảng thời gian xóa đi cột t−ơng ứng với chi tiết đã đ−ợc sắp xếp trình tự. 4) Nếu mọi chi tiết đã đ−ợc sắp xếp trình tự thì dừng: Thứ tự sắp xếp đó là tối −u. Nếu không, thì quay lại b−ớc 2) đrre sắp xếp thứ tự cho các chi tiết còn lại. Chú ý: Tr−ờng hợp trong bảng có nhiều số dạt giá trị nhỏ nhất, ta có thể chọn một số bất kỳ trong các số đó. Tuy nhiên để xác định ta chọn số ứng với chi tiết có số thứ tự nhỏ nhất. Còn nếu số nhỏ nhất là bằng nhauthì ta sắp xếp gia công chi tiết theo máy A tr−ớc. Ví dụ: Một phân x−ởng có 2 máy A, B dùng gia công 4 chi tiết, mỗi chi tiết đều đ−ợc gia công trên 2 máy, theo thứ tự A tr−ớc b sau. Mỗi máy chỉ gia công từng chi tiết một và xong 22
24. chi tiết này mới chuyển sang chi tiết khác. Thời gian gia công (tính ra giờ) cho trong bảng sau: Chi tiết I II III IV Máy A 1 5 3 4 Máy B 2 3 2 5 Thứ tự tối −u đ−ợc xếp nh− sau: Số nhỏ nhất trong bảng là 1, nằm ở hàng máy A, nên chi tiết I đ−ợc xếp gia công đầu tiên. Bây giờ xóa đi cột chi tiết I. Nh− vậy số nhỏ nhất bây giờ là 2, nằm ở hàng máy B, nên chi tiết III đ−ợc xếp gia công sau cùng. T−ơng tự số nhỏ nhất bây giờ là 3, nằm trên hàng B, nên chi tiết II đ−ợc xếp tr−ớc chi tiết III. Còn lại là chi tiết IV. Thứ tự gia công tối −u là: I, IV, II, III. 3. Bài toán điều công-ten-nơ: Có n loại hàng đ−ợc xếp xếp lên các công-ten-nơ nh− nhau với tải trọng của mỗi công-ten-nơ là T và dung l−ơng la K. Hàng loại j có trọng l−ợng aj, thể tích bj và số l−ợng cần vận chuyển là sj (j= 1, 2, , n). Hãy tìm cách xếp tất cả số hàng này lên các công-ten-nơ sao cho sử dụng ít công-ten-nơ nhất. Giả sử số công-ten-nơ có sẵn là m, gọi xij là số hàng lọai j đ−ợc chở trên công-ten-nơ thứ i, yi là biến nhận giá trị 1 khi công-ten-nơ thứ i đ−ợc dùng, ngoài ra thì nhận giá trị 0. Bài toán đ−a đến mô hình: m Z = ∑ yi → Min i=1 Với các điều kiện: n ∑ a j xij ≤ Tyi , i = 1, 2, , m i=1 n ∑b j xij ≤ Kyi , i = 1, 2, , m i=1 m ∑ xij = s j , j =1, 2, , n i=1 yi ∈{0, 1} Bài tập 1. Một x−ởng mộc sản xuất 3 loại ghế dựa khác nhau A, B, c. Mỗi loại ghế cần trải qua các nguyên công đánh bóng, đánh màu và đánh vécni. Ngoài ra ghế loại C còn phải thêm nguyên công bọc nệm. Bảng d−ới đây cho biết thời gian cần thiết (tính theo số giờ/tháng) để thực hiện các nguyên công và tiền lãi của mỗi loại ghế. Cần sản xuất bao nhiêu ghế mỗi loại để thu đ−ợc nhiều lãi nhất. Loại ghế Bóng Màu Vécni Nệm Tiền lãi (đồng) (giờ) A 1.0 0.5 0.7 0 100.000 B 1.2 0.5 0.7 0 130.000 C 0.7 0.3 0.3 0.7 80.000 Thời gian có 600 300 300 140 Mỗi tháng 2. một x−ởng dự định mua hai loại máy để in hình lên vải. Máy A có thể in 100m/ph và chiếm 50m2 diện tích sản xuất, còn máy b có thể in 200m/ph và chiếm diện tích là 140m2. x−ởng cần in ít nhất là 600m/ph và diện tích mặt bằng tối đa là 350m2. Giá mua là 22 triệu đồng cho 1 máy loại A và máy loại B là 42 triệu đồng. Hỏi cần mua bao nhiêu máy in mỗi loại để chi phí là ít nhất. 23
25. 3. Có 2 loại sản phẩm A, B đ−ợc gia công trên 4 máy I, II, III, IV. Thời gian gia công mỗi loại sản phẩm trên từng máy nh− bảng sau: Máy I Máy II Máy III Máy IV Sản phẩm A (giờ) 2 4 3 1 Sản phẩm B (giờ) 1/4 2 1 4 Thời gian sử dụng các máy theo thứ tự 45, 100, 300, 50 giờ. Một đơn vị sản phẩm A lãi 600 đồng, còn sản phẩm B là 400 đồng. Nên sản xuất mỗi loại bao nhiêu để lãi tối đa. 4. Một Công ty lọc dầu sử dụng ngay nguồn dầu thô nặng có giá 300 đồng/lít và dầu thô nhẹ có giá 350đồng/lít. Công ty sản xuất 3 loại sản phẩm Gasoline, Heating Oil và Jet Fuel và l−ợng 3 loại dầu trên có đ−ợc từ việc lấy từ 1 lita dầu thô nặng và nhẹ cho ở bảng sau: Gasoline Heating oil Jet Fuel Dầu thô nặng 0.3 0.2 0.3 Dầu thô nhẹ 0.3 0.4 0.2 Công ty thực hiện hợp đồng cung cấp 90m3 Gasoline, 80m3 Heating oil, 50m3 Jet Fuel. Công ty cần mua bao nhiêu lít dầu thô nặng, nhẹ để chi phí là ít nhất. 24
26. Ch−ơng 5: bài toán tối −u động Tối −u động đ−ợc dùng một cách có hiệu quả để giải một số loại bài toán tối −u phi tuyến. Nó xuất hiện trong kết quả khi nghiên cứu các bài toán, ở đó có sự thay đổi theo thời gian. Về sau công cụ này đã đ−ợc phát triển để giải các bài toán không liên quan đến sự thay đổi theo thời gian. Ta hiểu tối −u động là ph−ơng pháp tính dựa trên công cụ các công thức truy hồi, nó đã đ−ợc nghiên cứu khá kỹ l−ỡng trong các công trình của R. Bellman. 5.1. Bản chất của bài toán tối −u động Để làm sáng tỏ các t− t−ởng cơ bản của tối −u động ta sử dụng bài toán tối −u trong quá trình phân phối tài nguyên. Giả sử ta có số l−ợng hạn chế các tài nguyên nào đó. Có thể hiểu là máy móc, tiền, sức lao động, Những tài nguyên hiện có có thể đ−ợc sử dụng trong nhiều ph−ơng pháp sản xuất khác nhau. Kết quả của việc sử dụng tất cả hoặc một phần tài nguyên đó trong một ph−ơng pháp sản xuất nào đó là một khoản thu nhập, mà khối l−ợng của nó vừa phụ thuộc vào số l−ợng tài nguyên đ−ợc sử dụng vừa phụ thuộc vào ph−ơng pháp sản xuất đ−ợc chọn. Bài toán của ta là phân phối những tài nguyên hiện có nh− thế nào để tổng thu nhập lớn nhất. Tr−ớc khi phát biểu chính xác về mặt toán học bài toán này, ta đ−a ra các giả thiết sau để đơn giản bài toán: 1. Thu nhập của một ph−ơng pháp bất kỳ chỉ phụ thuộc vào số l−ợng tài nguyên dành cho nó chứ không phụ thuộc vào số l−ợng tài nguyên dành cho những ph−ơng pháp khác. 2. Các thu nhập của những ph−ơng pháp khác nhau đều tính theo một loại đơn vị. 3. Thu nhập chung là tổng số các thu nhập của từng ph−ơng pháp riêng biệt. Bây giờ bài toán của chúng ta có thể phát biểu theo ngôn ngữ toán học nh− sau: có N ph−ơng pháp sản xuất khác nhau, ứng với mỗi ph−ơng pháp có một hàm số xác định khối l−ợng thu nhập phụ thuộc vào số l−ợng tài nguyên dành cho ph−ơng pháp đó, tức là nếu đặt yi là số l−ợng tài nguyên dành cho ph−ơng pháp sản xuất i thì giả thiết (1), gi(yi) cho ta khối l−ợng thu nhập từ ph−ơng pháp sản xuất i. Theo giả thiết (2) và (3) thu nhập chung D(y1, y2, , yn) có thể viết d−ới dạng: D(y1, y2, , yn) = g1(y1) + g2(y2) + + gN(yN) (5.1) Ký hiệu y là số l−ợng tài nguyên hiện có, ta đi đến bài toán Max sau: Cần làm Max hàm mục tiêu D(y1, y2, , yN) với điều kiện sau: y1 + y2 + + yN = y (5.2) Trong đó hiển nhiên là tất cả yi không âm, tức là yi ≥ 0 (i = 1, 2, N). Nh− chúng ta đã biết, công cụ cổ điển của giải tích toán học không có hiệu lực ngay cả trong tr−ờng hợp tất cả các hàm gi(yi) tuyến tính (trong tr−ờng hợp tuyến tính ta đi đến bài toán tối −u tuyến tính). Để tìm cực trị có điều kiện, theo các ph−ơng pháp cổ điển, cần phải lựa chọn và so sánh các giá trị của hàm đ−ợc làm tối −u trên biên của miền xác định. Đối với tuyệt đại đa số các bài toán, việc đó không thể làm đ−ợc ngay cả khi có sự giúp đỡ của những máy tính điện tử hoạt động nhanh nhất. Vì thế ta cố gắng đi đến lời giải bài toán theo h−ớng khác. 25
27. Thay vào một bài toán với các số liệu cụ thể cho tr−ớc N và y ta sẽ xét tập hợp những bài toán loại nh− vậy, trong đó số l−ợng ph−ơng pháp sản xuất và tài nguyên hiện có có thể thay đổi. Tiếp theo, ta nhận thấy giá trị lớn nhất của thu nhập chung chỉ phụ thuộc vào số ph−ơng pháp và tài nguyên hiện có vì thế, ta đ−a vào xét hàm fn(x) xác định thu nhập tối −u nhận đ−ợc khi phân phối x tài nguyên theo n ph−ơng pháp sản xuất. Dễ dàng tìm công thức truy hồi giữa fn(x) và fn-1(x) với n và x bất kỳ. Thật vậy, giả sử xn ∈ [0, x] là số l−ợng tài nguyên dành cho ph−ơng pháp sản xuất thứ n. Khi đó số l−ợng tài nguyên còn lại x - xn sẽ đ−ợc sử dụng nh− thế nào để thu nhập từ (n - 1) ph−ơng pháp còn lại là lớn nhất. Theo định nghĩa của hàm fn(x) thu nhập tối −u này sẽ bằng fn-1(x - xn). Từ đó thu nhập chung từ n ph−ơng pháp sẽ bằng: gn(xn) + fn-1(x - xn) (5.3) Bây giờ phải hiểu là xn cần chọn nh− thế nào đó để làm lớn nhất hàm (5.3). Nh− vậy ta đ−ợc công thức truy hồi cơ bản fn(x) = Max{gn(x) + fn-1(x - xn) (5.4) 0 ≤ xn ≤ x với n = 1, 2, , N và với mọi x ≥ 0. Trong đó hiển nhiên là fo(x) ≡ 0, tức là khi không có ph−ơng pháp sản xuất thì thu nhập lớn nhất bằng không. Công thức (5.4) cho phép lập dãy hàm {fn(x)} xác định thu nhập từ n ph−ơng pháp và dãy {xn(x)} là phân phối tối −u. Nh− vậy, việc giải bài toán này dẫn đến việc lập bảng các dãy hàm này. Và ta thu ngay đ−ợc nghiệm của bài toán ban đầu chỉ khi lập xong bảng đó. Chính phân phối tối −u khi cho tr−ớc N và y bây giờ đ−ợc xác định theo các công thức sau: y1 = xN(y); y2 = xn-1(y - y1); . . . . . yN = x1(y - y1 - - yN-1); còn thu nhập lớn nhất sẽ bằng yN(y). Việc lập bằng số cụ thể dãy các hàm xác định bởi công thức truy hồi (5.4) sẽ đ−ợc xét ở d−ới đây. Bây giờ ta chỉ l−u ý một điều là trong cách giải quyết mới, bài toán ban đầu trở thành một tr−ờng hợp riêng của tập hợp những bài toán t−ơng tự với nó. Nh− vậy ta đã thay việc giải bài toán tìm cực trị N chiều của hàm (5.1) với điều kiện (5.2) bằng việc giải liên tiếp N bài toán một chiều (5.4). T− t−ởng xét bài toán cụ thể bất kỳ nh− là đại diện của một lớp các bài toán t−ơng tự với nó này chính là cơ sở của tối −u động. Cách giải quyết nh− vậy cho phép ta thay bài toán tìm cực trị nhiều chiều đã cho bằng cách tính các công thức truy hồi gồm những hàm có số biến ít hơn nhiều nhờ việc ghép bài toán riêng biệt của ta vào lớp những bài toán giống nó. Trong những mục cuối chúng ta sẽ xét một loạt bài toán và chỉ ra việc sử dụng các t− t−ởng của tối −u động để giải chúng. 5.2. Qúa trình phân phối nhiều b−ớc các tài nguyên Chúng ta sẽ xét quá trình trong đó mỗi thời điểm ta phải thông qua quyết định làm biến đổi hệ thống vật lý (kinh tế, sản xuất, ) nào đấy. Ta sẽ gọi quá trình thông qua quyết định liên tiếp nh− thế là quá trình giải nhiều b−ớc. Để có một ví dụ đơn giản, nh−ng lại quan trọng, về quá trình giải nhiều b−ớc, ta xét quá trình phân bố tài nguyên. 26
28. Giả sử ta có tài nguyên x nào đó mà sau khi chia nó thành hai phần không âm y và x- y ta nhận đ−ợc thu nhập t−ơng ứng với phần thứ nhất và thứ hai là g(y) và h(x - y). ý muốn làm max tổng thu nhập đ−a ta đến bài toán xác định max của hàm: D1(x, y) = g(y) + h(x - y) (5.5) với mọi y ∈ [0, x] Tiếp theo, ta giả thiết số l−ợng ban đầu y giảm xuống đến ay, trong đó a là hằng số nằm giữa 0 và 1. Điều đó có thể xảy ra, chẳng hạn, do các chi phí cần thiết để có khoản thu nhập g(y). Giả sử số l−ợng x - y t−ơng tự cũng giảm xuống đến b(x - y), trong đó b ∈ [0, 1]. Sau đó ta lặp lại quá trình phân phối với tổng số phần còn lại ay + b(x - y), ở đây ta đặt: ay + b(x - y) = x1 = y1 + (x1 - y1) (5.6) trong đó 0 ≤ y1 ≤ x1. Trong kết quả của phân phối mới, ở b−ớc thứ hai thu nhập chung sẽ bằng g(y1) + h(x1 - y1). Thu nhập toàn bộ từ quá trình cả hai b−ớc sẽ bằng: D2(x, y, y1) = g(y) + h(x - y) + g(y1) + h(x1 - y1) (5.7) Khi làm max hàm số này trong miền hai chiều 0 ≤ y ≤ x; 0 ≤ y1 ≤ x1; (5.8) trong đó x1 đ−ợc xác định theo công thức (5.6), ta đ−ợc tổng thu nhập lớn nhất sau hai b−ớc. Lặp lại quá trình phân phối nói ở trên liên tiếp N lần, ta đi đến quá trình N b−ớc. Trong tr−ờng hợp này, thu nhập toàn bộ sau quá trình N b−ớc sẽ bằng: DN(x, y, y1, , yN-1) = g(y) + h(x - y) + g(y1) + h(x1 - y1) + + + g(yN-1) + h(xN-1 - yN-1). (5.9) trong đó xi là giá trị thuộc phân phối tiếp sau b−ớc thứ i (i = 1, 2, , N - 1) Tất cả xi, yi thỏa mãn các biểu thức: x1 = ay + b (x - y), 0 ≤ y ≤ x x2 = ay1 + b (x1 - y1), 0 ≤ y1 ≤ x1 . . . . . . . . (5.10) xN-1 = ayN-2 + b(xN-2 - yN-2), 0 ≤ yN-2 ≤ xN-2) 0 ≤ yN-1 ≤ xN-1 Ta sẽ có thu nhập toàn bộ lớn nhất sau quá trình N b−ớc trong kết quả của việc làm max hàm DN trên miền N chiều của không gian các biến y, y1, , yN-1 đ−ợc xác định bởi các công thức (5.10). Tuân theo t− t−ởng của tối −u động, ta đ−a vào xét hàm fn(z) cho thu nhập lớn nhất sau quá trình n b−ớc bắt đầu từ giá trị z, tức là fn(z) = Max Dn(z, y, y1, , yn-1); (n = 2, 3, , N) {y, y1} trong đó rõ ràng là: f1(z) = max {g(y) + h(z - y)} (5.11) 0 ≤ y ≤ z 27
29. Để thu đ−ợc công thức truy hồi cơ bản liên hệ giữa fn(z) và fn-1(z) ta sử dụng thủ thuật đã làm ở 5.1. Ta sẽ xét quá trình n b−ớc. Giả sử y là phân phối nào đó ở b−ớc thứ nhất. Khi đó thu nhập chung sau quá trình n b−ớc sẽ bằng: g(y) + h(z - y) + fn-1{ay + b(z - y)} làm max tổng này theo y, theo định nghĩa ta sẽ đ−ợc fn(z), tức là: fn(z) = max {g(y) + h(z - y) + fn-1 [ay + b(z - y)]} (5.12) 0 ≤ y ≤ z với n = 2, 3, , N, còn f1(z) đ−ợc xác định theo công thức (5.11). Lại nh− trong 5.1, việc giải bài toán ban đầu đ−ợc đ−a về việc lập bảng các hàm {yn(z)} và {yn(z)} với z ≥ 0 và n = 1, 2, , N. Nghiệm của bài toán với N và x cho tr−ớc có dạng: o y = yN(x) o o o y1 = yN-1 [ay + b(x - y )] o o o y2 = yN-2 [ay1 + b(x1 - y1 )] (5.13) . . . . . . . . o o o yN−1 = y1[ayN−2 + b(x N−2 − yN−2 )] o o o tức là bộ (y , y1 , , yN−1) làm max thu nhập toàn bộ sau quá trình N b−ớc bắt đầu từ số l−ợng x. Trong bài toán này ta đã giả thiết rằng thu nhập ở mỗi b−ớc chỉ phụ thuộc vào phân phối tài nguyên mà không phụ thuộc vào thu nhận đ−ợc tính ở b−ớc nào. Bây giờ ta sẽ xét tình huống tổng quát hơn. Giả sử số l−ợng x trong khi phân phối y ở b−ớc thứ k chuyển thành dk (x, y) thuộc quá trình phân phối tiếp theo, còn thu nhập ở b−ớc này khi đó sẽ bằng ϕk (x, y). Theo các điều kiện của bài toán trên ta có: dk (x, y) = ay + b (x - y) ϕk (x, y) = g(y) + h (x - y) tức là kết quả chấp nhận đ−ợc của lời giải trên từng b−ớc không phụ thuộc vào số thứ tự của b−ớc. Đối với các hàm dk(x, y), tất nhiên, nên giả thiết chúng thỏa mãn hàm các bất đẳng thức 0 ≤ dk(x, y) ≤ γx, trong đó γ < 1 còn k = 1, 2, , N. Cũng nh− trên, ta xác định cho tất cả k = 1, 2, , N hàm fk(x) nh− là thu nhập toàn bộ có đ−ợc sau quá trình bắt đầu từ đại l−ợng x ở b−ớc thứ k và kết thúc ở b−ớc N, nếu giữ nguyên tình trạng tối −u (1). Rõ ràng là: fN(x) = max ϕN(x, y); 0 ≤ y ≤ x còn các hàm fk(x) và fk+1(x) liên hệ với nhau bởi công thức truy hồi: fk(x) = Max{ϕk(x, y) + fk+1 [dk(x, y)]} 0 ≤ y ≤ x; (k = 1, 2, , N - 1) (5.14) Trong tr−ờng hợp này việc giải bài toán cực trị lại đ−ợc đ−a về việc xây dựng các hàm fk(x) thỏa mãn công thức truy hồi (5.14) và các hàm yk(x), trong đó giá trị max đạt ở (5.14). Sau khi xây dựng các hàm này, việc viết nghiệm của bài toán ban đầu t−ơng tự nh− các công thức (5.13) không khó khăn gì. 28
30. Có thể sử dụng ph−ơng pháp công thức truy hồi trong cả những bài toán tổng quát hơn và gần với tình huống thực tế hơn. Chẳng hạn trong bài toán phân phối nhiều b−ớc với một số loại tài nguyên mà ở mỗi b−ớc, tại thời điểm nào đó, tài nguyên đ−ợc phân phối giữa các ph−ơng pháp sản xuất khác nhau, mục đích của quá trình nhiều b−ớc là làm max hàm thành phẩm đã cho. Ta sẽ không dừng lại ở việc đặt vấn đề chính xác và giải bài toán này, bởi vì ứng dụng cách giải miêu tả ở trên không khó khăn gì. Tất cả các quá trình phân phối nhiều b−ớc đ−ợc xét ở trên đều đ−ợc đặc tr−ng bởi một điều là: kết quả của bất kỳ nghiệm đ−ợc chấp nhận xác định một cách đơn trị bởi nghiệm đó. Những quá trình loại nh− vậy th−ờng đ−ợc gọi là quá trình tiền định. Tuy nhiên trong một loạt các tình huống thực tế, điều đáng chú ý là không thể chỉ ra một cách đơn trị kết quả của nghiệm đ−ợc chấp nhận, mà chỉ có thể nói về xác xuất xuất hiện của kết quả này hoặc kết quả khác. Những quá trình loại đó ng−ời ta quen gọi là những quá trình ngẫu nhiên. Khi nghiên cứu các quá trình giải ngẫu nhiên và khi giải những bài toán liên quan đến chúng, khó khăn cơ bản là việc xác định thế nào là hình trạng tối −u trong các điều kiện kết quả của nó không xác định. Có nhiều cách giải quyết khó khăn này, ta dừng lại một trong những cách đó. T− t−ởng chung của cách này là sử dụng các đặc tr−ng trung bình của những kết quả có thể có, hoặc nói cách khác, là kỳ vọng toán học của các kết quả của việc thông qua các quyết định. Để làm ví dụ quá trình thông qua quyết định ngẫu nhiên ta lấy tr−ờng hợp miêu tả ở đầu mục này và đ−a vào đó các đại l−ợng đặc tr−ng xác xuất. Giả sử trong kết quả phân chia số l−ợng x thành y và x - y với xác suất p sẽ đ−ợc thu nhập g1(y) + h1(x - y), còn lại để phân phối a1y + b1(x - y) và với xác suất q = 1 - p thu nhập sẽ bằng g2(y) + h2(x - y) và còn lại để phân phối là a2y + b2(x - y). Cũng nh− tr−ớc kia cần phải tổ chức quá trình phân phối (đ−ợc lặp lại N lần) nh− thế nào để làm cực đại kỳ vọng toán học của tổng thu nhập từ quá trình ngẫu nhiên N b−ớc. Để làm điều này ta xét hàm fn(x) là kỳ vọng toán học của toàn phần từ quá trình n b−ớc bắt đầu với số l−ợng đã cho x, nếu giữ nguyên nghĩa hình dạng tối −u. Việc lập công thức truy hồi, trong tr−ờng hợp này, về nguyên tắc không có gì khác với việc ta đã làm. Thật vậy, kỳ vọng toán học của thu nhập từ một b−ớc khi phân chia y và x - y bằng: p{g1(y) + h1(x - y)} + q{g2(y) + h2(x - y)} làm max biểu thức này theo y cho ta chính f1(x), tức là: f1(x) = max{p[g1(y) + h1(x - y)] + q[g2(y) + h2(x - y)]} (5.15) 0 ≤ y ≤ x Tiếp theo đó, xét quá trình n b−ớc ta tính đ−ợc kỳ vọng toán học của tổng thu nhập. Giả sử y là phân phối nào đó trên b−ớc thứ nhất, khi đó thu nhập chung từ quá trình n b−ớc với xác suất p sẽ bằng: g1(y) + h1(x - y) + fn-1 [a1y + b1(x - y)] và với xác suất q = 1 - p sẽ bằng: g2(y) + h2(x - y) + fn-1 [a2y + b2(x - y)] Kỳ vọng toán học của tổng thu nhập khi đó sẽ bằng p{g1(y) + h1(x - y) + fn-1 [a1y + b1(x - y)]} + + q {g2(y) + h2(x - y) + fn-1 [a2y + b2(x - y)]}, 29
31. làm max nó sẽ cho ta fn(x), nghĩa là ta đi đến công thức truy hồi sau: fn(x) = Max{p[g1(y) + h1(x - y) + fn-1[a1y + b1(x - y)]} + q{g2(y) + h2(x - y) + fn-1[a2y + b2(x - y)]}, (5.16) 0 ≤ y ≤ x trong đó n = 2, 3, , N, còn f1(x) đ−ợc xác định theo công thức (5.15). Nh− vậy việc sử dụng kỳ vọng toán học cho phép gạt bỏ những quan điểm xác suất của quá trình đang xét và nhận đ−ợc công thức truy hồi có cùng cơ cấu nh− những công thức nhận đ−ợc ở trên. Việc ta chỉ xét hai kết quả có thể có không ảnh h−ởng gì đến việc rút ra công thức truy hồi (5.16) và đặc tính của nó. Cuối cùng để kết thúc mục này ta sẽ xét bài toán thay thế thiết bị trên quan điểm quy hoạch động. Các bài toán loại đó rất đặc tr−ng cho các ngành công nghiệp khác nhau, bởi vì thiết bị trong quá trình phục vụ không những chỉ hao mòn vật lý mà còn hao mòn về giá trị. Vì vậy trong một thời gian nhất định, việc thay thế các thiết bị cũ bằng thiết bị mới là điều chính đáng, những chi phí liên quan đến việc tìm kiếm và đặt các thiết bị mới sẽ đ−ợc bù đắp bằng việc tăng năng suất lao động và giảm chi phí th−ờng ngày. Rõ ràng là thời gian thay thế thiết bị cũ bằng thiết bị mới phụ thuộc vào chi phí th−ờng ngày, các đặc tính sản xuất và sự phát triển của kỹ thuật. Vì thế ý muốn nhận đ−ợc chính sách tối −u (t− cách tối −u) của việc thay thế và hiện đại hóa thiết bị lại dẫn ta đến việc nghiên cứu quá trình giải nhiều b−ớc. Giả sử ta có một cái máy mà hàng năm cho khoản thu nhập nào đó, yêu cầu của việc chi phí hàng năm để bảo đảm nó và vào thời điểm bất kỳ có thể thay thế nó bằng máy mới liên quan đến những chi phí nhất định. Ta sẽ coi thu nhập và chi phí để bảo đảm nó phụ thuộc vào thời hạn phục vụ của máy, và chúng ta quan tâm đến quá trình kéo dài 10 năm. Khi ký hiệu rn(t) là lãi hàng năm ở năm thứ n từ máy t tuổi; vn(t) là các chi phí liên quan tới việc thay thế máy t tuổi ở năm thứ n, và khi đ−a vào xét hàm fn(x) cho giá trị tổng thu nhập của quá trình bắt đầu khi máy t tuổi, trong thời kỳ từ năm thứ n đến năm thứ 10 với chính sách thay thế tối −u trong giai đoạn đó, ta sẽ lập đ−ợc công thức truy hồi cho hàm fn(t). Lời giải cho việc thay thế hoặc giữ nguyên máy cũ đ−ợc thông qua hàng năm, tức là trong những thời điểm t = 0, 1, 2, , 9. Công việc trong năm thứ n ta có thể bắt đầu trên máy cũ và khi đó lãi tổng số trong giai đoạn còn lại sẽ bằng: 1 un (t) = rn (t) + fn +1(t +1), (5.17) hoặc mua thêm máy mới, và khi đó lãi tổng số trong giai đoạn làm việc còn lại là: 2 un (t) = rn (0) − vn (t) + fn+1(1). (5.18) Điều này dẫn ta đến công thức truy hồi sau: 1 2 fn(t) = max {un (t), un (t)} (5.19) (n = 1, 2, , 9, 10) Trong đó hiển nhiên giả thiết là hàm fn(t) với n > 10 đồng nhất bằng không, vì ta chỉ quan tâm đến giai đoạn 10 năm. 30
32. Công thức truy hồi (5.17) cho phép liên tiếp xây dựng các hàm f10(t), f9(t), , f1(t), hàm cuối cùng, tức là hàm f1(t) cho ta lãi tối −u trong cả giai đoạn 10 năm đang xét. Hơn nữa, nhờ lời giải đạt đ−ợc max ở (5.19), ta sẽ nhận đ−ợc chính sách thay thế thiết bị tối −u. Trên ví dụ cụ thể của hàm rn(t) và vn(t), cho theo bảng (5.1 và 5.2), ta sẽ chỉ ra thực tế xây dựng chúng nh− thế nào. Các giá trị của những hàm này khi t > n không cần cho việc giải nên chúng không có trong cácbảng. Bảng 5.1 Các giá trị của các hàm rn(t) t n 0 1 2 3 4 5 6 7 8 9 10 1 70 5 2 85 65 5 3 95 70 55 -5 4 100 90 60 50 -10 5 110 95 80 50 40 -10 6 115 105 80 75 45 40 -20 7 125 110 100 70 65 35 35 -20 8 135 115 100 95 65 55 35 20 -25 9 145 125 100 90 85 45 40 30 15 -35 10 150 130 115 95 85 80 30 30 30 10 -40 Việc giải bắt đầu từ việc xây dựng hàm f10(t). Trong công thức truy hồi (5.19) cho n = 10 ta đ−ợc: f10(t) = max {r10(t), r10(0) - v10(t)} (5.20) vì f11(t) ≡ 0 với mọi t. ý nghĩa kinh tế của công thức (5.20) là: để tính các giá trị của hàm f10(t), ta cần so sánh lãi ở máy cũ r10(t) với các chi phí để thay thế nó r10(0) - v10(t). Cho các giá trị của hàm r10(t) và v10(t) từ các bảng 5.1 và 5.2 vào (5.20) ta tìm đ−ợc: f10(1) = max {130, 150 - 225} = 130 Bảng 5.2 Các giá trị của các hàm vn(t) t n 0 1 2 3 4 5 6 7 8 9 10 1 200 250 2 200 220 260 3 200 220 240 270 4 210 220 240 250 280 5 220 215 240 250 255 280 6 210 215 220 250 255 260 290 31
33. 7 210 220 220 225 255 260 265 290 8 220 220 230 225 230 260 265 270 300 9 220 230 230 240 230 235 265 270 270 300 10 220 225 240 240 250 235 240 270 270 270 310 trong đó quyết định tối −u là giữ nguyên máy cũ, tức là quyết định 1: f10(2) = Max{115, 115 - 225} = 115 quyết định tối −u cũng nh− vậy, và v.v Các kết quả tính hàm f10(t) và các quyết định tối −u t−ơng ứng cho ở bảng 5.3. Bây giờ có thể xây dựng hàm f9(t). Thật vậy, trong công thức truy hồi (5.19) cho n = 9 ta đ−ợc: f9(t) = Max{τ9(t) + f10(t + 1), r9(0) - v9(t) + f10(1)} (5.21) Từ đó liên tiếp đối với các t = 1, 2, , 9 ta dựng hàm f9(t): f9(1) = Max{r9(1) + f10(2), r9(0) - v9(1) + f10(1)} = = Max{125 + 115, 145 - 230 + 130} = 240. còn quyết định tối −u sẽ là giữ nguyên máy cũ. Các kết quả tính các giá trị tiếp theo của hàm này cho ở trong bảng 5.3. Công thức truy hồi (5.19) đ−ợc sử dụng đúng nh− vậy để xây dựng các hàm còn lại, tức là f8(t), , f1(t). Số cuối cùng trong bảng 5.3, tức là f1(t) = 310 cho ta lãi tổng số mà có thể nhận đ−ợc trong hình trạng tối −u. Ta thử xem lại tổng số này gồm những gì. Lúc bắt đầu công việc ta có thể giữ nguyên máy hiện có hoặc thay thế nó bằng máy mới. Nếu ta quyết định giữ nguyên máy hiện có thì sau năm làm việc đầu tiên lãi sẽ là r1(1) = 5, còn sau tất cả các năm còn lại f2(2) = 285, tức là lãi sau cả giai đoạn kế hoạch sẽ là 285 + 5 = 290. Cũng trong thời gian đó nếu ta thay thế máy cũ với chi phí v1(1) = 250 thì thu nhập qua năm đầu tiên r1(0) = 70 cùng với thu nhập t−ơng lai f2(1) = 490 cho lãi cả trong giai đoạn kế hoạch bằng 70 + 490 - 250 = 310. Vì 310 > 290 nên hợp lý là bắt đầu công việc bằng việc mua máy mới. Tiếp theo, nh− thấy rõ từ bảng 5.3 hình trạng tối −u là giữ nguyên máy này trong vòng 4 năm cùng với việc mua máy mới tiếp theo và giữ nó đến tận cùng của quá trình. Hình trạng tối −u (ph−ơng án 1) và thu nhập t−ơng ứng cho ở bảng 5.4. Cũng trong bảng này cho quyết định tối −u khác (ph−ơng án 2) mà cần giữ nguyên nó nếu nh− trong năm đầu tiên do các Bảng 5.3 Hàm fn(t) và các quyết định tối −u t−ơng ứng Tuổi của máy t 1 2 3 4 5 6 7 8 9 10 Hàm f10(t) 130 115 95 85 80 30 30 30 10 -40 Lời giải 1 1 1 1 1 1 1 1 1 1 Hàm f9(t) 240 195 175 165 75 79 60 25 25 Lời giải 1 1 1 1 1 1 1 1 2 Hàm f8(t) 310 275 260 145 125 110 105 75 Lời giải 1 1 1 1 1 2 2 2 Hàm f7(t) 385 360 215 190 175 170 145 32
34. Lời giải 1 1 1 1 2 2 2 Hàm f6(t) 465 295 265 245 240 210 Lời giải 1 1 1 2 2 2 Hàm f5(t) 390 345 325 320 295 Lời giải 1 1 2 2 2 Hàm f4(t) 435 385 370 285 Lời giải 1 1 1 1 Hàm f3(t) 440 425 280 Lời giải 1 1 1 Hàm f2(t) 490 285 Lời giải 1 1 Hàm f1(t) 310 Lời giải 2 nguyên nhân nào đó không có điều kiện mua máy mới. Ph−ơng án giải quyết này nhận đ−ợc nh− kết quả phụ của việc phân tích từ bảng 5.3. Việc so sánh những ph−ơng án giải quyết này buộc ta phải suy nghĩ về tính hợp lý của việc chi phí với khối l−ợng 250 đơn vị trong năm đầu tiên để thu thêm đ−ợc lãi khi kết thúc giai đoạn kế hoạch là 20 đơn vị (hiệu giữa lãi tổng số theo ph−ơng án 1 và 2). Bảng 5.4 Chính sách thay thế thiết bị tối −u Lời giải tối −u Thu nhập Lời giải tối −u Thu nhập Năm (ph−ơng án 1) hàng năm (ph−ơng án 2) hàng năm 1 Mua máy mới -180 Bảo toàn máy 5 2 Bảo toàn máy 65 - 5 3 - 55 Bảo toàn máy -5 4 - 50 - -10 5 Mua máy mới -145 Mua máy mới -170 6 Bảo toàn máy 105 Bảo toàn máy 105 7 - 100 - 100 8 - 95 - 95 9 - 85 - 85 10 - 80 - 80 Tổng cộng 310 Tổng cộng 290 5.3. Cấu trúc quá trình tối −u động Đặc tr−ng và những điểm chung nhất đối với các bài toán xét ở trên là: 1. Một hệ thống nào đó đ−ợc nghiên cứu và ở từng b−ớc nó đ−ợc đặc tr−ng bởi các thông số xác định, gọi là các thông số trạng thái. 33
35. 2. ở từng b−ớc của quá trình đang nghiên cứu cần chọn quyết định này hoặc quyết định khác trong tập hợp những quyết định cho phép. 3. Kết quả của việc thông qua quyết định là việc biến đổi các thông số trạng thái. 4. Trong khi xác định những quyết định tiếp theo, những quyết định tr−ớc không đóng vai trò gì. 5. Mục đích cuối cùng của những quyết định đ−ợc thông qua là làm max hàm mục tiêu nào đó của các thông số trạng thái. Những đặc điểm này hoặc những tính chất của các bài toán đã xét cho phép tách ra phạm vi t−ơng đối rộng của những quá trình th−ờng gặp trong hoạt động thực tế. Tất cả những quá trình có những tính chất kể trên có thể chia thành các quá trình tiền định và các quá trình ngẫu nhiên. Trong các quá trình tiền định kết quả của việc thông qua quyết định (các thông số trạng thái) ở từng b−ớc đ−ợc xác định duy nhất. Còn trong các quá trình ngẫu nhiên chỉ có thể nói về xác suất xuất hiện kết quả này hoặc kết quả khác, tức là kết quả của quyết định không duy nhất, trong đó hàm phân phối những đại l−ợng ngẫu nhiên trong các quá trình ngẫu nhiên coi nh− là đã biết. Các quá trình tiền định cũng nh− các quá trình ngẫu nhiên của việc thông qua quyết định đều chia thành những quá trình liên tục và rời rạc. Các quá trình rời rạc khác với các quá trình liên tục là trong đó quyết định đ−ợc thông qua hữu hạn lần hay một số đếm đ−ợc lần. Ta sẽ xét một cách tỉ mỉ sơ đồ tổng quát của quá trình tiền định rời rạc là quá trình th−ờng gặp hơn cả trong ứng dụng kinh tế và kỹ thuật. Có một hệ thống vật lý nào đó mà trạng thái của nó đ−ợc đặc tr−ng bởi phần tử nào đó của tập hợp P. Tập hợp này ta sẽ gọi là tập hợp các trạng thái. Các phần tử của tập hợp này có thể có bản chất bất kỳ. Hệ vật lý nh− vậy có thể là hệ thống kinh tế nào đó mà trạng thái của nó đ−ợc đặc tr−ng bởi số l−ợng nào đó các tài nguyên. Khi đó các phần tử của tập hợp trạng thái sẽ là các vectơ nhiều chiều, mà chiều của chúng đ−ợc xác định bởi số l−ợng các tài nguyên đang xét. Giả sử, tiếp theo đó, hệ thống của chúng ta có thể chuyển từ trạng thái này sang trạng thái khác ở những thời điểm rời rạc t1, t2, , tN. Giả sử tại thời điểm đầu tiên hệ thống nằm ở trạng thái đ−ợc đặc tr−ng bởi thông số p1, hoặc gọn hơn, ta sẽ nói là hệ thống nằm ở trạng thái p1, trong đó tất nhiên p1 thuộc P. Trong trạng thái này quyết định đ−ợc chọn là quyết định mà kết quả của nó là việc chuyển hệ thống của ta sang trạng thái khác p2 ∈ P. Quyết định đ−ợc chọn từ tập hợp Q nào đó mà đ−ợc gọi là tập hợp những quyết định. Các phần tử của tập hợp này là bất kỳ. Việc chọn quyết định ban đầu q1 ∈ Q xác định hơn trị (vì quá trình là tiền định), phép biến đổi Aq1 cho phép tính đ−ợc trạng thái mới của hệ thống, tức là p2 = Aq1p1. Chúng ta sẽ chỉ xét những phép biến đổi chuyển những phần tử của tập hợp P vào những phần tử của chính tập hợp ấy, nghĩa là những phép biến đổi Aσ mà Aqp ∈ P với mọi p ∈ P. B−ớc thứ nhất của quá trình của chúng ta là chọn quyết định q1, với sự giúp đỡ của nó hệ thống chuyển sang trạng thái mới p2. B−ớc thứ hai tiến hành t−ơng tự. Lại chọn quyết định q2 ∈ Q xác định phép biến đổi Aq2. Phép biến đổi này chuyển hệ thống từ trạng thái p2 sang trạng thái p3, tức là p3 = Aq2p2 và quá trình thông qua quyết định đ−ợc tiếp tục. Bộ nghiệm (q1, q2, , qN) nhận đ−ợc trong kết quả hoạt động N b−ớc của hệ thống ta sẽ gọi là mô hình trạng (1). 34
36. Ta còn giả thiết tiếp theo là hiệu suất của hình trạng đ−ợc chọn có thể đánh giá đ−ợc bằng số l−ợng, tức là cho hàm số t−ơng ứng hình dạng đã cho và những trạng thái thu đ−ợc của hệ thống với một số nào đó. Hàm này ta sẽ gọi là hàm mục tiêu và ký hiệu là: F(p1, p2, , pN+1, q1, , qN) (5.22) ta cũng sẽ nói hàm số này cho thu nhập từ hình trạng. Th−ờng gặp phải những quá trình có tính chất là: ở b−ớc bất kỳ của quá trình, thu nhận từ hình trạng tiếp theo chỉ phụ thuộc vào trạng thái của hệ thống và hình trạng đ−ợc chọn ở b−ớc này mà không phụ thuộc vào hình trạng ở những b−ớc tr−ớc. Trong tr−ờng hợp này ta sẽ nói là hệ thống có tính chất Markôv. Tối −u động chỉ ứng dụng đ−ợc với những quá trình có tính chất đó. Việc tồn tại hàm mục tiêu (5.22) cho phép (và bắt buộc) đặt bài toán chọn trong những hình trạng cho phép, hình trạng nào tối −u (làm max hoặc min) hàm mục tiêu đó. Nh− vậy ta đi đến bài toán sau: cần tìm: Max F(p1, p2, PN+1, q1, , qN) (5.23) với điều kiện: qi ∈ Q (i = 1, 2, , N) (5.24) Tiếp theo ta giới hạn chỉ xét các bài toán làm max là chính, vì đối với những bài toán làm min, các lý luận vẫn đúng. Khi để ý rằng tất cả các trạng thái p2, p3, , pN+1 cuối cùng đều phụ thuộc vào trạng thái ban đầu và những quyết định đ−ợc thông qua (tức là thu nhập hoặc hàm mục tiêu (5.22) là hàm hợp chỉ của những biến số máy) ta thấy hàm mục tiêu của quá trình có thể viết theo cách khác. Sự phụ thuộc t−ơng minh của hàm mục tiêu vào p1, q1, q2, , qN ký hiệu là: ϕ(p1, q1, q2, , qN) (5.25) Nếu hàm (5.23) hoặc (5.25) tuyến tính, còn các hạn chế (5.24) là những bất đẳng thức hoặc đẳng thức tuyến tính thì trong tr−ờng hợp này ta có bài toán tối −u tuyến tính th−ờng Ta chuyển sang việc giải bài toán của ta dựa trên đặc điểm động của nó (các quyết định cần thông qua liên tiếp và không cùng một lúc tất cả). Để tiện việc trình bày về sau, ta giả thiết hàm ϕ có dạng: ϕ(p1, q1, , qN) = ϕN(p1, q1, , qN) = g(p1, q1) + b(p1, q1) ϕN-1(p2, q2, , qN), (5.26) hoặc, vì p2 = Aq1p1 nên (5.26) có thể viết d−ới dạng: ϕN(p1, q1, , qN) = g(p1, q1) + b(p1, q1) ϕN-1(Aq1p1, q2, , qN) (5.27) trong đó 0 < b (p1, q1) ≤ 1. Kết quả bài toán (5.23) và (5.24) đ−ợc viết nh− sau: Tìm Max ϕN(p1, q1, , qN) = Max{g (p1, q1) + b(p1, q1)ϕN-1(Aq1p1, p2, , qN)} (5.28) qi ∈ Q Các quá trình với các hàm dạng (5.27) có tính chất Markôv, vì trong hàm ϕN phần ϕN- 1 chỉ phụ thuộc vào trạng thái ban đầu tính đến thời điểm này và các quyết định tiếp theo q2, q3, , qN đ−ợc tách riêng ra. ý nghĩa kinh tế của hàm b(p1, q1) là ở chỗ: đến thời điểm hiện tại hàm này là hệ số chuyển tiếp những thu nhập t−ơng lai ϕN-1. 35
37. Trong tất cả những bài toán xét ở hai mục đầu, các hàm thu nhập đều đ−ợc biểu diễn d−ới dạng (5.27). Ta đ−a vào xét hàm fn(p) cho thu nhập từ quá trình n b−ớc bắt đầu từ trạng thái ban đầu p. Trong những bài toán đã xét ở trên, khi lập công thức truy hồi cho fn ta đã sử dụng một cách trực giác nguyên lý tối −u sau: hình trạng tối −u có tính chất là, mặc cho trạng thái ban đầu và những quyết định ở thời điểm đầu tiên thế nào chăng nữa, những quyết định tiếp theo phải lập thành một hình trạng tối −u cho trạng thái nhận đ−ợc trong kết quả quyết định đầu tiên. Bây giờ ta sử dụng nguyên lý này để lập công thức truy hồi của dãy {fn(p)}. Ta giả thiết là trong b−ớc thứ nhất ta chọn quyết định q mà kết quả của nó là hệ thống của chúng ta chuyển từ trạng thái p sang trạng thái mới Aqp. Khi đó, theo định nghĩa hàm fn-1, thu nhập lớn nhất sau n - 1 b−ớc sẽ bằng fn-1 (Aqp), còn thu nhập sau tất cả n b−ớc sẽ bằng: g(p, q) + b(p, q)fn-1 (Aqp). (5.29) nh− vậy nếu ta muốn nhận đ−ợc sau n b−ớc thu nhập lớn nhất thì ta cần chọn quyết định q thế nào đó để làm max tổng (5.29). Kết quả đi đến công thức truy hồi cơ bản: fn(p) = max {g(p, q) + b(p, q)fn-1 (Aqp)} (5.30) q ∈ Q (n ≥ 2) còn f1(p) = max g(p, q) (5.31) q ∈ Q Ta nhận thấy đại l−ợng fn(p) đ−ợc xác định đơn trị, trong khi đó quyết định q để nó đạt đ−ợc max trong công thức (5.30) có thể không phải là duy nhất, tức là có thể tồn tại nhiều quyết định tối −u bảo đảm có đ−ợc thu nhập lớn nhất này. Trong tr−ờng hợp quá trình kéo dài không có giới hạn, dãy các hàm fn(p) đ−ợc thay thế bởi một hàm f(p) duy nhất bằng thu nhập toàn phần nhận đ−ợc khi sử dụng hình trạng tối −u, nếu trạng thái ban đầu đ−ợc biểu diễn bằng thông số p. Trong tr−ờng hợp này các ph−ơng trình (5.30) và (5.31) đ−ợc thay bởi một ph−ơng trình phiếm hàm: f(p) = max {g(p, q) + b(p, q)f(Aqp)} (5.32) q ∈ Q Nh− vậy, nhờ việc đ−a vào hàm fn(p) một quá trình cụ thể, sinh ra bài toán (5.28) có thể gộp vào tập hợp những quá trình t−ơng tự chỉ khác nhau về thời hạn và trạng thái ban đầu, còn bài toán chọn cùng một lúc tất cả q1 ∈ Q; (i = 1, 2, , N) đ−ợc đ−a về việc tìm liên tiếp quyết định tối −u trong một b−ớc. Bây giờ để tìm nghiệm của bài toán (5.28) ta cần tính (xây dựng) dãy hàm f1(p), f2(p), , fN(p), trong đó xuất hiện vấn đề nhận hình trạng tối −u cho toàn bộ quá trình theo dãy này nh− thế nào. o o o Ta ký hiệu hình trạng tối −u này là (q1 ,q2 , ,q N ). Khi xây dựng dãy {fn(p)} (n = 2, 3, , N) nhờ công thức truy hồi (VI-30) trong mỗi b−ớc ta sẽ ghi nhớ giá trị qn tại đó đạt max trong (5.30), rõ ràng là giá trị này phụ thuộc vào p, nói một cách khác, là hàm số của thông số p. Ta ký hiệu hàm số đó là qn(p), tức là hàm qn(p) nh− thế nào để: fn(p) = g(p, qn(p)) + b(p, qn(p))fn-1(Aqn(p)p) 36
38. trong đó n = 2, 3, , N. Bây giờ viết hình trạng tối −u không khó khăn gì, thật vậy: o q1 = q N (p1 ); o q2 = q N−1(p2) trong đó p2 = A o p1 ; q1 o q3 = q N−2 (p3) trong đó p3 = A o p2 ; q 2 . . . . . . . . . . o q N = q1 (pn) trong đó pN = A o pN−1; q N−1 Xây dựng thực hành các dãy {fn(p)} và {qn(p)} đòi hỏi phải sử dụng các máy tính điện tử hoạt động nhanh, tuy nhiên, các bài toán khối l−ợng không lớn có thể giải đ−ợc mà không cần sử dụng máy tính. Việc xây dựng {fn(p)} và {qn(p)} theo công thức truy hồi (5.30) không phụ thuộc vào tính chất và cách cho hàm g(p, q), b(p, q), và phép biến đổi Aq không gây khó khăn về mặt nguyên tắc. Khi đó để tồn tại nghiệm của ph−ơng trình (5.31) cần đặt một số hạn chế lên hàm g(p, q), b(p, q) và phép biến đổi Aq. Trong hàng loạt các bài toán thực tế, điều đáng quan tâm lớn nhất không phải là giá trị lớn nhất hoặc nhỏ nhất của hàm này hoặc hàm khác mà chính là những giá trị thực của các thông số ở đấy cực trị đó đạt đ−ợc, nói cách khác, điều đáng quan tâm lớn nhất chính là hình trạng tối −u. Kết thúc mục này ta sẽ xét bài toán trong đó nhờ các t− t−ởng của quy hoạch động, tức là ph−ơng pháp các ph−ơng trình phiếm hàm, có thể nhận đ−ợc hình trạng tối −u. Ta sẽ xét bài toán đ−ợc gọi là bài toán Đgiônxơn. Có N chi tiết khác nhau cần đ−ợc gia công liên tiếp trên hai máy. Mỗi máy khi đã bắt đầu gia công một chi tiết thì không gia công chi tiết tiếp theo nếu ch−a kết thúc việc gia công chi tiết tr−ớc. Giả sử trình tự gia công các chi tiết trên các máy không thể thay đổi sau khi đã bắt đầu quá trình. Thời gian gia công các chi tiết trên mỗi máy đã cho tr−ớc. Hỏi cần phải đ−a các chi tiết lên máy thứ nhất theo trình tự thế nào để có thể gia công tất cả các chi tiết sau khoảng thời gian ngắn nhất. Nói một cách khác bài toán đặt ra là định trình sự đ−a các chi tiết vào gia công, trong đó tổng số thời gian bỏ trống của máy thứ hai để đợi các chi tiết từ máy thứ nhất là nhỏ nhất. Ta ký hiệu ai và bi là thời gian gia công chi tiết thứ i (i = 1,2, , N) t−ơng ứng trên máy thứ nhất và thứ hai. ứng với ph−ơng pháp quy hoạch động ta đ−a vào xét hàm f(a1, b1; a2, b2; ; aN, bN; t) là thời gian gia công ít nhất N chi tiết trong điều kiện là máy thứ hai bắt đầu làm việc muộn hơn máy thứ nhất t đơn vị thời gian. Khi đó nếu các máy bắt đầu việc gia công từ chi tiết thứ i thì nh− trên ta nhận đ−ợc ph−ơng trình phiếm hàm sau: f(a1, b1, ; aN, bN; t) - min{ai + f(a1, b1, ; ai-1, bi-1; 0, 0; ai+1, bi+1 ; ; aN, bN; bi + max(t - ai; 0)} Ph−ơng trình phiếm hàm này cho phép chỉ ra quy tắc lập cách chuyển vị trí tối −u. Thật vậy, đầu tiên gia công chi tiết t sau đó chi tiết j, ta đ−ợc: f(a1, b1, ; aN, bN; t) - min {ai + aj + f(a1, b1, ; ; 0, 0; ; 0, 0; ; aN, bN; tij)}, ở đây các cặp (ai, bi) và (aj, bj) là cặp (0, 0), còn tij = bj + max [bi + max(t - ai, 0) - aj, 0] (5.33) 37
39. Biến đổi (5.33) ta đ−ợc: tij = bj + max [bi + max(t - ai, 0) - aj, 0] = = bi + bi - aj + max [max(t - ai, 0) aj - bi] = = bj + bi - aj + max [t - ai, aj - bi, 0] = = bj + bi - aj - ai + max [t, ai + aj - bi, ai] = = bj + bi - (aj + ai) + max [t, max (ai + aj - bi, ai)] Bây giờ rõ ràng là nếu: Max(a1 + aj - bi, ai) < Max(aj + ai - bj, aj). (5.34) thì không cần đổi chỗ các chi tiết i và j. Bất đẳng thức (5.34) t−ơng đ−ơng với bất đẳng thức: ai + aj + max(-bi - aj) < aj + ai + max(-bj, -ai) tức là việc đổi chỗ các chi tiết i và j là cần thiết nếu Min(bi, aj) < Min (bj, ai) Từ đó suy ngay ra quy tắc xác định việc chuyển vị trí tối −u sau: 1. Lập bảng (A): i ai bi 1 a1 b1 2 a2 b2 3 a3 b3 N aN bN 2. Tìm giá trị nhỏ nhất trong tất cả các giá trị ai và bi 3. Nếu giá trị nhỏ nhất đó là một trong các số ai thì chi tiết t−ơng ứng đ−ợc đ−a vào đầu tiên. 4. Nếu giá trị nhỏ nhất là bi thì chi tiết t−ơng ứng đ−a vào sau cùng. 5. Gạch khỏi bảng hàng ứng với chi tiết bị đổi chỗ. 6. Lặp lại quá trình này với các chi tiết còn lại. 7. Trong tr−ờng hợp có một vài phần tử nhỏ nhất thì đầu tiên loại chi tiết với số thứ tự nhỏ nhất. Nếu giá trị nhỏ nhất là ai và bi thì coi là min đạt ở ai Ta xét ví dụ (B): B C t ai bi t ai bi 1 31 41 2 15 92 2 15 92 1 31 41 3 65 35 5 51 73 4 89 29 3 65 35 5 51 73 4 89 29 38
40. Số nhỏ nhất trong tất cả các số là 15, tức là a2, vì vậy chi tiết 2 đ−ợc đ−a vào đầu tiên; số nhỏ nhất tiếp theo sẽ là 29, tức là b4 - chi tiết 4 đ−ợc đ−a vào cuối cùng và v.v Việc sắp đặt tối −u các chi tiết dẫn ở bảng (C). 5.4. Ph−ơng trình điều khiển tối −u các dự trữ Trong mục kết thúc này ta sẽ xét một số mẫu điều khiển các dự trữ, trong đó để lập các ph−ơng trình điều khiển tối −u có thể sử dụng tối −u động. Ta sẽ xét mẫu đơn giản nhất với khối l−ợng đặt hàng cố định. Giả sử các chi phí liên quan đến việc mua hoặc sản xuất các mặt hàng cố định và trong khoảng thời gian ta quan tâm đến, giá hàng hóa không thay đổi. Vì vậy ta chỉ quan tâm đến việc hoàn thành các đơn đặt hàng (mua hoặc sản xuất) và việc bảo quản các trữ l−ợng. Ta giả thiết là khoảng thời gian ta quan tâm đến đ−ợc chia thành N phần bằng nhau Ta đ−a vào các ký hiệu sau: Sk là giá trị của nhu cầu trong khoảng thứ k (k = 1, ; N); dk là các chỉ tiêu cho việc bảo quản một đơn vị hàng hóa chuyển từ khoảng thứ k sang khoảng thứ (k + 1); (k = 1, 2, , N - 1). Cok là các chi phí liên quan đến việc thỏa mãn đơn đặt hàng trong khoảng thứ k (k = 1, 2, , N), ví dụ các chi phí cho các nguyên công chuẩn bị cuối cùng. qk là số l−ợng hàng hóa đ−ợc đặt làm hoặc sản xuất ra trong khoảng thứ k (k = 1, 2, , N). lk là mức độ ban đầu của trữ l−ợng trong khoản k (k = 1, 2, , N). Yêu cầu chỉ ra ph−ơng án sản xuất (hoặc mua) và lập các dự trữ, trong đó tổng chi phí là nhỏ nhất. Chỉ ra ph−ơng án có nghĩa là đối với từng khoảng cho các số qk và lk xác định các mức độ sản xuất và dự trữ. Trong đó ph−ơng án cần phải nh− thế nào để toàn bộ nhu cầu đ−ợc thỏa mãn, tức là cần thỏa mãn bất đẳng thức: k k lk = lo + ∑∑qi − si ≥ 0 i==1 i 1 (k = 1, 2, , N). Ta đặt f(i) là các chi phí nhỏ nhất sau các khoảng thời gian từ khoảng thứ nhất đến khoảng thứ i. Khi đó sử dụng nguyên lý tối −u đ−ợc phát biểu ở tr−ớc, đối với hàm này ta có thể viết công thức truy hồi sau: i−1 i f(i) = min {Coi + f(i - 1), min[Coi + ∑dl , ∑Sk + f (j−1)]} (5.35) 1≤ j≤i l= j k=l+1 trong đó hiển nhiên là f(1) = Coi và f(0) = 0. Đây là ph−ơng trình ta th−ờng gặp trong bài toán thay thế thiết bị cho phép liên tiếp tính các giá trị của hàm f(i) với i = 2, 3, , N và đó chính là sự chỉ ra ph−ơng án sản xuất và lập dự trữ tối −u. Sử dụng ph−ơng trình (5.35) có thể chứng minh hình trạng tối −u có những tính chất sau: 1. Nếu trong thời gian dầu của giai đoạn nào đó có d− hàng hóa thì trong giai đoạn đó việc đặt mua hàng (chế tạo) không xảy ra. 2. Chỉ sản xuất số l−ợng hàng hóa vừa đủ để thỏa mãn nhu cầu trong khoảng thời gian tới nào đó. 39
41. 3. Nếu nhu cầu trong giai đoạn nào đó đ−ợc thỏa mãn hoàn toàn bằng hàng hóa sản xuất ra trong một giai đoạn tr−ớc thì hàng hóa đó sẽ đủ làm thỏa mãn nhu cầu trong những khoảng trung gian. 4. Nếu tr−ớc lúc bắt đầu giai đoạn nào đó dự trữ bằng không thì tất cả những giai đoạn tr−ớc có thể xét một cách độc lập với các giai đoạn còn lại. T−ơng tự, có thể xét các tình huống phức tạp hơn. Chẳng hạn có thể coi nhu cầu trong mỗi giai đoạn thời gian là đại l−ợng ngẫu nhiên với hàm phân phối đã biết, v.v 40
42. Ch−ơng 6: Bài toán tối −u phi tuyến không ràng buộc 6.1. Mở đầu về bài toán tối −u phi tuyến Bài toán tối −u phi tuyến tổng quát: Tìm giá trị tối −u (Max hoặc Min) của hàm mục T n tiêu f(x) với các ràng buộc gi(x) ≤ bi; i = 1, m; trong đó x = [x1, xn) ∈ R ; các hàm f(x) và gi(x) là phi tuyến. Tập các nghiệm chấp nhận đ−ợc: n D = {x ∈ R : gi (x) ≤ bi; i = 1, , m} Tối −u toàn cục (tối −u tuyệt đối): Max: f (x*) ≥ f (x); x ∈ D Min: f (x*) ≤ f (x); x ∈ D x* là nghiệm tối −u; f(x*) là giá trị tối −u của f (x). Tối −u địa ph−ơng (tối −u t−ơng đối): Nếu tồn tại lân cận V của x* sao cho: Max: f (x*) ≥ f (x); x ∈ D∩V Min: f (x*) ≤ f (x); x ∈ D∩V f D e b x A c Hình 6.1 Trong hình 6.1: A, C, E: Min địa ph−ơng B, D : Max địa ph−ơng C : Min toàn cục F : Max toàn cục Không có ph−ơng pháp chung nào có hiệu quả để giải bài toán tối −u phi tuyến. Nói chung, các ph−ơng pháp có thể chia thành 2 nhóm: - Các ph−ơng pháp gradient có dùng đạo hàm. - Các ph−ơng pháp trực tiếp không dùng đạo hàm. 6.2. Điều kiện tối −u của bài toán không bị ràng buộc 6.2.1. Bài toán: Tìm x* để f(x) → Min, x ∈ En T x = [x1, , xn] 6.2.2. Điều kiện cần của tối −u địa ph−ơng: 1) f (x) khả vi tại x* 2) ∇f (x*) = 0 nghĩa là x* là điểm dừng 6.2.3. Điều kiện đủ của minimum địa ph−ơng: Ngoài 2 điều kiện cần còn thêm điều kiện đủ: 3) H = ∇2f (x*) > 0, nghĩa là ma trận Hesse xác định d−ơng. 41
43. L−u ý rằng: ma trận đối xứng A = (aij) cấp n là xác định d−ơng khi và chỉ khi định thức cấp n và mọi định thức ứng với phần tử chéo chính đều > 0. ⎡ ∂ 2 f ∂ 2 f ∂ 2 f ⎤ ⎢ L ⎥ ∂x ∂x ∂x ∂x ∂x ∂x ⎢ 1 1 1 2 1 n ⎥ ⎢ ∂ 2 f ∂ 2 f ∂ 2 f ⎥ ⎛ 2 ⎞ ⎢ ⎥ ⎜ ∂ f(x) ⎟ L H = = ⎢∂x2∂x1 ∂x2∂x2 ∂x2∂xn ⎥ xác định d−ơng. ⎜ ∂x ∂x ⎟ ⎝ i j ⎠ ⎢ ⎥ ⎢ ⎥ ⎢ ∂ 2 f ∂ 2 f ∂ 2 f ⎥ ⎢ L ⎥ ⎣∂xn∂x1 ∂xn∂x2 ∂xn∂xn ⎦ a11 L a1n a11 a12 ∆n = L L L > 0 , , ∆2 = > 0; ∆1 = a11 > 0 a21 a22 an1 L ann Chú ý: Điều kiện đủ đối với maximum địa ph−ơng 1) ⎫ ⎬ nh− đối với minimum. 2)⎭ 3) ∇2f(x*) là xác định âm. Có thể tồn tại cực trị địa ph−ơng mà không thoả mãn điều kiện cần 1) và 2) nói trên, khi điều kiện đủ đ−ợc thoả mãn thì x* đảm bảo hàm mục tiêu đạt cực trị. 6.3. Các ph−ơng pháp dùng đạo hàm 6.3.1. Ph−ơng pháp gradient: 1. Gradient của 1 hàm và h−ớng gradient: Khi f(x) là một hàm vô h−ớng thì gradient của f (x) là 1 vectơ: T ⎡ ∂f ∂f ⎤ ∇f(x) = ⎢ , , ⎥ ⎣∂x1 ∂xn ⎦ Theo h−ớng của ∇f(x0) thì hàm f(x) tăng nhanh nhất tại x0; Theo h−ớng của - ∇f(x0) thì f(x) giảm nhanh nhất tại x0. 2. Nội dung ph−ơng pháp Gradient: Ph−ơng pháp Gradient là một trong những ph−ơng pháp phổ biến nhất để tìm cực tiểu của một hàm. Theo ph−ơng pháp này phép lặp đ−ợc tính theo công thức: x(k+1) = x(k) - λ(k)∇f(x(k)) trong đó k ≥ 0: b−ớc lập thứ k. λ(k) > 0: là hệ số xác định độ dài của b−ớc đi theo h−ớng gradient. Ta có thể chọn λ = const. cho cả quá trình hoặc xác định giá trị tối −u λ(k) cho từng b−ớc theo ph−ơng pháp tối −u một tham số. - ∇f(x(k)): h−ớng ng−ợc lại của gradient tại x(k) (h−ớng dốc nhất xác định tại x(k)). Ban đầu ta chọn điểm xuất phát x(k) tuỳ ý. Nếu dãy {x(k)}không hội tụ ta lấy λ nhỏ hơn. Khi λ đủ nhỏ thì {x(k)} sẽ hội tụ về giá trị tối −u x*. Ví dụ: Tìm Min của f(x) = 2x2 + 1. Giải: ∇f(x) = 4x Chọn x(0) = 1; ∇f(x(0)) = 4x(0) = 4≠ 0. x(1) = x(0) - λ∇f( x(0))= 1 - 4λ; λ > 0 42
44. ∇f(x(1)) = 4x(1) = 4(1- 4λ); nếu chọn λ ≠ 1/4 thì ∇f(x(1)) ≠ 0 và x(2) = (1 - 4λ) - 4λ(1 - 4λ) = (1- 4λ)2 Tiếp tục quá trình, ở phép lập thứ k ta có: x(k) = (1 - 4λ)k Rõ ràng nếu 0 < λ < 1/4 thì x(k) → 0 khi k → ∞ Điểm x* = 0 là điểm cực tiểu của f(x) và f(x*) = 1. 6.3.2. Ph−ơng pháp h−ớng dốc nhất: ∇f (x (k ) ) Chọn điểm xuất phát, tính ∇f(x(k)); ∇f(x (k) ) ; s (k) = ∇f (x (k ) ) trong đó s(k) là vectơ đơn vị theo h−ớng ∇f(x(k)) (k+1) (k) (k) Đặt x = x - λk.s . Dùng tối −u hoá theo 1 tham số: (k+1) (k) * f(x ) = f(λ ) → Min ⇒ Tìm đ−ợc λ k (k+1) (k) * (k) Chọn điểm mới: x = x - λ k.s . Ví dụ: Tìm Min của hàm: 2 2 2 f(x) = 100(x2 - x 1) + (1-x1) Giải: + Chọn x(k) = (- 0,5; 0,5)T → f(x(k)) = 8,5 + Tính ∇f(x(k)) và ⏐⏐∇f(x(k)⏐⏐ ∂f ∂f = 47; = 50; ∂x1 ∂x2 ∇f ( x( k ) ) = 47 2 + 502 = 68,6 (k ) ∇f (x) 1 ⎡47⎤ T s = = ⎢ ⎥ = []0,658;0,729 ∇f (x) 68,6 ⎣50⎦ Vectơ s(k) vuông góc với đ−ờng cùng mục tiêu của f(x) tại x(k) =(-0,5; 0,5) (k+1) (k) (k) Đặt x = x - λk s (k+1) ⎡− 0,5⎤ ⎡0,685⎤ hay: x = ⎢ ⎥ − λk ⎢ ⎥ ⎣0,5 ⎦ ⎣0,729⎦ (k+1) 2 2 2 f(x ) = f(λk) = 100 [0,5 - 0,729 λk - (0,5 + 0,685λk) ] + (1,5 + 0,685λk) → Min * Sau khi tối −u hóa theo một tham số, ta nhận đ−ợc: λ k = 0,164. * (k+1) Chọn điểm mới: Thay λk = λ k = 0,164 vào x (k+1) ⎡− 0,5⎤ ⎡0,685⎤ ⎡− 0,612⎤ (x ) = ⎢ ⎥ − 0,164⎢ ⎥ = ⎢ ⎥ ⎣0,5 ⎦ ⎣0,729⎦ ⎣0,381 ⎦ f(x(k+1)) = 2,6 Tiếp tục tìm s(k+1), cuối cùng quá trình hội tụ về x* = [1 ; 1]T và f(x*) = 0. Chú ý: Nếu dùng ph−ơng pháp gradient đơn giản, ta đặt λk = const. cho cả quá trình tính. 5.3.3. Ph−ơng pháp Newton: Dùng gradient cấp 2 của f (x): Theo ph−ơng pháp này phải tính ma trận Hesse. 43
45. ⎡ ∂2 f ∂2 f ⎤ ⎢ L ⎥ ∂x1∂x1 ∂x1∂xn ⎛ ∂2 f ( x ) ⎞ ⎢ ⎥ ∇2f(x) = H(x) = ⎜ ⎟ = ⎢ ⎥ ⎜ ∂x ∂x ⎟ ⎝ i j ⎠ ⎢ 2 2 ⎥ ⎢ ∂ f ∂ f ⎥ ⎢ L ⎥ ⎣∂xn∂x1 ∂xn∂xn ⎦ (k+1) * -1 (k) (k) (k) * (k) và chọn: x = x(k) + λ k.H (x ).∇f(x ) = x + λ ks Ví dụ: Tìm (x1, x2) sao cho hàm mục tiêu: 1 1 f(x) = 4x1 + x2 + + → Min x1 x2 Giải: ⎡ 1 ⎤ ⎡ 2 ⎤ 4 − 0 ⎢ x2 ⎥ ⎢ x3 ⎥ ∇f(x) = ⎢ 1 ⎥ và H(x) = ⎢ 1 ⎥ ⎢ 1 ⎥ ⎢ 2 ⎥ − ⎢1 2 ⎥ ⎢0 3 ⎥ ⎣ x2 ⎦ ⎣ x2 ⎦ Chọn vectơ xuất phát x(0) = [1,13; 3,55]T (0) T (0) ⎡1,41 0 ⎤ ∇f(x ) = [3,21; 0,92] ; H(x ) = ⎢ ⎥ ; ⎣0 0,04⎦ -1 (0) ⎡0,71 0⎤ H (x ) = ⎢ ⎥ ⎣0 25⎦ (1) (0) -1 (0) (0) x = x - λk , H (x ). ∇f(x ) = ⎡1,13 ⎤ ⎡0,71 0 ⎤ ⎡3,21⎤ ⎡1,13 ⎤ ⎡2,28⎤ * ⎢ ⎥ − λk ⎢ ⎥ ⎢ ⎥ = ⎢ ⎥ − λk ⎢ ⎥ → λk = 0,112 ⎣3,56⎦ ⎣0 25⎦ ⎣0,92⎦ ⎣3,56⎦ ⎣23 ⎦ Chọn điểm mới: (1) ⎡1,13 ⎤ ⎡2,28⎤ ⎡0,88⎤ x = ⎢ ⎥ − 0,112⎢ ⎥ = ⎢ ⎥ ⎣3,56⎦ ⎣23 ⎦ ⎣0,98⎦ Để đi đến kết quả x* = (0,5; 1), ph−ơng pháp h−ớng dốc nhất cần 20 b−ớc, ph−ơng pháp Newton cần 2 b−ớc. 6.3.4. Ph−ơng pháp Gradient liên hợp: 1. H−ớng liên hợp: Hai h−ớng si và sj là liên hợp với nhau, nếu: T T 2 (sj ) .H.si = 0 = 0; i ≠ j và (sj) . H.sj ≥ 0; i = j; H = ∇ f(x) 2 2 Ví dụ: f(x) = 2x1 + x2 − x1x2 ( 0 ) ⎛0⎞ 0 ⎛0⎞ ( 0 ) T (0) (0) s1 = ⎜ ⎟;s2 = ⎜ ⎟ → ( s1 ) , s2 = 0 → hai vecto s1 ⎝1⎠ ⎝1⎠ ( 0 ) ( 0 ) T ( 0 ) và s2 vuông góc nh−ng không liên hợp vì ( s1 ) .H. s2 = 4 ≠ 0. 2. Nội dung ph−ơng pháp: Chọn x(0) và tính s(0) = - ∇f(x(0)) ở b−ớc thứ k, dùng tối −u 1 tham số xác định Min f(x) theo h−ớng s(k), xác định đ−ợc x(k+1) Tính f(x(k+1)) và ∇f(x(k+1)) Xác định h−ớng: ∇T f ( x( k +1 ) ).∇f ( x( k +1 ) ) s(k+1) = - ∇f(x(k+1)) + s(k) ∇T f ( x( k ) ).∇f ( x( k ) ) 44
46. Sau (n+1) b−ớc (tức k = n), chu trình tính lập lại, s(k+1) trở thành x(0). Quá trình tính đ−ợc kết thúc khi s( k ) < ε chọn tr−ớc. Nhận xét : các ph−ơng pháp dùng đạo hàm hội tụ nhanh nh−ng khi số biến là lớn thì khó khăn nhận đ−ợc các đạo hàm d−ới dạng giải tích, mặt khác việc chuẩn bị bài toán để giải tốn nhiều thời gian. 6.4. Các ph−ơng pháp không dùng đạo hàm 6.4.1. Ph−ơng pháp trực tiếp Tìm x* sao cho f(x) → Max; x ∈ Rn Thực chất là ở mỗi b−ớc chỉ biến đổi một thành phần xi của x còn các thành phần khác giữ nguyên và cứ làm nh− vậy cho tới khi nhận đ−ợc cực đại. Các b−ớc tìm kiếm: 1. Tìm thăm dò b−ớc 1 (0) ( 0 ) ( 0 ) T Cho các giá trị đầu của x = [ x1 , , xn ] và số gia của biến số ∆x( ∆x1 , ∆xn). Tính giá trị f(x(0)): Cho 1 thành phần của x biến đổi, các thành phần khác giữ nguyên: ( 1 ) ( 0 ) ( 1 ) ( 0 ) ( 0 ) x1 = x1 + ∆x1→ Tính α = f( x1 , x2 , xn ) (0) ( 1 ) ( 0 ) ( 0 ) Nếu α ≤ f(x ) thì lấy: x1 = x1 - ∆ x1 → Tính α ( 0 ) ( 0 ) ( 0 ) Nếu f(x) không cải tiến đ−ợc cả 2 phía (với x1 + ∆x1 và x1 - ∆x1) thì cố định x1 không cho biến đổi nữa. ( 1 ) ( 0 ) Tiếp tục tiến hành với x2 = x2 ± ∆x2 cho tới khi tất cả các biến đều đ−ợc biến đổi. Nh− vậy trong tìm thăm dò b−ớc 1, tại mỗi b−ớc dịch chuyển theo biến số độc lập, giá trị hàm mục tiêu đ−ợc so sánh với giá trị của nó tại điểm đ−ợc thay bằng giá trị mới trong những so sánh sau đó. Nếu hàm mục tiêu không đ−ợc cải tiến thì giữ nguyên giá trị cũ. 2. Tìm theo mẫu: Khi kết thúc tìm thăm dò b−ớc 1, ta xác định đ−ợc x(k). ở b−ớc tìm theo mẫu ta lấy: x(k+1) = m x(k) - x(b) ( k +1 ) (k) ( b ) tức là: xi = m xi − xi trong đó: y x(b) - điểm cơ sở, ở lần lặp đầu x(b)= x(0) y m - số biến tìm thăm dò cần thiết. Ví dụ với f(x1, x2) ta có m = 2. 3. Tìm thăm dò b−ớc 2: Xuất phát từ điểm x(k+1) tính f(x(k+1)) và so với giá trị f(x) ở b−ớc tìm theo mẫu để xem thăm dò b−ớc 2 có kết quả không. Nếu thăm dò b−ớc 2 có kết quả tại x(k+2) thì tìm theo mẫu đ−ợc coi là có kết quả nếu: f(x(k+2)) ≥ f(x(k)) và quá trình đ−ợc lặp lại với điểm xuất phát x(b) = x(k), Nếu thăm dò b−ớc 2 không kết quả thì kết luận rằng tìm theo mẫu đã thất bại và lại phải tìm kiếm thăm dò b−ớc 1 sao cho việc xác định h−ớng mới có hiệu quả. Nếu tìm thăm dò b−ớc I liên tiếp không cho h−ớng mới hiệu quả thì kết luận rằng tìm theo mẫu đã thất bại và lại phải tìm kiếm thăm dò b−ớc 1 sao cho việc xác định h−ớng mới có hiệu quả. Nếu tìm thăm dò b−ớc 1 liên tiếp không cho h−ớng mới hiệu quả thì liên tiếp giảm ∆x cho tới khi hoặc xác định đ−ợc h−ớng mới có hiệu quả, hoặc ∆x đã nhỏ hơn sai số cho phép. Việc không có khả năng tăng f(x) khi ∆x đã khá bé tức là tối −u cục bộ đã đạt đ−ợc. Nhận xét : ph−ơng pháp trực tiếp nói chung chậm hội tụ hơn so với ph−ơng pháp dùng đạo hàm nh−ng sử dụng lại tiện lợi hơn vì không phải tính đạo hàm. Ví dụ: Tìm (x1, x2) sao cho hàm mục tiêu: 45
47. 1 f(x) = 2 2 → Max (x1 +1) + x2 Giải: Tìm thăm dò b−ớc 1: - Chọn x(0) = [2,0; 0,8]T; ∆x = [0,6; 0,84]T - Tính f(x(0)) = 0,059. ( 1 ) x1 = 2,0 + 0,6 = 2,6; f(2,6; 2,8) = 0,048; (không cải thiện) ( 1 ) x1 = 2,0 - 0,6 = 1,4; f(1,4; 2,8) = 0,073; (cải thiện) ( 1 ) x2 = 2,8 + 0,84 = 3,64; f(1,4; 3,64) = 0,052; (không cải thiện) ( 1 ) x2 = 2,8 - 0,84 = 1,96; f(1,4; 1,96) = 0,104; (cải thiện) Nh− vậy tìm thăm dò b−ớc 1 đã đạt kết quả, vectơ mới x(1) = [1,4; 1,96]T Tìm theo mẫu: ( k +1 ) ( k ) ( b ) xi = 2xi − xi với x(b) = x(0) = [2,0; 2,8]T, ( 1 ) x2 = 2. (1,4) - 2,00 = 0,8 ( 2 ) (2) T x2 = 2(1,96) - 2,8 = 1,12 → x = [0,8; 1,12] f(0,8; 1,12 ) = 0,22. Đến đây ch−a kết luận đ−ợc mà phải tìm thăm dò b−ớc 2 và so sánh với f(x(2)) = 0,22. Tìm thăm dò b−ớc 2: ( 3 ) x1 = 0,8 + 0,6 = 1,4; f(1,4; 1,12) = 0,14 (không cải thiện ) ( 3 ) x1 = 0,8 - 0,6 = 0,2; f(0,2; 1,12) = 0,38 (cải thiện ) ( 3 ) x2 = 1,12 + 0,84 = 1,96; f(0,2; 1,96) = 0,19 (không cải thiện ) ( 3 ) x2 = 1,12 - 0,84 = 0,28; f(0,2; 0,28) = 0,67 (cải thiện ) Nh− vậy x(3) = [0,2; 0,28] Để xác định xem tìm thăm dò b−ớc 2 có kết quả không cần so sánh với f(x(1)): f(x(3)) = f (0,2; 0,28) = 0,67 f (x(0)) = f (1,4; 1,96) = 0,104 Vì f(x(3)) > f (x((1)) nên tìm kiếm theo mẫu có kết quả. Điểm cơ sở bây giờ là: x(b) = x(1) = [1,4; 1,96)T Điểm x(3) = [0,2; 0,28]T đ−ợc coi là điểm kết quả của tìm kiếm thăm dò nên chỉ việc tìm kiếm theo mẫu xuất phát x(3). Tìm theo mẫu xuất phát từ x(3). ( 4 ) x1 = 2.(0,2) - 1,4 = 1,00 ( 4 ) (4) T x2 = 2.(0,28) - 1,96 = -1,40 → x = [1,0; -14] fx((4)) = f(-1,0; 1,4 ) = 0,51 Tìm thăm dò b−ớc 2, so sánh với f (x(4)): ( 5 ) x1 = -1,0 + 0,6 = -1,4 ; f(-0,4; - 1,4) = 0,43 (không cải thiện) ( 5 ) x1 = 1,0 - 0,6 = -1,6 ; f(-1,6; -1,4) = 0,43 (không cải thiện) ( 5 ) (5) x2 = -1,4 + 0,84 = -0,56 ; f(1,0; -0,56) = 3,18 (cải thiện) và x = (-1,0; -0,56) Vì f(x(5)) = f(-0,1; -0,56) =3,18 > f(x(3)) = f(0,2; 0,28 ) = 0,60 nên điểm x(5) đ−ợc coi là kết quả tìm thăm dò. Tìm theo mẫu xuất phát từ x(5); x(b) = x(3) ( 6 ) (6) x1 = 2.(-1,0) - 0,2 = - 2,2; x2 = 2.(0,56) - 0,28 = -1,4 Do đó: x(6) = [-2,2; - 1,1]T; f(x(6)) = f(-2,2; - 1,4) = 0,29 46
48. Tìm thăm dò b−ớc 2 so sánh với f(x(6)): (7 ) x1 = - 2,2 + 0,6 = 1,6; f(-1,6; - 1,4) = 0,43 (không cải thiện) (7 ) x2 = -1,4 + 0,84 = - 0,56 ; f(-1,6; - 0,56) = 1,49 (cải thiện) Vì f(x(7)) = f(-1,6; - 0,56) = 1,49 0 thì vị trí xr đ−ợc xác định theo công thức: xr - xo = α(x0 - xp) xr = (1+α)xo - αxp x − x và α = r o xo − x p B−ớc 5: So sánh giá trị của fr và fq 1) Nếu fr 1 đ−ợc tìm từ biểu thức: xm - xo = γ(xr - xo) 47
49. xm = γxr + (1- γ)xo x − x γ = m o xr − xo Tính f(xm)=fm. a) Nếu fm fq thì bỏ điểm xm vì đã đi quá xa. Thay xp bởi xm, kiểm tra lại tính hội tụ. Nếu vẫn ch−a thì quay lại b−ớc 2. 2) Nếu fr>fq nh−ng fr fq nh−ng fr>fg thì chuyển sang b−ớc 6. B−ớc 6: So sánh các giá trị fr và fp 1) Nếu fr>fp thì chuyển về phép co (mục 2) của b−ớc 6): Nếu fr fg chuyển sang b−ớc co. 2) Thực hiện phép co: - Tr−ờng hợp fr>fp ta đã dịch quá xa theo h−ớng từ xp đến xo nên cần sửa lại phép co để tìm xc nh− sau (Hình 6.1c): xc - xo = β(xp-xo) với 0 fp thì việc tìm giá trị nhỏ hơn fp không đ−ợc, phải chuyển qua b−ớc 8. B−ớc 8: Thu nhỏ kích th−ớc của đơn hình còn một nửa, lấy xq làm chuẩn. Nh− vậy điểm xi nào đó đ−ợc thay bằng điểm: 1 1 x - (x - x ) = (x + x ) i 2 i q 2 i q Tính các giá trị fi (i=1 ữn+1). Kiểm tra tính hội tụ, nếu không quay lại b−ớc 2. B−ớc 9: Tính: n+1 2 2 σ = ∑( f i − f ) /(n +1) ; f = fi/(n+1) i=1 Nếu σ nhỏ hơn độ chính xác ε nào đó thì giá trị của các hàm số rất gần nhau và do đó điểm Min gần với xq. Bài tập 1. Tìm minimum các hàm mục tiêu d−ới đây theo ph−ơng pháp gradient: 2 2 2 1) f(x) = 3(x1 - 4) +5(x2 + 3) + 7(2x3 + 1) 2 2 2) f(x) = 1 -2x1 - 2x2 - 4x1x2 + 10 x1 + 2 x2 3 2 3) f(x) = x1 + x2 − 3x3 − 2x2 + 2 2. Tìm minimum các hàm mục tiêu sau theo ph−ơng pháp trực tiếp: 4 4 2 2 1) f(x) = x1 + x2 + 2x1 x2 − 4x1 + 3 2 2 2 2 2) f(x) = (x1 + x2 −11) + (x1 + x2 − 7) 48
50. * 1 3) Tìm x sao cho f(x) = 2 2 → Max (x1 +1) + x2 49
51. Ch−ơng 7: Bài toán tối −u phi tuyến có ràng buộc 7.1. Mở đầu 7.1.1. Bài toán: Hàm mục tiêu f(x) → Min: x ∈Rn. Các ràng buộc: hj(x) = 0, j = 1,2, , m gj(x) ≥ 0, i = m + 1, ,p. 7.1.2. Khái niệm: 1/Tập nghiệm chấp nhận đ−ợc: n D = {x ∈ E : hj (x) = 0; gj (x) ≥ 0, ∀j} 2/ H−ớng chấp nhận đ−ợc tại x*: h−ớng V thoả mãn. T * T * V. ∇gj(x ) ≥ 0 và V .∇hj(x ) = 0 (*) Điều kiện (*) thực hiện đ−ợc khi thoả mãn 1 trong các điều kiện sau: a) Các hàm ràng buộc là tuyến tính; b) Các hàm ràng buộc lồi và ∃ x : gi ( x ) ≥ 0 * * c) Các hàm ràng buộc phi tuyến, các ∇gj(x ) và ∇hj(x ) là độc lập tuyến tính. 3/ Hàm Lagrange: m p L(x,u,w) = f(x) + ∑∑wi .hi (x) − u j .g j (x) i=+11j=m Nếu giới hạn gi(x) ≤ 0 thì điều kiện (*) là: m p T * V . ∇gj(x ) ≥ 0 và L(x,u,w) = f(x) + ∑∑wi .hi (x) + u j .g j (x) i=+11j=m 7.1.3. Điều kiện cần của cực trị địa ph−ơng: 1/ f(x), gj(x), hj(x) khả vi 2/ Điều kiện về h−ớng chấp nhận đ−ợc (*) đ−ợc thoả mãn tại x*∈ D. 3/ Tồn tại các nhân tử Lagrange u*, w* sao cho (định lý Kuhn -Tucker): * a) hi(x ) = 0 ; i = i, m * b) gj(x ) ≥ 0 ; j = m+1, p * * c) uj .gj(x ) = 0 ; j = m+1, p * d) uj ≥ 0 ; j = m+1, p → nhân tử đối với gi(x) e) ∇L (x*, u*, w*) = 0 m p * * * * * * * * trong đó: ∇L(x ,u ,w ) = ∇f(x ) + ∑∑w i .∇hi (x ) + u j .∇g j (x ) = 0 i=+11j=m 7.1.4. Điều kiện đủ: Khi muốn xác định loại cực trị (min hay max) ta phải xét đến gradient cấp hai ∇2L (x*,u*,w*), tuy nhiên khi tính bằng ph−ơng pháp số ta chỉ dùng đến điều kiện cần. 7.2. Ph−ơng pháp Gradient Thuật toán: ( 0 ) Chọn 1 điểm bất kỳ x 0 trong miền ràng buộc. Đi theo h−ớng đối gradient [nếu Max f(x) thì đi theo h−ớng gradient tại x(0)]. Chọn b−ớc đi λ tối −u: x(k+1) = x(k) - λ ∇f(x(k)) λ đ−ợc xác định từ tối −u 1 tham số hoặc biến thiên ∇f(x) theo λ là lớn nhất tức là: 50
52. d ∇f = ∇f (x (1) ).∇f (x (0) ) = 0 dλ Kiểm tra xem x có nằm trong miền ràng buộc không. Nếu chạm vào biên phải kiểm tra điều kiện ∇f//∇gi. Quá trình kết thúc khi các vectơ m m (k) ∇f(x) và ∑∇ gi(x) song song tức là: ∇f(x ). ∑∇ gj(x) = 1 j =1 j =1 Ví dụ 1: Tìm (x1, x2) sao cho hàm mục tiêu: 2 2 f(x)= - 6x1 - 4x2 + x 1 + x 2 +18→ Min Các ràng buộc: ⎧4x1 + 3x2 ≤ 24 ⎪ 2 2 ⎨x1 − 5x1 + x2 0 nên với λ = 0,5 đại l−ợng ∆f đạt giá trị lớn nhất. dλ2 Chọn điểm : x(1) = (1,5 + 3. 0,5; 3 - 2. 0,5) = (3 ; 2) Thử lại xem x(1) có trong miền ràng buộc không: 4,3 + 3,2 = 18 < 24 32 - 5,3 + 22 = - 2 <6 Tính - ∇f(x(1)) = (6 - 2,3; 4 - 2.2) = (0; 0). Nghĩa là không có cách di chuyển nào từ x(1) làm giảm f nữa, vậy x(1) = x*: x* = [3 ; 2]T ; f (x*) = 5. Ví dụ 2: Tìm (x1, x2) sao cho hàm mục tiêu: 2 2 f(x) = 2x1 + 3x2 - 0,1 x1 + 0,1x2 → Max 51
53. với các ràng buộc: 2 2 ⎧10x1 + x1 + 20x2 + x2 ≤ 100 ⎪ 2 2 ⎪20x1 + x1 +10x2 + x2 ≤ 120 ⎨ 2 2 ⎪20x1 + x1 + 20x2 + x1 ≤ 150 ⎪ ⎩x j ≥ 0 2 2 hay: g1(x) = 100 - (10x1 + x 1 + 20x2 + x 2 ) ≥ 0 2 2 g2(x) = 120 - (20x1 + x 1 + 10x2 + x 2 ) ≥ 0 2 2 g3(x) = 150 - (20x1 + x 1 + 20x2 + x 2 ) ≥ 0 Giải: Chọn điểm xuất phát x(0) = (1; 3) ; f(x(0)) = 10 Tính gradient: ∂f ∂f (0) = 2 − 0,2x1 ; = 3 − 0,2x2 ; ∇f(x ) = (1,8 ; 2,4) ∂x1 ∂x2 (1) (0) (1) Đặt x = x + λ1∇f(x ) = (1+1,8λ1) = (1,8λ1 ; 3 + 2,4λ1) Đặt λ1 = 0,5 Lấy x(1) = [1,9 ; 4,2]T (1) Kiểm tra: g1 (x ) = -24,25 0 (1) g3 (x ) = - 6,75 0 (3) g2 (x ) = 20,2894 > 0 (3) g3 (x ) = 30,57 > 0 Vậy x(3) thuộc miền ràng buộc và f(x(3)) = 11,8579 (3) (3) Tìm ∇f(x ) và ∇g1(x ) ∇f(x(3)) = (1,4850; 2,4600); (3) ∇g1(x ) = (-15,15 ; - 25,40) Tính tỷ số các toạ độ t−ơng ứng của 2 vectơ này: 52
54. 1,4850 2,46 = −0,089; = −0,097 → Hai giá trị đã xấp xỉ nhau − 15,15 − 25,4 (3) (3) Do đó ∇f(x ) và ∇g1(x ) là song song và việc chuyển dọc theo đúng sẽ đi theo đ−ờng dích dắc gần biên của miền ràng buộc và cắt biên. Ngoài ra cần l−u ý rằng độ nghiêng: (3) (3) g1(x ) = 6,3294 là t−ơng đối lớn và x thuộc miền ràng buộc, do đó ta lấy kết quả: x* = [2,5575; 2,70000]T; f(x*) = 11,8579 = Max. 7.3. Ph−ơng pháp hàm phạt Trong ph−ơng pháp hàm phạt, ta thay thế hàm mục tiêu ban đầu f(x) bởi hàm mục tiêu mở rộng F(x,r) chứa thông số r và có tính đến các ràng buộc. Giá trị của hàm mục tiêu mở rộng F(x,r) phải trùng với giá trị hàm mục tiêu ban đầu f(x) và khi ra bên ngoài miền nghiệm chấp nhận đ−ợc thì F(x,r) khác với f(x). Khi x → x* thì F(x*,r) → f (x*). Các thuật toán dùng hàm phạt khác nhau ở dạng hàm F(x,r) nh−ng đều nhằm mục đích đ−a bài toán tối −u bị ràng buộc về bài toán tối −u không bị ràng buộc. Ph−ơng pháp nhân tử Lagrange: T Hàm mục tiêu: f(x) → Min ; x = [x1; x2, , xn] Ràng buộc ở dạng đẳng thức: gj(x) = 0; j = 1,2, , ,m Xây dựng hàm Lagrange (hàm mục tiêu mở rộng): L (x,λ) = f(x) + ∑λj.gj (x); λj - các nhân tử Lagrange j = 1,2, ,m. Điều kiện cần để tồn tại cực trị địa ph−ơng của L(x,λ) là: ⎧ ∂L ⎪ = 0; j = 1,2, , n ⎨∂x1 ⎪ ⎩g j (x) = 0; j = 1,2, , n Nh− vậy ta có (n+m) ph−ơng trình dùng để xác định (n+m) ẩn: x1, ,xn, λ1, ,λm. Ví dụ: với bài toán: 2 2 2 f(x) = 2 x1 + 4x2 + x3 → Min g1(x) = x1 + 2x2 + x3 - 2 = 0 g2(x) = x1 + x2 - x3 - 1 = 0 Hàm Lagrange có dạng: 2 2 2 L(x,λ) = 2 x1 + 4x2 + x3 +λ1(x1 + 2x2 + x3 - 2) + λ2 (x1 + x2 - x3 -1) Ta có các ph−ơng trình: ∂L = 4x1 = λ1 + λ2 = 0 ∂x1 ∂L = 8x2 + 2λ1 + λ2 = 0 ∂x2 ∂L = 2x3 + λ1 − λ2 = 0 ∂x3 x1 + 2x2 + x3 - 2 = 0 x1 + x2 - x3 -1 = 0 Khi giải các ph−ơng trình trên ta đ−ợc: λ1 = - 8/5 ; λ2 = - 8/7 Nghiệm dùng x* = [0,685; 0,542 ; - 0,226]T. Hàm mục tiêu f(x*) = 2,164. Nhận xét: 53