Kỹ thuật Quy hoạch tuyến tính

Tài liệu Quy hoạch tuyến tính có cấu trúc gồm 5 chương trình bày các nội dung: Bài toán quy hoạch tuyến tính, tính chất của tập phương án và tập phương án tối ưu của bài toán quy hoạch tuyến tính, phương pháp đơn hình và các thuật toán của nó, bài toán quy hoạch tuyến tính đối ngẫu và thuật toán đơn hình đối ngẫu, bài toán vận tải và thuật toán thế vị. Mời các bạn tham khảo.
Nội dung trích xuất từ tài liệu:
Kỹ thuật Quy hoạch tuyến tínhQuy hoạch tuyến tính Trường ĐHSP Đồng ThápMục lụcChương 1. Bài toán quy hoạch tuyến tính 3 1.1. Một vài bài toán thực tế . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Bài toán lập kế hoạch sản xuất . . . . . . . . . . . . . . . . 3 1.1.2 Bài toán vận tải . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2. Bài toán quy hoạch tuyến tính . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 Dạng tổng quát . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.2 Dạng chính tắc và dạng chuẩn tắc . . . . . . . . . . . . . . . 6 1.3. ý nghĩa hình học và phương pháp đồ thị . . . . . . . . . . . . . . . 8 1.4. Bài tập chương 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9Chương 2. Tính chất của tập phương án và tập phương án tối ưu của bài toán quy hoạch tuyến tính 14 2.1. Tập hợp lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2. Tính chất của tập phương án và tập phương án tối ưu của bài toán quy hoạch tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3. Tính chất của quy hoạch tuyến tính dạng chính tắc . . . . . . . . . 16 2.4. Bài tập chương 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16Chương 3. Phương pháp đơn hình và các thuật toán của nó 21 3.1. Cơ sở lí luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2. Thuật toán đơn hình . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2.1 Thuật toán đơn hình . . . . . . . . . . . . . . . . . . . . . . 24 3.2.2 Bảng đơn hình . . . . . . . . . . . . . . . . . . . . . . . . . 24 1Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp 3.2.4 Trường hợp bài toán suy biến . . . . . . . . . . . . . . . . . 27 3.2.5 Tìm phương án cực biên và cơ sở ban đầu . . . . . . . . . . 27 3.3. Bài tập chương 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35Chương 4. Bài toán quy hoạch tuyến tính đối ngẫu và thuật toán đơn hình đối ngẫu 42 4.1. Bài toán quy hoạch tuyến tính đối ngẫu . . . . . . . . . . . . . . . 42 4.2. Thuật toán đơn hình đối ngẫu . . . . . . . . . . . . . . . . . . . . . 47 4.2.1 Cơ sở lí luận . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.2.5 Thuật toán đơn hình đối ngẫu . . . . . . . . . . . . . . . . . 49 4.3. Vấn đề tìm phương án cực biên xuất phát của bài toán đối ngẫu . . 54 4.4. Vấn đề hậu tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.5. Bài tập chương 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62Chương 5. Bài toán vận tải và thuật toán thế vị 68 5.1. Bài toán vận tải . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.2. Các Tính chất của bài toán vận tải . . . . . . . . . . . . . . . . . . 69 5.2.1 Chu trình . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.3. Vấn đề tính các ước lượng . . . . . . . . . . . . . . . . . . . . . . . 70 5.4. Một số phương pháp xây dựng phương án cực biên ban đầu . . . . 73 5.5. Thuật toán thế vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.6. Tiêu chuẩn tối ưu. Bài toán đối ngẫu của bài toán vận tải . . . . . 77 5.6.1 Tiêu chuẩn tối ưu . . . . . . . . . . . . . . . . . . . . . . . . 77 5.6.2 Bài toán đối ngẫu của bài toán vận tải . . . . . . . . . . . . 78 2Quy hoạch tuyến tính Trường ĐHSP Đồng ThápChương 1.BÀI TOÁN QUY HOẠCH TUYẾNTÍNH1.1. Một vài bài toán thực tế1.1.1 Bài toán lập kế hoạch sản xuấtBài toán: Một cơ sở sản xuất dự định sản xuất hai loại sản phẩm A và B. Cácsản phẩm được chế tạo từ ba loại nguyên liệu I, II và III. Số lượng dự trữ của từngloại và số lượng từng loại nguyên liệu cần dùng để sản xuất ra một sản phẩm đượccho bằng bảng sau: Loại Nguyên liệu Nguyên liệu cần dùng để sản xuất một đơn vị sản phẩm Nguyên liệu dự trử A B I 18 2 3 II 30 5 4 III 25 1 6Hãy lập quy hoạch sản suất để thu được tiền lãi là lớn nhất, biết rằng tiền lãi thuđượ ...