129
CHƯƠNG
4
ứng dụng quy hoạch phi tuyến và
quy hoạch động trong hệ thống
nguồn nớc
Những ứng dụng ban đầu các kỹ thuật vận trù học vào các bài toán hệ
thống nguồn nớc chủ yếu dựa vào việc sử dụng các kỹ thuật quy hoạch
tuyến tính và quy hoạch động. Việc sử dụng những kỹ thuật này để giải các
bài toán hệ thống nguồn nớc đã đợc ghi lại trong khá nhiều các tài liệu.
Các đoạn chơng trình quy hoạch tuyến tính đợc phổ biến rộng rãi, tuy
nhiên quy hoạch động đòi hỏi mỗi đoạn chơng trình riêng cho từng ứng
dụng. Việc sử dụng quy hoạch phi tuyến trong giải quyết các bài toán hệ
thống nguồn nớc cha đợc phổ biến mặc dù hầu hết các bài toán yêu cầu
lời giải trong thực tế là những bài toán phi tuyến. Sự phát triển gần đây của
những kỹ thuật quy hoạch phi tuyến mới và các đoạn chơng trình quy
hoạch phi tuyến sẵn có đã lôi cuốn những ứng dụng mới của quy hoạch phi
tuyến vào các bài toán hệ thống nguồn nớc. Hai phần đầu tiên của chơng
này trình bày những cơ sở của quy hoạch động. Sau đó, trình bày các bớc
tính toán tối u hóa phi tuyến không ràng buộc và các bớc tính toán tối u
hóa phi tuyến có ràng buộc.
4.1. Quy hoạch động
Quy hoạch động (DP-Dynamic Programming) biến đổi một bài toán
quyết định nối tiếp hay nhiều giai đoạn có thể có nhiều biến quyết định liên
quan với nhau thành một chuỗi những bài toán từng giai đoạn đơn lẻ, mỗi
những tính toán ban đầu; và (3) không thể loại trừ ngay từ đầu những tổ hợp
nghiệm không khả thi.
Trong quy hoạch động mỗi phơng án cho mỗi dự án đợc xem xét
riêng mà không bỏ qua sự phụ thuộc lẫn nhau giữa các dự án thông qua
tổng ngân sách hiện có. Vì tổng lợng vốn bị hạn chế, lợng vốn dành cho
mỗi dự án phụ thuộc vào sự phân bổ cho các dự án còn lại. Với bất kỳ
những lợng vốn đợc ấn định cho các dự án A và B, sự phân bổ cho dự án
còn lại, C, phải đợc tiến hành để tối u hóa lợi nhuận của nó đối với khả
năng vốn còn lại đó. Nói cách khác, sự phân bổ tối u cho dự án C phụ
thuộc vào lợng vốn dành cho C sau khi đã phân bổ cho A và B. Vì không
biết những sự phân bổ tối u cho các dự án A và B, sự phân bổ và lợi nhuận
tối u từ dự án C phải đợc xác định cho tất cả các lợng vốn còn lại có thể,
sau khi những sự phân bổ cho các dự án A và B đợc tiến hành. Hơn nữa
với bất cứ lợng vốn nào đợc phân bổ cho dự án A, những sự phân bổ cho
dự án B và C phải đợc làm một cách tối u đối với lợng vốn còn lại sau
khi đã phân bổ cho dự án A. Để tìm đợc sự phân bổ tối u cho dự án B ta
tìm sự phân bổ làm tối đa hóa lợi nhuận từ dự án B cùng với lợi nhuận tối
u từ dự án C. Sự phân bổ này là một hàm của các lợng vốn còn lại từ sự
phân bổ cho dự án B. Cuối cùng, sự phân bổ tối u cho dự án A đợc xác
định để tối đa lợi nhuận từ dự án A cộng với lợi nhuận tối u kết hợp của dự 131
án B và C, nh một hàm của các lợng vốn còn lại sau khi phân bổ cho dự
án A.
Trong thực tế, những lợng vốn đợc phân bổ đồng thời cho cả ba dự án
này. Sự phân bổ theo một chuỗi thứ tự là một động tác về mặt toán học cho
phép ta tiến hành các quyết định kế tiếp nhau. Quy hoạch động có thể khắc
phục đợc những hạn chế của phơng pháp liệt kê đầy đủ bằng việc sử
dụng các khái niệm sau:
(4.1.1b)
1
1, 1,2,3,
i
M
ij
j
x i N
với
(4.1.1c)
Tất cả x
ij
= 0 hoặc 1 (4.1.1d)
Trong đó
ij
r
là lợi nhuận có thể sinh ra từ phơng án j của dự án i,
ij
c
là
yêu cầu cấp vốn cho phơng án j của dự án i,
ij
x
là một biến quyết định mà
n
,
trong mỗi giai đoạn không nhất thiết bằng 1.
3. Các biến trạng thái (S
n
) là các biến diễn tả trạng thái của một hệ
thống tại giai đoạn n bất kỳ. Một biến trạng thái có thể là rời rạc
hoặc liên tục, hạn định hoặc không hạn định. Trong hình 4.1.1, ở
giai đoạn n bất kỳ, có các trạng thái đầu vào, S
n
, và các trạng thái
đầu ra, S
n+1
. Các biến trạng thái của hệ thống trong một mô hình quy
hoạch động có chức năng liên kết các giai đoạn kế tiếp sao cho khi
mỗi giai đoạn đợc tối u hóa riêng biệt quyết định thu đợc tự động
khả thi cho toàn bộ bài toán. Hơn nữa, nó cho phép ta ra những quyết
định tối u cho các giai đoạn còn lại mà không cần phải kiểm tra ảnh
hởng của các quyết định trong tơng lai tới các quyết định đã ra
trớc đấy.
4. Lợi nhuận giai đoạn (r
n
) là một chỉ số đo tính hiệu quả của quyết
định làm trong mỗi giai đoạn. Nó là một hàm của trạng thái đầu vào,
trạng thái đầu ra và các biến quyết định của một giai đoạn nhất định.
Tức là: r
n
=r(S
n
, S
A
(triệu đô)
Lợi nhuận
r
A
(triệu đô)
Chi phí
c
A
(triệu đô)
Lợi nhuận
r
A
(triệu đô)
1
2
3
1
2
3
5
6
8
2
3
4
8
9
12
1
): biến trạng thái tại mỗi giai đoạn là tập hợp các phơng án đợc xét.
3. Biến quyết định (d
n
): biến quyết định là phơng án đợc chọn cho mỗi giai đoạn (dự án).
4. Lợi nhuận giai đoạn (r
n
): lợi nhuận đợc sinh ra từ phơng án đã chọn.
5. Hàm chuyển đổi trạng thái (t
n
): S
n
= d
n
với n = C và S
n+1
= d
n
với n = A và B.
Theo dạng giản đồ, bài toán này có thể đợc miêu tả nh trong hình 4.1.2a dới dạng một bài toán
chuỗi quyết định. Một cách rõ ràng hơn, hệ thống này có thể đợc
Hình 4.1.2a
Sự biểu thị thành
chuỗi của bài toán
ví dụ phân bổ ngân
sách. 134
trạng thái khả thi trong các giai đoạn ngay sau (chỉ có giai đoạn C ở thời điểm hiện tại). Bài toán tối
u hóa là
Max
*
( )
B B B B C B
f S r S f dNhững tính toán để xác định các kết nối tối u cho mỗi trạng thái khả thi trong dự án B đợc đa ra
trong Bảng 4.1.2(b). Chú ý rằng bài toán này là một chuỗi lựa chọn các phơng án với ràng buộc về
ngân sách. Cần phải theo dõi và kiểm tra các phí tổn tích lũy khi quá trình tối u hóa chuyển từ một
giai đoạn này sang giai đoạn kế tiếp.
Trong Bảng 4.1.2(b) với mỗi trạng thái khả thi của dự án B, đó là, SB = (phơng án 1, phơng án 2,
phơng án 3), điều đó tơng ứng hai quyết định có thể với các trạng thái trong giai đoạn kế tiếp (dự
án C), dC = SC = (phơng án 1, phơng án 2). Để giải thích những tính toán có liên quan trong Bảng
4.1.2(b) xét dòng cuối cùng tơng ứng với SB = phơng án 3. Lợi nhuận tích lũy gắn liền với dC =
phơng án 1 là 12 triệu đô la + 3 triệu đô la = 15 triệu đô la trong đó số đầu tiên (12 triệu đô la) là lợi
nhuận sinh ra từ sự lựa chọn phơng án 3 cho dự án B và số thứ hai (3 triệu đô la) do sự lựa chọn
phơng án 1 cho dự án C nh đã đợc chỉ ra trong Bảng 4.1.2(a). Chi phí tích lũy tơng ứng với sự
kết nối các trạng thái giữa các dự án B và C này (tức là, SB = phơng án 3 và SC = phơng án 1) là 4
triệu đô + 1 triệu đô = 5 triệu đô, là khả thi trong vòng hạn chế ngân sách là 7 triệu đô. Với chú ý tới
SB = phơng án 3 và dB = SC = phơng án 2, lợi nhuận tích lũy là 17 triệu đô, lớn hơn quyết định
ban đầu là 15 triệu đô; tuy nhiên, chi phí tích lũy là 7 triệu đô sử dụng hết toàn bộ ngân sách và
không còn kinh phí cho dự án A. Điều này vi phạm ràng buộc yêu cầu rằng tất cả các dự án phải
đợc thực thi. Vì vậy, quyết định dB = SC = phơng án 2 là không khả thi và cần phải loại bỏ. Hai
B C
d S
= phơng án 1. Đến
đây thì hoàn thành bớc tìm ngợc chỉ ra sự lựa chọn tối u của các phơng án là
* * *
A B C
( d ,d ,d )
(
phơng án 2, phơng án 3, phơng án 1) và tổng lợi nhuận tối u (lớn nhất) là 21 triệu đô la. Bớc
tìm ngợc đợc minh họa trong hình 4.1.2b chỉ ra bởi các đờng nét đậm. Bài toán này cũng có thể
đợc giải bằng việc xác định biến trạng thái là lợng ngân sách sẵn có (Bài toán 4.1.2).
4.1.2. Các đặc trng về thuật giải của quy hoạch động
Từ ví dụ 4.1.1, các đặc tính cơ bản đặc trng cho tất cả các bài toán quy
hoạch động là nh sau:
1. Bài toán đợc chia ra thành các giai đoạn, với các biến quyết định tại
mỗi giai đoạn.
2. Mỗi giai đoạn có một số trạng thái gắn liền với nó.
3. ảnh hởng của quyết định đợc lựa chọn tại mỗi giai đoạn là để tạo
ra một lợi nhuận, dựa trên hàm lợi nhuận của giai đoạn đó, và để
biến đổi biến trạng thái hiện tại thành biến trạng thái cho giai đoạn
kế tiếp, thông qua hàm chuyển đổi trạng thái.
4. Với trạng thái hiện tại, một chính sách tối u cho các giai đoạn còn
lại là độc lập với chính sách đã đợc chấp nhận trong các giai đoạn
trớc. Đây gọi là nguyên lý Bellman về tính tối u, đợc xem nh là
cốt lõi của quy hoạch động.
5. Lời giải bắt đầu bằng việc tìm quyết định tối u cho mỗi trạng thái
có thể trong
Bảng 4.1.2(a)
trong () là chi phí tích lũy cho các dự án C.
136
Bảng 4.1.2(b)
Tính toán quy hoạch động cho dự án B
*
B B B B B C B
f (S ,d ) = r (S )+ f (d )
d
B
= S
C
S
B
Phơng án 1 Phơng án 2
*
B
f ()
*
B
d
Phơng án 1
8+3=11
(2+1=3)
giai đoạn cuối cùng (gọi là đệ quy lùi) hay trong giai đoạn đầu tiên (gọi
là đệ quy tiến). Một thuật giải tiến bắt đầu tính toán từ giai đoạn đầu
tiên cho tới giai đoạn cuối cùng còn một thuật giải lùi bắt đầu tính toán
từ giai đoạn cuối cùng tới giai đoạn đầu tiên.
6. Một mối quan hệ đệ quy xác định chính sách tối u cho mỗi trạng
thái ở giai đoạn n bất kỳ có thể đợc xây dựng khi cho trớc chính
sách tối u cho mỗi trạng thái ở giai đoạn tiếp theo, n+1. Phơng
trình đệ quy lùi này, theo hình 4.1.1, có thể đợc viết là:
* *
1 1
*
1
( ) . ( . ) ( )
. ( . ) [ ( , )]
n
n
n n n n n
n n
d
n n n n n n
n
d
f S opt r S d f S
opt r S d f t S d
chung đây sẽ là trờng hợp sử dụng tối u hóa quy hoạch động lùi. Do đó,
phơng trình đệ quy cho kỹ thuật quy hoạch động lùi có thể đợc viết là:
*
*
1 1
.[ ( , )],
( )
.[ ( , ) ( )],
n
n
n n n
d
n n
n n n n n
d
opt r S d
S
opt r S d f S
f
o
với = (4.1.5 )
với = 1 đến - 1 (4.1.5 )
n N a
Phơng án 1 Phơng án 2 Phơng án 3
PA - 1
5+13=8
(1+5=6)
+
5+14=19
(1+6=7)
5+15=20
(1+5=6)
20 PA - 3
($6)
PA - 2
6+13=19
(2+5=7)
6+14=20
(2+6=8, không khả
thi)
6+15=21
(2+5=7)
21 PA - 3
($7)
PA - 3
8+13=21
(3+5=8, không khả
thi)
8+14=22
(3+6=9, không khả
thi)
*
d
f S Max r f
; và với giai đoạn 1
*
1 1
A
A B
d
f S Max r f
.
Ví dụ 4.1.3. Các dòng chảy tới một hồ có tổng dung tích bằng 4 đơn vị nớc là 2, 1, 2 và 1 đơn vị
tơng ứng với bốn mùa trong năm. Để tiện lợi, lợng nớc chỉ đợc tính bằng các đơn vị nguyên.
Do đó, lợng xả ra từ hồ để cung cấp cho một thành phố và nông nghiệp đợc bán với giá là $2000
cho đơn vị đầu tiên, $1500 cho đơn vị thứ hai, $1000 cho đơn vị thứ ba, và $500 cho đơn vị thứ t.
Khi hồ chứa đầy nớc và xả tràn 1 đơn vị nớc, một trận lũ nhỏ sẽ dẫn tới thiệt hại $1500, Khi xả
tràn lên tới 2 đơn vị, một trận lũ lớn sẽ gây thiệt hại $4000, Xác định chính sách vận hành để lợi
nhuận hàng năm lớn nhất bằng quy hoạch động sử dụng thuật giải lùi, xét với bất kỳ lợng dự trữ
nào ở thời điểm cuối năm.
Lời giải. Bớc đầu tiên là giải thích hàm lợi nhuận. Một đơn vị xả ra từ hồ có lợi nhuận là $2000; 2
đơn vị xả có lợi nhuận là $2000+ $1500 = $3500; 3 đơn vị xả có lợi nhuận là $3500 + $1000 =
$4500; 4 đơn vị xả có lợi nhuận là $4500 + $500 = $5000; 5 đơn vị xả (khi mà hồ chứa chỉ có dung
tích là 4 đơn vị thì điều này có nghĩa là hồ chứa bị đầy và 1 đơn vị phải xả tràn); lợi nhuận sẽ là
$5000 (4 đơn vị cấp nớc) - $1500 (1 đơn vị xả tràn) = $3500; và 6 đơn vị xả thì lợi nhuận sẽ là
$5000 -$4000 (2 đơn vị xả tràn) = $1000,
Mỗi mùa thể hiện một giai đoạn nh trên hình 4.1.3. Biến trạng thái cho bài toán vận hành hồ chứa
nn
SS
Phơng trình đệ quy lùi quy hoạch động cho ví dụ này là:
[
*
)],([
Max
nnnn
dSrMaxf
Các bớc tính toán quy hoạch động đợc trình bày ở các bảng 4.1.3(a)-(d). Xem bảng 4.1.3(a) để
theo dõi các bớc tính toán cho giai đoạn 4. Cột đầu tiên thể hiện lợng trữ (trạng thái) ban đầu của
mùa (giai đoạn) 4. Cột thứ hai là giá trị lợng trữ ban đầu cộng với lợng dòng chảy tới hồ QF
4
= 1.
Năm cột tiếp theo là linh hồn của tính toán quy hoạch động mà ở đó các phơng trình đệ quy đợc 138
giải. Mỗi cột dành cho các giá trị có thể của lợng trữ cuối thời đoạn
4
QFSR
Với lợng xả là 1 đơn vị thì lợi nhuận là $2000 do đó f
4
(S
4
)=r
4
(S
4
=0, d
4
=R
4
=1) = $2000, Một cách
tơng tự cho S
4
= 1 và
0
4
~
S
, R4 = 1 + 1 - 0 = 2 và khi đó f
4
(S
4
)=r
4
(S
343
S
QFSR
, do vậy lợi nhuận là r
3
(S
3
=0, d
3
=R
3
=2) = $3500, Từ bảng
4.1.3(a) lợi nhuận luỹ tích tối u cho giai đoạn 4 là
2000$)0(
4
*
4
Sf
đối với
4
~
3
S
S
. Các
bớc tính toán đợc lặp theo chiều ngợc lại cho giai đoạn 2 (mùa 2) rồi giai đoạn (mùa) 1 nh
đợc trình bày lần lợt tại các bảng 4.1.3(c) và (d).
hoặc 3 đơn vị và tơng ứng với chúng là lợng trữ cuối thời
đoạn
4
1
~
S
hoặc 3. Xét trong bảng 4.1.3(c) với
4
~
12
SS
hoặc 3 thì lợng xả tối u với S
2
=
3 là
2
*
2
d
hoặc 3 đối với các lợng trữ cuối cùng tơng ứng của giai đoạn 2
2
2
~
S
hoặc 1. Đối
với S
2
= 4, lợng xả tối u
2
*
3
d
hoặc 3 và
2
*
3
~
S
hoặc 3; và với S
3
= 3,
3
*
3
d
và
2
*
3
~
S
. Các lợng trữ cuối tối u của giai đoạn 3 là
1
*
3
~
S
hoặc 2. Quá trình tìm
trờng hợp: (1) khi số các biến trạng thái là lớn; và (2) khi quy hoạch động
đợc áp dụng theo phơng pháp rời rạc để tính toán cho một không gian
trạng thái liên tục. Vấn đề liên quan đến trờng hợp 2 là tồn tại nhiều khó
khăn trong việc tìm kiếm nghiệm tối u thực nếu không tăng một cách đáng
kể số các khoảng rời rạc hoá trong không gian trạng thái. Cùng với những
tiến bộ về công nghệ máy tính, những nhợc điểm này dần trở nên ít
nghiêm trọng.
Một gia số các rời rạc hoá hay số các biến trạng thái có thể làm tăng
theo hàm mũ số các tính toán các công thức đệ quy và bộ nhớ cho mỗi giai
đoạn. Vấn đề tăng nhanh yêu cầu về bộ nhớ và thời gian tính gắn với các
bài toán quy hoạch động đa biến trạng thái này thờng đợc đề cập tới với
tên gọi lời nguyền của số chiều (vấn đề tăng theo quy luật hàm mũ khi
tăng số chiều trên không gian tính). 140
Bảng 4.1.3(a)
Tính toán quy hoạch động cho giai đoạn 4 của Ví dụ 4.1.3
(a) Giai đoạn 4 - Mùa 4
Lợi nhuận f
4
(S
4
)=r
4
(S
4
,d
4
d = R
Lợng
trữ cuối
*
4
S
0 1 2000
0 - - - 2000 1 0
1 2 3500
2000
0 - - 3500 2 0
2 3 4500
3500
2000
0 - 4500 3 0
3 4 5000
4500
3500
2000
*
3 3 3 3 3 4 4
f S = r S ,d + f S
Lợng trữ cuối
3
4
S = S
Lợng trữ
ban đầu
S
3
Tổng
lợng trữ
S
3
+ QF
3
0 1 2 3 4
Lợi nhuận
lớn nhất
*
3 3
f S
-
-
5500 2,1 0,1
1 3
4500 + 2000
=
6500
3500 + 3500
=
7000
2000 + 4500
=
6500
0 + 5000 =
5000
-
7000 2 1
2 4
5000 + 2000
=
8500
4500 + 4500
=
9000
3500 + 5000
=
8500
2000 + 5000
= 7000
9000 3 2,
4 6
1000 + 2000
=
3000
3500 + 3500
=
7000
5000 + 4500
3
*
322222
, SfdSrSf
Lợng trữ cuối
3
2
SS
Lợng trữ
ban đầu
S
2
Tổng lợng
trữ
S
2
+QF
2
0 1 2 3 4
Lợi nhuận
lớn nhất
2
*
3
4
5
2000+5500=
7500
3500+5500=
9000
4500+5500=
10000
5000+5500=
10500
3500+5500=
9000
0+7000=
7000
2000+7000=
9000
3500+7000=
10500
4500+7000=
11500
5000+7000=
12000
_
7500
9000
10500
11500
12500
1
2,1
2
3,2
3,2
0
0,1
1
1,2
2,3
Lợng trữ
ban đầu
S
1
Tổng
lợng trữ
S
1
+QF
1
0 1 2 3 4
Lợi nhuận
lớn nhất
1
*
1
Sf
Quyết định
(Xả)
*
11
Rd
Lợng trữ
cuối cùng
2
*
11000
1000+7500=
8500
2000+9000=
11000
3500+9000=
12500
4500+9000=
13500
5000+9000=
14000
3500+9000=
12500
0+10500=
10500
2000+10500=
12500
3500+10500=
14000
4500+10500=
15000
5000+10500=
15500
_
0+11500=
11500
2,1
2
3,2
3,2
0,1
1,2
2
2,3
3,4 118
Hình 4.1.4
Bớc tìm ngợc cho ví dụ 4.1.3.
4.2. Quy hoạch động sai phân rời rạc
Quy hoạch động sai phân rời rạc (DDDP-Discrete Differential Dynamic
Programming) là một thủ tục quy hoạch động lặp, đợc đặc biệt thiết kế để
khắc phục một số khó khăn của cách tiếp cận quy hoạch động đã đợc đề cập
đến ở trớc. Quy hoạch động sai phân rời rạc sử dụng phơng trình đệ quy
giống nh quy hoạch động để tìm kiếm trong số các trạng thái rời rạc thuộc
miền giai đoạn-trạng thái. Thay bằng việc tìm kiếm nghiệm tối u trên toàn
dụng mối quan hệ đệ quy để tìm ra một quỹ đạo tốt hơn. Quỹ đạo này xác
định một chính sách hay tập hợp của các quyết định trong hành lang đã đợc
đa ra. Quỹ đạo thử nghiệm này sau đó đợc sử dụng nh một quỹ đạo mới để
tạo ra một hành lang mới. Quá trình hình thành và tối u hành lang này xét tới
các trạng thái nằm trong hành lang đó và qua trình tìm ngợc trở lại để nhận
đợc một quỹ đạo tốt hơn cho toàn bộ hệ thống đợc gọi là một bớc lặp.
Quỹ đạo mới, định nghĩa hệ thống thông qua sự tối u của hành lang thử
nghiệm, sau đó đợc sử dụng nh quỹ đạo thử nghiệm mới để thiết lập hành
lang tốt hơn cho bớc lặp tiếp theo. Thủ tục này đợc lặp tới quá một bớc lặp
thứ k nào đó mà ở đó cho ra một hành lang. Hành lang này cung cấp một lợi
nhuận của hệ thống f
k
sao cho các bớc lặp tiếp theo với cùng kích thớc của
hành lang này sẽ tạo ra một chênh lệch trong lợi nhuận hệ thống, f
k
-f
k-1
nhỏ
hơn một dung sai xác định. Tại điểm này trong thủ tục tối u hóa, kích thớc
của số gia trạng thái có thể đợc giảm xuống để thiết lập một hành lang mới
mà trong đó các trạng thái hay các điểm lới xít nhau hơn. Một hành lang nhỏ
hơn đợc hình thành quanh quỹ đạo đã đợc cải thiện từ bớc lặp cuối cùng. 120
Các bớc lặp tiếp tục giảm kích thớc của số gia trạng thái thông qua hệ thống
cho đến khi đạt tới một kích thớc hành lang nhỏ nhất xác định.
Tiêu chuẩn đợc sử dụng để xác định khi nào kích thớc số gia trạng thái
cần đợc giảm là dựa trên sự thay đổi tơng đối của giá trị hàm mục tiêu tối
u của bớc lặp trớc, đó là:
tối u. Có thể trong một số trờng hợp bài toán quy hoạch động sai phân rời
rạc sẽ hội tụ tới một nghiệm khá xa nghiệm tối u. Số các điểm lới và số gia
trạng thái ban đầu cùng xác định độ rộng của hành lang ban đầu. Sử dụng một
sự kết hợp một số lợng nhỏ các điểm lới và một số gia trạng thái ban đầu
nhỏ cũng có thể dẫn tới những lời giải tối u địa phơng cách xa nghiệm tối
u.
ảnh hởng của việc chọn một quỹ đạo ban đầu không tốt có thể đợc
giảm đi nếu một số lợng lớn các điểm lới và/hoặc các số gia trạng thái ban
đầu lớn đợc sử dụng. Thực chất, quỹ đạo ban đầu càng tốt thì yêu cầu số các
điểm lới và các số gia trạng thái ban đầu càng nhỏ, hoặc đơn giản, càng có
thể sử dụng độ rộng hành lang ban đầu nhỏ. Số gia trạng thái rất nhỏ với các
điểm lới nhiều hơn cũng có thể đợc sử dụng để thiết lập một độ rộng hành
lang nhỏ. Điều này có thể dẫn tới sự hội tụ tốt hơn; tuy nhiên, việc tăng số 121
lợng các điểm lới làm tăng thời gian tính toán và nhu cầu lu trữ. Thời gian
tính toán có thể đợc cải thiện bằng việc gia tăng tốc độ giảm của số gia trạng
thái tại mỗi bớc lặp; tuy nhiên, tốc độ suy giảm của số gia trạng thái quá lớn
có thể bỏ qua khu vực tối u vì vậy không cung cấp lời giải tối u. Việc lựa
chọn một số gia trạng thái ban đầu lớn và một tốc độ suy giảm kích thớc số
gia trạng thái lớn có thể là có lợi. Tuy nhiên, khi số gia trạng thái ban đầu quá
lớn, dẫn tới các độ rộng hành lang lớn, những sự tính toán không cần thiết
đợc thực hiện ở các khu vực không gian trạng thái cách xa vùng tối u.
HìNH 4.2.2
Thuật giải tổng quát cho quy hoạch động sai phân rời rạc
4.3. Đại số ma trận cho quy hoạch phi tuyến
1 2
, , ,
T
n
f f f f
f x
x x x x
(4.3.2)
trong đó
là vector của toán tử gradient
1
/ , , /
T
n
x x
. Về mặt hình
học, vector gradient tại một điểm cho trớc biểu thị hớng mà theo đó tốc độ
(4.3.3) 123
Hessian là một ma trận vuông đối xứng.
Ví dụ 4.3.1. Xét hàm bậc hai sau (Edgar và Himmelblau, 1988)
2 2
1 2 1 2
4 2
f x x x x x
Các đờng đẳng trị của hàm này đợc biểu thị trong hình 4.3.2. Xác định gradient và Hessian cho hàm
và Hessian theo phơng trình (4.3.3) là :
2
8 2
2 2
H x f x
Tại điểm x = (1,1), gradient là:
6
(1,1)
0
f
Trong khi đó Hessian là không đổi với mọi điểm.
Các khái niệm về tính lồi và tính lõm đợc sử dụng để xác định liệu tối
u địa phơng, cực tiểu địa phơng, hay cực đại địa phơng, cũng là tối
u toàn cục, và là tốt nhất trong tất cả các nghiệm. Trong trờng hợp một 124
biến, một hàm f(x) đợc gọi là lồi trên một vùng nếu với mọi x
a
và x
b
, x
a
x
b
,
thỏa mãn nh sau:
1 1 ,0 1
a a
b b
f x x f x f x
(4.3.5)
Hàm này là lõm thực sự khi quan hệ trên thỏa mãn với dấu >. hình 4.3.3
minh họa thêm các khái niệm trên.
T
Hx > 0 với mọi x
0
H xác định âm:
x
T
Hx < 0 với mọi x
0
H không xác định:
x
T
Hx < 0 với một số x;
> 0 với một số khác
H bán xác định dơng:
x
T
Hx
0 với mọi x
H bán xác định âm:
x
T
Hx
0 với mọi x 125
x
b
, tất cả các
điểm nằm trên đờng thẳng nối x
a
và x
b
là
ba
xxx
1
, trong đó
10
,
đều nằm trong tập hợp đó. hình 4.3.4 minh họa các miền lồi và không lồi.
Tính lồi của một miền khả thi và hàm mục tiêu trong tối u hóa phi tuyến
có một sự liên quan cực kỳ quan trọng đối với loại lời giải tối u nhận đợc.
Với các bài toán quy hoạch tuyến tính (trong Chơng 3), hàm mục tiêu và
miền khả thi đều là lồi do đó lời giải tối u là một tối u toàn cục. Mặt khác,
tính lồi của cả hàm mục tiêu và miền khả thi trong một bài toán quy hoạch phi
tuyến không thể đợc đảm bảo, do đó lời giải tối u đạt đợc không thể bảo
đảm cho toàn cục.
Ví dụ 4.3.2. Phân loại hàm sau
2 2
Cả hai phần tử đờng chéo đều dơng. Tiếp theo tính các định thức ma trận con:
M
1
=8 det M
1
=8
M
2
= H det M
2
= (8)(8)-(-4)(-4)=48
Ma trận Hessian là xác định dơng vì cả hai phần tử đờng chéo đều dơng và các ma trận con đều
dơng; do đó f(x) là lồi thực sự. 126
Ví dụ 4.3.3. Phân loại miền đợc xác định bởi tập hợp các ràng buộc sau:
2
1 2
1 2
2
3
x x
x x
H x
H x
Cả g
1
(x) và g
2
(x) đều lõm dẫn đến một miền lồi
127
H×nh 4.3.3
So s¸nh cña c¸c hµm bËc hai låi vµ lâm.
Copyright: Tài liệu đại học ©