Thuật toán chuyển bài toán qui hoạch phi tuyến về qui hoạch tuyến tính

T¹p chÝ Khoa häc & C«ng nghÖ - Sè 3(43)/N¨m 2007 
32 
THUẬT TOÁN CHUYỂN BÀI TOÁN QUI HOẠCH PHI TUYẾN 
VỀ QUI HOẠCH TUYẾN TÍNH 
 Nguyễn Hữu Công (Trường ĐH Kỹ thuật Công nghiệp - ĐH Thái Nguyên) 
1. Đặt vấn đề 
Trong lý thuyết điều khiển tự động, khi giải bài toán tối ưu hoặc tìm thông số tối ưu cho 
bộ điều chỉnh, ta thường sử dụng chỉ tiêu tích phân bình phương sai lệch. Nếu ta áp dụng 
phương pháp số để tìm nghiệm tối ưu, thường dẫn tới việc giải bài toán qui hoạch phi tuyến sau: 
Tìm min của ( )
2
*
0 0
n m
i i ij j
i j
F w c q a w
= =
 
= − 
 
∑ ∑ (1) 
Với ràng buộc A1 ≤ wj ≤ A2 (j = 0,1,...,m) (2) 
Trong đó wj là Nn cần tìm, qi*, aij, ci là các hằng số dương đã biết 
Như vậy, bài toán được đặt ra là hãy tìm cực tiểu hàm (1) phụ thuộc vào m+1 biến wj 
tuân theo ràng buộc (2). 
Rõ ràng (1) là bài toán qui hoạch phi tuyến của các biến wj và các ràng buộc (2) là tuyến 
tính. Với bài toán này có thể tìm nghiệm đúng bằng phương pháp số sau một số hữu hạn phép 
lặp[2], [3]. 
Mặc dù nghiệm của bài toán qui hoạch bậc hai có thể thu được sau một số hữu hạn phép 
lặp nhưng thuật toán của nó phức tạp hơn và thời gian tính toán lâu hơn so với thuật toán của 
phương pháp đơn hình cho bài toán quy hoạch tuyến tính. 
2. Nội dung của thuật toán 
Thay vì việc sử dụng chỉ tiêu tích phân bình phương sai lệch, ta đặt chỉ tiêu là tích phân 
trị tuyệt đối của sai lệch. Như vậy, thay vì tìm min của (1) với ràng buộc (2), ta tìm min của bài 
toán tương đương sau: ( ) *
0 0
n m
i i ij j
i j
L w c q a w
= =
= −∑ ∑ (3) 
Để giải bài toán tìm min (3) với các ràng buộc (2), ta có thể đưa về bài toán quy hoạch 
tuyến tính bằng cách dùng các kỹ thuật như sau[1]: 
Ta đưa ra ( )2 1n + biến phụ không âm là iy và iz (i = 0,1,... n). Ta sẽ chứng minh rằng 
min của (3) với ràng buộc (2) tương đương với min của 
( )ii
n
i
i zycL += ∑
=0
' (4) 
với ràng buộc: 
( )
*
0 0,1,...,
0, 0
m
ij j i i i
j
i i
a w q y z
i n
y z
=

− = − 
=
≥ ≥ 
∑
 (5) 
T¹p chÝ Khoa häc & C«ng nghÖ - Sè 3(43)/N¨m 2007 
33
và 1 2jA w A≤ ≤ với j = 0, 1, 2,, m 
 Khi đó với bất kỳ [wj, yi, zi] nào là phương án tối ưu của bài toán (4), (5) thì zi , yi phải 
thoả mãn điều kiện: 
0iz = nếu : 
*
0
m
ij j i
j
a w q
=
−∑ không âm và 
0iy = nếu: 
*
0
m
ij j i
j
a w q
=
−∑ âm 
 Với cách đặt biến phụ như vậy, ta sẽ có: 
minL = minL’ (6) 
Ta có thể chứng minh các kết luận trên như sau 
Bổ đề 1: Giả sử ( ), ,w z y là một phương án tối ưu của bài toán (4), (5) khi đó ta phải có: 
a, . 0iiy z = với ∀i = 0, 1,.., n (tức là 1 trong 2 biến iy hoặc iz phải = 0). 
b, )y,z,w(L)w(L '= 
 Chứng minh: 
a, Giả sử trái lại iz . iy ≠ 0. Do 0iy ≥ và 0iz ≥ nên lúc đó ta phải có iz > 0, iy > 0 
Ta đặt : 
h = min { iz , iy }; ta thấy h > 0 (7) 
lại đặt : hyy i
'
i −= 
và hzz i
'
i −= 
Rõ ràng: 0y;0z 'i
'
i ≥≥ và với mỗi i thì hoặc yi’
 = 0 hoặc zi’ = 0 nghĩa là ' ' 0i iy z = với 
mọi i. 
Mặt khác ta thấy: ii
'
i
'
i zyzy −=− . Vì thế w j, y'i, z'i vẫn thoả mãn điều kiện (5) 
nghĩa là [ w j, y'i, z'i] cũng là phương án của bài toán (4),(5) 
Song ( ) ( )' ' ' '
0
' , ,
n
j i i i i i
i
L w y z c y z
=
= +∑ ( )∑
=
−+=
n
i
iiii hczyc
0
).2( (8) 
 ở đây chú ý : h>0 , ci > 0 với ∀ i=0,1.n 
Vậy ta dễ thấy ( ) ( ) ( )' '
0
' , , ' , ,
n
j i i i i i j i i
i
L w z y c y z L w y z
=
< + =∑ (9) 
T¹p chÝ Khoa häc & C«ng nghÖ - Sè 3(43)/N¨m 2007 
34 
Điều này trái với giả thiết ( )iij y,z,w là phương án tối ưu của (4), (5). 
 Tóm lại ta phải có ii z.y = 0 với ∀i = 0,1 ,..n. 
b, Do ( z,y,w ) là phương án tối ưu của bài toán (4), (5) nên phải thoả mãn ràng buộc 
(5). Theo chứng minh ở phần a, với mỗi i = 0,1,2,n thì hoặc 
0iy = hoặc 0iz = . 
- Nếu 0iz = thì *i
m
0j
jij qwa −∑
=
 = iy ≥ 0 
từ đó ∑
=
−
m
0j
jij
*
i waq = iy + iz (10) 
- Nếu 0iy = thì 
*
i
m
0j
jij qwa −∑
=
 = - iz ≤ 0 
từ đó *
0
m
i ij j i i
j
q a w y z
=
− = =∑ (11) 
Tóm lại ta luôn có: 
( )* 'ij j
0 0 0
(w) w ( ( , , )
n m n
i i i i i
i j i
L c q a c y z L w z y
= = =
= − = + =∑ ∑ ∑ (12) 
Vậy )y,z,w(L)w(L '= (đpcm) ‘
‘‘
‘ (13) 
Mệnh đề 1: Giả sử ( z,y,w ) là phương án tối ưu của bài toán (4) ,(5). Khi đó w chính là 
phương án tối ưu của bài toán (3) với ràng buộc (2). 
Chứng minh: Thật vậy, giả sử trái lại, ∃ wˆ là phương án của bài toán (3), (2) 
với ( ) ( )wˆ wL L= . Từ wˆ ta sẽ xây dựng phương án [ wˆ , zˆ,yˆ ] của bài toán (4), (5) 
như sau: 
Đặt *
0
ˆ ˆ.
m
ji ij i
j
y a w q
=
= −∑ và ˆ 0iz = 
 nếu *
0
ˆ. 0
m
jij i
j
a w q
=
− ≥∑ 
T¹p chÝ Khoa häc & C«ng nghÖ - Sè 3(43)/N¨m 2007 
35
Đặt *
0
ˆˆ .
m
i jij i
j
z a w q
=
 
= − − 
 
∑ và ˆ 0iy = 
 nếu ∑
=
<−
m
j
iij qa
0
* 0 
Khi đó ta có : 
a) Bộ tham số ˆ ˆ ˆ, ,w y z  
 
 cũng là phương án của bài toán (4), (5) 
b) *
0
ˆ ˆˆ .
m
i i ij ji
j
y z q a w
=
+ = −∑ , nghĩa là ( ) 'ˆ ˆ ˆ ˆw , ,L L w y z =  
 
 (14) 
Theo giả thiết, theo (14) và theo bổ đề 1 (13) ta có : 
'
0
ˆ ˆ ˆˆ ˆ, , ( )
n
i i i
i
L w y z c y z
=
 
= + = 
 
∑ 
=
* '
0 0
ˆ ˆ. . ( ) ( ) ( , , )
n m
i i ij j
i j
c q a w L w L w L w y z
= =
− = < =∑ ∑ (15) 
trái với giả thiết ( ), ,w y z là phương án tối ưu của bài toán (4), (5) (đpcm) ‘ . 
3. Kết luận 
Qua các chứng minh trên ta có kết luận: 
 Có thể thay thế việc tìm lời giải cho bài toán (1), (2) bằng việc cực tiểu hoá bài toán (4) 
với ràng buộc (5). 
Dùng phương pháp đơn hình giải bài toán (4), (5), ta sẽ nhận được phương án tối ưu của 
bài toán sau một số hữu hạn phép lặp. 
 Dễ thấy việc tìm lời giải cho bài toán (4), (5) sẽ đơn giản hơn nhiều so với bài toán (1), (2). 
TÓM TẮT 
Bài báo nghiên cứu việc chuyển bài toán qui hoạch phi tuyến về bài toán qui hoạch tuyến 
tính. Việc đưa ra thuật toán này sẽ làm cho việc lập trình đơn giản hơn, thời gian tính toán ngắn 
hơn. Điều này rất có ý nghĩa trong khoa học nói chung và trong lĩnh vực Điều khiển Tự động 
nói riêng và mở ra khả năng áp dụng vào thực tế. 
Mọi sự quan tâm xin liên hệ: 
TS. Nguyễn Hữu Công; Khoa Điện tử, Trường Đại học Kĩ thuật Công nghiệp - Đại học 
Thái Nguyên. 
ĐT: 0913589758. Email: huucongdk55@yahoo.com 
T¹p chÝ Khoa häc & C«ng nghÖ - Sè 3(43)/N¨m 2007 
36 
Summary 
This paper proposes a method used to convert nonlinear programming problem into 
linear programming problem. A new algorithm used in this paper can support for 
programming more easily, and calculating time is shorter. This is very significant in science in 
general and in automation control in special and open the applying capabilities in practice 
Further information, please contact Dr. Nguyen Huu Cong, Electronics Engineering 
Faculty, Thainguyen University of Technology. Tel: 0913589758. Email: huucongdk55@ 
yahoo.com 
TÀI LIỆU THAM KHẢO 
[1]. Nguyễn Hữu Công (2003), “Điều khiển tối ưu cho đối tượng có tham số phân bố, biến đổi 
chậm”, Luận án Tiến sỹ kỹ thuật. 
[2]. Jinghao Zhu (2006), A Numerical Method of the Optimal Control Approach to Nonlinear 
Programming, Problems. 
[3]. Bùi Minh Trí (1999), Qui hoạch toán học, Nxb Khoa học Kĩ thuật, Hà Nội.