Điều kiện cần và đủ cho bài toán đối ngẫu dạng Mond-Weir của bài toán quy hoạch toán học với ràng buộc cân bằng

87
ĐIỀU KIỆN CẦN VÀ ĐỦ CHo BÀI ToÁN ĐỐI NGẪU 
DẠNG MoND-wEIR CỦA BÀI ToÁN QUY HoẠCH 
ToÁN HỌC VỚI RÀNG BUỘC CÂN BẰNG
Trần Văn Sự 1
Võ Văn Minh2
Tóm tắt: Bài toán quy hoạch toán học có vai trò quan trọng trong lý thuyết tối ưu 
và được nghiên cứu nhiều trong toán học ứng dụng và mô hình trong thời gian gần đây 
bởi nhiều nhà nghiên cứu. Cho trước một bài toán quy hoạch toán học với ràng buộc 
cân bằng, để nghiên cứu điều kiện tối ưu cấp một và tính đối ngẫu cho bài toán chúng 
tôi thiết lập bài toán đối ngẫu dạng Mond-Weir đối với bài toán này. Dưới một số điều 
kiện phù hợp ban đầu liên quan đến các ràng buộc tập, đẳng thức và bất đẳng thức, 
các điều kiện cần và đủ tối ưu cho bài toán gốc và bài toán đối ngẫu được nghiên cứu 
sử dụng công cụ của giải tích lồi và đại số tuyến tính. Một số ứng dụng của bài toán 
quy hoạch toán học cùng với hai ví dụ cụ thể để mô tả kết quả đạt được cũng được 
cung cấp.
Từ khóa: Bài toán quy hoạch toán học với ràng buộc cân bằng, Bài toán đối 
ngẫu dạng Mond-Weir, Tính đối ngẫu yếu, tính đối ngẫu mạnh, Điều kiện cần và đủ 
cho nghiệm hữu hiệu yếu địa phương.
 1. Mở đầu 
 Lý thuyết đối ngẫu trong lý thuyết của các bài toán quy hoạch toán học giữ một 
vai trò quan trọng trong lý thuyết tối ưu. Bài toán quy hoạch toán học với ràng buộc 
cân bằng xuất hiện rất nhiều trong mô hình toán ứng dụng, chẳng hạn như lý thuyết 
tập mờ, lý thuyết điều khiển, robot, thiết kế kỹ thuật, v.v., và có nhiều ứng dụng lý 
thuyết khác như ứng dụng trong giải quyết các bài toán quy hoạch tuyến tính tổng quát, 
chẳng hạn bài toán bán hàng, bài toán vận tải, bài toán tìm bus, bài toán phân công 
lao động, bài toán phân bổ nguồn tài nguyên, v.v. (xem [1,2,3,4,5,6,7, 10] trong danh 
mục tài liệu tham khảo). Để nghiên cứu điều kiện cần và đủ cho bài toán quy hoạch 
toán học một cách đầy đủ, sâu sắc hơn và nhiều khi có phần tiện ích hơn nếu bài toán 
được nghiên cứu trong bài báo này gọi tên là (LOPEC) có thể biểu diễn thông qua 
một mô hình đối ngẫu dạng Mond-Weir của nó. Với mục đích này, chúng tôi gọi là 
bài toán (LOPEC) là bài toán gốc và bài toán đối ngẫu dạng Mond-Weir của bài toán 
gốc (LOPEC) là bài toán (MWLOPEC). Chú ý bài toán quy hoạch toán học với ràng 
buộc cân bằng được xem xét trong bài báo này là một dạng bài toán tối ưu tuyến tính. 
Chúng tôi dùng ký hiệu (LOPEC) thay cho ký hiệu thông dụng là (MPEC). Ký hiệu 
1. TS., Khoa Toán, Trường Đại học Quảng Nam 
2. ThS., Khoa Toán, Trường Đại học Quảng Nam
88
ĐIều KIỆN CẦN VÀ ĐỦ CHO BÀI TOáN ĐỐI NGẪu...
mới này chưa được sử dụng bởi bất kỳ tác giả nào khác. Bên cạnh, bài toán (LOPEC) 
là một dạng mở rộng trực tiếp tử bài toán quy hoạch tuyến tính tổng quát, bởi vì khi 
chúng ta chọn 0 0,G H≡ ∨ ≡ bài toán trên trở thành một bài toán quy hoạch tuyến 
tính tổng quát dạng “min” mà chúng ta biết nhiều trong giáo trình quy hoạch tuyến 
tính hay giáo trình tối ưu hóa. Do đó, bài toán mới được nghiên cứu trong bài báo này 
có nhiều ứng dụng trong các bài toán bán hàng, bài toán phân công lao động, bài toán 
đèn giao thông, bài toán tìm bus, v.v. như được đề cập bên trên. Ngoài ra, đối ngẫu kiểu 
Mond-Weir liên kết với bài toán gốc trên cũng chưa từng được nghiên cứu cho trường 
hợp tuyến tính. 
 2. Nội dung
Trong tiểu mục này chúng tôi giới thiệu một bài toán quy hoạch toán học gốc có 
ràng buộc cân bằng và đề xuất một mô hình đối ngẫu dạng Mond-Weir liên kết với bài 
toán gốc, bên cạnh chúng tôi cung cấp các định lý về tính đối ngẫu yếu và đối ngẫu 
mạnh cho cặp bài toán này. 
 2.1. Bài toán gốc 
Xét bài toán quy hoạch toán học với ràng buộc cân bằng cho ở dạng sau:
trong đó .,.〈 〉 ký hiệu tích vô hướng, C là một tập con khác rỗng trong không 
gian qR với chuẩn Euclidean, : ,q mg R R→ : ,q mg R R→ : , : , :q n q p q ph R R G R R H R R→ → → 
 là các ánh xạ tuyến tính cho trước. Ký hiệu K thay cho tập chấp nhận 
được của bài toán (LOPEC), ở đây 
 { }: ( ) 0, ( ) 0, ( ) 0, ( ) 0, ( ), ( ) 0K x C g x h x G x H x G x H x= ∈ ≤ = ≥ ≥ =
Mỗi vectơ x K∈ được gọi là một chấp nhận được của bài toán (LOPEC). 
Vectơ x K∈ là một nghiệm hữu hiệu yếu (toàn cục) của bài toán (LOPEC) nếu 
( ) ( ) .f x f x x K≥ ∀ ∈ (*) Nếu tồn tại 0δ > sao cho bất đẳng thức (*) đúng với mọi 
{ }:px K x R x x δ∈ ∩ ∈ − <
thì ta nói vectơ x K∈ là một nghiệm hữu hiệu yếu địa 
phương của bài toán (LOPEC). 
2.2. Bài toán đối ngẫu: Bài toán đối ngẫu dạng Mond-Weir liên kết với bài toán 
gốc (LOPEC) là bài toán “max” sau: 
 (MWLOPEC): [ ]
,
m ax ( )
u
f u
λ
( ) : min ( )
( ) 0, ( ) 0,
( ) 0, ( ) 0,
( ), ( ) 0,
x C
LOPEC f x
g x h x
G x H x
G x H x
∈
≤ = ≥ ≥〈 〉 =
: , : , :q n q p q ph R R G R R H R R→ → →
89
TRẦN VăN SỰ, Võ VăN MINH
trong đó
Ta đặt
Từ nay trở đi nếu không có giả thiết gì thêm, để tiện lợi trong công việc phát biểu 
chúng tôi luôn giả sử rằng:
 G HB B A Cµ µ µ µ φ+ +∪ ∪ ∪ = ,
( )
( )
1
1
( ) ( ) ( )
( ) ( ) 0 ;
( ) 0 ; ( ) 0 1,..., ;
( ) 0 ; ( ) 0 ;
0 ; , 0 1,2,..., ;
, , , 0 1,2,..., ;
g
n
g h h
i i j j j
i I j
p
G H
i i i i
i
i g j
i i
g h h
i g j j
G H G H
i i i i
G
C
f v g v h v
G v H v v C u
g u i I h u j n
G u i A B H u i C B
i I j n
i p
λ λ µ
λ λ
λ λ µ
λ λ µ µ
λ
∈ =
=
+ + −
 
− + ≥ ∀ ∈ −  
≥ ∀ ∈ = ∀ =
≤ ∀ ∈ ∪ ≤ ∀ ∈ ∪
≥ ∀ ∈ ≥ ∀ =
≥ ∀ =
=
∑ ∑
∑
( ) ( )
( ) ( ) ( )
( )
2
2
0, , 0,
, , ,
, , , , ,
, , , ,
H G H G H
A C A i i
G G H H
C c A ac C a A
G G H H h G H n p
C c A ac C a A
g h G H m n p
i B
u C
R
R
λ µ µ µ µ
λ λ λ λ
µ µ µ µ µ µ µ µ
λ λ λ λ λ
∈ ∈
+
∈ ∈
+ +

= = = ∀ ∈ = = ∈ = =
= = = ∈
= ∈
{ }
{ }
{ }
{ }
1
1
1
1
( ,..., ) : ,
( ,..., ) : ,
( ,..., ) : ,
( ,..., ) : ,
( ) 1... : ( ) 0 ,
( ) 1... : ( ) 0, ( ) 0 ;
( ) 1... : ( ) 0, ( ) 0 ;
( ) 1... : ( ) 0, ( ) 0 .
q m
m
q n
n
q p
p
q p
p
g g i
i i
i i
i i
g g g R R
h h h R R
G G G R R
H H H R R
I I x i m g x
A A x i p G x H x
B B x i p G x H x
C C x i p G x H x
= →
= →
= →
= →
= = = =
= = = = >
= = = = =
= = = > =
{ }
{ }
{ }
{ }
: 0 ;
: 0 ;
: 0, 0 ;
: 0, 0 .
G
i
H
i
G H G
i i
H G H
i i
A i A
C i C
B i B
B i B
µ
µ
µ
µ
µ
µ
µ µ
µ µ
+
+
= ∈ >
= ∈ >
= ∈ = >
= ∈ = >
90
ĐIều KIỆN CẦN VÀ ĐỦ CHO BÀI TOáN ĐỐI NGẪu...
các hàm ràng buộc g, h, G, H và hàm mục tiêu f là các ánh xạ tuyến tính (xem giáo 
trình Đại số tuyến tính của GS. TSKH. Ngô Việt Trung [9]).
Để làm rõ ràng hơn trong các phát biểu ở các tiểu mục tiếp theo, chúng tôi cung 
cấp một ví dụ số minh họa cho các mô hình được xây dựng bên trên như sau:
2.2.1. Ví dụ Cho [ ]2, ( 1, 1) 2, 3 , 1q C m n p= = − × − = = = . Xét bài toán quy 
hoạch toán học với ràng buộc cân bằng (LOPEC) trên không gian 2R như sau:
Tính toán trực tiếp ta nhận được một tập chấp nhận được của bài toán (LOPEC) là 
 { }(0, 0) .K =
Chọn một vectơ chấp nhận được (0,0)x = và ta thu được 
{ } { }1 , , 1 .gI A C Bφ= = = = Khi đó mô hình đối ngẫu dạng Mond-Weir của bài toán 
gốc (LOPEC) là bài toán đối ngẫu (MWLOPEC) sau:
2.2.2. Nhận xét Ta thấy rằng mô hình của bài toán gốc (LOPEC) và bài toán 
đối ngẫu (MWLOPEC) được đề xuất bên trên với các hàm ràng buộc và hàm mục tiêu 
là tuyến tính có thể giải bằng công cụ đại số tuyến tính, tuy nhiên để chúng ta có cơ sở 
nền tảng cho việc xây dựng các thuật toán số tìm nghiệm hữu hiệu yếu (địa phương) 
của chúng trong tương lai, mục đích chính của chúng tôi trong bài báo này là xây dựng 
1 2
1 2( , )
1 2
1 2
1 2
2
2
1 2 2
( W ) : min ( ) 2 3
( ) 2 0,
( ) 0,
( ) 0,
( ) 0,
( ), ( ) 0.
x x C
M LOPEC f x x x
g x x x
h x x x
G x x x
H x x
G x H x x x x
∈
= −
 = − ≤
= − =
= + ≥
= ≥ = + =
[ ]
( ) ( )( )
( ) ( ) ( )
1 2 1 1 11
1 2
, , , , ,
1 2 1 1 2 1 1 1 2
1 1 2 1 2 1 2 1 2
1 2
1 2
1 2
2
1 1 1 1 1
1
( W ) : m ax ( ) 2 3
2 3 2
0 , , ;
( ) 2 0,
( ) 0,
( ) 0,
( ) 0,
0, 0, 0, 0, 0,
1 1, 2
g h G Hu u
g h h
G H
g h h G H
M LOPEC f u u u
v v v v v v
v v v v v C u u
g u u u
h u u u
G u u u
H u u
u u
λ λ λ λ
λ λ µ
λ λ
λ λ µ λ λ
= −
− + − + − −
− + − ≥ ∀ ∈ −
= − ≥
= − =
= + ≤
= ≤
≥ ≥ ≥ ≥ ≥
− < < − ≤ 2 3.

≤
91
TRẦN VăN SỰ, Võ VăN MINH
các định lí tính đối ngẫu yếu và tính đối ngẫu mạnh cho cặp bài toán gốc-đối ngẫu 
(LOPEC) và (MWLOPEC). 
2.3. Kết quả mới của bài báo 
2.3.1. Định lý (tính đối ngẫu yếu) Cho x là vectơ chấp nhận được của bài toán 
gốc (LOPEC) và cặp ( ),u λ là vectơ chấp nhận được của bài toán đối ngẫu dạng 
Mond-Weir (MWDOPEC). Khi đó, với mọi x là vectơ chấp nhận được của bài toán gốc 
(LOPEC), ta luôn có bất đẳng thức sau ( ) ( ).f x f u≥
Chứng minh: Vì ánh xạ f được giả thiết là tuyến tính nên 
 ( ) ( ) ( ).f x u f x f u− = − (2.1)
Các ánh xạ ràng buộc g, h, G và H cũng được giả thiết là tuyến tính, do đó 
các thành phần bên trong của chúng là các hàm vô hướng tuyến tính. Vậy, các đẳng 
thức sau đúng:
 ( ) ( ) ( ) .i i i gg x u g x g u i I− = − ∀ ∈ (2.2)
 ( )( ) ( )( ) ( )( ), .i i iH x u H x H u i C B− − = − − − ∀ ∈ ∪ (2.3)
 ( )( ) ( )( ) ( )( ), .i i iH x u H x H u i C B− − = − − − ∀ ∈ ∪ (2.4)
 ( )( ) ( )( ) ( )( ), .i i iH x u H x H u i C B− − = − − − ∀ ∈ ∪ (2.5)
 ( )( ) ( )( ) ( )( ), .i i iH x u H x H u i C B− − = − − − ∀ ∈ ∪ (2.6)
Theo giả thiết ban đầu ta có điều kiện ràng buộc G HB B A Cµ µ µ µ φ+ +∪ ∪ ∪ = , vì vậy 
chúng ta có thể nhân lần lượt từng phương trình trong (2.2), (2.3), (2.4), (2.5) và (2.6) 
bởi 0, ; 0 1,2,..., ;g hi g ii I i nλ λ≥ ∀ ∈ > ∀ = 0 1,2,..., ;hi i nµ > ∀ = 0 ;Gi i A Bλ > ∀ ∈ ∪ 
0 ,Hi i B Cλ > ∀ ∈ ∪ , sau đó cộng lần lượt chúng lại với nhau ta được: 
 (2.7)
Ta lại có cặp ( ),u λ là vectơ chấp nhận được cho bài toán đối ngẫu dạng Mond-
Weir (MWLOPEC) và thêm nửa một vectơ hiệu x u C u− ∈ − , theo định nghĩa ta suy ra 
( ) ( )
( ) ( )
1... 1...
1... 1... 1 1
1 1
( ) ( ) ( ) ( ) ( ) ( )
( )( ) ( )( ) ( ) ( )
( ) ( )
( ) ( )
g g
g
g g h h
i i i i j j j j
i I i I j n j n
p p
h h G G
j j j j i i i i
j n j n i i
p p
H H
i i i i
i i
g h
i i i
i I
f x f u g x g u h x h u
h x h u G x G u
H x H u
f u x g x u
λ λ λ λ
µ µ λ λ
λ λ
λ λ µ
∈ ∈ = =
= = = =
= =
∈
− + − + −
+ − − − + − − −
+ − − −
= − + − + −
∑ ∑ ∑ ∑
∑ ∑ ∑ ∑
∑ ∑
∑ ( )
( ) ( )
1
1 1
( )
( ) ( ).
n
h
i i
i
p p
G H
i i i i
i i
h x u
G x u H x uλ λ
=
= =
−
+ − − + − −
∑
∑ ∑
92
ĐIều KIỆN CẦN VÀ ĐỦ CHO BÀI TOáN ĐỐI NGẪu...
Kết hợp bất đẳng thức này với điều kiện (2.7) cho ta kết quả
 (2.8)
Lại có x là vectơ chấp nhận được của bài toán quy hoạch toán học gốc (LOPEC), 
suy ra 
 (2.9)
Tiến hành một cách tương tự cách bước như ở trên, ta nhận được
 (2.10)
Kết hợp các điều kiện (2.9)-(2.10) ta thu được bất đẳng thức ( ) ( ).f x f u≥
Điều phải chứng minh.
2.3.2. Nhận xét: Chúng ta thấy rằng tính đối ngẫu yếu cung cấp một chặn dưới 
đối với hàm mục tiêu của bài toán gốc (LOPEC). Đó là lý do tại sao đối ngẫu có vai trò 
quan trọng trong nghiên cứu các bài toán quy hoạch toán học và nhờ nó có thể nghiên 
cứu sâu hơn cấu trúc của lớp các bài toán quy hoạch này.
Trong trường hợp x K∈ một phát biểu mới về tính đối ngẫu mạnh của chúng 
tôi cho nghiệm hữu hiệu yếu địa phương là như sau. 
2.3.3. Định lý (tính đối ngẫu mạnh) Cho một vectơ x K∈ là nghiệm hữu hiệu 
yếu địa phương của bài toán gốc (LOPEC). Giả sử rằng 0,h ≡ và tồn tại ít nhất một 
phương chấp nhận được v C x∈ − sao cho 
( )
( ) ( )
1
1 1
( ) ( ) ( )
( ) ( ) 0.
g
n
g h h
i i i i i
i I i
p p
G H
i i i i
i i
f u x g x u h x u
G x u H x u
λ λ µ
λ λ
∈ =
= =
− + − + − −
+ − − + − − ≥
∑ ∑
∑ ∑
( ) ( )
1... 1...
1 1
( ) ( ) ( )( )
( ) ( ) 0.
g
g h h
i i j j j j
i I j n j n
p p
G H
i i i i
i i
g x h x h x
G x H x
λ λ µ
λ λ
∈ = =
= =
+ + −
+ − + − ≤
∑ ∑ ∑
∑ ∑
( ) ( )
( ) ( )
1... 1...
1... 1... 1 1
1 1
( ) ( ) ( ) ( ) ( ) ( )
( )( ) ( )( ) ( ) ( )
( ) ( ) 0.
g g
g g h h
i i i i j j j j
i I i I j n j n
p p
h h G G
j j j j i i i i
j n j n i i
p p
H H
i i i i
i i
f x f u g x g u h x h u
h x h u G x G u
H x H u
λ λ λ λ
µ µ λ λ
λ λ
∈ ∈ = =
= = = =
= =
− + − + −
+ − − − + − − −
+ − − − ≥
∑ ∑ ∑ ∑
∑ ∑ ∑ ∑
∑ ∑
( ) ( )
1... 1...
1 1
( ) ( ) ( )( )
( ) ( ) 0.
g
g h h
i i j j j j
i I j n j n
p p
G H
i i i i
i i
g x h u h u
G u H u
λ λ µ
λ λ
∈ = =
= =
+ + −
+ − + − ≥
∑ ∑ ∑
∑ ∑
93
TRẦN VăN SỰ, Võ VăN MINH
Khi đó tồn tại một vectơ ( ) 2, ,g G H m pRλ λ λ λ += ∈ sao cho một cặp ( ),x λ là 
nghiệm hữu hiệu yếu địa phương của bài toán đối ngẫu Mond-Weir (MWLOPEC) và 
giá trị hàm mục tiêu của chúng tương ứng bằng nhau. 
Chứng minh: Theo giả thiết ban đầu, một vectơ x K∈ là nghiệm hữu hiệu yếu 
địa phương của bài toán gốc (LOPEC) nên hệ sau không xảy ra:
áp dụng Định lí 21.2 trong Giáo trình của Rockafeller [8], tồn tại một vectơ 
chấp nhận được ( ) 1 4, , m pRτ λ µ + +∈ , trong đó ( ) 2, , ,g G H m pRτ λ λ λ λ ++∈ = ∈¡ và ( ) 2,G H pRµ µ µ= ∈ không đồng thời bằng không thỏa mãn bất đẳng thức sau
 (2.11)
Mặt khác, theo giả thiết ban đầu ta chọn ra một phương v C x∈ − sao cho 
 ( ) 0, .i gg v i I< ∀ ∈ (2.12)
 ( )( ) 0, ,iG v i A B− < ∀ ∈ ∪ (2.13)
 ( )( ) 0, .iH v i B C− < ∀ ∈ ∪ (2.14)
Kết hợp các điều kiện (2.11), (2.12), (2.13) và (2.14) ta đi đến kết luận .λ λ= 
Không mất tính tổng quát ta coi .λ λ= và do đó có thể coi .λ λ= áp dụng Định lí 2.1, 
ta nhận được
 ( ) ( )
1 1
( ) ( ) ( ) ( ) ( ) 0
g
p p
g G H
i i i i i i
i I i i
f x f u g u G u H uλ λ λ
∈ = =
≥ + + − + − ≥∑ ∑ ∑ (2.15)
với mọi cặp vectơ ( ),u λ là nghiệm chấp nhận được của bài toán đối ngẫu dạng 
Mond-Weir (MWLOPEC). Tiếp theo ta thấy rằng
 ( ) ( )
1 1
( ) ( ) ( ) ( ) ( ).
g
p p
g G H
i i i i i i
i I i i
f x f x g x G x H xλ λ λ
∈ = =
= + + − + −∑ ∑ ∑ (2.16)
Thật vậy, ta luôn có ( ) 0;g ii I g x∈ ⇒ = ( ) 0; ( ) 0.i ii A B G x i B C H x∈ ∪ ⇒ = ∈ ∪ ⇒ = 
Vì 
1
( ) ( ) 0.
p
i i
i
x K G x H x
=
∈ ⇒ =∑ Điều này kéo theo kết quả sau được thỏa mãn
( ) 0, ,
( )( ) 0, ,
( )( ) 0, .
i g
i
i
g v i I
G v i A B
H v i B C
< ∀ ∈
− < ∀ ∈ ∪
− < ∀ ∈ ∪
( ) 0
( ) 0, ,
( )( ) 0, ,
( )( ) 0, ,
.
i g
i
i
f v
g v i I
G v i A B
H v i B C
v C x
<
< ∀ ∈
− < ∀ ∈ ∪
− < ∀ ∈ ∪ ∈ −
( ) ( )
1 1
( ) ( ) ( ) ( ) 0, .
g
p p
g G H
i i i i i i
i I i i
f v g v G v H v v C xτ λ λ λ
∈ = =
+ + − + − ≥ ∀ ∈ −∑ ∑ ∑
94
ĐIều KIỆN CẦN VÀ ĐỦ CHO BÀI TOáN ĐỐI NGẪu...
( ) ( ) ( ) ( )
1 1
( ) ( ) ( ) ( ) ( ).
g
p p
g G H G H
i i i i i i i i i i
i I i i i C i A
g x G x H x G x H xλ λ λ λ λ
∈ = = ∈ ∈
+ − + − = − + −∑ ∑ ∑ ∑ ∑
Sử dụng khái niệm bài toán đối ngẫu (MWLOPEC) ta cũng có
 0; 0.G Hi ii C i Aλ λ∈ ⇒ = ∈ ⇒ =
Vậy đẳng thức (2.16) được thỏa mãn. Một lần nửa, kết hợp (2.15) và (2.16) ta được
( ) ( )
( ) ( )
1 1
1 1
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
g
g
p p
g G H
i i i i i i
i I i i
p p
g G H
i i i i i i
i I i i
f x g x G x H x
f u g u G u H u
λ λ λ
λ λ λ
∈ = =
∈ = =
+ + − + −
≥ + + − + −
∑ ∑ ∑
∑ ∑ ∑
với mọi cặp vectơ ( ),u λ là nghiệm chấp nhận được của bài toán đối ngẫu (MWLOPEC). 
Hệ quả là một cặp vectơ ban đầu ( ),x λ trở thành một nghiệm hữu hiệu yếu địa 
phương của bài toán đối ngẫu Mond-Weir (MWLOPEC), và thêm nửa giá trị hàm mục 
tiêu của chúng tương ứng bằng nhau. 
Điều phải chứng minh. 
2.3.4. Nhận xét Các kết quả thu được của chúng tôi trong tiểu mục này là mới 
và chưa được nghiên cứu trước đây. Khi 0G ≡ hoặc 0H ≡ , bài toán quy hoạch toán 
học (LOPEC) qui về bài toán quy hoạch tuyến tính dạng tổng quát, do đó kết quả thu 
được này cũng có thể áp dụng trực tiếp cho các mô hình của bài toán quy hoạch tuyến 
dạng min, bài toán vận tải, bài toán sản xuất đồng bộ, bài toán cái túi, .v.v. (xem Giáo 
trình quy hoạch tuyến tính của Phí Mạnh Ban [10] cho chi tiết). 
Để mô tả kết quả nhận được, chúng tôi cung cấp một ví dụ số như sau. 
2.3.5. Ví dụ Cho [ ] [ ]2, 0, 3 0, 3 , 1.q C m p= = × = = Xét bài toán quy hoạch 
toán học với ràng buộc cân bằng (LOPEC) trên không gian 2R như sau:
( )
1 2
1 2( , )
1 2
1 2
2
1 2 2
( ) : min ( ) 2 3
( ) 2 0,
( ) 5 0,
( ) 0,
( ), ( ) 5 0.
x x C
LOPEC f x x x
g x x x
G x x x
H x x
G x H x x x x
∈
= +
= − ≤
= − ≥
= ≥ = − =
Khi đó tập chấp nhận được của bài toán (LOPEC) có dạng 
( ) 2 3, 5 : 0 .
5
K a a a = ∈ ≤ ≤  ¡
Dễ dàng thấy rằng vectơ (0,0)x = là một nghiệm hữu hiệu yếu địa phương của 
bài toán gốc (LOPEC). Kiểm tra trực tiếp các tập chỉ số ta thu được Chọn một hướng 
95
TRẦN VăN SỰ, Võ VăN MINH
1
, 2
2
v C x = ∈ −   , các bất đẳng thức (2.12), (2.13) và (2.14) luôn được thỏa mãn. 
Vậy tất cả các giả thiết trong Định lí 2.3 đúng. Khi đó, một mô hình đối ngẫu 
dạng Mond-Weir cho bài toán gốc (LOPEC) là bài toán (MWLOPEC) có dạng:
( )
( ) ( ) ( )
1 2 1 1 2
1 1 2 1 2 1 2 1 2
1 2 1 2 2
1 1 1
2 3 2
5 0 , , ;
2 0, 5 0, 0,
0, 0, 0,
0 3, 1, 2.
g
G H
g G H
i
v v v v
v v v v v C u u
u u u u u
u i
λ
λ λ
λ λ λ
 + + −
− − − ≥ ∀ ∈ −
− ≥ − ≤ ≤ ≥ ≥ ≥ ≤ ≤ =
Giả sử không xảy ra điều kiện sau:
nghĩa là 
.G HB B A Cµ µ µ µ φ+ +∪ ∪ ∪ =
Một lần nửa chúng ta áp dụng Định lí 2.3, khi đó tồn tại một vectơ 
( ) 3, ,g G H Rλ λ λ λ= ∈ sao cho một cặp ( ),x λ là nghiệm hữu hiệu yếu địa phương 
của bài toán đối ngẫu dạng Mond-Weir (MWLOPEC) và giá trị hàm mục tiêu của 
chúng tương ứng bằng nhau. Thật vậy, chúng ta thử trực tiếp lại nhận định trên như 
sau: Ta có (0,0)x = là nghiệm hữu hiệu yếu địa phương của bài toán (LOPEC) với 
giá trị của hàm mục tiêu ( ) 0.f x = Mặt khác, giải trực tiếp bài toán đối ngẫu dạng 
Mond-Weir (MWLOPEC), tìm được nghiệm hữu hiệu yếu địa phương là một cặp vectơ 
( ) ( ), 0, 0, 4, 2,1u λ = và giá trị hàm mục tiêu của chúng ( ) 0.f u = Vậy, ( ) ( ).f x f u= 
Định lí được kiểm tra đầy đủ. 
3. Kết luận
Bài báo đã cung cấp một mô hình đối ngẫu dạng Mond-Weir cho bài toán gốc 
(LOPEC) với ràng buộc cân bằng; chứng minh hai định lí chính về tính đối ngẫu yếu 
và tính đối ngẫu mạnh cho bài toán quy hoạch toán học gốc (LOPEC) và bài toán đối 
ngẫu dạng Mond-Weir (MWLOPEC) liên kết với nó; và chỉ ra được một số ứng dụng 
cụ thể của bài toán quy hoạch toán học với ràng buộc cân bằng. Kết quả đạt được trong 
bài báo là mới và chưa từng được nghiên cứu trước đây bằng các công cụ của đại số 
tuyến tính. 
1 2 1 11
1 2
, , , ,
( W ) : m ax ( ) 2 3
g G Hu u
M LOPEC f u u u
λ λ λ
= +
1 1
1 1
0, 0
0, 0
H G
G H
µ µ
µ µ
 = >
= >
96
ĐIều KIỆN CẦN VÀ ĐỦ CHO BÀI TOáN ĐỐI NGẪu...
TÀI LIỆU THAM KHẢo 
[1] R.I. Bot, S.-M. Grad (2010), “Wolfe duality and Mond-Weir duality via 
perturbations”, Nonlinear Anal. Theory Methods Appl., 73: 374-384.
[2] S. Dempe, A.B. Zemkoho (2012), “Bilevel road pricing: Theoretical analysis and 
optimality conditions”, Ann. Oper. Research, 196: 223-240. 
[3] Z.Q. Luo, J.S. Pang, D. Ralph (1996), “Mathematical problems with equilibrium 
constraints”, Cambridge University Press, Cambridge.
[4] M. Mond, T. Weir (1981), “Generallized concavity and duality, Generallized 
concavity in optimization and economics”, Academic Press, New York.
[5] N. Movahedian, S. Nabakhtian (2010), “Necessary and sufficient conditions for 
nonsmooth mathematical problems with equilibrium constraints”, Nonlinear Anal., 
72: 2694-2705.
[6] R. Reemtsen, J.J. Ruckmann (1998), “Semi-infinite programming”, Dordrecht: 
Kluwer.
[7] J. J. Ye (2005), “Necessary and sufficient optimality conditions for mathematical 
program with equilibrium constraints”, J. Math. Anal. Appl., 307: 350-369. 
[8] R. T. Rockafellar (1970), “Convex Analysis”, Princeton Univ. Press, Princeton.
[9] Ngô Việt Trung (2001), “Giáo trình đại số tuyến tính”, NXB KHTN&CN, Hà Nội.
[10] Phí Mạnh Ban (2007), “Quy hoạch tuyến tính”, NXB ĐHSP, Hà Nội. 
Title: NECESSARY AND SUFFICIENT CoNDITIoNS FoR THE 
MoND-wEIR TYPE DUAL PRoBLEM oF MATHEMATICAL 
PRoGRAMMING PRoBLEM wITH EQUILIBRIUM CoNSTRAINTS
TRAN VAN Su 
VO VAN MINH
 Quang Nam University 
Abstract: The mathematical programming problem plays an important role in the 
theory of optimization and has been widly investigated in the field of applied mathematics 
and modellings in recently times by many researchers. Given a mathematical programming 
problem with equilibrium constraints, in order to study the optimality condition of order 
one and the duality of these problem, we formulate the Mond-Weir type dual problem 
to such problem. Under suitable initial conditions on the set, inequality and equality 
constraints, necessary and sufficient conditions between the original problem and the 
dual problem with respect to these problem are studied by using the tools of convex 
analysis and linear algebra. Some applications to the mathematical programming 
problems are provided as well. 
 Key words: Mathematical programming problem with equilibrium constraints, 
Mond-Weir type dual problem, Weak duality, S3trong duality, Necessary and sufficient 
condition for locally weak efficient solutions.