TRONG HỆ THỐNG THỦY LỢI
7.1. GIỚI THIỆU CHUNG VỀ TOÁN TỐI ƯU
Lịch sử hình thành và phát triển toán tối ưu và phương pháp tính có thể được lược thuật tóm tắt dưới đây.
Những người đã đặt nền móng cho toán tối ưu phải kể đến Newton, Lagrange và Cauchy. Newton và Leibnitz đã đặt nền tảng cho phương pháp vi phân giải tích trong khi Bernoulli, Euler, Lagrange và Weirstrass đã xây dựng nền móng cho phương pháp tính toán sai số, độ biến động và giải quyết vấn đề cực tiểu của hàm số. Lagrange có công trong việc đi đầu giải quyết phương pháp tính của bài toán tối ưu có ràng buộc với những số nhân phát sinh. Cauchy là người đầu tiên công bố nghiên cứu ứng dụng phương pháp độ giảm dốc nhất để giải quyết các bài toán cực tiểu không ràng buộc. Mặc dù những đóng góp trên đây rất sớm, nhưng cho mãi đến giữa thế kỷ thứ 20 với sự trợ giúp đắc lực của máy tính số thì toán tối ưu mới thực sự phát triển với nhiều kỹ thuật và phương pháp mới và được áp dụng rộng rãi vào thực tế.
Mãi đến những năm 1960 thì phương pháp số để giải quyết bài toán tối ưu không ràng buộc mới được phát triển ở nước Anh. Còn phương pháp Đơn hình được Dantzig xây dựng trong năm 1947 để giải các bài toán Quy hoạch tuyến tính, năm 1957 Bellman công bố nguyên tắc tối ưu để giải các bài toán quy hoạch động đã đặt kim chỉ nam để xây dựng thuật toán giải các bài toán tối ưu có ràng buộc.
Năm 1951 Kuhn và Tucker đã đưa ra những điều kiện cần và đủ để có nghiệm tối ưu của bài toán quy hoạch và do đó đã đặt nền móng để giải quyết các bài toán Quy hoạch phi tuyến sau này. Đóng góp của Zoutendijk và Rosen trong những
năm 1960 cho bài toán Quy hoạch phi tuyến là rất có ý nghĩa. Mặc dù chưa có được một phương pháp độc lập để giải mọi bài toán Quy hoạch phi tuyến, nhưng những nghiên cứu của Carroll, Fiacco và McCormick đã cho phép giải quyết nhiều vấn đề khó khăn của loại bài toán này thông qua những kỹ thuật giải đã biết của toán tối ưu không ràng buộc. Trong những năm 1960 Duffin, Zener và Peterson đã xây dựng thuật toán Quy hoạch ràng buộc hình học. Cùng thời gian này Gomory đã đi tiên phong trong toán Quy hoạch nguyên, một trong những lĩnh vực được quan tâm và phát triển nhanh nhất trong toán tối ưu do nhu cầu thực tiễn đối với lĩnh vực này. Dantzig, Charnes và Cooper đã xây dựng kỹ thuật Quy hoạch xác suất và giải bài toán thông qua giả thiết về các thông số phụ thuộc và phân bố tần suất.
Theo yêu cầu ngày càng cao của xã hội và mong muốn của con người, bài toán tối ưu nhằm một lúc thỏa mãn nhiều hơn một mục tiêu đã được phát triển với tên gọi Quy hoạch tối ưu đa mục tiêu. Người đề ra bài toán đa mục tiêu sớm nhất là nhà kinh tế học V. Pareto với khái niệm "hiệu quả Pereto" nổi tiếng. Vào năm 1944, Von Newmann và Morgenstern đã xây dựng quyết sách đa nhân dựa trên lý thuyết Đối sách. Một thuật toán nổi tiếng để giải quyết một trong các dạng của bài toán tối ưu đa mục tiêu là Quy hoạch hướng đích, thuật toán này lúc đầu được xây dựng cho bài toán tuyến tính do Charnes và Cooper đề xướng trong năm 1961.
Khái niệm cơ bản của lý thuyết trò chơi được Neumann đặt cơ sở từ năm 1928 và từ đó nó được áp dụng để giải quyết các vấn đề kinh tế, quốc phòng và gần đây là các bài toán thiết kế kỹ thuật (Rao, 1996).
Trong thập kỷ qua đã phát triển thêm một số dạng mới về thuật toán quy hoạch như: Thuật toán di truyền, thuật toán tối ưu mô phỏng và phương pháp hệ thần kinh cơ sở. Thuật toán di truyền là phương pháp tìm kiếm dựa trên nguyên lý cơ học của quá trình chọn lọc tự nhiên và di truyền trong sinh học. Thuật toán tối ưu mô phỏng lại dựa theo quá trình tối ưu của các chất rắn. Còn phương pháp hệ thần kinh cơ sở thì giải quyết vấn đề dựa trên năng lượng tiêu hao hiệu quả của hoạt động của hệ thần kinh trung tâm.
7.1.2. Dạng chung của bài toán tối ưu cơ bản 1. Bài toán tìm cực tiểu và cực đại
Toán tối ưu là quá trình toán học nhằm tìm và nhận được lời giải hay kết quả tốt nhất của một bài toán trong các điều kiện ràng buộc của nó. Mục tiêu tìm kiếm của bài toán tối ưu trong thực tế thường là: tối thiểu (Minimum) nguồn lực hay chi phí, hoặc tối đa (Maximum) lợi nhuận hay lợi ích có thể. Trong rất nhiều trường hợp có thể thấy ngay rằng nghiệm X* cho kết quả Minimum của hàm f(X) thì cũng với X* đó sẽ cho Maximum của hàm -f(X). Do đó trong toán tối ưu người ta thường chỉ nghiên cứu dạng bài toán tìm cực tiểu hoặc ngược lại.
2. Bài toán tối ưu tổng quát và các khái niệm
Mọi bài toán tối ưu đều có thể được diễn giải dưới dạng tổng quát sau:
Hàm mục tiêu cần đạt được: Min (hoặc Max) của f(X) (7.1)
Thỏa mãn các ràng buộc: gj(X)=0 (7.2)
Miền của biến quyết định: x*<xi<x* (7.3) Trong đó: x - véc tơ n biến chính (x1, x2,..., xn), n=1, ..., n;
g(x) - véc tơ m phương trình ràng buộc, j=1,...,m;
x* - véc tơ giới hạn dưới của các biến chính x;
x* - véc tơ giới hạn trên của các biến chính x;
f(X) - hàm mục tiêu được tối ưu, thường thì Max f(X) tương đương
với Min -f(X) và ngược lại.
Nếu bài toán được mô tả dầy đủ như trên thì được gọi là bài toán tối ưu có ràng buộc, khi bài toán không có ràng buộc (7.3) thì được gọi là bài toán tối ưu không ràng buộc (Rao, 1996).
Khi bài toán tối ưu được thiết lập và diễn giải dưới dạng đầy đủ, thì tồn tại một số khái niệm và định nghĩa có liên quan như sau:
(a) Biến chính (hay biến quyết định)
Biến chính hay véc tơ biến chính là hai cách gọi ma trận n biến quyết định mà bài toán tối ưu phải tìm nhằm đạt được mục tiêu đặt ra và thỏa mãn các điều kiện ràng buộc kèm theo. Như vậy thực chất của bài toán tối ưu là đi tìm ma trận (véc tơ) nghiệm:
1 2
n
x X x
. x
⎧ ⎫⎪ ⎪
= ⎨ ⎬⎪ ⎪
⎪ ⎪⎪ ⎪
⎩ ⎭
Thỏa mãn các điều kiện ràng buộc và cho giá trị tối ưu của hàm mục tiêu.
Biến chính nhận các giá trị trong khoảng từ x* đến x*, khoảng [x*, x*] này được gọi là miền biến thiên của biến chính.
(b) Ràng buộc
Trong rất nhiều bài toán, biến chính không thể nhận giá trị bất kỳ mà chúng bị giới hạn và buộc phải thỏa mãn các điều kiện hay yêu cầu nào đó. Các điều kiện và yêu cầu giới hạn trên đây được gọi chung là Điều kiện ràng buộc hay ngắn gọn hơn là Ràng buộc.
Ràng buộc thể hiện các giới hạn của hệ thống và của hàm mục tiêu được gọi là Ràng buộc mục tiêu. Ràng buộc biểu thị giới hạn về vật lý của các biến chính được gọi là Ràng buộc hình học hay ràng buộc buộc chặn.
(c) Hàm mục tiêu
Nhiệm vụ của bài toán tối ưu là so sánh lựa chọn phương án tốt nhất trong các phương án có thể của biến chính. Muốn vậy phải có một tiêu chí hay chỉ tiêu để so sánh các phương án nghiệm đã nêu, thông thường tiêu chí này được thể hiện dưới dạng hàm số của các biến chính, hàm này được định nghĩa là hàm mục tiêu.
Loại và dạng hàm mục tiêu phụ thuộc vào bản chất tự nhiên của bài toán tối ưu đồng thời phụ thuộc vào người lập bài toán. Cần chú ý rằng việc xác định hàm mục tiêu được chọn là bước quan trọng nhất trong toàn bộ quá trình giải một bài toán tối ưu.
Nếu bài toán tối ưu nhằm giải quyết một tiêu chí và chỉ đưa ra một hàm mục tiêu thì đó là bài toán tối ưu Đơn mục tiêu. Khi bài toán tối ưu đồng thời phải thỏa mãn từ hai mục tiêu trở lên thì bài toán thuộc Tối ưu đa mục tiêu (Rao, 1996).
7.1.3. Phân loại toán tối ưu
Có nhiều cách phân loại bài toán tối ưu, có thể dựa vào đặc điểm của các ràng buộc, dựa vào bản chất tự nhiên của biến quyết định, phân loại dựa vào cấu trúc vật lý của bài toán, dựa vào đặc điểm giá trị của biến chính, phân loại dựa vào số lượng mục tiêu,... Sau đây là các cách phân loại thường gặp nhất dựa trên tính chất, đặc điểm của hàm mục tiêu và điều kiện ràng buộc.
Mỗi bài toán tối ưu đều bao gồm hai bộ phận là: Hàm mục tiêu và các ràng buộc. Hàm mục tiêu thể hiện mục tiêu về khả năng của hệ thống, còn các ràng buộc thể hiện những điều kiện và giới hạn mà các biến chính phải tuân theo.
Nghiệm của bài toán tối ưu là tập hợp các phương án biến chính thỏa mãn các ràng buộc. Vùng nghiệm của bài toán tối ưu là miền chứa các nghiệm của bài toán.
Nghiệm tối ưu là tập hợp một phương án biến chính thỏa mãn các ràng buộc và cho giá trị tối ưu của hàm mục tiêu.
Tùy thuộc vào tính chất và đặc điểm của hàm mục tiêu và các điều kiện ràng buộc mà người ta có thể chia bài toán tối ưu thành những loại sau:
(1) Tuyến tính hay Phi tuyến (2) Xác định hay Không xác định (3) Tĩnh hay Động
(4) Liên tục hay Rời rạc
(5) Thông số đồng nhất hay Thông số phân bố
Bài toán Tuyến tính tức là hàm mục tiêu cùng các ràng buộc của nó là tuyến tính, còn bài toán Phi tuyến có các ràng buộc là phi tuyến còn hàm mục tiêu là phi
tuyến hoặc tuyến tính. Với bài toán Xác định thì các thông số hay hệ số được gán giá trị xác định, trong khi đó ở bài toán Không xác định thì các thông số lại nhận các giá trị ngẫu nhiên. Các bài toán Tĩnh thì rõ ràng không xét đến yếu tố thời gian thay đổi còn các bài toán Động lại quan tâm và xem xét đến yếu tố thời gian. Bài toán liên tục có các biến và thông số của nó nhận các giá trị đồng nhất đối với toàn bộ hệ thống, còn bài toán phân bố thì biến và thông số lại nhận những giá trị biến đổi từ vị trí này sang vị trí khác của hệ thống (Hillier, et al., 1995).
Thông thường phương pháp được lựa chọn để giải bài toán tối ưu trong thủy lợi nói riêng và bài toán tối ưu nói chung phụ thuộc vào ba yếu tố là:
- Loại của hàm mục tiêu;
- Loại của các ràng buộc;
- Số lượng các biến chính và số lượng ràng buộc.
Dựa vào ba yếu tố trên đây chúng ta có thể định dạng được loại bài toán tối ưu và phương pháp giải phù hợp (Mays, et al., 1992).
7.1.4. Một số lý thuyết tối ưu được đề cập trong chương này
Toán tối ưu được phân chia thành nhiều loại, về cơ bản, tất cả các loại đã được đề cập trên đây đều có thể được áp dụng trong lĩnh vực thủy lợi, tuy nhiên có một số loại tối ưu được ứng dụng đặc biệt rộng rãi trong mảng thiết kế, vận hành và phân tích kinh tế tài chính các dự án thủy lợi. Đó là:
(1) Quy hoạch tuyến tính.
(2) Quy hoạch động.
(3) Quy hoạch phi tuyến.
(4) Quy hoạch đa mục tiêu.
Trong chương này sẽ đề cập tới bốn loại toán tối ưu nêu trên.