Ứng dụng thuật toán nhánh cận giải bài toán quy hoạch tích Affine với các ràng buộc tuyến tính

Trần Đình Hùng Tạp chí KHOA HỌC & CÔNG NGHỆ 63(1): 28 - 30

28

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn

ỨNG DỤNG THUẬT TOÁN NHÁNH CẬN GIẢI BÀI TOÁN

QUY HOẠCH TÍCH AFFINE VỚI CÁC RÀNG BUỘC TUYẾN TÍNH

Trần Đình Hùng

Trường Đại học Sư phạm - ĐH Thái Nguyên

TÓM TẮT

Quy hoạch tích affine là một trong những bài toán quan trọng của tối ưu toàn cục. Một phương

pháp khá hữu hiệu để giải bài toán này là phương pháp nhánh cận, ở đó bài toán gốc được chia

thành các bài toán nhỏ dễ giải hơn.

Trong [4] Lê Dũng Mưu và Bùi Thế Tâm đã phát biểu và đưa ra phương pháp giải bài toán quy

hoạch tích hai hàm phân thức affine với các ràng buộc tuyến tính:

1 1 2 2

1 1 2 2

min{ ( ) } a x b a x b f x x D

c x d c x d

 

 

 

.

Bài toán quy hoạch tích hai hàm affine là một trường hợp riêng của bài toán này, trong đó khó

khăn nằm ở chỗ, nghiệm tối ưu địa phương không nhất thiết là nghiệm tối ưu toàn cục. Để giải bài

toán, ta chuyển về một dạng quy hoạch lồi-lõm và áp dụng thuật toán nhánh cận trong [2], đặc

điểm quan trọng của thuật toán này là có sử dụng các thông tin của các bước lặp trước, không cần

vét kiệt, nhưng vẫn bảo đảm sự hội tụ.

Mục đích của bài báo này là nghiên cứu thuật toán nhánh cận để giải bài toán quy hoạch tích hai

hàm affine với các ràng buộc tuyến tính, từ đó mở rộng cho trường hợp tích nhiều hàm affine.

Từ khoá: Thuật toán nhánh cận, tối ưu toàn cục, quy hoạch lồi-lõm, quy hoạch tích hai hàm phân

thức affine.

*BÀI TOÁN QUY HOẠCH TÍCH HAI HÀM

AFFINE VỚI CÁC RÀNG BUỘC TUYẾN

TÍNH

Xét bài toán

( ) P

:

min{ ( ) ( ) ( ): }, 1 2 f x f x f x x D  

trong đó

D

là một đa diện xác định bởi

{ : , 0}, ( ) ( 1,2) n D x Ax b x f x i      i

là các hàm affine trên

n

, ( ) T

i i i f x c x b   .

Để giải bài toán này, ta chuyển về một

quy hoạch lồi-lõm như sau:

Đặt

2

y f x  ( )

, khi đó bài toán được đưa

về dạng

min{ ( , ) ( ) : , (x)=y} 1 2 f x y f x y x D f  

(Q)

Đây là bài toán quy hoạch lồi-lõm do

hàm

f x y ( , )

là hàm lồi-lõm trên tập lồi

D

*

Tel: 0912347199

(

f x y ( , )

được gọi là hàm lồi-lõm nếu nó lồi theo

x

khi cố định

y

và lõm theo

y

khi cố định

x

).

KẾT QUẢ CHÍNH

Thuật toán nhánh cận

Áp dụng thuật toán nhánh cận tổng quát trong [5]

và đối với trường hợp bài toán quy hoạch lồi-lõm

trong [2], [3], ý tưởng là chia nhỏ miền ràng buộc

lõm y của bài toán (chia nhánh), trong quá trình đó

tính cận trên và cận dưới của

f x y ( , )

trên các

miền ràng buộc lõm (tính cận), từ đó thu hẹp dần

khoảng chứa nghiệm của bài toán.

Nhận xét

( ) ( 1,2) i

f x i 

là các hàm affine, với miền ràng

buộc

D

gồm các ràng buộc tuyến tính, do đó việc

tính cực tiểu hay cực đại của chúng thực chất là

bài toán quy hoạch tuyến tính đã quen thuộc.

Đặt

0 2 min ( )

x D

z f x



 ,

0 2 max ( )

x D

Z f x





, khi đó

miền ràng buộc của biến lõm y chỉ là một đoạn