1-Mô tả chính xác các khái niệm về bài toán quy hoạch tuyến tính
2-Phân tích và áp dụng đúng các bài toán quy hoạch tuyến tính
4-Phát huy khả năng sáng tạo
5-Rèn luyện kỹ năng tính toán chính xác
Trang bị cho sinh viên công cụ giải QHTT, phân biệt các dạng bài toán QHTT, các phương pháp đơn hình gốc, đối ngẫu, tổng hợp. Cách thành lập các mô hình từ bài toán thực tế.
This course provides:
- Definition of linear programming (LP). Solving simple LP
- The simplex algorithm. Initialization. The unbounded case. Tableau form. Degeneracy and anticycling
- The geometry of LP: convex polyhedra, extreme points, vertices and basic feasible solutions, geometric explanation of simplex algorithm, column geometry
- Computational efficiency
- Dual LP, duallity theorems, the dual simplex algorithm, the primal – dual algorithm
- Modified simplex algorithm
Chương 1: QHTT và cách giải đơn giản
1.1 Bài toán thực tế
1.2 Định nghĩa QHTT
1.3 Giải bằng hình học
1.4 Trường hợp không có nghiệm chấp nhận được
Chương 2:Phương pháp đơn hình
2.1 Ví dụ
2.2 Thuật toán đơn hình trên từ vựng
2.3 Tìm từ vựng xuất phát
2.4 Trường hợp mục tiêu không giới nội
2.5 Sự d y nhất nghiệm tối ưu
2.6 Dạng bảng của phương pháp đơn hình
Chương 3: Hiện tượng suy biến (8 tiết)
3.1 Định nghĩa và thí dụ
3.2 Quy tắc xoay Bland
3.3 Phương pháp nhiễu loạn
3.4 Phương pháp từ điển
Chương 4: Nghiên cứu hình học quy hoạch tuyến tính
4.1 Điểm cực biên, đỉnh, cơ sở
4.2 Trường hợp tập ràng buộc có dạng chính tắc
4.3 Sự ồn tại đỉnh và đỉnh tối ưu
4.4 Hiện tượng suy biến
4.5 Giải thích hình học thuật toán đơn hình
4.6 Tại sao lại gọi là thuật toán đơn hình
Chương 5: Hiệu quả của phương pháp đơn hình. Độ phức tạp tính toán
5.1 Số bước lặp điển hình
5.2 Trường hợp xấu nhất
5.3 Quy tắc cải thiện nhiều nhất
5.4 Độ phức tạp tính toán
Chương 6: Lý thuyết đối ngẫu
6.1 Bài toán mở đầu
6.2 Định nghĩa bài toán đối ngẫu
6.3 Các định lý về đối ngẫu
6.4 Độ lệch bù
6.5 Thuật toán đơn hình đối ngẫu
6.6 Pha một dựa trên tính đối ngẫu
Chương 7: Phương pháp đơn hình cải biên
7.1 Dạng ma trận của phương pháp đơn hình
7.2 Thuật toán đơn hình cải biên
Chương 8: Nghiên cứu độ nhạy cảm và quy hoạch có tham số
8.1 Trường hợp cơ sở tối ưu không đổi
8.2 Trường hợp hiệu chỉnh được nghiêm tối ưu
8.3 Quy hoạch tuyến tính tham số
Phương pháp thuyết giảng và chia nhóm giải bài tập
Kiểm tra cuối kỳ, tự luận
6. Giáo Trình: P.Q. Khánh, T.H. Nương, Quy hoạch tuyến tính, NXB Giáo Dục, 2003.
[1] V. Chvatal, Linear Programming, Freeman and Company, New York, 1983.
[2] H. Karloff, Linear Programming, Bickhauser, Boston. Berlin, 1991.
o MATLAB, MAPLE