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

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...
Nội dung trích xuất từ tài liệu:
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 nlogarit đ 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 tta 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 tbà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 )Tlà 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 utươ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 . 432 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 tqu 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 đư cc a c h ...