
Bài giảng Toán Kinh tế
Biên soạn: TS. Lê Thị Ngọc Diệp – K.QTKD – Học viện CNBCVT
2.6.3 Phương pháp đơn hình đối ngẫu ............................................................ 91
2.6.4 Ứng dụng lý thuyết đối ngẫu ................................................................. 98
CHƯƠNG 3. MÔ HÌNH BÀI TOÁN VẬN TẢI ..................................................... 105
3.1 NỘI DUNG BÀI TOÁN VÀ CÁC TÍNH CHẤT ............................................ 105
3.1.1 Nội dung bài toán ................................................................................. 105
3.1.2 Các tính chất của bài toán vận tải ........................................................ 108
3.2 PHƯƠNG PHÁP TÌM PHƯƠNG ÁN CỰC BIÊN BAN ĐẦU ..................... 109
3.2.1 Phương pháp chi phí nhỏ nhất (min cước) ........................................... 110
3.2.2 Phương pháp góc Tây - Bắc ................................................................. 114
3.2.3 Phương án xấp xỉ Phôghen .................................................................. 115
3.3 PHƯƠNG PHÁP THẾ VỊ GIẢI BÀI TOÁN VẬN TẢI .................................. 117
3.3.1 Bài toán đối ngẫu của bài toán vận tải và tiêu chuẩn tối ưu ................ 117
3.3.2 Thuật toán thế vị giải bài toán vận tải .................................................. 118
3.4 MỘT SỐ DẠNG ĐẶC BIỆT CỦA BÀI TOÁN VẬN TẢI .............................. 124
3.4.1 Bài toán vận tải mở (không cân bằng cung - cầu) ............................... 124
3.4.2 Bài toán vận tải cực đại ........................................................................ 128
3.4.3 Bài toán vận tải theo thời gian ............................................................. 131
3.4.4 Bài toán vận tải có ô cấm ..................................................................... 136
3.4.5 Bài toán xác lập kho hợp lý ................................................................. 140
3.4.6 Bài toán điều xe ................................................................................... 144
3.4.7 Bài toán phân công lao động ................................................................ 147
CHƯƠNG 4. MÔ HÌNH BÀI TOÁN TỐI ƯU TRÊN MẠNG ............................. 150
4.1 MỘT SỐ KHÁI NIỆM CƠ BẢN .................................................................... 150
4.1.1 Định nghĩa về đồ thị hữu hạn ............................................................... 150
4.1.2 Biểu diễn đồ thị dưới dạng ma trận...................................................... 151
4.1.3 Một số yếu tố của đồ thị ....................................................................... 152
4.2 BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT (NGUỒN ĐƠN) .............................. 156
4.2.1 Nội dung và ý nghĩa bài toán ............................................................... 156
4.2.2 Phương pháp giải – Thuật toán Dijkstra .............................................. 157
4.3 MẠNG LIÊN THÔNG NGẮN NHẤT ............................................................ 160
4.3.1 Nội dung và ý nghĩa bài toán ............................................................... 160
4.3.2 Phương pháp giải ................................................................................. 160
4.4 BÀI TOÁN LUỒNG LỚN NHẤT VÀ LUỒNG NHỎ NHẤT ......................... 162
4.4.1 Bài toán luồng lớn nhất ........................................................................ 162
4.4.2 Bài toán luồng nhỏ nhất ....................................................................... 167
4.5 PHƯƠNG PHÁP SƠ ĐỒ LƯỚI (MẠNG PERT) ......................................... 170
4.5.1 Các khái niệm và ý nghĩa ..................................................................... 170
4.5.2 Các quy tắc thành lập sơ đồ lưới .......................................................... 171
4.5.3 Các yếu tố của sơ đồ lưới ..................................................................... 174
4.5.4 Thuật toán tìm đường căng .................................................................. 176
4.5.5 Tối ưu hóa quá trình rút ngắn đường căng ........................................... 178
CHƯƠNG 5. MÔ HÌNH HỆ THỐNG PHỤC VỤ CÔNG CỘNG ....................... 181
5.1 NỘI DUNG BÀI TOÁN ................................................................................ 181
5.2 MÔ HÌNH HÓA HỆ THỐNG PHỤC VỤ CÔNG CỘNG ............................. 181
5.2.1 Hệ thống phục vụ công cộng và các yếu tố cấu thành ......................... 181