96 Quy hoạch và quản lý nguồn n"ớc
Bài toán tìm cực đại (5-21) có dạng:

1122 iinn
F(X)cxcx cx cxmax
+++++đ
(5-36)

Với c
i
là hằng số với biến thứ i.
Với ràng buộc là:

jj11j22jnn j
g(X)axax axb;j1,m
=+++== (5-37)
và x
i


0 với i=1, 2, , n;
đEợc đEa về dạng chính tắc với hàm mục tiêu:
max F(X) = min(-F(X))
tức là:

11122 iinn
F(X) F(X)cxcx cx cxmin
=-= đ


Ví dụ: Tìm X =

(x
1,
, x
2
, x
3
, x
4
) sao cho hàm mục tiêu:
Z = x
1
+ 2x
2
- 3x
3
+ 4x
4

đ
max
Với các ràng buộc:
1234
1234
i
xx7xx100
2x 3xx10x800
x0;i14
-++=
ỡ

ù
+-+=
ớ
ù
=á
ợ

ĐEợc đEa về dạng chính tắc nhE sau:
Tìm X =

(x
1,
, x
2
, x
3
, x
4
) sao cho hàm mục tiêu:
Z = -x
1
- 2x
2
+ 3x
5
- 4x
4

đ
min

Với các ràng buộc:

1234
1234
i
xx7xx100
2x 3xx10x800
x0;i14
-++=
ỡ
ù
+-+=
ớ
ù
=á
ợ


5.4.2.2. Dạng chuẩn tắc
Dạng chuẩn tắc là dạng mà ràng buộc là bất đẳng thức, tức là:

g(X)axax ax axb
jj11j22jii jnn j
=+++++Ê
;
j1,m
=
(5-38)
và x
i



0 với i =1, 2, , n.
Ch"ơng 5- Kỹ thuật phân tích hệ thống 97


5.4.2.3. Đ-a bài toán QHTT về dạng chuẩn tắc và dạng chính tắc
+ Nếu ràng buộc có dạng g
j
(X)

b
j
: Nhân 2 vế của biểu thức ràng buộc với (-1),
đEa bài toán về dạng chuẩn với ràng buộc dạng (5-21).
+ ĐEa bài toán chuẩn tắc về dạng chính tắc:
Bài toán dạng chuẩn có thể đEa về dạng chính tắc bằng cách thêm các biến phụ
vào vế trái của các bất đẳng thức. Có m ràng buộc bất đẳng thức sẽ có m biến phụ. Do
đó dạng chính tắc mới sẽ có n + m nghiệm. Ta có:

n j
g(X)x0
j +
+=
;
j1,m
=
(5-39)
trong đó: x
nj

+
là biến phụ;
và x
i


0 với i=1, 2, , n.

5.4.3. Định lý cơ bản và các định nghĩa về quy hoạch tuyến tính
5.4.3.1. Định lý cơ bản của quy hoạch tuyến tính
Định lý (phát biểu cho dạng chính tắc): PhEơng án tối Eu của quy hoạch tuyến
tính chứa một số biến d"ơng đúng bằng số các ràng buộc dạng đẳng thức độc lập,
các biến còn lại có giá trị 0.
Ví dụ bài toán QHTT có 5 biến và 3 ràng buộc nhE sau:

1122 ii55
F(X)cxcx cx cxmin
+++++đ
với n = 5

với các ràng buộc đẳng thức:
a
11
x
1
+ a
12
x
2
+ + a

15
x
5
= b
1

a
21
x
1
+ a
22
x
2
+ + a
25
x
5
= b
2

a
31
x
1
+ a
32
x
2
+ + a

35
x
5
= b
3

đ
Số ràng buộc m = 3
Do đó nghiệm tối Eu có 3 biến khác không, hai biến còn lại có giá trị không.
Chẳng hạn nghiệm là:
X(,,0,0,)
*
=***
.
Nếu bài toán tối Eu tuyến tính dạng chính tắc có nghiệm thì nghiệm của bài toán
sẽ nằm ở các điểm cực biên: các đỉnh tam giác (đối với bài toán phẳng) và đỉnh các đa
giác (đối với bài toán 3 chiều) v.v Các phEơng pháp tìm nghiệm của bài toán thEờng
là các phép thử dần tại các điểm cực biên. Giả sử đã dò tìm ở tất cả những điểm
cực biên mà không tìm đEợc một trEờng hợp nào có x
i


0 với mọi i thì bài toán là
vô nghiệm.
98 Quy hoạch và quản lý nguồn n"ớc
5.4.3.2. Khái niệm về ph-ơng án cơ sở chấp nhận đ-ợc
a. Biến cơ sở (BCS) và biến tự do (BTD)
Giả sử ta xét một bài toán tối Eu chính tắc có n biến số, với số phEơng trình ràng
buộc đẳng thức là m. Ta gọi:
ã


Tập hợp các biến đEợc chọn tuỳ ý với giả thiết là x
i


o, với i=1
đ
m,
trong đó m là số các phEơng trình ràng buộc đEợc gọi các biến cơ sở.
ã

Tập hợp các biến còn lại x
j
với j
ạ
i, j = (n-m)
đ
n đEợc gọi là biến tự do.
b. Ph-ơng án cơ sở
Là phEơng án mà các biến tự do đEợc chọn bằng không, tức là ta giả định x
j
=0
với mọi j thuộc biến tự do.
Giá trị của các biến cơ sở đEợc xác định theo thủ tục sau:
- Chọn biến cơ sở của bài toán
- Giả định các giá trị của biến tự do bằng không x
j
=0 với mọi j thuộc biến tự do.
- Xác định giá trị của biến cơ sở bằng cách giải hệ các phEơng trình ràng buộc
sau khi thay các giá trị bằng không của biến tự do vào phEơng trình.

c. Ph-ơng án cơ sở chấp nhận đ-ợc
Là phEơng án cơ sở có các biến cơ sở nhận các giá trị dEơng.
d. Ví dụ
Xét bài toán QHTT
1234 56 7
Z6x 2x5xx 4x 3x 12xmin
=+-++-+đ

Với các ràng buộc:
x
1
+ x
2
+ x
3
+ x
4
= 4
x
1
+ x
5
= 2
x
3
+ x
6
= 3 (5-40)
3x
2

+ x
3
+ x
7
= 6
x
i


0, j = 1, 2, , 7
Chọn biến cơ sở:
Ph-ơng án 1:
- Chọn các biến x
4
, x
5
, x
6
, x
7
là biến cơ sở, tức là X = (0, 0, 0, x
4
, x
5
, x
6
, x
7
).
- Thay các giá trị của X vào hệ phEơng trình ràng buộc (5-40) tìm đEợc giá trị

các biến là X = (0, 0, 0, 4, 2, 3, 6).
Ch"ơng 5- Kỹ thuật phân tích hệ thống 99


Các biến cơ sở đều nhận giá trị dEơng vậy phEơng án 1 là ph"ơng án cơ sở chấp
nhận đ"ợc.
Ph-ơng án 2:
- Chọn các biến x
2
, x
5
, x
6
, x
7
là biến cơ sở, tức là X = (0, x
2
, 0, 0,, x
5
, x
6
, x
7
).
- Thay các giá trị của X vào hệ phEơng trình ràng buộc (5-40) tìm đEợc giá trị
các biến là X = (0, 4, 0, 0, 2, 3, - 6).
Trong các biến cơ sở có một biến (x
7
) nhận giá trị âm vậy phEơng án 2 không
phải là ph"ơng án cơ sở chấp nhận đ"ợc.


5.4.4. Giải bài toán quy hoạch tuyến tính
5.4.4.1. Ph-ơng pháp đồ thị
PhEơng pháp đồ thị đEợc dùng khi số biến số
Ê
4. Về phEơng pháp này có thể
tham khảo ở nhiều tài liệu chuyên khảo. Ta xem xét bài toán phẳng qua một ví dụ.
Bài toán:
Tìm nghiệm tối Eu
X(x,x)
12
***
=
sao cho hàm mục tiêu:
Z = c
1
x
1
+c
2
x
2

đ
max (5-41)
Các ràng buộc:

1111221
2112222
i

axaxb
axaxb
x0;i1,2
+
ỡ
ù
+
ớ
ù
=
ợ
(5-42)
Cách giải
Cách giải bài toán phẳng đEợc tiến hành nhE sau:
1. Vẽ miền chấp nhận đEợc (miền D mà X thoả mãn ràng buộc (5-40), xem hình
(5-1).
+ Nếu ràng buộc là đẳng thức thì miền chấp nhận đEợc là điểm A, giao của
đEờng N
1
M
1
và N
2
M
2
.
+ Nếu ràng buộc là bất đẳng thức thì miền chấp nhận đEợc là hình AN
1
OM
2


bao gồm cả biên AN
1
và AM
2
.
2. Vẽ các đEờng cùng mục tiêu (đEờng mức):
+ Cho một giá trị cụ thể Z = Z
0
. Vẽ đEờng x
2
=
o 1
1
12
zc
x
cc
-

100 Quy hoạch và quản lý nguồn n"ớc
+ Thay đổi giá trị Z
0
ta đEợc các đEờng song song. Trên mỗi đEờng hàm mục
tiêu có cùng giá trị. Giá trị Z
0
càng lớn thì đEờng x
2
càng xa điểm 0.
3. Tìm nghiệm tối Eu:

+ Di chuyển đEờng Z
0
(theo giá trị Z
0
) xác định đEợc nghiệm cực đại tại A
+ Nếu đEờng cùng mục tiêu tiếp xúc tại 1 đỉnh thì nghiệm tối Eu là đơn trị.
+ Nếu đEờng cùng mục tiêu tiếp xúc tại 2 đỉnh (1 cạnh) thì nghiệm tối Eu là
đa trị.
X
2

1
2
1
1
0
2
x
c
c
c
z
x -=
N
2
N
1
A
x
2

*
D
O x
1
*
M
2
M
1
X
1

X
2

1
2
1
1
0
2
x
c
c
c
z
x -=
N
2
N

1
A
x
2
*
D
O x
1
*
M
2
M
1
X
1

Hình 5-1 Hình 5-2

Tr"ờng hợp mở rộng: Đối với bài toán có n biến x
1
, x
2
, , x
n
với m ràng buộc.
+ Nghiệm tối Eu là toạ độ của một đỉnh hay nhiều đỉnh miền cho phép. Miền
đa diện là một đa diện lồi (n-m) chiều.
+ Nghiệm đơn trị nếu có 1 đỉnh tiếp xúc với mặt cùng mục tiêu.
+ Nghiệm đa trị nếu có k đỉnh ( k
>

1) tiếp xúc với mặt mục tiêu, tạo thành 1
đơn hình (k-1) chiều. Đó là cơ sở của phEơng pháp đơn hình.
Ví dụ: Bài toán phân bố diện tích cây trồng
Giả sử có khu tEới với diện tích 1800 ha đEợc quy hoạch gieo trồng 2 nhóm cây:
- Nhóm A: Để gieo trồng 1 ha loại cây trồng này cần đến 3 ha diện tích đất (trên
mội ha có 1/3 diện tích đEợc gieo trồng và đất trống chiếm 2/3 diện tích). Giá trị tiền
thu đEợc trên mỗi ha gieo trồng là 300USD/ha. Diện tích lớn nhất gieo trồng loại cây
này là 400 ha.
- Nhóm B: Để gieo trồng 1 ha loại cây này cần đến 2 ha diện tích đất (trên mội
ha có 1/2 diện tích đEợc gieo trồng và đất trống chiếm 1/2 diện tích). Giá trị tiền thu
đEợc trên mỗi ha gieo trồng là 500USD/ha. Diện tích lớn nhất là 600 ha.
Ch"ơng 5- Kỹ thuật phân tích hệ thống 101


Hãy xác định diện tích gieo trồng hai loại cây trên để lợi ích mang lại đạt giá trị
lớn nhất.
Gọi x
A
diện tích gieo trồng nhóm A và x
B
diện tích gieo trồng nhóm B. Gọi Z là
tổng lợi ích hàng năm của hai loại cây trồng, ta có hàm mục tiêu cần cực đại là và các
ràng buộc nhE sau:
AB
A
B
AB
AB
Maximize Z300x500x
x400

x600
3x2x1800
x0x0
=+
Ê
Ê
+Ê



Hình 5-3
Bằng phEơng pháp hình học (xem hình 5-3) có thể tìm đEợc nghiệm tối Eu khi
x
A
= 200 ha và x
B
= 600 ha. Giá trị hàm mục tiêu Z
max
= 300

200+500

600 = 360.000 $.
5.4.4.2. Ph-ơng pháp đơn hình
PhEơng pháp đơn hình là phEơng pháp cơ bản nhất khi giải các bài toán quy
hoạch tuyến tính. PhEơng pháp do G.B. Dantzig đEa ra năm 1948.
102 Quy hoạch và quản lý nguồn n"ớc
Nội dung của phEơng pháp nhE sau: Tìm đỉnh tối Eu của đa diện các nghiệm cho
phép bằng phEơng pháp lần lEợt thử các đỉnh của đa diện. Để việc thử không phải mò
mẫm, ngEời ta đEa ra thuật toán đi từ nghiệm xấu đến nghiệm tốt hơn tức là đi dần đến

nghiệm tối Eu.
Giải bài toán Quy hoạch tuyến tính theo phEơng pháp đơn hình đEợc tiến hành
bằng cách tính thử dần hoặc bằng bảng gọi là bảng đơn hình. DEới đây sẽ trình bày
cách giải bài toán quy hoạch tuyến tính bằng cách lập bảng đơn hình.
1. Bảng đơn hình
Giả sử có bài toán QHTT có hàm mục tiêu dạng chính tắc (5-43) Dạng tìm
min (Bài toán tìm max có thể đEa về dạng tìm min nhE đã trình bày ở trên). Ràng buộc
của bài toán viết dEới dạng tổng quát cho m phEơng trình ràng buộc.

1122 iinn
Z cxcx cx cxmin
=+++++đ
( 5-43)
Với ràng buộc:

1111221ii 1nn 1
2112222ii 2nn 2
j11j22jii jnn j
axax ax axb
axax ax axb


axax ax axb

+++++=
+++++=
+++++=
m11 m22 mimnnm

axax a axb

ỡ
ù
ù
ù
ù
ớ
ù
ù
ù
+++++=
ù
ợ
(5-44)
Hoặc viết gọn dEới dạng:

g(X)axax ax=b
jj11j22jnn j
=+++
;
j1,m
=
(5- 45)
Giả sử có phEơng án cơ sở chấp nhận đEợc X với các biến cơ sở tEơng ứng là x
1
,
x
2
, , x
j
, , x

m
(ký hiệu tổng quát là x
j
, j = 1, 2, , m). Các thông tin về một bEớc lặp
đơn hình thực hiện đối với phEơng án chấp nhận đEợc ghi trong bảng (5-2), gọi là bảng
đơn hình tEơng ứng với phEơng án cơ sở chấp nhận đEợc X.
Các cột và hàng trong bảng (5-2):
- Cột đầu tiên ghi hệ số c
j
của hàm mục tiêu đối với các biến cơ sở tEơng ứng
- Cột 2: ghi tên các biến cơ sở
- Cột 3: Giá trị của các biến cơ sở đEợc xác định trên cơ sở giải hệ m phEơng
trình (5-45) với các biến tự do lấy bằng không.
- Cột cuối cùng ghi hệ số
q
tính theo công thức (5-48) (xem ở mục sau).
Ch"ơng 5- Kỹ thuật phân tích hệ thống 103


- Dòng trên cùng ghi giá trị các hệ số của hàm mục tiêu c
i
với i =1, 2, , n. Giá
trị này đối với các biến lấy bằng không nếu biến đó vắng mặt trong hàm mục tiêu.
- Dòng thứ 2: ghi tên các biến x
i
với i =1, 2, , n
- Các ô tEơng ứng từ cột 4 đến cột 8 ghi hệ số của các số hạng của hệ phEơng
trình ràng buộc (5-44). Hệ số này sẽ bằng không nếu phEơng trình ràng buộc vắng mặt
biến tEơng ứng.
- Dòng cuối cùng là dòng Eớc lEợng các phần tử tEơng ứng với các biến tính theo

công thức:

D
i
=
m
jjii
j1
cac
=
-
ồ
với i =1, 2, , n (5-46)
Ghi chú: Các giá trị c
j
lấy ở cột đầu tiên; c
i
lấy ở hàng trên cùng theo cột tEơng
ứng thứ i; a
ji
lấy ở các ô tEơng ứng với cột i.
Bảng đơn hình lập cho phEơng án chọn đầu tiên đEợc gọi là phEơng án xuất phát.
Bảng 5-2: Bảng đơn hình đối với bài toán tìm min
(1) (2) (3) (4) (5) (6) (7) (8) (9)
c
1
c
i
c
n

Hệ số c
j

Dòng thứ

Tên biến cơ
sở
Giá trị của biến
cơ sở
x
1
x
i
x
n

Hệ số
q
j
c
1
(1) x
1
x
*
1
a
11
a
1i

a
1n
q
1



(2)
c
j
(3) x
j
x
j
*
a
j1
a
ji
a
jn
q
j

(4)
c
m
(5) x
m
x

m
*
a
m1
a
mi
a
mn
q
m

D

(6)
D
1

D
i

D
n



2. Giải bài toán đơn hình dạng bảng
Với bảng đơn hình đEợc xây dựng (bắt đầu từ bảng xuất phát) tiến hành các bEớc
lặp đơn hình đối với phEơng án chấp nhận đEợc nhE sau.
1. Kiểm tra tiêu chuẩn tối Eu:
Nếu các phần tử của dòng Eớc lEợng là không dEơng (

D
i

Ê
0, với mọi i = 1, 2, , n)
thì phEơng án cơ sở chấp nhận đEợc đang xét là tối Eu, thuật toán kết thúc. Điều này
có thể đúng ngay trong lần thử đầu tiên (bảng xuất phát).
2. Kiểm tra điều kiện hàm mục tiêu không bị chặn dEới (vô nghiệm):
104 Quy hoạch và quản lý nguồn n"ớc
Nếu có Eớc lEợng nào đó (
D
i

>
0 với i là bất kỳ) mà các phần tử trong bảng đơn
hình ở cột ứng với nó đều không dEơng ( a
ji

Ê
0, với j =1, 2, , m) thì hàm mục tiêu
của bài toán không bị chặn dEới. Thuật toán kết thúc và vô nghiệm.
Nếu ở 2 bEớc trên không xảy ra phải tìm dòng xoay và cột xoay để lập bảng đơn
hình mới.
3. Tìm cột xoay
Cột xoay của biến đổi sẽ là cột có giá trị Eớc lEợng lớn nhất và không âm:

D
i0
= max (
D

i
với i = 1, 2, , n)
>
0 (5-47)
Cột tEơng ứng x
i0
gọi là cột xoay, các phần tử của cột xoay là a
ji0
.
4. Tìm dòng xoay
Tính giá trị
q
j
:

q
j
=
jji0ij
ij
x/a,nếu a0
,nếu a0
>
ỡ
ù
ớ
+ƠÊ
ù
ợ
(5-48)

Dòng xoay sẽ là dòng có giá trị
q
j
nhỏ nhất:

q
0
= min (
q
j
) (5-49)
Phần tử giao điểm của dòng xoay và cột xoay gọi là phần tử xoay, ký hiệu là
ji
00
a

- Đặt
o
k
ji
a
là các giá trị thuộc cột xoay (cột i
0
) của bảng đơn hình đang xét (gọi là
bảng cũ), j =1, 2, , m.
- Đặt
0
k
ij
a

là các giá trị của dòng xoay (dòng j
0
) của bảng đơn hình đang xét (bảng
cũ), i =1, 2, , n.
5. Lập bảng đơn hình mới
Lập bảng đơn hình mới thực chất là chuyển từ phEơng án cơ sở chấp nhận đEợc
cũ sang phEơng án cơ sở chấp nhận mới. Cách làm nhE sau:
i) Chọn biến mới thay thế cho biến cơ sở thuộc dòng xoay.
ii) Các phần tử ở vị trí dòng xoay thuộc bảng mới bằng các phần tử tEơng ứng ở
bảng cũ chia cho giá trị của phần tử xoay:

k 1 k
jji
ji
0
0
oi
aa/a
+
=
0
với j =1, 2, , m (5-50)
k 1 k
jj i
oi
aa
+
0
,
là giá trị của phần tử mới và phần tử cũ thuộc dòng xoay.

Ch"ơng 5- Kỹ thuật phân tích hệ thống 105


iii) Các phần tử ở vị trí cột xoay của bảng mới đều bằng không, ngoại trừ giá trị
phần tử ở vị trí phần tử xoay bằng 1.
iv) Giá trị của các phần tử còn lại đEợc tính từ phần tử cũ theo công thức:

o
k 1 kkk
ji jijiij ij
00
0
aaaa /a
+
=-
(5-51)

o
k 1 kkk
iiijiij
00
0
a /a
+
D=D-D
(5-52)
Trong đó:
k1
ji
a

+
- giá trị của phần tử tại ô (ij) của bảng mới;
k
ji
a
- giá trị của phần tử tại ô (ij) của bảng cũ;
o
k
ji
a
- giá trị phần tử ô (ji
0
) thuộc hàng thứ j (tEơng ứng với ô đang xét ij) nằm
trên cột xoay i
0
của bảng cũ;
k
ij
0
a
- giá trị phần tử ô (ij
0
) thuộc cột thứ i của phần tử đang xét, nằm trên dòng
xoay j
0
của bảng cũ;
k1
i
+
D

- giá trị Eớc lEợng của bảng mới tại cột thứ i đang xét;
k
i
D
- giá trị Eớc lEợng của bảng cũ cột thứ i đang xét;
i
0
D
- giá trị Eớc lEợng của bảng cũ cột ứng với cột xoay i
0
;
ij
00
a
- giá trị của phần tử xoay của bảng cũ.
Khi đã chuyển sang bảng đơn hình với cơ sở mới việc đánh giá tìm tối Eu lại
đEợc bắt đầu từ bEớc đầu tiên cho đến khi đã rà hết các biến của bài toán.
3. Ví dụ minh họa
Giải bài toán QHTT có dạng:

1234 56 7
Zx6x 32xxx10x 100xmin
=-+++++đ
(5-53)
Với các ràng buộc dạng phEơng trình tuyến tính:

1234 567
1234567
1234567
i

x0x0xx0x6x0x 9
3xx4x0x0x 2xx2
x2x0x0xx2x0x6
x0;i1,2, ,7
++++++=
ỡ
ù
+-++++=
ù
ớ
++++++=
ù
ù
=
ợ
(5-54)
Chọn phEơng án chấp nhận đEợc (phEơng án xuất phát) với các biến cơ sở là x
4
,
x
7
, x
5
. Từ hệ các phEơng trình ràng buộc (5-54) tìm đEợc phEơng án chấp nhận đầu
tiên X = (0, 0, 0, 9, 6, 0, 2). Các thông tin về một bEớc lặp đơn hình thực hiện đối với
phEơng án chấp nhận đEợc ghi trong bảng (5-3).
106 Quy hoạch và quản lý nguồn n"ớc
Theo tiêu chuẩn (5-47) và (5-48) tìm đEợc cột (4) là cột xoay, dòng (3) là dòng
xoay, phần tử xoay có giá trị
00

j i
a 3
=
(có dấu @).
Trong bảng (5-3) các giá trị Eớc lEợng
D
(dòng 5) còn tồn tại các giá trị dEơng
nên chEa phải là phEơng án tối Eu. Ta phải lập bảng đơn hình mới.
Chọn biến cơ sở mới cho dòng xoay là x
1
. Lập bảng (5-4) trên cơ sở bảng đơn
hình (5-3).
Tiếp tục đối chiếu với tiêu chuẩn (5-47) và (5-49) ở bảng đơn hình mới (5-4) tìm
đEợc cột (5) là cột xoay, dòng (3) là dòng xoay, phần tử xoay có giá trị
j i
00
a
= 1/3 (có
dấu @).
Bảng 5-3: Bảng đơn hình số 1 (bảng xuất phát)
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11)
1 -6 32 1 1 10 100 (1) Hệ số c
j

Tên biến
cơ sở
Giá trị
biến cơ sở

x

1
x
2
x
3
x
4
x
5
x
6
x
7
Hệ số
q
j
(2) 1 x
4
9 1 0 0 1 0 6 0 9
(3) 100 x
7
2 3
@
1 -4 0 0 2 1 2/3
(4) 1 x
5
6 1 2 0 0 1 2 0 6
(5)
D


301 108 -432 0 0 198 0

Bảng 5-4: Bảng đơn hình số 2
(1) (2) (3) (4) (5) (6) (7) (8)

(9) (10) (11)
1 -6 32 1 1 10 100 (1) Hệ số c
j

Tên biến
cơ sở
Giá trị
biến cơ sở

x
1
x
2
x
3
x
4
x
5
x
6
x
7
Hệ số q
j

(2) 1 x
4
25/3 0 -1/3 4/3 1 0 16/3

-1/3
+Ơ
(3) 1 x
1
2/3 1 1/3
@
-4/3 0 0 2/3 1/3 2
(4) 1 x
5
16/3 0 5/3 4/3 0 1 4/3 -1/3 16/5
(5)
D

0 23/3
3
92
-

0 0 -8/3
3
301
-



Ch"ơng 5- Kỹ thuật phân tích hệ thống 107



Bảng 5- 5: Bảng đơn hình số 3
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11)
1 -6 32 1 1 10 100 (1) Hệ số c
j

Tên biến
cơ sở
Giá trị
biến cơ sở

x
1
x
2
x
3
x
4
x
5
x
6
x
7
Hệ số q
j
(2) 1 x
4

9 1 0 0 1 0 6 0
(3) -6 x
2
2
3
1 -4 0 0 2 1
(4) 1 x
5
2 -5 0 8 0 1 -2 -2
(5)
D

-23 0 0 0 0 -18 -108

TEơng tự bảng cũ (5-3) trong bảng đơn hình mới (5-4) các giá trị Eớc lEợng
D

(dòng 5) còn tồn tại các giá trị dEơng nên chEa phải là phEơng án tối Eu. Ta phải lập
bảng đơn hình mới (bảng 5-5). Việc lập bảng (5-5) đEơc tiến hành tEơng tự nhE bảng
(5-4). NhEng bảng (5-4) bây giờ là bảng cũ của bảng (5-5).
Khi lập bảng (5-5) đã chọn x
2
là biến cơ sở mới thế chỗ cho biến cơ sở ở dòng
xoay của bảng (5-4).
Trong bảng (5-5) tất cả các giá trị Eớc lEợng
D
(dòng 5) không còn tồn tại các
giá trị dEơng. Bởi vậy, đây là phEơng án tối Eu.
Nghiệm tối Eu là X
*

= (0, 2, 0, 9, 2, 0, 0), giá trị tối Eu của hàm mục tiêu là Z
*
= -1.

5.5. Quy hoạch phi tuyến
5.5.1. Khái niệm về quy hoạch lồi
5.5.1.1. Tập lồi
Tập C
ẻ
R
n
đEợc gọi là lồi nếu x
1

ẻ
C, x
2
ẻ
Cthì đoạn x
1
x
2
cũng thuộc C, tức là C
chứa tất cả các điểm có dạng:
x =
l
x
1
+ (1-
l

) x
2
; 0
Ê

l

Ê
1 (5-55)
Hình 5-4 minh hoạ tập lồi thoả mãn biểu thức dạng (5-55). Hình 5-5 không thỏa
mãn biểu thức dạng (5-55) không phải tập lồi.
5.5.1.2. Hàm lồi
a. Định nghĩa
Hàm f(x) là hàm lồi trên tập lồi C nếu với mọi cặp (x
1
, x
2
) thuộc C và mọi
l

thuộc
[
0,1
]
, ta có:
f
[l
x
1
+ (1-

l
)x
2
]

Ê

l
f(x
1
)+ (1-
l
)f(x
2
) (5-56)
108 Quy hoạch và quản lý nguồn n"ớc
Có nghĩa là điểm x =
l
x
1
+ (1-
l
)x
2
trong
[
x
1
, x
2

]
thì mọi điểm của đồ thị f(x)
luôn nằm dEới M
1
M
2
(hình 5-6).
x
1
x
2
x
2
x
1

Hình 5-4 Hình 5-5

b. Cực trị của hàm lồi
Bất kỳ cực tiểu địa phEơng nào của hàm lồi trên tập lồi cũng là cực tiểu tuyệt đối
của hàm trên tập đó.
NhE vậy, trong quy hoạch lồi thì giá trị tối Eu địa phEơng cũng là giá trị tối Eu
toàn thể.
f(x)
x
x
1
x
2
x

M
1
M
2

x
L
l
X
*
,
l
*

Hình 5-6 Hình 5-7

5.5.2. Bài toán quy hoạch lồi tổng quát
5.5.2.1. Phát biểu bài toán
Tìm X = (x
1
, x
2
, , x
n
) sao cho hàm mục tiêu:
F(X) = F(x
1
, x
2
, , x

n
)
đ
min (5-57)
Ch"ơng 5- Kỹ thuật phân tích hệ thống 109


Với ràng buộc X
ẻ
C; g
j
(X)
Ê
0 với j =1, 2, , m (5-58)
Trong đó C là tập lồi; F, g là các hàm lồi trên C.
5.5.2.2. Điều kiện tối -u
a. Miền nghiệm chấp nhận đ-ợc
D =
{
x
ẻ
C; g
j
(X)
Ê
0
}
j =1, 2, , m
b. Điểm yên ngựa (hình 5-7)
ỉ

Hàm Lagrange L(X,
l
) = F(X) +
m
jj
j1
g(X)
=
l
ồ
(5-59)
với véc tơ
l
= (
l
1
,
l
2
, ,
l
m
)
ỉ
Điểm yên ngựa của hàm L(X,
l
) là điểm ( x*,
l
*)
với X

ẻ
D;
l


0 sao cho (X,
l
*)
Ê
L(X*,
l
*)
Ê
L(X*,
l
) (5-60)

c. Điều kiện cần và đủ của tối -u
Có hai định lý để nhận biết X
*
là giá trị tối Eu.
Định lý 1:
Điểm X
*
là tối Eu khi và chỉ khi F
z
(X
*
) =
ỏẹ

F(X
*
), Z
ủ


0 với mọi Z
ẻ
D(X
*
).
Nghĩa là, nếu đi từ X
*
theo mọi hEớng mà F(X) đều tăng thì hàm F(X) đạt giá trị min
tại X
*
.
ỏẹ
F(X
*
), Z
ủ
là đạo hàm theo hEớng Z của hàm F(X) tại điểm X
*
.
Định lý 2 (Định lý Kuhn - Tucker):
Giả sử bài toán quy hoạch lồi thoả mãn điều kiện Slater:
Với mọi X
0
thuộc C thoả mãn ràng buộc g

j
(X)
<
0 với j =1, 2, , m)
Điều kiện cần và đủ để X
*
trở thành nghiệm tối Eu là tồn tại một véc tơ m chiều,
không âm:
l
= (
l
1
,
l
2
, ,
l
m
) sao cho cặp (X
*
,
l
*
) là điểm yên ngựa của hàm Lagrange L(X,
l
*
).
5.5.2.3. Khái niệm về quy hoạch lõm
Hàm F(X) là hàm lõm nếu hàm - F(X) là hàm lồi.
Hàm F(X) là lõm khi:

F
[l
x
1
+ (1-
l
)x
2
]



l
F(x
1
)+ (1-
l
)F(x
2
) (5-61)
Với mọi x
1
, x
2

ẻ
R
n
và mọi
l

nằm trong khoảng 0
Ê

l

Ê
1
110 Quy hoạch và quản lý nguồn n"ớc
5.5.3. Bài toán quy hoạch phi tuyến tổng quát
Phát biểu bài toán
Bài toán quy hoạch phi tuyến tổng quát có dạng: Tìm giá trị tối Eu (max hoặc
min) của hàm mục tiêu
F(X)
đ
min (5-62)
với ràng buộc :
g
j
(X)
Ê
b
j
; j=1, 2, , m (5-63)
Trong đó: X = (x
1
, x
2
, , x
n
)

ẻ
R
n
; các hàm F(X) và g
j
(X) là phi tuyến.
Tập các nghiệm chấp nhận đEợc:
D =
{
X
ẻ
R
n
: g
j
(X)
Ê
b
j
; j =1, 2, , m
}
(5-64)
Chú ý:
Đối với bài toán tìm cực đại dạng: F(X)
đ
max có thể đEa về dạng tìm cực tiểu
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
5.5.4. Tối "u của bài toán phi tuyến tổng quát
Tối Eu toàn bộ (tối Eu tuyệt đối):
max: F(X
*
)

F(X); X
ẻ
D (5-65)
min: F(X
*
)
Ê
F(X); X
ẻ
D
Tối Eu địa phEơng (tối Eu tEơng đối):
Nếu tồn tại lân cận V của X

*
sao cho:
max: F(X
*
)

F(X); X
ẻ
D
ầ
V (5-66)
min: F(X
*
)
Ê
F(X); X
ẻ
D
ầ
V
X
*

là nghiệm tối Eu; F(X
*
) là giá trị tối Eu của hàm mục tiêu F(X).
Trên hình 5-8 (đối với hàm 1 biến các điểm A, C là cực tiểu địa phEơng và A là
cực tiểu tuyệt đối; điểm B và D là cực đại địa phEơng với D là cực đại tuyệt đối.
Trong quy hoạch lồi thì tối Eu địa phEơng cũng là tối Eu toàn thể. Trong quy
hoạch phi tuyến tổng quát thì tối Eu toàn thể cũng là tối Eu địa phEơng, nhEng điều

ngEợc lại không đúng.
Ch"ơng 5- Kỹ thuật phân tích hệ thống 111



A
B
C
D
f(x
)
x


Hình 5-8

Trong quy hoạch tuyến tính hàm mục tiêu đạt giá trị tối Eu tại điểm cực biên của
miền D. Trong quy hoạch phi tuyến, hàm mục tiêu có thể đạt giá trị tối Eu tại trong
hoặc trên biên của D và có thể tồn tại một giá trị tối Eu địa phEơng.
Không có phEơng pháp chung nào có hiệu quả để giải bài toán quy hoạch phi
tuyến. Các phEơng pháp có thể chia làm 2 nhóm:
- Các phEơng pháp gradient có dùng đạo hàm.
- Các phEơng pháp trực tiếp không dùng đạo hàm.


5.5.5. Bài toán quy hoạch phi tuyến không có ràng buộc
5.5.5.1. Bài toán
F(X)=F(x
1
, x

2
, x
3
, , x
i
, ,x
n
)
đ
min (5-67)
Trong đó: X = (x
1
, x
2
, , x
n
)
ẻ
E
n

5.5.5.2. Điều kiện cần và đủ của tối -u địa ph-ơng
a. Điều kiện cần
Nghiệm tối Eu phải là những điểm mà:
-
x0
F(X)
ẹ
(các điểm dừng) (5-68)
- Hàm F(X

0
) khả thi tại X
0

Trong đó :
x0
F(X)
ẹ
là các đạo hàm riêng cấp 1, tức là:

x0
F(X)
ẹ
=
1
2
n
F(X)
x
F(X)
x


F(X)
x
ả
ả
ả
ả
ả

ả
(5-69)
112 Quy hoạch và quản lý nguồn n"ớc
b. Điều kiện đủ
Những điểm dừng phải thoả mãn điều kiện đủ: Điểm dừng là cực trị nếu ma trận
Hessein có xác định dEơng đối với bài toán cực tiểu và xác định âm đối với bài toán
cực đại. Ma trận Hessein có dạng:
2
n
x
F
2

i
x
n
x
F
2

2
x
n
x
F
2
1
x
n
x

F
2

n
x
j
x
F
2

i
x
j
x
F
2

2
x
j
x
F
2
1
x
j
x
F
2


n
x
2
x
F
2

i
x
2
x
F
2

2
2
x
F
2
1
x
2
x
F
2
n
x
1
x
F

2

i
x
1
x
F
2

2
x
1
x
F
2
2
1
x
F
2
))((
ả
ả
ảả
ả
ảả
ả
ảả
ả
ảả

ả
ảả
ả
ảả
ả
ả
ả
ảả
ả
ảả
ả
ảả
ả
ả
ả
ảả
ả
ììì
ảả
ả
ảả
ả
ảả
ả
=
o
XFH
(5-70)
Ma trận Hessein là ma trận đối xứng có dạng tổng quát A = (a
ij

) cấp n, có xác
định dEơng khi và chỉ khi định thức cấp n và mọi định thức ứng với phần tử chéo chính
đều dEơng. Tức là:

111n
1112
n 2111
2122
n1 nn
a a
aa
0, ,0;a0
aa
a a
D>D=>D=>
(5-71)
Ví dụ: Tìm min F(X) = (x
1
-2)
2
+ (x
2
- 1)
2

Ta có:

FF
2(x12);2(x21)
x1 x2

ảả
=-=-
ảả

Các điểm dừng tại
FF
0; 0
x1 x2
ảả
==
ảả
khi
1
00
2
x 2; x 1
==

Tính đEợc:
222
22
1212
FFF
0;2;2
xx
xx
ảảả
===
ảả
ảả


Vậy ma trận Hessein H là:
Ch"ơng 5- Kỹ thuật phân tích hệ thống 113



ỳ
ỷ
ự
ờ
ở
ộ
20
02

Ma trận con chính thứ nhất bằng 2
>
0; ma trận chính thứ hai bằng 4
>
0. Vì vậy
ma trận Hessein là xác định dEơng và hàm F(X) có cực tiểu tại X
0
= (2,1).
5.5.6. Giải bài toán tối "u phi tuyến không ràng buộc bằng ph"ơng
pháp sử dụng đạo hàm
Có hai loại phEơng pháp giải bài toán tối Eu phi tuyến:
- PhEơng pháp dùng đạo hàm: PhEơng pháp gradient; phEơng pháp hEớng dốc
nhất; phEơng pháp Newton v.v
- PhEơng pháp không dùng đạo hàm: PhEơng pháp lặp trực tiếp; phEơng pháp
Pwell; phEơng pháp Nelder và Mead v.v

5.5.6.1. Ph-ơng pháp gradient
PhEơng pháp gradient là phEơng pháp đEợc dùng phổ biến để tìm cực tiểu của
hàm. PhEơng pháp luôn hội tụ nếu hàm có nghiệm tối Eu. Theo phEơng pháp này phép
lặp đEợc tính theo công thức:
X
(k+1)
= X
(k)
-
l
(k)

ẹ
F(X
(k)
) (5-72)
Trong đó:
k

0: bEớc lắp thứ k.
l
(k)

>
0: là hệ số xác định độ dài của bEớc đi theo hEớng gradient. Có thể chọn
l
= const cho cả quá trình lặp, hoặc có thể chọn giá trị tối Eu của
l
theo từng bEớc
lặp theo phEơng pháp tối Eu 1 tham số.

ẹ
F(X
(k
): hEớng

ngEợc lại của gradient tại X
(k)
.
Ban đầu ta chọn điểm xuất phát X
0
tùy ý. Nếu dãy X
k
không hội tụ ta lấy
l
nhỏ
hơn. Khi
l
đủ nhỏ thì X
k
sẽ hội tụ về X
*
.
Ví dụ: Tìm min của f(x) = x
2
+3
Giải:

ẹ
f(x) = 2x. Chọn x
(0)

=1
đ
2 x
(0)
= 2
ạ
0
x
(1)
= x
(0)
-
lẹ
f(x
(0)
) = 1 - 2
l
;
l

>
0 .
ẹ
f(x
(1)
) =2 x
(1)
= 2(1 - 2
l
);

114 Quy hoạch và quản lý nguồn n"ớc
Nếu chọn
l

ạ
1/2 thì
ẹ
f(x
(1)
)
ạ
0
Và x
(2)
= (1 - 2l) - 2l(1 - 2l) = (1 - 2l)
2

Tiếp tục sẽ đEợc ở phép lặp thứ k có
x
(k)
= (1 - 2
l
)
k

NhE vậy, nếu 0
<

l<
1 thì x

(k)

đ
0 khi k
đ
+
Ơ

Điểm x
*

= 0 là điểm cực tiểu và f(x
*
) = 3.
5.5.6.2. Ph-ơng pháp h-ớng dốc nhất
PhEơng pháp hEớng dốc nhất đEợc thực hiện theo trình tự sau:
Chọn điểm xuất phát; tính
ẹ
F(X
(k)
);
(k)
F(Xẹ
.
Tính véc tơ đơn vị theo hEớng
ẹ
F(X
(k)
):
S

(k)
=
(k)
(k)
F(X )
F(X
ẹ
ẹ

Đặt X
(k)
= X
(k)
-
l
k
S
(k)

Dùng tối Eu hoá 1 tham số:
F(X
(k+1)
) = F(
l
k
)
đ
min từ đó tìm đEợc giá trị tối Eu
*
k

l
.
Chọn điểm mới: X
(k+1)
= X
(k)
-
*
k
l
S
(k)
.
Tiếp tục thực hiện các phép lặp tiếp theo.
Ví dụ: Tìm min của hàm Rosenbrock có dạng
F(X) = 100(x
2
- x
1
2
)
2

Giải:
Chọn điểm xuất phát X
(k)
= (-0,5; 0,5)
Tính
ẹ
F(X

(k)
) và
(k)
F(X )
ẹ
:

FF
47; 50
x1 x2
ảả
==
ảả

(k)
F(X )
ẹ
=
22
47 50
+
= 68,6
Ch"ơng 5- Kỹ thuật phân tích hệ thống 115


Tính véc tơ đơn vị theo hEớng
ẹ
F(X
(k)
):

S
(k)
=
(k)
(k)
F(X)
F(X
ẹ
ẹ
=
147
68,650
ộự
ờỳ
ởỷ
= (0,658; 0,729)
T

Véc tơ S
(k)
vuông góc với đEờng cùng mục tiêu của F(X) tại X
(k)
= (-0,5; 0,5)
Đặt X
(k)
= X
(k)
-
l
k

S
(k)

hay : X
(k0
=
k
0,5 47
0,550
-
ộự
ộự
-l
ờỳ
ờỳ
ởỷ
ởỷ

Dùng tối Eu hoá 1 tham số:
F(X
(k+1)
) = F(
l
k
) =100
[
0,50.729
l
k
(0,5+0,685

l
k
)
2
]
+(1,5+0,685
l
k
)
đ
min từ đó
tìm đEợc giá trị tối Eu
*
k
l
= 0,164
Chọn điểm mới: thay
l
=
*
k
l
=0,164 vào công thức X
(k+1)
= X
(k)
-
*
k
l

S
(k)
.
X
(k+1)
=
0,5 47
0,164
0,550
-
ộự
ộự
-
ờỳ
ờỳ
ởỷ
ởỷ
đ
F(X
(k)
) = 2,6
Tiếp tục tính S
(k+1)
, cuối cùng quá trình tính hội tụ tại X
*
= (1;1) và giá trị tối Eu
của hàm F(X
*
) = 0.
Cũng có thể dùng

k
l
= const cho cả quá trình.
5.5.6.3. Ph-ơng pháp Newton
PhEơng pháp Newton đEợc sử dụng giải phEơng trình có nghiệm gần đúng, đồng
thời cũng là phEơng pháp ứng dụng để giải các bài toán tối Eu phi tuyến.
1. Ph-ơng pháp Newton giải ph-ơng trình có nghiệm gần đúng
PhEơng pháp lặp Newton-Raphson là một phEơng pháp khá hiệu quả khi phải
giải các phEơng trình có nghiệm gần đúng, và do đó đEợc áp dụng khá rộng rãi đối với
các bài toán thuộc hệ thống nguồn nEớc. Ta bắt đầu từ bài toán có một biến số.
a. Bài toán một chiều
Giả sử phải tìm nghiệm xấp xỉ của hàm số f(x) = 0. Nếu hàm f(x) có đạo hàm
khác không, tức là
Â
ạ
f
(x)
0
với
"
x. Khi đó xấp xỉ nghiệm ở phép lặp n bất kỳ có
dạng:

f(x)
n
xx
n
n1
f(x)
n

=-
+
Â
(5-73)