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. | 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 . 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 LP min cTX I Ax b X 0 trong đó C X 2 Rn b 2 Rm và A 2 Rmxn là ma trận có hạng bằng m. Bài toán đối ngẫu của LP là LD max bTA I ATA s C s 0 . Y tưởng chính của phưong 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 Y n 1 log Xj từ đó đưa Bài toán LP về bài toán BP min cTX t 2logXj I Ax b X 0 . j i ở đâ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 đinh nghĩa bài toán chắn của Bài toán LD BD max bTA t 2 log Sj I ATA s C s 0 . j i 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 2 Rn X-1 1 x1 . 1 xn T và XS x1s1 . Xnsn 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 4 chỉ phần nguyên trên của số thực a và projơ 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 X s cTx XT b Ax sTx. Từ Đinh 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ý . x là nghiệm của Bài toán LP và X s là nghiệm của Bài toán LD khi và chỉ khi x X s là nghiệm của hệ KKT AT X 8 c. Ax b XSe 0. Ax s 0. 1 Định lý . xt là nghiệm của Bài toán BP và Xt st là nghiệm của Bài toán BD khi và chỉ khi
