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


Tối ưu hàm nhiều biến với ràng buộc bất
đẳng thức
Tì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:

f x

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

Với:

x   x1

x2

xn 

T



y2

m 

T

ym  ;
T


4

Giải hệ (n+2m) phương trình sau:
m
 L
g j
f
  x, y , λ  
 x     j  x  ; i  1..n
xi
xi
j 1
 xi
 L
j  1..m
 x, y, λ   2 j y j  0;

 y j
 L

x 
;λ 
;y 
 
 
 
 
 
 
 xn 
m 
 ym 

1
 2
 3


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ị.

Ma trận Hessian
m

n+m



Gm 2

L n  m 1

L n  m 2

L n  m 3

G2 n  m 

Gm n  m 

G11

G12

G13

G1 n  m 

0

0

0

G21

G22


n+m

m


6

Biến đổi:
n

n

m 

m

m

m

L11  z

L12

L13

L1n

0


Ln1

Ln 2

Ln 3

Lnn  z

0

0

0

g1n

g2n

g mn

0

0

0

0

21  z


0

0

0

0

0

0

2m  z

0

0

2 ym

g11

g12

g13

g1n

2 y1


g m1

gm2

g m3

g mn

0

0

2 ym

0

0

0

m

n
 2 L  x, y , λ 
Lij 
xi x j
i, j  1..n

 x ,y ,λ 

x
,
x

x

x

x
Cực tiểu hàm số sau:  1 2 3  1
2
3  40 x1  20 x2  min
Với các ràng buộc: x1  50; x1  x2  100; x1  x2  x3  150 n  3
m  3

Biến đổi lại các
ràng buộc:

Hàm Lagrange:

 g1  x1 , x2 , x3    x1  50  0

 g 2  x1 , x2 , x3    x1  x2  100  0

 g3  x1 , x2 , x3    x1  x2  x3  150  0
G1  x1 , x2 , x3 , y1    x1  50  y12  0

 G2  x1 , x2 , x3 , y2    x1  x2  100  y22  0

2

j 1


L  x, y , λ    x  x  x  40 x1  20 x2   1   x1  50  y
2
1

2
2

2
3

2
1



2   x1  x2  100  y22   3   x1  x2  x3  150  y32 
Hệ PT (1)÷(3) tương đương 9 phương trình:
2 x1  40  1  2  3  0

1  2 x2  20  2  3  0
 4
2 x    0
 3 3

21 y1  0

 2   22 y2  0



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:

  0
 1
2  0
  0
 3
2 x1  40  1  2  3  0

2 x2  20  2  3  0
2 x    0
 3 3
 x1  50  y12  0

2

x

x

100

y
 1 2
2 0

2 x1  40  1  2  3  0

2 x2  20  2  3  0
2 x    0
 3 3
 x1  50  y12  0

2

x

x

100

y
 1 2
2 0

2

x

x

x

150

y


y
 1 2
2 0

2

x

x

x

150

y
3 0
 1 2 3

Vô
nghiệm


12

4) Hệ PT 4:

  0
 1
 y2  0


y
3 0
 1 2 3

Vô
nghiệm


13

5) Hệ PT 5:

y  0
 1
2  0
  0
 3
2 x1  40  1  2  3  0

2 x2  20  2  3  0
2 x    0
 3 3
 x1  50  y12  0

2

x

x

 1
2  0
y  0
 3
2 x1  40  1  2  3  0

2 x2  20  2  3  0
2 x    0
 3 3
 x1  50  y12  0

2

x

x

100

y
 1 2
2 0

2

x

x

x


x

100

y
 1 2
2 0

2

x

x

x

150

y
3 0
 1 2 3

Vô
nghiệm


16

8) Hệ PT 8:


x

x

100

y

0
x
 1 2
 2  50
2

 
2
 x1  x2  x3  150  y3  0
 x3  50

Đây là điểm
dừng, cần
kiểm tra điều
kiện đủ để
biết về cực
trị


Tính ma trận Δ như slide 6:


x1x3
x2
x3x1

g1
g12 
0
x2

2 L
2 L
2 L
L33  2  2 L21 
 0 L32 
0
x3
x2 x1
x3x2

g1
g13 
0
x3


g3
g 2
 1
g 21 
 1 g31 

y   y2    0 
1   20 
 y3  0 
 
   

λ  2    20 
3  100 
 

0
0
0
0
0
1 1 1
2  z
 0

2

z
0
0
0
0
0

1


0
0 0 0


0
0
0
0
0
200

z
0
0
0


 1
0
0
0
0
0
0 0 0


1
0
0
0

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

f
1   x  
xi

g j

p

Giả sử p ràng buộc đầu tiên làm việc, phương trình (4):
g1
g 2
f

x


x


  1   2 x 
xi
xi
xi
 f  1g1  2g 2 

 p

g p
xi

  p g p

x;

i  1..n

7


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ị.


Hướng khả thi (Feasible Direction)

23

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:
T

S g j  0;

Hàm ràng
buộc lồi

j  1.. p

Hàm ràng buộc
tuyến tính

Góc = 90°

Hàm ràng
buộc lõm

Hàm

Nếu ST f  0 Giá trị hàm f tăng khi di chuyển dọc theo hướng S
Nếu ST f  0 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
m
g j
 L
f
 x     j  x   0; i  1..n
  x, λ  
xi
xi
j 1
 xi
 g  0;
j  1..m
 j j
 g  0;
j  1..m
j

 j  0;

10 
12 