Phương pháp chia đôi giải bài toán tối ưu trên tập Pareto tuyến tính

Kỷ yếu công trình khoa học 2015 - Phần I

PHƯƠNG PHÁP CHIA ĐÔI GIẢI BÀI TOÁN TỐI ƯU TRÊN TẬP
PARETO TUYẾN TÍNH
Nguyễn Lâm Tùng
Bộ môn Toán Đại học Thăng Long
Email: nguyenlamtung01@gmail.com
Tóm tắt. Báo cáo trình bày một số cải tiến trong thuật toán chia đôi giải bài
toán tối ưu một hàm tuyến tính trên tập Pareto [1]. Bài toán được phát biểu như
sau:
max ⟨d, x⟩,
(P)
x∈E(C,X)

trong đó d ∈ R , E(C, X) là tập Pareto của bài toán tối ưu đa mục tiêu tuyến
tính:
V max Cx,
(LP)
n

x∈X

với C là ma trận p × n, p là số hàm mục tiêu tuyến tính, X là đa diện lồi bị
chặn trong R n .
Báo cáo trình bày các tính chất quan trọng của bài toán (LP), cở sở lý thuyết,
điều kiện dừng của thuật toán chia đôi. Cuối cùng báo cáo nêu một ví dụ minh
họa cho thuật toán.
Từ khóa: đa diện lồi, tập Pareto, tối ưu, hàm tuyến tính, thuật toán chia đôi,
nghiệm tối ưu.

1 Mở đầu
Định nghĩa 1. Cho R n = {x ∈ R n |xi ≥ 0, ∀i = 1, n} là nón các phần
+
n
tử không âm của R . Ta nói điểm x ∈ X cực đại Pareto của bài toán (LP)
nếu: Cy − Cx ∈ R n , ∀y ∈ X, y ̸= x, tập tất cả các điểm cực đại Pareto
/ +
của bài toán (LP) ký hiệu là E(C,X), gọi tắt là tập Pareto hay tập hữu hiệu.
Định lý 1.Tập Pareto E(C, X) của bài toán (LP) là đóng, liên thông đường
và bao gồm một số diện của X.
Định lý 2. Điểm x0 là điểm Pareto của bài toán tối ưu p mục tiêu tuyến tính
¯
(LP) khi và chỉ khi tồn tại λ ∈ Λ0 sao cho:
¯
¯
λT Cx0 ≥ λT Cx, ∀x ∈ X
với Λ = {λ = (λ1 , . . . , λp ) | λ1 + · · · + λp = 1, λi ≥ 0, ∀i = 1, p}
Λ0 là phần trong tương đối của Λ.
Trường Đại học Thăng Long

141

Kỷ yếu công trình khoa học 2015 - Phần I

Nhận xét: Theo định lý trên, bài toán (P ) có thể mô tả thành bài toán sau:
max{dT x |λT Cx ≥ g(λ), x ∈ X, λ ∈ Λ0 }
trong đó g(λ) = max{λT Cy |y ∈ X}.
Định lý 3.[Philip] Điểm x0 là điểm Pareto của bài toán tối ưu p mục tiêu tuyến
¯
tính (LP) khi và chỉ khi tồn tại M > 0 và λ ∈ ΛM sao cho:
¯
¯
λT Cx0 ≥ λT Cx, ∀x ∈ X
với ΛM = {λ = (λ1 , . . . , λp ) | λ1 +· · ·+λp ≤ M, λi ≥ 1, ∀i = 1, p}.
Trong bài báo [1], tác giả đã sử dụng định lý 3 để đưa ra thuật toán tìm kiếm
chia đôi, tuy nhiên thuật toán đó có nhược điểm là:
Thứ nhất, trong định lý 3 chỉ khẳng định sự tồn tại của M chứ không đưa cách
xác định M, do đó khi áp dụng vào ví dụ cụ thể, việc lấy giá trị M nào đó là thiếu
chặt chẽ.
Thứ hai, thuật toán hội tụ chậm và chưa đưa ra được nghiệm chính xác.
Bài báo cáo này chỉ dùng định lý 2, không sử dụng định lý 3 nên thuật toán chặt
chẽ hơn, đồng thời đưa ra điều kiện dừng của thuật toán làm cho thuật toán dừng
rất nhanh và có nghiệm chính xác.

2 Thuật toán tìm kiếm chia đôi
Đặt:

d∗ =

max ⟨d, x⟩, γ0 = min⟨d, x⟩, β0 = max⟨d, x⟩

x∈E(C,X)

x∈X

x∈X

trong đó E(C, X) là tập Pareto của bài toán đa mục tiêu tuyến tính (LP), X là
đa diện lồi bị chặn.
Dễ thấy γ0 ≤ d∗ ≤ β0 , ý tưởng của thuật toán là áp dụng một sơ đồ chia đôi
miền giá trị của hàm mục tiêu để định vị giá trị d∗ . Bắt đầu từ đoạn [γ0 , β0 ]
chứa d∗ , qua mỗi bước lặp k sẽ co ngắn đoạn γk , βk còn một nửa bằng cách
giải bài toán:
Tìm x ∈ E(C, X) sao cho dT x ≥ αk với αk = (γk + βk )/2
(Pk )
• Nếu bài toán (Pk ) có nghiệm là xk thì đặt γk+1 = dT xk , βk+1 = βk
• Nếu bài toán (Pk ) vô nghiệm thì đặt γk+1 = γk , βk+1 = αk
Sau khi giải bài toán (Pk ) ta có d∗ ∈ [γk+1 , βk+1 ], quá trình này sẽ kết thúc
khi βk − γk ≤ ϵ cho trước. Cho α ∈ R , ký hiệu:
E α = {x ∈ E(C, X) | ⟨d, x⟩ ≥ α}
Trường Đại học Thăng Long

142

Kỷ yếu công trình khoa học 2015 - Phần I

Ta có:
E α = {x ∈ X |∃λ ∈ Λ0 : λT Cx ≥ λT Cy, ∀y ∈ X, ⟨d, x⟩ ≥ α}
= {x ∈ X |∃λ ∈ Λ0 : λT Cx ≥ g(λ), ⟨d, x⟩ ≥ α}
trong đó g(λ) = max{λT Cy | y ∈ X}.
Đặt: hα (λ) = max{λT Cx | x ∈ X, ⟨d, x⟩ ≥ α}.
Dễ dàng chứng minh được hα (λ) là hàm lồi theo λ.
Xây dựng các tập:
Λ = {(λ1 , λ2 , . . . , λp ) | λ1 + λ2 + · · · + λp = 1, λi ≥ 0, ∀i = 1, ..., p}
Λ0 = {(λ1 , λ2 , . . . , λp ) | λ1 +λ2 +· · ·+λp = 1, λi > 0, ∀i = 1, ..., p}
Ω = {(λ, t) | λ ∈ Λ0 , t ≥ g(λ)}
Ωα = {(λ, t) | λ ∈ Λ0 , t > hα (λ)}
¯
Ωα = {(λ, t) | λ ∈ Λ0 , t ≥ hα (λ)}
Mệnh đề 1. a. Ω và Ωα là hai tập lồi,
¯
b. Ω ⊂ Ωα ,
c. E α (C, X) ̸= ∅ khi và chỉ khi Ω \ Ωα ̸= ∅.
Chứng minh:
a. Các Ω và Ωα lồi do nó là trên đồ thị của các hàm lồi g(λ) và hα (λ).
b. Hiển nhiên do g(λ) ≥ hα (λ).
c. Giả sử x ∈ E α (C, X) khi đó tồn tại λ ∈ Λ0 sao cho g(λ) ≤ λT Cx.
Lấy t = g(λ) suy ra (λ, t) ∈ Ω. Hơn nữa:
t ≤ λT Cx, x ∈ X, ⟨d, x⟩ ≥ α
nên:
t ≤ max{λT Cx | x ∈ X, ⟨d, x⟩ ≥ α} = hα (λ)
do đó t − hα (λ) ≤ 0 suy ra (λ, t) ∈ Ωα .
/
Do vậy (λ, t) ∈ Ω \ Ωα hay Ω \ Ωα ̸= ∅ .
Ngược lại, giả sử (λ, t) ∈ Ω \ Ωα , theo định nghĩa ta có:
t ≥ g(λ), λ ∈ Λ0 , t ≤ hα (λ)
Trường Đại học Thăng Long

143

Kỷ yếu công trình khoa học 2015 - Phần I

Gọi x∗ là nghiệm tối ưu của bài toán:
max{λT Cx | x ∈ X, ⟨d, x⟩ ≥ α}
ta có:

t ≤ hα (λ) = λT Cx∗ , ⟨d, x∗ ⟩ ≥ α, x∗ ∈ X

suy ra g(λ) ≤ λT Cx∗ , λ ∈ Λ, ⟨d, x∗ ⟩ ≥ α, x∗ ∈ X, tức là
x∗ ∈ E α (C, X) hay E α (C, X) ̸= ∅.
Giả sử x0 ∈ X và Sk = {(λ, t) | λ ∈ Λ, t ≥ λT Cx0 , }, khi đó Sk là
đa diện lồi chứa Ω và Sk có hướng lùi xa duy nhất là u = (0, . . . , 0, 1) ∈
R p × R . Gọi Vk là tập đỉnh của Sk và ta định nghĩa Wk như sau:
Wk = {(λ, t) ∈ Vk | t − hα (λ) ≤ 0}
Hệ quả 1. Nếu Wk = ∅ thì Ω \ Ωα = ∅.
Chứng minh: Do tập Sk có hướng lùi xa duy nhất là vecto u nên hàm φ(λ, t) =
t − hα (λ) bị chặn dưới trên tập Sk , đồng thời φ(λ, t) là hàm lõm. Do đó:
min{t − hα (λ) | (λ, t) ∈ Sk } = min{t − hα (λ) | (λ, t) ∈ Vk }
Do vậy nếu Wk = ∅ thì: min{t − hα (λ) | (λ, t) ∈ Vk } > 0, tức là:
min{t − hα (λ) | (λ, t) ∈ Sk } > 0
Vì Ω ⊂ Sk nên ∀(λ, t) ∈ Ω ta có t − hα (λ) > 0 tức là (λ, t) ∈ Ωα , suy
ra Ω ⊂ Ωα , nghĩa là Ω \ Ωα = ∅.
Như vậy nếu Wk = ∅ thì E α (C, X) = ∅, tức là bài toán (Pk ) vô nghiệm.
Ngược lại, nếu Wk ̸= ∅ ta có điểm (λk , tk ) ∈ Wk .
Nhận xét:
• Nếu (λk , tk ) ∈ Ω, tức là λk ∈ Λ và g(λk ) ≤ tk , thì (λk , tk ) ∈ Ω\Ωα .
Gọi xk là một nghiệm tối ưu của bài toán quy hoạch tuyến tính:
max{(λk )T Cx | x ∈ X, ⟨d, x⟩ ≥ α}
theo chứng minh mệnh đề 1, ta có xk ∈ E α (C, X).
• Nếu (λk , tk ) ∈ Ω, tức là g(λk ) − tk > 0, gọi y k là nghiệm tối ưu của
/
bài toán quy hoạch tuyến tính:
max{(λk )T Cy | y ∈ X}
suy ra g(λk ) = (λk )T Cy k , do đó (λk )T Cy k − tk = g(λk ) − tk > 0.
Mặt khác, ∀(λ, t) ∈ Ω ta có λT Cy k − t ≤ g(λ) − t ≤ 0
Trường Đại học Thăng Long

144

Kỷ yếu công trình khoa học 2015 - Phần I

Như vậy siêu phẳng {(λ, t) | λT Cy k − t = 0} tách chặt đỉnh (λk , tk )
với tập Ω. Ta xây dựng đa diện Sk+1 chứa Ω như sau:
Sk+1 = Sk ∩ {(λ, t) | λT Cy k − t ≤ 0}
Mệnh đề 2. Giả sử tất cả các đỉnh của Sk là v1 , v2 , . . . , vm , đồng thời φ(v1 ) =
0, φ(v2 ) > 0, . . . , φ(vm ) > 0. Khi đó φ(x) > 0, ∀x ∈ Sk , x ̸= v1 .
Chứng minh: Do Sk có hướng lùi xa duy nhất là u = (0, . . . , 0, 1) nên
với mọi x ∈ Sk tồn tại các số thực không âm q1 , q2 , . . . , qm , r sao cho
q1 + q2 + · · · + qm = 1 và x − r.u = q1 v1 + · · · + qm vm . Do
φ(x) = φ(λ, t) = t − hα (t) là hàm lõm và tăng theo t nên φ(x) ≥
φ(x − ru) ≥ q1 φ(v1 ) + · · · + qm φ(vm ) ≥ 0, dễ thấy dấu bằng xẩy ra chỉ
khi x = v1 , do đó ta có điều phải chứng minh.
Hệ quả 2. Giả sử (λ1 , t1 ), . . . , (λm , tm ) là tất cả các đỉnh của Sk , đồng thời
φ(λ1 , t1 ) = 0, φ(λ2 , t2 ) > 0, . . . φ(λm , tm ) > 0, (λ1 , t1 ) ∈ Ω. Khi đó
/
φ(λ, t) > 0, ∀(λ, t) ∈ Ω.
Chứng minh: Suy ra trực tiếp từ mệnh đề 2 do Ω ⊂ Sk và (λ1 , t1 ) ∈ Ω.
/
Từ các tính chất và nhận xét trên ta có thủ tục OA như sau:
Khởi tạo: Lấy v ∈ X sao cho Cv ̸= 0. Đặt S0 = {(λ, t) | λ ∈
Λ, λT Cv ≤ t}, V0 là tập đỉnh của S0 và đặt k = 0.
Vòng lặp k:
Bước 1: Giải bài toán: θ = min{t−hα (λ) | (λ, t) ∈ Vk } ta được θ, λk , tk .
• TH1: Nếu θ > 0 hoặc θ = 0 nhưng φ(λ, t) > 0, ∀(λ, t) ∈
V (Sk ), (λ, t) ̸= (λk , tk ) thì dừng thuật toán: E α (C, X) = ∅, nói
cách khác bài toán Pk không có nghiệm.
• TH2: Nếu θ < 0 hoặc θ = 0 và có λk ∈ Λ0 thì chuyển sang bước 2.
• TH3: Nếu θ = 0 và không thuộc TH1 và TH2 thì chọn ε > 0 đủ nhỏ và
đặt:
ε
ε
Sk = Sk ∩ {(λ, t)|λi ≥ ε}, Vkε = V (Sk )
Giải bài toán:
θ = min{t − hα (λ) | (λ, t) ∈ Vkε }
ta được nghiệm θε , λk , tk
ε ε
– Nếu θε > 0 thì dừng thuật toán, bài toán Pk không có nghiệm.
– Nếu θε = 0 đặt λk = λk , tk = tk , chuyển sang bước 2.
ε
ε
Trường Đại học Thăng Long

145