Báo cáo nghiên cứu khoa học: "Phương pháp chắn logarit gốc giải bài toán quy hoạch tuyến tính"

Chia sẻ: Nguyễn Phương Hà Linh Linh | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

64
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Xét bài toán quy ho ch tuy n tính d ng chu n (LP) : min{cT x | Ax = b, x ≥ 0} trong đó c, x ∈ Rn , b ∈ Rm và A ∈ Rm×n là ma tr n có h ng b ng m. Bài toán đ i ng u c a (LP) là (LD) : max{bT λ | AT λ + s = c, s ≥ 0}. Ý tư ng chính c a phương pháp ch n logarit g c gi i bài toán (LP) d a trên vi c x lý ràng bu c b t đ ng th c x ≥ 0 b...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo nghiên cứu khoa học: "Phương pháp chắn logarit gốc giải bài toán quy hoạch tuyến tính"

T P CHÍ KHOA H C, Đ i h c Hu , S 53, 2009 PHƯƠNG PHÁP CH N LOGARIT G C GI I BÀI TOÁN QUY HO CH TUY N TÍNH Bùi Văn Hi u, Huỳnh Th Phùng Trư ng Đ i h c Khoa h c, Đ i h c Hu TÓM T T Các phương pháp đi m trong cho t i ưu tuy n tính đã đư c gi i thi u khá chi ti t b i C. Roos, T. Terlaky, J.P. Vial [3]. Trong bài báo này, áp d ng các kĩ thu t c a phương pháp ch n logarit đ i ng u vào bài toán g c, chúng tôi đ xu t phương pháp ch n logarit g c. Hơn n a, đ ph c t p đa th c c a thu t toán này cũng đư c thi t l p. 1 Gi i thi u Xét bài toán quy ho ch tuy n tính d ng chu n min{cT x | Ax = b, x ≥ 0} (LP) : trong đó c, x ∈ Rn , b ∈ Rm và A ∈ Rm×n là ma tr n có h ng b ng m. Bài toán đ i ng u c a (LP) là (LD) : max{bT λ | AT λ + s = c, s ≥ 0}. Ý tư ng chính c a phương pháp ch n logarit g c gi i bài toán (LP) d a trên vi c x lý ràng bu c b t đ ng th c x ≥ 0 b ng cách s d ng hàm ph t là hàm ch n logarit φ(x) := − n=1 log xj , t đó đưa Bài toán (LP) v bài toán j n T (BP) : min{c x − t log xj | Ax = b, x > 0}. j =1 đây tham s t > 0 g i là tham s ch n và Bài toán (BP) g i là bài toán ch n. Tương t ta cũng đ nh nghĩa bài toán ch n c a Bài toán (LD) n T log sj | AT λ + s = c, s > 0}. (BD) : max{b λ + t j =1 Bây gi , cho x = (x1 , . . . , xn )T và s = (s1 , . . . , sn )T là hai vectơ dương trong Rn . Trong su t bài báo này, ta kí hi u e = (1, . . . , 1)T ∈ Rn , x−1 := (1/x1 , . . . , 1/xn )T và xs := (x1 s1 , . . . , xn sn )T là tích Hadamard c a hai vectơ x và s. Các phép toán s h c khác gi a hai vectơ đư c hi u tương t . X = diag(x), S = diag(s) là các ma tr n chéo có các ph n t chéo tương ng là các t a đ c a x, s; X −2 = diag(1/x2 ). Cu i cùng, a ch ph n nguyên trên c a s th c a và projU (u) là hình chi u c a u lên U . 43
2 M t s tính ch t cơ b n Nh c l i hàm Lagrange c a Bài toán (LP) là L(x, λ, s) = cT x + λT (b − Ax) − sT x. T Đ nh lý KKT (Karush-Kuhn-Tucker) đ i v i bài toán quy ho ch l i, ta có ngay các k t qu sau Đ nh lý 2.1. x∗ là nghi m c a Bài toán (LP) và (λ∗ , s∗ ) là nghi m c a Bài toán (LD) khi và ch khi (x∗ , λ∗ , s∗ ) là nghi m c a h KKT T A λ + s = c,   Ax = b, (1) XSe = 0,    (x, s) ≥ 0. Đ nh lý 2.2. xt là nghi m c a Bài toán (BP) và (λt , st ) là nghi m c a Bài toán (BD) khi và ch khi (xt , λt , st ) là nghi m c a h KKT T A λ + s = c,   Ax = b, (2) XSe = te,    (x, s) > 0. Đ nh nghĩa 2.1. C := {xt | t > 0} đư c g i là đư ng trung tâm c a Bài toán (LP). M nh đ 2.3 (Theorem II.4, [3]). Cho t > 0. Các kh ng đ nh sau là tương đương a) F+ := {(x, λ, s) | Ax = b, AT λ + s = c, (x, s) > 0} = ∅; b) Bài toán (BP) có nghi m (duy nh t); c) Bài toán (BD) có nghi m (duy nh t); d) H KKT (2) có nghi m (duy nh t). M nh đ 2.3 suy ra r ng đư ng trung tâm ch t n t i khi và ch khi mi n ch p nh n đư c c a c hai bài toán g c và bài toán đ i ng u đ u ch a các vectơ dương. Do đó, trong bài báo này ta luôn gi thi t r ng F+ = ∅ . Cơ s c a phương pháp ch n logarit g c d a trên đ nh lý sau. Đ nh lý 2.4. cT xt cT x∗ khi t 0. Ch ng minh. Ta có cT x∗ ≥ inf L(x, λt , st ) = L(xt , λt , st ) = cT xt − sT xt = cT xt − nt. t x Do đó 0 ≤ cT xt − cT x∗ ≤ nt, suy ra đi u c n ch ng minh. 44
c xt x∗ Hình 1: Đư ng trung tâm ti n đ n nghi m c a Bài toán (LP) khi t 0. 3 X p x nghi m c a Bài toán ch n (BP) Trong Bài toán (BP), vi c tìm nghi m xt là không đơn gi n do hàm m c tiêu Pt (x) := cT x − t n=1 log xj là phi tuy n. Ta tìm nghi m x p x c a bài toán này b ng cách x p x hàm j m c tiêu Pt (x) b i hàm toàn phương trong khai tri n Taylor c a Pt (x) đ n c p hai. Ta có Pt (x) = c − tx−1 2 Pt (x) = tX −2 . và Do đó 1 Pt (x + ∆x) ≈ Pt (x) + (c − tx−1 )T ∆x + ∆xT tX −2 ∆x. 2 Đt P + := {x | Ax = b, x > 0}. Lúc đó, m i đi m x ∈ P + đư c g i là m t đi m trong ch p nh n đư c hay đi m ch p nh n đư c ch t c a Bài toán (LP). T i bư c l p hi n hành (v i nghi m x p x xt là x ∈ P + ), ta c n xác đ nh hư ng tìm ki m ∆x sao cho x + ∆x ∈ P + . Do Ax = b nên A∆x = 0. T đó, ∆x là nghi m c a bài toán x p x 1 min{Pt (x) + (c − tx−1 )T ∆x + ∆xT tX −2 ∆x | A∆x = 0}. 2 Vì Pt (x) là h ng đ i v i ∆x nên ta có bài toán tương đương 1 min{(c − tx−1 )T ∆x + ∆xT tX −2 ∆x | A∆x = 0}. (3) 2 Đ ý r ng hàm m c tiêu c a Bài toán (3) là hàm toàn phương l i (vì ma tr n Hessian tX −2 xác đ nh dương). Theo Đ nh lý KKT, ∆x là nghi m c a Bài toán (3) khi và ch khi t n t i λ ∈ Rm sao cho c − tx−1 + tX −2 ∆x − AT λ = 0 (4) A∆x = 0. H này có nghi m duy nh t  12 ∆x = X 2 AT (AX 2 AT )−1 A − I X c−x t (5)  λ = (AX 2 AT )−1 A(X 2 c − tx). 45
Đ t s(x, t) := c − AT λ (s ph thu c x và t), h (4) tr thành s(x, t) − tx−1 + tX −2 ∆x = 0 (6) A∆x = 0. Ý nghĩa c a s(x, t) th hi n m nh đ sau M nh đ 3.1. s(x, t) là đi m làm c c ti u te − xs , trong đó s ch y kh p không gian affine c + Im(AT ), t c là s(x, t) = argmin{ te − xs | s ∈ c + Im(AT )}. Ch ng minh. Nh n xét r ng vectơ x ∈ Rn là đi m làm c c ti u C x − d , v i C ∈ Rm×n , d ∈ Rm khi và ch khi x là nghi m c a phương trình chu n t c C T Cx = C T d. Th t v y, C x − d đ t c c ti u khi và ch khi Cx = projIm(C ) d. Hơn n a Cx = projIm(C ) d ⇔ projIm(C ) (Cx − d) = 0 ⇔ Cx − d ∈ Im(C )⊥ = Ker(C T ) ⇔ C T (Cx − d) = 0 ⇔ C T Cx = C T d Tr l i m nh đ , v i b t kì s = c − AT λ ∈ c + Im(AT ), ta có te − xs = X AT λ + te − Xc trong đó X = diag(x). Lúc đó bài toán min{ te − xs | s ∈ c + Im(AT )} tương đương v i bài toán min{ XAT λ + te − Xc | λ ∈ Rm }. T nh n xét trên, λ là nghi m c a bài toán này khi và ch khi AX 2 (c − AT λ) = tAx. M t khác, v i λ đư c ch n th a (4), ta có AX 2 (c − AT λ) = AX 2 (tx−1 − tX −2 ∆x) = tAx − tA∆x = tAx. Do đó s(x, t) := c − AT λ = tx−1 − tX −2 ∆x đư c đ nh nghĩa như trong (6) chính là đi m c c ti u c a bài toán đã cho. 4 Các tính ch t c a bư c l p Newton bư c l p hi n hành, t i x ∈ P + , ta c p nh t x+ = x + ∆x = x(e + x−1 ∆x). Rõ ràng x+ là đi m ch p nh n đư c n u và ch n u e + x−1 ∆x ≥ 0. Hơn n a, t (6) ta có s(x, t) = tx−1 (e − x−1 ∆x). (7) Do đó s(x, t) ch p nh n đư c n u e − x−1 ∆x ≥ 0. T các nh n xét này ta có ngay k t qu sau 46
M nh đ 4.1. (x+ , s(x, t)) ch p nh n đư c (ch t) khi và ch khi −e ≤ x−1 ∆x ≤ e (−e < x−1 ∆x < e). Đi u này tương đương v i x−1 ∆x ≤ 1 ( x−1 ∆x < 1). ∞ ∞ Trong trư ng h p lý tư ng ∆x = 0, ta có xs(x, t) = te, do đó x và s(x, t) th a mãn đi u ki n KKT. Vì v y (x, s(x, t)) = (xt , st ). Trong trư ng h p t ng quát ∆x = 0 nên các bư c l p Newton không th trùng v i xt , do đó ta c n m t đ i lư ng, kí hi u là δ (x, t), dùng đ đo m c đ g n nhau gi a đi m x và xt trên đư ng trung tâm. T M nh đ 4.1 ta có th ch n δ (x, t) chính là x−1 ∆x ∞ . Tuy nhiên đ thu n ti n trong vi c phân tích đ ph c t p c a thu t toán, ta thay chu n vô cùng b ng chu n Euclide. T c là δ (x, t) := x−1 ∆x . T (6) và M nh đ 3.1 ta có xs(x, t) 1 δ (x, t) := x−1 ∆x = e − = min{ te − xs | s ∈ c + Im(AT )}. t ts M nh đ 4.2. N u δ := δ (x, t) ≤ 1 thì (x+ , s(x, t)) là c p ch p nh n đư c c a bài toán. Hơn na δ (x+ , t) ≤ δ (x, t)2 . Ch ng minh. Ta có x−1 ∆x ∞ ≤ x−1 ∆x = δ ≤ 1 nên t M nh đ 4.1 suy ra (x+ , s(x, t)) là c p ch p nh n đư c c a bài toán. T Đ nh nghĩa c a δ (x+ , t) ta có 1 δ (x+ , t) ≤ te − x+ s(x, t) . t Do (7) nên te − x+ s(x, t) = te − (x + ∆x)s(x, t) = t(x−1 ∆x)2 . Vì v y δ (x+ , t) ≤ (x−1 ∆x)2 ≤ x−1 ∆x 2 = δ (x, t)2 . 5 L h ng đ i ng u Trong lý thuy t đ i ng u, ta bi t r ng bT λ ≤ cT x v i b t kì x thu c mi n ch p nh n đư c c a Bài toán (LP) và (λ, s) thu c mi n ch p nh n đư c c a Bài toán (LD). Đ i lư ng không âm cT x − bT λ = λT Ax + sT x − bT λ = sT x chính là l h ng đ i ng u. Như v y, t i m i đi m trên đư ng trung tâm, l h ng đ i ng u có giá tr b ng nt (do sT xt = nt). Rõ ràng khi t 0 thì l h ng đ i ng u d n v 0, cT xt đơn đi u t T gi m và b λt đơn đi u tăng v giá tr t i ưu chung c a hai bài toán (LP) và (LD). M nh đ sau cho ta m t ư c lư ng c a l h ng đ i ng u t i (x, s(x, t)). M nh đ 5.1. N u δ := δ (x, t) ≤ 1 thì l h ng đ i ng u t i (x, s(x, t)) th a mãn nt(1 − δ ) ≤ xT s(x, t) ≤ nt(1 + δ ). Ch ng minh. Ta có xT s(x, t) = xT [tx−1 (e − x−1 ∆x)] = teT (e − x−1 ∆x). Do δ ≤ 1 nên t a đ c a vectơ e − x−1 ∆x n m trong kho ng [1 − δ, 1 + δ ], t đó suy ra b t đ ng th c c n ch ng minh. 47
6 Thu t toán Trong thu t toán ch n logarit g c, ta đưa vào sai s x p x τ ∈ [0, 1) v i yêu c u δ (x, t) ≤ τ m i bư c l p và tham s θ ∈ (0, 1) dùng đ c p nh t tham s ch n. Thu t toán này có th mô t như sau: ch n đi m xu t phát x0 th a mãn x0 > 0, Ax0 = b và tham s ch n xu t phát t0 > 0 sao cho x0 s0 δ (x0 , t0 ) = e − 0 ≤ τ. t m i bư c l p, ta tính ∆x và λ theo công th c (5) và c p nh t x+ := x + ∆x, t+ := (1 − θ)t. Thu t toán d ng khi l h ng đ i ng u nt ≤ . Thu t toán ch n logarit g c cho Bài toán (LP). Input: A, b, c; Sai s x p x τ , 0 ≤ τ < 1; Sai s > 0; Đi m xu t phát x0 th a mãn x0 > 0, Ax0 = b và tham s ch n t0 > 0 sao cho δ (x0 , t0 ) ≤ τ ; Tham s θ, 0 < θ < 1 (dùng đ c p nh t tham s ch n). Begin x := x0 ; t := t0 ; while nt > do begin x := x + ∆x; t := (1 − θ)t; end end Hình 2 minh h a các bư c l p c a thu t toán ch n logarit g c. T i m i bư c l p, các đi m hình (*) th hi n chính xác các đi m trên đư ng trung tâm, các vòng tròn nh (◦ ) là các đi m x p x đư ng trung tâm sinh ra b i thu t toán, còn các vòng tròn l n th hi n ph m vi gi i 0, các đi m (◦ ) ti n đ n nghi m t i ưu h n c a các đi m này (theo nghĩa δ (x, t) ≤ τ ). Khi t c a bài toán. Sau đây, ta s ch ng t r ng, v i các tham s τ , θ đư c ch n thích h p và đi m xu t phát th a mãn các gi thi t c a thu t toán, đi u ki n (x, λ, s) ∈ F+ (8) δ (x, t) ≤ τ luôn đư c đ m b o m i bư c l p, do đó tính đúng đ n c a thu t toán đư c thi t l p. B đ 6.1. Gi s δ (x, t) ≤ 1. Lúc đó θ2 n + +2 4 δ (x , t ) = δ (x, t) + (1 − θ)2 48
t = 0. 1 0 K 1 K 2 K 3 K K 1.0 0.5 0.0 0.5 1.0 Hình 2: Minh h a các bư c l p c a thu t toán ch n logarit g c. trong đó t+ := (1 − θ)t. Ch ng minh. Ta có x+ s(x, t) 1+ δ ( x+ , t + ) ≤ t e − x+ s(x, t) = e − . t+ t(1 − θ) Mà x+ s(x, t) = t[e − (x−1 ∆x)2 ] nên e − h2 θ δ (x+ , t+ ) ≤ e − = h2 − (e − h2 ) 1−θ 1−θ θ đây h := x−1 ∆x. Đ t η = , suy ra 1−θ δ (x+ , t+ )2 ≤ h2 2 − 2η (h2 )T (e − h2 ) + η 2 e − h2 2 . Do gi thi t h = δ (x, t) ≤ 1 nên 0 ≤ e − h2 ≤ e, và do đó (h2 )T (e − h2 ) ≥ 0, e − h2 2 ≤ e 2. Vì v y δ (x+ , t+ )2 ≤ h2 2 + η2 e 2 4 + η 2 n = δ (x, t)4 + η 2 n. ≤h B đ đư c ch ng minh. √ √ M nh đ 6.1. V i τ = 1/ 2 và tham s θ = 1/(3 n), đi u ki n (8) luôn th a mãn mi bư c l p. Ch ng minh. m i bư c l p, các đi u ki n đi m trong ch p nh n đư c Ax = b, x > 0 và s = c − AT λ√ 0 đã đư c ch ng minh trong m c 4. Ta ch c n ki m tra δ (x, t) ≤ τ . Th t v y, > √ 2n v i θ = 1/(3 n), ta có (1θ θ)2 ≤ 1 . Do đó n u δ (x, t) ≤ τ = 1/ 2 thì t B đ 6.1 suy ra − 4 11 1 δ (x+ , t+ )2 ≤ += 44 2 √ hay δ (x+ , t+ ) ≤ 1/ 2 = τ . Như v y, sau m i bư c l p, đi u ki n (8) luôn th a mãn nên tính đúng đ n c a thu t toán đư c thi t l p. 49
Đ nh lý sau kh ng đ nh t c đ h i t đa th c c a thu t toán ch n logarit g c. √ √ Đ nh lý 6.2. V i τ = 1/ 2 và tham s θ = 1/(3 n), thu t toán ch n logarit g c đòi h i nhi u nh t √ nt0 3 n log bư c l p. Đ u ra c a thu t toán là c p (x, s) th a mãn xT s ≤ 2 . Ch ng minh. Sau k bư c l p, tham s ch n đư c c p nh t là t = (1 − θ)k t0 , do đó thu t toán s d ng n u l h ng đ i ng u không vư t quá , t c là nt0 (1 − θ)k ≤ . L y logarit hai v , ta đư c k log(1 − θ) + log(nt0 ) ≤ log . Hơn n a do − log(1 − θ) ≥ θ nên b t đ ng th c trên đư c th a mãn n u nt0 kθ ≥ log(nt0 ) − log = log hay √ nt0 k ≥ 3 n log . Hơn n a, n u x là bư c l p k t thúc thu t toán và t là tham s ch n tương ng thì t M nh đ 5.1 suy ra xT s(x, t) ≤ nt[1 + δ (x, t)] ≤ nt(1 + τ ) ≤ 2nt. Khi thu t toán k t thúc ta có nt ≤ , do đó xT s(x, t) ≤ 2 . Đ nh lý đư c ch ng minh. 7 Đi m xu t phát c a thu t toán Thu t toán ch n logarit g c mà ta gi i thi u ph n trên đòi h i đi m xu t phát ph i là m t đi m trong c a mi n ch p nh n đư c và ph i g n ho c n m trên đư ng trung tâm. Đôi khi m t đi m như th có th bi t trư c nhưng thông thư ng thì không. Có nhi u phương pháp bi n đ i đ đưa bài toán ban đ u v bài toán tương đương mà đó m t đi m xu t phát th a mãn yêu c u c a thu t toán là có s n. Ph n này s gi i thi u phương pháp t đ i ng u bi n đ i bài toán ban đ u v bài toán tương đương có s n m t đi m xu t phát trên đư ng trung tâm. Trư c h t, ta xét bài toán quy ho ch tuy n tính d ng chính t c min{cT x | Ax ≥ b, x ≥ 0}. (P): (9) Bài toán đ i ng u c a (P) là max{bT λ | AT λ ≤ c, λ ≥ 0}. (D): (10) D th y r ng Bài toán (P) và (D) có nghi m v i l h ng đ i ng u b ng 0 khi và ch khi h  Ax ≥ b, x ≥ 0;  −AT λ ≥ −c, λ ≥ 0; (11) T  T b λ − c x ≥ 0; có nghi m. Đ t    0 A −b λ −AT  , z :=  x  ; 0 c M := bT −cT 0 α 50
và z 0m+n+1 Mu M := , z := , q := ; − uT 0 β m+n+2 trong đó α, β ∈ R và u := em+n+1 − M em+n+1 (kí hi u ei đ ch vectơ đ dài i có t t c các t a đ đ u b ng 1). Xét các h M z ≥ 0, z ≥ 0; (12) M z ≥ −q, z ≥ 0; (13) và bài toán min{q T z | M z ≥ −q, z ≥ 0}. (SP): (14) Ta d ki m ch ng đư c k t qu sau M nh đ 7.1 (Theorem I.5, I.6, [3]). Các kh ng đ nh sau là tương đương a) Bài toán (P) và (D) có nghi m t i ưu v i l h ng đ i ng u b ng 0; b) H (12) có nghi m v i α > 0; c) H (13) có nghi m v i α > 0 và β = 0; d) Bài toán (SP) có nghi m v i α > 0. Như v y, ta đã qui vi c gi i bài toán (P) v bài toán tương đương (SP). Đ ý r ng (SP) là bài toán t đ i ng u (bài toán đ i ng u trùng v i chính nó). Hơn n a, v i k := m + n + 2 và z = ek , ta có M u ek−1 0 M ek −1 + u + k−1 = Mz + q = . −uT 0 −uT ek−1 + k 1 k D th y M ek−1 + u = ek−1 (t đ nh nghĩa c a u) và −uT ek−1 + k = −(ek−1 − M ek−1 )T ek−1 + k = −eT−1 ek−1 + k = 1 k (eT−1 M ek−1 = 0 vì M là ma tr n ph n đ i x ng). T đó suy ra M ek + q = ek hay z = ek là k m t đi m trong ch p nh n đư c c a bài toán (SP). Bây gi , tr l i bài toán quy ho ch tuy n tính d ng chu n ban đ u min cT x | Ax = b, x ≥ 0}, (LP) : (15) trong đó c, x ∈ Rn , b ∈ Rm và A ∈ Rm×n là ma tr n có h ng b ng m. G i I ⊂ {1, 2, . . . , n} là t p các ch s c t c a ma tr n A sao cho ma tr n AI t o thành t các c t này là ma tr n vuông c p m không suy bi n. B ng cách s p x p l i các c t c a A, ta có th vi t A = (AI , AJ ) v i J = {1, 2, . . . , n} \ I . Lúc đó h Ax = b có th vi t l i AI xI + AJ xJ = b. T đó suy ra xI = A−1 (b − AJ xJ ) và cT x = cT A−1 b + (cJ − AT A−T cI )T xJ . Vì cT A−1 b là II JI II I h ng s nên bài toán d ng chu n (LP) tương đương v i bài toán d ng chính t c min{(cJ − AT A−T cI )T xJ | −A−1 AJ xJ ≥ −A−1 b, xJ ≥ 0}. JI I I Áp d ng phép bi n đ i gi i thi u trên đ đưa bài toán này v bài toán t đ i ng u min{q T z | M z ≥ −q, z ≥ 0} (SLP) : 51
trong đó M en+2 + q = en+2 . Đ t σ := σ (z ) = M z + q , ta có en+2 σ (en+2 ) = en+2 . Đi u này suy ra z = en+2 là m t đi m n m trên đư ng trung tâm c a Bài toán (SLP) ng v i tham s ch n q z t0 = 1. B ng cách kí hi u A := [M, −I ], c := , b := −q và x := , ta có Bài toán (SLP) 0 σ tương đương v i bài toán d ng chu n min{cT x | Ax = b, x ≥ 0}. (LP) : (16) Bây gi , ta ch ng t x = e2(n+2) là đi m n m trên đư ng trung tâm c a bài toán (LP) v i tham s ch n t0 = 1. Th t v y, ta có bài toán đ i ng u c a (LP) là T T (DP) : max{b λ | A λ + s = c, s ≥ 0}. (17) D th y x := e2(n+2) là đi m ch p nh n đư c c a bài toán (LP) và λ := en+2 là đi m ch p nh n đư c c a bài toán (DP). Hơn n a, ta có q − MT λ q + Mλ T s=c−A λ= = = e2(n+2) . λ λ Do đó x s = e2(n+2) hay x = e2(n+2) là đi m n m trên đư ng trung tâm c a bài toán (LP) v i tham s ch n t0 = 1. Tóm l i, b ng phương pháp t đ i ng u, ta đã đưa Bài toán (LP) v Bài toán tương đương (LP) có ngay m t đi m xu t phát x = e2(n+2) n m trên đư ng trung tâm ng v i tham s ch n t0 = 1. Gi i Bài toán (LP) b ng phương pháp ch n logarit g c ta thu đư c xJ , t đó tính đư c xI = A−1 (b − AJ xJ ) và suy ra nghi m c a Bài toán (LP). I TÀI LI U THAM KH O [1] Bùi Văn Hi u, Phương pháp đi m trong gi i bài toán quy ho ch toán h c, Lu n văn th c sĩ toán h c, trư ng Đ i h c Khoa h c Hu , 2008. [2] Y. Nesterov, A. Nemirovskii, Interior - Point Polynomial Algorithms in Convex Program- ming, SIAM Publications, Philadelphia, 1994. [3] C. Roos, T. Terlaky, J.P. Vial, Interior Point Methods for Linear Optimization, Springer, 2005. [4] G. Wang, X. Cai, Y. Yue, A New Polynomial Interior-Point Algorithm for Monotone Mixed Linear Complementarity Problem, Fourth International Conference on Natural Computa- tion, IEEE, 2008. [5] Margaret H. Wright, The Interior-point revolution in optimization: history, development and lasting consequences, Bulletin of the AMS, Vol 42, No 1, pages 31-56, 2004. 52
THE PRIMAL LOGARITHMIC BARRIER METHOD FOR SOLVING LINEAR PROGRAMMING PROBLEM Bui Van Hieu, Huynh The Phung College of sciences, Hue University SUMMARY Interior point methods for linear optimization was introduced in detail by C. Roos, T. Terlaky, J.P. Vial [3]. In this paper, applying techniques of the Dual Logarithmic Barrier Method to the primal problem, we propose a Primal Logarithmic Barrier Method. Furthermore, the algorithm will be proved to have polynomial-time complexity.