Trường Đại học Công nghiệp thành phố Hồ Chí Minh

Khoa Công nghệ Cơ khí

CHƯƠNG 06:
TỐI ƯU HÀM NHIỀU BIẾN SỐ
VỚI RÀNG BUỘC TỔNG QUÁT:
PHƯƠNG PHÁP CỔ ĐIỂN
Thời lượng: 3 tiết


2

Tối ưu hàm nhiều biến với ràng buộc tổng quát

Tìm cực trị (Optimum) của hàm nhiều biến sau:
Với m điều kiện ràng buộc bất đẳng thức:

f x

g j x  0
j  1, 2,

Với p điều kiện ràng buộc đẳng thức:

hl  x   0
l  1, 2,

Với:

x   x1


m  ; η  1 2
T

 p 


p
m
g j
hl

L

f
  x, λ , η  
 x     j  x    j  x   0; i  1..n
 xi
xi
xi
xi
j 1
l 1

j  1..m
 j g j  x   0;

j  1..m
 g j  x   0;


x 
;λ 
;η 
 
 
 
 
 
 
 xn 
m 
 p 

1

2

Giải hệ
(1)÷(5) với
(n+m+p) ẩn,
ta có:


1

2

Kiểm tra J1 véctơ Gradient của hàm bất đẳng thức ràng buộc g
tại điểm cực trị và p véc tơ Gradient của hàm đẳng thức ràng
buộc h tại điểm cực trị x*, phải là không phụ thuộc tuyến tính

vJ

1

x2

vJ

xn 

1

vJ

1

1

, h p  x  
vJ

2

5

1

p

T

 a12 
 1
 2
a2 
a2 


v1 
; v2 
;
 
 
 1
 2
 aN 
 aN 

 a1M 
 M
a2 

; vM 
 
 M
 aN 

a

a


M
1
M
2

Đưa về
dạng bậc
thang

Xác định
hạng
Rank(A)

6


Không phụ thuộc/phụ thuộc tuyến tính
 a11
 1
a2

 A  
N xM
 1
 aN

a12
2
2


9 
v1    ; v 2    ; v 3    ;
2 
 2
 4
 
 
 

2
0
 
 
1 

2
6
 A   
2

 2

2
4 6

3 9  Gaussian
0
Elimination



9

Tối ưu hàm nhiều biến với ràng buộc tổng quát

Tìm cực trị hàm sau: f  x1 , x2 , x3   x12  2 x22  30 x1  16 x3  min/ max
n  3
x

6
x

3
x

0;
x

0
Với 2 ràng buộc bđt: 1
2
3
3

m  2
Với 1 ràng buộc đt: 5 x1  3x2  4 x3  20  0
p 1

L  x, λ , η   x12  2 x22  30 x1  16 x3  1  x1  6 x2  3 x3   2   x3  
 1  5 x1  3 x2  4 x3  20 
x   x1


2  0

5 x1  3 x2  4 x3  20  0

1
 2
 3
 4
 5
6
7
8
9
10 

Giải hệ
PT tìm
6 ẩn
Hệ PT (4) và (5) sẽ
tương đương với 4
trường hợp con như
sau:


11

1) Trường hợp 1:
2 x1  30  1  51  0
4 x  6  3  0



2) Trường hợp 2:
2 x1  30  1  51  0
335
 
4 x  6  3  0
x1  

2
1
1

59

16  31  2  41  0
165



x2 

59
1  0
 
 x  0
 x3  0
3
 


2 x1  30  1  51  0
1695
 
4 x  6  3  0
 x1   947
1
1
 2

16  31  2  41  0
 x  1641

 2 947
 x1  6 x2  3 x3  0

3847

  0

 x3 
2

947

 x1  6 x2  3 x3  0
 
1280
0
 x3  0
1  


16  31  2  41  0
 x   20

 2
33
x

6
x

3
x

0
2
3
 1
 
x3  0
 x  0


3
 

2650
 x1  6 x2  3x3  0
1  
1089




 x1   1 
 x1   0 
 g1    
 g 2    
g1  x   
   6  x ; g 2  x   
   0  x ;
 x2   3 
 x2   1
 g1   
 g 2   




 x3 
 x3 
 h1 



x
 1 5
 h1   

h1  x   


 4 
1) Trường hợp 1: Do λ1 = 0 và λ2 = 0 nên

5
  A  h1  x    3  x
 4 

Trường hợp này không xét 2
grandient của g vì các λ của
chúng = 0. Grandient của h
đứng 1 mình nên không phụ
thuộc tuyến tính với ai.

2) Trường hợp 2: Do λ1 = 0 nên


  A    g 2  x 

0 5




h1  x     0 3 
 1 4 

Có 2 định thức
thành phần khác 0
nên 2 véctơ này
không phụ thuộc

3 véctơ trên không phụ thuộc tuyến tính nên trường hợp 4
cũng là cực trị địa phương.
Điểm dừng ở trường hợp 1 là điểm cực tiểu với giá trị nhỏ
nhất. 3 trường hợp còn lại là cực đại địa phương. Trường
hợp 4 là điểm cực đại toàn cục.


Bài toán tối ưu hóa các hàm lồi

18

Nếu hàm mục tiêu f(x) cùng các hàm ràng buộc gj(x), hl(x) là
những hàm số lồi thì bài toán gọi là các bài toán tối ưu hàm
lồi (convex programming problem)
 Khi đó nếu các λj ≥ 0 thì các hàm Lagrange L cũng sẽ là
những hàm lồi
 Khi đó thì tại các điểm dừng x* cũng sẽ chính là điểm cực
tiểu tuyệt đối (toàn cục)
 Điều kiện KKT sẽ trở thành điều kiện cần và đủ để tìm min
toàn cục
 Nếu bài toán tối ưu là tìm cực tiểu các hàm lồi, thì sẽ
không có điểm dừng cũng như các cực đại địa phương.
Tuy nhiên những bài toán kỹ thuật thực tế rất khó xác
định được các hàm số là lồi hay không.


19

Tối ưu hàm nhiều biến với ràng buộc tổng quát
2



L  x, λ , η   6 x1  2 x2  4 x32  1  2 x1  2 x2  x3   2   x2  
 1  2 x1  4 x2  x32 

x   x1

x2

x3  ; λ   1 2  ; η  1 
T

T

T


20

 L
 x  6  21  21  0
 1
 L
 x  2  21  2  41  0
 2
 L
 x  8 x3  1  21 x3  0
 3
1  2 x1  2 x2  x3   0


8
9
10 

Giải hệ
PT tìm
6 ẩn
Hệ PT (4) và (5) sẽ
tương đương với 4
trường hợp con như ví
dụ trước.


21

1) Trường hợp 1:
6  21  21  0

2  21  2  41  0
8 x    2 x  0
1 3
 3 1
1  0

2  0

2 x1  2 x2  x3  0
 x  0
 2
1  0

 2
2 x1  4 x2  x32  0

1
 2

Vô nghiệm


23

3) Trường hợp 3:
6  21  21  0

2  21  2  41  0
8 x    2 x  0
1 3
 3 1
2 x1  2 x2  x3  0

2  0

2 x1  2 x2  x3  0
 x  0
 2
1  0
  0
 2
2 x1  4 x2  x32  0



2  21  2  41  0
8 x    2 x  0
1 3
 3 1
2 x1  2 x2  x3  0

 x2  0

2 x1  2 x2  x3  0
 x  0
 2
1  0
  0
 2
2 x1  4 x2  x32  0

1
 2

Vô nghiệm


25

Tính Gradient của các hàm ràng buộc gj và hl:
 g1 
 g 2 



h1  x   
   4   h1  x    4 
 h2   2 x 
 5
3

 h1 
 
 8


 x3 