ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
—————————————————
NGUYỄN THỊ HẢI NHƯ
MỘT THUẬT TOÁN TÌM NGHIỆM TỐI ƯU
CỦA BÀI TOÁN QUY HOẠCH SONG TUYẾN TÍNH
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - Năm 2017
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HOC
—————————————————
NGUYỄN THỊ HẢI NHƯ
MỘT THUẬT TOÁN TÌM NGHIỆM TỐI ƯU
CỦA BÀI TOÁN QUY HOẠCH SONG TUYẾN TÍNH
Chuyên ngành: TOÁN ỨNG DỤNG
Mã số: 60.46.01.12
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học
GS. TS. TRẦN VŨ THIỆU
Thái Nguyên - Năm 2017
i
Lời cảm ơn
Tôi xin bày tỏ lòng biết ơn tới GS.TS Trần Vũ Thiệu, người đã định hướng
chọn đề tài và tận tình hướng dẫn, cho tôi những nhận xét quý báu để tôi có
thể hoàn thành luận văn.
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 dạy cao học chuyên ngành Toán ứng dụng trường Đại học Khoa Học -
Đại học Thái Nguyên đã giúp đỡ và tạo điều kiện cho tôi trong suốt quá trình
học tập và nghiên cứu khoa học.
Nhân dịp này tôi cũng xin gửi lời cảm ơn chân thành tới gia đình, bạn bè
đã luôn động viên, cổ vũ, tạo mọi điều kiện thuận lợi cho tôi trong suốt quá
trình học tập.
Thái Nguyên, tháng 6 năm 2017
Người viết luận văn
Nguyễn Thị Hải Như
ii
Mục lục
Lời cảm ơn i
Mục lục i
Một số ký hiệu viết tắt 1
Mở đầu 1
5 1 Bài toán quy hoạch song tuyến tính
5 1.1 Đối ngẫu trong quy hoạch tuyến tính . . . . . . . . . . . . . .
8 1.2 Bài toán quy hoạch lõm với ràng buộc tuyến tính . . . . . . . .
8 1.2.1 Hàm lõm và tính chất . . . . . . . . . . . . . . . . . . .
10 1.2.2 Bài toán quy hoạch lõm . . . . . . . . . . . . . . . . .
11 1.3 Bài toán quy hoạch song tuyến tính . . . . . . . . . . . . . . .
12 1.3.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . .
13 1.3.2 Quan hệ với bài toán quy hoạch lõm . . . . . . . . . . .
15 1.3.3 Tính chất nghiệm của bài toán song tuyến tính . . . . .
16 1.4 Tìm nghiệm cực tiểu địa phương . . . . . . . . . . . . . . . . .
iii
2 Thuật toán giải quy hoạch song tuyến tính 19
2.1 Cơ sở lý thuyết của thuật toán . . . . . . . . . . . . . . . . . . 19
2.1.1 Biến đổi bài toán quy hoạch song tuyến tính . . . . . . 19
2.1.2 Điều kiện tối ưu của thuật toán . . . . . . . . . . . . . 23
2.2 Mô tả thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.1 Các bước của thuật toán . . . . . . . . . . . . . . . . . 25
2.2.2 Suy biến . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.3 Sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3 Cách tiếp cận siêu phẳng cắt . . . . . . . . . . . . . . . . . . . 34
2.4 Ví dụ minh họa thuật toán . . . . . . . . . . . . . . . . . . . . 36
Tài liệu tham khảo 46
1
Một số ký hiệu viết tắt R
Tập số thực hay đường thẳng thực.
Rn Không gian Euclid n chiều.
Rm×n Tập các ma trận thực cấp (m × n).
x ∈ C
x thuộc tâp C (x là một phần tử của tập C).
∅
Tập rỗng (Tập không chứa phần tử nào).
C ∪ D
Hợp của tập C và tập D.
C ∩ D
Giao của tập C và tập D.
C ⊂ D
C là tập con của tập D.
C ⊆ D
C là tập con (có thể bằng) của tập D.
xT y
Tích vô hướng cuả x và y.
x0, x1, x2, ......, xn
Các tọa độ của điểm hay thành phần của véctơ x
( cùng chỉ số dưới ).
x1, x2, x3
Liệt kê các véctơ có cùng số chiều (cùng chỉ số trên).
AT
Ma trận chuyển vị của ma trận A.
A−1
Ma trận nghịch đảo của ma trận A.
2
Mở đầu
Hàm f (x, y) được gọi là một hàm song tuyến tính (bilinear function) nếu
nó là hàm tuyến tính khi cố định véctơ biến x hay véctơ biến y ở một giá trị
f (x, y) = aT x + xT Qy + bT y,
cụ thể. Tổng quát, hàm song tuyến tính có dạng:
trong đó a, x ∈ Rn, b, y ∈ Rm và Q là ma trận cấp n × m. Có thể thấy hàm
song tuyến tính là một trường hợp riêng của hàm toàn phương và hàm song
tuyến tính nói chung không lồi, cũng như không lõm.
Bài toán cực tiểu một hàm song tuyến tính với các ràng buộc tuyến tính
đối với các biến x và biến y được gọi là một quy hoạch song tuyến tính (bilinear
programming problem). Như vậy, có thể xem quy hoạch song tuyến tính là một
bài toán quy hoạch toàn phương đặc biệt.
Quy hoạch song tuyến tính có nhiều ứng dụng đa dạng trong các bài toán
trò chơi ma trận có ràng buộc, bài toán bù tuyến tính và bài toán phân việc
3-chiều. Đáng chú ý là bài toán quy hoạch lõm, tuyến tính từng khúc và các
bài toán luồng trên mạng với phụ phí cố định (rất quen thuộc trong quản lý
các chuỗi cung ứng) cũng có thể giải nhờ dùng cách diễn đạt song tuyến tính
(xem [4]).
3
f (x, y) = aT x + xT Qy + bT y,
(BP )
min x∈X, y∈Y
Luận văn xét bài toán quy hoạch song tuyến tính, ký hiệu là (BP):
trong đó X, Y là các tập lồi đa diện, khác rỗng.
Có nhiều thuật toán khác nhau để giải (BP). Luận văn tìm hiểu và trình
bày một thuật toán cơ bản, nêu ở tài liệu [3] để giải bài toán.
Để hiểu rõ bài toán quy hoạch song tuyến tính và thuật toán sẽ trình bày,
luận văn nhắc lại một số kiến thức tối ưu có liên quan: đối ngẫu trong quy
hoạch tuyến tính, bài toán quy hoạch lõm và tính chất, bài toán tối ưu toàn
cục, ... Các kiến thức cơ bản về quy hoạch song tuyến sẽ được nêu ở chương 1
của luận văn.
Nội dung chính của luận văn là thuật toán [3] giải quy hoạch song tuyến
tính: các bước thuật toán, sự hội tụ của thuật toán và ví dụ minh họa thuật
toán. Các nội dung này sẽ được trình bày chi tiết ở chương 2 của luận văn.
Luận văn được viết dựa chủ yếu trên các tài liệu tham khảo [1] - [6] hiện
có và gồm hai chương:
Chương 1: Bài toán quy hoạch song tuyến tính nhắc lại các kiến thức
về đối ngẫu trong quy hoạch tuyến tính, bài toán quy hoạch lõm với ràng buộc
tuyến tính, khái niệm hàm lõm (hàm tựa lõm) và tính chất cơ bản của hàm
lõm. Tiếp đó, giới thiệu bài toán quy hoạch song tuyến tính, tính chất nghiệm
của bài toán và mối liên hệ với bài toán cực tiểu hàm lõm, tuyến tính từng
khúc. Cuối chương giới thiệu "thuật toán xuống núi" tìm nghiệm cực tiểu địa
phương của bài toán quy hoạch song tuyến tính và đưa ra ví dụ minh họa thuật
4
toán.
Chương 2: Thuật toán giải bài toán quy hoạch song tuyến tính
trình bày thuật toán được nêu ở tài liệu tham khảo [3] để giải bài toán quy
hoạch song tuyến tính. Thuật toán này biến đổi bài toán ban đầu về bài toán
tối ưu trên một tập không lồi và giải bài toán đó, dựa trên điều kiện tối ưu cần
và đủ đưa ra và chứng minh sự hội tụ về nghiệm đúng của bài toán quy hoạch
song tuyến tính ban đầu. Thuật toán trình bày được minh họa bằng ví dụ số
cụ thể.
5
Chương 1
Bài toán quy hoạch song tuyến tính
Chương này nhắc lại các kết quả về đối ngẫu trong quy hoạch tuyến tính,
bài toán quy hoạch lõm ràng buộc tuyến tính. Tiếp đó đề cập tới bài toán quy
hoạch song tuyến tính, tính chất nghiệm bài toán và mối liên hệ với bài toán
cực tiểu hàm lõm, tuyến tính từng khúc. Cuối chương nêu thuật toán tìm cực
tiểu địa phương của bài toán. Nội dung của chương được tham khảo chủ yếu
từ các tài liệu [5] - [6].
1.1 Đối ngẫu trong quy hoạch tuyến tính
• Dạng chuẩn tắc:
min (cid:8)f (x) = cT x : Ax (cid:62) b, x (cid:62) 0(cid:9) ,
A. Trong quy hoạch tuyến tính người ta hay xét hai dạng bài toán sau đây.
+. Trong bài toán này tập
Trong đó A ∈ Rm×n, b ∈ Rn, x (cid:62) 0 có nghĩa x ∈ Rn
ràng buộc D = {x ∈ Rn : Ax (cid:62) b, x (cid:62) 0} là một tập lồi đa diện.
6
• Dạng chính tắc:
min (cid:8)f (x) = cT x : Ax = b, x (cid:62) 0(cid:9) ,
trong đó A, b, c và x được xác định như ở trên. Trong bài toán này tập ràng
buộc D = {x ∈ Rn : Ax = b, x (cid:62) 0} cũng là một tập lồi đa diện. Có thể dễ
dàng chuyển từ dạng chuẩn tắc sang dạng chính tắc và ngược lại.
Trong các bài toán trên f(x) được gọi là hàm mục tiêu. Mỗi bất phương
xj ≥ 0, j = 1, ..., n, gọi là các ràng buộc không âm hay ràng buộc về dấu.
(cid:62) bi hay phương trình (Ax)i = bi gọi là một ràng buộc chính, trình (Ax)i
Véctơ (điểm) x ∈ D gọi là một nghiệm chấp nhận được hay một phương án.
Một phương án đạt cực tiểu của hàm mục tiêu f(x) gọi là một phương án tối
ưu hay một nghiệm tối ưu của bài toán. Mỗi bài toán quy hoạch tuyến tính đã
cho, gọi là bài toán gốc, luôn đi kèm với một bài toán quy hoạch tuyến tính
thứ hai, gọi là bài toán đối ngẫu. Hai bài toán này quan hệ mật thiết với nhau
và từ nghiệm tối ưu của bài toán này có thể suy ra nghiệm tối ưu bài toán kia
và ngược lại.
• Đối ngẫu của qui hoạch tuyến tính dạng chuẩn tắc (bài toán gốc)
B. Sau đây là hai dạng cặp bài toán đối ngẫu thường gặp.
min (cid:8)f (x) = cT x : Ax (cid:62) b, x (cid:62) 0(cid:9)
(P)
là bài toán qui hoạch tuyến tính (bài toán đối ngẫu):
max (cid:8)g (y) = bT y : AT y (cid:54) c, y (cid:62) 0(cid:9)
(Q)
• Đối ngẫu của qui hoạch tuyến tính dạng chính tắc (bài toán gốc):
( AT là ma trận chuyển vị của ma trận A ).
7
min (cid:8)f (x) = cT x : Ax = b, x (cid:62) 0(cid:9)
(P)
là bài toán qui hoạch tuyến tính (bài toán đối ngẫu):
max (cid:8)g (y) = bT y : AT y (cid:54) c(cid:9) .
(Q)
Dễ kiểm tra lại rằng lấy đối ngẫu của bài toán đối ngẫu ta được lại bài toán
gốc. Vì thế ta gọi (P) và (Q) là cặp bài toán qui hoạch tuyến tính đối ngẫu
nhau.
C. Các kết quả sau đúng cho cặp bài toán đối ngẫu (P), (Q) dạng bất kỳ.
Định lý 1.1.1. (Đối ngẫu yếu). Nếu x là một lời giải chấp nhận được của bài
f (x) = c1x1 + c2x2 + ... + cnxn (cid:62) g (y) = b1y1 + b2y2 + ... +
bmym, nghĩa là giá trị mục tiêu của một phương án gốc bất kỳ (bài toán min)
toán gốc (P) và y là một lời giải chấp nhận được của bài toán đối ngẫu (Q) thì
không nhỏ hơn giá trị mục tiêu của một phương án đối ngẫu bất kỳ (bài toán
max).
Định lý 1.1.2. (Đối ngẫu mạnh). Nếu một qui hoạch có nghiệm tối ưu thì qui
hoạch đối ngẫu của nó cũng có nghiệm tối ưu và hai giá trị tối ưu bằng nhau.
Các định lý trên suy ra các quan hệ sau giữa hai bài toán gốc và đối ngẫu
Định lý 1.1.3. (Định lý đối ngẫu cơ bản). Đối với một cặp bài toán qui hoạch
tuyến tính đối ngẫu nhau chỉ có một trong ba khả năng loại trừ nhau sau đây:
(a) Cả hai bài toán đều không có nghiệm chấp nhận được.
(b) Cả hai bài toán đều có nghiệm chấp nhận được. Khi đó, cả hai đều có
nghiệm tối ưu và giá trị tối ưu của hai hàm mục tiêu bằng nhau.
(c) Một bài toán có nghiệm chấp nhận được và bài toán kia không có nghiệm
8
chấp nhận được. Khi đó, bài toán có nghiệm chấp nhận được sẽ có giá trị tối
ưu vô cực ( +∞ hay −∞ tùy theo bài toán max hay min).
Quan hệ giữa cặp bài toán đối ngẫu nhau còn thẻ hiện ở định lý sau đây.
Định lý 1.1.4. (Định lý độ lệch bù). Một cặp nghiệm chấp nhận được x, y của
hai qui hoạch tuyến tính đối ngẫu nhau (P) và (Q) là cặp nghiệm tối ưu khi và
= 0, ∀i = 1, 2, ...., m ⇔ yT (Ax − b) = 0
yi
aijxj − bi
chỉ khi chúng nghiệm đúng các hệ thức: (cid:33)
= 0, ∀j = 1, 2, ...., m ⇔ xT (cid:0)c − AT y(cid:1) = 0
xj
cj −
aijyj
m (cid:80) i=1
(cid:32) n (cid:80) j=1 (cid:18) (cid:19)
1.2 Bài toán quy hoạch lõm với ràng buộc tuyến tính
1.2.1 Hàm lõm và tính chất
Trước khi phát biểu bài toán quy hoạch lõm, ta nhắc lại khái niệm hàm lõm
(hàm tựa lõm) trong Rn và một số tính chất cơ bản của hàm này.
f (λx + (1 − λ) y) (cid:62) λf (x) + (1 − λ) f (y) ∀x, y ∈ Rn, ∀λ ∈ [0, 1]
Định nghĩa 1.2.1. Hàm f: Rn → R gọi là lõm nếu:
Với n = 1, bất đẳng thức này có thể diễn tả như sau: dây cung nối hai điểm
bất kỳ trên đồ thị của hàm phải nằm dưới đồ thị của hàm nằm trong đoạn đó.
f (λx + (1 − λ) y) (cid:62) min {f (x) , f (y)} ∀x, y ∈ Rn, ∀λ ∈ [0, 1]
Định nghĩa 1.2.2. Hàm f: Rn → R gọi là tựa lõm nếu:
Bất đẳng thức trên có nghĩa là giá trị của hàm f tại một điểm bất kỳ trên đoạn
thẳng [x, y] không nhỏ hơn giá trị nhỏ nhất của hàm tại hai đầu mút của đoạn
9
thẳng đó.
Từ các định nghĩa trên cho thấy một hàm lõm là hàm tựa lõm, nhưng điều
ngược lại không chắc đúng. Ví dụ, f(x) = x3(x ∈ R) là hàm tựa lõm, nhưng
hàm này không là hàm lõm trên R. Như vậy lớp hàm tựa lõm rộng hơn lớp
hàm lõm.
Khác với hàm lồi, điểm cực tiểu địa phương của hàm lõm trên (trên một
tập lồi) không nhất thiết là điểm cực tiểu toàn cục. Nói chung, thông tin địa
phương không đủ để xác định điểm cực tiểu toàn cục của một hàm lõm.
Định lý 1.2.3. Với mọi hàm lõm f: Rn → R ta có các kết luận sau:
a) Cực tiểu của f trên một đoạn thẳng đạt tại một đầu mút của đoạn đó.
b) Nếu f hữu hạn và bị chặn dưới trên một nửa đường thẳng thì cực tiểu của
f trên nửa đường thẳng này đạt tại điểm gốc của nó.
c) Nếu f hữu hạn và bị chặn dưới trên một tập afin thì f bằng hằng số trên
tập afin đó.
Định lý 1.2.4. Giả sử C ⊂ Rn là một tập lồi và f: C ⊂ Rnlà hàm lõm. Nếu
f(x) đạt cực tiểu trên C tại điểm trong tương đối x∗ của C ( x∗ ∈ ri C ) thì
f(x) bằng hằng số trên C. Tập Argminx∈Cf (x) là hợp của một số diện của C.
trong đó V(C) là tập các điểm cực biên của C, nghĩa là nếu cực tiểu của f(x)
đạt được trên C thì cực tiểu cũng đạt được trên V(C).
Định lý 1.2.5. Giả sử C là tập lồi, đóng và f: C → R là hàm lõm. Nếu C
không chứa đường thẳng nào và f(x) bị chặn dưới trên mọi nửa đường thẳng
trong C thì
10
inf {f (x)
: x ∈ C} = inf {f (x)
: x ∈ V (C)} ,
trong đó V(C) là tập các điểm cực biên của C, nghĩa là nếu cực tiểu của f(x)
đạt được trên C thì cực tiểu cũng đạt được trên V(C).
Hệ quả 1.2.6. Cho hàm lõm f(x) trên tập lồi đa diện D, không chứa đường
thẳng nào. Khi đó, hoặc f(x) không bị chặn dưới trên một cạnh vô hạn nào đó
của D, hoặc f(x) đạt cực tiểu tại một đỉnh nào đó của D.
Hệ quả 1.2.7. Hàm lõm f(x) trên tập lồi compac C đạt cực tiểu tại một điểm
cực biên của C.
Nhận xét 1. Thực ra, tính chất nêu trong Hệ quả 1.2.7 cũng đúng cho lớp
hàm rộng hơn. Cụ thể là các hàm tựa lõm, nghĩa là các hàm f : Rn → [−∞, +∞]
sao cho các tập mức trên Lβ = {x ∈ Rn : f (x) (cid:62) β} là lồi với mọi β ∈ R.
Cũng có thể chứng minh được rằng cận dưới của một họ hàm tựa lõm là hàm
tựa lõm, nhưng tổng của hai hàm tựa lõm không chắc là hàm tựa lõm.
Nhận xét 2. Do hàm lồi là đối của hàm lõm nên các kết luận trên đây
(phát biểu cho hàm lõm) cũng đúng cho hàm lồi chỉ cần thay cực tiểu bởi cực
đại và bị chặn dưới bằng bị chặn trên.
1.2.2 Bài toán quy hoạch lõm
(Cực tiểu hàm lõm hay cực đại hàm lồi)
Xét bài toán tối ưu có dạng:
(CP) min {f (x) : x ∈ C},
trong đó f(x) là hàm lõm (hay tựa lõm), C là tập lồi đóng, chẳng hạn
11
C = {x : g(x) (cid:54) 0} với g(x) là một hàm lồi. Đặc biệt quan trọng là trường hợp
C là tập lồi đa diện. Khi đó bài toán được gọi là một quy hoạch lõm với ràng
buộc tuyến tính.
Quy hoạch tuyến tính và quy hoạch lồi thuộc lớp bài toán một cực trị ( hàm
mục tiêu của bài toán có nhiều nhất một giá trị cực tiểu ). Một bài toán sở dĩ
có nhiều giá trị cực tiểu khác nhau là do nó không lồi. Nói chung, một bài toán
càng có nhiều yếu tố không lồi thì càng khó. Bài toán quy hoạch lõm thuộc lớp
bài toán như thế.
Quy hoạch lõm vừa nêu trên là bài toán cơ bản của tối ưu toàn cục, vì tính
phổ biến của nó và vì nhiều bài toán tối ưu toàn cục quy được về nó hoặc dựa
ít nhiều trên phép giải của nó. Mục tiếp sau sẽ chỉ ra rằng bài toán quy hoạch
song tuyến tính có thể phát biểu như một bài toán quy hoạch lõm với hàm mục
tiêu lõm, tuyến tính từng khúc và với các ràng buộc tuyến tính.
1.3 Bài toán quy hoạch song tuyến tính
Định nghĩa 1.3.1. Hàm f(x, y) được gọi là một hàm song tuyến tính ( bilinear
funcyion ) nếu nó là hàm tuyến tính khi cố định véctơ x hay véctơ y ở một giá
f (x, y) = aT x + xT Qy + bT y,
trị cụ thể. Tổng quát, hàm song tuyến tính có dạng:
trong đó a, x ∈ Rn, b, y ∈ Rm và Q là ma trận cấp n × m.
Dễ dàng thấy rằng các hàm song tuyến tính tạo nên một lớp con các hàm
toàn phương.
12
1.3.1 Phát biểu bài toán
Ta gọi bài toán tối ưu với hàm mục tiêu song tuyến tính và các hàm ràng
buộc song tuyến tính là bài toán song tuyến tính (bilinear problem) và các bài
toán này có thể xem như một lớp con của quy hoạch toàn phương (quadratic
programming).
Quy hoạch song tuyến tính có nhiều ứng dụng đa dạng trong các trò chơi
ma trận có ràng buộc, bài toán bù và bài toán phân việc 3 - chiều, Markovian.
Nhiều bài toán nguyên 0 - 1 có thể phát biểu như các bài toán song tuyến tính.
Bài toán quy hoạch lõm tuyến tính từng khúc và bài toán luồng trên mạng với
phụ phí cố định, rất quen thuộc trong quản lý các chuỗi cung ứng, cũng có thể
giải bằng cách dùng cách diễn đạt song tuyến tính.
Tuy có nhiều dạng bài toán quy hoạch song tuyến tính, song phần lớn các
bài toán thực tiễn gồm hàm mục tiêu song tuyến tính và với các ràng buộc
tuyến tính và các kết quả lý thuyết được đưa ra trong trường hợp này. Trong
luận văn chúng tôi xét bài toán song tuyến tính sau đây, ký hiệu bài toán là
f (x, y) = aT x + xT Qy + bT y,
(BP )
min x∈X, y∈Y
BP:
trong đó X, Y là các tập lồi đa diện, khác rỗng. Bài toán BP còn được biết
với tên gọi bài toán song tuyến tính với miền ràng buộc rời nhau , bởi vì tính
chấp nhận của x(y) độc lập với việc chọn véctơ y(x).
13
1.3.2 Quan hệ với bài toán quy hoạch lõm
Dưới đây ta sẽ đề cập tới một số kết quả lý thuyết về sự tương đương giữa
= aT x + miny∈Y
bài toán song tuyến tính và bài toán cực tiểu lõm.
Cho V (x) và V (y) lần lượt là tập đỉnh của X và Y , và g(x) = miny∈Y f (x, y) (cid:8)xT Qy + bT y(cid:9). Trong đó miny∈Y f (x, y) là bài toán tuyến
tính. Bởi vì nghiệm của bài toán tuyến tính đạt tại đỉnh của miền chấp nhận
g(x) = miny∈Y f (x, y) = miny∈V (Y ) f (x, y). Sử dụng ký
được nên:
hiệu này, bài toán BP có thể phát biểu lại thành:
g(x)
min x∈X,y∈Y
f (x, y) = min x∈X
f (x, y)} = min x∈X
{ min y∈Y
{ min y∈V (Y )
f (x, y)} = min x∈X Nhận xét rằng tập của Y là hữu hạn, cho mỗi y ∈ Y , f (x, y) là môt hàm
(1)
tuyến tính theo x; vì thế hàm g(x) là hàm lõm tuyến tính từng khúc. Từ nhận
xét này cho thấy BP tương đương với bài toán cực tiểu hàm lõm tuyến tính
từng khúc với ràng buộc tuyến tính.
Ngược lại, có thể chỉ ra rằng bất kì bài toán cực tiểu hàm mục tiêu lõm,
tách biến và tuyến tính từng khúc có thể quy được về bài toán quy hoạch song
tuyến tính. Để thiết lập mối quan hệ này, ta xét bài toán tối ưu dưới đây:
Φi(xi)
min x∈X
(2) (cid:80) i
Trong đó X là tập hợp các vectơ tùy ý khác rỗng, gồm các vectơ chấp nhận
được, và Φi(xi) là hàm lõm, tuyến tính từng khúc chỉ của một biến xi tức là
14
i xi + s1 c1
i (= Φ1
i , λ1 i
(cid:1)
i (xi)), xi ∈ (cid:2)λ0 i (xi)), xi ∈ (cid:2)λ0
i , λ2 i
i xi + s2 c2
i (= Φ2
Φi(xi) =
...............................................
(cid:1)
i xi + sni cni
i (= Φni
, λni i
i
(cid:1)
i > c2
i > ... > cni
i (xi)), xi ∈ (cid:2)λni−1 i . Cho Ki = {1, 2, ..., ni}. Hàm có thể viết lại như sau:
Với c1
i (xi)(cid:9) = min
i xi + sk i
k∈Ki
Φi(xi) = min k∈Ki Lập bài toán quy hoạch song tuyến tính sau đây:
(3) (cid:8)Φk (cid:8)ck (cid:9) .
(ck
Φk
i xi + sk
i (xi)yk
i )yk i .
min x∈X,y∈Y
f (x, y) = (cid:80) i
(cid:80)
i = (cid:80) i i |Ki|. Chứng minh định lý sau đây được suy trực tiếp từ
(4) (cid:80) k∈Ki (cid:80) k∈Ki
Trong đó Y = [0, 1]
phương trình (3).
Định lý 1.3.2. Nếu (x∗, y∗) là một nghiệm tói ưu của bài toán (4) thì x∗ là
một nghiệm tối ưu của bài toán (2) Chú ý là không đòi hỏi X là một đa diện
lồi. Nếu X là một đa diện lồi thì cấu trúc của bài toán (4) là tương đương với
(BP).
Hơn nữa, ta có thể chỉ ra rằng có thể đưa bất kì bài toán cực tiểu hàm lõm
toàn phương về bài toán quy hoạch song tuyến tính. Nói riêng, xét bài toán tối
ưu sau đây :
Φ(x) = 2aT x + xT Qx.
min x∈X
(5)
Trong đó Q là một ma trận bán đối xứng, nửa xác định âm. Ta xây dựng bài
toán quy hoạch song tuyến tính như sau:
f (x, y) = aT x + aT x + xT Qy.
min x∈X,y∈Y
(6)
Trong đó Y = X.
15
Định lý 1.3.3. Nếu x∗ là một nghiệm của bài toán (5) thì (x∗, x∗) là một
nghiệm của bài toán (6). Nếu ((cid:98)x, (cid:98)y) là một nghiệm của bài toán (6) thì (cid:98)x và (cid:98)y là các nghiệm của bài toán (5)
1.3.3 Tính chất nghiệm của bài toán song tuyến tính
Mục trước cho thấy rằng BP tương đương với bài toán cực tiểu hàm lõm
tuyến tính từng khúc. Mặt khác, ta lại biết rằng cực tiểu của hàm lõm trên
một tập lồi đa diện luôn đạt tại một đỉnh. Định lý sau đây được suy ra từ nhận
xét này:
(x∗, y∗) với mỗi x∗ ∈ V (X) và y∗ ∈ V (Y )
Định lý 1.3.4. Nếu X và Y bị chặn thì tồn tại một nghiệm tối ưu của BP là
Giả sử (x∗, y∗) là một nghiệm của (BP). Khi cố định x = x∗, Bài toán BP
trở thành bài toán tuyến tính và y∗ là một nghiệm của bài toán nhận được. Từ
tính đối xứng của bài toán, kết quả tương tự cũng đúng khi cố định y = y∗.
Định lý sau đây là một điều kiện cần của tối ưu.
Định lý 1.3.5. Nếu (x∗, y∗) là một nghiệm của bài toán BP, thì
minx∈X f (x, y∗) = f (x∗, y∗) = minx∈X f (x∗, y).
(7)
Tuy nhiên, (7) không phải là một điều kiện đầy đủ. Trong thực tế nó đảm
bảo tối ưu địa phương của (x∗, y∗) theo một yêu cầu bổ sung. Cụ thể y∗ là một
nghiệm tối ưu nhất của bài toán minx∈X f (x, y∗). Từ đó suy ra rằng f (x∗, y∗)
V (y), y (cid:54)= y∗, f (x∗, y∗) < f (x, y) trong lân cận Uy đủ nhỏ của điểm x∗. Đặt:
< f (x∗, y), ∀y ∈ V (y), y (cid:54)= y∗. Do hàm f(x, y) liên tục nên với mọi ∀y ∈
16
U =
Uy∗
∩ y∈V (y),y(cid:54)=y∗
Khi đó f (x∗, y∗) < f (x, y), ∀x ∈ U , ∀y ∈ V (Y ), y (cid:54)= y∗. Cuối cùng để chú
ý rằng Y là một đa diện lồi và mỗi điểm của Y có thể biểu diễn dưới dạng một
∀y ∈ Y , điều này chứng tỏ cho định lý sau.
tổ hợp lồi của các đỉnh của Y. Từ đó suy ra rằng f (x∗, y∗) < f (x, y), ∀x ∈ U ,
Định lý 1.3.6. Nếu (x∗, y∗) thỏa mãn điều kiện (7) và y∗ là nghiệm duy nhất
của bài toán miny∈Y f (x∗, y∗) thì (x∗, y∗) là nghiệm tối ưu địa phương của BP.
Nhớ rằng BP tương đương với bài toán cực tiểu hàm lõm, tuyến tính từng
khúc. Với các giả thiết của định lý 5 có thể chỉ ra rằng x∗ cũng là cực tiểu địa
phương của hàm g(x).
1.4 Tìm nghiệm cực tiểu địa phương
Mục này đề cập tới phương pháp tìm một nghiệm của bài toán song tuyến
tính. Do BP tương đương với bài toán cực tiểu hàm lõm tuyến tính từng khúc,
nên có thể dùng bất kỳ thuật toán giải bài toán sau để giải bài toán trước. Nói
riêng, ta có thể dùng thuật toán siêu phẳng cắt đã đề xuất cho hai bài toán
đó. Tuy nhiên, cấu trúc đối xứng của bài toán BP cho phép xây dựng các lát
cắt hiệu quả hơn. Trong [4] Kono H. bàn về thuật toán hội tụ tới nghiệm thỏa
mãn điều kiện (7) và sau đó đề ra thuật toán siêu phẳng cắt tìm nghiệm tối ưu
toàn cục của bài toán. Giả sử X và Y bị chặn. Thuật toán 1, còn gọi là "thủ
tục xuống núi", xuất phát từ véctơ ban đầu y0 và liên tiếp giải hai bài toán
tuyến tính LP.Bài toán LP thứ nhất nhận được bằng cách cố định véctơ y ở
17
giá trị ym−1. Lời giải của bài toán này được dùng để cố định giá trị của véctơ
x và xây dựng bài toán LP thứ hai. Nếu f (xm, ym−1) (cid:54)= f (xm, ym) thì tiếp tục
giải các bài toán bằng cách cố định véctơ y ở giá trị ym. Nếu tiêu chuẩn dừng
được thỏa mãn thì có thể chỉ ra rằng véctơ (xm, ym) thỏa mãn điều kiện (7).
f (xm, ym−1) ≥ f (xm, ym) suy ra rằng thuật toán hội tụ sau hữu hạn lần lặp
Thêm vào đó, nhận xét rằng V(X) và V(Y) là hữu hạn. Từ đó và từ sự kiện là
Thuật toán 1. Thủ tục xuống núi.
Bước 1: Giả sử y0 ∈ Y là một nghiệm chấp nhận được ban đầu và m ←1
Bước 2: Giả sử xm = arg minx∈X (cid:8)f (x, ym−1)(cid:9) và ym = arg miny∈Y {f (xm, y)}
Bước 3: Nếu f (xm, ym−1) = f (xm, ym) thì dừng. Trái lại, m ← m + 1 và
quay lại Bước 1.
Giả sử (x∗, y∗) là nghiệm nhận được theo thuật toán 1. Với giả thiết rằng
đỉnh x∗ không suy biến, ta ký hiệu D là tập các hướng dj dọc theo cạnh của
X đi từ điểm x∗. Nhớ rằng g(x) = min y ∈ Y f (x, y) là một hàm lõm. Để xây
g (x∗ + θjdj) ≥ f (x∗, y∗) − ε, nghĩa là
θj = arg max {θj : g (x∗ + θjdj) ≥ f (x∗, y∗) − ε}
dựng lát cắt đúng cho mỗi hướng dj ta tìm giá trị lớn nhất của θj sao cho
∆1
x|
C −1 (x − x∗) ≥ 1
,
x =
Trong đó ε là một số dương đủ nhỏ. Đặt C = {d1, d2, ..., dn}, (cid:26) (cid:27) (cid:17)T
, ...., 1 θn
(cid:16) 1 θ1
x. Nếu X1 = ∅ thì
f (x, y) ≥ f (x∗, y∗) − ε,
min x∈X,y∈Y
và X1 = X ∩ ∆1
và (x∗, y∗) là một nghiệm ε tối ưu toàn cục của bài toán. Nếu X1 = ∅ thì ta có
thể thay X bởi tập X1, nghĩa là xét bài toán tối ưu
18
f (x, y)
min x∈X,y∈Y
và chạy Thuật toán 1 để tìm một nghiệm tốt hơn. Tuy nhiên, do cấu trúc đối
xứng của bài toán nên có thể áp dụng một thủ tục tương tự để xây dựng một
y là nửa không gian tương ứng và Y1 = Y ∩ ∆1 y.
lát cắt đối với tập Y. Ký hiệu ∆1
f (x, y)
min x∈X,y∈Y
Bằng cách đổi mới cả hai tập, nghĩa là xét bài toán tối ưu
thuật toán siêu phẳng cắt (xem Thuật toán 2) có thể cho phép tìm nghiệm
toàn cục của bài toán với số lần lặp ít hơn.
Thuật toán 2 . Thuật toán siêu phẳng cắt.
Bước 1: Áp dụng Thuật toán 1 tìm véctơ (x∗, y∗) thỏa mãn hệ thức (7).
Bước 2: : Dựa vào nghiệm (x∗, y∗) tính các lát cắt thích hợp và xây dựng
các tập X1 và Y1.
Bước 3: Nếu X1 (cid:54)= ∅ hoặc Y1 (cid:54)= ∅ thì (x∗, y∗) là một nghiệm ε - tối ưu
toàn cục. Trái lại, X ← X1 và Y ← Y1 và quay lại Bước 1.
Kết luận chương 1
Chương này nhắc lại các kiến thức cơ bản liên quan tới bài toán quy hoạch song
tuyến tính, như quan hệ đối ngẫu trong quy hoạch tuyến tính, bài toán cực
tiểu hàm lõm với ràng buộc tuyến tính, bài toán quy hoạch song tuyến tính,
tính chất nghiệm của bài toán và thuật toán tìm nghiệm cực tiểu địa phương
của bài toán quy hoạch song tuyến tính.
19
Chương 2
Thuật toán giải quy hoạch song tuyến
tính
Chương này trình bày thuật toán được nêu ra ở tài liệu tham khảo [3], để
giải bài toán quy hoạch song tuyến tính. Thuật toán biến đổi bài toán ban đầu
về bài toán tối ưu trên một tập không lồi và đề xuất thuật toán giải bài toán
đó, dựa trên tiêu chuẩn tối ưu đưa ra và chứng minh sự hội tụ về nghiệm đúng
của bài toán song tuyến tính ban đầu. Thuật toán trình bày được minh họa
bằng ví dụ số cụ thể. Nội dung của chương được tham khảo chủ yếu từ các tài
liệu [3] và [6].
2.1 Cơ sở lý thuyết của thuật toán
2.1.1 Biến đổi bài toán quy hoạch song tuyến tính
n(cid:48) - chiều y sao cho:
Ta xét bài toán quy hoạch song tuyến tính: tìm véctơ n - chiều x và véctơ
20
cT x + xT QT y + dT y → max,
Ax ≤ a, BT y ≤ b,
x ≥ 0, y ≥ 0
(2.1)
trong đó A là ma trận m × n , B là ma trận m(cid:48) × n(cid:48), QT là ma trận n(cid:48) × n(cid:48), a
X = {x : Ax ≤ a, x ≥ 0} và Y = (cid:8)y : BTy ≤ b, y ≥ 0(cid:9)
và b là các véctơ có số chiều n, n(cid:48), m và m(cid:48) tương ứng. Giả sử:
là các tập khác rỗng và bị chặn.
Theo Định lý 1.3.4, tập tất cả các nghiệm tối ưu của bài toán (2.1) chứa ít
nhất một phần tử (x∗, y∗) sao cho x∗ là một đỉnh của X và y∗ là một đỉnh của
Y.
cT x + max
(d + Qx)T y : BT y ≤ b, y ≥ 0
→ max
Ax ≤ a, x ≥ 0
Bài toán (2.1) có thể viết lại thành: (cid:110) (cid:111)
Từ lý thuyết đối ngẫu của quy hoạch tuyến tính trực tiếp suy ra rằng (2.1)
cT x + min bT u → max,
tương đương với bài toán tìm véctơ n chiều x và véctơ m(cid:48) chiều u sao cho:
Ax ≤ a, Bu ≥ d + Qx,
x ≥ 0, y ≥ 0,
(2.2)
Sau đây thay cho bài toán (2.1), ta giải trực tiếp bài toán (2.2). Trước hết
ta xét một số tính chất hình học của nghiệm bài toán (2.2) và nêu điều kiện tối
ưu cần và đủ. Sau đó, ở mục 2.2 sẽ trình bày thuật toán tìm nghiệm tối ưu của
bài toán (2.2) và xét sự hội tụ của thuật toán. Mục 2.3 trình bày biến thể siêu
phẳng cắt của thuật toán. Ở mục 2.3 đưa ra ví dụ số minh họa thuật toán. Ta
21
P = {(x, u) : Ax ≤ a, Bu ≥ d + Qx, (x, u) ≥ 0} . Λ = (cid:8)(x, u) : (x, u) ∈ P, bTu ≤ bTu(cid:48), (x, u(cid:48)) ∈ P(cid:9) .
sẽ sử dụng các ký hiệu sau:
Bài toán (2.2) bây giờ có thể viết lại thành:
max{cTx + bTu : (x, u) ∈ Λ}.
(2.3)
Hàm mục tiêu của bài toán (2.3) là tuyến tính, nhưng tập ràng buộc của
bài toán nói chung là một tập không lồi. Hơn nữa, tập nghiệm tối ưu của bài
toán có thể không liên thông. Điều này có thể thấy rõ như vẽ ở Hình 1.1, trong đó (cid:8)(cid:0)x1, y1(cid:1) , (cid:0)x2, y2(cid:1)(cid:9) là tập nghiệm tối ưu của bài toán.
Tuy nhiên, tập Λ có một số tính chất đặc biệt được nêu dưới đây:
Bổ đề 2.1.1. U (x) = {u : Bu ≥ d + Qx, u ≥ 0} (cid:54)= ∅ với mọi x ∈ Rn
Chứng minh. Do Y = {y : BTy ≥ b, y ≥ 0} khác rỗng và bị chặn nên giá trị
(d + Qx)T y : y ∈ Y
(cid:110) (cid:111) max là bị chặn. Từ đó, theo lý thuyết đối ngẫu trong
quy hoạch tuyến tính, tập ràng buộc của bài toán đối ngẫu tương ứng là khác
rỗng, tức U(x) (cid:54)= ∅ với mọi x ∈ Rn .
Bổ đề 2.1.2. Λ là hợp của một số diện của P
Chứng minh. Trước hết ta muốn chỉ ra rằng nếu một diện F của P mà chứa
Λ. Rõ ràng điều này đúng nếu F là diện thứ nguyên 0. Bây giờ giả sử F là diện
một điểm thuộc Λ ở phần trong tương đối của F thì toàn bộ diện F nằm trong
thứ nguyên d ≥ 1 và trong phần trong của F có chứa điểm (x0, u0) ∈ Λ . Giả
sử (x1, u1) là điểm tùy ý trong F, khi đó tồn tại điểm (x2, u2) ∈ F sao cho:
22
(cid:0)x0, u0(cid:1) = λ (cid:0)x1, u1(cid:1) + (1 − λ) (cid:0)x2, u2(cid:1) , 0 < λ < 1.
Cho điểm bất kỳ
(cid:0)x1, u(cid:1) ∈ P , xét: (cid:0)x0, u∗(cid:1) = λ (cid:0)x1, u(cid:1) + (1 − λ) (cid:0)x2, u2(cid:1)
bTu0 = λbTu1 + (1 − λ)bTu2 ≤ bTu∗ = λbTu + (1 − λ) bT u2
Bởi vì (x0, u0) ∈ Λ cho nên:
và do đó bTu1 ≤ bT u, điều này kéo theo (x1, u1) ∈ Λ . Chứng minh bổ để dược
hoàn thành là do sự kiện mọi điểm trong P đều chứa trong tập các phần trong
tương đối của một diện nào đó của P.
Định lý 2.1.3. Tập hợp Λ là liên thông
Chứng minh. Giả sử Λ không liên thông, thì tồn tại hai tập hợp đóng Λ1 và Λ2
sao cho Λ = Λ1 ∪ Λ2 và Λ1 ∩ Λ2 = ∅. Tính đóng của Λ1 và Λ2 là do tập Λ là
tập đóng, bởi vì Λ là hợp của một số diện của P . Giả sử X1 và X2 là hai hình
chiếu của Λ1 và Λ2 trên không gian các biến x. Do hình chiếu của tập đóng là
tập đóng nên X1 và X2 là các tập đóng. Vì thế, do X là tập liên thông nên tồn
tại điểm x ∈ X sao cho x ∈ X1 ∩ X2. Do đó có thể tìm thấy hai điểm thuộc Λ
(x,u1) ∈ Λ1 , (x,u2) ∈ Λ2
với
Λ. Do đó toàn bộ đoạn thẳng nối (x,u1) với (x,u2) nằm trong Λ. Điều này trái
Hai điểm thuộc tập (cid:8)(x, u) : bT u = minu(cid:48)∈U (x) bT u(cid:48)(cid:9) lồi và liên thông trong
với Λ1 và Λ2 rời nhau. Chứng minh được hoàn thành.
Từ định lý trên đây suy ra rằng hai đỉnh bất kỳ của P mà thuộc Λ sẽ được
23
nối với nhau bằng một đường đi nằm trong Λ. Tuy nhiên tính chất này trên
thực tế không được dùng đến trong quá trình xây dựng thuật toán sẽ trình bày.
2.1.2 Điều kiện tối ưu của thuật toán
Trong mục này phát biểu và chứng minh định lý về điều kiện cần và đủ để
một điểm thuộc P là tối ưu. Sau đó nêu ra điều kiện đủ cái biên phục vụ cho
mục đích tính toán.
Định lý 2.1.4. Cho (x,u) ∈ Λ, với z = cT x + bT u, (x,u)là một nghiệm tối
ưu của bài toán (1.1) khi và chỉ khi với mỗi x ∈ X có tồn tại u sao cho:
(2.1) Bu ≥ d + Qx, -bT u ≥ - z + cT x
Chứng minh. (→) Phần chứng minh này được trực tiếp suy ra từ Bổ đề 2.1.1
và từ (x,u) là tối ưu.
(←) Giả sử (2.1) chấp nhận được với mỗi x ∈ X và ((cid:98)x,(cid:98)u) là một nghiệm tối ưu (cid:98)u (cid:54) bT u∗. Từ của (1.1). Với ((cid:98)x,u∗) là một nghiệm của (1.2). Từ ((cid:98)x,(cid:98)u) ∈ Λ, bT tính tối ưu cuả ((cid:98)x,(cid:98)u) ∈ Λ, suy ra cT (cid:98)u ≥ z = cT x + bT u, và bởi tính khả thi của ((cid:98)x,u∗)z ≥ cT (cid:98)u ≥ bT u∗. Do đó bT (cid:98)u = bT u∗ và (cid:98)x + bT u∗ = cT x + bT u. Từ đó ta có (x,u) là một nghiệm tối (cid:98)u = cT cT
(cid:98)x + bT (cid:98)x + bT u∗; suy ra bT
(cid:98)x + bT
ưu.
B
d
Q
B =
d =
Q =
Giả sử V = (cid:8)x1, x2, ..., xk(cid:9) là tập hữu hạn các điểm thuộc X. Xác định
−bT
−z(V )
cT
, ,
trong đó z(V) = max {cT xi + bT ui : xi ∈ V, (xi, ui) ∈ Λ}.
24
Ta đặt S(V) = (cid:8)x|∃u ≥ 0 : Bu ≥ d(V ) + Qx(cid:9). Bây giờ ta có thể phát biểu
Λ, U chứa một nghiệm tối ưu của (1.1) khi và chỉ khi với mỗi x ∈ X có tồn tại
lại Định lý 2.1.4 như sau. Định lý 2.1.4a Cho V = (cid:8)x1, x2, ..., xk(cid:9) ⊆ X và U = (cid:8)(cid:0)x1, u1(cid:1) , ..., (cid:0)xk, uk(cid:1)(cid:9) ⊆
Bu ≥ d (V ) + Qx, u ≥ 0
u sao cho
tức là S(V ) ⊇ X. Tiêu chuẩn tối ưu này đã được dùng trong thuật toán trình
bày trong luận văn để kiểm tra xem X có nằm trong S(V) không. Đó là điều
kiện cần và đủ của tối ưu của định lý trên đây. Tính chất hiển nhiên của S(V)
là tính đơn điệu (nghĩa là S (V(cid:48)) ⊇ S (V) mỗi khi V(cid:48) ⊇ V làm cho S(V) dễ
được xử lý xét theo quan điểm thuật toán. Tuy nhiên có một tập khác với các
R (V ) =
λiwi
k (cid:80) x : ∃λi ≥ 0, d (V ) + Qx ≤ i=1 = d (cid:0)(cid:8)xi(cid:9)(cid:1). Rõ ràng R (V(cid:48)) ⊇ R (V) nếu V(cid:48) ⊇ V. Định
i Với wi = d
i + Q
i , d
tính chất tương tự. Đó là: (cid:26) (cid:27)
lý sau đây chỉ ra rằng R(V ) ⊇ X là điều kiện đủ của tối ưu.
Bổ đề 2.1.5. Với mỗi x ∈ R(V ) tồn tại u ≥ 0 sao cho Bu ≥ d (V ) + Qx
Chứng minh. Từ Bổ đề 2.1.1. và định nghĩa của z(V) suy ra tồn tại ui > 0 sao
d (V ) + Qx∗ ≤
i wi, λ∗
k (cid:80) i=1
cho Bui ≥ wi, i = 1, ... , k. Cho x∗ và ≥ 0 sao cho:
d (V ) + Qx∗ ≤
λ∗ i Bui = B
i ui = Bu∗, λ∗
k (cid:80) i=1
k (cid:80) i=1
ta suy ra
i=1λ∗
i ui ≥ 0
trong đó u∗ = (cid:80) k
25
Định lý 2.1.6. Cho một tập Cho tập V = {x1, ...., xk} là các điểm thuộc X
R(V) ⊆ X → z(V) = max {cT x + bT u |(x,u) ∈ Λ}
Chứng minh. Suy ra từ Định lý 2.1.4.a và bổ đề trước đó
Chúng ta thấy rằng R(V) ⊆ X, khi đó V chứa tất cả các đỉnh của X. Từ
∈ I }, nếu tồn tại λi ≥ 0, i ∈ I sao cho λiωi > 0, thì R(V) ⊆ X.Do có thể dùng
đó dùng R(V) thay cho V trong các thuật toán. Hơn nữa với V = {xi ∈ X | i
i như thế, nên dùng
Pha I trong quy hoạch tuyến tính để kiểm tra sự tồn tại λ∗
R(V) có thể trình bày ngắn gọn thuật toán
2.2 Mô tả thuật toán
Mục này trình bày thuật toán giải bài toán (2.2). Thuật toán dựa trên điều
kiện tối ưu nêu ở Định lý 2.1.4a. Ở mỗi vòng lặp của thuật toán một đỉnh mới
của X được tìm thấy cùng với một điểm tương ứng trong Λ và giá trị hàm mục
tiêu được tính. Sau đó tập lồi đa diện T được xây dựng sao cho tập đã cho V
các đỉnh của X đã được khám phá, giao của nó với X chứa trong S(V). Thuật
toán dừng khi có điều kiện X ⊆ T , điều này tương ứng với điều kiện nói ở Định
lý 2.1.4.a. Ở mục 2.2 giới thiệu một biến thể khác của thuật toán này. Nó dựa
trên cùng các công cụ toán học và sử dụng cách tiếp cận siêu phẳng cắt.
2.2.1 Các bước của thuật toán
Bước 0. . Lấy trong S một đỉnh không suy biến x0, tức là đỉnh có đúng n
đỉnh kề x1, x2, . . . , xn. (Giả thiết này đối với x0 được đưa ra để làm đơn giản
26
cách trình bày và ở mục tiếp sau nó sẽ được loại bỏ). Với mỗi xi ∈ X, ta gọi vi
là véc tơ đơn vị xác định nửa đường thẳng xuất phát từ x0 và đi qua xi. Đặt V = (cid:8)x0, x1, . . . , xn(cid:9), ω = (cid:8)v1, . . . , vn(cid:9) và ∆ = {ω} . Tiến tới bước 1
Bước 1. Nếu ∆ = ∅ thì dừng thuật toán và z(V) là giá trị tối ưu của hàm hàm mục tiêu. Trái lại, chọn một tập ω = (cid:0)vi1, ..., vin(cid:1) trong D và chuyển sang
Bước 2.
θij = max (cid:8)θij : x0 + θijvij ∈ S (V )(cid:9) và chuyển sang Bước 3.
Bước 2. Với mỗi j = 1, . . . , n, giải quy hoạch tuyến tính để tìm:
n) là nghiệm tối ưu cực biên của quy hoạch tuyến
1, ..., λ∗
Bước 3. Tìm (λ∗
tính
n (cid:80) j=1
x0 +
λijvij ∈ X và chuyển sang Bước 4.
n (cid:80) j=1
(cid:0)1/θij (cid:1)λij → max
≤ 1 thì loại bỏ ω ra khỏi ∆ và trở lại Bước
n (cid:80) j=1
Bước 4. a) Nếu (cid:0)1/θij (cid:1)λ∗ ij
1.
vij . Thêm xq vào V và đổi mới giá trị
j=1λ∗ ij
> 0, tạo ra một tập bằng cách thay vq trong ω cho, sau
b) Trái lại, đặt xq = x0 + (cid:80) n
z(V). Với mọi j với λ∗ ij
đó thay ω trong ∆ bằng các tập mới này. Quay trở lại Bước 1.
Nhận xét 1. Để tính z(V) ở Bước 0, với mỗi i = 0, 1, . . . , n, ta giải một
min (cid:8)bTu : u ∈ U (cid:0)xi(cid:1)(cid:9)
bài toán tuyến tính:
và nhận được một nghiệm tối ưu gốc ui và một nghiệm tối ưu đối ngẫu yi. Sau
đó véctơ (xk, yk), k = {0, 1, . . . , n}, được chọn sao cho:
27
cTxk + bTuk = max (cid:8)cTxi + bTui : i = 0, 1, . . . , n(cid:9) = z (V) ,
và được lưu giữ làm nghiệm tối ưu hiện có. Trong quá trình thực hiện thuật
toán, mỗi lần véctơ mới xq được thêm vào V, thì giá trị nghiệm tối ưu hiện có
z(V) lại được thay đổi mới.
Nhận xét 2. Theo cách xây dựng θij > 0 , j = 1, . . . , n, và nếu θij = +∞
(cid:1) = 0. thì theo quy ước (cid:0)1/θij
Nhận xét 3. Phần lớn công việc trong thuật toán là thực hiện Bước 2. Với
(cid:1) ≥ d (V ) + Qx0, u ≥ 0(cid:9) mỗi j = 1, . . . , n, cần giải một bài toán tuyến tính max (cid:8)θij : Bu − (cid:0)(cid:0)Qvij (cid:1) θij
Tuy nhiên các bài toán tuyến tính này chỉ khác nhau ở một cột hệ số và do
đó công sức cần bỏ ra để giải chúng có thể giảm bớt đáng kể nhờ khéo liên kết
các nghiệm. Cũng nên chú ý là θij có thể thay đổi chỉ nếu z(V) thực sự giảm Nhận xét 4. Mỗi ω = (cid:8)vi1, ..., vin(cid:9) trong ∆ tương ứng với một ma trận không suy biến E (ω) = (cid:2)vi1, ..., vin(cid:3) bài toán tuyến tính ở Bước 3 có thể diễn
max
, trong đó g (ω)T = (cid:2)1/θi1, ..., 1/θin
(cid:111) đạt lại như sau: (cid:110) g (ω)T (cid:0)x − x0(cid:1) : x ∈ X (cid:3) E (ω)−1
Tập chấp nhận được của bài toán này không thay đổi từ vòng lặp này sang
vòng lặp khác, trong khi đó véctơ hệ số mục tiêu b(ω) thay đổi theo ω. Một
ω khác vòng lặp trước chỉ bởi một véctơ.
vài cố gắng tính toán có thể được lưu lại bằng cách thay đổi ω từ từ giống như
Nhận xét 5. Như đã nói tới ở mục trước, trong thuật toán có thể thay thế
S(V) bằng R(V).
28
2.2.2 Suy biến
Lúc này trong thuật toán x0 được giả thiết là một đỉnh không suy biến. Hai
x0 là một đỉnh của
định lý sau cho phép ta sửa lại bước 0 để có thể bỏ qua giả thiết này. Giả sử
X =
aijxj (cid:54) ai, i ∈ M, x (cid:62) 0
x ∈ Rn : (cid:80) j∈N
(cid:40) (cid:41)
{1, 2, . . . , n} và M = {1, 2, . . . , m}. Xét
trong đó aij và ai là các phần tử của ma trận A và véctơ a tương ứng, N =
aijxj + si = ai, i ∈ M, x (cid:62) 0, s (cid:62) 0
(cid:40) (cid:41)
(x, s) ∈ Rn+m : (cid:80) j∈N
i = ai − (cid:80)
j, i =
j∈N aijx0
(cid:101)X =
Rõ ràng là (cid:101)x0 = (cid:0)x0, s0(cid:1) là một đỉnh của (cid:101)X nếu s0 1,..., m. Đặt
j > 0 hay x0
j là biến phi cơ sở }.
J = {j : x0
j > 0 hay s0
j là biến phi cơ sở }.
I = {i : s0
X (cid:48) =
aijxj (cid:54) ai, i ∈ I, x (cid:62) 0, j ∈ J
x ∈ Rn : (cid:80) j∈N
Xác định: (cid:40) (cid:41)
Rõ ràng X ⊆ X (cid:48)
Định lý 2.2.1. Cho x0 là một đỉnh của X (cid:48) và liên thuộc với đúng n cạnh khác
biệt của X (cid:48).
Chứng minh. Do (x0, s0), là một nghiệm chấp nhận được cơ sở nên tồn tại các
số thực αjh, βjk, ¯αjh, ¯βjk, sao cho
si = s0
j -((cid:80) i -((cid:80)
k∈M (cid:118)I 0βjksk), j ∈ J 0 k∈M (cid:118)I 0 ¯βiksk), i ∈ I 0
(cid:101)X = { (x, s) ∈ Rn+m | xj = x0
h∈N (cid:118)J 0αjhxh + (cid:80) h∈N (cid:118)J 0 ¯αihxh + (cid:80) xj (cid:62) 0, j ∈ N; si (cid:62) 0, i ∈ M },
(3.1)
29
j là biến cơ sở },
I 0 ={ ı| x0
i là biến cơ sở }.
Trong đó J 0 ={ | x0
Xét
si = s0
j -((cid:80) i -((cid:80)
k∈M (cid:118)I 0βjksk), j ∈ J 0 k∈M (cid:118)I 0 ¯βiksk), i ∈ I 0
(cid:102)X (cid:48) = { (x, s) ∈ Rn+m | xj = x0
h∈N (cid:118)J 0αjhxh + (cid:80) h∈N (cid:118)J 0 ¯αihxh + (cid:80) xj (cid:62) 0, j ∈ N; si (cid:62) 0, i ∈ I }
(3.2)
Giả sử (x0, s0) không phải là một đỉnh của (cid:102)X (cid:48). Khi đó tồn tại hai điểm khác
nhau (x(cid:48), s(cid:48)), (x(cid:48)(cid:48), s(cid:48)(cid:48)) trong đó (cid:102)X (cid:48), và λ, với 0 < λ < 1,
j = x(cid:48)(cid:48) x(cid:48)
j = 0 với mọi j ∈ N ∼ J 0
i = s(cid:48)(cid:48) s(cid:48)
i = 0 với mọi i ∈ M ∼ I 0. Theo (3.2) điều này kéo theo
(x(cid:48), s(cid:48)) = (x(cid:48)(cid:48), s(cid:48)(cid:48)) ta gặp mâu thuẫn. Do đó x0 là một đỉnh của X (cid:48)
sao cho (x0, s0) = λ(x(cid:48), s(cid:48)) + ( 1 - λ )(x(cid:48)(cid:48), s(cid:48)(cid:48)), dễ thấy
xj = x0
j - δhαjh, j ∈ J 0,
si = s0
j - δh ¯αih, i ∈ I 0,
Với h ∈ N ∼ J 0 và δh ≥ 0, xây dựng n tia (nửa đường thẳng) xác định bởi :
xh = δh,
xj = 0, j ∈ N ∼ (J 0 ∪ {h}),
si = 0, i ∈ M ∼ I 0,
(3.3)
xj = x0
si = s0
j - δkβjk, j ∈ J 0, ¯βik, i ∈ I 0,
i - δh
Và cho k ∈ M ∼ I 0 và δk ≥ 0, sao cho:
sk = δk,
si = 0, i ∈ M ∼ (J 0 ∪ {k}),
(3.4)
30
δh ≤ δ∗
j/αjh|αjh > 0(cid:9) , min
h = min
min j∈J 0∩J
i∈I∩I 0
Từ mục (3.2) suy ra các siêu phẳng này giao với (cid:101)X (cid:48), sao cho: (cid:27) (cid:26) (3.5) (cid:8)x0 (cid:8)s0
i /αih|αih > 0(cid:9) (cid:27)
δk ≤ δ∗
j/βjk|βjk > 0(cid:9) , min
i /βik|βik > 0(cid:9)
k = min
min j∈J 0∩J
(cid:26) (3.6) (cid:8)x0 (cid:8)s0
i∈I∩I 0 k không thể bằng 0, nghĩa là mỗi
h và δ∗
Từ định nghĩa của I và J suy ra rằng δ∗
siêu phẳng có ít nhất một điểm khác với (x0, s0) trong (cid:101)X (cid:48) . Các đoạn thẳng
được xác định bởi (3.3) - (3.6) là n cạnh khác nhau của và liên thuộc với (x0, s0).
Do (cid:101)X (cid:48) biểu diễn cùng một tập lồi đa diện như X (cid:48) nên định lý được chứng minh
xong.
Chứng minh trên đây sử dụng các ký hiệu quen thuộc của quy hoạch tuyến
tính và được nêu ra để chỉ rõ cách xác định n cạnh khác biệt của X (cid:48) kề x0.
Định lý 2.2.2. Cho một vectơ x0 ∈ X, với (x0, u0) ∈ Λ, và tập hữu hạn V các
điểm trong X, sao cho cT x0 + bT u0 < z(V ). Khi đó trên tia bất kỳ đi từ x0,
¯Bu ≥ ¯d(V) + ¯Qx.
tồn tại điểm x (cid:54)= x0 sao cho với x đó tìm được u ≥ 0 thỏa mãn:
Chứng minh. Xét tia (cid:96) bất kỳ đi từ x0 và giả sử x∗ là điểm trên (cid:96) khác x0. Theo
Bổ đề 1.1.1, tồn tại u∗ ≥ 0 sao cho: Bu∗ ≥ d + Qu∗.Đặt z∗ = cT x∗ + bT u∗.
Kết luận của định lý là đúng nếu z∗ ≤ z(V). Trái lại, (x, u) = µ (x0, u0) + (1
µ = (z∗ - z(V))/(z∗ - cT x0 − bT u0) và 0 < µ < 1
- µ)(x∗, u∗) là một nghiệm của (2.2) trong đó
Theo Định lý 3.1, có thể giả thiết x0 là đỉnh không suy biến của tập lồi đa
diện mới X (cid:48) chứa X. Trong X (cid:48) x0 là đỉnh có đúng n cạnh kề, các cạnh này được
31
xác định bởi n véctơ với chuẩn đơn vị v1, . . . , vn. Nón sinh bởi x0, v1, . . . , vn
chứa X. Vì thế, nếu với mỗi vi xác định được số dương ¯θi thì có thể dùng tập {v1, . . . , vn} làm tập ω để bắt đầu thuật toán. Định lý 3.2 bảo đảm ¯θi > 0 với
một số giả thiết có thể dễ dàng kiểm tra, trừ ra một vài trường hợp ngoại lệ.
Khi loại bỏ giả thiết không suy biến, có thể diễn đạt lại Bước 0 của thuật toán
như sau.
Bước 0: Tìm đỉnh x0 ∈ X với các đỉnh kề x1, ..., xr, sao cho nếu r > n thì
x0, u0) ∈ Λ. Giả sử v1, ..., vn là các véctơ chuẩn đơn vị xác định các tia đi từ
x0 qua các đỉnh kề với x0 trong X (cid:48) (X (cid:48) xác định như ở Định lý 3.1). Đặt V =
{x0, x1, ..., xr}, ω = {v1, ..., vn} và ∆ = {ω}. Chuyển sang Bước 1
có xj, j ∈ {1, ..., n}, thỏa mãn cT xi + bT ui > cT x0 + bT u0 với ( xj, uj) ∈ Λ, (
2.2.3 Sự hội tụ
Mục này trình bày chứng minh sự đạt nghiệm tối ưu khi kết thúc thuật
toán. Một vòng lặp của thuật toán gồm các bước từ 1 đến 4, và ∆c là tập tất
cả các ω bị loại khỏi ∆ mà không bị thay thế. Rõ ràng ở Bước 0 ∆c = ∅ và mở
rộng dần mỗi khi điều kiện ở Bước 4.a được kiểm tra là đúng. Cho tập véctơ ω
sao cho I(ω) = {i : vi ∈ ω}, xét các tập lồi đa diện: (cid:40)
C(ω) =
λivi; λi ≥ 0, i ∈ I(ω)
x|x = x0 + (cid:80) i∈I(ω)
(cid:41) ,
(cid:40)
H(ω) =
λivi; (cid:80)
(1/θi)λi ≤ 1
x|x = x0 + (cid:80) i∈I(ω)
i∈I(ω)
(cid:41) ,
C (ω)
∩
H (ω)
∪ ω∈∆∪∆c
∩ ω∈∆∪∆c
(cid:20) (cid:21) (cid:20) (cid:21) T =
32
trong đó θi = max (cid:8)θi : x0 + θivi ∈ S (V )(cid:9) > 0 và V là tập các đỉnh của X đã
được thăm dò ở vòng lặp hiện tại của thuật toán.
Theo Định lý 2.2.3 được nêu dưới đây, T ⊆ S(V) ở mọi vòng lặp của thuật
toán. Hơn nữa, theo Hệ quả 2.2.4, X ⊆ T nếu ∆ = ∅. Điều này kéo theo X ⊆
S(V) khi thuật toán kết thúc. Do đó theo Định lý 2.1.4.a, quy tắc dừng thuật
toán bảo đảm rằng đã nhận được nghiệm tối ưu.
Định lý 2.2.3. Ở mọi vòng lặp của thuật toán T ⊆ S(V)
H (ω)
C (ω)
∩
∩ ω∈∆∪∆c
∪ ω∈∆∪∆c
Chứng minh. Do (cid:21) (cid:21) (cid:20) (cid:20) T =
H(ω)
[C (ω) ∩ H(ω)]
C (ω) ∩
⊆ ∪
ω∈∆∪∆c
∪ ω∈∆∪∆c
ω∈∆∪∆c
(cid:19)(cid:21) (cid:20) (cid:18) = ∪
Để hoàn thành việc chứng minh ta cần nêu được C (ω) ∩ H (ω) ⊆ S (V ). Cho
ˆx là một điểm trong C (ω) ∩ H (ω), sao cho: ˆx = x0 (cid:80) i=I(ω)
≤ 1, (cid:98)λi ≥ 0, i ∈ I(ω). Ta có thể viết lại như sau:
(cid:98)λi θi
θivi
(cid:98)λi θi
(cid:98)λivi
Với (cid:80) i=I(ω) x = x0 + (cid:80) i∈I(ω) (cid:32) (cid:33)
(x0 + θivi)
(cid:98)λi θi
x0 + (cid:80) i∈I(ω)
1 − (cid:80) i∈I(ω) = (cid:98)µ0x0 + (cid:80)
(cid:98)λi θi (cid:98)µi(x0 + θivi)
i∈I(ω)
≥ 0, i ∈ I(ω)
≥ 0, (cid:98)µi = (cid:98)λi
=
(cid:98)λi θi
θi
i∈I(ω)
Trong đó: (cid:98)µ0 = 1 − (cid:80)
i∈I(ω)
(cid:98)µ0 + (cid:80) (cid:98)µi = 1
Từ tính lồi của S(V ), ˆx là tổ hợp lồi của các điểm thuộc S(V ), Từ tính lồi của
S(V), là tổ hợp lồi của các điểm thuộc S(V) nên sẽ nằm trong S(V) và đến đây
33
định lý được chứng minh đầy đủ.
Định lý 2.2.1 tương tự như Bổ đề về lát cắt lồi của Glover [3], dựa trên ý
tưởng lát cắt Hoàng Tụy [6].
i vi trong đó λ∗ λ∗
i ≤ 0 với i ∈ I 0 và λ∗
i > 0 với i ∈ I + (cid:54)=
i∈I +
v∗ = (cid:80) i∈I 0
i vi + (cid:80) λ∗ ∅, I 0 ∪ I + = {1, ....n}. Ta đặt
Bổ đề 2.2.4. Cho n véctơ n - chiều độc lập tuyến tính v1, . . . , vn và bất kỳ
,
C =
x : x =
λivi, λi ≥ 0, i = 1, ..., n
n (cid:80) i=1
(cid:27) (cid:26)
và với j ∈ I +
λivi, λi ≥ 0, i = 1, ..., n
Cj =
x : x = λjv∗ +
n (cid:80) i=1 i(cid:54)=j
Cj
Khi đó: C ⊆ ∪ j∈I +
x = (cid:80)
λivi
i∈I 0∪I +
Chứng minh. Lấy điểm bất kỳ trong C, chẳng hạn:
µv∗ = (cid:80)
với λi ≥ 0. Với µ bất kỳ
i
i
(cid:1)vi (cid:1)vi + (cid:80) i∈I +
i∈I 0∪I + x = µv∗ + (cid:80) i∈I 0 r = min (cid:8)λi/λ∗
i )vi (µλ∗ (cid:0)λi − µλ∗ (cid:0)λi − µλ∗ i : i ∈ I +(cid:9) ≥ 0. Khi đó,x ∈ Cr (trên biên của
Cr nếu µ = 0)
Chọn µ = λr/λ∗
H(ω)
T ⊇ C0 ∩ (cid:26)
Định lý 2.2.5. Tại mỗi vòng lặp của thuật toán (cid:20) (cid:21) , Trong đó
x|x0 +
C0 =
λivi; λi ≥ 0, i = 1, ..., n
∩ ω∈∆∪∆c n (cid:80) i=1
(cid:27) ,
Và v1,...,vn là các vectơ chuẩn đơn vị xác định ở Bước 0
34
Chứng minh. Theo định nghĩa của T chỉ cần chứng minh rằng C0 ⊆ ∪ω∈∆∪∆cC(ω)
. Có thể thấy rằng trong thuật toán ∪ω∈∆∪∆cC(ω) được xây dựng như sau: Ta
js, hợp của chúng chứa C0. Các tập tiếp
bắt đầu với tập C0 và tạo ra các tập C ‘
sau được xây dựng bằng cách xuất phát từ tập Cj nào đó và quá trình được
áp dụng lặp lại để nhận được ∪ω∈∆∪∆cC(ω). Như vậy, kết luận định lý suy ra
từ Bổ đề 2.2.2.
Hệ quả 2.2.6. Nếu ∆ = ∅, thì X ⊆ T
Chứng minh. X được chứa trong C0 theo cách xây dựng C0 và trong H(ω) với
mọi ω ∈ ∆c theo điều kiện ở Bước 4.a. Từ đó, kết luận của hệ quả được suy ra
từ Định lý 2.2.3.
2.3 Cách tiếp cận siêu phẳng cắt
Mục này trình bày biến thể siêu phẳng cắt của thuật toán. Cách tiếp cận
siêu phẳng cắt này dựa trên quan sát sau đây. Trong thuật toán nêu ở mục 2.2,
vòng lặp thứ nhất tạo ra nửa không gian H(ω) sao cho H (ω) ∩ X ⊆ S (V) .
Do đó, theo tiêu chuẩn tối ưu sẽ không có điểm nào trong H (ω) ∩ X cho
giá trị hàm mục tiêu tốt hơn z(V). Trong thuật toán siêu phẳng cắt, phần của
X nằm trong H(ω) bị cắt bỏ và tạo ra một tập X mới nhỏ hơn. Sau đó, tìm
một đỉnh của tập X mới và tiếp tục thực hiện cũng các vòng lặp như trước. Ưu
điểm của cách tiếp cận này là đòi hỏi bộ nhớ ít hơn. Thuật toán siêu phẳng cắt
gồm các bước như sau.
35
X0 = X, k = 0. Chuyển sang Bước 1.
Bước 0. . Chọn một đỉnh bất kỳ trong X và xác định V = {x0}. Đặt
Bước 1. Trong Xk tìm các đỉnh xk,1, xk,2, . . . , xk,r kề xk và đưa các đỉnh
xk,j sao cho zk,j < zk rồi đặt xk = xk,j và tìm các đỉnh kề xk và chuyển sang
này vào V. Với mỗi j = 1, 2, . . . , r tính giá trị zk,j = cTxk,j + bTuk,j sao cho (cid:0)xk,j, uk,j(cid:1) ∈ Λ. Nếu hoặc r = n hoặc r > n và tồn tại j sao cho zk,j > zk = cTxk + bTuk với (cid:0)xk, uk(cid:1) ∈ Λ thì chuyển sang Bước 2. Trái lại, chọn một đỉnh
Bước 2 (Đối với trường hợp đặc biệt khi r > n và zk = zk,i với mọi
i = 1,2, . . . , n, xem Nhận xét 1 dưới đây).
Bước 2. Giả sử vk,1, . . . , vk,n là các véctơ chuẩn đơn vị, xác định các nửa
k ( xác định như trong Định
đường thẳng đi từ xk qua các đỉnh xk kề trong X ‘
, n bằng cách giải quy hoạch
lý 3.1 với X = Xk và x0 = xk). Với i = 1, . . . tuyến tính tìm số θi = (cid:8)θi : xk + θivk,i ∈ S (V)(cid:9) . Chuyển sang Bước 3. Bước 3. Xác định ma trận M = (cid:2)vk,1, . . . , vk,n(cid:3) và h = (cid:0)1/θ1, ...., 1/θn (cid:1)T (cid:0)θi > 0(cid:1).
Giải quy hoạch tuyến tính:
max (cid:8)hT M −1 (cid:0)x − xk(cid:1) : x ∈ Xk
(cid:9)
Giả sử x∗ là một nghiệm tối ưu và α là giá trị tối ưu nhận được. Nếu α ≥ 1
thì dừng thuật toán. Trái lại chuyển sang Bước 4.
Xk+1 = Xk ∩ (cid:8)x ∈ Rn : hT M −1 (cid:0)x − xk(cid:1) (cid:62) 1(cid:9)
Bước 4. Thêm x∗ vào V. Đặt xk+1 = x∗ và
Đặt k = k + 1. Nếu zk < Z(V ) thì quay lại Bước 2. Trái lại, quay lại Bước 1.
Nhận xét 1. Nếu r > n và zk = zk,j, j = 1, ... , r thì các giả thiết của
Định lý 3.2 có thể không còn đúng, do đó ở Bước 2, zk = zk,j > 0 không còn
36
α = max (cid:8)πT (cid:0)x − xk(cid:1) : x ∈ X(cid:9)
được bảo đảm nữa. Trong trường hợp này ở Bước 3, α cần được thay bằng:
Khi đó, ràng buộc mới ở Bước 4 trở thành πT (cid:0)x − xk(cid:1) (cid:62) 1 , trong đó π là
min
πT (cid:98)θk,i
(cid:27) (cid:0)xk,i − xk(cid:1) (cid:62) 1, i = 1, ..., r nghiệm của bài toán sau: (cid:26) n (cid:80) i=1
(cid:0)xk,i − xk(cid:1) :πT (cid:98)θk,i (cid:0)xk,i − xk(cid:1) ∈ S (V )(cid:9) Với (cid:98)θk,i = max (cid:8)θk,i : xk + θk,i
xk,1,
. . . , xk,n được nhận ra thuộc cùng một diện của Xk thì không cần hoàn
Nhận xét 2. Để ý rằng nếu ở lúc bắt đầu một vòng lặp đã cho, các điểm
thành vòng lặp đó và có thể kết thúc thủ tục.
Nhận xét 3. Cũng như trong biến thể thứ nhất của thuật toán, S(V) có
thể được thay bằng R(V)
2.4 Ví dụ minh họa thuật toán
Xét ví dụ số trong R2
1 −1
y1
y1
x1
[2, 0]
Xét bài toán quy hoạch song tuyến tính
−1
1
y2
y2
x2
→ max, + [0, 1] + [x1, x2]
1
1
với điều kiện x ∈ X, y ∈ Y, trong đó:
2
1
x1
(LP1)
3 −1
x2
(cid:54) ,x ≥ 0}, X = {x ∈ R2 :
1 −2
5 7 6 1
37
1 2
8
3 1
14
y1
2 0
6
y2
(cid:54) Y = {(y ∈ R2 : ,y ≥ 0}.
0 1
3
u1
Các tập X và Y được vẽ ở Hình 2.1. Phát biểu đối ngẫu của bài toán này là
x1
u2
[2, 0]
→ max
(LP2)
x2
u3
u4
+ min [8, 14, 9, 3]
u1
Với điều kiện
1 −1
1 3 2 0
x1
u2
≥
−1
1
2 1 0 1
x2
u3
x ∈ X và , u ≥ 0 + 0 1
u4
Để tìm nghiệm tối ưu của bài toán, thuật toán mô tả ở trên phải qua các
vòng lặp như sau.
x2 = (0, 5)T . Giải (LP2) bằng cách đặt x = xi, i 0, 1, 2. Các giá trị tối ưu tương
Khởi sự (Bước 0). Chọn x0 = (0, 0)T . Các đỉnh kề x0 là x1 = (1, 0)T và
z(x0) = 3, z(x1) = 13/2, z(x2) = 18.
ứng là
Đặt V = (cid:8)x0, x1, x2(cid:9) , z (V ) = 18, w1 = (cid:8)v1, v2(cid:9) và ∆ = {ω1}, trong
đó:
38
v1 = (1, 0)T , v2 = (0, 1)T .
Vòng lặp 1
Bước 1. ∆ (cid:54)= ∅. Chọn ω1
• Tìm cực đại θ1,
Bước 2. Giải quy hoạch tuyến tính:
u1
1
3
2
0
1
0
u2
θ1 ≥
2
1
0
1
−1
1
u3
với điều kiện - ,
−8 −14 −9 −3
2
−18
u4
u ≥ 0, θ1 ≥ 0
• Tìm cực đại θ2,
u1
1
3
2
0
−1
0
u2
θ2 ≥
2
1
0
1
1
1
u3
- , với điều kiện
−8 −14 −9 −3
0
−18
u4
u ≥ 0, θ2 ≥ 0
Giá trị tối ưu lần lượt là: θ1 = 36/13, θ2 = 5
• Tìm cực đại 13
36λ1 + 1
5λ2,
Bước 3. Giải quy hoạch tuyến tính
39
1
1
2
1
3 −1
(cid:54) với điều kiện λ1 + 1 0 0 λ2 1
1 −2 Nghiệm tối ưu là λ∗ (cid:1) λ∗
5 7 6 1
√
13
90 > 1 nên ta đặt 2/
x3 =
√
Bước 4. Do (cid:0)1/θ1
3/
13
1 = 2, λ∗ 1 + (cid:0)1/θ2 0 + 2 0
2 = 3. (cid:1) λ∗ 2 = 119 1 0
+ 3 0 , v3 = 1
Thêm x3 vào V và thay ω1 trong ∆ bằng ω2 = {v1, v3} và ω3 = {v3, v2}.
Để đổi mới z(V), ta đặt x = x3 trong (LP2) và giải quy hoạch tuyến tính thu
được. Giá trị tối ưu là 10, nghĩa là nhỏ hơn z(V). Vì thế, z(V) được giữ nguyên.
Vòng lặp 2
Bước 1. ∆ (cid:54)= ∅. Chọn ω2 = (cid:8)v1, v3(cid:9).
• Tìm cực đại θ3,
Bước 2. θ1 không thay đổi; θ3 là giá trị tối ưu của quy hoạch tuyến tính:
u1
√
1
3
2
0
13
0
u2
−1/ √
θ3 ≥
13
2
1
0
1
1/
1
u3
√
- với điều kiện
4/
13
−8 −14 −9 −3
−18
,
u4
u (cid:62) 0, θ3 (cid:62) 0. √
13.
Giá trị tối ưu θ3 = 15 7
Bước 3. Giải
40
√
• Tìm cực đại 13
λ3
15
3
36λ1 + 7
1
1
2
1
0
3 −1
1
(cid:54) với điều kiện λ1 + λ2 1 0
√
13.
1 −2 Nghiệm tối ưu là λ∗
2 = 3 5
5, λ∗ (cid:1) λ∗
5 7 6 1
3 × 707/900 =< 1. Do đó, ω2 bị loại khỏi ∆.
1 = 7 1 + (cid:0)1/θ3
(cid:1) λ∗ Bước 4. (cid:0)1/θ1
Vòng lặp 3
Bước 1. ∆ = (cid:8)ω3(cid:9) .. Chọn ω3 = (cid:8)v3, v2(cid:9).
Bước 2. θ3 và θ3 không thay đổi.
√
• Tìm cực đại 1
λ3,
5λ2 + 7
15
3
Bước 3. Giải
1
1
√
13
2/
2
1
√
3/
13
3 −1
(cid:54) với điều kiện λ3 λ2 + 0 1
1 −2 Nghiệm tối ưu là λ∗
3 = 0
2 = 5, λ∗ (cid:1) λ∗
5 7 6 1
2 + (cid:0)1/θ3
3 = 1. Do đó, ω3 bị loại khỏi ∆.
(cid:1) λ∗ Bước 4. (cid:0)1/θ2
Vòng lặp 4
Bước 1. ∆ = ∅. Do đó dừng thuật toán. Nghiệm tối ưu là
41
x∗ =
0 , y∗ = 5 0 , 3
trong đó y∗ là nghiệm đối ngẫu tối ưu của bài toán thứ ba được giải ở Bước 0.
Giá trị tối ưu của hàm mục tiêu bằng 18.
Nhận xét. Để ý rằng chiến thuật duyệt toàn bộ phải duyệt qua tất cả 6 đỉnh
• Giải theo thuật toán siêu phẳng cắt
của X, trong khi đó thuật toán đề xuất chỉ phải khảo sát 4 đỉnh trong số đó.
Mục này giải lại bài toán (LP1) theo thuật toán siêu phẳng cắt.
Vòng lặp 1
Bước 1. Các đỉnh kề x0 là x0,1 = (1, 0)T và x0,2 = (0, 5)T với z0,1 = 13 2 và z0,2 = 18. Đặt V = (cid:8)x0, x0,1, x0,2(cid:9) , z (V ) = 18. Vì r = 2 = n nên chuyển sang
13, θ2 = 5.
Bước 2.
1 0
1 0
13 36
Bước 2. v0,1 = (1, 0)T , v0,2 = (0, 1)T và như trước đây θ1 = 36
0 1
0 1
1 5
Bước 3. M = và h = . Tính giá trị , M −1=
1 0
α = max {
(cid:20) (cid:21)
13 36
1 5
0 1
(cid:0)x − x0(cid:1) : x ∈ X0}, bằng cách giải quy hoạch
tuyến tính:
max (cid:8) 13
36x1 + 1
5x2 : x ∈ X0
90 > 1. Chuyển sang Bước 4.
(cid:9)
5x2 (cid:62) 1(cid:9)
36x1 + 1
Nghiệm tối ưu: x∗ = (2, 3)T với α = 119 Bước 4. Đặt V = (cid:8)x0, x0,1, x0,2, x∗(cid:9) , x1 = x∗ và X1 = X0 ∩ (cid:8)x ∈ R2 : 13
Vì z1 = 10 < 18 = z(V) nên chuyển Bước 2 của vòng lặp 2.
42
Vòng lặp 2
x1,1 =
9 5
13 5
−
−
Bước 2. Các đỉnh kề x1 là 13 5 , x1,2 = 0 , 5
√
√
2 3
2 3
0 5
2
1/
√
√
v1,1 =
5 √
−1/ √
9 5 3/
5
2/
2
−2/
5
1/
2
= = , v1,2 = .
• Tìm cực đại θ1 với các điều kiện
Giải hai quy hoạch tuyến tính:
u1
0
1
3
2
0
1 −1
√
2
u2
≥
×
1
2
1
0
1
−1
1
−1/ √
1/
2
u3
−8 −14 −9 −3
−18
2
0
+ θ2 2 3
u4
√
√
2
5, θ2 = 2
, u (cid:62) 0, θ2 (cid:62) 0.
√
√
√
√
2
5
1/
−
√
5 −1/ √ √
5 − √
5
1/
2
2
2 −
−2/
−2/
Bước 3. M = Nghiệm tối ưu lần lượt là: θ1 = 37 31 , M −1 =
31 √
37
5
1 √
2
2
và h = . Tính giá trị
√
√
−
5
31 √
α = max {
(cid:20) (cid:21)
√
5 − √
37
5
1 √ 2
2
2
2 −
−2/
(cid:0)x − x1(cid:1) : x ∈ X1}
Bằng cách giải quy hoạch tuyến tính:
43
max (cid:8)− 68
74 : x ∈ X1
37x1 − 99 (cid:1)T
74x2 + 569 với α = 9803
173, 150
6401 > 1. chuyển sang Bước 4.
173
(cid:9) .
37x1 − 99
74x2 + 569
74
(cid:62) 1(cid:9) . Nghiệm tối ưu: x∗ = (cid:0) 396 Bước 4. V = (cid:8)x0, x0,1, x0,2, x1, x1,1, x1,2, x∗(cid:9) , x2 = x∗ và X2 = X1 ∩ (cid:8)x ∈ R2 : − 66
Vì z2 < z(V ) nên chuyển Bước 2 của vòng lặp 3.
Vòng lặp 3
Bước 2. Các đỉnh kề x2 là
1089 433
x2,1 =
669 433
, x2,2 = 0 5
Do cả hai điểm này thuộc cùng một diện của X2, cụ thể là lát cắt tạo ra ở vòng
lặp trước nên dừng thuật toán.
x∗ =
Nghiệm tối ưu của bài toán quy hoạch song tuyến tính là:
0 , y∗ = 5 0 3
với giá trị tối ưu của hàm mục tiêu bằng 18.
Kết luận chương 2
Chương này giới thiệu thuật toán nêu ở [3] tìm nghiệm của bài toán quy
hoạch song tuyến tính với miền ràng buộc rời nhau và với giả thiết các tập ràng
buộc X, Y bị chặn. Thuật toán đưa bài toán ban đầu về bài toán tối ưu trên
một tập không lồi và giải bài toán nhận được dựa trên điều kiện tối ưu đưa
ra. Thuật toán hội tụ về nghiệm đúng của bài toán quy hoạch song tuyến tính
ban đầu và được minh họa bằng ví dụ số cụ thể.
44
Kết luận
Luận văn đề cập tới bài toán quy hoạch song tuyến tính, một dạng đặc biệt
của quy hoạch toàn phương. Nói chung, quy hoạch song tuyến tính là một bài
toán tối ưu không lồi, không lõm và thuộc lớp bài toán tối ưu toàn cục, rất khó
giải. Tuy nhiên, bài toán này có nhiều ứng dụng trong lý thuyết và thực tiễn,
nên được nhiều tác giả quan tâm nghiên cứu, cả về lý thuyết và thuật toán
giải. Luận văn đã trình bày những nội dung cụ thể sau:
1. Các kiến thức toán học có liên quan tới bài toán quy hoạch song tuyến
tính: đối ngẫu trong quy hoạch tuyến tính, bài toán quy hoạch lõm với ràng
buộc tuyến tính, tính chất nghiệm của bài toán quy hoạch song tuyến tính và
mối liên hệ với bài toán cực tiểu hàm lõm, tuyến tính từng khúc. Giới thiêu
"thuật toán xuống núi" tìm nghiệm cực tiểu địa phương của bài toán quy hoạch
song tuyến tính khi miền ràng buộc bị chặn.
2. Cách đưa bài toán quy hoạch song tuyến tính về bài toán tối ưu tương
đương trên một tập không lồi. Từ đó có thể tìm nghiệm đúng của bài toán quy
hoạch song tuyến tính với miền ràng buộc tách biến và với giả thiết miền ràng
buộc bị chặn, theo thuật toán dựa trên điều kiện tối ưu của nghiệm bài toán.
Biến thể siêu phẳng cắt của thuật toán và ví dụ số minh họa thuật toán.
45
Tài liệu tham khảo
Tiếng Việt
[1] Lê Dũng Mưu, Nguyễn Hiền và Nguyễn Hữu Điển (2014), Giáo trình giải
tích lồi và ứng dụng, NXB Đại học Quốc gia Hà Nội.
[2] Trần Vũ Thiệu, Nguyễn Thị Thu Thủy (2011), Giáo trình tối ưu phi tuyến,
NXB Đại học Quốc gia Hà Nội.
Tiếng Anh
[3] Gallo G., ¨Ulk¨uc¨u A. (1977), "Bilinear Programming: An Exact Algorithm",
Math. Programming, 12, 173–194.
[4] Nahapetyan A, Pardalos P. (2007), "A Bilinear Relaxation Based Algo-
rithm for Concave Piecewise Linear Network Flow Problems", Journal of
Industrial and Management Optimization, 3(1), 71–85.
[5] Thieu T. V. (1980), "Relationship between Bilinear Programming Prob-
lem and Concave Minimization Under Linear Constraints", Acta Math.
Vietnam., 2 67–81.
46
[6] Horst R., Tuy H. (1996), Global Optimization, 3-rd Edition, New York:
Springer.
