Giáo trình Quy hoạch tuyến tính: Phần 1

Phần 1 giáo trình "Quy hoạch tuyến tính" của tác giả Trần Xuân Sinh gồm 3 chương: Chương 1 - Bài toán quy hoạch tuyến tính, chương 2 - Tính chất bài toán quy hoạch tuyến tính, chương 3 - Phương pháp đơn hình. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Giáo trình Quy hoạch tuyến tính: Phần 1 t ) u H Ọ C VINH TRUNG TÁM mõm TIN-THƯV1ỆN 4N X U Â N S I N H 519.3 TS 274q/ 03 DT.009345 Quy hoạch SP NHÀ XUẤT BẢN ĐẠI H Ọ C s ư PHÀM T R Ấ N XUÂN SINH Q U Y H O Ạ C H T U Y Ế N TÍNH • NHÀ X U Ấ T BẢN ĐAI H O C sư PHÀM Mã số: 01.01-57/103 - ĐH 2003 MỤC L Ụ C trang Lời nói đầu 5 C h ư ơ n g 1. Bài t o á n quy hoạch t u y ế n t í n h 7 §1. Mơ đ ầ u 7 §2. Bài toán quy hoạch tuyên tính 8 §3. Mô t ả hình học bài toán quy hoạch tuyến tính và thuật toán đồ thị 16 Câu hỏi và bài tập chướng Ì 19 C h ư ơ n g 2. T í n h c h ấ t b à i t o á n quy hoạch t u y ế n t í n h 22 §1. Một số vấn để cớ bản của giải tích l ồ i 22 §2. Tính chất bài t o á n quy hoạch tuyến tính 39 §3. Cặp bài toán đối ngẫu 48 Câu hỏi và bài tập chương 2 62 Chương 3. P h ư ơ n g p h á p đ ơ n h ì n h 69 §1. Cơ sụ lý luận của phương p h á p 69 §2. Công thức biến đổi và bảng đơn hình 77 §3. Thuật toán đớn h ì n h và ví dụ 80 §4. Tìm phương án cực biên xuất phát 83 §5. Tính hữu hạn của t h u ậ t toán đơn h ì n h 87 Câu hỏi và bài tập chương 3 93 3 Chương4. Các p h ư ơ n g p h á p đơn h ì n h đ ặ c biệt 99 §1. Phương pháp đơn hình cải biên 99 §2. Phương pháp đơn hình đối ngẫu 104 §3. Phương pháp phân phối 112 Câu hỏi và bài tập chương 4 126 Chương 5. Một sô v â n đ ể k h á c liên quan b à i t o á n quy hoạch t u y ê n t í n h 128 §1. Độ phức tạp tính toán của thuật toán đơn hình 128 §2. Bài toán quy hoạch nguyên 130 §3. Thuật toán Khachiart và thuật toán điểm trong Karmarkar giải bài toán quy hoạch tuyến tính 151 §4. Thuật toán Frank-Wolfe giải bài toán quy hoạch lồi vối ràng buộc tuyến tính 170 Câu hỏi và bài tập chương 5 174 Tài l i ệ u tham khảo 177 4 L Ờ I NÓI Đ Ầ U Một số giáo t r ì n h quy hoạch tuyến tính trong những n ă m qua gần như chi dừng l ạ i ỏ những k ế t quả từ trước những n ă m 50. Trong sự p h á t t r i ể n của khoa học ngày nay. chúng ta không thê không nói tới một số t h à n h tựu mới gần đây (kê cả lý t h u y ê t và ứng dụng). Ngày nay, k h i nói đèn phương pháp giải một bài t o á n , người ta quan t â m nhiều đến độ phức tạp tính toán của nó. Độ phức tạp tính toán ỏ đây thông thường xét theo hai mật: Tốc độ tính toán và dung lượng bộ nhớ. cả hai đều phụ thuộc vào độ dài dữ l i ệ u cở k của bài toán. Ta sẽ gọi t h u ậ t toán A có độ phức tạp T (k) thời gian đa thức nếu A t ồ n t ạ i đa thức P (k) sao cho T (k) < P (k). Trong trường m A m hợp còn l ạ i . ta nói t h u ậ t toán A có độ phức tạp thời gian mũ. Cho đến nay. người ta thấy rằng thuật toán đơn hình (1949) có độ phức tạp tính toán thời gian mũ. N ă m 1979, Khachian (nhà toán học Nga) đã đưa ra thuật toán Ellipsoid, với thời gian đa thức. Và n ă m 1984, Karmarkar (nhà toán học Mỹ) công bố thuật toán điểm trong, cũng với thòi gian đa thức. Với k ế t quả của Khachian và Karmarkar đã chỉ ra r ằ n g bài toán quy hoạch tuyến tính thuộc lớp bài t o á n có độ phức tạp thòi gian đa thức. Kết quả đó đ ậ t ra câu hỏi: phải chăng t h u ậ t toán đơn hình kém hơn các 5 thuật toán vừa nêu? Người ta nhận thấy rằng với những bài toán cỡ vừa, thường gặp, xét theo độ phức tạp trung bình thì t h u ậ t toán đơn hình vẫn t h ế h i ệ n t í n h ưu việt của nó. Tuy nhiên, người ta hy vọng rằng trong tương lai, với những bài toán cỡ lớn thì các t h u ậ t toán Ellipsoid và điểm trong sẽ có lợi t h ế hơn nhiều. Vì vậy, c h ú n g tôi sẽ giới t h i ệ u sơ lược một sứ k ế t quả mới trong phạm vi cho phép của cuứn sách. Trong cuứn sách này, chúng ta ...