CHƯƠNG 1: TỔNG QUAN VỀ LĨNH VỰC NGHIÊN CỨU VÀ KHU VỰC NGHIÊN CỨU 1. Tổng quan về lĩnh vực nghiên cứu 1. Phân loại tổng quan các mô hình tối ưu Hiện nay tồn tại khá nhiều các phương pháp tối ưu hoá có phạm vi ứng dụng khác nhau. Trong các bài toán kỹ thuật người ta cố gắng đưa các bài toán tối ưu về các dạng chuẩn tắc đã có và có thể giải được.
Để làm được điều đó cần có những giả thiết về những điều kiện giản hoá sao cho bản chất vật lý của bài toán được bảo toàn một cách tương đối. Có thể có một số mẫu bài toán tối ưu thích hợp khi thiết kế và điều khiển hệ thống nguồn nước. Do đó trong đồ án chỉ trình bày một số phương pháp đơn giản nhưng điển hình cho các dạng áp dụng được. Bài toán tối ưu tổng quát Bài toán tối ưu tổng quát có thể mô tả như sau: Cần tìm cực trị hàm mục tiêu có dạng: F(X) → min (max) (1 - 1) Với hệ các biểu thức ràng buộc: gj (X) ≤ bj, với j = 1, 2,…, m (1 - 2) Hệ (1 – 1) và (1 – 2) có thể viết dưới dạng đầy đủ: F(x1, x2,…, xi,…, xn) → min (max) (1 – 3) Với các ràng buộc: g1 (x1, x2,…, xi,…, xn) ≤ b1 g2 (x1, x2,…, xi,…, xn) ≤ b2 ………………………………… (1 – 4) gj (x1, x2,…, xi,…, xn) ≤ bj ………………………………… gm (x1, x2,…, xi,…, xn) ≤ bm Với các biến của hàm số là véc tơ có dạng: Nghiên cứu ứng dụng phương pháp quy hoạch tuyến tính trong bài toán phân bổ tài nguyên nước tỉnh Cao Bằng 12 X = (x1, x2,…, xn) (1 - 5) Nghiệm tối ưu của bài toán tối ưu là véc tơ nghiệm X* = (x1*, x2*,…, xn*) (1 - 6) 1.
Bài toán quy hoạch tuyến tính Bài toán (1 – 1), (1 – 2) được gọi là tuyến tính, nếu hàm mục tiêu và các ràng buộc đều là hàm tuyến tính đối với các đối số của véc tơ X = (x1, x2,…., xm), tức là: n F ( X ) = ∑ ci xi → min (max) (1 – 7) i =1 n Với ràng buộc ∑ a x ≤ b với j = 1, 2,…, m; i =1 ji i j (1 – 8) Và xi ≥ 0 với i = 1, 2,…, n 1. Quy hoạch tuyến tính 1. Khái niệm và các ví dụ về bài toán quy hoạch tuyến tính (QHTT) Quy hoạch tuyến tính là môn toán học nghiên cứu phương pháp tìm giá trị nhỏ nhất (min) hoặc lớn nhất (max) của một hàm tuyến tính (hàm mục tiêu) theo một số biến, thỏa 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. Hai dạng cơ bản của quy hoạch tuyến tính 1.
Dạng chính tắc Nếu hàm mục tiêu và ràng buộc (1 – 1) và (1 – 2) là các biểu thức tuyến tính đối với các biến số, ta có mô hình tối ưu là tuyến tính đối với các biến số: Mô hình tuyến tính được gọi là chính tắc nếu các ràng buộc là đẳng thức. Ta có hàm mục tiêu của mô hình tuyến tính là: F(X) c1x1 + c2x2 + … + cixi + …+ cnxn → min (1 – 9) Với ci là hằng số với biến thứ i. Với ràng buộc là: gj(X) = aj1x1 + aj2x2 + … + ajmxm = bj; j = 1, m (1 – 10) Nghiên cứu ứng dụng phương pháp quy hoạch tuyến tính trong bài toán phân bổ tài nguyên nước tỉnh Cao Bằng 13 và xi ≥ 0 với i = 1, 2,…, n. Với bj là hằng số với ràng buộc thứ j; aji là các hằng số.
Trong trường hợp bài toán cần tìm cực đại (max), phải nhân hàm mục tiêu với (-1) để đưa về bài toán tối ưu dạng chính tắc. Bài toán tìm cực đại (1 – 2) có dạng: F(X) c1x1 + c2x2 + … + cixi + …+ cnxn → max (1 – 11) Với ci là hằng số với biến thứ i. Với ràng buộc là: gj(X) = aj1x1 + aj2x2 + … + ajmxm = bj; j = 1, m (1 – 12) và xi ≥ 0 với i = 1, 2,…, n. được đưa về dạng chính tắc với hàm mục tiêu: max F(X) = min (-F(X)) tức là: F1(X) = -F(X) = -c1x1 – c2x2 - … - cixi - … - cnxn → min 2.
Dạng chuẩn tắc Dạng chuẩn tắc là dạng mà ràng buộc là bất đẳng thức, tức là: gj(X) = aj1x1 + aj2x2 + … + ajixi+ … + ajnxn ≤ bj; j = 1, m (1 – 13) và xi ≥0 với i = 1, 2,…, n. Đưa bài toán quy hoạch tuyến tính về dạng chuẩn tắc và dạng chính tắc + Nếu ràng buộc có dạng gj(X) ≥ bj: Nhân 2 vế của biểu thức ràng buộc với (- 1), đưa bài toán về dạng chuẩn với ràng buộc dạng (1 - 2). + Đưa bài toán chuẩn tắc về dạng chính tắc: Bài toán dạng chuẩn có thể đưa về dạng chính tắc bằng cách thêm các biến phụ vào vế trái của các bất đẳng thức. Có m ràng buộc bất đẳng thức sẽ có m biến phụ.
Do đó dạng chính tắc mới sẽ có n + m nghiệm. Ta có: gj (X) + xn+j = 0; j = 1, m (1 – 14) Nghiên cứu ứng dụng phương pháp quy hoạch tuyến tính trong bài toán phân bổ tài nguyên nước tỉnh Cao Bằng 14 trong đó: xn+j là biến phụ; và xi ≥ 0 với i =1, 2,. Định lý cơ bản và các định nghĩa về quy hoạch tuyến tính 1. Định lý cơ bản của quy hoạch tuyến tính Định lý: (Phát biểu cho dạng chính tắc): Phương án tối ưu quy hoạch 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ác biến còn lại có giá trị không.
Nếu bài toán tối ưu tuyến tính dạng chính tắc có nghiệm thì nghiệm của bài toán sẽ nằm ở các điểm cực biên: các đỉnh tam giác (đối với bài toán phẳng) và đỉnh các đa giác (đối với bài toán 3 chiều)…Các phương pháp tìm nghiệm của bài toán thường là các phép thử dần tại các điểm cực biên. Giả sử đã dò tìm ở tất cả những điểm cực biên mà không tìm được một trường hợp nào có xi ≥ 0 với mọi i thì bài toán là vô nghiệm. Khái niệm về phương án cơ sở chấp nhận được Biến cơ sở (BCS) và biến tự do (BTD) Giả sử ta xét một bài toán tối ưu chính tắc có n biến số, với số phương trình ràng buộc đẳng thức là m. Ta gọi: Tập hợp các biến được chọn tùy ý với giả thiết là xi ≥ 0, với i = 1→ m, trong đó m là số các phương trình ràng buộc được gọi các biến cơ sở.
Tập hợp các biến còn lại xj với j≠i, j = (n-m) → n được gọi là biến tự do. Phương án cơ sở là phương án mà các biến tự do được chọn bằng không, tức là giả định xj = 0 với mọi j thuộc biến tự do. Giá trị của các biến cơ sở được xác định theo thủ tục sau: Chọn biến cơ sở của bài toán Giả định các giá trị của biến tự do bằng không xj = 0 với mọi j thuộc biến tự do. Nghiên cứu ứng dụng phương pháp quy hoạch tuyến tính trong bài toán phân bổ tài nguyên nước tỉnh Cao Bằng 15 Xác định giá trị của biến cơ sở bằng cách giải hệ các phương trình ràng buộc với sau khi thay các giá trị bằng không của biến tự do vào phương trình.
Phương án cơ sở chấp nhận được Là phương án cơ sở có các biến cơ sở nhận các giá trị dương. Giải bài toán quy hoạch tuyến tính 1. Phương pháp đồ thị Phương pháp đồ thị được dùng khi số biến số ≤ 3. Về phương pháp này có thể tham khảo ở nhiều tài liệu chuyên khảo.
Ta xem xét bài toán phẳng qua một ví dụ: Bài toán: Tìm nghiệm tối ưu X* = (x1*, x2*) sao cho hàm mục tiêu: Z = c1x1 + c2x2 → max (1 – 15) Các ràng buộc: a11x1 + a12x2 ≥ b1 a21x1 + a22x2 ≥ b2 xi ≥ 0; i = 1, 2 (1 – 16) Cách giải Cách giải bài toán phẳng được tiến hành như sau: Vẽ miền chấp nhận được (miền D mà X thỏa mãn ràng buộc 1 – 16) xem Hình 1.1 + Nếu ràng buộc là đẳng thức thì miền chấp nhận được là điểm A, giao của đường N1M1 và N2M2. + Nếu ràng buộc 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 và AN2. Vẽ các đường cùng mục tiêu (đường mức): z 0 c1 + Cho một giá trị cụ thể Z = Z0. Vẽ đường x 2 = − x1 c1 c 2 Nghiên cứu ứng dụng phương pháp quy hoạch tuyến tính trong bài toán phân bổ tài nguyên nước tỉnh Cao Bằng 16 + 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 điểm “0”. Tìm nghiệm tối ưu: + Di chuyển đường Z0 (theo giá trị Z0) xác định được nghiệm cực đại tại A + Nếu đường cùng mục tiêu tiếp xúc tại 1 đỉnh thì nghiệm tối ưu là đơn trị. + Nếu đường cùng mục tiêu tiếp xúc tại 2 đỉnh (1 cạnh) thì nghiệm tối ưu là đa trị.
+ Nếu miền chấp nhận được có dạng khác (Hình 1.2) thì tọa độ điểm A xác định giá trị cực tiểu.2 Trường hợp mở rộng: Đối với bài toán có n biến x1, x2,…, xn với m ràng buộc. + Nghiệm tối ưu là tọa độ của một đỉnh hay nhiều đỉnh miền cho phép. Miền đa diện là một đa diện lồi (n-m) chiều. + Nghiệm đơn trị nếu có 1 đỉnh tiếp xúc với mặt cùng mục tiêu.
+ Nghiệm đa trị nếu có k đỉnh (k > 1) tiếp xúc với mặt mục tiêu, tạo thành 1 đơn hình (k – 1) chiều. Đó là cơ sở của phương pháp đơn hình. Phương pháp đơn hình Phương pháp đơn hình là phương pháp cơ bản nhất khi giải các bài toán quy hoạch tuyến tính. Phương pháp do G.
Nghiên cứu ứng dụng phương pháp quy hoạch tuyến tính trong bài toán phân bổ tài nguyên nước tỉnh Cao Bằng 17 Nội dung của phương pháp như sau: 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 đến nghiệm tốt hơn tức là đi dần đến nghiệm tối ưu. Cơ sở của phương pháp tính thử dần: Trong đồ án này chỉ nêu nguyên tắc và các bước tính toán. Cơ sở cho việc tìm nghiệm có thể tham khảo các sách chuyên khảo.