Bài giảng Quy hoạch tuyến tính

1.1. Các bài toán thực tế......................................................................................................... 1 
1.1.1. Bài toán lập kế hoạch sản xuất...................................................................................... 1 
1.1.2. Bài toán vận tải ............................................................................................................. 2 
1.1.3. Bài toán xác định khẩu phần......................................................................................... 2 
1.2. Bài toán qui hoạch tuyến tính ......................................................................................... 2 
1.3. Phương pháp hình học .................................................................................................... 3 
1.4. Bài tập ............................................................................................................................. 5 
Chương 2. PHƯƠNG PHÁP ĐƠN HÌNH................................................................................ 6 
2.1. Dạng chính tắc và dạng chuẩn tắc................................................................................... 6 
2.1.1. Định nghĩa..................................................................................................................... 6 
2.1.2. Các phép biến đổi.......................................................................................................... 6 
2.1.3. Phương án cơ bản.......................................................................................................... 7 
2.1.4. Các tính chất ................................................................................................................. 7 
2.2. Phương pháp đơn hình .................................................................................................... 8 
2.2.1. Nội dung........................................................................................................................ 8 
2.2.2. Bảng đơn hình............................................................................................................... 9 
2.2.3. Cơ sở lý luận ............................................................................................................... 10 
2.2.4. Các bước của thuật toán đơn hình............................................................................... 13 
2.2.5. Bài toán ẩn phụ ........................................................................................................... 15 
2.2.6. Bài toán ẩn giả ............................................................................................................ 16 
2.3. Cài đặt thuật toán đơn hình ........................................................................................... 20 
2.3.1. Khai báo dữ liệu.......................................................................................................... 20 
2.3.2. Tính các ước lượng ∆j ................................................................................................. 20 
2.3.3. Kiểm tra tối ưu và tìm ẩn thay thế .............................................................................. 20 
2.3.4. Kiểm tra vô nghiệm .................................................................................................... 20 
2.3.5. Tìm ẩn loại ra .............................................................................................................. 21 
2.3.6. Biến đổi bảng .............................................................................................................. 21 
2.4. Bài tập ........................................................................................................................... 22 
Chương 3. BÀI TOÁN ĐỐI NGẪU....................................................................................... 24 
3.1. Các bài toán thực tế....................................................................................................... 24 
3.1.1. Bài toán lập kế hoạch sản xuất.................................................................................... 24 
3.1.2. Bài toán đánh giá sản phẩm ........................................................................................ 24 
3.2. Bài toán đối ngẫu .......................................................................................................... 25 
3.2.1. Đối ngẫu không đối xứng ........................................................................................... 25 
3.2.2. Đối ngẫu đối xứng ...................................................................................................... 26 
3.2.3. Sơ đồ tucker ................................................................................................................ 28 
3.3. Các nguyên lý đối ngẫu................................................................................................. 28 
3.3.1. Nguyên lý 1................................................................................................................. 29 
3.3.2. Nguyên lý 2................................................................................................................. 29 
3.3.3. Nguyên lý 3 (Độ lệch bù)............................................................................................ 29 
3.4. Ý nghĩa kinh tế.............................................................................................................. 30 
3.4.1. Ý nghĩa bài toán (2) .................................................................................................... 30 
________________________________________________________________________ 
GV: Phan Thanh Tao 
Bài giảng Quy hoạch toán học Trang 64 
________________________________________________________________________ 
3.4.2. Ý nghĩa bài toán ( 2~ )................................................................................................... 30 
3.4.3. Ý nghĩa nguyên lý độ lệch bù ..................................................................................... 31 
3.5. Bài tập ........................................................................................................................... 31 
Chương 4. BÀI TOÁN VẬN TẢI .......................................................................................... 33 
4.1. Bài toán vận tải dạng chính tắc ..................................................................................... 33 
4.1.1. Định nghĩa................................................................................................................... 33 
4.1.2. Điều kiện cân bằng thu phát........................................................................................ 34 
4.2. Bảng phân phối và tính chất.......................................................................................... 34 
4.2.1. Bảng phân phối ........................................................................................................... 34 
4.2.2. Tính chất ..................................................................................................................... 35 
4.3. Thuật toán thế vị ........................................................................................................... 36 
4.3.1. Nội dung...................................................................................................................... 36 
4.3.2. Xây dựng phương án cơ bản ban đầu ......................................................................... 36 
4.3.3. Các bước của thuật toán thế vị.................................................................................... 37 
4.4. Các dạng khác ............................................................................................................... 38 
4.4.1. Không cân bằng thu phát ............................................................................................ 38 
4.4.2. Suy biến ...................................................................................................................... 39 
4.4.3. Dạng cực đại ............................................................................................................... 41 
4.4.4. Bài toán xe rỗng.......................................................................................................... 45 
4.4.5. Bài toán ô cấm ............................................................................................................ 47 
4.5. Cài đặt thuật toán thế vị ................................................................................................ 48 
4.5.1. Khai báo dữ liệu.......................................................................................................... 48 
4.5.2. Xây dựng phương án cơ bản ban đầu ......................................................................... 48 
4.5.3. Xây dựng hệ thống thế vị............................................................................................ 49 
4.5.4. Kiểm tra tối ưu ............................................................................................................ 49 
4.5.5. Tìm vòng điều chỉnh ................................................................................................... 50 
4.5.6. Biến đổi bảng .............................................................................................................. 50 
4.6. Bài tập ........................................................................................................................... 51 
Chương 5. PHƯƠNG PHÁP HUNGARY ............................................................................. 53 
5.1. Bài toán bổ nhiệm ......................................................................................................... 53 
5.2. Bài tập ........................................................................................................................... 62 
________________________________________________________________________ 
GV: Phan Thanh Tao