QUY HOẠCH RỜI RẠC - CHƯƠNG 2

NHỮNG KHÁI NIỆM MỞ ĐẦUTrong chương này sẽ trình bày những khái niệm cơ bản về quy hoạch tuyến tính, phương pháp đơn hình bình thường, phương pháp đơn hình đối ngẫu từ vựng, và khái niệm về bài toán quy hoạch tuyến tính nguyên.
Nội dung trích xuất từ tài liệu:
QUY HOẠCH RỜI RẠC - CHƯƠNG 2Bùi Thế Tâm II.1 Quy hoạch rời rạcChương 2 NHỮNG KHÁI NIỆM MỞ ĐẦU Trong chương này sẽ trình bày những khái niệm cơ bản về quy hoạch tuyến tính,phương pháp đơn hình bình thường, phương pháp đơn hình đối ngẫu từ vựng, và kháiniệm về bài toán quy hoạch tuyến tính nguyên.1. NHỮNG KHÁI NIỆM CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 1.1. Bài toán qui hoạch tuyến tính là bài toán có dạng: n ∑ x0 = → m ax c jx (1 ) j j =1 n ∑ = bi , i = 1, 2 , ..., l a ij x (2) j j =1 n ∑ ≤ bi , i = l + 1, ..., m a ij x (3) j j =1 ≥ 0, j = 1, .., n x (4) j Miền xác định: tập hợp các véc tơ x thoả mãn (2) và (4) Phương án bài toán: véc tơ x thoả mãn (2) và (4) n Nếu (x1,…,xn) là phương án của bài toán, x0 = ∑ c j x j thì X = (x0 ,x1,…,xn) gọi j =1là phương án mở rộng của bài toán (1) – (4). Phương án X * làm cực đại (1) gọi là phương án tối ưu. Phương án mở rộngX gọi là phương án tối ưu mở rộng nếu X* là phương án tối ưu . * Kí hiệu: L - miền xác định của bài toán (1)-(4) ( L, C ) – kí hiệu bài toán qui hoạch tuyến tính (1) - (4) X ( L, C ) – phương án tối ưu của bài toán (1) - (4) X ( L, C ) - phương án tối ưu mở rộng của bài toán (1) - (4) LC là tập hợp các phương án tối ưu của bài toán ( L, C ) Bài toán qui hoạch tuyến tính gọi là giải được nếu tồn tại phương án tối ưu. http://www.ebook.edu.vnBùi Thế Tâm II.2 Quy hoạch rời rạc 1.2. Dạng chính tắc của bài toán qui hoạch tuyến tính n ∑ x0 = → m ax c x (5) j j j=1 n ∑ = bi , i = 1, 2 , ..., m a ij x (6) j j =1 ≥ 0, j = 1, 2 , ..., n (7) x j  a1 j   a   2j  Gọi Aj =  .  là véc tơ điều kiện thứ j của bài toán (5)-(7)  .   amj     b1     b2  là véc tơ ràng buộc của bài toán (5)-(7). B= . .  .  b  m Phương án X của bài toán (5)-(7) gọi là tựa nếu các véc tơ điều kiện ứng vớicác thành phần dương của nó là độc lập tuyến tính. Cơ sở của phương án tựa X là tập hợp { A j | x j > 0 } . Các thành phần củaphương án tựa ứng với các véc tơ cơ sở gọi là các thành phần cơ sở (các biến tương ứnggọi là biến cơ sở), các thành phần còn lại gọi là các thành phần phi cơ sở (các biếntương ứng gọi là biến phi cơ sở). Nếu X = ( x1 ,..., xn ) phương án tựa của bài toán quy hoạch tuyến tính,( A j1 ,..., A jk ) là cơ sở của phương án tựa, B = { j1 ,..., jk } , N = {1,..., n} B thì hàm mụctiêu x0 , x1,..., xn có thể biểu diễn qua các biến phi cơ sở: ∑ xi j (− x j ),xi = xi 0 + i = 0,1,..., n ...