BÀI GIẢNG - TỐI ƯU HÓA TRONG GIAO THÔNG VẬN TẢI (Huỳnh Văn Tùng Cb)



Bài giảng  “Tối ưu hóa trong Giao thông Vận tải” được biên soạn nhằm giúp sinh viên có tài liệu phong phú hơn trong việc học tập các học phần “Toán kinh tế” và  học  phần  “Tối  ưu  hóa”.  Nội  dung  cuốn  sách  được  cấu  trúc  gồm  bốn  chương: chương 1: Quy hoạch tuyến tính; chương  2: Bài toán vận tải; chương 3:  Sơ đồ mạng PERT và chương 4: Quy hoạch động.



NỘI DUNG:


CHƯƠNG 1. Quy hoạch tuyến tính............................................................................ 6 

1.1. Một số ví dụ thực tế dẫn đến bài toán quy hoạch tuyến tính............................... 6 

1.1.1. Bài toán lập kế hoạch sản xuất...................................................................... 6 

1.1.2. Bài toán vận tải.............................................................................................. 7 

1.1.3. Bài toán cắt vật liệu....................................................................................... 8 

1.2. Mô hình toán của bài toán quy hoạch tuyến tính................................................. 9 

1.2.1. Dạng tổng quát.............................................................................................. 9 

1.2.2. Dạng chính tắc, dạng chuẩn tắc.................................................................... 9 

1.2.3. Một số quy tắc đưa bài toán quy hoạch tuyến tính dạng tổng quát về dạng 

chính tắc................................................................................................................ 11 

1.2.4. Ẩn cơ bản, phương án cực biên.................................................................. 12 

1.3. Một số tính chất của bài toán quy hoạch tuyến tính.......................................... 14 

1.3.1. Cơ sở giải tích lồi........................................................................................ 14 

1.3.2. Một số tính chất của bài toán quy hoạch tuyến tính.................................... 15 

1.4. Giải bài toán quy hoạch tuyến tính hai biến bằng phương pháp hình học........ 15 

1.4.1. Biểu diễn hình học tập phương án.............................................................. 15 

1.4.2. Phương pháp hình học................................................................................. 15 

1.5. Phương pháp đơn hình....................................................................................... 17 

1.5.1. Cơ sở lý luận của phương pháp................................................................... 17 

1.5.2. Bảng đơn hình............................................................................................. 19 

1.5.3. Thuật toán đơn hình.................................................................................... 19 

1.5.4. Phương pháp đơn hình giải bài toán quy hoạch tuyến tính dạng tổng quát26 

1.6. Bài toán quy hoạch tuyến tính chứa tham số ở hàm mục tiêu........................... 30 

1.6.1. Mở đầu........................................................................................................ 30 

1.6.2. Phương pháp giải........................................................................................ 30 

1.7. Bài toán quy hoạch tuyến tính đối ngẫu............................................................ 37 

1.7.1. Hai ví dụ dẫn nhập...................................................................................... 37 

1.7.2. Định nghĩa cặp bài toán đối ngẫu................................................................ 39 

1.7.3. Các tính chất của cặp bài toán đối ngẫu...................................................... 42 

Downloaded by EBOOKBKMT VMTC (nguyenphihung1009@gmail.com)

lOMoARcPSD|2935381

Bộ môn Toán – Trường ĐH.GTVT TP. Hồ Chí Minh

Tối ưu hóa trong Giao thông Vận tải –2021  4 

1.7.4. Quan hệ của cặp bài toán đối ngẫu............................................................. 44 

1.7.5. Các dạng bài tập.......................................................................................... 44 

BÀI TẬP CHƯƠNG 1................................................................................................ 51 

CHƯƠNG 2. Bài toán vận tải.................................................................................... 61 

2.1. Các khái niệm về bài toán vận tải...................................................................... 61 

2.1.1. Phát biểu bài toán vận tải (btvt).................................................................. 61 

2.1.2. Mô hình toán học của bài toán vận tải........................................................ 61 

2.1.3. Bài toán vận tải cân bằng thu phát.............................................................. 62 

2.1.4. Bài toán vận tải dạng bảng, dạng ma trận................................................... 62 

2.1.5. Bảng phân phối........................................................................................... 63 

2.2. Thuật toán thế vị giải bài toán vận tải đóng ....................................................... 64 

2.2.1. Các khái niệm.............................................................................................. 64 

2.2.2. Các tính chất của bài toán vận tải............................................................... 64 

2.2.3. Một số phương pháp tìm phương án cực biên ban đầu............................... 65 

2.2.4. Cơ sở của thuật toán thế vị.......................................................................... 68 

2.2.5. Thuật toán thế vị chi tiết.............................................................................. 70 

2.3. Các trường hợp đặc biệt của bài toán vận tải..................................................... 73 

2.3.1. Bài toán vận tải không cân bằng thu phát................................................... 73 

2.3.2. Bài toán vận tải có hàm mục tiêu cực đại................................................... 75 

2.3.3. Bài toán vận tải có ô cấm............................................................................ 77 

2.3.4. Bài toán vận tải có hạn chế khả năng thông qua......................................... 79 

2.4. Bài toán điều tàu rỗng........................................................................................ 84 

2.4.1. Phát biểu bài toán........................................................................................ 84 

2.4.2. Mô hình toán ............................................................................................... 85 

2.4.3. Phương pháp giải........................................................................................ 86 

2.5. Bài toán vận tải chứa tham số ở hàm mục tiêu.................................................. 88 

2.5.1. Mô hình toán học........................................................................................ 88 

2.5.2. Phương pháp giải........................................................................................ 88 

BÀI TẬP CHƯƠNG 2................................................................................................ 91 

CHƯƠNG 3. Sơ đồ mạng PERT............................................................................... 94 

3.1. Giới thiệu........................................................................................................... 94 

3.2. Các khái niệm cơ bản về đồ thị.......................................................................... 95 

3.2.1. Đồ thị có hướng........................................................................................... 95 

3.2.2. Đồ thị vô hướng.......................................................................................... 95 

3.2.3. Một số dạng đồ thị đặc biệt......................................................................... 96 

Downloaded by EBOOKBKMT VMTC (nguyenphihung1009@gmail.com)

lOMoARcPSD|2935381

Bộ môn Toán – Trường ĐH.GTVT TP. Hồ Chí Minh

Tối ưu hóa trong Giao thông Vận tải –2021  5 

3.3. Sơ đồ mạng PERT............................................................................................. 97 

3.3.1. Các định nghĩa............................................................................................. 97 

3.3.2. Các bước lập sơ đồ mạng PERT................................................................. 99 

3.4. Các chỉ tiêu thời gian trên sơ đồ mạng PERT................................................. 100 

3.4.1. Thời điểm sớm nhất, thời điểm muộn nhất của một sự kiện..................... 100 

3.4.2. Cách ghi các tham số tại một sự kiện........................................................ 100 

3.4.3. Thời gian dự trữ của sự kiện và công việc................................................ 100 

3.4.4. Đường găng............................................................................................... 101 

3.5. Sơ đồ mạng PERT kèm theo trục thời gian..................................................... 103 

BÀI TẬP CHƯƠNG 3.............................................................................................. 104 

CHƯƠNG 4. Quy hoạch động................................................................................. 106 

4.1. Những nội dung cơ bản.................................................................................... 106 

4.1.1. Bài toán dẫn (bài toán phân phối sản phẩm)............................................. 106 

4.1.2. Các nguyên tắc cơ bản của quy hoạch động............................................. 107 

4.1.3. Quá trình nhiều giai đoạn.......................................................................... 108 

4.1.4. Xây dựng phương trình hàm..................................................................... 109 

4.1.5. Sơ đồ tính toán.......................................................................................... 110 

4.2. Áp dụng sơ đồ mạng PERT giải một số bài toán trong thực tế có dạng bài toán 

quy hoạch động....................................................................................................... 111 

4.2.1. Sơ đồ mạng PERT..................................................................................... 111 

4.2.2. Bài toán phân phối sản phẩm (bài toán dẫn)............................................. 112 

4.2.3. Một bài toán quy hoạch nguyên................................................................ 114 

4.2.4. Ứng dụng quy hoạch động trong giao thông vận tải................................. 115 

4.2.5. Bài toán phân phối công suất của các nhà máy điện................................. 117 

BÀI TẬP CHƯƠNG 4.............................................................................................. 119 

TÀI LIỆU THAM KHẢO.







LINK DOWNLOAD



Bài giảng  “Tối ưu hóa trong Giao thông Vận tải” được biên soạn nhằm giúp sinh viên có tài liệu phong phú hơn trong việc học tập các học phần “Toán kinh tế” và  học  phần  “Tối  ưu  hóa”.  Nội  dung  cuốn  sách  được  cấu  trúc  gồm  bốn  chương: chương 1: Quy hoạch tuyến tính; chương  2: Bài toán vận tải; chương 3:  Sơ đồ mạng PERT và chương 4: Quy hoạch động.



NỘI DUNG:


CHƯƠNG 1. Quy hoạch tuyến tính............................................................................ 6 

1.1. Một số ví dụ thực tế dẫn đến bài toán quy hoạch tuyến tính............................... 6 

1.1.1. Bài toán lập kế hoạch sản xuất...................................................................... 6 

1.1.2. Bài toán vận tải.............................................................................................. 7 

1.1.3. Bài toán cắt vật liệu....................................................................................... 8 

1.2. Mô hình toán của bài toán quy hoạch tuyến tính................................................. 9 

1.2.1. Dạng tổng quát.............................................................................................. 9 

1.2.2. Dạng chính tắc, dạng chuẩn tắc.................................................................... 9 

1.2.3. Một số quy tắc đưa bài toán quy hoạch tuyến tính dạng tổng quát về dạng 

chính tắc................................................................................................................ 11 

1.2.4. Ẩn cơ bản, phương án cực biên.................................................................. 12 

1.3. Một số tính chất của bài toán quy hoạch tuyến tính.......................................... 14 

1.3.1. Cơ sở giải tích lồi........................................................................................ 14 

1.3.2. Một số tính chất của bài toán quy hoạch tuyến tính.................................... 15 

1.4. Giải bài toán quy hoạch tuyến tính hai biến bằng phương pháp hình học........ 15 

1.4.1. Biểu diễn hình học tập phương án.............................................................. 15 

1.4.2. Phương pháp hình học................................................................................. 15 

1.5. Phương pháp đơn hình....................................................................................... 17 

1.5.1. Cơ sở lý luận của phương pháp................................................................... 17 

1.5.2. Bảng đơn hình............................................................................................. 19 

1.5.3. Thuật toán đơn hình.................................................................................... 19 

1.5.4. Phương pháp đơn hình giải bài toán quy hoạch tuyến tính dạng tổng quát26 

1.6. Bài toán quy hoạch tuyến tính chứa tham số ở hàm mục tiêu........................... 30 

1.6.1. Mở đầu........................................................................................................ 30 

1.6.2. Phương pháp giải........................................................................................ 30 

1.7. Bài toán quy hoạch tuyến tính đối ngẫu............................................................ 37 

1.7.1. Hai ví dụ dẫn nhập...................................................................................... 37 

1.7.2. Định nghĩa cặp bài toán đối ngẫu................................................................ 39 

1.7.3. Các tính chất của cặp bài toán đối ngẫu...................................................... 42 

Downloaded by EBOOKBKMT VMTC (nguyenphihung1009@gmail.com)

lOMoARcPSD|2935381

Bộ môn Toán – Trường ĐH.GTVT TP. Hồ Chí Minh

Tối ưu hóa trong Giao thông Vận tải –2021  4 

1.7.4. Quan hệ của cặp bài toán đối ngẫu............................................................. 44 

1.7.5. Các dạng bài tập.......................................................................................... 44 

BÀI TẬP CHƯƠNG 1................................................................................................ 51 

CHƯƠNG 2. Bài toán vận tải.................................................................................... 61 

2.1. Các khái niệm về bài toán vận tải...................................................................... 61 

2.1.1. Phát biểu bài toán vận tải (btvt).................................................................. 61 

2.1.2. Mô hình toán học của bài toán vận tải........................................................ 61 

2.1.3. Bài toán vận tải cân bằng thu phát.............................................................. 62 

2.1.4. Bài toán vận tải dạng bảng, dạng ma trận................................................... 62 

2.1.5. Bảng phân phối........................................................................................... 63 

2.2. Thuật toán thế vị giải bài toán vận tải đóng ....................................................... 64 

2.2.1. Các khái niệm.............................................................................................. 64 

2.2.2. Các tính chất của bài toán vận tải............................................................... 64 

2.2.3. Một số phương pháp tìm phương án cực biên ban đầu............................... 65 

2.2.4. Cơ sở của thuật toán thế vị.......................................................................... 68 

2.2.5. Thuật toán thế vị chi tiết.............................................................................. 70 

2.3. Các trường hợp đặc biệt của bài toán vận tải..................................................... 73 

2.3.1. Bài toán vận tải không cân bằng thu phát................................................... 73 

2.3.2. Bài toán vận tải có hàm mục tiêu cực đại................................................... 75 

2.3.3. Bài toán vận tải có ô cấm............................................................................ 77 

2.3.4. Bài toán vận tải có hạn chế khả năng thông qua......................................... 79 

2.4. Bài toán điều tàu rỗng........................................................................................ 84 

2.4.1. Phát biểu bài toán........................................................................................ 84 

2.4.2. Mô hình toán ............................................................................................... 85 

2.4.3. Phương pháp giải........................................................................................ 86 

2.5. Bài toán vận tải chứa tham số ở hàm mục tiêu.................................................. 88 

2.5.1. Mô hình toán học........................................................................................ 88 

2.5.2. Phương pháp giải........................................................................................ 88 

BÀI TẬP CHƯƠNG 2................................................................................................ 91 

CHƯƠNG 3. Sơ đồ mạng PERT............................................................................... 94 

3.1. Giới thiệu........................................................................................................... 94 

3.2. Các khái niệm cơ bản về đồ thị.......................................................................... 95 

3.2.1. Đồ thị có hướng........................................................................................... 95 

3.2.2. Đồ thị vô hướng.......................................................................................... 95 

3.2.3. Một số dạng đồ thị đặc biệt......................................................................... 96 

Downloaded by EBOOKBKMT VMTC (nguyenphihung1009@gmail.com)

lOMoARcPSD|2935381

Bộ môn Toán – Trường ĐH.GTVT TP. Hồ Chí Minh

Tối ưu hóa trong Giao thông Vận tải –2021  5 

3.3. Sơ đồ mạng PERT............................................................................................. 97 

3.3.1. Các định nghĩa............................................................................................. 97 

3.3.2. Các bước lập sơ đồ mạng PERT................................................................. 99 

3.4. Các chỉ tiêu thời gian trên sơ đồ mạng PERT................................................. 100 

3.4.1. Thời điểm sớm nhất, thời điểm muộn nhất của một sự kiện..................... 100 

3.4.2. Cách ghi các tham số tại một sự kiện........................................................ 100 

3.4.3. Thời gian dự trữ của sự kiện và công việc................................................ 100 

3.4.4. Đường găng............................................................................................... 101 

3.5. Sơ đồ mạng PERT kèm theo trục thời gian..................................................... 103 

BÀI TẬP CHƯƠNG 3.............................................................................................. 104 

CHƯƠNG 4. Quy hoạch động................................................................................. 106 

4.1. Những nội dung cơ bản.................................................................................... 106 

4.1.1. Bài toán dẫn (bài toán phân phối sản phẩm)............................................. 106 

4.1.2. Các nguyên tắc cơ bản của quy hoạch động............................................. 107 

4.1.3. Quá trình nhiều giai đoạn.......................................................................... 108 

4.1.4. Xây dựng phương trình hàm..................................................................... 109 

4.1.5. Sơ đồ tính toán.......................................................................................... 110 

4.2. Áp dụng sơ đồ mạng PERT giải một số bài toán trong thực tế có dạng bài toán 

quy hoạch động....................................................................................................... 111 

4.2.1. Sơ đồ mạng PERT..................................................................................... 111 

4.2.2. Bài toán phân phối sản phẩm (bài toán dẫn)............................................. 112 

4.2.3. Một bài toán quy hoạch nguyên................................................................ 114 

4.2.4. Ứng dụng quy hoạch động trong giao thông vận tải................................. 115 

4.2.5. Bài toán phân phối công suất của các nhà máy điện................................. 117 

BÀI TẬP CHƯƠNG 4.............................................................................................. 119 

TÀI LIỆU THAM KHẢO.







LINK DOWNLOAD

M_tả
M_tả

Chuyên mục:

Không có nhận xét nào: