Tối ưu hóa trong thiết kế cơ khí - Chương 05: Tối ưu hàm nhiều biến số với ràng buộc bất đẳng thức: phương pháp cổ điển

Trường Đại học Công nghiệp thành phố Hồ Chí Minh 
Khoa Công nghệ Cơ khí 
CHƯƠNG 05: 
TỐI ƯU HÀM NHIỀU BIẾN SỐ 
 VỚI RÀNG BUỘC BẤT ĐẲNG THỨC: 
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 bất 
đẳng thức 
 f xTìm cực trị (Optimum) của hàm nhiều biến sau: 
Với các điều kiện ràng buộc bất đẳng thức: 
Với:  1 2
T
nx x x x
 0
1,2, ,
jg
j m
x
3 
 20 0
1,2, , 1, 2, ,
j j j
g g y
j m j m
x x
 2, 0
1,2, ,
j j jG g y
j m
x y x
   
 
1
1 2 1 2
1 2
, , ,
; ;
m
j j
j
T T
n m
T
m
L f G
x x x y y y

  
x y λ x x y
x y
λ
4 
Giải hệ (n+2m) phương trình sau: 
1
2
, , ; 1.. 1
, , 2 0; 1.. 2
, , , 0; 1.. 3
m
j
j
ji i i
j j
j
j j j
j
gL f
i n
x x x
L
y j m
y
L
G g y j m



  
   
  
 
 
 
x y λ x x
x y λ
x y λ x y x
1 1 1
2 2 2; ;
n m m
x y
x y
x y



x λ y
5 
Tính định thức sau. Tìm nghiệm của phương trình định thức = 0. Nếu tất cả các 
nghiệm đều mang dấu – hoặc 1 số = 0 thì lời giải là cực đại, nếu tất cả nghiệm 
mang dấu + hoặc 1 số = 0 thì lời giải là cực tiểu. Nếu 1 vài nghiệm mang dấu –, một 
số còn lại mang dấu + thì đó không phải là cực trị. 
11 12 13 11 21 11
21 22 23 12 22 22
1 2 3 1 2
11 12 13 1
21 22 23 2
1 2 3
0 0 0
0 0 0
0 0 0
mn m
mn m
n m n m n m n m n m n m n m m n m
n m
n m
m m m m n m
L z L L L G G G
L L z L L G G G
L L L L z G G G
G G G G
G G G G
G G G G
m n+m 
m m 
n+m n+m 
n+m m 
Ma trận Hessian 
6 Biến đổi: 
11 12 13 1 11 21 1
21 22 23 2 12 22 2
1 2 3 1 2
1 1
2 2
11 12 13 1 1
21 22 23 2 2
0 0 0
0 0 0
0 0 0
0 0 0 0 2 0 0 2 0 0
0 0 0 0 0 2 0 0 2 0
0 0 0 0 0 0 2 0 0 2
2 0 0 0 0 0
0 2
n m
n m
n n n nn n n mn
m m
n
n
L z L L L g g g
L L z L L g g g
L L L L z g g g
z y
z y
z y
g g g g y
g g g g y



1 2 3
0 0 0 0
0 0 2 0 0 0m m m mn mg g g g y
m m 
m m 
n n 
n 
n 
m m 
m m 
2
, ,
, ,
1.. ; 1.., 1..
k
ij kl
i j l
L g
L g
x x x
k m l ni j n
 
  
x y λ x
x y λ x
 Định thức này là 1 hàm đa 
thức bậc n có tối đa n nghiệm 
7 
Cực tiểu hàm số sau: 2 2 21 2 3 1 2 3 1 2, , 40 20 minf x x x x x x x x 
Với các ràng buộc: 1 1 2 1 2 350; 100; 150x x x x x x 
3
3
n
m
Biến đổi lại các 
ràng buộc: 
1 1 2 3 1
2 1 2 3 1 2
3 1 2 3 1 2 3
2
1 1 2 3 1 1 1
2
2 1 2 3 2 1 2 2
2
3 1 2 3 3 1 2 3 3
, , 50 0
, , 100 0
, , 150 0
, , , 50 0
, , , 100 0
, , , 150 0
g x x x x
g x x x x x
g x x x x x x
G x x x y x y
G x x x y x x y
G x x x y x x x y
 Hàm Lagrange: 
3
1 2 3 1 2 3
1
, , , , , , ,j j j
j
L f x x x G x x x y
 x y λ
8 
2 2 2 2
1 2 3 1 2 1 1 1
2 2
2 1 2 2 3 1 2 3 3
, , 40 20 50
100 150
L x x x x x x y
x x y x x x y

 
x y λ
Hệ PT (1)÷(3) tương đương 9 phương trình: 
1 1 2 3
2 2 3
3 3
1 1
2 2
3 3
2
1 1
2
1 2 2
2
1 2 3 3
2 40 0
1 2 20 0 4
2 0
2 0
2 2 0 5
2 0
50 0
3 100 0 6
150 0
x
x
x
y
y
y
x y
x x y
x x x y
  
 




Giải hệ 
PT tìm 
9 ẩn 
9 Hệ PT (5) sẽ tương đương với 8 tình huống. Mỗi tình huống sẽ 
kết hợp với hệ phương trình (4) và (6). Ta sẽ được 8 hệ 
phương trình như sau: 
1) Hệ PT 1: 
1
2
3
1 1 2 3
2 2 3
3 3
2
1 1
2
1 2 2
2
1 2 3 3
0
0
0
2 40 0
2 20 0
2 0
50 0
100 0
150 0
x
x
x
x y
x x y
x x x y



  
 

Vô 
nghiệm 
10 
2) Hệ PT 2: 
1
2
3
1 1 2 3
2 2 3
3 3
2
1 1
2
1 2 2
2
1 2 3 3
0
0
0
2 40 0
2 20 0
2 0
50 0
100 0
150 0
y
x
x
x
x y
x x y
x x x y


  
 

Vô 
nghiệm 
11 
3) Hệ PT 3: 
1
2
3
1 1 2 3
2 2 3
3 3
2
1 1
2
1 2 2
2
1 2 3 3
0
0
0
2 40 0
2 20 0
2 0
50 0
100 0
150 0
y
x
x
x
x y
x x y
x x x y


  
 

Vô 
nghiệm 
12 
4) Hệ PT 4: 
1
2
3
1 1 2 3
2 2 3
3 3
2
1 1
2
1 2 2
2
1 2 3 3
0
0
0
2 40 0
2 20 0
2 0
50 0
100 0
150 0
y
y
x
x
x
x y
x x y
x x x y

  
 

Vô 
nghiệm 
13 
5) Hệ PT 5: 
1
2
3
1 1 2 3
2 2 3
3 3
2
1 1
2
1 2 2
2
1 2 3 3
0
0
0
2 40 0
2 20 0
2 0
50 0
100 0
150 0
y
x
x
x
x y
x x y
x x x y


  
 

Vô 
nghiệm 
14 
6) Hệ PT 6: 
1
2
3
1 1 2 3
2 2 3
3 3
2
1 1
2
1 2 2
2
1 2 3 3
0
0
0
2 40 0
2 20 0
2 0
50 0
100 0
150 0
y
y
x
x
x
x y
x x y
x x x y

  
 

Vô 
nghiệm 
15 
7) Hệ PT 7: 
1
2
3
1 1 2 3
2 2 3
3 3
2
1 1
2
1 2 2
2
1 2 3 3
0
0
0
2 40 0
2 20 0
2 0
50 0
100 0
150 0
y
y
x
x
x
x y
x x y
x x x y

  
 

Vô 
nghiệm 
16 
8) Hệ PT 8: 
1
2
3
1 1 2 3
2 2 3
3 3
2
1 1
2
1 2 2
2
1 2 3
1
1
2
2
1
2
3
3
33
0
0
0
2 40 0
2 20 0
2 0
50 0
100 0
150
20
20
1
50
50
50
00
0
0
0
0
y
y
y
y
y
x
x
x
x y
x x
x
x
x
y
x x x
y
y
 






Đây là điểm 
dừng, cần 
kiểm tra điều 
kiện đủ để 
biết về cực 
trị 
17 Tính ma trận Δ như slide 6: 
2
11 2
1
2
22 2
2
2
33 2
3
2
2
2
L
L
x
L
L
x
L
L
x






2 2 2 2
1 2 3 1 2 1 1 1
2 2
2 1 2 2 3 1 2 3 3
1 1 2 3 1
2 1 2 3 1 2
3 1 2 3 1 2 3
, , 40 20 50
100 150
, , 50
, , 100
, , 150
L x x x x x x y
x x y x x x y
g x x x x
g x x x x x
g x x x x x x

 
x y λ
2
12
1 2
2
13
1 3
2
21
2 1
0
0
0
L
L
x x
L
L
x x
L
L
x x

 

 

 
2
23
2 3
2
31
3 1
2
32
3 2
0
0
0
L
L
x x
L
L
x x
L
L
x x

 

 

 
1
11
1
1
12
2
1
13
3
1
0
0
g
g
x
g
g
x
g
g
x






18 
2
21
1
2
22
2
2
23
3
1
1
0
g
g
x
g
g
x
g
g
x






3
31
1
3
32
2
3
33
3
1
1
1
g
g
x
g
g
x
g
g
x






2 0 0 0 0 0 1 1 1
0 2 0 0 0 0 0 1 1
0 0 2 0 0 0 0 0 1
0 0 0 40 0 0 0 0 0
0 0 0 0 40 0 0 0 0
0 0 0 0 0 200 0 0 0
1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
z
z
z
z
z
z
1
2
3
1
2
3
50
50
50
20
20
100
x
x
x



x
λ
1
2
3
0
0
0
y
y
y
y
Tính 
định 
thức 
của 
ma 
trận 
này 
19 Tính định thức của ma trận Δ 
2
40 0
det 40 200 0 40 0
200 0
z z
Z Cực tiểu tại 
ràng buộc 
Kết luận: Cực tiểu của hàm f = 10500 với x1*=50, x2*=50, x3*= 50 
20 
- Phương trình (3) để đảm bảo các điều kiện gj(x) ≤ 0 
được thỏa mãn 
- Phương trình (2) cho ra kết quả hoặc là λj = 0, hoặc là 
yj = 0 
- Nếu λj = 0 thì có nghĩa là ràng buộc thứ j không cần 
dùng tới và nó có thể được bỏ qua 
- Nếu yj = 0 thì có nghĩa là ràng buộc gj(x)=0 hoạt động 
tại ngay điểm cực trị 
 Ta có thể chia các ràng buộc ra 2 tập hợp con: 
 Tập hợp j ϵ J1 khi yj = 0 (ràng buộc hoạt động ngay 
điểm cực trị, λj ≠ 0 ) 
 Tập hợp j ϵ J2 khi λj = 0 (ràng buộc được bỏ qua) 
21 
1
1
1
2
2
1 0; 1.. 4
0; 5
2
0; 6
p
j
j
ji i
j J
j
j j
gf
i n
x x
g j J
g y j J


 
x x
x
x
Hệ phương trình (4)÷(6) thể hiện n+p+(m-p) = n+m phương 
trình với n+m ẩn số: xi (i=1..n), λj (jϵJ1 hay j=1..p), yj (jϵJ2 hay 
j=(p+1)..(m-p)). Với p – số ràng buộc làm việc. 
Giả sử p ràng buộc đầu tiên làm việc, phương trình (4): 
1 2
1 2
1 1 2 2
; 1..
7
p
p
i i i i
p p
gg gf
i n
x x x x
f g g g
  
  
 
   
    
x x x x
22 
Trong đó: 
11
2 2
; 1..
i
i
j
n i n
g xf x
f x g x
f g j p
f x g x
   
      
    
Phương trình (7) có ý nghĩa rằng: giá trị đối của độ dốc của hàm 
mục tiêu f có liên hệ tuyến tính với độ dốc của các ràng buộc 
làm việc tại điểm cực trị. 
23 
Hướng khả thi (Feasible Direction) 
Véctơ S được gọi là hướng khả thi từ điểm x nếu có thể tiến một 
bước nhỏ dọc theo S mà không rời khỏi ngay lập tức khỏi vùng 
hợp lệ. Với các bài toán có các bề mặt ràng buộc đủ mịn ta có 
điều kiện sau: 
0; 1..T jg j p S
Hàm ràng 
buộc lồi 
Góc > 90° 
Hàm ràng buộc 
tuyến tính 
Góc = 90° 
Góc > 90° 
Hàm ràng 
buộc lõm 
Hàm 
lõm 
Góc > 90° 
Tích vô hướng < 0 thì góc giữa 2 véc tơ là góc tù 
24 
Gọi S là hướng khả thi tại điểm cực trị. Nhân cả 2 vế của (7’) cho 
ST, Ta có: 1 1 2 2 8
T T Tf g g    S S S
Xét trường hợp chỉ có 2 ràng buộc làm việc p = 2 
 1 1 2 27 7f g g    
Do S là hướng khả thi nên nó phải thỏa mãn các điều kiện: 
1
2
0
0
T
T
g
g
  
 
S
S
Nếu 0T f S Giá trị hàm f tăng khi di chuyển dọc theo hướng S 
Nếu 0T f S Giá trị hàm f giảm khi di chuyển dọc theo hướng S 
Tìm cực tiểu (min) λj ≥ 0 (j=1..p) 
Tìm cực đại (max) λj ≤ 0 (j=1..p) 
Ý nghĩa của điều này giúp chúng ta tìm thẳng cực tiểu hay 
cực đại bằng cách chọn thông qua dấu của các λj 
25 
Điều kiện Karush-Kuhn-Tucker 
1
, 0; 1.. 8
0; 1.. 9
0; 1.
0; 1..
. 10
11j
m
j
j
ji i i
j j
j
gL f
i n
x x x
g j m
g j m
j m



  
   
x λ x x
1
, 0; 1.. 8
0; 1.. 9
0; 1.
0; 1..
. 10
12j
m
j
j
ji i i
j j
j
gL f
i n
x x x
g j m
g j m
j m



  
   
x λ x x
26 
Điều kiện Karush-Kuhn-Tucker 
1. Luôn xuất phát từ hệ phương trình (9). Sẽ 
có 2m trường hợp con, tương ứng 2m hệ 
phương trình 9’. Ví dụ, ta sẽ có hệ phương 
trình 9.1, 9.2, , 9.2m. Mỗi hệ phương 
trình sẽ có m phương trình. 
2. Với mỗi hệ phương trình 9.i (i=1.. 2m), ta 
ghép với các hệ phương & bất phương 
trình (8), (10) và (11) khi tìm cực tiểu / (12) 
khi tìm cực đại, để tìm toàn bộ các nghiệm 
x* và λ* thỏa mãn 
27 
Điều kiện Karush-Kuhn-Tucker 
Cực tiểu hàm số sau: 2 2 21 2 3 1 2 3 1 2, , 40 20 minf x x x x x x x x 
Với các ràng buộc: 1 1 2 1 2 350; 100; 150x x x x x x 
3
3
n
m
Biến đổi lại các 
ràng buộc: 
1 1 2 3 1
2 1 2 3 1 2
3 1 2 3 1 2 3
, , 50 0
, , 100 0
, , 150 0
g x x x x
g x x x x x
g x x x x x x
Hàm Lagrange: 
3
1 2 3 1 2 3
1
2 2 2
1 2 3 1 2 1 1
2 1 2 3 1 2 3
, , , , ,
40 20 50
100 150
j j
j
L f x x x g x x x
x x x x x x
x x x x x


 
x λ
28 
Điều kiện Karush-Kuhn-Tucker 
1 1 2 3
1
2 2 3
2
3 3
3
1 1
2 1 2
3 1 2 3
, 2 40 0
8 , 2 20 0
, 2 0
50 0
9 100 0
150 0
L
x
x
L
x
x
L
x
x
x
x x
x x x
  
 




 
 
 
 
 
 
x λ
x λ
x λ
1
1 2
1 2 3
1
2
3
50 0
10 100 0
150 0
0
11 0
0
x
x x
x x x



Hệ số (9) sẽ tương đương với 23=8 trường hợp con như sau: 
29 1) Trường hợp 1: 
1
2
3
1 1 2 3
2 2 3
3 3
1
1 2
1 2 3
1
2
3
0
0
0
2 40 0
2 20 0
2 0
50 0
100 0
150 0
0
0
0
x
x
x
x
x x
x x x



  
 




Vô nghiệm 
30 2) Trường hợp 2: 
1
2
3 1 2 3
1 1 2 3
2 2 3
3 3
1
1 2
1 2 3
1
2
3
0
0
150 0
2 40 0
2 20 0
2 0
50 0
100 0
150 0
0
0
0
g x x x
x
x
x
x
x x
x x x


  
 




Vô nghiệm 
31 3) Trường hợp 3: 
1
2 1 2
3
1 1 2 3
2 2 3
3 3
1
1 2
1 2 3
1
2
3
0
100 0
0
2 40 0
2 20 0
2 0
50 0
100 0
150 0
0
0
0
g x x
x
x
x
x
x x
x x x


  
 




Vô nghiệm 
32 4) Trường hợp 4: 
1
2 1 2
3 1 2 3
1 1 2 3
2 2 3
3 3
1
1 2
1 2 3
1
2
3
0
100 0
150 0
2 40 0
2 20 0
2 0
50 0
100 0
150 0
0
0
0
g x x
g x x x
x
x
x
x
x x
x x x

  
 




Vô nghiệm 
33 5) Trường hợp 5: 
1 1
2
3
1 1 2 3
2 2 3
3 3
1
1 2
1 2 3
1
2
3
50 0
0
0
2 40 0
2 20 0
2 0
50 0
100 0
150 0
0
0
0
g x
x
x
x
x
x x
x x x


  
 




Vô nghiệm 
34 6) Trường hợp 6: 
1 1
2
3 1 2 3
1 1 2 3
2 2 3
3 3
1
1 2
1 2 3
1
2
3
50 0
0
150 0
2 40 0
2 20 0
2 0
50 0
100 0
150 0
0
0
0
g x
g x x x
x
x
x
x
x x
x x x

  
 




Vô nghiệm 
35 7) Trường hợp 7: 
1 1
2 1 2
3
1 1 2 3
2 2 3
3 3
1
1 2
1 2 3
1
2
3
50 0
100 0
0
2 40 0
2 20 0
2 0
50 0
100 0
150 0
0
0
0
g x
g x x
x
x
x
x
x x
x x x

  
 




Vô nghiệm 
36 8) Trường hợp 8: 
1 1
2 1 2
3 1 2 3
1 1 2 3
2 2 3
3 3
1
1
1
2
2
1 2 3
1
2
3
1
2
3
3
50 0
100 0
150 0
2 40 0
2 20 0
2 0
50 0
10
50
50
5
0 0
15
0
0
20
0
0
0
0
20
100
g x
g x x
g x x x
x
x
x
x
x x
x x x
x
x
x
  
 






 
Đây là điểm 
cực tiểu. 
Không cần 
kiểm tra lại 
điều kiện đủ 
(Định thức Δ) 
 fmin = 10500