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ái niệm về bài toán quy hoạch tuyến tính nguyên. | Bùi Thế Tâm Quy hoạch rời rạc Chươ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ái niệ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 . Bài toán qui hoạch tuyến tính là bài toán có dạng n X0 c jX j m ax 1 j b i 1 2 . l 2 j 1 t aijx j b i l 1 . m 3 j 1 Xj 0 j 1 . n 4 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 xb. xn là phương án của bài toán X0 CjXj thì X x0 xb. xn gọi j 1 là 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ộng X 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. Bùi Thế Tâm Quy hoạch rời rạc . Dạng chính tắc của bài toán qui hoạch tuyến tính n X 0 c j X j m a x 5 j 1 n s a ij X j bi i 1 2 . m 6 j 1 X j 0 j 1 2 . n 7 a. ì a a2 j Gọi Aj là véc tơ điều kiện thứ j của bài toán 5 - 7 b1 ì B b2 là véc tơ ràng buộc của bài toán 5 - 7 . V bm 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ới cá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 Aj Xj 0 . Các thành phần của phươ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 ứng gọ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ến tươ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 Aj1 . Ajk là cơ sở của phương án tựa B j1 . jk N 1 . n B thì hàm mục tiêu X0 X1 . xn có thể biểu diễn qua các biến phi cơ sở Xi Xi0 Xij -Xj i 0
