tailieunhanh - QUY HOẠCH RỜI RẠC - CHƯƠNG 1

Tài liệu này là các Bài giảng của môn Quy hoạch rời rạc thuộc Trung tâm đào tạo sau đại học, Viện Toán học, Viện Khoa học và Công nghệ Việt nam trong các năm 2006, 2007 và 2008. Đây là tài liệu đầu tiên được viết bằng tiếng Việt trình bày một cách hệ thống về Quy hoạch rời rạc với cơ sở lý thuyết chặt chẽ, chứng minh tính hữu hạn của các thuật toán Gomory, hơn nữa còn đưa ra chương trình nguồn viết bằng C cho các thuật toán. Kiến thức chuẩn bị để tiếp thu giáo trình này là lý thuyết. | VIỆN KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM VIỆN TOÁN HỌC . BÙI THẾ TÂM QUY HOẠCH RỜI RẠC BÀI GIẢNG CAO HỌC HÀ NỘI 10-2008 Bùi Thế Tâm i Quy hoạch rời rạc LỜI NÓI ĐẦU Tài liệu này là các Bài giảng của môn Quy hoạch rời rạc thuộc Trung tâm đào tạo sau đại học Viện Toán học Viện Khoa học và Công nghệ Việt nam trong các năm 2006 2007 và 2008. Đây là tài liệu đầu tiên được viết bằng tiếng Việt trình bày một cách hệ thống về Quy hoạch rời rạc với cơ sở lý thuyết chặt chẽ chứng minh tính hữu hạn của các thuật toán Gomory hơn nữa còn đưa ra chương trình nguồn viết bằng C cho các thuật toán. Kiến thức chuẩn bị để tiếp thu giáo trình này là lý thuyết căn bản về quy hoạch tuyến tính và phương pháp đơn hình 9 lập trình bằng ngôn ngữ C 11 bảng tính điện tử Microsoft Excel 12 . Tài liệu gồm bảy chương. Chương 1 trình bày các bài toán phát sinh trong thực tiễn dẫn đến các bài toán quy hoạch rời rạc phát biểu bài toán quy hoạch rời rạc tổng quát. Các bài tập ở cuối chương 1 có thể dùng lệnh Solver trong Microsoft Excel để giải hướng dẫn lệnh này cho trong tài liệu 12 hoặc 13 . Trong Chương 2 nêu 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à chương trình máy tính viết bằng C và khái niệm về bài toán quy hoạch tuyến tính nguyên. Chương 3 trình bày tư tưởng phương pháp cắt thuật toán Gomory thứ nhất và chứng minh sự hội tụ của nó tài liệu gốc trong 1 2 chương trình máy tính của thuật toán Gomory thứ nhất. Chương 4 xét hai thuật toán thuật toán Gomory thứ hai dùng để giải bài toán quy hoạch tuyến tính nguyên bộ phận 3 thuật toán Dalton - Llewellyn dùng để giải bài toán quy hoạch tuyến tính với các biến nhận giá trị rời rạc 4 chương trình máy tính của hai thuật toán này. Chương 5 trình bày thuật toán Gomory thứ ba nhằm xây dựng các lát cắt đảm bảo tất cả các Bảng đơn hình ở mỗi bước đều có tất cả các phần tử là nguyên 5 6 chương trình máy tính của thuật toán Gomory thứ ba. Chương 6 trình bày tư tưởng của phương .