Đề cương môn Quy hoạch tuyến tính

ĐÈ CƯƠNG MÔN HỌC
ĐỀ CƯƠNG MÔN HỌC 
MÔN : QUY HOẠCH TUYẾN TÍNH 
MÃ MÔN HỌC : TH 431 
SỐ ĐƠN VỊ HỌC TRÌNH : 2 
HỌC KÌ : 5 
MỤC ĐÍCH YÊU CẦU 
 Sau khi học xong môn quy hoạch tuyến tính sinh viên phải biết cách xây dựng 
mô hình toán cho bài toán thực tế đơn giản, áp dụng thành thạo giải thuật đơn hình để 
giải lớp bài toán quy hoạch tuyến tính và lập trình được trên máy tính. 
KIẾN THỨC NỀN CẦN THIẾT 
Mức độ yêu cầu 
STT Nội dung kiến thức nền 
Tiên quyết 
Vận dụng khái 
niệm/ mô hình 
Vận dụng kỹ năng/ 
phương pháp 
1 Tin học đại cương x x 
KIẾN THỨC TOÁN CẦN THIẾT 
STT Nội dung kiến thức Mức độ yêu cầu 
 Hiểu 
Khái 
niệm 
Vận dụng 
Công thức/ 
định lý 
Chứng minh 
Công thức/ 
định lý 
Vận dụng 
Phương pháp 
1 Đại số tuyến tính x x 
TÓM TẮT NỘI DUNG MÔN HỌC 
Môn học được mở đầu bằng việc giới thiệu vài vấn đề thực tế dẫn đến mô hình 
quy hoạch tuyến tính. Trọng tâm của môn học là phần trình bày giải thuật đơn hình ở 
các mức độ sử dụng khác nhau. Lý thuyết đối ngẫu được trình bày một cách đơn giản. 
Phần ứng của quy hoạch tuyến tính được trình bày sau cùng để thấy sự ứng dụng rộng 
rãi của quy hoạch tuyến tính 
1
ĐÈ CƯƠNG MÔN HỌC
ĐỀ CƯƠNG CHI TIẾT CÁC CHƯƠNG 
CHƯƠNG I : LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 
I- GIỚI THIỆU BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 
 1- Bài toán vốn đầu tư 
 2- Bài toán lập kế hoạch sản xuất 
 3- Bài toán vận tải 
II- ĐỊNH NGHĨA VÀ NHỮNG KẾT QUẢ CƠ BẢN 
 1- Quy hoạch tuyến tính tổng quát 
 2- Quy hoạch tuyến tính dạng chính tắc 
 3- Phương án 
 4- Đa diện lồi các phương án khả thi - Phương pháp hình học 
III- MỘT VÍ DỤ MỞ ĐẦU 
IV- DẤU HIỆU TỐI ƯU 
 1- Ma trận cơ sở - Phương án cơ sở - Suy biến 
 2- Dấu hiệu tối ưu 
CHƯƠNG II : GIẢI THUẬT ĐƠN HÌNH 
I- GIẢI THUẬT ĐƠN HÌNH CƠ BẢN 
 1- Cơ sở lý thuyết 
 2- Định lý về sự hội tụ 
 3- Giải thuật đơn hình cơ bản 
 4- Chú ý trong trường hợp suy biến 
II- GIẢI THUẬT ĐƠN HÌNH CẢI TIẾN 
 1- Một cách tính ma trận nghịch đảo 
 2- Quy hoạch tuyến tính dạng chuẩn 
 3- Giải thuật đơn hình cải tiến 
 4- Phép tính trên dòng - Bảng đơn hình 
III- PHƯƠNG PHÁP BIẾN GIẢ CẢI BIÊN 
 1- Bài toán cải biên 
 2- Phương pháp hai pha 
 3- Phương pháp M vô cùng lớn 
CHƯƠNG III : BÀI TOÁN ĐỐI NGẪU 
2
ĐÈ CƯƠNG MÔN HỌC
I- KHÁI NIỆM VỀ ĐỐI NGẪU 
 1- Đối ngẫu của quy hoạch tuyến tính dạng chính tắc 
 2- Định nghĩa đối ngẫu trong trường hợp quy hoạch tổng quát 
 3- Các định lý về sự đối ngẫu 
II- GIẢI THUẬT ĐỐI NGẪU 
CHƯƠNG IV : ỨNG DỤNG QUY HOẠCH TUYẾN TÍNH 
I- MỞ ĐẦU 
II- BÀI TOÁN TRÒ CHƠI 
 1- Trò chơi có nghiệm ổn định 
2- Trò chơi không có nghiệm ổn định 
III- BÀI TOÁN VẬN TẢI 
 1- Mở đầu 
 2- Các khái niệm cơ bản 
 3- Bài toán vận tải cân bằng thu phát 
 4- Các bài toán được đưa về bài toán vận tải 
IV- BÀI TOÁN DÒNG TRÊN MẠNG 
 1- Mở đầu 
 2- Phát biểu bài toán dòng trên mạng 
V- QUY HOẠCH NGUYÊN 
 1- Mở đầu 
 2- Bài toán quy hoạch nguyên trong thực tế 
TÀI LIỆU THAM KHẢO 
[ Ban - 1998] 
 Phí Mạnh Ban – Quy Hoạch Tuyến Tính 
3
ĐÈ CƯƠNG MÔN HỌC
 Nhà xuất bản Giáo Dục ( tái bản lần 2) 
[ Hấn - xxxx] 
 Đặng Hấn – Quy Hoạch Tuyến Tính 
 Đại học Kinh tế TP Hồ Chí Minh ( lưu hành nội bộ ) 
[ Khánh-Nương - 2000] 
 Phan Quốc Khánh – Trần Huệ Nương – Quy Hoạch Tuyến Tính 
 Nhà xuất bản Giáo Dục 
4