BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
======

BÙI THỊ BÍCH PHƯƠNG

CÁC ĐIỀU KIỆN TỐI ƯU TRONG BÀI TOÁN
QUY HOẠCH HAI CẤP TUYẾN TÍNH
Chuyên ngành: Toán Giải tích
Mã số: 60 46 01 02

LUẬN VĂN THẠC SĨ TOÁN HỌC

Người hướng dẫn khoa học: PGS. TS. NGUYỄN QUANG HUY

HÀ NỘI - 2015


LỜI CẢM ƠN
Trước khi trình bày nội dung chính của luận văn, tôi xin bày tỏ lòng
biết ơn sâu sắc tới PGS. TS. Nguyễn Quang Huy người đã định hướng
chọn đề tài và tận tình hướng dẫn để tôi có thể hoàn thành luận văn
này.
Tôi cũng xin bày tỏ lòng biết ơn chân thành tới phòng Sau đại học,
các thầy cô giáo giảng dạy chuyên ngành Toán giải tích trường Đại học
Sư phạm Hà Nội 2 đã giúp đỡ tôi trong suốt quá trình học tập và làm
luận văn.
Cuối cùng, tôi xin được gửi lời cảm ơn chân thành tới gia đình và
bạn bè đã động viên, giúp đỡ và tạo điều kiện về mọi mặt trong quá
trình học tập để tôi hoàn thành bản luận văn này.


∅

tập rỗng

| x|

giá trị tuyệt đối của x ∈ Rn

grphF

đồ thị của F

A×B

tích Descartes của hai tập hợp A và B

∀x

với mọi x

Argmin{f (x) | x ∈ ΣΩ} tập nghiệm của bài toán tối ưu vô hướng
A := B

A được định nghĩa bằng B

limsup

giới hạn trên cho dãy số thực

intΩ

ep = (1, · · · , 1)T ∈ Rp

vectơ p chiều có các tọa độ bằng một

ΨL (·)

tập nghiệm của bài toán cấp dưới tuyến tính

R(B)

miền ổn định với một nghiệm của một quy hoạch
tuyến tính

∇f (x)

gradient của hàm f : Rn → R, gradient là một
hàng vectơ

∇x f (x, y)

gradient của hàm f : Rn × Rm → R tương ứng
với biến x


Mục lục
Mở đầu

1

1 Bài toán tối ưu hai cấp tuyến tính


2.2.1

Tối ưu đa mục tiêu . . . . . . . . . . . . . . . . .

17

2.2.2

Quy hoạch 0–1 tuyến tính . . . . . . . . . . . . .

22

3 Các điều kiện tối ưu hai cấp tuyến tính

25

3.1

Điều kiện Karush-Kuhn-Tucker . . . . . . . . . . . . . .

25

3.2

Một số điều kiện tối ưu khác . . . . . . . . . . . . . . . .

31

3.2.1

quy hoạch hai cấp được giới thiệu tới cộng đồng tối ưu hóa trong những
năm bảy mươi của thế kỷ 20. Sau thời điểm đó đã có một sự phát triển
nhanh chóng các nghiên cứu chuyên sâu cho lớp bài toán này theo cả
hai hướng nghiên cứu lý thuyết và ứng dụng bởi các nhà toán học, kinh
tế và kỹ sư. Từ quan điểm toán học, bài toán quy hoạch hai cấp là bài
toán phức tạp có độ khó NP. Với những lí do này và trong khoảng thời
gian có hạn, tôi chọn nghiên cứu một lớp đặc biệt của các bài toán này
là “Các điều kiện tối ưu trong bài toán quy hoạch hai cấp tuyến tính”
cho đề tài luận văn thạc sĩ của mình.

2. Mục đích nghiên cứu
Tìm hiểu về lý thuyết quy hoạch hai cấp, cụ thể là mô hình bài
toán, các khái niệm nghiệm, sự tồn tại nghiệm, mối quan hệ giữa bài
toán quy hoạch hai cấp và các bài toán quy hoạch toán học khác, điều


2
kiện cần và đủ tối ưu trong các bài toán quy hoạch hai cấp.

3. Nhiệm vụ nghiên cứu
Sự tồn tại nghiệm, mối quan hệ giữa bài toán quy hoạch hai cấp
tuyến tính và các bài toán quy hoạch toán học khác, điều kiện cần và
đủ tối ưu trong các bài toán quy hoạch hai cấp tuyến tính.

4. Đối tượng và phạm vi nghiên cứu
Lý thuyết tối ưu tuyến tính, quy hoạch hai cấp tuyến tính, sự tồn
tại nghiệm và các điều kiện tối ưu.

5. Phương pháp nghiên cứu
Sử dụng các phương pháp nghiên cứu trong đại số tuyến tính, giải

ở đó f : Rn × Rm → R,
Rq ,

g : Rn × R m → Rp ,

g (x, y) = (g1 (x, y) , ..., gp (x, y))T ,

(1.1)
h : Rn × Rm →

h (x, y) = (h1 (x, y) , ..., hq (x, y))T ,

có tập nghiệm kí hiệu là Ψ(y) với cố định y ∈ Rn và Ψ được gọi là ánh
n

xạ đa trị từ Rm vào Rn , kí hiệu là Ψ : Rm → 2R ,Ψ(y) = Sol(1.1) =


4
Argmin{f (x, y) : g (x, y) ≤ 0, h (x, y) = 0}
x

= {x ∈ Rn : f (x, y) = min{f (x, y) : g (x, y) ≤ 0, h (x, y) = 0}}.
x

Khi đó ta có bài toán quy hoạch hai cấp có dạng là:
“ min ” {F (x(y), y) : G(x(y), y) ≤ 0, H(x(y), y) = 0, x(y) ∈ Ψ(y)} ,
y

(1.2)


Chú ý rằng sự mô tả của bài toán tối ưu tuyến tính phụ thuộc tham số
ở trên không thực sự hạn chế trong trường hợp tổng quát miễn là chúng
ta chỉ nhiễu tuyến tính vế phải. Trường hợp hàm mục tiêu của bài toán
cấp dưới phụ thuộc tham số cũng như trường hợp khi cả vế phải và hàm
mục tiêu là nhiễu tuyến tính có thể giải quyết bằng cách tương tự. Kí
hiệu
ΨL (y) = Argmin < c, x >: A1 x ≤ a − A2 y, x ≥ 0
x

là tập các nghiệm tối ưu của bài toán (1.3). Khi đó, bài toán quy hoạch
hai cấp có dạng:
min < d1 , x > + < d2 , y >: A3 y = b, y ≥ 0, x ∈ ΨL (y) ,
y

(1.4)


5
ở đó b ∈ Rl y ∈ Rm , và A3 ∈ Rl×m . Ta cũng chú ý rằng, dạng phát biểu
của bài toán trên thường được sử dụng để biểu thị tính bất định trong
định nghĩa của bài toán hai cấp trong trường hợp nghiệm của bài toán
cấp dưới không duy nhất.
Ví dụ 1.1. Xét bài toán cực tiểu của hàm mục tiêu cấp trên
3x + y → min,
với 1 ≤ y ≤ 6 và x là nghiệm của bài toán cấp dưới
min {−x : x + y ≤ 8, 4x + y ≥ 8, 2x + y ≤ 13} .
x

Tập tất cả các cặp (x, y) thỏa mãn các ràng buộc cả cấp trên và


E

F(x,y)

M

D
B

1
y

1

Hình 1.1: Bài toán quy hoạch hai cấp tuyến tính.


7
ưu là 12.
Từ Hình 1.1 ta thấy, kể cả trường hợp đơn giản nhất là các hàm
tuyến tính, bài toán quy hoạch hai cấp là một bài toán tối ưu không lồi
và không khả vi. Vì vậy, khi tìm nghiệm tối ưu hay là tìm các điểm dừng
của các bài toán này có thể gặp rất nhiều khó khăn.

1.2

Tính chất hình học của quy hoạch hai
cấp tuyến tính


(1.6)

J ⊆ {1, . . . , p} xét tập nghiệm M (I, J)

của hệ đẳng thức (bất đẳng thức) tuyến tính
(A1 x + A2 y − a)i = 0, i ∈ J, (A1 x + A2 y − a)i ≤, i ∈
/ J,
xj = 0, j ∈
/ I, xj ≥ 0, j ∈ I, λi = 0, i ∈
/ J, λi ≥ 0, i ∈ J,
(A1T λ + c)j = 0, j ∈ I, (A1T λ + c)j ≥ 0, j ∈
/ I.
Khi đó, điều kiện (1.6) được thỏa mãn. Tập M (I, J) là đa diện và hình
chiếu của nó cũng là đa diện trên Rn × Rm . Từ đồ thị của ΨL (·) là hợp
của các tập M (I, J), ta có các khẳng định sau. Nếu một tập M (I, J) là
khác rỗng thì hình chiếu của nó trên không gian Rn × Rm bằng tập tất
cả các nghiệm của hệ:
(A1 x + A2 y − a)i = 0, i ∈ J, (A1 x + A2 y − a)i ≤ 0, i ∈
/ J,
xj = 0, j ∈
/ I, xj ≥ 0, j ∈ I.
Tập này xác định một mặt của tập lồi đa diện {(x, y) : A1 x + A2 y ≤
a, x ≥ 0}. Mặt khác, nếu một số điểm trong (x, y) của một mặt của tập
{(x, y) : A1 x + A2 y ≤ a, x ≥ 0} là chấp nhận được, thì x ∈ ΨL (y), suy
ra tất cả các mặt có tính chất này.
Sử dụng Định lý (1.1) cho quy hoạch hai cấp tuyến tính có thể tìm
được hàm mục tiêu cực tiểu trên mỗi phần của grphΨL (·) phụ thuộc vào
các ràng buộc cấp trên của bài toán (1.4). Mỗi bài toán con này là một
bài toán tối ưu tuyến tính. Do đó từ Định lý (1.1) ta thu được hệ quả
sau

8 − y
với y ∈

8 10
15 , 7

13
8,

với

8
15

≤y≤

với

13
8

≤ y ≤ 3,

với 3 ≤ y ≤ 8,

∪ [3, 8], x ≤ 5 cố định. Ta thấy tập chấp nhận được của

bài toán trong ví dụ trước thay đổi tính cực trị nếu ràng buộc cấp trên
x ≤ 5 được đưa vào bài toán cấp dưới. Khi đó tập chấp nhận được của
bài toán cấp trên lại không liên thông và bằng tập các điểm (x(y), y) với

1
y

1

Hình 1.2: Bài toán quy hoạch hai cấp tuyến tính với tập chấp nhận
được không liên thông.


11
Vì với x = 5 thì có nhiều giá trị của y (tập liên thông là tập với mỗi giá
trị của x thì có một giá trị của y).
Kết luận: Chương một trình bày cụ thể mô hình của bài toán tối
ưu hai cấp tuyến tính; mối liên hệ của bài toán này với các bài toán quy
hoạch khác.


12

Chương 2

Sự tồn tại nghiệm trong
tối ưu hai cấp tuyến tính
2.1

Sự tồn tại nghiệm

Ở chương trước ta đã xét bài toán quy hoạch hai cấp (1.4) có dạng:
min < d1 , x > + < d2 , y >: A3 y = b, y ≥ 0, x ∈ ΨL (y) .
y

một hàm số liên tục x : Rn+m → Rn với {x(y)} = Ψ(y) với mọi y sao
cho bài toán (2.1) có một nghiệm tối ưu. Khi đó, nếu nghiệm này được
thay vào bài toán quy hoạch hai cấp (1.4), thì ta nhận được bài toán
min{ d1 , x(y) + d2 , y : A3 y = b, y ≥ 0},
y

(2.2)

với định nghĩa cực tiểu tốt tương ứng với y. Bài toán tối ưu này là liên
tục nhưng không khả vi. Sử dụng Định lý Weierstrass ta có
Định lý 2.1. (Sự tồn tại nghiệm của bài toán tối ưu hai cấp
tuyến tính)[2, Theorem 3.2] Nếu tập M := {y ≥ 0 : A3 y = b} là khác
rỗng và compact, bài toán cấp dưới (2.1) có nhiều nhất một nghiệm tối
ưu với mọi y ∈ M và tập chấp nhận được của bài toán (1.4) là khác
rỗng, thì bài toán này có ít nhất một nghiệm tối ưu.
Như vậy nghiệm tối ưu (toàn cục) và tất cả các nghiệm tối ưu địa
phương có thể tìm thấy tại các đỉnh của một số các tập đa diện. Các
tập này là hình chiếu của tập nghiệm mỗi một hệ đẳng thức (bất đẳng
thức) tuyến tính sau lên Rn × Rm . Mỗi hệ này tương ứng với hai tập chỉ
số I ⊆ {1, . . . , n} ,J ⊆ {1, . . . , p} và được xác định như sau
(A1 x + A2 y 2 − a)i = 0,

λi ≥ 0,

với i ∈ J,

(A1 x + A2 y 2 − a)i ≤ 0,

λi = 0,



(2.4)

trong đó hàm mục tiêu là hàm tối ưu theo hai biến x, y độc lập. Một
nghiệm tối ưu của bài toán (2.4) được gọi là nghiệm tối ưu optimistic
của bài toán quy hoạch hai cấp (1.4), (2.1). Chú ý rằng, nếu bài toán
này có một nghiệm tối ưu thì nó tương đương với bài toán sau
min{ϕo (y) + d2 , y : A3 y = b, y ≥ 0},
y

(2.5)

ở đó
ϕo (y) = min{ d1 , x : x ∈ ΨL (y)}.
x

Thứ hai, nếu lựa chọn y không thể ảnh hưởng đến lựa chọn x trong
trường hợp bài toán tối ưu không biết trước kết quả. Ta thu được bài
toán được gọi là bài toán hai cấp pessimistic:
min{ϕp (y) + d2 , y : A3 y = b, y ≥ 0},
y

(2.6)

ở đó
ϕp (y) = max{ d1 , x : x ∈ ΨL (y)}.
x

Một nghiệm tối ưu pessimistic của bài toán quy hoạch hai cấp (1.4),
(2.1) được định nghĩa là một nghiệm tối ưu của bài toán (2.6).










2
1

nếu 0 ≤ y2 < y1 ≤ 1,

1
2

nếu 0 ≤ y1 < y2 ≤ 1,



conv




M (0, 0)

2
1


k→∞

lim ϕp (y1k , y2k ) = lim (−10y1k − 10y2k − x2 (y1k , y2k )) = −22.

k→∞

k→∞

Từ x2 ≤ 2, suy ra giá trị hàm mục tiêu tối ưu của bài toán hai cấp không
thể nhỏ hơn −22, nhưng với y1 = y2 = 1 ta có ϕp (1, 1) = −1 và giá trị
hàm mục tiêu cấp trên bằng −21. Do đó, giá trị cận dưới của ϕp (·) bằng
−22 và ϕp (·) = −22. Nên bài toán hai cấp pessimistic không có nghiệm
tối ưu.
Ở đây, giá trị cận dưới của hàm mục tiêu trong (1.4) tương ứng với
một đỉnh (x, y) của một số tập lồi đa diện. Đỉnh này là tối ưu nếu nó là
chấp nhận được với bài toán (2.6) trong trường hợp ít nhất nếu ΨL (y)
chứa duy nhất một điểm.

2.2

Mối liên hệ với các bài toán quy hoạch
toán học khác

Bài toán quy hoạch hai cấp có mối quan hệ gần gũi với các bài toán
khác trong quy hoạch toán học. Ở đây ta sẽ đưa ra hai mối liên hệ. Đó
là liên hệ giữa bài toán quy hoạch hai cấp với bài toán tối ưu đa mục
tiêu và bài toán quy hoạch 0–1 tuyến tính.

2.2.1

các kí hiệu tương tự như đã sử dụng trong công thức (1.3), (1.4). Tuy
nhiên, chỉ có điểm hữu hiệu chấp nhận được với bài toán quy hoạch hai
cấp là điểm A điểm này có giá trị hàm xấu nhất trong hàm mục tiêu
cấp trên. Do đó, trong tổng quát không thể sử dụng phương pháp của
tối ưu đa mục tiêu để giải trực tiếp các bài toán quy hoạch hai cấp. Dễ
thấy nghiệm tối ưu (optimistic hay pessimistic) của bài toán quy hoạch
hai cấp là tối ưu Pareto với bài toán tối ưu đa mục tiêu tương ứng nếu
c = αd1 với α ≥ 0. Kết luận này không đúng trong tổng quát nếu c
không song song với d1 . Điều này được minh họa trong ví dụ sau:
Ví dụ 2.2. Xét bài toán quy hoạch hai cấp tuyến tính:
2x2 − y → min,
y

0 ≤ y ≤ 3,
x ∈ Ψ( y),
ở đó
Ψ(y) = Argmin{−x1 : 100x1 − x2 ≤ 1, x2 ≤ y, x ≥ 0}.
x

Khi đó, cực tiểu hóa theo −x1 ta có
100x1 = 1 + x2 = 1 + y,
hay
Ψ(y) =

(1+y)
100

y

,


và

1+ε
, x2 = ε,
100

y = 3 − ε, x1 =
với mỗi ε ≥ 0 đủ nhỏ:

Giá trị hàm mục tiêu vectơ của bài toán tối ưu hai mục tiêu với ba
điểm (x∗ , y ∗ ), (ˆ
x, yˆ), (x, y) tương ứng là
2x∗2 − y ∗
−x∗1
Ta có

2x∗2 − y ∗
−x∗1

=

0

=

≥

−1
100


với ε > 0 đủ nhỏ. Suy ra nghiệm tối ưu của bài toán quy hoạch hai cấp
tuyến tính không cần là hữu hiệu với bài toán tối ưu vectơ tương ứng.
Sau đây ta chỉ ra rằng mối liên hệ giữa hai cấp tuyến tính và các bài
toán quy hoạch đa mục tiêu tuyến tính là gần gũi hơn trên những gợi
ý quan sát được. Tương tự, với mỗi bài toán quy hoạch hai cấp tuyến
tính, tồn tại một số bài toán đa mục tiêu tuyến tính sao cho nghiệm tối