TRONG HỆ THỐNG THỦY LỢI
7.3. LÝ THUYẾT QUY HOẠCH ĐỘNG (QHĐ)
7.3.3. Thí dụ về bài toán QHĐ
Đây là một thí dụ kinh điển minh họa bài toán QHĐ, được đề cập trong nhiều giáo trình và sách về toán tối ưu, trong cuốn sách này chúng tôi sẽ mô tả thí dụ đó dưới dạng một bài toán có ý nghĩa thực tế trong thủy lợi và kinh tế sử dụng tổng hợp nguồn nước, đó là bài toán tìm phương án tối ưu khi chuyển nước lưu vực.
Thí dụ 7.3: Trên con sông C người ta đã thiết kế một hồ chứa điều tiết dòng chảy phục vụ cấp nước cho dân cư vùng hạ lưu, tuy nhiên qua tính toán cân bằng nước hồ chứa, thấy rằng nguồn nước của bản thân lưu vực sông C không đủ phục vụ nhu cầu. Qua nghiên cứu, người ta thấy rằng ở lưu vực sông M kề cận, lượng nước thiên nhiên rất dồi dào và có thể tìm kiếm một phương án chuyển một phần nước của lưu vực sông M (từ hồ chứa 1) sang lưu vực sông C (đến hồ chứa 10).
Sông C
Sông M
Hồ chứa
Hồ chứa và trạm bơm
§uê ng p
hân thủy
10
1
2
3 4 5
6 7 8 9
Hình 7.7: Địa hình và các vị trí có thể xây dựng bể chứa và trạm bơm
1 3 6 10
2 5
4 7
8
9 2
4
3
7
5
1
3
3
4 2
4
1 3
4
4 6
6 3
4 3
Cấp bơm 1 Cấp bơm 2 Cấp tự chảy 1 Cấp tự chảy 2
Giai đoạn 1 Giai đoạn 2 Giai đoạn 3 Giai đoạn 4
Chi phí từ 8 đến 10 là 3 tỷ đồng
Hình 7.8: Sơ đồ các phương án chuyển nước và chi phí
Địa hình giữa hồ 1 trên sông M và hồ 10 trên sông C (hình 7.7) khá phức tạp, cho nên phương án dẫn nước bằng bơm và đường ống có áp là khả thi nhất. Do độ chênh địa hình khá lớn, cho nên cần ít nhất hai cấp bơm và sau đó là hai cấp tự chảy. Đối với cấp bơm thứ nhất có 3 phương án vị trí bể chứa và nhà máy bơm là 2, 3 và 4. Với cấp bơm thứ hai cũng có 3 phương án vị trí là 5, 6 và 7. Sau khi đã đạt độ cao, có thể sử dụng đường ống tự chảy với hai phương án vị trí bể điều hòa là 8 và 9, trước khi đổ vào hồ 10 (Nhật, et. al., 2001).
Tất nhiên đối với mỗi phương án chuyển nước, từ điểm này tới điểm tiếp sau đều có tổng chi phí tương ứng. Trong hình 7.8, mô tả sơ đồ bài toán và chi phí tương ứng cho mỗi phương án. Vấn đề ở đây là lựa chọn phương án chuyển nước từ hồ 1 đến hồ 10 sau cho tổng chi phí toàn tuyến là thấp nhất.
7.3.4. Lập mô hình và giải bài toán QHĐ ở thí dụ minh họa
Từ bài toán thực tế trong thí dụ 7.3, chúng ta thấy rất gần gũi với lý thuyết QHĐ ở chỗ, nếu tồn tại một phương án chuyển nước rẻ nhất (Min tổng chi phí) từ điểm 1 đến điểm 10 trải qua 4 giai đoạn (4 cấp độ chuyển nước), thì có thể chia bài toán thành 4 bài toán con mà ở mỗi bài toán con đó cần thỏa mãn tiêu chuẩn min chi phí của chính nó cùng với giai đoạn trước.
Áp dụng lý thuyết QHĐ để giải, trước tiên cần xác định rõ các thành phần của bài toán.
1. Giai đoạn (n): Có 4 giai đoạn như trong hình 7.8, tức là n=4.
2. Biến chính (Xn): Biến chính của bài toán chính và vị trí có thể xây dựng trạm bơm, bể chứa hoặc bể điều hòa. Như vậy hai điểm 1 và 10 là cố định vì là điểm đầu và cuối của tuyến chuyển nước. Tại giai đoạn 1, có 3 phương án biến là các vị trí 2, 3, và 4. Giai đoạn 2 cũng có 3 phương án vị trí là 5, 6 và 7. Trong khi đó giai đoạn 3 chỉ có 2 phương án là vị trí 8 và 9.
3. Biến trạng thái (Sn): Trong trường hợp đơn giản này, biến trạng thái cũng chính là biến chính mà không phải là một hàm của biến chính. Như vậy, với bài toán này, biến trạng thái là rời rạc, và hữu hạn.
4. Kết quả giai đoạn (rn): Kết quả giai đoạn trong bài toán này chính là chi phí cho mỗi phương án chuyển nước từ vị trí này tới vị trí tiếp theo. Đây chính là một ma trận chi phí. Do đó hàm r là hàm ẩn và cho thẳng kết quả. Có thể nói rằng
( )
n n n 1 n SXn
r =r S , S + , X = C là các giá trị rời rạc được cho trong ma trận sau.
Bảng chi phí (CSXn - tỷ đồng) cho các phương án tuyến dẫn giữa các vị trí
Điểm xuất phát (điểm đi)
1 2 3 4 5 6 7 8 9 10
1 2 2 3 4 4 3 5 7 3 4 6 4 2 1 7 6 4 5 8 1 6 3
Điểm đến
9 4 3 3 10 3 4
5. Phép biến đổi trạng thái (tn): Trong bài toán này, như ở phần biến trạng thái đã nêu, phép biến đổi trạng thái tn = 1. Nghĩa là: Sn 1+ = Xn.
6. Trình tự giải: Trước hết chọn trình tự ngược để giải bài toán, tức là đi từ điểm 10 (hồ chứa trên sông C). Lưu ý rằng, người ta rất hay sử dụng trình tự ngược để giải bởi nó theo logic xuôi. Có nghĩa là: nếu tuyến trước đó đã tối ưu thì đoạn cuối cùng (giai đoạn cuối cùng) đạt tiêu chuẩn tối ưu thì sẽ cho tối ưu toàn tuyến.
7. Phương trình truy toán): Từ phương trình truy toán tổng quát dạng giải ngược:
[ ]
{ }
n
* *
n n n n n n 1 n n n
X
f (S ) = Max (Min) r (S , X )• f + t (S , X kết hợp với những điều kiện nêu trên, chúng ta có:
n
* *
n n n n n n n n
X
f (S ) = f (S , X ) = Min f (S , X ) trong đó:
*
n n SXn n 1 n 1
*
SXn n 1 n
f (S, X ) C f (S )
C f (X )
+ +
+
= +
= + (7.39)
Với (7.39) cùng các dữ liệu của bài toán, chúng ta bắt tay vào giải bài toán QHĐ của thí dụ 7.3 theo trình tự ngược cho từng giai đoạn để tìm được lời giải tối ưu là dẫn chuyển nước theo phương án tuyến nào sẽ cho tổng chi phí thấp nhất.
Với giai đoạn n=4: Chúng ta có điểm đến cuối cùng là điểm 10 (hồ chứa trên sông C), đây chính là biến X4*, có hai phương án đến điểm 10, hay có hai biến trạng thái của giai đoạn 3 đến điểm 10, đó là S3 = 8 và 9. Sau đó có được giá trị của f4 và đồng thời là f4* như trong bảng sau.
(n=4)
Biến trạng
thái 3 (S3) f4(S) = f4*(S) X4*
8 3 vị trí 10
9 4 vị trí 10
Với giai đoạn n=3: Chúng ta có 2 điểm đến là điểm 8 và 9, một trong hai điểm hoặc cả hai có thể là biến X3*, có 3 phương án đến hai điểm này, tức là có tổ hợp 6 phương án có thể, những biến trạng thái của giai đoạn 2 sang giai đoạn 3 chỉ là 3 biến là S2 = 5, 6 và 7. Sau đó có được giá trị của f3 và f3* như trong bảng sau.
(n=3)
Biến trạng f3(S,X3) = CSX3 + f4*(X3) f3*(S) X3*
thái 2 (S2) X3 = 8 X3 = 9
5 1 + 3 = 4 4 + 4 =8 4 vị trí 8 6 6 + 3 = 9 3 + 4 = 7 7 vị trí 9 7 3 + 3 = 6 3 + 4 = 7 6 vị trí 8
Với giai đoạn n = 2: Thực hiện tương tự như ở giai đoạn n=3, chúng ta có bảng sau.
(n=2)
f2(S,X2) = CSX2 + f3*(X2) Biến trạng
thái 1 (S1) X2 = 5 X2 = 6 X2 = 7 f2*(S) X2*
2 7 + 4 = 11 4 + 7 = 11 6 + 6 = 12 11 vị trí 5, 6 3 3 + 4 = 7 2 + 7 = 9 4 + 6 = 10 7 vị trí 5 4 4 + 4 = 8 1 + 7 = 8 5 + 6 = 11 8 vị trí 5,6
Với giai đoạn n = 1: Thực hiện tương tự như ở giai đoạn n=3 và n=2, chúng ta có bảng sau.
(n=1)
f1(S,X1) = f1*(X1) Biến trạng
thái 0 (S0) X1 = 2 X1 = 3 X1 = 4 f1*(S) X0*
1 2 + 11 = 13 4 + 7 = 11 3 + 8 = 11 11 vị trí 3, 4
Vậy các phương án tối ưu về vị trí và tuyến chuyển nước sau đều cho minimum tổng chi phí bằng 11 tỷ đồng:
1 - 3 - 5 - 8 - 10 1 - 4 - 5 - 8 - 10 1 - 4 - 6 - 9 - 10
Bây giờ chúng ta sẽ giải theo trình tự xuôi qua các bảng sau. Với phương trình truy toán xuôi là:
n
* *
n n n n n n n n
X
f (S ) = f (S , X ) = Min f (S , X ) trong đó:
*
n n SXn n 1 n 1
*
SXn n 1 n
f (S, X ) C f (S )
C f (X )
− −
−
= +
= + (7.40)
(n=1)
Biến trạngthái 1
(S1) f1(S) = f1*(S) X0*
2 2 Vị trí 1
3 4 Vị trí 1
4 3 Vị trí 1
(n=2)
f2(S,X2) = CSX2 + f1*(X1) Biến trạng
thái 2 (S2) X1 = 2 X1 = 3 X1 = 4 f2*(S) X1*
5 7 + 2 = 9 3 + 4 = 7 4 + 3 = 7 7 vị trí 3, 4 6 4 + 2 = 6 2 + 4 = 6 1 + 3 = 4 4 vị trí 4 7 6 + 2 = 8 4 + 4 = 8 5 + 3 = 8 8 vị trí 2, 3, 4
(n=3)
f3(S,X3) = CSX3 + f2*(X2) Biến trạng
thái 3 (S3) X2 = 5 X2 = 6 X2 = 7 f3*(S) X2*
8 1 + 7 = 8 6 + 4 = 10 3 + 8 = 11 8 vị trí 5 9 4 + 7 = 11 3 + 4 = 7 3 + 8 = 11 7 vị trí 6
(n=4)
f4(S,X4) = CSX4 + f3*(X3) Biến trạng
thái 4 (S4) X3 = 8 X3 = 9 f4*(S) X3*
10 3 + 8 = 11 4 + 7 =11 11 vị trí 8, 9
Vậy các phương án tối ưu về vị trí và tuyến chuyển nước sau đều cho minimum tổng chi phí bằng 11 tỷ đồng:
10 - 8 - 5 - 3 - 1 10 - 8 - 5 - 4 - 1 10 - 9 - 6 - 4 - 1
Như vậy dù giải theo trình tự xuôi hay trình tự ngược chúng ta thu được cùng một kết quả về tuyến dẫn nước và các vị trí tối ưu (Trí, 1999).