TRONG HỆ THỐNG THỦY LỢI
7.4. GIỚI THIỆU LÝ THUYẾT QUY HOẠCH PHI TUYẾN (QHPT)
7.4.2. Tối ưu phi tuyến ràng buộc
Xét bài toán quy hoạch phi tuyến ràng buộc mà đại diện là hàm mục tiêu phi tuyến sau:
Min f(X) (7.48)
Thỏa mãn các ràng buộc:
gi(X) = 0 (i=1, 2,..., m) (7.49)
j j j
x ≤ x ≤ x (j= 1, 2,..., n) (7.50) Phương trình (7.50) là ràng buộc (điều kiện) biên của biến xj thứ j với xj và xj là giới hạn dưới và trên.
Đối với bài toán tối ưu phi tuyến ràng buộc thì điều kiện Kuhn-Tucker là rất quan trọng. Điều kiện này phải được thỏa mãn tại mọi điểm tối ưu ràng buộc (dù là nghiệm cục bộ hay nghiệm toàn miền, với bài toán quy hoạch tuyến tính hay quy hoạch phi tuyến) (Trí, 1999).
(a) Toán tử Lagrangian L(x,λ)
Toán tử Lagrangian được sử dụng để chuyển bài toán quy hoạch phi tuyến bất kỳ thành bài toán qui hoạch phi tuyến không ràng buộc, toán tử được định nghĩa như sau:
L(x,λ)= f(x) + λT g(x) (7.51)
Trong đó λ là véc tơ các số nhân Lagrangian, g(x) là véc tơ các phương trình ràng buộc. Phương trình (7.51) có thể viết khai triển như sau:
m
1 m 1 m 1 n i i 1 n
i 1
L(x ,..., x ; ,..., ) f(x ,..., x ) g (x ,...x )
λ λ = + ∑= λ (7.52)
Đối với bài toán tìm cực tiểu, L(x,λ) là hàm mục tiêu có m+n biến. Điều kiện cần và đủ để tồn tại nghiệm tối ưu x* là:
(1) f(x*) và g(x*) là hàm lồi trong miền lân cận của x* (2) * m i i
j j i 1 j
L(x ) f g
x x = x
∂ ∂ ∂
= + ∑λ
∂ ∂ ∂ j =1,..., n (7.53)
(3) i
i
L g (x) 0
∂ = =
∂λ i =1,..., m (7.54)
(4) λi không bị hạn chế về dấu i=1,..., m (7.55) Giải đồng thời hai phương trình (7.53) và (7.54) sẽ thu được nghiệm tối ưu.
Số nhân Lagrangian có một ý nghĩa quan trọng trong các bài toán tối ưu. Đối với một ràng buộc cho trước, số nhân tương ứng sẽ chỉ độ nhạy của giá trị hàm mục tiêu khi thay đổi vế phải của ràng buộc, nghĩa là:
* i
i x x
f b =
∂ = λ
∂
λi được gọi là biến đối ngẫu.
(b) Điều kiện Kuhn Tucker
Nếu sử dụng phương pháp số nhân Lagrange thì các điều kiện cho bài toán dạng tổng quát quy hoạch phi tuyến là:
Min f(x) Thỏa mãn các ràng buộc:
gi(x) = 0 i = 1, 2,..., m
j j j
x ≤ x ≤ x (j = 1, 2,..., n)
Áp dụng toán tử Lagrange bài toán quy hoạch phi tuyến có thể viết dưới dạng sau:
T T T
MinL = f(x)+ λ g(x) + λ (x − x)+ λ (x − x) (7.56) Trong đú: λ λ, và λ là cỏc vộc tơ của toỏn tử Lagrange tương ứng với cỏc ràng buộc: g(x) = 0, (x − x) ≤ 0 và (x − x) ≤ 0. Lỳc này điều kiện Kuhn-Tucker để bài toán tồn tại nghiệm tối ưu là:
T
xL xf xg 0
∇ = ∇ + λ ∇ − λ + λ = (7.57)
gi(x) = 0 i =1, 2,..., m (7.58)
j (xj x )j j(xj x )j 0
λ − = λ − = j =1, 2,..., n (7.59) m biến cơ sở có thể khai triển dưới dạng n-m biến phi cơ sở xB(xN). Giả thiết rằng các ràng buộc g(x) = 0 là có thể vi phân được, như vậy sẽ thu được m ma trận cơ sở B dưới dạng:
B
B g(x) x
⎡∂ ⎤
= ⎢⎣ ∂ ⎥⎦
Ràng buộc được gọi là ràng buộc rút gọn có thể được viết dưới dạng biến phi cơ sở là:
F(xN) = f(xB(xN), xN) (7.60)
Và bài toán quy hoạch phi tuyến gốc bây giờ được chuyển sang dạng bài toán rút gọn như sau:
Min (xN) (7.61)
Thỏa mãn ràng buộc:
N N N
x ≤ x ≤ x (7.62)
Bài toán rút gọn này có thể dễ dàng giải bằng kỹ thuật tối thiểu phi ràng buộc mà dưới đây là một phương pháp giải hay được áp dụng.
(c) Phương pháp gradient tổng hạ nhanh nhất
Mô hình tổng quát của bài toán đơn mục tiêu có ràng buộc như sau:
Hàm mục tiêu đơn: Min f(X) (7.63)
Thỏa mãn các ràng buộc: hi(X) ≤ 0, Với i = 1, 2, ..., I (7.64) lj(X) = 0, Với j = 1, 2,..., J (7.65) 0 ≤ xn ≤ xnmax, Với n = 1, 2,..., N (7.66) Trong đó: X - véctơ nghiệm: X = {x1, x2, .., xn};
f - hàm mục tiêu riêng biệt;
h - các ràng buộc không chặt;
l - các ràng buộc chặt;
I - số lượng ràng buộc không chặt;
J - số lượng ràng buộc chặt;
n - chỉ số thứ tự hồ chứa được xét trong bài toán.
Với các biến không âm thêm vào các ràng buộc không chặt (7.64) ta được:
Hàm mục tiêu đơn: Min f(X) (7.67)
Thỏa mãn các ràng buộc: hi(X) + xN+i = 0, Với i = 1, 2, ..., I (7.68) lj(X) = 0, Với j = 1, 2, ..., J (7.69) 0 ≤ xn ≤ xnmax, Với n =1,2, ..., N (7.70) xN+i ≥ 0, Với i = 1, 2, ..., I (7.71) Số lượng biến bây giờ là: N+I với X = {x1, x2,.., xN, xN+1, xN+I}, bài toán trở thành:
Hàm mục tiêu đơn: Min f(X) (7.72)
Thỏa mãn các ràng buộc: gi(X) = 0, Với i = 1, 2, ..., I+J (7.73)
0 ≤ xn ≤ xnmax, Với n = 1, 2, ..., N+I (7.74) Để giải bài toán từ (7.72) đến (7.74), phương pháp giải phù hợp là Phương pháp gradient tổng hạ nhanh nhất (Generalied Reduced Gradient Method), gọi tắt là phương pháp GRG.
Phương pháp GRG dựa trên ý tưởng giảm bớt độ lớn các biến thông qua những ràng buộc tương đương. Về lý thuyết, mỗi biến có thể giảm kích cỡ mảng bằng cách tách thành hai mảng tương đương. Tức là có thể tách:
X Y Z
= ⎨ ⎬⎧ ⎫
⎩ ⎭ (7.75)
thành hai mảng:
1 2
N J
y y
Y .
. y −
⎧ ⎫
⎪ ⎪
⎪ ⎪
⎪ ⎪
= ⎨ ⎬
⎪ ⎪
⎪ ⎪
⎪ ⎪
⎩ ⎭
= Biến chính độc lập (7.76)
và
1 2
I J
z z
Z .
. z +
⎧ ⎫
⎪ ⎪
⎪ ⎪
⎪ ⎪
= ⎨ ⎬
⎪ ⎪
⎪ ⎪
⎪ ⎪
⎩ ⎭
= Biến phụ phụ thuộc (7.77)
Xét đạo hàm bậc nhất của hàm mục tiêu và các ràng buộc như sau:
N J I J
T T
i i Y Z
i 1 i i 1 i
f f
df(X) dy dz fdY fdZ
y z
− +
= =
∂ ∂
= ∑ + ∑ = ∇ + ∇
∂ ∂ (7.78)
N J I J
i i
i j j
j 1 j j 1 j
g g
dg (X) dy dz
y z
− +
= =
∂ ∂
= ∑ + ∑
∂ ∂ (7.79)
Có thể viết (7.79) dưới dạng: dg = [C] dY + [D] dZ (7.80) Trong đó:
1
2 Y
N J
f y f y
f .
. f y −
⎧ ∂ ⎫
⎪∂ ⎪
⎪ ⎪
⎪ ∂ ⎪
⎪∂ ⎪
⎪ ⎪
⎪ ⎪
∇ = ⎨ ⎬
⎪ ⎪
⎪ ⎪
∂
⎪ ⎪
⎪∂ ⎪
⎪ ⎪
⎪ ⎪
⎩ ⎭
(7.81)
1
2 Z
I J
f z f z
f .
. f z +
⎧∂ ⎫
⎪∂ ⎪
⎪ ⎪
⎪ ∂ ⎪
⎪∂ ⎪
⎪ ⎪
⎪ ⎪
∇ = ⎨ ⎬
⎪ ⎪
⎪ ⎪
∂
⎪ ⎪
⎪∂ ⎪
⎪ ⎪
⎪ ⎪
⎩ ⎭
(7.82)
1 1
1 N J
I J I J
1 N J
g g
y . . y
. .
[C] . .
g g
y . . y
−
+ +
−
∂ ∂
⎡ ⎤
⎢∂ ∂ ⎥
⎢ ⎥
⎢ ⎥
= ⎢ ⎥
⎢ ⎥
⎢∂ ∂ ⎥
⎢ ⎥
∂ ∂
⎢ ⎥
⎣ ⎦
(7.83)
1 1
1 I J
I J I J
1 I J
g g
z . . z
. .
[D] . .
g g
z . . z
+
+ +
+
∂ ∂
⎡ ⎤
⎢∂ ∂ ⎥
⎢ ⎥
⎢ ⎥
= ⎢ ⎥
⎢ ⎥
⎢∂ ∂ ⎥
⎢ ⎥
∂ ∂
⎢ ⎥
⎣ ⎦
(7.84)
1 2
N J
dy dy
dY .
. dy −
⎧ ⎫
⎪ ⎪
⎪ ⎪
⎪ ⎪
= ⎨ ⎬
⎪ ⎪
⎪ ⎪
⎪ ⎪
⎩ ⎭
(7.85)
1 2
I J
dz dz
dZ .
. dz +
⎧ ⎫
⎪ ⎪
⎪ ⎪
⎪ ⎪
= ⎨ ⎬
⎪ ⎪
⎪ ⎪
⎪ ⎪
⎩ ⎭
(7.86)
Giả thiết rằng các ràng buộc của bài toán thỏa mãn với véctơ X, tức là g(X)=
0, như vậy bất cứ thay đổi nào với véctơ dX đều phải cho dg = 0 nhằm duy trì được tính khả dĩ tại X + dX. Phương trình (7.80) có thể giải bằng cách khai triển dZ như sau:
dZ = -[D]-1 [C] dY (7.87) Khi thay đổi biến X sẽ làm cho giá trị của hàm mục tiêu thay đổi theo. Sự thay đổi này được biểu hiện bằng phương trình (7.78). Thay (7.87) vào (7.78) sẽ có:
[ ] [ ]
( TY TZ 1 )
df(X) = ∇ f − ∇ f D − C dY (7.88)
hoặc: df (X) GR
dY = (7.89)
trong đó: GR = ∇Yf − ( [ ] [ ]D −1 C )T∇Zf (7.90)
GR được gọi là độ giảm gradient tổng. Về mặt hình học, độ giảm gradient tổng có thể được mô tả như là hình chiếu của gradient gốc N chiều lên vùng
nghiệm khả dĩ
(N-I) chiều.
Chúng ta biết rằng, điều kiện cần để tồn tại cực tiểu của hàm không ràng buộc là các thành phần của gradient bị triệt tiêu. Tương tự như vậy, đối với hàm mục tiêu có ràng buộc, sẽ tồn tại giá trị cực tiểu của hàm khi các thành phần của gradient giảm xuống bằng không (zero). Điều kiện này đã được chứng minh và được áp dụng trong toán tối ưu, khi các điều kiện này được thỏa mãn thì sẽ tồn tại giá trị nhỏ nhất tương đối của hàm mục tiêu.
Giá trị gradient∇f có được sử dụng để tạo phương tìm kiếm S cho hàm mục tiêu không ràng buộc, tương tự như vậy, gradient giảm GR được sử dụng để tạo phương tìm kiếm S cho hàm mục tiêu có ràng buộc. Trên phương tìm kiếm S, cần xác định bước tìm kiếm λ phù hợp để có thể nhanh chóng tìm ra giá trị cực tiểu của hàm mục tiêu. Đối với giá trị của λ, véctơ biến phụ thuộc Z được điều chỉnh thông qua phương trình (7.87). Chú ý rằng phương trình (7.87) sử dụng cơ sở gần đúng tuyến tính để áp dụng cho bài toán phi tuyến chuẩn, vì vậy đôi khi ta thấy các ràng buộc không tuyệt đối bằng zero tại λ (tức là dg≠0). Do đó khi Y đã sơ bộ được xác định, để đạt được:
gi(X) + dgi(X) = 0, Với i = 1, 2, ..., I+J (7.91) Phải có: g(X) + dg(X) = 0 (7.92)
Thay (7.80) vào (7.92) ta được:
dZ = [D]-1 (-g(X) - [C] dY) (7.93) Giá trị dZ tính được từ (7.93) được sử dụng để điều chỉnh lại giá trị của Z bằng cách:
Zđiều chỉnh = Zhiện tại + dZ (7.94)
Giá trị tính toán của các ràng buộc tại X sau khi điều chỉnh và quá trình điều chỉnh dZ bằng phương trình (7.93) được lặp lại nhiều lần cho đến khi đạt được dZ đủ nhỏ. Thuật toán và các bước giải như sau:
♦ Thuật toán và các bước giải bài toán đơn mục tiêu phi tuyến ràng buộc Bước 1:
Xác định các biến chính Y (biến độc lập) và biến trạng thái Z (biến phụ thuộc). Cho một véctơ nghiệm X ban đầu và bắt đầu quá trình với X. Trong bước này lưu ý một số điểm sau:
(a) Chọn biến trạng thái sao cho ma trận [D] không là đơn nhất;
(b) Vì biến trạng thái sẽ được điều chỉnh trong quá trình tính lặp nhằm duy trì vùng nghiệm khả dĩ, cho nên bất kỳ thành phần nào của ma trận X bằng giá trị biên dưới và biên trên đều phải chọn làm biến chính;
(c) Các biến đưa thêm vào ràng buộc (để biến bất phương trình thành phương trình) đều phải cho là biến trạng thái. Tuy nhiên nếu giá trị ban đầu của biến trạng thái là zero (giá trị biên dưới) thì phải chuyển nó thành biến chính.
Bước 2:
Tính giá trị độ giảm gradient tổng GRG bằng phương trình (7.90). Nếu cần thì tính các đạo hàm có liên quan trong phương trình (7.90).
Bước 3:
Kiểm tra sự hội tụ. Nếu tất cả các thành phần của GRG xấp xỉ bằng zero, thì bài toán được coi là hội tụ và véctơ nghiệm X sau cùng được coi là nghiệm của bài toán. Như vậy có thể kiểm tra mức độ hội tụ thông qua giá trị vô cùng bé ε chọn trước và kiểm tra theo công thức:
GR ≤ ε (7.95)
Nếu (7.85) được thỏa mãn thì dừng quá trình, nếu chưa thỏa mãn thì chuyển sang bước 4.
Bước 4:
Xác định phương tìm kiếm S. Nếu sử dụng phương pháp độ dốc lớn nhất, S sẽ được xác định theo:
S = -GR (7.96)
Bước 5:
Tìm giá trị nhỏ nhất trên phương tìm kiếm. Quá trình này như sau:
(a) Xác định giá trị λ bằng khoảng cách nhỏ nhất tới biên trên và biên dưới:
- Khi xác định theo biến chính:
(u) i i cu
i i
(l) i i cu
i i
y (y )
khi s 0 s
y (y )
khi s 0 s
⎧ −
⎪ >
λ = ⎨⎪
⎪ − <
⎪⎩
(7.97)
Trong đó: si - thành phần thứ i của S;
(u) và (l) - chỉ giá trị biên trên và biên dưới của y;
cu - chỉ giá trị cũ.
- Khi xác định theo biến trạng thái, từ (7.87) có: dZ = -[D]-1[C]dY với dY = λS, ta có phương tìm kiếm cho biến Z là:
T = -[D]-1[C]S (7.98)
(u) i i cu
i i
(l) i i cu
i i
z (z )
khi t 0 t
z (z )
khi t 0 t
⎧ −
>
⎪⎪ λ = ⎨
⎪ −
⎪ <
⎩
(7.99)
Trong đó: ti - thành phần thứ i của T.
(b) Giá trị nhỏ nhất của λ tính theo (7.97) ký hiệu là λ1, tạo nên một số biến chính nằm trong khoảng biên trên và biên dưới. Tương tự, giá trị tính theo (7.99) là λ2, cũng tạo nên một số biến phụ nằm trong khoảng biên trên và biên dưới của chúng. Giá trị nhỏ hơn của cặp λ1 và λ2, có thể xem như là biên trên của λ trong quá trình ban đầu. Với phương pháp nội suy bậc hai, ta có thể tìm được bước tìm kiếm tốt nhất λ*.
(c) Tìm véctơ Xmoi:
*
cu cu
new *
cu cu
Y dY Y S
X Z dZ Z T
⎧ ⎫
+ + λ
⎧ ⎫ ⎪ ⎪
= ⎨⎩ + ⎬⎭ = ⎨⎪⎩ + λ ⎬⎪⎭
(7.100) Nếu véctơ Xmoi tương ứng với λ*không nằm trong miền nghiệm, thì Ymoi
được coi là hằng số còn Zmoi sẽ được điều chỉnh theo (7.94) với: dZ = Zmoi - Zcu. Cuối cùng, khi phương trình (7.93) cho kết quả hội tụ, sẽ thu được:
cu moi
cu
Y Y
X Z Z
⎧ + Δ ⎫
= ⎨⎩ + Δ ⎬⎭ (7.101)
Sau khi có Xmoi, quay lại bước 1 cho đến khi thỏa mãn điều kiện (7.95).