Chương 3. Bài toán tối ưu có điều kiện cho bởi phương trình và bất phương trình
3.5. Giải thuật cho bài toán tối ưu có điều kiện cho bởi phương trình và bất phương trình
Trong phần này, chúng ta nghiên cứu các phương pháp hàm phạt, bao gồm phương pháp hàm phạt điểm ngoài và phương pháp hàm phạt điểm trong, để tìm nghiệm số cho bài toán tối ưu sau:
minf(x) h(x) = 0 g(x) ≤ 0 x ∈ S.
(3.121)
trong đúh(x) = (h1(x),ã ã ã , hm(x)), g(x) = (g1(x),ã ã ã , gr(x)). Ở đõy,f, hi, gj : S ⊂Rn −→ R, i = 1,ã ã ã , m, j = 1,2,ã ã ã , r.
Các bài toán tối ưu không ràng buộc thường đơn giản hơn các bài toán tối ưu có ràng buộc. Phương pháp hàm phạt hướng đến việc biến đổi một bài toán tối ưu có ràng buộc thành một dãy các bài toán có ràng buộc đơn giản hoặc bài toán tối ưu không ràng buộc.
3.5.1. Phương pháp hàm phạt điểm trong
Phương pháp hàm phạt điểm trong tìm cách để đưa bài toán có ràng buộc cho bởi bất phương trình về bài toán không ràng buộc hoặc một dãy các bài toán không ràng buộc. Xét bài toán (3.121) chỉ với ràng buộc cho bởi bất đẳng thức. Đặt Do = {x ∈ S : g(x) < 0}. Một hàm B : Do −→ R thỏa mãn các điều kiện sau
a) B liên tục trên Do.
b) Với mọi dãy {xk} ⊂ Do mà limxk = x /∈ Do thì
lim infB(xk) = +∞, (3.122) được gọi là hàm phạt điểm trong của bài toán (3.121). Để giải bài toán (3.121) trong trường hợp này, ta xét bài toán sau
(infθ(à) à > 0 ,
với θ(à) := inf{f(x) +àB(x), x ∈ S}.
Trong một số trường hợp đặc biệt, hàm B được xác định như sau B(x) =
m
P
i=1
φ(gi(x)) với φ là một hàm liên tục trên {y, y <0} thỏa
φ(y) ≥ 0, lim
y→0−φ(y) = ∞. (3.123)
Ví dụ 3.2. Hai hàm phạt điểm trong thường được dùng:
a) Hàm Fiacco
B(x) =−
m
P
i=1
ln(−gi(x)). b) Hàm McCormick
B(x) =
m
P
i=1
−1 gi(x).
Từ (3.123) ta thấy φ chỉ cần xác định trong một lân cận đủ nhỏ của y = 0.
Bổ đề 3.5. Cho f, g là các hàm liên tục trên S ⊂ Rn, S ̸= ∅. Giả sử Do := {x|g(x) < 0} ̸= ∅ và B thỏa mãn (3.122), liên tục trên Do. Hơn nữa, giả sử cho à > 0, nếu dóy {xk} ⊂ S thỏa g(xk) < 0 và f(xk) +àB(xk) −→
θ(à) thỡ {xk} cú một dóy con hội tụ. Khi đú a) ∀à > 0,∃xà ∈ S thỏa g(x) < 0 và
θ(à) = f(xà) + àB(xà) = inf{f(x) +àB(x)|g(x) < 0, x ∈ S}. b) inf{f(x)|g(x) < 0, x ∈ S} ≤ inf{θ(à), à > 0}.
c) ∀à > 0, f(xà) và θ(à) là cỏc hàm khụng giảm đối với à; B(xà) là hàm khụng tăng đối với à.
Chứng minh. Ta chứng minh lần lượt các mệnh đề của định lý.
1. Với à > 0, từ định nghĩa của hàm θ, tồn tại dóy {xk} ⊂ S thỏa g(xk) < 0 và f(xk) + àB(xk) −→θ(à).
Từ giả thiết, {xk} cú một dóy con hội tụ {xkn} −→ xà ∈ S.
Do gj, j = 1, ..., m liờn tục nờn gj(xà) ≤ 0, j = 1, ..., m. Ta sẽ chứng minh gj(xà) < 0, j = 1, ..., m. Thật vậy, giả sử tồn tại j ∈ {1, ..., m} sao cho
gj(xà) = 0. Vỡ B thỏa (3.122) nờn B(xkn) −→+∞, tức là θ(à) = +∞, điều này vụ lý vỡ D ̸= ∅. Vậy θ(à) = f(xà+àB(xà)).
2. Với à > 0,∀x ∈ S mà g(x) < 0, vỡ B(x) ≥ 0 nờn θ(à) = inf{f(x) +àB(x)|g(x) < 0, x ∈ S}
≥ inf{f(x) : g(x) < 0, x ∈ S}
≥ inf{f(x) : g(x) ≤ 0, x ∈ S}
Cỏc bất đẳng thức trờn đỳng với mọi à > 0 nờn ta cú
inf{f(x) : g(x) < 0, x ∈ S} ≤ infθ(à), à > 0. 3. Xột à > λ > 0,∀x ∈ S mà g(x) < 0, B(x) ≥ 0 nờn ta cú
f(x) + àB(x) ≥f(x) +λN(x),
nờn θ(à) ≥θ(λ). Từ (1), tồn tại xà, xλ ∈ S thỏa g(xà) < 0, g(xλ) < 0 và f(xà) +àB(xà) ≤f(xλ) +àB(xλ), (3.124) f(xλ) +λB(xλ) ≤f(xà) +λB(xà). (3.125) Từ (3.124) và (3.125) ta có
(à−λ)(B(xà)−B(xλ)) ≤ 0.
Vỡ à−λ > 0 nờn B(xà) ≤ B(xλ) và từ (3.125) ta cú f(xλ) ≤f(xà).
2 Từ Bổ đề trên, do θ là hàm không tăng nên ta có
à>0inf θ(à) = lim
à→0+θ(à).
Định lí 3.15. Cho f : Rn −→ R, g : Rn −→ Rm là các hàm liên tục, S ⊂ Rn, S ̸= ∅. Giả sử Do := {x ∈ S|g(x) < 0} ̸= ∅. Hơn nữa, giả sử bài
toán
minf(x) g(x) ≤ 0 x ∈ S
(3.126)
có nghiệm tối ưu x có các tính chất sau: Với mọi lân cận V của x, tồn tại x ∈ V ∩S thỏa g(x) < 0. Khi đó,
min{f(x) : g(x ≤ 0, x ∈ S)}= lim
à→0+θ(à) = inf
à>0θ(à).
Đặt θ(à) = f(xà) +àB(xà) với xà ∈ S thỏa g(xà) < 0. Khi đú, giới hạn của dãy con bất kỳ của dãy {xk} là nghiệm tối ưu của bài toán (3.126), hơn nữa àB(xà) −→0 khi à−→ 0+.
Chứng minh. Cho x là một nghiệm tối ưu của bài toán (3.126) thỏa mãn các
điều kiện đã cho, ϵ > 0. Từ các điều kiện của định lý và tính liên tục của f, tồn tại bx ∈ S, g(bx) < 0 thỏa
f(x) +ϵ > f(x)b , với à > 0 ta cú
f(x) +ϵ+àB(bx) > f(x) +b àB(x)b ≥ θ(à). Cho à−→ 0+ ta cú
f(x) + ϵ≥ lim
à→0+θ(à).
Vì bất đẳng thức trên đúng với mọi ϵ > 0 nên ta có f(x) ≥ lim
à→0+θ(à). Từ (2) của Bổ đề 3.5 ta có f(x) = lim
à→0+θ(à). Ta có
θ(à) = f(xà) + àB(xà) ≥ f(xà) ≥ f(x), vì f(x) = lim
à→0+θ(à) nờn
à→0lim+f(xà) = lim
à→0+f(xà) +àB(xà) =f(x). Từ đó ta có lim
à→0+àB(xà) = 0.
Nếu {xk} có một dãy con có giới hạn là x′ thì từ tính liên tục của f ta có f(x′) = f(x) hay x′ là một nghiệm tối ưu của bài toán (3.126).
2 Giải thuật giải bài toán tối ưu phi tuyến có ràng buộc bằng phương pháp hàm phạt điểm trong:
- Bước khởi tạo: Cho ϵ > 0, chọn x1 ∈ S thỏa g(x) < 0. Cho à1 >
0, β ∈ (0,1), k = 1, chuyển sang bước chính.
- Thực hiện vòng lặp:
Bước 1 Bắt đầu với xk, giải bài toán
min [f(x) +àkB(x)]
h(x) = 0 x ∈ S
gọi xk+1 là một nghiệm của bài toán trên, chuyển sang bước 2.
Bước 2 Nếu àkB(xk+1) < ϵ, dừng.
Ngược lại, đặt àk+1 = βàk, thay k := k+ 1 quay lại Bước 1.
3.5.2. Phương pháp hàm phạt điểm ngoài
Xét bài toán (3.121), hàm phạt điểm ngoài được xác định như sau p(x) =
m
X
i=1
ϕ(gi(x)) +
r
X
i=1
ψ(hi(x)), (3.127) với ϕ, ψ là các hàm liên tục trên R thỏa
ϕ(y) = 0,∀y ≤ 0 ϕ(y) > 0,∀y > 0
ψ(y) = 0,∀y = 0 ψ(y) > 0,∀y ̸= 0. (3.128) Một ví dụ cho các hàm ϕ, ψ thỏa mãn các điều kiện trên là
ϕ(y) = (max{0, y})q, ψ(y) = |y|q,
với q là một hằng số dương.
bài toán (3.121) được đơn giản các ràng buộc thành bài toán sau (supθ(à)
à≥ 0,
với θ(à) = inf{f(x) +àp(x), x ∈ S}, p xỏc định bởi (3.127) và thỏa điều kiện (3.128).
Bổ đề 3.6. Giả sử f, g, h là các hàm liên tục trên Rn, S ⊂ Rn, S ̸= ∅. Cho hàm p xỏc định bởi (3.127), liờn tục trờn Rn và giả sử ∀à,∃xà ∈ S thỏa
θ(à) =f(xà) +àp(xà). Khi đó, các mệnh đề sau luôn đúng
a) inf{f(x) : x ∈ S, g(x) ≥0, h(x) = 0} ≥ sup
à≥0
θ(à).
b) f(xà), θ(à) là hàm khụng tăng với mọi à ≥ 0, p(xà) là hàm khụng giảm với mọi à≥ 0.
Chứng minh. Ta sẽ chứng minh lần lượt từng mệnh đề
1. ∀x ∈ S thỏa g(x) ≤ 0, h(x) = 0, p(x) = 0. Xột à ≥ 0 ta cú f(x) = f(x) + àp(x) ≥ inf{f(y) +àp(y), y ∈ S} = θ(à). Vậy mệnh đề được chứng minh.
2. Xột 0 ≤ λ ≤à ta cú
f(xà) +λp(xà) ≥ f(xλ) +λp(xλ) (3.129) f(xλ) +àp(xλ) ≥ f(xà) +àp(xà). (3.130)
Cộng theo vế của (3.129) và (3.130) ta có
(à−λ)[p(xλ)−p(xà)] ≥ 0
⇒p(xλ) ≥ p(xà) Từ (3.129) ta cú f(xà) ≥ f(xλ).
Từ (3.130) ta có
f(xà) + àp(xà) + (λ−à)p(xà) ≥ θ(λ), vỡ à > λ và p(xà) ≥ 0 nờn θ(à) ≥θ(λ).
2 Định lí 3.16. Xét bài toán (3.121), hàm p cho bởi (3.127), thỏa mãn điều kiện (3.128). Hơn nữa, giả sử ∀à ≥ 0, tồn tại nghiệm của bài toỏn min (f(x) +àp(x)) và dóy {xà}à≥0 chứa trong một tập con compact của S. Khi đó,
inf{f(x) : x ∈ S, g(x) ≥ 0, h(x) = 0} = sup
à≥0
θ(à) = lim
à→∞θ(à), trong đú θ(à) = inf{f(x) +àp(x), x ∈ S} = f(xà) +àp(xà).
Hơn nữa, x = limxà là một nghiệm tối ưu của Bài toỏn (3.121) và àp(xà) →0 khi à→ +∞.
Chứng minh. Từ (2) của Bổ đề 3.6, θ(à) là hàm đơn điệu nờn sup
à≥0
θ(à) = lim
à≥0θ(à). Ta sẽ chứng minh p(xà) → 0 khi à →+∞.
Thật vậy, cho y ∈ S và ϵ > 0. Giả sử x1 là một nghiệm tối ưu của bài toỏn min{f(x) +àp(x), x ∈ S}.
Nếu
à ≥ 1
ϵ |f(y)−f(x1)|+ 2, theo mệnh đề 2 của Bổ đề 3.6 ta cú f(xà) ≥f(x1).
Giả sử p(xà) > ϵ, theo mệnh đề 1 của Bổ đề 3.6 ta cú
inf{f(x) : x ∈ S, g(x) ≥0, h(x) = 0} (3.131)
≥ θ(à)
= f(xà) +àp(xà)
≥ f(x1) +àp(xà)
> f(x1) + |f(y)−f(x1)|+ 2ϵ
> f(y).
Điều này là vụ lý, nờn p(xà) ≤ϵ. Vỡ ϵ > 0 lấy tựy ý nờn ta cú
à→∞lim p(xà) = 0.
Xột{xàk}là một dóy con của dóy{xà}, do{xà}chứa trong một tập compact nờn tồn tại x ∈ S là giới hạn của dóy con {xàk}. Ta cú
sup
à≥0
θ(à) ≥ θ(àk) = f(xàk) +àkp(xàk) ≥ f(xàk), ta cú xàk →x và f liờn tục nờn
sup
à≥0
θ(à) ≥ f(x). (3.132)
Vỡ p(xà) →0 khi à → 0 nờn p(x) = 0, cú nghĩa x là một phương ỏn khả thi của bài toán (3.121). Từ (3.132) và (1) của Bổ đề 3.6 ta có x là một nghiệm tối ưu của Bài toán (3.121) và
sup
à≥0
θ(à) = f(x). Ta có
àp(xà) =θ(à)−f(xà) và
à→∞lim θ(à) = lim
à→∞f(xà) =f(x) nên
à→+∞lim àp(xà) = 0.
2 Hệ quả 3.4. ∀à≥ 0 mà p(xà) = 0 thỡ xà là nghiệm tối ưu của bài toỏn (3.121).
Chứng minh. ∀à ≥0mà p(xà) = 0 thỡ xà là phương ỏn khả thi của Bài toỏn (3.121). Ta có
inf{f(x) : x ∈ S, g(x) ≥ 0, h(x) = 0} ≥ θ(à) =f(xà) +àp(xà) = f(xà), vậy xà là nghiệm tối ưu của Bài toỏn (3.121).
2 Giải thuật giải bài toán (3.121) bằng phương pháp hàm phạt điểm ngoài:
- Bước khởi tạo: Cho ϵ > 0, chọn điểm khởi đầu x1 ∈ S, tham số phạt à1 > 0, hằng số β > 1, cho k = 1, chuyển sang bước chớnh.
- Thực hiện vòng lặp:
Bước 1 Bắt đầu với xk, giải bài toán
min [f(x) +àkp(x)],
gọi xk+1 là một nghiệm của bài toán trên, chuyển sang bước 2.
Bước 2 Nếu àkp(xk+1) < ϵ, dừng. Ngược lại, cho àk+1 := βàk, k := k+ 1, quay lại Bước 1.
Bài tập Chương 3
Câu 3.1. Tìm nghiệm của bài toán
(min 2ex1 + 3x21 + 2x1x2 + 4x22 3x1 + 2x2 −6 = 0.
Dùng phương pháp hàm phạt bậc hai tìm nghiệm xấp xỉ của bài toán.
Câu 3.2. Tìm nghiệm của bài toán
min 1
2(x21 + 1 3x22) x1 +x2 = 1.
Dùng phương pháp hàm phạt bậc hai tìm nghiệm xấp xỉ của bài toán.
Câu 3.3. Tìm nghiệm của bài toán sau
(min(x1 −2)4 + (x1 −2x2)2 x21 −x2 = 0
Dùng phương pháp hàm phạt bậc hai tìm nghiệm xấp xỉ của bài toán.
Câu 3.4. Tìm nghiệm của bài toán
min 2x21 −3x1x2 + x22
x21 −x2 + 3 ≤ 0 3x1 + 2x2 −6 ≤ 0
−x1 ≤ 0
−x2 ≤ 0.
Câu 3.5. Tìm nghiệm của bài toán
minf(x) = (x1 −6)2 + (x2 −7)2 g1(x) = −3x1 −2x2 + 6 ≤0
g2(x) = −x1 + x2 −3 ≤0 g3(x) = x1 +x2 −7 ≤ 0
.
Câu 3.6. Xét bài toán tối ưu
min
5
P
i=1
x2i
x1 + 2x2 +x3 −1 = 0 x3 −x4 +x5 −3 = 0
Xác định hàm Lagrange và hệ điều kiện Kuhn-Tucker của bài toán này. Tìm nghiệm của bài toán.
Câu 3.7. Xét bài toán tối ưu phi tuyến
minf(x) = (x1 + 1)2 + (x2 −1)2 x1 −2 ≤0
x2 −1 ≤0
−x1 ≤0
−x2 ≤0.
Xác định hàm Lagrange và hệ điều kiện Kuhn-Tucker của bài toán này. Tìm nghiệm của bài toán.
Câu 3.8. Xét bài toán tối ưu
minf(x) =x21 +x22
g1(x1, x2) =x21 +x22 ≤5 g2(x1, x2) =−x1 ≤0 g3(x1, x2) =−x2 ≤0 h(x1, x2) = x1 + 2x2 = 4
Xác định hàm Lagrange và hệ điều kiện Kuhn-Tucker của bài toán này. Tìm nghiệm của bài toán.
Câu 3.9. Một nhà máy sản xuất đồ gia dụng có chi phí công nhân mỗi giờ là 50 000 đồng, giá nguyên liệu là 1 700 000 đồng/tấn. Lợi nhuận được mô hình hóa theo công thức
R(h, s) = 2.106.h2/3s1/3 h: số giờ làm việc,
s: số tấn nguyên liệu.
Hãy tính lợi nhuận lớn nhất biết tổng chi phí là 200 000 000 đồng.
Câu 3.10. Một tổ hợp gồm 3 máy phát cần sinh ra lượng điện là 952 Mw trong một giờ. Bỏ qua lượng điện thất thoát, chi phí của mỗi máy phát được cho bởi các công thức sau
f1 :x1 + 0,0625x21( $/ giờ), f2 : x2 + 0,125x22( $/ giờ),
f3 : x3 + 0,25x23( $/ giờ).
với xi, i= 1,2,3 là lượng điện phát ra của máy phát thứ i trong 1 giờ. Tìm phương án phát điện tiết kiệm chi phí nhất.
Câu 3.11. Giải bài toán sau:
min
1 2
4
P
i=1
(x1 −ai)2 + (x2 −bi)2
x1 + x2 −2 = 0
−x1 ≤ 0
−x2 ≤ 0.
Câu 3.12. Cho các số thựca, b, cthỏa mãna+b+c = 0vàa2+b2+c2 = 6. Tìm giá trị lớn nhất của biểu thức
A = a2b+b2c+c2a.
Câu 3.13. Cho a, b, c, d là các số thực dương thỏa a + b + c+ d = 1. Chứng minh rằng
abc+bcd+cda+dab ≤ 176
27abcd + 1 27. Câu 3.14. Tìm nghiệm của bài toán
min [f(x, y) =x−2y]
−1−x+y2 ≤0
−y ≤0
Câu 3.15. Tìm nghiệm của bài toán
minf(x, y, z) =x−2y + 3z+z2 x+y +z−2 = 0
−x≤ 0
−y ≤0
−z ≤ 0
Câu 3.16. Tìm nghiệm của bài toán
(min(x1 −2)4 + (x1 −2x2)2 x21 −x2 ≤ 0.
Câu 3.17. Dùng phương pháp hàm phạt điểm trong và phương pháp hàm phạt điểm ngoài tìm nghiệm số của các bài tập trên. So sánh hai phương pháp này với phương pháp nhân tử Lagrange tăng cường cho các bài toán
tối ưu có điều kiện cho bởi phương trình.