Tìm kiếm
Đang tải khung tìm kiếm
Kết quả 1 đến 1 của 1

    THẠC SĨ Vai trò của tính lồi trong bài toán tối ưu

    D
    dream dream Đang Ngoại tuyến (18524 tài liệu)
    .:: Cộng Tác Viên ::.
  1. Gửi tài liệu
  2. Bình luận
  3. Chia sẻ
  4. Thông tin
  5. Công cụ
  6. Vai trò của tính lồi trong bài toán tối ưu

    Möc löc
    Líi c£m ìn . ii
    Mð ƒu 1
    Chưìng 1. T“p lçi v h m lçi 3
    1.1. ành ngh¾a v t‰nh ch§t cıa t“p lçi 3
    1.1.1. ành ngh¾a v t‰nh ch§t . 3
    1.1.2. C¡c ành lþ t¡ch . 6
    1.2. ành ngh¾a v t‰nh ch§t cıa h m lçi . 8
    1.2.1. H m lçi . 8
    1.2.2. C¡c t‰nh ch§t . 10
    1.3. C¡c ành lþ cì b£n vã dưîi vi ph¥n h m lçi . 14
    Chưìng 2. Vai trÆ cıa t‰nh lçi trong b i to¡n tŁi ưu 16
    2.1. B i to¡n tŁi ưu lçi . 16
    2.1.1. B i to¡n tŁi ưu hâa ìn möc ti¶u . 16
    2.1.2. V‰ dö . 17
    2.2. iãu ki»n cƒn v ı cho b i to¡n tŁi ưu lçi . 18
    2.3. Thu“t to¡n chi‚u dưîi ⁄o h m 29
    2.3.1. Phưìng ph¡p chi‚u dưîi ⁄o h m . 30
    2.3.2. Thu“t to¡n chi‚u dưîi ⁄o h m . 30
    K‚t lu“n 35
    T i li»u tham kh£o 36ii
    Líi c£m ìn
    Lu“n v«n n y ưæc ho n th nh t⁄i trưíng ⁄i håc Khoa håc, ⁄i
    håc Th¡i Nguy¶n dưîi sü hưîng d¤n cıa GS.TSKH. L¶ Dông Mưu. Tæi
    xin b y tä lÆng bi‚t ìn s¥u s›c Łi vîi thƒy vã sü t“n t¥m v nhi»t t nh
    hưîng d¤n, cung c§p t i li»u, truyãn ⁄t nhœng kinh nghi»m vã m°t
    nghi¶n cøu trong suŁt qu¡ tr nh t¡c gi£ thüc hi»n lu“n v«n.
    Tæi xin ch¥n th nh c£m ìn Ban Gi¡m hi»u, phÆng  o t⁄o Khoa håc,
    Khoa To¡n - tin trưíng ⁄i håc Khoa håc, ⁄i håc Th¡i nguy¶n còng
    c¡c thƒy, cæ gi¡o tham gia gi£ng d⁄y cao håc khâa 2013 - 2015 ¢ quan
    t¥m v gióp ï trong suŁt thíi gian håc t“p t⁄i trưíng.
    CuŁi còng, tæi xin gßi líi c£m ìn tîi gia  nh, b⁄n b–, l¢nh ⁄o trưíng
    THPT Hòng An, B›c Quang, H Giang v c¡c b⁄n çng nghi»p ¢ gióp
    ï t⁄o iãu ki»n cho tæi khi håc t“p v nghi¶n cøu.
    Tæi xin ch¥n th nh c£m ìn!
    Th¡i Nguy¶n, th¡ng 06 n«m 2015
    Håc vi¶n
    Nguy„n L¥m H 1
    Mð ƒu
    Trong thíi ⁄i ng y nay, to¡n håc ng y c ng câ nhiãu øng döng ð c¡c
    l¾nh vüc kh¡c nhau cıa íi sŁng x¢ hºi. °c bi»t, lþ thuy‚t vã c¡c t“p
    lçi v h m lçi câ mºt và tr‰ quan trång trong to¡n håc, li¶n quan ‚n
    hƒu h‚t c¡c ng nh như gi£i t‰ch lçi, tŁi ưu hâa, gi£i t‰ch h m, h nh håc,
    to¡n kinh t‚, . Mºt c¡ch tŒng qu¡t, c¡c h m lçi vîi mºt sŁ t‰nh ch§t
    cì b£n ưæc sß döng rºng r¢i trong to¡n håc lþ thuy‚t công như to¡n
    håc øng döng.
    Trong nhiãu v§n ã øng döng ta thưíng g°p c¡c b i to¡n tŁi ưu lçi,
    t‰nh ch§t b i to¡n tŁi ưu lçi, iãu ki»n cƒn v ı cho b i to¡n tŁi ưu
    lçi, công như vai trÆ cıa t‰nh lçi trong b i to¡n tŁi ưu, nhœng d⁄ng to¡n
    tr¶n câ nhœng t‰nh ch§t cì b£n r§t kh¡c nhau.
    Tuy nhi¶n t‰nh lçi k†o theo nhœng °c thò ri¶ng cho mØi b i to¡n.
    Düa tr¶n c¡c t‰nh ch§t n y, ngưíi ta ¢ ưa ra ưæc nhœng phưìng ph¡p
    gi£i quy‚t kh¡c nhau cho mØi b i to¡n.
    Nh‹m möc ‰ch t m hi”u vã t‰nh lçi trong b i to¡n tŁi ưu to n di»n
    v logic hìn, tæi ¢ chån ã t i "Vai trÆ cıa t‰nh lçi trong b i to¡n tŁi
    ưu" cho lu“n v«n cıa m nh.
    Lu“n v«n bao gçm phƒn mð ƒu, hai chưìng nºi dung, phƒn k‚t lu“n
    v danh möc t i li»u tham kh£o.
    Chưìng 1. Lu“n v«n tr nh b y c¡c ki‚n thøc cì b£n vã gi£i t‰ch lçi:
    ành ngh¾a t“p lçi, h m lçi, c¡c t‰nh ch§t cıa h m lçi, dưîi vi ph¥n cıa
    h m lçi, i‚u ki»n cƒn v ı cho b i to¡n tŁi ưu lçi, b i to¡n tŁi ưu lçi
    như c§u tróc t“p nghi»m, cho phưìng ph¡p chi‚u ⁄o h m v dưîi ⁄o
    h m, gi£i b i to¡n tŁi ưu lçi.
    Chưìng 2. Giîi thi»u vã b i to¡n tŁi ưu lçi, iãu ki»n cƒn v ı cho2
    b i to¡n tŁi ưu lçi v °c bi»t l giîi thi»u thu“t to¡n chi‚u dưîi ⁄o
    h m cho b i to¡n kh£ vi v thu“t to¡n chi‚u dưîi ⁄o h m cho b i to¡n
    tŁi ưu lçi khæng kh£ vi, .
    Th¡i Nguy¶n, th¡ng 06 n«m 2015
    Nguy„n L¥m H
    Håc vi¶n Cao håc To¡n K7A
    Chuy¶n ng nh To¡n øng döng
    Trưíng ⁄i håc Khoa håc - ⁄i håc Th¡i Nguy¶n
    Email: anhthubonghg@gmail.com3
    Chưìng 1
    T“p lçi v h m lçi
    Trong lu“n v«n n y, chóng ta s‡ l m vi»c vîi khæng gian Euclide n -
    chiãu tr¶n trưíng sŁ thüc R , k‰ hi»u l R
    n . Chưìng 1 tr nh b y mºt sŁ
    ki‚n thøc cì b£n nh§t vã t“p lçi v h m lçi còng vîi mºt sŁ t‰nh ch§t
    °c trưng cıa nâ s‡ ưæc sß döng trong lu“n v«n. Nºi dung cıa chưìng
    ưæc tr‰ch d¤n chı y‚u tł t i li»u tham kh£o [1] v [2].
    1.1. ành ngh¾a v t‰nh ch§t cıa t“p lçi
    1.1.1. ành ngh¾a v t‰nh ch§t
    ành ngh¾a 1.1. Cho A ⊂ X, x 1 , x 2 ∈ A.
    (i) o⁄n thflng nŁi hai i”m x 1 , x 2 câ d⁄ng
    {x ∈ X : x = αx 1 + βx 2 , α, β ∈ R , α + β = 1}.
    (ii) ưíng thflng i qua hai i”m x 1 , x 2 ưæc ành ngh¾a
    {x ∈ R : x = αx 1 + βx 2 , α ≥ 0, β ≥ 0, α + β = 1}.
    ành ngh¾a 1.2. Mºt t“p A ưæc gåi l affine n‚u A chøa måi ưíng
    thflng i qua hai i”m x 1 , x 2 b§t k thuºc A, tøc l :
    ∀x 1 , x 2 ∈ A, ∀λ ∈ R th λx 1 + (1 ư λ)x 2 ∈ A.
    ành ngh¾a 1.3. Gi£ sß a ∈ R
    n l mºt vectì kh¡c 0 v α ∈ R . Khi â:4
    ã {x : a T x ≥ α} l nßa khæng gian âng.
    ã {x : a T x > α} l nßa khæng gian mð.
    ành ngh¾a 1.4. T“p A ⊂ X ưæc gåi l lçi n‚u
    ∀x 1 , x 2 ∈ A, ∀λ ∈ R : 0 ≤ λ ≤ 1 th λx 1 + (1 ư λ)x 2 ∈ A.
    V‰ dö 1.1.
    (i) T“p X v ∅ l c¡c t“p lçi.
    (ii) C¡c nßa khæng gian trong R
    2 v R
    3 l c¡c t“p lçi.
    (iii) C¡c h nh trÆn trong m°t phflng, h nh cƒu ìn và trong khæng gian
    Banach, h nh cƒu trong khæng gian Hillbert l c¡c t“p lçi.
    M»nh ã 1.1. T“p lçi l âng vîi ph†p giao, ph†p cºng, ph†p nh¥n
    vîi mºt sŁ thüc, tøc l , n‚u C v D l hai t“p lçi trong R
    n th C ∩ D,
    λC + βD công l c¡c t“p lçi.
    ành l‰ 1.1. Giao cıa mºt hå tòy þ c¡c t“p lçi trong R
    n l mºt t“p lçi
    trong R
    n .
    Chøng minh. Gi£ sß A α ∈ R
    n (α ∈ I) l c¡c t“p lçi vîi I l t“p ch¿ sŁ
    b§t k , ta cƒn chøng minh t“p A = ∩ α∈I A α l lçi.
    L§y tòy þ x 1 , x 2 ∈ A. Khi â, x 1 , x 2 ∈ A α , vîi ∀α ∈ I. Do A α l lçi
    cho n¶n λx 1 + (1 ư λ)x 2 ∈ A α vîi ∀λ ∈ [0, 1] → λx 1 + (1 ư λ)x 2 ∈ A.
    V v“y, A l t“p lçi.
    ành l‰ 1.2. Gi£ sß A i ⊂ R
    n lçi; λ i ∈ R (i = 1, 2, . , m). Khi â,
    λ 1 A 1 + λ 2 A 2 + . + λ m A m l lçi.
    ành ngh¾a 1.5. Vectì x ∈ R
    n ưæc gåi l tŒ hæp lçi cıa c¡c vectì
    x 1 , x 2 , . , x m ∈ R
    n n‚u
    ∃λ i ≥ 0, i = 1, 2, . , m,
    m
    X
    i=1
    λ i = 1 : x =
    m
    X
    i=1
    λ i x i .5
    ành l‰ 1.3. T“p A ⊂ R
    n l lçi khi v ch¿ khi nâ chøa måi tŒ hæp lçi
    cıa c¡c vectì cıa nâ, tøc l A ⊂ R
    n lçi khi v ch¿ khi
    ∀m ∈ N , ∀λ 1 , . , λ m ≥ 0 :
    m
    X
    i=1
    λ i = 1, ∀x 1 , . , x m ∈ A →
    m
    X
    i=1
    λ i x i ∈ A.
    Chøng minh. Chån m = 2, hi”n nhi”n óng.
    Ta chøng minh quy n⁄p. Gi£ sß A l t“p lçi, ta l§y tòy þ x 1 , . , x m ∈
    A; λ 1 , . , λ m ≥ 0 v
    m
    P
    i=1
    λ i = 1; x =
    m
    P
    i=1
    . Ta chøng minh x ∈ A.
    m = 1 : x 1 ∈ A; λ 1 = 1 → x ∈ A.
    m = 2 : x 1 , x 2 ∈ A; λ 1 + λ 2 = 1 m A lçi suy ra x = λ 1 x 1 + λ 2 x 2 ∈ A.
    Gi£ sß x ∈ A óng vîi m ư 1, ta câ
    m
    X
    i=1
    λ i x i ∈ A; ∀x i ∈ A;
    m
    X
    i=1
    λ i = 1; λ i ≥ 0; i ∈ N .
    X†t x =
    m
    P
    i=1
    λ i x i =
    mư1
    P
    i=1
    λ i x i + λ m x m .
    Vîi λ m = 0 → x ∈ A.
    Vîi λ m = 1 → λ 1 = . = λ mư1 = 0 → x = x m ∈ A.
    Vîi 0 < λ < 1, ta câ:
    1 ư λ m = λ 1 + . + λ mư1 > 0,
    λ i
    1 ư λ m
    ≥ 0(i = 1, . , m ư 1).
    V
    mư1
    P
    i=1
    λ i
    1 ư λ m
    = 1 n¶n theo gi£ thi‚t quy n⁄p y =
    mư1
    P
    i=1
    x i ∈ A. Vîi
    y ∈ A v x m ∈ A, ta câ
    1 ư λ m > 0 v (1 ư λ m ) + λ m = 1 → x = (1 ư λ m )y + λ m x m ∈ A.
    ành ngh¾a 1.6. Chiãu cıa mºt t“p lçi A ưæc cho bði chiãu cıa a
    t⁄p affine nhä nh§t chøa A (khæng gian con song song vîi A), ưæc k‰
    hi»u l dimA. a t⁄p affine n y ưæc gåi l bao affine cıa A, ưæc k‰
    hi»u affA.6
    ành ngh¾a 1.7. i”m x 0 cıa t“p lçi A ⊂ R
    n ưæc gåi l i”m trong
    tưìng Łi cıa A n‚u vîi måi x ∈ affA câ mºt sŁ λ > 0 sao cho
    x 0 + λ(x ư x 0 ) ∈ A. Phƒn trong tưìng Łi cıa A l t“p c¡c i”m trong
    tưìng Łi cıa A, ưæc k‰ hi»u riA.
    ành ngh¾a 1.8. T“p A ⊂ R
    n ưæc gåi l nân n‚u:
    ∀a ∈ A, ∀λ > 0 th λx ∈ A.
    Nân A ưæc gåi l nân nhån n‚u nâ khæng chøa ưíng thflng. Nân A
    ưæc gåi l nân lçi n‚u A l t“p lçi. N‚u A l mºt t“p lçi a di»n th ta
    nâi nân sinh bði A l nân lçi a di»n.
    Mºt v‰ dö quan trång vã nân lçi trong R
    n l nân orthant dưìng
    R
    n
    +
    = {(x 1 , x 2 , . , x n ) : x i ≥ 0, i = 1, 2, . , n}.
    ành ngh¾a 1.9. Gi£ sß A ⊆ R
    n l t“p lçi v x 0 ∈ A. T“p
    N A (x
    0
    ) = {x

    ∈ R
    n
    : hx

    , x ư x
    0 i ≤ 0, ∀x ∈ A},
    ưæc gåi l nân ph¡p tuy‚n cıa A t⁄i x 0 .
    Hi”n nhi¶n, 0 ∈ N A (x 0 ) n¶n ta câ N A (x 0 ) l nân lçi âng.
    1.1.2. C¡c ành lþ t¡ch
    C¡c ành lþ t¡ch t“p lçi l mºt trong nhœng nºi dung cì b£n v quan
    trång nh§t cıa gi£i t‰ch lçi.
    ành ngh¾a 1.10. Si¶u phflng trong khæng gian R
    n l t“p t§t c£ c¡c
    i”m câ d⁄ng
    {x ∈ R
    n
    : a
    T
    x = α},
    trong â, a ∈ R
    n l vectì kh¡c 0 v α ∈ R .
    ành ngh¾a 1.11. T“p câ d⁄ng
    {x ∈ R
    n
    : ha, xi ≥ α},
    ưæc gåi l nßa khæng gian âng, trong â a 6= 0 v α ∈ R .7
    T“p
    {x ∈ R
    n
    : ha, xi > α},
    ưæc gåi l nßa khæng gian mð.
    Mºt si¶u phflng s‡ chia khæng gian ra l m hai nßa khæng gian, mØi
    nßa khæng gian ð vã mºt ph‰a cıa si¶u phflng. Si¶u phflng l phƒn chung
    cıa hai nßa khæng gian n‚u hai nßa khæng gian n y l âng.
    ành ngh¾a 1.12. Cho hai t“p S v T kh¡c rØng. Ta nâi si¶u phflng
    ht, xi = α
    (i) t¡ch S v T n‚u
    ht, xi ≤ α ≤ ht, yi, ∀x ∈ S, ∀y ∈ T.
    (ii) t¡ch ch°t S v T n‚u
    ht, xi < α < ht, yi, ∀x ∈ S, ∀y ∈ T.
    (iii) t¡ch m⁄nh S v T n‚u
    sup
    x∈S
    ht, xi < α < inf
    y∈T
    ht, yi, ∀x ∈ S, ∀y ∈ T.
    ành l‰ 1.4. (ành lþ t¡ch 1). Cho S v T l hai t“p lçi kh¡c rØng trong
    R
    n sao cho S ∩ T = ∅. Khi â, ta câ mºt si¶u phflng t¡ch S v T.
    ành l‰ 1.5. (ành lþ t¡ch 2). Cho S v T l hai t“p lçi âng kh¡c rØng
    sao cho S ∩ T = ∅. Gi£ sß câ ‰t nh§t mºt t“p compact. Khi â, hai t“p
    n y câ th” t¡ch m⁄nh bði mºt si¶u phflng.
    Chó þ 1.1. N‚u gi£ thi‚t "mºt trong hai t“p l compact" khæng thäa
    m¢n th ành lþ 1.5 khæng cÆn óng.
    V‰ dö 1.2. S = {(x, y) ∈ R
    2 | xy ≥ 1} v T = {(x, y) ∈ R
    2 | y ≤ 0} l
    hai t“p âng, ríi nhau nhưng khæng t¡ch m⁄nh.
    H» qu£ 1.1. (BŒ ã Farkas) Cho a ∈ R
    n v A l ma tr“n c§p m × n.
    Khi â ha, xi ≥ 0 vîi måi x thäa m¢n Ax ≥ 0 khi v ch¿ khi tçn t⁄i
    y ≥ 0 thuºc R
    m sao cho a = A T y.

    Xem Thêm: Vai trò của tính lồi trong bài toán tối ưu
    Nội dung trên chỉ thể hiện một phần hoặc nhiều phần trích dẫn. Để có thể xem đầy đủ, chi tiết và đúng định dạng tài liệu, bạn vui lòng tải tài liệu. Hy vọng tài liệu Vai trò của tính lồi trong bài toán tối ưu sẽ giúp ích cho bạn.
    #1
  7. Đang tải dữ liệu...

    Chia sẻ link hay nhận ngay tiền thưởng
    Vui lòng Tải xuống để xem tài liệu đầy đủ.

    Gửi bình luận

    ♥ Tải tài liệu

social Thư Viện Tài Liệu
Tài liệu mới

Từ khóa được tìm kiếm

Nobody landed on this page from a search engine, yet!

Quyền viết bài

  • Bạn Không thể gửi Chủ đề mới
  • Bạn Không thể Gửi trả lời
  • Bạn Không thể Gửi file đính kèm
  • Bạn Không thể Sửa bài viết của mình
  •  
DMCA.com Protection Status