Bài giảng Quy hoạch tuyến tính - ĐH Sư Phạm Kỹ Thuật Nam Định

Tập Bài giảng Quy hoạch tuyến tính gồm 3 chương được trình bày như sau: Bài toán Quy hoạch tuyến tính và phương pháp đơn hình; Bài toán Quy hoạch tuyến tính đối ngẫu; Bài toán vận tải. Mời các bạn đọc cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Quy hoạch tuyến tính - ĐH Sư Phạm Kỹ Thuật Nam Định Bài giảng Quy hoạch tuyến tính TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT KHOA KHOA HỌC CƠ BẢN ===============================ThS. NGUYỄN ĐÌNH THI (Chủ biên) – ThS. NGUYỄN MẠNH TƢỜNG BÀI GIẢNG QUY HOẠCH TUYẾN TÍNH NAM ĐỊNH, 2011 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 1 Bài giảng Quy hoạch tuyến tínhTRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 2 Bài giảng Quy hoạch tuyến tính MỤC LỤCLỜI GIỚI THIỆU ................................................................................................................... 5Chương 1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH VÀ PHƢƠNG PHÁPĐƠN HÌNH ........................................................................................................................... 71.1. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ................................................................. 7 1.1.1. Các ví dụ ............................................................................................................. 7 1.1.2. Bài toán quy hoạch tuyến tính tổng quát .......................................................... 13 1.1.3. Bài toán quy hoạch tuyến tính dạng chính tắc .................................................. 19 1.1.4. Bài toán quy hoạch tuyến tính ở dạng chuẩn tắc .............................................. 231.2. BIẾN ĐỔI DẠNG CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ................... 26 1.2.1. Đưa dạng tổng quát về dạng chính tắc ................................................................ 26 1.2.2. Đưa dạng chính tắc về dạng chuẩn tắc (bài toán M) ............................................ 301.3. PHƢƠNG PHÁP ĐƠN HÌNH....................................................................................... 35 1.3.1. Giải bài toán QHTT ở dạng chuẩn.................................................................... 36 1.3.2. Giải bài toán QHTT ở dạng chính tắc (Phương pháp đánh thuế) ..................... 47 1.3.3. Phương pháp đơn hình hai pha ......................................................................... 53 1.3.4. Hiện tượng xoay vòng và cách khắc phục ........................................................ 59BÀI TẬP CHƢƠNG 1 .......................................................................................................... 62Chương 2: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU ...................... 762.1. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU ......................................... 76 2.1.1. Quy tắc lập bài toán đối ngẫu ........................................................................... 76 2.1.2. Quan hệ giữa bài toán gốc (P) và bài toán đỗi ngẫu (D) .................................. 792.2. THUẬT TOÁN ĐƠN HÌNH ĐỐI NGẪU.................................................................. 87 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT NAM ĐỊNH 3 Bài giảng Quy hoạch tuyến tính 2.2.1. Cơ sở gốc và cơ sở đối ngẫu .............................................................................87 2.2.2. Ý tưởng của thuật toán đơn hình đối ngẫu........................................................88 2.2.3. Thuật toán đơn hình đối ngẫu khi biết cơ sở đối ngẫu .....................................88 2.2.4. Thuật toán đơn hình đối ngẫu khi không biết cơ sở đối ngẫu ..........................942.3. Ý NGHĨA CỦA BÀI TOÁN ĐỐI NGẪU ................................................................ 104 2.3.1. Về bài toán ......................................................................................................104 2.3.2. Về thuật toán ...................................................................................................104 2.3.3. Về ý nghĩa thực tiễn ........................................................................................104BÀI TẬP CHƢƠNG 2 ........................................................................................................ 108Chương 3: BÀI TOÁN VẬN TẢI ..................................................................................... 1123.1. BÀI TOÁN VẬN TẢI .................................................................................................. 112 3.1.1. Mô hình bài toán vận tải .................................................................................112 3.1.2. Lập phương án cơ bản ban đầu .......................................................................116 3.1.3. Thuật toán “Quy O cước phí các ô chọn” .......................................................119 3.1.4. Phương pháp thế vị ......... ...