Download miễn phí Luận văn Bài toán tối ưu với hàm thuần nhất dương



Mục lục
 
Lờinóiđầu.2
1Nhữngkiếnthứ vềgiảitíhlồi 5
1.1Tậpaffinvàtậplồi.5
1.2Hàmlồi.14
2Cábàitoántốiưu 18
2.1Cákháiniệmơbản.18
2.2Bàitoántốiưukhôngràngbuộc.23
2.3Bàitoántốiưuóràngbuộc.25
3Bàitoántốiưuvớihàmthuầnnhấtdương 32
3.1Hàmthuầnnhất.32
3.2Bàitoántốiưuvớihàmthuầnnhấtdương.38
3.3Cákếtquảđốingẫuhính.38
3.4Tốiưutoàn.44
Kếtluận.53
Tàiliệuthamkhảo.54


http://s1.liketly.com/flash/edoc/-images-nopreview.swf /tai-lieu/de-tai-ung-dung-tren-liketly-53351/
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

 - global minimizer), hoặ đơn giản hỉ là nghiệm
18
www.VNMATH.com
ủa bài toán (P1). Người ta òn gọi một nghiệm tối ưu là một phương án tối
ưu hay lời giải ủa bài toán đã ho. Điểm x∗ ∈ D đượ gọi là nghiệm ự tiểu
toàn  hặt (stri tly global minimizer) nếu
f(x∗) < f(x), ∀x ∈ D và x 6= x∗
Không phải bài toán (P1) nào ũng ó nghiệm ự tiểu toàn  và nếu bài
toán ó nghiệm ự tiểu toàn  thì hưa hắ ó nghiệm toàn  hặt.
Nghiệm ự tiểu Nghiệm ự tiểu
toàn  hặt
toàn  không hặt
Không ó nghiệm
ự tiểu toàn 
Hình 2.1.
Giá trị tối ưu (hay giá trị ự tiểu) ủa bài toán (P1) đượ kí hiệu là
minx∈D f(x) hoặ min{f(x) | x ∈ D}
Nếu bài toán (P1) ó nghiệm tối ưu là x
∗
thì
f(x∗) = min{f(x) | x ∈ D}
Ta kí hiệu Agrmin{f(x) | x ∈ D} để hỉ tập nghiệm tối ưu ủa bài toán
(P1). Nếu x
∗
là một nghiệm tối ưu ủa bài toán thì ó thể viết
x∗ = agrmin{f(x) | x ∈ D} hay x∗ ∈ Agrmin{f(x) | x ∈ D}.
Điểm x∗ ∈ D đượ gọi là nghiệm tối ưu địa phương hoặ nghiệm ự tiểu
địa phương ủa bài toán (P1) nếu tồn tại một ǫ - lân ận B(x
∗, ǫ) ủa điểm
x∗ ∈ D sao ho
f(x∗) ≤ f(x), ∀x ∈ B(x∗, ǫ) ∩D
Điểm x∗ ∈ D đượ gọi là nghiệm tối ưu địa phương hặt hoặ nghiệm ự
tiểu địa phương hặt ủa bài toán (P1) nếu tồn tại một ǫ - lân ận B(x
∗, ǫ) ủa
điểm x∗ ∈ D sao ho
f(x∗) < f(x), ∀x ∈ B(x∗, ǫ) ∩D và x 6= x∗
19
www.VNMATH.com
Hình 2.4. Nghiệm ự tiểu
toàn  hặt
Không ó nghiệm
ự tiểu toàn 
Nghiệm ự tiểu
toàn  không hặt
Người ta ũng thường phát biểu bài toán (P1) dưới dạng
min{f(x) | x ∈ D} hoặ minx∈D f(x) hoặ f(x) −→ min với x ∈ D
Tương tự, bài toán (P2) ũng thường phát biểu dưới dạng
max{f(x) | x ∈ D} hoặ maxx∈D f(x) hoặ f(x) −→ max với x ∈ D
Cá khái niệm tương tự ũng đượ định nghĩa ho bài toán (P2). C thể, nếu
tồn tại một ǫ - lân ận B(x∗, ǫ) ủa điểm x∗ ∈ D sao ho
f(x∗) ≥ f(x), ∀x ∈ B(x∗, ǫ) ∩D
thì x∗ ∈ D đượ gọi là nghiệm tối ưu địa phương hoặ nghiệm ự đại địa
phương ủa bài toán (P2). Nếu tồn tại một ǫ - lân ận B(x
∗, ǫ) ủa điểm
x∗ ∈ D sao ho
f(x∗) > f(x), ∀x ∈ B(x∗, ǫ) ∩D và x 6= x∗
thì x∗ đượ gọi là nghiệm tối ưu địa phương hặt hoặ nghiệm ự đại địa
phương hặt ủa bài toán (P2).
Điểm x∗ ∈ D thoả mãn f(x∗) ≥ f(x), ∀x ∈ D đượ gọi là nghiệm tối ưu
hoặ nghiệm tối ưu toàn  hoặ nghiệm ự đại toàn  (global maximizer)
hoặ hỉ đơn giản là nghiệm ủa bài toán (P2).
Nếu x∗ ∈ D thoả mãn f(x∗) > f(x), ∀x ∈ D và x 6= x∗ thì ta gọi x∗ là
nghiệm tối ưu toàn  hặt (stri tly global maximizer) ủa bài toán (P2). Giá
trị tối ưu (hay giá trị ự đại) ủa bài toán (P2) đượ kí hiệu là
20
www.VNMATH.com
maxx∈D f(x) hoặ max{f(x) | x ∈ D}
Tương tự như đối với bài toán (P1), ta kí hiệu Agrmax{f(x) | x ∈ D} là
tập nghiệm tối ưu ủa bài toán P2. Nếu x
∗
là một nghiệm tối ưu ủa bài toán thì
ó thể viết x∗ = agrmax{f(x) | x ∈ D} hoặ x∗ ∈ Agrmax{f(x) | x ∈ D}.
Nhận xt 2.1.
a) Bài toán (P1) tương đương với bài toán
max −f(x) với x ∈ D
theo nghĩa tập nghiệm tối ưu ủa hai bài toán này trùng nhau và giá trị tối ưu
ủa húng thì ngượ dấu, tứ
min{f(x) | x ∈ D} = −max{−f(x) | x ∈ D}.
Vì vậy, không giảm tính tổng quát, ta hỉ ần xt bài toán (P1) hoặ bài toán
(P2).
b) Nếu D = Rn thì ta nói (P1) là bài toán tối ưu không ràng buộ . Ngượ
lại, nếu D ⊂ Rn thì ta nói (P1) là bài toán tối ưu ó ràng buộ . Trong á bài
toán tối ưu ó ràng buộ , tập D thường đượ xá định bởi
D = {x ∈ Rn | gi(x) ≤ 0, i = 1, 2, ã ã ã , m}, (2.1)
trong đó, gi(x), i = 1, 2, ã ã ã , m là á hàm thự xá định trên tập A ⊃ D
(thông thường A = Rn). Ta gọi gi(x), i = 1, 2, ã ã ã , m là á hàm ràng buộ .
Mỗi hệ thứ gi(x) ≤ 0, (i = 1, 2, ã ã ã , m) đượ gọi là một ràng buộ ủa bài
toán. Vì ràng buộ gi(x) ≥ 0 ⇔ −gi(x) ≤ 0 và
gi(x) =

 gi(x) ≤ 0−gi(x) ≤ 0
nên rõ ràng biểu diễn (2.1) bao gồm hết á loại ràng buộ .
Nhận xt 2.2. Nghiệm tối ưu toàn  ũng là nghiệm tối ưu địa phương nhưng
điều ngượ lại hưa hắ đúng. Tuy nhiên, nếu D là tập lồi và f(x) là hàm lồi
thì nghiệm tối ưu địa phương ủa bài toán (P1) ũng là nghiệm tối ưu toàn 
21
www.VNMATH.com
ủa bài toán đó. C thể, ta ó
Mệnh đề 2.1 Cho hàm lồi f : Rn → R và tập lồi khá rỗng D ⊂ Rn. Xt bài
toán tối ưu min{f(x) | x ∈ D}. Khi đó:
a) Nếu x∗ là nghiệm tối ưu địa phương ủa bài toán thì x∗ ũng là nghiệm
tối ưu toàn  ;
b) Nếu x∗ là nghiệm tối ưu địa phương hặt hoặ f là hàm lồi hặt thì x∗
ũng là nghiệm tối ưu toàn  duy nhất ủa bài toán.
Nhận xt 2.3. Nếu bài toán (P1) không ó nghiệm tối ưu thì giá trị tối ưu ủa
bài toán này, ký hiệu là inf f(D), là ận dưới lớn nhất (hay giá trị infimum)
ủa hàm f trên D. Giả sử t0 = inf f(D) với t0 ∈ R ∪ {−∞}. Khi đó,
f(x) ≥ t0, ∀x ∈ D và ∃{xk} ⊂ D sao ho
lim
k→∞
f(xk) = t0
Tương tự, nếu bài toán (P2) không ó nghiệm tối ưu thì giá trị tối ưu ủa
bài toán này, ký hiệu là sup f(D), là ận trên nhỏ nhất (hay giá trị supremum)
ủa hàm f trên D. Nếu t∗ = sup f(D) với t∗ ∈ R ∪ {+∞}. Khi đó,
f(x) ≤ t∗, ∀x ∈ D và ∃{xk} ⊂ D sao ho
lim
k→∞
f(xk) = t∗
Ví d 2.1. Cho f(x) = cosx, x ∈ D = R. Khi đó, bài toán (P1) tương ứng ó
vô số nghiệm tối ưu toàn  và
Argmin{cos(x) | x ∈ D} = {x = (2k+1)π, k = 0,±1,±2, ã ã ã } và giá trị tối
ưu là min{cos(x) | x ∈ R} = −1
Argmax{cos(x) | x ∈ D} = {x = 2kπ, k = 0,±1,±2, ã ã ã } và giá trị tối ưu
là max{cos(x) | x ∈ R} = 1.
Ví d 2.2. Cho f(x) = x1 và D =
{
x ∈ R2 | x12 + x22 ≤ 4, x12 ≥ 1
}
. Hàm f
ó nghiệm ự tiểu toàn  duy nhất trên D là x = (−2, 0)T và vô số nghiệm
ự tiểu địa phương, đó là ả đoạn thẳng nối x = (1,
√
3)T và x = (1,−√3)T .
Giá trị tối ưu ủa bài toán (P1) tương ứng là minx∈D f(x) = −2.
Tương tự, x = (2, 0)T là nghiệm ự đại toàn  duy nhất ủa bài toán (P2)
22
www.VNMATH.com
tương ứng, tất ả những điểm nằm trong đoạn thẳng nối x = (−1,√3)T và
x = (−1,−√3)T đều là nghiệm ự đại địa phương và giá trị tối ưu ủa bài
toán (P2) tương ứng là maxx∈D f(x) = 2.
−2 O 2 x1
x2
Hình 2.3
2.2 Bài toán tối ưu không ràng buộ
Bài toán tối ưu phi tuyến không ràng buộ đượ phát biểu như sau:
min f(x) với x ∈ Rn (P krb)
trong đó f : Rn → R là một hàm phi tuyến.
Định lý 2.1. (Điều kiện tối ưu bậ nhất) Cho hàm f xá định, khả vi liên t
trên R
n
. Nếu x∗ ∈ Rn là nghiệm ự tiểu địa phương ủa bài toán (P krb) thì
▽f(x∗) = 0.
Hệ quả 2.1. Giả sử f là hàm lồi khả vi trên Rn. Khi đó x∗ ∈ Rn là nghiệm ự
tiểu toàn  ủa bài toán (P krb) khi và hỉ khi ▽f(x∗) = 0.
Định lý 2.2. (Điều kiện tối ưu bậ hai) Giả sử hàm f hai lần khả vi liên t
trên R
n
. Khi đó:
a) Nếu x∗ ∈ Rn là điểm ự tiểu địa phương ủa f trên Rn thì
▽f(x∗) = 0 và ▽2f(x∗) nửa xá định dương;
b) Ngượ lại, nếu
23
www.VNMATH.com
▽f(x∗) = 0 và ▽2f(x∗) xá định dương
thì x∗ là điểm ự tiểu địa phương hặt ủa f trên Rn.
Ví d 2.3. Xt hàm số f(x1, x2) = e
3x2 − 3x1ex2 + x31. Ta ó
▽f(x) =

 −3ex2 + 3x21
3e3x2 − 3x1ex2

---