Dđiều kiện để học môn tối ưu hóa năm 2024
|
Bài toán tối ưu là bài toán tìm cực tiểu hoặc cực đại của hàm mục tiêu tương ứng với một tập ràng buộc (thể hiện các khả năng lựa chọn của bài toán). Hàm mục tiêu cho phép so sánh các nghiệm ứng viên để chọn ra giá trị tốt nhất. 1. Mô hình quy hoạch tuyến tính 1.1. Các bước cần thiết khi áp dụng phương pháp mô hình hoá − Trước hết phải khảo sát, phát hiện vấn đề cần giải quyết. − Phát biểu các điều kiện ràng buộc, mục tiêu của bài toán dưới dạng định tính. Sau đó lựa chọn các biến quyết định / các ẩn số và xây dựng mô hình định lượng (còn gọi là mô hình toán học). − Thu thập số liệu, xác định phương pháp giải quyết. − Định ra quy trình giải / thuật giải. Có thể giải mô hình bằng cách tính toán thông thường. Đối với các mô hình lớn, gồm nhiều biến và nhiều điều kiện ràng buộc cần lập trình và giải mô hình trên máy tính. − Đánh giá kết quả. Trong trường hợp phát hiện thấy có kết quả bất thường hoặc kết quả không phù hợp với thực tế, cần kiểm tra và chỉnh sửa lại quy trình giải hoặc mô hình. − Triển khai các phương án tìm được trên thực tế. Các thuật ngữ sau thường gặp khi áp dụng phương pháp mô hình hoá: − Ứng dụng toán / Toán ứng dụng (Mathematical Applications hay Applied Mathematics). − Vận trù học (Operations Research viết tắt là OR). − Khoa học quản lí (Management Science viết tắt là MS) 1.2. Mô hình quy hoạch tuyến tính Phát biểu mô hình Với mục đích tìm hiểu bước đầu, xét mô hình toán học sau đây, còn gọi là mô hình quy hoạch tuyến tính hay bài toán quy hoạch tuyến tính (BTQHTT), mà trong đó chúng ta muốn tối ưu hoá (cực đại hoá hay cực tiểu hoá) hàm mục tiêu: z = c 1 x 1 + c 2 x 2 + c n x n → Max (Min) 57 61 4. BÀI TOÁN VẬN TẢI 62 4. Phát biểu bài toán vận tải 4. Các tính chất của bài toán vận tải 4. Phương pháp phân phối giải bài toán vận tải 62 66 68 4. Phương pháp thế vị giải bài toán vận tải 72 4. Cơ sở của phương pháp phân phối và phương pháp thế vị 74 BÀI TẬP CHƯƠNG III 78 CHƯƠNG IV. QUY HOẠCH NGUYÊN 81
88 88 3. GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN BẰNG QUY HOẠCH ĐỘNG 90 3. Bài toán người du lịch 90 3. Quy trình tính toán tổng quát 91 3. Áp dụng quy hoạch động giải bài toán quy hoạch tuyến tính nguyên 93 3. Bài toán cái túi 3. Hợp nhất hóa các ràng buộc của bài toán quy hoạch tuyến tính nguyên 95 100 BÀI TẬP CHƯƠNG IV 103 CHƯƠNG V. MỘT SỐ PHƯƠNG PHÁP QUY HOẠCH PHI TUYẾN 105
107 108 2. MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN QUY HOẠCH PHI TUYẾN KHÔNG RÀNG BUỘC 109 2. Phương pháp đường dốc nhất 109 2. Phương pháp Newton 2. Phương pháp hướng liên hợp 111 113 3. THIẾT LẬP ĐIỀU KIỆN TỐI ƯU KUHN – TUCKER CHO CÁC BÀI TOÁN QUY HOẠCH PHI TUYẾN CÓ RÀNG BUỘC 116 3. Hàm Lagrange 116 3. Thiết lập điều kiện Kuhn – Tucker 117 4. MỘT SỐ PHƯƠNG PHÁP GIẢI QUY HOẠCH TOÀN PHƯƠNG 120 4. Bài toán quy hoạch toàn phương 120 4. Phát biểu điều kiện Kuhn – Tucker cho bài toán quy hoạch toàn phương 121
121 123
126 129 BÀI TẬP CHƯƠNG V 133 CHƯƠNG VI. MỘT SỐ VẤN ĐỀ CƠ SỞ CỦA LÝ THUYẾT QUY HOẠCH LỒI VÀ QUY HOẠCH PHI TUYẾN 136
139 144 2. ỨNG DỤNG GIẢI TÍCH LỒI VÀO BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 145 2. Điểm cực biên và hướng cực biên 145 2. Biểu diễn tập lồi đa diện qua điểm cực biên và hướng cực biên 2. Điều kiện tối ưu trong phương pháp đơn hình giải bài toán quy hoạch tuyến tính 148 150 3. CÁC TÍNH CHẤT CỦA HÀM LỒI 152 3. Các định nghĩa và tính chất cơ bản 152 3. Dưới vi phân của hàm lồi 153 3. Hàm lồi khả vi 155 3. Cực đại và cực tiểu của hàm lồi 158 4. CÁC ĐIỀU KIỆN TỐI ƯU FRITZ – JOHN VÀ KUHN – TUCKER 162 4. Bài toán tối ưu không ràng buộc 162 4. Bài toán tối ưu có ràng buộc 164 4. Điều kiện tối ưu Fritz – John 4. Điều kiện tối ưu Kuhn – Tucker 166 166 5. MỘT SỐ PHƯƠNG PHÁP HƯỚNG CHẤP NHẬN GIẢI BÀI TOÁN QUY HOẠCH PHI TUYẾN 170 5. Phương pháp hướng chấp nhận 5. Thuật toán Frank – Wolfe giải bài toán quy hoạch lồi có miền ràng buộc là tập lồi đa diện 170 172 5. Phương pháp gradient rút gọn 5. Phương pháp đơn hình lồi Zangwill 172 174 6. GIỚI THIỆU PHƯƠNG PHÁP ĐIỂM TRONG GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 177 6. Bài toán ellipsoid xấp xỉ 177 6. Một số thuật toán điểm trong 181 BÀI TẬP CHƯƠNG VI 183 TÀI LIỆU THAM KHẢO 186 Chương IBài toán tối ưu tổng quát và ứng dụng
Tối ưu hóa là một trong những lĩnh vực kinh điển của toán học có ảnh hưởng đến hầu hết các lĩnh vực khoa học – công nghệ và kinh tế – xã hội. Trong thực tế, việc tìm giải pháp tối ưu cho một vấn đề nào đó chiếm một vai trò hết sức quan trọng. Phương án tối ưu là phương án hợp lý nhất, tốt nhất, tiết kiệm chi phí, tài nguyên, nguồn lực mà lại cho hiệu quả cao. Ví dụ 1. Tìm x ∈ D = −[ 2,2, 1,8] ⊂ R 1 sao cho f(x) = x 3 – 3x + 1 → Max. Bài toán tối ưu trên có dạng cực đại hoá được giải như sau: Cho f’(x) = 3x 2 – 3 = 0, ta có các điểm tới hạn là x = –1 và x = +1. Xét giá trị hàm số f(x) tại các điểm tới hạn vừa tìm được và tại các giá trị x = –2,2 và x = 1,8 (các điểm đầu mút của đoạn [–2,2, 1,8]), ta có f(–2,2) = –3,048 , f(–
được giá trị lớn nhất đối với bài toán Max – cực đại hoá (giá trị bé nhất đối với bài toán Min
y –3, –1 0 1 1, 3 x –2, - 1, Hình I. Đồ thị hàm f(x) Điểm x = (x 1 , x 2 , ..., xn) ∈ D ⊂ Rn được gọi là phương án khả thi (hay phương án chấp nhận được hoặc phương án, nếu nói vắn tắt) của bài toán tối ưu: Max (Min) f(x), với x ∈ D ⊂ Rn. Miền D được gọi là miền ràng buộc. Các toạ độ thành phần của điểm x được gọi là các biến quyết định, còn x cũng được gọi là véc tơ quyết định. Xét bài toán cực đại hoá: Max f(x), với x ∈ D ⊂ Rn. Điểm x* = ( x , x , ..., x 1 ∗ 2 ∗ n∗ )∈ Rn đượcgọi là điểm tối ưu (hay phương án tối ưu) toàn cục nếu x* ∈ D và f(x*) ≥ f(x), ∀x ∈ D. Điểm x ∈ Rn được gọi là điểm tối ưu (hay phương án tối ưu) địa phương nếu x ∈ D và tồn tại một lân cận Nε đủ nhỏ của điểm x sao cho f( x ) ≥ f(x), ∀x ∈ Nε ∩ D. Đối với bài toán cực tiểu hoá Min f(x), với x ∈ D ⊂ Rn, điểm x* ∈ Rn được gọi là điểm tối ưu (hay phương án tối ưu) toàn cục nếu x* ∈ D và f(x*) ≤ f(x), ∀x ∈ D. Điểm x ∈ Rn được gọi là điểm tối ưu (hay phương án tối ưu) địa phương nếu x ∈ D và tồn tại một lân cận Nε đủ nhỏ của điểm x sao cho f( x ) ≤ f(x), ∀x ∈ Nε ∩ D. Dễ thấy, mọi phương án tối ưu toàn cục cũng là phương án tối ưu địa phương, trong khi đó một phương án tối ưu địa phương không nhất thiết là phương án tối ưu toàn cục. Trên hình I, điểm x = 1 chỉ là phương án tối ưu địa phương khi xét bài toán cực tiểu hoá. Ví dụ 2. Xét bài toán tối ưu sau: Max f (x) = 8x 1 + 6x 2 , với điều kiện ràng buộc x ∈ D = { (x 1 , x 2 ) ∈ R 2 : 4x 1 + 2x 2 ≤ 60; 2x 1 + 4x 2 ≤ 48, x 1 ≥ 0, x 2 ≥ 0}. Bài toán tối ưu trên đây còn được gọi là bài toán quy hoạch tuyến tính. Người ta đã chứng minh được rằng mọi phương án tối ưu địa phương của bài toán quy hoạch tuyến tính cũng đồng thời là phương án tối ưu toàn cục.
Các bài toán tối ưu, cũng còn được gọi là các bài toán quy hoạch toán học, được chia ra thành các lớp sau:
Những năm gần đây, nhiều bài toán thực tế được giải quyết bằng phương pháp mô hình hóa toán học rất thành công. Trong số các mô hình toán học đã được áp dụng có nhiều mô hình tối ưu, được giải quyết thông qua các bài toán tối ưu kinh điển. Trong trường hợp hàm mục tiêu cũng như tất cả các ràng buộc đều là các hàm tuyến tính, thì bài toán tối ưu là BTQHTT. BTQHTT có thể giải được bằng một số phương pháp tối ưu quen biết (như phương pháp đơn hình, phương pháp đơn hình cải biên hay các phương pháp điểm trong). BTQHTT đã và đang được sử dụng rộng rãi trong quy hoạch tài nguyên, quản lý sử dụng đất cũng như nhiều lĩnh vực của quản lý, kinh tế và quản trị kinh doanh. Trong trường hợp hoặc hàm mục tiêu hoặc một trong số các ràng buộc là phi tuyến, chúng ta có BTQHPT. Trong các mô hình tối ưu dựa trên BTQHPT nói chung, và trong các mô hình tối ưu trong lĩnh vực nông nghiệp nói riêng, lời giải tối ưu toàn cục có một ý nghĩa quan trọng. Chẳng hạn trong thiết kế máy nông nghiệp, sau khi dùng phương pháp phân tích hồi quy nhiều chiều, ta thường thu được hàm mục tiêu có dạng phi tuyến. Các bài toán tối ưu toàn cục cũng có thể nảy sinh trong quy hoạch kinh tế – sinh thái vùng, hay xác định cơ cấu đất canh tác – cây trồng. Bài toán đặt ra là phải tìm được lời giải tối ưu toàn cục. Có rất nhiều phương pháp giải các lớp bài toán tối ưu phi tuyến riêng biệt, nhưng chưa có phương pháp nào tỏ ra hữu hiệu cho mọi bài toán tối ưu phi tuyến, đặc biệt là cho các bài toán với một số hay tất cả các biến quyết định nhận các giá trị nguyên. Sau đây là các ví dụ minh hoạ một số ứng dụng của bài toán tối ưu. Ví dụ 3. Bài toán quy hoạch sử dụng đất (Mô hình tối ưu tuyến tính giải bài toán quy hoạch sử dụng đất trên địa bàn xã Đông Dư, huyện Gia Lâm, tỉnh Hà Nội) Chúng ta xét mô hình tối ưu với mục tiêu cần cực đại hoá là hiệu quả kinh tế. Để thiết lập mô hình, trước hết chọn các biến quyết định. Dựa vào kết quả các dữ liệu đã thu được, ta chọn các biến quyết định như sau: xj với j = 1, 2, ..., 18 là diện tích các loại cây trồng, đơn vị tính là ha (theo thứ tự là: lúa xuân, lúa mùa, ngô xuân, ngô đông, ngô bao tử đông, lạc xuân, đậu xanh xuân, đậu tương đông đất chuyên màu, đậu tương đông đất ba vụ, dưa chuột xuân, dưa chuột bao tử, mướp đắng xuân, rau mùi tàu, rau gia vị, đậu cô ve đông, ớt xuân, cà chua xuân, cà chua đông), x 19 là diện tích ao hồ thả cá, xj với j = 20, ..., 23 là số đầu vật nuôi trong năm (trâu, bò, lợn, gia cầm). Còn x 24 là số công lao động thuê ngoài, x 25 là lượng tiền vốn vay ngân hàng, đơn vị tính là nghìn đồng. Lúc đó chúng ta có BTQHTT sau với 33 ràng buộc (chưa kể điều kiện không âm của các biến). Hiệu quả kinh tế cần cực đại hóa là: f(x) = 4306,14x 1 + 4168,73x 2 + 3115,21x 3 + 3013,11x 4 + 4158,68x 5 + 4860,91x 6 + 4295,31x 7 + 3706,11x 8 + 3788,25x 9 + 12747,31x 10 + 12752,96x 11 + 12064,81x 12 + 79228,88x 13 + 35961,31x 14 + 10823,91x 15 + 7950,16x 16 + 7928,06x 17 + 5738,46x 18 + 11129,50x 19 + 429,00x 20 + 674,00x 21 + 219,50x 22 + 11,10x 23 – 15,50x 24
Các ràng buộc hay các điều kiện hạn chế được định lượng như sau: x 1 ≤ 80,88; x 2 ≤ 75,78; x 3 ≤ 64,89; x 4 ≤ 64,89; x 5 ≤ 10,50; x 6 ≤ 64,89; x 7 ≤ 64,89; x 8 ≤ 16,50; x 9 ≤ 45,30; x 10 ≤ 5,50; x 11 ≤ 8,50; x 12 ≤ 6,80; x 13 ≤ 13,70; x 14 ≤ 14,50; x 15 ≤ 4,80; x 16 ≤ 4,50; x 17 ≤ 4,20; x 18 ≤ 10,20; x 19 ≤ 33,11; x 20 ≤ 40,00; x 21 ≤ 180,00; x 22 ≤ 4280; x 23 ≤ 18800; x 5 + x 9 + x 11 + x 13 + x 18 ≤ 45,30; x 3 + x 6 + x 7 + x 10 + x 12 + x 16 + x 17 ≤ 64,89; x 4 + x 8 + x 14 + x 15 ≤ 64,89; x 1 + x 13 ≤ 80,88; x 2 + x 13 ≤ 75,88; 205,5x 1 + 150x 3 + 75,75x 4 + 75x 5 + 225,5x 6 + 221,5x 7 + 102,7x 8 + 100,75x 9 + 360 x 10 + 140x 11 + 385x 12 + 1833,6x 13 + 1446,3x 14 + 210,25 x 15 + 410,5x 16 + 360,5 x 17 + 176x 18 + 67x 19 + 20x 20 + 16x 21 + 9x 22 + 0,3x 23 – x 24 ≤ 226149,00; 201,5x 2 + 150x 3 + 75,25x 4 + 102,7x 8 + 100,75x 9 + 140x 11 + 2475,4x 13 + 1446,3x 14 + 210,25x 15 + 176x 18 + 58x 19 + 16x 20 + 12x 21 + 7x 22 + 0,2x 23 – x 24 ≤ 152190,00; 2871,89x 1 + 2691,89x 2 + 2243,62x 3 + 2243,66x 4 + 3630,89x 5 + 4780,06x 6 + 2229,11x 7 + 2401,41x 8 + 2326,88x 9 + 16440,61x 10 + 16058,39x 11 + 15960,61x 12 + 68494,59x 13 + 23146,11x 14
3,5x 5 + 8x 6 + 3,5x 7 + 4,1x 8 + 3,5x 9 + 4,16x 10 + 3,5x 11 + 4x 12 + 12,1x 13 + 14,4x 14 + 3,42x 15
Các biến đều phải thỏa mãn điều kiện không âm: xj ≥ 0, ∀j = 1,. Bằng cách áp dụng phương pháp đơn hình để giải BTQHTT có thể tìm được phương án tối ưu của mô hình trên như sau: x 1 = 67,18; x 2 = 62,18; x 3 = 25,19; x 4 = 45,59; x 5 = 10,50; x 6 = 18,7; x 9 = 2,40; x 10 = 5,50; x 11 \= 8,50; x 12 = 6,80; x 13 = 13,70; x 14 = 14,50; x 15 = 4,80; x 16 = 4,50; x 17 = 4,20; x 18 = 10,20; x 19 = 33,11; x 20 = 40,00; x 21 = 180; x 22 = 4280; x 23 = 18800; x 25 = 2368646. Hiệu quả kinh tế cực đại đạt được là 4325863 (nghìn đồng). Ví dụ 4. Bài toán cực đại hoá giá trị sản xuất (Mô hình tối ưu phi tuyến giải bài toán cực đại hoá giá trị sản xuất trên một héc ta nuôi cá tại huyện Văn Giang, tỉnh Hưng Yên) Sử dụng số liệu điều tra 112 hộ nuôi cá vùng đồng trong đê thuộc 4 xã thuộc huyện Văn Giang, Hưng Yên, để tìm phương trình hồi quy mũ, chúng ta nhận được hàm giá trị sản xuất (dạng Cobb – Douglas) chính là hàm mục tiêu cần cực đại hoá sau đây: z = f(x) = 19,375 x10,236 x20,104 x30,096 x40,056 x50,056 e0,168 x6 e0,066 x7 → Max trong đó: z : giá trị sản xuất bình quân 1 ha 1 năm (triệu đồng / ha), x 1 : chi phí giống bình quân 1 ha 1 năm (triệu đồng / ha), x 2 : chi phí thức ăn bình quân 1 ha 1 năm (triệu đồng / ha), x 3 : chi phí lao động bình quân 1 ha 1 năm (triệu đồng / ha), x 4 : chi phí khấu hao và thuê đất bình quân 1 ha 1 năm (triệu đồng / ha), x 5 : các chi phí khác bình quân 1 ha 1 năm (triệu đồng / ha), x 6 , x 7 : các biến 0 – 1 giả định về hình thức nuôi, x 6 = 1 đối với nuôi chuyên canh, x 6 = 0 đối với nuôi tổng hợp, x 7 = 1 với hình thức nuôi 1 loại cá chính kết hợp với các loại cá khác, Ví dụ này chỉ nêu vắn tắt một ứng dụng của mô hình tối ưu phi tuyến một mục tiêu trong việc tìm nghiệm của hệ phương trình phi tuyến phát sinh trong quá trình tính toán một số thông số hình học và động học của cơ cấu sàng phân loại dao động (cần chú ý rằng nhiều phương pháp tính toán thông dụng khác của giải tích số đã tỏ ra không hiệu quả): r cosφ 1 + v cosφ 2 + v 3 //cosφ 3 + v 4 cosφ 4 – xC1 = 0, r sinφ 1 + v sinφ 2 + v // 3 sinφ 3 + v 4 sinφ 4 – yC1 = 0, r cosφ 1 + v cosφ 2 + v 3 /cos(φ 3 – α) + v 5 cosφ 5 – xD1 = 0, r sinφ 1 + v sinφ 2 + v / 3 sin(φ 3 – α) + v 5 sinφ 5 – yD1 = 0. Trong hệ phương trình phi tuyến trên các thông số đã biết là: r = 0,05m; v = 0,30m; v 3 //= 0,15m; v / 3 = 1,075m; v 3 = 1,025m; v 4 = 0,50m; v 5 = 0,40m; xC1 = 0,365m; yC1 = 0,635m; xD1 = 1,365m; yD1 = 0,635m; α = π/8. Để giải hệ phương trình phi tuyến khi φ 1 = kπ/8 (k = 0, ..., 9), chúng ta cần cực tiểu hoá hàm mục tiêu sau: z = (r cosφ 1 + v cosφ 2 + v / 3 /cosφ 3 + v 4 cosφ 4 – xC1) 2 + (r sinφ 1 + v sinφ 2 + v 3 //sinφ 3 + v 4 sinφ 4 – yC1) 2 + (r cosφ 1 + v cosφ 2 + v / 3 cos(φ 3 – α) + v 5 cosφ 5 – xD1) 2 + (r sinφ 1 + v sinφ 2 + / v 3 sin(φ 3 – α) + v 5 sinφ 5 – yD1) 2 → min Kết quả tính toán được tổng hợp trong bảng I với zmin = 0. Bảng I. Kết quả tính toán giá trị các thông số của sàng phân loại φ 1 ∈ [0,2 π] φ 2 ∈ [0, π] φ 3 ∈ [0, π] φ 4 ∈ [0, π] φ 5 ∈ [0, π] 0 0,226128 0,551311 1,783873 1, π/18 0,199269 0,550518 1,784628 1, 2 π/18 0,170835 0,550590 1,782751 1, 3 π/18 0,143343 0,550490 1,778826 1, 4 π/18 0,112669 0,552073 1,770032 1, 5 π/18 0,090986 0,551991 1,759350 1, 6 π/18 0,066036 0,553576 1,745374 1, 7 π/18 0,051284 0,554296 1,730174 1, 8 π/18 0,039053 0,555262 1,713242 1, 9 π/18 0,033773 0,556277 1,695605 1, Ví dụ 6. Bài toán thiết kế trục máy (Mô hình quy hoạch phi tuyến đa mục tiêu giải quyết bài toán thiết kế trục máy) Trong ví dụ này chúng ta đề cập tới một mô hình tối ưu phi tuyến hai mục tiêu. Mục tiêu 1 là cực tiểu hoá thể tích của trục máy: f 1 (x) = 0,785 [x 1 (6400 – x 22 ) + (1000 – x 1 ) (1000 – x 22 )] (mm 3 ), Mục tiêu 2 là cực tiểu hoá độ nén tĩnh của trục: f 2 (x) = 3,298× 10 – 3 9 7 4 8 4 1 8 4 2 2 2 1 1 x 10 4,096 10 x 10 x 10 x ####### ⎡ ⎛ ⎞ ⎤ ####### ⎢ ⎜ − ⎟ + ⎥ ⎢⎣ ⎝ × − − ⎠ − ⎥⎦ (mm/N). Ở đây, x = (x 1 , x 2 ) là véc tơ quyết định, với x 1 , x 2 là các biến quyết định sau: x 1 – độ dài phần giáp nối trục, x 2 – đường kính trong của trục. Các thông số khác đã được thể hiện trong các hàm mục tiêu f 1 (x) và f 2 (x). Vậy cần phải chọn các giá trị cho các biến quyết định (còn gọi là các biến thiết kế) x 1 , x 2 để tối ưu hoá đồng thời các mục tiêu 1 và 2 trong các điều kiện ràng buộc sau: g 1 (x) = 180 – 6 1 7 9,78 10 x 4,096 10 x ####### × ####### × − ####### ≥ 0 (1) g 2 (x) = 75,2 – x 2 ≥ 0 (1) g 3 (x) = x 2 – 40 ≥ 0 (1) g 4 (x) = x 1 ≥ 0 (1) Các điều kiện (1), (1), (1) là dễ hiểu, còn điều kiện (1) nảy sinh là do yêu cầu: Một mặt, trục máy phải chịu đựng được tới mức tối đa lực Fmax = 12000 N. Mặt khác, độ nén kết nối cho phép là 180 N/mm. Việc phát biểu bài toán tối ưu đa mục tiêu dưới dạng toán học (chính là việc lập mô hình toán học cho vấn đề phát sinh) là một khâu rất quan trọng nhằm mô tả tốt nhất hành vi của hệ thống đang được xem xét, mặt khác nhằm tìm ra được các phương pháp tối ưu hoá có hiệu quả để đi tới một phương án đủ tốt và mang lại lợi ích. Sau đây, với mục đích tìm hiểu bước đầu, việc áp dụng phương pháp tương tác người – máy tính giải bài toán tối ưu hai mục tiêu đã được thiết lập trên đây sẽ được trình bày một cách vắn tắt. Trước hết, hai mục tiêu f 1 (x) và f 2 (x) được chuyển thành hai hàm thuộc mờ phản ánh độ thoả mãn của người ra quyết định đối với từng mục tiêu. Các hàm thuộc mờ này là các hàm tuyến tính từng khúc, được viết dưới dạng giản lược như sau cho một số nút nội suy: 0 nếu f 1 ≥ 6,594× 106 = a 1 μ 1 (f 1 ) = 0,5 nếu f 1 = 4× 106 = b 1 1 nếu f 1 ≤ 2,944× 106 = c 1 , 0 nếu f 2 ≥ 0,499× 10 –3 = a 2 μ 2 (f 2 ) = 0,5 nếu f 2 = 0,450× 10 –3 = b 2 1 nếu f 2 ≤ 0,338× 10 –3 = c 2. Chương IIPhương pháp đơn hình giải bài toánquy hoạch tuyến tính
Với mục đích tìm hiểu bước đầu, xét mô hình toán học sau đây, còn gọi là mô hình quy hoạch tuyến tính hay bài toán quy hoạch tuyến tính (BTQHTT), mà trong đó chúng ta muốn tối ưu hoá / cực đại hoá hay cực tiểu hoá hàm mục tiêu: z = f(x) = c 1 x 1 + c 2 x 2 + .... + cnxn → Max (Min), với các điều kiện ràng buộc a 11 x 1 + a 12 x 2 + ... + a1nxn ≤ b 1a 21 x 1 + a 22 x 2 + ... + a2nxn ≤ b 2 ####### ... am1x 1 + am2x 2 + ... + amnxn ≤ bm x 1 , x 2 , ..., xn ≥ 0 (điều kiện không âm). Ví dụ 1. Xét BTQHTT: Max z = 8x 1 + 6x 2 , với các ràng buộc 4x 1 + 2x 2 ≤ 60 2x 1 + 4x 2 ≤ 48 x 1 , x 2 ≥ 0. Cần tìm các giá trị của các biến quyết định x 1 , x 2 để các ràng buộc được thoả mãn và hàm mục tiêu đạt giá trị lớn nhất. Bài toán này có ý nghĩa kinh tế như sau: Giả sử một xí nghiệp sản xuất hai loại sản phẩm I và II. Để sản xuất ra một đơn vị sản phẩm I cần có 4 đơn vị nguyên liệu loại A và 2 đơn vị nguyên liệu loại B, các chỉ tiêu đó cho một đơn vị sản phẩm loại II là 2 và 4. Lượng nguyên liệu dự trữ loại A và B hiện có là 60 và 48 (đơn vị). Hãy xác định phương án sản xuất đạt lợi nhuận lớn nhất, biết lợi nhuận / đơn vị sản phẩm bán ra là 8 và 6 (đơn vị tiền tệ) cho các sản phẩm loại I và II.
Phương pháp đồ thị có ý nghĩa minh họa và giúp hiểu bản chất vấn đề. Bước 1: Vẽ miền các phương án khả thi (còn gọi là miền ràng buộc) là tập hợp các phương án khả thi (các phương án, nếu nói một cách ngắn gọn). Mỗi phương án được thể hiện qua bộ số (x 1 , x 2 ), thoả mãn tất cả các ràng buộc đã có kể cả điều kiện không âm của các biến (xem hình II).
Đường thẳng này chia mặt phẳng làm hai nửa mặt phẳng. Một phần gồm các điểm (x 1 , x 2 ) thoả mãn: 4x 1 + 2x 2 ≤ 60, phần còn lại thoả mãn: 4x 1 + 2x 2 ≥ 60. Ta tìm được nửa mặt phẳng thoả mãn: 4x 1 + 2x 2 ≤ 60.
Bước 2: Trong miền (OABC) ta tìm điểm (x 1 , x 2 ) sao cho z = 8x 1 + 6x 2 đạt giá trị lớn nhất. Cách 1. Dùng đường đồng mức. Tùy theo giá trị của x 1 , x 2 mà z có những mức giá trị khác nhau. 30 4x 1 + 2x 2 = 60 O 4 8 12 x 1 2x 1 + 4x 2 = 48 x 2 3 6 15 24 A B C Hình II. Phương pháp đồ thị giải bài toán quy hoạch tuyến tính Sơ đồ khối
Phương pháp đơn hình là phương pháp số giải BTQHTT theo sơ đồ trên. Để giải ví dụ đã cho, trước hết chúng ta cần đưa BTQHTT về dạng chính tắc bằng các biến bù không âm x 3 và x 4 như sau: Max z = 8x 1 + 6x 2 + 0x 3 + 0x 4 với các ràng buộc 4x 1 + 2x 2 + x 3 = 60 2x 1 + 4x 2 + x 4 = 48 x 1 , x 2 , x 3 , x 4 ≥ 0. Chú ý. BTQHTT có dạng chính tắc là BTQHTT với các biến không âm, các ràng buộc có dấu “=”, hệ số vế phải của các ràng buộc không âm. Ngoài ra, mỗi phương trình bắt buộc phải có một biến đứng độc lập với hệ số +1. Cách lập và biến đổi các bảng đơn hình Bắt đầu Nhập dữ liệu Tìm điểm cực biên xuất phát Tìm điểm cực biên kề tốt hơn Kiểm tra điều kiện tối ưu In và lưu trữ kết quả Dừng Đúng Sai Hình II. Sơ đồ khối giải BTQHTT Để giải BTQHTT dạng chính tắc trên đây, cần lập một số bảng đơn hình như trong bảng II. Trước hết, cần điền số liệu của bài toán đã cho vào bảng đơn hình bước 1:
Bảng II. Các bảng đơn hình giải BTQHTT Hệ số hàm c 1 = 8 c 2 = 6 c 3 = 0 c 4 = 0 mục tiêu cj Biến cơ sở Phương án x 1 x 2 x 3 x 4 Bảng đơn hình bước 1 0 0 x 3 x 4 60 48 4 2 2 4 1 0 0 1 Hàng z z 0 = 0 z 1 = 0 z 2 = 0 z 3 = 0 z 4 = 0 Hàng Δj = cj – zj Δ 1 = 8 Δ 2 = 6 Δ 3 = 0 Δ 4 = 0 Bảng đơn hình bước 2 8 0 x 1 x 4 15 18 1 0 1/ 3 1/ –1/ 0 1 Hàng z z 0 = 120 z 1 = 8 z 2 = 4 z 3 = 2 z 4 = 0 Hàng Δj = cj – zj Δ 1 = 0 Δ 2 = 2 Δ 3 = –2 Δ 4 = 0 Bảng đơn hình bước 3 8 6 x 1 x 2 12 6 1 0 0 1 1/ –1/ –1/ 1/ Hàng z z 0 = 132 8 6 5/3 2/ Hàng Δj = cj – zj 0 0 –5/3 –2/ Các biến bù có giá trị lớn hơn 0 có nghĩa là các nguyên liệu loại tương ứng chưa được sử dụng hết. Ta gọi các biến x 3 và x 4 là các biến cơ sở vì chúng có giá trị lớn hơn 0 còn x 1 và x 2 là các biến ngoài cơ sở vì chúng có giá trị bằng 0. Với bài toán có hai ràng buộc, tại mỗi bước chỉ có hai biến cơ sở.
Các cột tiếp theo là các cột hệ số trong các điều kiện ràng buộc tương ứng với các biến x 1 , x 2 , x 3 và x 4 của bài toán đã cho. |
