Tuyển tập Hội nghị Khoa học thường niên năm 2019. ISBN: 978-604-82-2981-8
570
PHƯƠNG PHÁP CHUYỂN ĐỔI GIẢI BÀI TOÁN TỐI ƯU
BIẾN NGUYÊN KHÔNG LỒI
Phạm Đức Đại1, Nguyễn Thị Thúy Hằng1
1Trường Đại học Thủy lợi, email: daipd@tlu.edu.vn
1. GIỚI THIỆU
Bài toán tối ưu biến nguyên (MINLP)
được ứng dụng rộng rãi để giải các bài toán
tối ưu hoạt động trong thực tế, như bài toán
tối ưu hoạt động đóng mở bơm; bài toán tối
ưu hộp số; bài toán tối ưu đặt van trong mạng
cấp nước. Các bài toán tối ưu MINLP thường
phi tuyến và không lồi (Non-convex) dẫn đến
nghiệm của bài toán này thường là cục bộ và
có chất lượng thấp. Các phương pháp giải bài
toán tối ưu MINLP có thể sử dụng phương
pháp Branch and Bound [1], phương áp OA
(outer approximation) [1], phương pháp phân
tích Benders (GBD). Các phương pháp trên
cho nghiệm tin cậy (reliable) khi mà bài toán
MINLP là lồi. Tuy nhiên, hầu hết các bài
toán kỹ thuật là phi tuyến không lồi, việc tìm
được nghiệm thỏa mãn các rằng buộc của bài
toán MINLP cũng là một bài toán khó. Rất
nhiều phương pháp đã quan tâm đến việc
chuyển bài toán không lồi MINLP thành bài
toán lồi. Trong bài báo này tác giả quan tâm
đến dạng bài toán có các thành phần mũ
không lồi, có dạng như sau:

 
min
..
0
0
n
mm
fz
st
g
q

Az a
Bz b
z
zz
Trong đó
f
, n
g
, m
q là các hàm phi tuyến
lồi, có đạo hàm;

m
z là các hàm mũ
(signomial functions) phi tuyến không lồi
(non-convex). Mục tiêu của bài báo này là áp
dụng các phương pháp chuyển đổi nhằm
chuyển các thành phần mũ không lồi thành
các thành phần lồi kết hợp với phương pháp
xấp xỉ từng đoạn (piece-wise linearization).
2. PHƯƠNG PHÁP CHUYỂN ĐỔI
Hàm mũ được định nghĩa như sau:

11
j
i
I
Jp
mji
ji
cz
z
Với hàm dương 0
j
c, hàm mũ lồi khi và
chỉ khi:
(i) 0, 1,...,
i
p
iI

(ii)
#
:1,0,1,...,,#
ii i
ik
kp p p i Iik
Với hàm âm (cj < 0) thì hàm mũ là lồi khi
và chỉ khi:

1
1
; 0; 0, 1,...,
1
i
I
p
mii
i
n
i
i
czc p i I
p

z
2.1. Phương pháp chuyển đổi cho hàm
mũ âm
Hàm mũ không lồi có thể được chuyển
thành hàm mũ lối với phương pháp chuyển
đổi như sau:
i
Q
ii
zZ hay 1/ i
Q
ii
Z
z. Chú ý rằng:
Khi 0
i
p thì 0
i
Q; 0
i
p
thì 0
i
Q và 0
i
p
thì 0
i
Q
. Hơn nữa để thành phần sau khi
chuyển đổi là lồi thì ta cần điều kiện:
1
1
I
ii
i
pQ
Thành phần mới sẽ là:

1
ii
I
pQ
mi
i
cZ
z
Điều kiện để hàm mới là lồi như sau:
1
01, 0 1
0, 0
I
ii
ii
i
ii
Qp pQ
Qp


Tuyển tập Hội nghị Khoa học thường niên năm 2019. ISBN: 978-604-82-2981-8
571
2.2. Phương pháp chuyển đổi cho hàm
mũ dương

1
ii
I
pQ
mi
i
cZ
z
1, 0
0, 0 #
1, 0
ii
ii
ii
Qpik
Qpik
Qp



2.3. Tuyến tính hóa từng đoạn
Việc thực hiện chuyển đổi 1/ i
Q
ii
Z
z sẽ được
tuyến tính hóa, để bài toán MINLP trở thành
bài toán phi tuyến lồi. Trong bài báo này, tác
giả ứng dụng phương pháp tuyến tính hóa
từng đoạn (piecewise linear functions) để xấp
xỉ i
Z
bởi
Z
như sau:
1
M
mm
m
Z
Zw
với 0
m
w
Và do đó:
1
M
mm
m
zzw
và
1
1
M
m
m
w
2.4. Thuật giải bài toán không lồi MINLP
Bước 1. Chuyển đổi bài toán MINLP
không lồi về bài toán lồi; số điểm tuyến tính
hóa 2
TTH
N; MINLP
Obj
Bước 2: Tuyến tính hóa sử dụng số điểm
TTH
N.
Bước 3: Giải bài toán MINLP lồi được
hàm mục tiêu
k
MINLP
Obj .
Nếu
1kk
M
INLP MINLP
Obj Obj
đến bước 4, ngược
lại dừng và kết thúc.
Bước 4: Tăng số điểm tuyến tính hóa
1
TTH TTH
NN quay lại bước 1
3. ỨNG DỤNG PHƯƠNG PHÁP CHUYỂN
ĐỔI GIẢI BÀI TOÁN TỐI ƯU

2 0.5 0.5 2 1.5 1.5
min 3
..
536
0.25 1
2 2 11 8 20 2 0.1 0
17,17
yx
st
yx
yx
yy yx xy xy
xy




Dựa vào các định lý đã nêu trên, có thể
thấy rằng, bài toán có các thành phần phi
tuyến không lồi sau:
0.5 2
2
x
y và 1.5 1.5
0.1
x
y
Thực hiện chuyển đổi:
0.25
1
yY
1
3
2
yY
; các thành phần không lồi sẽ
trở thành:
2 0.5 0.5 0.5 1.5 0.5
12
2 2 11 8 20 2 0.1 0yy yx xY xY

Theo định nghĩa ở trên, 0.5 0.5
1
2
x
Y có tổng
các mũ
1
1
n
i
i
p
, do đó đây là hàm lồi; tương
tự như vậy thành phần 1.5 0.5
2
0.1
x
Y thỏa mãn
điều kiện
#
:1,0,1,...,,#
ii i
ik
kp p p i Iik
Bài toán trên còn cần hai điều kiện nữa để
tuyến tính hóa các thành phần sau:
4
1
Yy
và 3
2
Yy
4
112
1(7)Yw w và 3
212
1(7)Yw w
 và
12
17yw w
;12
1ww
. Bài toán tối ưu không lồi
giờ trở thành bài toán lồi như sau:

0.5 0.5
2 0.5 0.5 1.5
12
4
112
3
212
12
12
12
min 3
..
536
0.25 1
2 2 11 8 20 2 0.1 0
1(7)
1(7)
17
1
17,17
0,0
yx
st
yx
yx
yy yx xY xY
Yw w
Yw w
yw w
ww
xy
ww









Tác giả sử dụng phần mền GAMs để giải
bài toán trên ta được nghiệm là 6.6, 3xy.
Tiếp đến ta thêm số điểm tuyến tính hóa từ 2
lên 3, điểm mới là 3y
. Bài toán tối ưu mới
sẽ trở thành:



0.5 0.5
2 0.5 0.5 1.5
12
4
4
112 3
3
3
212 3
123
123
123
min 3
..
536
0.25 1
2 2 11 8 20 2 0.1 0
1(7) 3
1(7) 3
17 3
1
17,17
0,0 ,0
yx
st
yx
yx
yy yx xY xY
Yw w w
Yw w w
yw w w
www
xy
www









Tuyển tập Hội nghị Khoa học thường niên năm 2019. ISBN: 978-604-82-2981-8
572
Sau khi giải bài toán này, thu được nghiệm
như sau 6.2, 5xy. Tiếp tục, bài toán được
thêm số điểm tuyến tính hóa:

 
 
0.5 0.5
2 0.5 0.5 1.5
12
44
4
112 3 4
33
3
212 3 4
1234
1234
1234
min 3
..
536
0.25 1
2 2 11 8 20 2 0.1 0
1(7) 3 5
1(7) 3 5
17 35
1
17,17
0,0 ,0,0
yx
st
yx
yx
yy yx xY xY
Yw w w w
Yw w w w
yw w w w
wwww
xy
wwww










Giải bài toán, thu được kết quả là
6, 6xy
, với giá trị của hàm mục tiêu là -12,
đây là giá trị tối ưu toàn cục.
4. KẾT LUẬN
Nhóm tác giả đã ứng dụng phương pháp
chuyển đổi nhằm chuyển đổi bài toán MINLP
không lồi thành bài toán MINLP lồi. Phương
pháp tuyến tính hóa liên tục được sử dụng
nhằm làm giảm khối lượng tính toán cho bài
toán MINLP.
5. TÀI LIỆU THAM KHẢO
[1] Some transformation techniques with
applications in global optimization.