Về một lược đồ đối ngẫu trong tối ưu dạng phân thức tuyến tính

TAÏP CHÍ KHOA HOÏC ÑAÏI HOÏC SAØI GOØN Soá 23 (48) - Thaùng 12/2016 
155 
Về một lược đồ đối ngẫu trong tối ưu 
dạng phân thức tuyến tính 
A note on duality in linear fractional programming 
ThS. Huỳnh Khoa 
Trường THPT Nguyễn Thị Diệu 
Huynh Khoa, M.Sc. 
Nguyen Thi Dieu High School 
Tóm tắt 
Trong bài báo này, chúng tôi quan tâm đến một lược đồ đối ngẫu của bài toán tối ưu dạng phân thức 
tuyến tính do Seshan [12] đề xuất. Điểm đặc biệt của lược đồ đối ngẫu này là bài toán gốc và bài toán 
đối ngẫu có cùng hàm mục tiêu. Mặc dù lược đồ này đã thu hút sự quan tâm và được khảo cứu lại trong 
các tài liệu, nhưng các bước để dẫn đến sự hình thành lược đồ dường như chưa được làm rõ. Mục đích 
của bài báo này là chỉ rõ rằng, lược đồ đối ngẫu ấy có thể nhận được từ các phép biến đổi Charnes-
Cooper và phép biến đổi của Dinkelbach. Ví dụ minh họa được giới thiệu. 
Từ khóa: đối ngẫu Seshan, phương pháp Charnes - Cooper, phương pháp Dinkelbach. 
Abstract 
We are interested in the duality scheme of a linear fractional programming problem proposed by 
Seshan. The specification of the duality scheme is that the dual problem and the primal problem have 
the same objective functions. Despite having academic attentions and having been studied in literature, 
the motivation for the scheme is not clear. The aim of this paper is to show that the duality scheme can 
be obtained based on the Charnes-Cooper and Dinkelbach transformations. An example is given. 
Keywords: Seshan’s duality, Charnes – Cooper method, Dinkelbach method. 
1. Phần giới thiệu 
Bài toán tối ưu dạng phân thức tuyến 
tính được nhiều nhà toán học quan tâm từ 
rất sớm [14], [8], [7], [5]. Như là một sự 
mở rộng tự nhiên của bài toán tối ưu dạng 
tuyến tính, người ta quan tâm dạng bài toán 
tối ưu phân thức tuyến tính sau đây 
(P)Max 0
0
( )
T
T
c x c
F x
d x d
 (1.1) 
 Đ.k. ,Ax b (1.2) 
 0,x (1.3) 
trong đó 
1
2
n
c
c
c
c
 , 
1
2
n
d
d
d
d
 là các 
vectơ cột gồm n thành phần; 
1
2
m
b
b
b
b
 là 
vectơ cột gồm m thành phần; 0 0,c d là 
những hằng số, A là ma trận cấp m n 
156 
( m n , hạng của A bằng m). Từ bài toán 
(P), nếu mẫu thức là hằng số, ta có bài toán 
quy hoạch tuyến tính thông thường. Tuy 
nhiên nếu mẫu thức không là hàm số thì 
hàm mục tiêu thường là không là lồi. Điều 
đó có nghĩa, bài toán tối ưu dạng phân thức 
tuyến tính là bài toán tối ưu không lồi. Có 
nhiều phương pháp giải bài toán này đã 
được tổng hợp và giới thiệu trong tài liệu 
[3], [11]. Hơn thế nữa nhiều lược đồ đối 
ngẫu cho bài toán tối ưu dạng phân thức 
tuyến tính đã được thiết lập [1], [13], [6], 
[7], [2], [12]. 
Chúng ta đã biết rõ rằng: trong tối ưu 
tuyến tính, đối ngẫu của bài toán tối ưu 
tuyến tính cũng có dạng bài toán tối ưu 
tuyến tính. Câu hỏi này được đặt ra cho bài 
toán (P) nêu trên: Có hay không một lược 
đồ đối ngẫu của bài toán tối ưu dạng phân 
thức tuyến tính mà bài toán đối ngẫu cũng 
là dạng phân thức tuyến tính? 
Theo sự hiểu biết của chúng tôi, trong 
tất cả các lược đồ đối ngẫu áp dụng cho bài 
toán phân thức tuyến tính, chỉ có lược đồ 
đối ngẫu Seshan [12] đưa ra vào năm 1980 
là trả lời được câu hỏi nêu trên. 
Từ bài toán (P), trong bài báo [12], 
năm 1980, Seshan đã giới thiệu một bài 
toán đối ngẫu của (P) như sau: 
(D) Min 0
0
( , )
T
T
c u c
I u v
d u d
 (1.4) 
Đ.k. 0 0 ,T T Tc d u d c u A v c d d c (1.5) 
 0 0 0,
T T Tc d u d c u b v (1.6) 
 0, 0.u v (1.7) 
Với bài toán này, các định lý đối ngẫu 
yếu và đối ngẫu mạnh cho bài toán (P) đã 
được thiết lập. Năm 2006, T.Q. Sơn trong 
bài báo [2] đã quan tâm đến lược đồ này. 
Bằng cách điều chỉnh miền chấp nhận được 
của bài toán (P) một cách thích hợp, thông 
qua một lược đồ đối ngẫu cải biên, các 
định lí về đối ngẫu yếu và đối ngẫu mạnh 
được thiết lập. Hơn thế nữa, đặc trưng tập 
nghiệm của (P) đã được giới thiệu. Lược 
đồ đối ngẫu nói trên đã được tổng hợp và 
giới thiệu trong tài liệu [3]. Mặc dù lược 
đồ đối ngẫu Seshan thu hút được quan tâm, 
nhưng các bước tiến hành xây dựng bài 
toán đối ngẫu Seshan dường như vẫn chưa 
được làm rõ và câu hỏi về cơ sở để hình 
thành được bài toán đối ngẫu Seshan vẫn 
còn bỏ ngỏ trong nhiều năm. Năm 2010, 
trong bài báo số [4], các tác giả đã làm rõ 
một số lược đồ đối ngẫu tương đương của 
bài toán (P). Đặc biệt tác giả chỉ ra lược đồ 
đối ngẫu của (P) do Gol'stein đề nghị trong 
bài báo số [9] có thể dẫn tới đối ngẫu 
Seshan thông qua một hàm Lagrange thích 
hợp dạng phân thức và phép biến đổi của 
Charnes-Coopper. 
Mục đích của nghiên cứu này là đưa 
ra lời giải thích về sự hình thành bài toán 
đối ngẫu mà Seshan đã giới thiệu trong 
[12]. Bằng cách tiếp cận bài toán đối ngẫu 
theo kiểu biến đổi của Charnes - Cooper 
[10] và theo kiểu biến đổi Dinkelbach [3], 
chúng tôi đã đưa ra được các giải thích 
hợp lý cho việc hình thành lược đồ đối 
ngẫu của Seshan. Chú ý rằng, mặc dù sử 
dụng biến đổi Charnes-Cooper để đi đến 
lược đồ đối ngẫu Seshan, nhưng cách tiếp 
cận của chúng tôi là không trùng lặp với 
hướng tiếp cận của Gol'strein mà bài báo 
[4] đã bình luận. 
Trong các phần còn lại của bài báo 
này, phần tiếp theo được dành cho một số 
kết quả cơ bản đã biết để phục vụ cho các 
chứng minh trong bài báo. Trong phần 
cuối cùng, cũng là phần chính của bài 
báo, chúng tôi nêu ra hai cách tiếp cận để 
giải thích sự hình thành bài toán đối ngẫu 
đã giới thiệu trong [12]. Một ví dụ cũng 
157 
được giới thiệu để minh họa cho kết quả 
nghiên cứu. 
2. Các kí hiệu và kiến thức cơ bản 
Kí hiệu , 0nX x Ax b x là 
tập chấp nhận được của bài toán (P). Giả 
sử 
0 0
Td x d với mọi x X , tập X là 
bị chặn và hàm mục tiêu F của bài toán 
(P) không phải là hàm hằng trên X . Kí 
hiệu Y là tập chấp nhận được của bài toán 
(D) và giả sử 
0 0
Td u d với mọi 
 ,u v Y . 
Từ bài toán (P), bằng cách sử dụng 
phép đổi biến của Charnes – Cooper [3], 
đặt 
0
1
T
t
d x d
 và y tx ta thu