116 Quy hoạch và quản lý nguồn n"ớc
Trong đó: chỉ số n chỉ lần lặp thứ n. Phép lặp sẽ kết thúc ở lần lặp thứ n+1 nếu
thoả mãn biểu thức có dạng:

xx
n1n
-Êe
+
(5-74)
và giá trị
x
n
1
+
là nghiệm của phEơng trình.
b. Bài toán nhiều chiều
Giả sử cần tìm nghiệm xấp xỉ của hệ phEơng trình với n phEơng trình tEơng ứng
với n biến số chEa biết:

f
i
(X)0
=
với i =
1,n
(5-75)
Hoặc dEới dạng véc tơ F(X) = 0.
Trong đó X là véc tơ X = (x
1
, x
2

trận Jacobien tại X
n-1
: 111
12 n
FFF

xxx
ảảả
ảảả

J(Xn-1) =
222
12 n
FFF

xxx

ảảả
ảảả
(5-77)

nnn
12 n
FFF

xxx
ảảả

F(X)
x
ả
ả
ả
ả
ả
ả
(5-78)
- Tính ma trận Hesein theo giá trị ban đầu:

22
121n
(k)
22
n1 nn
FF
xxxx
H(F(X ))
FF
xxxx
ộự
ảả
ờỳ
ảảảả
ờỳ
ờỳ
=
ờỳ
ảả

(k)
.
Và tiếp tục với các phép lặp tiếp theo cho đến khi
*
k
l
đủ nhỏ sẽ đEợc nghiệm
tối Eu.
Ví dụ:
Tìm (x
1
, x
2
) sao cho cực tiểu hàm mục tiêu:
F(X) =
21
21
11
4
xx
xx +++

đ
min (5-80)
Giải:
1. Chọn điểm xuất phát: giá trị ban đầu của X
(0)
= (1,13; 3,56).
2. Tính giá trị đạo hàm cấp 1 tại vị trí xuất phát:


2
2
0
x
H(F(X ))
2
0
x
ộự
ờỳ
ờỳ
=
ờỳ
ờỳ
ởỷ
=
1,41 0
00,04
ộự
ờỳ
ởỷGiá trị:
1 (0)
0,71 0
H(F(X ))
0 25
-
ộự

ỳ
ỷ
ự
ờ
ở
ộ
250
071,2
4,21
0,92
ộự
ờỳ
ởỷ
=
1,13
3,56
ộự
ờỳ
ởỷ
-
k
l
2,28
23
ộự
ờỳ
ởỷ
đ
*
k


5.5.7. Giải bài toán tối "u phi tuyến không ràng buộc bằng ph"ơng pháp
không dùng đạo hàm
Các bài toán dạng cổ điển đEợc giải bằng cách tìm đạo hàm và xác định các
điểm dừng chỉ phù hợp với những dạng bài toán có thể hàm hoá đEợc. Ngoài ra cần
chứng minh sự tồn tại nghiệm và các đạo hàm tEơng ứng.
Trong các bài toán kỹ thuật những điều kiện này rất khó thỏa mãn, bởi vậy ngEời
ta tìm nghiệm của bài toán bằng các phEơng pháp dò tìm tối Eu. Các phEơng pháp loại
này áp dụng cho cả bài toán có ràng buộc và không ràng buộc.
PhEơng pháp phổ biến đEợc áp dụng là phEơng pháp dò tìm trực tiếp theo bEớc.
Trong tài liệu này sẽ trình bày một số phEơng pháp thEờng đEợc áp dụng trong lĩnh
vực phát triển nguồn nEớc.
5.5.7.1. Ph-ơng pháp dò tìm theo h-ớng của Hooke-Jeeves
PhEơng pháp Hooke - Jeeves có thể gọi là phEơng pháp di chuyển theo hEớng có
thể đến điểm cực trị. Sự dò tìm theo hEớng có thể đEợc thực hiện theo từng toạ độ của
véc tơ X.
1. Bài toán: Tìm giá trị của véc tơ X = (x
1
, x
2
, , x
n
) sao cho:
F(X)
đ
min với X
ẻ
R
n


x
một giá trị
D
x
1
.
Ta có:
1 0
111
xxx
=+D
(5-83)
(3) Tính giá trị
000
1112 n
FF(xx,x ,x)
=+D

và tính
0
11
FFF(X)
D=-
(5-84)
(4) Kiểm tra điều kiện:
- Nếu
1
F0
D<
chứng tỏ hEớng di chuyển là đúng ta cố định điểm đó với

Â
D=-

Nếu
1
F0
Â
D<
, chứng tỏ hEớng dò tìm đúng, ta cố định điểm đó và dò tìm cho
biến tiếp theo, tức là:

1 0
111
xxx
=-D

(5-86)
Nếu
1
F0
Â
D
, hEớng dò tìm không đạt, tức là rơi vào tình trạng "tiến thoái lEỡng
nan". Trong trEờng hợp này ta giữ nguyên biến x
1
, tức là "không tiến cũng không lùi":

10
11
xx

2
,
1
;
(
1
n
k
x
F
k
=

kxxk
i
xx
ikk
ạ=== ivớiivới
01
;
0fFD

I
=I+1
i
x
0


Đúng

Sai

Đúng

Sai
i=1

iii
xxx D+=
01
01
F
F
F
-
=
D

I > N

D
F
G

<
0
|DF

Hình 5-9: Sơ đồ tính dò tìm tối "u theo ph"ơng pháp Hooke-Jeeves
Ch"ơng 5- Kỹ thuật phân tích hệ thống 121 (5) Dò tìm theo hEớng có thể của biến thứ hai: Trong khi biến thứ nhất đã đEợc
cố định theo một trong các biểu thức (5-85)
á
(5-87). Giả sử chọn một gia lEợng
2
x
D

cho biến thứ hai ta có:
Chọn
1 0
222
xxx
=+D
và tính
1000
21223 n
FF(x,xx,x,x)
=+D
(6) Tính:
221
FFF
D=-

1000
21223 n
FF(x,xx,x,x)
=D-

Tính
'
221
FFF
D=-

- Nếu
2
F0
Â
D<
. HEớng dò tìm đạt yêu cầu và cố định điểm đó chọn:

1 0
222
xxx
=-D
(5-89)
Tiếp tục dò tìm cho biến tiếp theo.
- Trong trEờng hợp ngEợc lại, tEơng tự nhE đối với biến thứ nhất, ta giữ giá trị
của biến thứ hai, tức là:

10
22
xx

ã

Nếu (5-92) thỏa mãn, sự dò tìm theo hEớng này (xu thế chung đối với tất cả
các tham biến) đạt yêu cầu. Kiểm tra thêm điều kiện:
122 Quy hoạch và quản lý nguồn n"ớc
Nếu F
DÊ
e
(5-93)
Trong đó
e
là số dEơng cho trEớc tuỳ ý (sai số của kết quả dò tìm điểm cực trị)
- Nếu (5-93) thỏa mãn, kết thúc công việc dò tìm và nghiệm tối Eu của bài toán là:

8 **
12 n
,
X (x,xx)
=
(5-94)
- Nếu F
D>
e
, có nghĩa là hEớng di chuyển là đúng nhEng chEa đến điểm cực
tiểu với sai số cho trEớc
e
.
Ta tiếp tục dò tìm tiếp, nhEng toạ độ ban đầu cho lần dò tìm tiếp theo là điểm kết
thúc đối với lần dò tìm trEớc, tức là: X
0

x
i
với mọi i.
Nếu (5-95) thỏa mãn, kết thúc dò tìm và nghiệm của bài toán.
Trong trEờng hợp ngEợc lại cần chia nhỏ bEớc dò tìm bằng cách chọn :

21
ii
1
xx
2
D=D

và tiếp tục quay lại từ bEớc đầu tiên, cho đến khi đạt đEợc các điều kiện (5-93) và (5-95).
5.5.7.2. Ph-ơng pháp dò tìm theo mẫu
1. Bài toán:
Tìm giá trị của véc tơ X = (x
1
, x
2
, , x
n
) sao cho:
F(X)
đ
min với X
ẻ
R
n


1
x
, các biến khác đEợc giữ nguyên giá trị ban đầu. Giả sử ta tăng
giá trị của
1
x
một giá trị
1
x
D
.
Ta có:
(k 1)(k)
111
x
xx
+
+
=D
(5-98)
B"ớc 3: Tính giá trị
(k)(k)(k)
1112 n
FF(xx,x ,x)
=+D

và tính
(k)
11
FFF(X)

xx
+
-
=D

Tiếp tục tính
(k)(k)(k)
1112 n
FF(xx,x ,x)
=+D
và
' (k)
11
FFF(X)
D=-

Nếu
'
1
F0
D<
, chứng tỏ hEớng dò tìm đúng, ta cố định điểm đó và dò tìm cho
biến tiếp theo, tức là:

(k+1)(k)
111
xxx
=-D
(5-101)
Nếu

=D
và tính
(k 1)(k)(k)(k)
21223 n
FF(x,xx,x ,x)
+
=+D
B"ớc 6: Tính:

221
FFF
D=-

Nếu
D
F
2

<
0. Ta có hEớng di chuyển đạt yêu cầu, ta cố định toạ độ
2
x
và dò tìm
cho biến tiếp theo, tức là chọn

(k 1)(k)
222
xxx
+
=+D

F 0
D<
. HEớng dò tìm đạt yêu cầu và cố định điểm đó và chọn:

(k 1)(k)
222
xxx
+
=-D
(5-104)

Và tiếp tục dò tìm cho biến tiếp theo.
- Trong trEờng hợp ngEợc lại, tEơng tự nhE đối với biến thứ nhất, ta giữ giá trị
của biến thứ hai, tức là:

(k 1)(k)
22
xx
+
=
(5-105)
và chuyển sang dò tìm cho biến sau.
B"ớc 7: Tiếp tục làm nhE các bEớc trên cho đến biến cuối cùng là x
n
. Ta kết thúc lần
lặp thứ nhất.
NhE vậy trong dò tìm bEớc I, tại mỗi bEớc dịch chuyển theo biến độc lập, giá trị
hàm mục tiêu đEợc so sánh với giá trị của nó tại điểm trEớc. Nếu hàm mục tiêu đEợc
cải thiện tại mỗi bEớc nào đó thì giá trị cũ đEợc thay thế bằng giá trị mới trong những
so sánh sau đó. Nếu hàm mục tiêu không đEợc cải thiện thì giữ nguyên giá trị cũ.

(k+2)
= m x
i
(k+1)
- x
i
(b)
(5-108)
Dò theo mẫu sẽ có toạ độ mới là:

(k 2)(k 2)(k 2)(k 2)
12 n
X (x,x, ,x)
++++
=
(5-109)
Tính hàm mục tiêu:
(k 2)(k 2)(k 2)(k 2)
12 n
F(X)F(x,x, ,x)
++++
=
Trong đó:
x
i
(b)
- điểm cơ sở ở lần lặp đầu X
(b)
= X
(k)

- Nếu F ( X
(k+3)
)
Ê
F(X
(k+1)
), thì thăm dò theo mẫu đEợc coi là kết quả. Khi đó điểm
cơ sở là:
X
(b)
= X
(k+1)
(5-111)
Tiếp tục thăm thăm dò theo mẫu (quay loại Công đoạn II) nhEng điểm xuất phát
là X
(k+3)
, lấy:
X
(k+4)
= mk
(k+3)
- X
(b)
= mX
(k+3)
- X
(k+1)

Tức là:
x

D
x
i
cho đến khi hoặc cho hEớng mới có hiệu quả, hoặc khi a
i
nhỏ hơn
một giá trị cho phép.

Bắt đầu

(1)
Chọn điểm cơ sở
X
b
= X
0
. Tính F(X
b
) (2) Tìm kiếm thăm
dò bZớc 1 từ điểm
cơ sở X
b
. Tính F(X) F(X) > F(X
b

i

Kết
thúc
Sai

Đúng

Đúng

Sai

Đúng

SaiHình 5-10a: Sơ đồ thuật toán dò tìm trực tiếp - Dò theo mẫu

Việc giảm giá trị hàm F(X) khi các giá trị
D
x
i
khá bé chính là nghiệm của
bài toán.
Thuật toán của phép lặp này đEợc trình bày ở sơ đồ hình 5-10a.
PhEơng pháp này khác với phEơng pháp dò tìm Hooke-Jeeves ở nhE sau: Sau khi
dò tìm theo biến số đã hoàn thành đối với tất cả các biến số, phEơng pháp Hooke-
Jeeves sẽ chọn toạ độ đã di chuyển tới làm toạ độ xuất phát cho lần dò tìm tiếp theo,
còn phEơng pháp dò tìm theo mẫu lại tìm điểm xuất phát mới để kiểm tra hEớng di


0
X(2,0;2,8)
=
Chọn
X(0,6;0,84)
D=

Tính:
0
F(X)0,059
=

B"ớc 2: Chọn một biến bất kỳ trong véc tơ X và dò tìm hEớng có thể cho biến ấy. Ta
bắt đầu biến đầu tiên x
1
. Giả sử ta tăng giá trị
D
x
1
.
- Ta có :
(1)(0)
111
xxx
=+D
= 2,0 +0,6 = 2,6
- Tính giá trị
(0)(0)
1112

=

HEớng di chuyển đạt yêu cầu.
B"ớc 3: Dò sang biến thứ 2:
128 Quy hoạch và quản lý nguồn n"ớc
- Ta có :
(1)(0)
222
xxx
=+D
= 2,8 +0,84 = 3,64
- Tính giá trị
(1)(0)
1122
FF(x ;xx)
=+D
=
F(1,4;3,64)
= 0,052
<

0
F(X )0,059
=

HEớng di chuyển không đạt.
lấy:
(1)(0)
222
xxx

- x
i
(b)

Ta có: x
i
(2)
= 2x
i
(1)
-x
i
(0)
tìm đEợc x
1
(2)
= 2(1,4)-2 = 0,8; x
2
(2)
= 2(1,96)-2,8 = 1,12
Dò theo mẫu sẽ có toạ độ mới là:
(2)(2)(2)
12
,)
x(xx
=
= (0,8; 1,12)
Tính hàm mục tiêu:
(2)(2)(2)
12


HEớng di chuyển không đạt.
lấy:
(3)(2)
111
xxx
=-D
= 0,8 - 0,60 = 0,2
- Tính giá trị
(3)(2)
1112
FF(xx,x)
=-D
=
F(0, 2 ,1,12)
=0,38
>

2
F(X )0,22
=

HEớng di chuyển đạt yêu cầu.
Ch"ơng 5- Kỹ thuật phân tích hệ thống 129 Dò sang biến thứ 2:
- Ta có :
(3)(2)
222

F(0,2;0,28)
= 0,104
>

2
F(X)0,22
=

HEớng di chuyển đạt yêu cầu.
NhE vậy, tìm thăm dò bEớc 2 đạt và lấy
(3)
X
(0,2; 0,28)
=

Và tính:
(3) 33
12
),x
F(XF(x)F(0,2; 0,28)0,67
===

Kiểm tra sự thành công của thăm dò theo mẫu:
Ta có: F(X(
3)
) = 0,67
>
F(X
(1)
) = 0,105. Việc thăm dò theo mẫu có kết quả.

Tìm thăm dò bEớc 2 với điểm xuất phát là X
(4)
= (-1; -1,4) và F(X
(4)
) = 0,51
- Tính giá trị
(4)(4)
1112
FF(xx,x)
=+D
=
F(1,4;1,4)

= 0,43
<

4
F(X)0,51
=

HEớng di chuyển không đạt.
lấy:
(5)(4)
111
xxx
=-D
= -1 - 0,60 =-1,6
- Tính giá trị
(4)(4)
1112

222
xxx
=+D
= -1,4 +0,84 = -0,56
- Tính giá trị
(5)(4) 4
1122
)0,51
FF(x ;xx) F(1; 0,56) 3,18 F(X =
=+D= =>

HEớng di chuyển đạt yêu cầu.
Ta có: F(X(
5)
) = 3,18
>
F(X
(3)
) = 0,6. Việc thăm dò theo mẫu có kết quả. Điểm
cơ sở mới bây giờ là:
X
(b)
= X
(3)
= (0,2 ; 0,28)
Tiếp tục tìm theo mẫu với điểm xuất phát X
(5)
và điểm cơ sở X
(b)
= X

2

-
3

x
1
x
2
x
(0)

x
(1)

x
(3)

x
(4)

x
(5)

Điểm cơ sở: x
(0)
, x
(3)
, x
(5)

1
(7)
= -2,2 +0,6 = -1,6
đ
F(-1,6; - 1,4) = 0,43
>
F(X
(6)
) = 0,29
BEớc thăm dò có kết quả.
x
2
(7)
= -1,4 + 0,84 = -0,56
đ
F(-1,6; - 0,56) = 1,49
>
F(X
(6)
) = 0,29
Vì F(X
(7)
) = F(-1,6; - 0,56) = 1,49
<
F(X(
5)
) = 3,18 nên mặc dù thăm dò bEớc 2
có kết quả nhEng kết quả tìm mẫu đEợc coi là không thành công.
Do vậy, ta phải dò tìm bEớc 1 với điểm xuất phát là X
(5)

2
, , x
n
)
ẻ
R
n
(5-115)
Ph-ơng pháp giải
Để giải bài toán loại này ngEời ta tìm cách đEa bài toán tối Eu về loại không ràng
buộc bằng phEơng pháp hàm phạt, hoặc phEơng pháp nhân tử Lagrange.
Trong tài liệu này giới thiệu phEơng pháp nhân tử Lagrange (L).
Thiết lập hàm số Lagrange (L), có dạng:

m
jjj
j1
L(X,) F(X)g(X)b
=
ộự
l=+l-
ởỷ
ồ
(5-116)
trong đó : L(X,
l
) là hàm Lagrange;
l
là véc tơ nhân tử Lagrange:


Các điểm dừng của hàm L (X,
l
) là:

m
jjj
j1
iii
LF
(G(X)b)
xxx
=
ổử
ảảả
=+l-
ỗữ
ảảả
ốứ
ồ
(5-118)

ị

m
j
j
j1
iii
G(X)
L F

(G(X)b) K1,m
ả
=-=
ảl
(5-120)
vì với j
ạ
K có
J
K
0
ảl
=
ảl

NhE vậy ta phải giải hệ n + m phEơng trình sẽ tìm ra n + m nghiệm của x
i
và
l
j
.

5.5.8.2. Bài toán ràng buộc bất đẳng thức
Phát biểu bài toán
Bài toán tối Eu với ràng buộc bất đẳng thức đEợc viết dEới dạng:
F(X)
đ
min (5-121)
với G
j

; j = 1, 2, , m
Ph-ơng pháp giải
Trong trEờng hợp ràng buộc là bất đẳng thức: NgEời ta cũng đEa bài toán có ràng
buộc về bài toán không ràng buộc. Có hai cách đEa bài toán ràng buộc bất đẳng thức
về bài toán không ràng buộc.
1. Bằng cách đEa thêm vào vế phải một biến phụ để ràng buộc bất đẳng thức trở
thành ràng buộc đẳng thức:
G
j
(X) + x
j
= b
j

J1,m
=
(5-123)
với x
j


0
Khi đó hàm Lagrange có dạng (5-124). NhE vậy ta đã đEa về dạng bài toán ràng
buộc đẳng thức, đEợc giải tEơng tự nhE trEờng hợp (5.5.7.1):

m
L(X,) F(X)(G(X)bx)
jjjj
j1
l=+l-+

) (5-125)
trong đó các giá trị của
l
= (
l
1
,
l
2
, ,
l
j
, ,
l
m
) và của X
j
= (x
n+1
, , x
n+j
, , x
n+m
) là các
biến số.
Bài toán không ràng buộc dạng (5-125) bây giờ đã có số biến tăng lên và là
n+2m biến số. NhE vậy, thay vì giải bài toán (5-121) với có n biến số với ràng buộc
(5-122) ta có bài toán không ràng buộc (5-124) với n+2m biến số. Sau khi đEa bài toán
tối Eu về dạng không có ràng buộc ta có thể dử dụng một trong những phEơng pháp
giải đã trình bày ở trên đối với bài toán tối Eu không có ràng buộc.

bằng cách tìm cực tiểu của hàm -F(X), tức là:
max F(X) = min (-F(X))
TEơng tự vậy, nếu ràng buộc có dạng g
j
(X)

b
j
; j =1, 2, , m có thể đEa về dạng:
g
j
(X)
Ê
- b
j
; j =1, 2, , m
Ph-ơng pháp giải
Trong trEờng hợp này thiết lập hàm Lagrange có dạng:

mmk
jjjj kk
j1 k1
L(X,,) F(X)g(X)bxh(X)
==
ộự
lm=+l-++m
ởỷ
ồồ
(5-128)
Với
PhEơng pháp quy hoạch động cho phép đEa bài toán tối Eu nhiều biến về chuỗi
các bài toán tối Eu một biến số. PhEơng pháp quy hoạch động là phEơng pháp đEợc áp
dụng nhiều trong quy hoạch và quản lý nguồn nEớc.
Khi áp dụng phEơng pháp quy hoạch động đối với các bài toán thực tế cần chú ý
điều kiện sau: Hàm mục tiêu của bài toán phải là hàm tách đ"ợc, đEợc viết dEới
dạng tổng của các hàm thành phần, và mỗi hàm thành phần chỉ chứa một biến độc lập,
tức là:

n
12 n j
j1
Z(x,x ,x) z(x)
=
=
ồ
(5-129)
Hoặc có thể viết dEới dạng khai triển:

1122jj nn
Zz(x) z(x) z (x) z (x)
=+++++
(5-130)

5.6.2. Ph"ơng pháp quy hoạch động với bài toán phân bố tài nguyên
5.6.2.1. Bài toán
Giả sử có lEợng tài nguyên X
T
đEợc phân bố cho n đối tEợng sử dụng, giả thiết

=
==
ồ
(5-133)

5.6.2.2. Ph-ơng giáp giải của Bellman
Thuật toán tối Eu đEợc giải theo hai hai bEớc: BEớc tính xuôi nhằm xác định các
thể hiện tối Eu có điều kiện, bEớc tính ngEợc đEợc thực hiện để tìm nghiệm tối Eu đối
với các biến số.
a. B-ớc tính xuôi
Bellman đã đEa ra nguyên lý tối Eu nhiều giai đoạn. Đầu tiên xem xét chiến lEợc
phân bố tối Eu cho hai đối tEợng sau đó là 3, 4 v.v đến n đối tEợng ở mỗi một giai