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

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
x∈E(C,X)
⟨d, x⟩, (P)
trong đó d ∈ R n, 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:
Vmax
x∈X
Cx, (LP)
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
tử không âm của R n. 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ủaX .
Đị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:
λ¯TCx0 ≥ λ¯TCx, ∀x ∈ X
với Λ = {λ = (λ1, . . . , λp) | λ1 + · · ·+ λp = 1, λi ≥ 0, ∀i = 1, p}
Λ0 là phần trong tương đối của Λ.
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{dTx |λTCx ≥ g(λ), x ∈ X,λ ∈ Λ0}
trong đó g(λ) = max{λTCy |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ạiM > 0 và λ¯ ∈ ΛM sao cho:
λ¯TCx0 ≥ λ¯TCx, ∀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
x∈E(C,X)
⟨d, x⟩, γ0 = min
x∈X
⟨d, x⟩, β0 = max
x∈X
⟨d, 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
∗, 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 dTx ≥ αk với αk = (γk + βk)/2 (Pk)
 Nếu bài toán (Pk) có nghiệm là xk thì đặt γk+1 = dTxk, β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⟩ ≥ α}
]
chứa d
Ta có:
Eα = {x ∈ X |∃λ ∈ Λ0 : λTCx ≥ λTCy, ∀y ∈ X, ⟨d, x⟩ ≥ α}
= {x ∈ X |∃λ ∈ Λ0 : λTCx ≥ g(λ), ⟨d, x⟩ ≥ α}
trong đó g(λ) = max{λTCy | y ∈ X}.
Đặt: hα(λ) = max{λTCx | 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(λ) ≤ λTCx.
Lấy t = g(λ) suy ra (λ, t) ∈ Ω. Hơn nữa:
t ≤ λTCx, x ∈ X, ⟨d, x⟩ ≥ α
nên:
t ≤ max{λTCx | 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α(λ)
Gọi x∗ là nghiệm tối ưu của bài toán:
max{λTCx | x ∈ X, ⟨d, x⟩ ≥ α}
ta có:
t ≤ hα(λ) = λTCx∗, ⟨d, x∗⟩ ≥ α, x∗ ∈ X
suy ra g(λ) ≤ λTCx∗, λ ∈ Λ, ⟨d, x∗⟩ ≥ α, x∗ ∈ X , tức là
x∗ ∈ Eα(C,X) hay Eα(C,X) ̸= ∅.
Giả sử x0 ∈ X và Sk = {(λ, t) |λ ∈ Λ, t ≥ λTCx0, }, 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ĩaWk như sau:
Wk = {(λ, t) ∈ Vk | t− hα(λ) ≤ 0}
Hệ quả 1. NếuWk = ∅ thì Ω \ Ωα = ∅.
Chứngminh: Do tậpSk có hướng lùi xa duy nhất là vectou 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ếuWk = ∅ 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ếuWk ̸= ∅ 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)TCx | 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 yk là nghiệm tối ưu của
bài toán quy hoạch tuyến tính:
max{(λk)TCy | y ∈ X}
suy ra g(λk) = (λk)TCyk, do đó (λk)TCyk− tk = g(λk)− tk > 0.
Mặt khác, ∀(λ, t) ∈ Ω ta có λTCyk − t ≤ g(λ)− t ≤ 0
Như vậy siêu phẳng {(λ, t) | λTCyk − 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) | λTCyk − t ≤ 0}
Mệnhđề 2. Giả sử tất cả các đỉnh củaSk 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 = q1v1 + · · · + qmvm. 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) | λ ∈
Λ, λTCv ≤ 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:
Sεk = Sk ∩ {(λ, t)|λi ≥ ε}, V εk = V (Sεk)
Giải bài toán:
θ = min{t− hα(λ) | (λ, t) ∈ V εk }
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.
Bước 2: Giải bài toán quy hoạch tuyến tính: max{(λk)TCy | y ∈ X} được
nghiệm tối ưu yk và giá trị tối ưu η = g(λk).
 Nếu η ≤ tk ta có (λk, tk) ∈ Ω \ Ωα, gọi x∗ là nghiệm tối ưu của bài
toán:
max{(λk)TCx | x ∈ X, ⟨d, x⟩ ≥ α}
tức là x∗ ∈ Eα(C,X), dừng thuật toán.
 Nếu η > tk, chuyển sang bước 3.
Bước 3: Xây dựng tập:
Sk+1 = Sk ∩ {(λ, t) | λTCyk − t ≤ 0}
xác định tập đỉnh Vk+1 của Sk+1, gán k := k + 1, quay về bước 1.
Mệnh đề 3. Thủ tục OA dừng sau hữu hạn vòng lặp và cho nghiệm của bài toán
(Pk) hoặc chỉ ra bài toán (Pk) vô nghiệm.
Chứng minh: Ta chỉ cần chứng minh bước 3 của thuật toán không thể lặp vô
hạn lần. Thật vậy, theo cách xây dựng trong thủ tục, Sk+1 có được từ Sk bằng
cách thêm vào một siêu phẳng cắt t = λTCyk, do có siêu phẳng này nên điểm
(λ, tk) ∈ Sk bây giờ không thuộc Sk+1, tức là Sk+1 là tập con thực sự của Sk
nhờ có siêu phẳng cắt t = λTCyk, như vậy sau mỗi bước lặp các siêu phẳng
cắt này phải khác nhau. Mặt khác mỗi siêu phẳng này được xác định duy nhất
theo yk. Tóm lại, ở mỗi bước lặp giá trị yk phải khác nhau mà yk là một đỉnh
của đa diệnX có hữu hạn đỉnh. Vậy bước 3 của thuật toán lặp lại nhiều nhất là
bằng số đỉnh củaX .
Do bước 3 hữu hạn nên thuật toán dừng ở bước 1 hoặc bước 2.
Nếu thuật toán dừng ở bước 1 thì bài toán (Pk) vô nghiệm.
Nếu thuật toán dừng ở bước 2 thì bài toán (Pk) có nghiệm.
Nhận xét
 Nghiệm tối ưu xk của bài toán quy hoạch tuyến tính:
max{(λk)TCx | x ∈ X, ⟨d, x⟩ ≥ α}
chưa chắc đã phải đỉnh củaX . Tuy nhiên nhờ thủ tục tìm kiếm của Benson
ta có thể tìm được điểm Pareto x∗ thuộc tập đỉnh V (X) củaX mà tốt hơn
xk(theo nghĩa ⟨d, x∗⟩ ≥ ⟨d, xk⟩).
 Vậy khiX là đa diện lồi thì bài toán (P) luôn có nghiệm tại một đỉnh nào
đó củaX .
 Tại vòng lặp thứ k, đặt:
uk = min{⟨d, x⟩ − ⟨d, xk⟩ |x ∈ V (X), ⟨d, x⟩ > ⟨d, xk⟩}
khi đó nếu βk − γk < uk thì xk chính là điểm Pareto cần tìm bởi vì
nếu x¯ ̸= xk là đỉnh của X và là nghiệm của bài toán (P) thì ⟨d, x¯⟩ −
⟨d, xk⟩ ≤ βk − γk < uk, vô lý.
Thuật toán tìm kiếm chia đôi giải bài toán tối ưu tuyến tính trên tập Pareto:
Khởi tạo: Tìm V (X) và v ∈ V (X) sao cho Cv ̸= 0. Đặt:
γ0 = min{⟨d, x⟩ | x ∈ V (X)}, β0 = max{⟨d, x⟩ | x ∈ V (X)},
S0 = {(λ, t) | λ ∈ Λ, λTCv ≤ t},
tìm các đỉnh V0 của S0, chọn u0 = β0 − γ0 và gán xopt = x0 = v, k = 0.
Vòng lặp k:
1. Bước k.1:
 Nếu βk − γk < uk, dừng thuật toán, xopt là nghiệm của (P).
 Nếu βk − γk ≥ uk, chuyển sang bước k.2.
2. Bước k.2: Đặt αk = (βk + γk)/2, Vk = V (Sk) và giải bài toán:
θ = min{t− hαk(λ) | (λ, t) ∈ Vk}
tìm các giá trị θ, λk, tk là nghiệm của bài toán trên, chuyển sang bước k.3
3. Bước k.3:
 Nếuθ > 0 hoặcθ = 0 nhưngφ(λ, t) > 0, ∀(λ, t) ∈ V (Sk), (λ, t) ̸=
(λk, tk) đặt:
Sk+1 = Sk, βk+1 = αk, γk+1 = γk, uk+1 = uk, k := k + 1
rồi về bước k.1.
 Nếu θ < 0 hoặc θ = 0 và có λk ∈ Λ0, chuyển sang bước k.4.
 Nếu θ = 0 và không thuộc 2 trường hợp trên thì chọn ε > 0 đủ nhỏ
và đặt:
Sεk = Sk ∩ {(λ, t)|λi ≥ ε}, V εk = V (Sεk)
Giải bài toán:
θ = min{t− hαk(λ) | (λ, t) ∈ V εk }
ta được nghiệm θε, λkε , tkε
{ Nếu θε > 0 thì đặt:
Sk+1 = Sk, βk+1 = αk, γk+1 = γk, uk+1 = uk, k := k+1
rồi về bước k.1.
{ Nếu θε = 0 đặt λk = λkε , tk = tkε , chuyển sang bước k.4
4. Bước k.4: Tìm nghiệm tối ưu yk và giá trị tối ưu η của bài toán:
η = max{(λk)TCy | y ∈ X}
 Nếu η ≤ tk, chọn xopt = argmax{(λk)TCx | ⟨d, x⟩ ≥ αk}.
uk+1 = min{⟨d, x⟩−⟨d, xopt⟩ |x ∈ V (X), ⟨d, x⟩ > ⟨d, xopt⟩}
Sk+1 = Sk, βk+1 = βk, γk+1 = ⟨d, xopt⟩, k := k + 1
rồi về bước k.1.
 Nếu η > tk chuyển sang bước k.5.
5. Bước k.5:
Sk+1 = Sk ∩ {(λ, t) | λTCyk ≤ t}, βk+1 = βk, γk+1 = γk
uk+1 = uk, k := k + 1, trở về bước k.2.
3 Ví dụ
Xét bài toán: max{x1 − x2 + x3 |(x1, x2, x3) ∈ E(C,X)}
trong đó E(C,X) là điểm Pareto của bài toán:
Vmax
x∈X
{x1 − x3, x2}
với:X = {(x1, x2, x3) | x1 + x2 ≤ 3, 0 ≤ x1, x2, x3 ≤ 2}.
Khởi tạo:
Với giả thiết của bài toán ta có:
X = {(x1, x2, x3)|x1 + x2 ≤ 3, 0 ≤ x1, x2, x3 ≤ 2}, d = (1,−1, 1),
C =
(
1 0 −1
0 1 0
)
Các đỉnh củaX là: A(0, 0, 0), B(2, 0, 0), C(2, 1, 0), D(1, 2, 0), E(0, 2, 0),
F (0, 2, 2), G(0, 0, 2),H(2, 0, 2), I(2, 1, 2),K(1, 2, 2).
Đặt f(x1, x2, x3) = x1 − x2 + x3, ta có:
f(A) = 0, f(B) = 2, f(C) = 1, f(D) = −1, f(E) = −2,3
f(F ) = 0, f(G) = 2, f(H) = 4, f(I) = 3, f(K) = 1.
β0 = max{⟨d, x⟩ |x ∈ V (X)} = 4 tại điểm x0 = (2, 0, 2)
γ0 = min{⟨d, x⟩ |x ∈ V (X)} = −2 tại điểm x = (0, 2, 0)
Chọn v = (1, 2, 0), Cv =
(
x1 − x3
x2
)
, Cx0 =
(
1
2
)
Đặt: Λ = {(λ1, λ2) |λ1, λ2 ≥ 0, λ1 + λ2 = 1}
S0 = {(λ, t)|λ ∈ Λ, t ≥ Cx0} = {(λ, t)|λ ∈ Λ, t ≥ λ1 + 2λ2}
Chọn u0 = 4− (−2) = 6, xopt = x0 = v(chưa phải điểm pareto), k = 0.
Vòng lặp 0: Do u0 ≤ β0 − γ0 nên V0 = V (S0) = {(1, 0, 1), (0, 1, 2)}
α0 = 1/2(β0 + γ0) = 1, φ(λ, t) = t− hα0(λ)
trong đó hα0(λ) = max{λTCx |x ∈ X,x1 − x2 + x3 ≥ 1}
giải bài toán: θ = min{φ(λ, t) | (λ, t) ∈ V0}
hα0(1, 0) = max{x1 − x3 |x ∈ X,x1 − x2 + x3 ≥ 1} = 2,
hα0(0, 1) = max{x2 |x ∈ X,x1 − x2 + x3 ≥ 1} = 2.
θ = min{φ(1, 0, 1), φ(0, 1, 2)} = −1 khi λ0 = (1, 0), t0 = 1.
η = max{λ0Cy |y ∈ X} = max{y1 − y3 |y ∈ X} = 2
đạt được tại y0 = (2, 0, 0), do η = 2 > t0 = 1 nên đặt:
S1 = S0∩{(λ, t) |λTCy0 ≤ t} = {(λ, t)|λ ∈ Λ, λ1+2λ2 ≤ t, 2λ1 ≤ t}
Đặt: β1 = β0, γ1 = γ0, u1 = u0.
Vòng lặp 1: Do 6 = u1 ≤ β1 − γ1 = 4− (−2) nên đặt:
V1 = V (S1) = {(1, 0, 2), (0, 1, 2), (2/3, 1/3, 4/3)},
α1 = 1/2(β1 + γ1) = 1, φ(λ, t) = t− hα1(λ)
trong đó hα1(λ) = max{λTCx |x ∈ X,x1 − x2 + x3 ≥ 1}
hα1(1, 0) = 2, hα1(0, 1) = 2
hα1(2/3, 1/3) = max{23(x1 − x3) + 13x2) |x ∈ X,x1 − x2 + x3 ≥
1} = 5/3 khi x = (2, 1, 0)
θ = min{φ(λ, t) | (λ, t) ∈ V1} = −1/3, tại λ1 = (2/3, 1/3), t1 = 43 .
η = max{λ1Cy |y ∈ X} = max{23(y1 − y3) + 13y2 |y ∈ X} = 5/3,
tại y1 = (2, 1, 0).
Do η = 5/3 ≤ t1 = 4/3 nên đặt: S2 = S1 ∩ {(λ, t) |λTCy1 ≤ t} =
{(λ, t) |λ ∈ Λ, λ1 + 2λ2 ≤ t, 2λ1 + λ2 ≤ t}
β2 = β1, γ2 = γ1, u2 = u1
Vòng lặp 2: Do 6 = u2 ≤ β2 − γ2 = 4− (−2) nên đặt:
V2 = V (S2) = {(1, 0, 2), (0, 1, 2), (1/2, 1/2, 3/2)},
α2 = 1/2(β2 + γ2) = 1, φ(λ, t) = t− hα2(λ)
trong đó: hα2(λ) = max{λTCx |x ∈ X,x1 − x2 + x3 ≥ 1}
hα2(1, 0) = 2, hα2(0, 1) = 2, hα2(1/2, 1/2) = 3/2, khi x = (2, 1, 0)
Khi đó: θ = min{φ(λ, t) | (λ, t) ∈ V2} = 0 đạt được tại λ2 =
(1/2, 1/2) ∈ Λ0 nên ta được điểm hữu hiệu là xopt = (2, 1, 0).
Ta đặt: β3 = β3 = 4, γ3 = ⟨d, xopt⟩ = 1, S3 = S2
u3 = min{⟨d, x⟩ − ⟨d, xopt⟩ |x ∈ V (X), ⟨d, x⟩ > ⟨d, xopt⟩} = 1
Vòng lặp 3: Do 1 = u3 ≤ β3 − γ3 = 4− 1 nên đặt:
V3 = V (S3) = {(1, 0, 2), (0, 1, 2), (1/2, 1/2, 3/2)},
α3 = 1/2(β3 + γ3) = 5/2, φ(λ, t) = t− hα3(λ)
trong đó: hα3(λ) = max{λTCx |x ∈ X,x1 − x2 + x3 ≥ 5/2}
hα3(1, 0) = 3/2, hα3(0, 1) = 5/4, hα3(1/2, 1/2) = 3/4
Khi đó: θ = min{φ(λ, t) | (λ, t) ∈ V3} = 3/4 > 0 nên
Eα3(C,X) = {x ∈ EC(X) | ⟨d, x⟩ ≥ 5/2} = ∅.
Ta đặt: β4 = α3 = 5/2, γ4 = γ3 = 1, u4 = u3 = 1, S4 = S3.
Vòng lặp 4: Do 1 = u4 ≤ β4 − γ4 = 5/2− 1 nên đặt:
V4 = V (S4) = {(1, 0, 2), (0, 1, 2), (1/2, 1/2, 3/2)},
α4 = 1/2(β4 + γ4) = 7/4, φ(λ, t) = t− hα4(λ)
trong đó: hα4(λ) = max{λTCx |x ∈ X,x1 − x2 + x3 ≥ 7/4}
hα4(1, 0) = 2, hα4(0, 1) = 13/8, hα4(1/2, 1/2) = 9/8
θ = min{φ(λ, t) | (λ, t) ∈ V3} = 0 đạt được tại (1, 0, 2) /∈ Ω
nhưng φ(0, 1, 2) > 0, φ(1/2, 1/2, 3/2) > 0 nên theo hệ quả 2 φ(λ, t) >
0, ∀(λ, t) ∈ Ω, tức là:
Eα2(C,X) = {x ∈ EC(X) | ⟨d, x⟩ ≥ 7/4} = ∅.
Ta đặt: β5 = α4 = 7/4, γ5 = γ4 = 1, u5 = u4 = 1, S5 = S4.
Vòng lặp 5: Do 1 = u5 > β5 − γ5 = 7/4− 1 nên thuật toán dừng. Ta có
điểm tối ưu Pareto chính xác là xopt = (2, 1, 0) với giá trị lớn nhất của hàm
mục tiêu là ⟨d, xopt⟩ = 1.
Tài liệu tham khảo
[1] T.Q. Phong, H.Q. Tuyen,(2000), Bisection search algorithm for opti-
mizing over the efficient set, Vietnam Journal of Mathematics 28:3, 217-226.
[2] H.P. Benson,(1991), An all-linear programming relaxation algorithm
for optimizing over the efficient set, J. of Global Optimization 1, 83-104.
Abstract. In this report we present some improvements in splite algorithm for
optimizing a linear function over a Pareto set [1]. The problem is stated as fol-
lows :
max
x∈E(C,X)
⟩d, x⟨, (P)
where d ∈ R n, E(C,X) is the Pareto set of linear multiobjective program-
ming problem:
Vmax
x∈X
Cx, (LP)
whereC is matrix p×n, p is the number of objective function,X is a bounded
polyhedral convex set in R n.
We present some important properties of the problem, theoretical basis and stan-
tionary condition of the algorithm. Finally, an illustrative example are given as
well.
Keyword: polyhedral convex set, Pareto set, optimization, linear function, splite
algorithm, optimal solution.