Giải Quyết Bài Toán Vận Tải và Phân Công Hiệu Quả

Bài toán vận tải là một trong những vấn đề quan trọng trong lĩnh vực logistics. 57 trang · Đại Học Quốc Gia TP. Hồ Chí Minh · 2024.

• Tác giả: Nguyễn Tất Phú
• Người hướng dẫn: Ths. Võ Thị Ngọc Trân
• Trường học: Đại Học Quốc Gia TP. Hồ Chí Minh
• Chuyên ngành: Phương Pháp Định Lượng
• Đề tài: Giải Quyết Bài Toán Vận Tải và Phân Công Hiệu Quả
• Loại tài liệu: Báo Cáo Bài Tập Lớn
• Năm xuất bản: 2024
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• 1. Phần 1. BÀI TOÁN VẬN TẢI
• 1.1. Bài toán vận tải
• 1.2. Giải bài toán vận tải bằng phương pháp chi phí bé nhất
• 1.3. Tìm nghiệm tối ưu của bài toán vận tải
• 1.4. Xây dựng mô hình và giải bài toán bằng phương pháp truyền thống
• 1.5. Dùng phần mềm để giải toán
• 1.6. Phân tích rủi ro
• 2. BÀI TOÁN PHÂN CÔNG
• 2.1. Bài toán phân công
• 2.2. Giải bài toán phân công bằng phương pháp Hungarian
• 2.3. Dùng phần mềm để giải toán
• 2.4. Phân tích rủi ro
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Giải Quyết Bài Toán Vận Tải Hiệu Quả

Bài toán vận tải là một trong những vấn đề quan trọng trong lĩnh vực logistics. Nó liên quan đến việc tối ưu hóa chi phí vận chuyển hàng hóa từ các điểm cung cấp đến các điểm tiêu thụ. Mục tiêu chính là giảm thiểu chi phí vận chuyển trong khi vẫn đáp ứng đầy đủ nhu cầu của các điểm tiêu thụ. Việc áp dụng các phương pháp tối ưu hóa như quy hoạch tuyến tính giúp giải quyết bài toán này một cách hiệu quả.

1.1. Định Nghĩa Bài Toán Vận Tải

Bài toán vận tải được định nghĩa là việc xác định kế hoạch vận chuyển hàng hóa từ m điểm cung cấp đến n điểm tiêu thụ sao cho chi phí vận chuyển là thấp nhất. Các yếu tố cần xem xét bao gồm khả năng cung cấp và nhu cầu tiêu thụ.

1.2. Tầm Quan Trọng Của Bài Toán Vận Tải Trong Logistics

Bài toán vận tải đóng vai trò quan trọng trong việc quản lý logistics. Nó không chỉ giúp tiết kiệm chi phí mà còn tối ưu hóa quy trình vận chuyển, từ đó nâng cao hiệu quả hoạt động của doanh nghiệp.

II. Những Thách Thức Trong Giải Quyết Bài Toán Vận Tải

Giải quyết bài toán vận tải không phải là điều đơn giản. Có nhiều thách thức cần phải đối mặt, bao gồm sự biến động của chi phí vận chuyển, khả năng cung cấp không ổn định và nhu cầu thay đổi liên tục. Những yếu tố này có thể ảnh hưởng đến kế hoạch vận chuyển và làm tăng chi phí tổng thể.

2.1. Biến Động Chi Phí Vận Chuyển

Chi phí vận chuyển có thể thay đổi do nhiều yếu tố như giá nhiên liệu, chính sách thuế và phí cầu đường. Việc dự đoán và quản lý những biến động này là một thách thức lớn.

2.2. Khả Năng Cung Cấp Không Ổn Định

Sự không ổn định trong khả năng cung cấp hàng hóa từ các nhà cung cấp có thể dẫn đến tình trạng thiếu hụt hàng hóa, ảnh hưởng đến khả năng đáp ứng nhu cầu của khách hàng.

III. Phương Pháp Giải Quyết Bài Toán Vận Tải Hiệu Quả

Có nhiều phương pháp để giải quyết bài toán vận tải, trong đó phương pháp chi phí bé nhất và phương pháp tối ưu hóa quy hoạch tuyến tính là hai trong số những phương pháp phổ biến nhất. Những phương pháp này giúp tìm ra giải pháp tối ưu với chi phí thấp nhất.

3.1. Phương Pháp Chi Phí Bé Nhất

Phương pháp chi phí bé nhất là một trong những cách đơn giản và hiệu quả để giải quyết bài toán vận tải. Phương pháp này ưu tiên phân bổ hàng hóa đến các điểm tiêu thụ có chi phí vận chuyển thấp nhất.

3.2. Quy Hoạch Tuyến Tính Trong Giải Quyết Bài Toán Vận Tải

Quy hoạch tuyến tính là một công cụ mạnh mẽ trong việc tối ưu hóa bài toán vận tải. Nó cho phép xác định các biến quyết định và ràng buộc để tìm ra giải pháp tối ưu cho bài toán.

IV. Ứng Dụng Thực Tiễn Của Giải Quyết Bài Toán Vận Tải

Việc áp dụng các phương pháp giải quyết bài toán vận tải trong thực tiễn đã mang lại nhiều lợi ích cho các doanh nghiệp. Các công ty có thể tiết kiệm chi phí, nâng cao hiệu quả vận chuyển và cải thiện dịch vụ khách hàng.

4.1. Ví Dụ Thực Tế Về Giải Quyết Bài Toán Vận Tải

Nhiều công ty đã áp dụng thành công các phương pháp tối ưu hóa bài toán vận tải để giảm thiểu chi phí và nâng cao hiệu quả hoạt động. Ví dụ, một công ty logistics lớn đã giảm chi phí vận chuyển lên đến 20% nhờ áp dụng quy hoạch tuyến tính.

4.2. Kết Quả Nghiên Cứu Về Hiệu Quả Vận Tải

Nghiên cứu cho thấy rằng việc tối ưu hóa bài toán vận tải không chỉ giúp giảm chi phí mà còn cải thiện thời gian giao hàng và tăng cường sự hài lòng của khách hàng.

V. Kết Luận Về Giải Quyết Bài Toán Vận Tải

Giải quyết bài toán vận tải là một nhiệm vụ quan trọng trong quản lý logistics. Việc áp dụng các phương pháp tối ưu hóa giúp doanh nghiệp tiết kiệm chi phí và nâng cao hiệu quả hoạt động. Tương lai của bài toán vận tải sẽ tiếp tục phát triển với sự hỗ trợ của công nghệ và các phương pháp mới.

5.1. Tương Lai Của Bài Toán Vận Tải

Với sự phát triển của công nghệ, bài toán vận tải sẽ ngày càng trở nên phức tạp hơn. Tuy nhiên, các công cụ và phương pháp mới sẽ giúp giải quyết những thách thức này một cách hiệu quả.

5.2. Tầm Quan Trọng Của Việc Tối Ưu Hóa Vận Tải

Tối ưu hóa vận tải không chỉ giúp giảm chi phí mà còn nâng cao khả năng cạnh tranh của doanh nghiệp trên thị trường. Điều này càng trở nên quan trọng trong bối cảnh kinh tế hiện nay.

Nội dung chính

Tối Ưu Hóa Mạng Lưới Phân Phối và Phân Bổ Nguồn Lực: Nghiên Cứu Chuyên Sâu Về Các Biến Thể Quy Hoạch Tuyến Tính (Vận Tải, Phân Công và Dòng Chảy Tối Đa)

---

Tóm tắt nghiên cứu

Nghiên cứu này tập trung giải quyết bài toán cốt lõi trong khoa học quản lý và nghiên cứu vận hành (Operations Research): Làm thế nào để mô hình hóa và tối ưu hóa việc phân bổ nguồn lực hữu hạn trong các hệ thống mạng phức tạp nhằm đạt hiệu quả kinh tế cao nhất và độ trễ thấp nhất? Đề tài tiến hành phân tích đa chiều trên ba biến thể kinh điển của Quy hoạch Tuyến tính (Linear Programming - LP): Bài toán Vận tải (Transportation Problem), Bài toán Phân công (Assignment Problem), và Bài toán Dòng chảy Tối đa (Maximum Flow Problem).

Về mặt phương pháp luận, nghiên cứu tích hợp phương pháp toán học giải tích truyền thống (Phương pháp Chi phí bé nhất kết hợp vòng lặp cải tiến Stepping-Stone, Thuật toán Hungarian và Thuật toán gán nhãn Ford-Fulkerson) với công cụ mô phỏng số học tự động hóa thông qua Microsoft Excel Solver (Simplex LP) và Báo cáo Phân tích Độ nhạy (Sensitivity Analysis).

Kết quả thực nghiệm trên các tình huống kinh doanh thực tế chứng minh:

1. Xác lập kế hoạch vận tải khí đốt tối ưu đạt chi phí sàn $11,900 (mở rộng $13,200 khi tăng trưởng nhu cầu) và chỉ rõ nhà cung ứng cần mở rộng hợp đồng;
2. Tìm ra cấu hình gán việc tuyệt đối cho 5 đội lắp đặt với chi phí tối thiểu $162;
3. Xác định chính xác thông lượng cực đại 10,000 gallons/giờ của mạng lưới đường ống truyền dẫn và đo lường mức độ sụt giảm thông lượng (còn 9,000 gallons/giờ, thời gian đáp ứng kéo dài thêm 11.1%) khi xảy ra sự cố đứt gãy tuyến huyết mạch.

Nghiên cứu mang lại giá trị thực tiễn cao, cung cấp khung quy trình chuẩn giúp doanh nghiệp logistics, sản xuất và hạ tầng năng lượng ra quyết định phân bổ nguồn lực dựa trên dữ liệu định lượng.

---

Bối cảnh và tầm quan trọng

Trong kỷ nguyên chuyển đổi số và tối ưu hóa chuỗi giá trị toàn cầu, việc kiểm soát chi phí vận hành, nâng cao hiệu suất sử dụng tài sản và bảo đảm tính bền vững của mạng lưới cung ứng là yếu tố sống còn đối với mọi doanh nghiệp. Mặc dù lý thuyết Quy hoạch Tuyến tính tổng quát đã được thiết lập vững chắc, việc triển khai LP vào các bài toán cấu trúc mạng đặc thù vẫn đối mặt với nhiều rào cản lớn: độ phức tạp tính toán tăng theo cấp số nhân khi quy mô biến số mở rộng, nguy cơ tắc nghẽn cục bộ và sự thiếu hụt các công cụ đánh giá rủi ro nhanh khi tham số đầu vào biến động.

Khoảng trống nghiên cứu thực tế thường nằm ở việc thiếu tính liên kết giữa chứng minh lý thuyết thuật giải và ứng dụng phần mềm số hóa để quản trị rủi ro. Các doanh nghiệp thường gặp lúng túng khi đối mặt với các câu hỏi: Nếu chi phí vận chuyển một tuyến đường tăng thêm $x$ USD, kế hoạch phân phối hiện tại có còn tối ưu? Nếu nhu cầu tại một điểm tiêu thụ tăng đột biến, nên ký hợp đồng bổ sung với đối tác nào? Hay khi một tuyến đường ống bị tê liệt do sự cố kỹ thuật, hệ thống sẽ tổn thất bao nhiêu phần trăm công suất và mất bao lâu để phục hồi dòng chảy?

Nghiên cứu này có tính thời sự cấp thiết khi giải quyết trực diện bài toán điều phối tài nguyên dưới điều kiện biên ngặt nghèo. Bằng việc lượng hóa các kịch bản bất định, mô hình cung cấp cơ sở khoa học để loại bỏ các điểm nghẽn (bottlenecks), giảm thiểu lãng phí chi phí vận chuyển và nâng cao khả năng chống chịu (resilience) của hệ sinh thái logistics hiện đại.

---

Methodology và tiếp cận nghiên cứu

Nghiên cứu áp dụng thiết kế nghiên cứu định lượng thực nghiệm (Applied Quantitative Research Design), kết hợp giữa mô hình hóa giải tích toán học chuẩn mực và kiểm chứng bằng công cụ tối ưu hóa số Simplex LP.

1. Mô hình Toán học và Kỹ thuật Phân tích

• Bài toán Vận tải (Transportation Problem):
  • Hàm mục tiêu: $\min Z = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij}$
  • Ràng buộc: Tổng cung tại nguồn $\sum_{j=1}^n x_{ij} \le s_i$; Tổng cầu tại đích $\sum_{i=1}^m x_{ij} = d_j$; $x_{ij} \ge 0$.
  • Kỹ thuật giải: Khởi tạo phương án ban đầu bằng Phương pháp Chi phí bé nhất (Least Cost Method); đánh giá và tối ưu hóa nghiệm bằng Phương pháp đường đi kín (Stepping-Stone) thông qua chỉ số cải tiến $I_{ij}$.
• Bài toán Phân công (Assignment Problem):
  • Hàm mục tiêu: $\min Z = \sum_{i=1}^{n} \sum_{j=1}^{n} c_{ij} x_{ij}$ với $x_{ij} \in {0, 1}$.
  • Ràng buộc: $\sum_{j=1}^n x_{ij} = 1$ (mỗi nguồn chỉ thực hiện 1 việc) và $\sum_{i=1}^n x_{ij} = 1$ (mỗi việc chỉ giao cho 1 nguồn).
  • Kỹ thuật giải: Áp dụng Thuật toán Hungarian thông qua các phép biến đổi ma trận rút giảm dòng/cột, phủ số 0 bằng số đường thẳng tối thiểu để trích xuất tập nghiệm độc lập tối ưu.
• Bài toán Dòng chảy Tối đa (Maximum Flow Problem):
  • Hàm mục tiêu: $\max f$
  • Ràng buộc: Cân bằng dòng tại các nút trung gian $\sum x_{ki} - \sum x_{ij} = 0$; Ràng buộc dung lượng $0 \le x_{ij} \le c_{ij}$.
  • Kỹ thuật giải: Triển khai Thuật toán gán nhãn Ford-Fulkerson đa bước lặp để tìm đường tăng dòng và chứng minh tính tối ưu dựa trên Định lý Lát cắt hẹp nhất (Max-Flow Min-Cut Theorem).

2. Độ tin cậy và Kiểm chuẩn Dữ liệu

Toàn bộ dữ liệu tính toán thủ công được kiểm chứng chéo $1:1$ với kết quả chạy trên phần mềm chuyên dụng Excel Solver. Báo cáo phân tích độ nhạy (Sensitivity Report) cung cấp các giá trị Giảm chi phí (Reduced Cost), Giá bóng (Shadow Price), Mức tăng/giảm cho phép (Allowable Increase/Decrease), đảm bảo độ tin cậy và giá trị nội tại (internal validity) của mô hình.

---

Phát hiện chính

Nghiên cứu mang lại 5 phát hiện định lượng then chốt, phản ánh sâu sắc bản chất tối ưu hóa của các bài toán mạng:

========================================================================================
BÀI TOÁN                 MỤC TIÊU TỐI ƯU        KẾT QUẢ TỐI ƯU       GIÁ TRỊ KINH TẾ/VẬN HÀNH
========================================================================================
1. Phân phối Khí đốt    Min Chi phí            Z = $11,900          Tiết kiệm chi phí phân phối;
   (Tri-County)                                                     Xác định đúng đối tác mở rộng
----------------------------------------------------------------------------------------
2. Phân công Đội thợ     Min Chi phí ghép việc  Z = $162             Ghép cặp hoàn hảo 1-1, 
   (CarpetPlus)                                                     không lãng phí nhân lực
----------------------------------------------------------------------------------------
3. Mạng lưới Dầu mỏ     Max Lưu lượng          F = 10,000 gal/h     Thời gian hoàn thành 100k gal
   (Trạng thái chuẩn)                                               chính xác là 10.0 giờ
----------------------------------------------------------------------------------------
4. Mạng lưới Dầu mỏ     Đánh giá sự cố tuyến   F = 9,000 gal/h      Thông lượng giảm 10%, thời gian
   (Đứt gãy dòng 2-3)   huyết mạch                                  kéo dài lên 11 giờ 6 phút 40 giây
========================================================================================

Phát hiện 1: Cơ chế điều chỉnh nghiệm trong Bài toán Vận tải Khí đốt Tri-County

Tại bước khởi tạo ban đầu theo phương pháp chi phí bé nhất, phương án đạt chi phí sơ bộ nhưng chưa tối ưu do tồn tại ô rỗng $(2,1)$ có chỉ số cải tiến âm ($I_{21} = +12 - 10 + 15 - 18 = -1 < 0$). Sau khi điều chỉnh lượng hàng chuyển dịch $\theta = \min(400, 200) = 200$ đơn vị qua chu trình kín, kế hoạch tối ưu cuối cùng được xác lập:

• Southern Gas: Cung cấp 200 đơn vị cho Hamilton (chi phí $2,000) và 300 đơn vị cho Clermont (chi phí $4,500).
• Northwest Gas: Cung cấp 200 đơn vị cho Hamilton (chi phí $2,400) và 200 đơn vị cho Butler (chi phí $3,000).
• Tổng chi phí tối thiểu: $11,900.

Phát hiện 2: Chiến lược mở rộng nguồn cung khi nhu cầu thị trường tăng trưởng

Khi nhu cầu tại Quận Butler tăng thêm 100 đơn vị, mô hình quy hoạch tuyến tính chứng minh rằng việc ký hợp đồng mở rộng với Southern Gas (thay vì Northwest Gas) là quyết định tối ưu. Kế hoạch mới phân bổ lại nguồn lực: Southern Gas cung ứng 300 đơn vị cho Hamilton và 300 cho Clermont; Northwest Gas cung cấp 100 cho Hamilton và 300 cho Butler, đưa tổng chi phí lên $13,200 (mức tăng thêm $1,300 là tối ưu nhất trên toàn cục hệ thống).

Phát hiện 3: Tối ưu hóa phân công lao động 1-1 qua Thuật toán Hungarian

Thông qua 2 bước rút giảm ma trận và hiệu chỉnh phần tử chưa phủ nhỏ nhất ($k=1$), cấu hình ghép việc hoàn hảo cho 5 đội lắp đặt của CarpetPlus được xác lập chính xác:

• Đội Red $\rightarrow$ Công việc 3 ($38)
• Đội White $\rightarrow$ Công việc 5 ($25)
• Đội Blue $\rightarrow$ Công việc 4 ($39)
• Đội Green $\rightarrow$ Công việc 1 ($26)
• Đội Brown $\rightarrow$ Công việc 2 ($34)
• Tổng chi phí gán việc tối thiểu: $162.

Phát hiện 4: Định lượng tác động của đứt gãy mạng lưới trong Bài toán Dòng chảy cực đại

Trong điều kiện vận hành bình thường của mạng lưới 7 kho chứa, lưu lượng tối đa đạt 10,000 gallons/giờ, đáp ứng nhu cầu 100,000 gallons cho Kho số 7 trong đúng 10 giờ. Điểm nghẽn hệ thống được xác định bởi lát cắt hẹp nhất $X = {1, 4, 3, 2}$ và $\bar{X} = {5, 6, 7}$.

Khi xảy ra sự cố kỹ thuật buộc đóng hoàn toàn tuyến ống huyết mạch $2-3$:

• Dung lượng dòng cực đại suy giảm xuống còn 9,000 gallons/giờ (tổn thất $10%$ hiệu năng).
• Thời gian cần thiết để bơm đủ 100,000 gallons cho Kho 7 kéo dài lên 11.11 giờ ($\approx 11$ giờ 6 phút 40 giây).
• Lát cắt nghẽn dịch chuyển về phía đầu nguồn: $X = {1, 2}$ và $\bar{X} = {3, 4, 5, 6, 7}$.

Phát hiện 5: Biên độ an toàn từ Báo cáo Độ nhạy (Sensitivity Analysis)

Phân tích độ nhạy chỉ ra cấu trúc tối ưu có tính bền vững cao trước các dao động giá nhỏ. Điển hình, tuyến vận chuyển Southern Gas – Hamilton có chi phí cơ sở là 10, với biên độ cho phép tăng thêm 2 đơn vị hoặc giảm 1 đơn vị mà không làm đảo lộn kế hoạch phân phối hiện hành. Đối với các tuyến không được phân bổ (như Southern Gas – Butler với chi phí 20), chi phí vận chuyển phải giảm mạnh hơn 7 đơn vị ($< 13$) thì mới có khả năng tham gia vào phương án tối ưu.

---

Đóng góp khoa học

1. Đóng góp về mặt lý thuyết: Hệ thống hóa và làm sáng tỏ bản chất toán học của các bài toán mạng đặc thù dưới góc nhìn Quy hoạch Tuyến tính. Nghiên cứu cung cấp minh chứng trực quan cho Định lý Lát cắt hẹp nhất (Max-Flow Min-Cut Theorem) và tính chất bất biến của không gian nghiệm tối ưu khi thực hiện các phép biến đổi ma trận trong thuật toán Hungarian.
2. Cải tiến phương pháp luận: Xây dựng quy trình tích hợp khép kín giữa "Phân tích thuật giải giải tích $\leftrightarrow$ Mô hình hóa số trên phần mềm $\leftrightarrow$ Đánh giá rủi ro độ nhạy". Quy trình này giúp thu hẹp khoảng cách giữa lý thuyết tối ưu hóa trừu tượng và các bài toán điều hành kinh doanh thực tế.
3. Ứng dụng thực tiễn: Cung cấp bộ công cụ định lượng hỗ trợ các nhà quản trị chuỗi cung ứng, doanh nghiệp logistics và kỹ sư vận hành hạ tầng tính toán nhanh các phương án phân bổ nhân sự, thiết lập lộ trình giao nhận chi phí thấp và chủ động lập kịch bản ứng phó sự cố mạng lưới truyền dẫn.

---

Đối tượng quan tâm

• Nhà nghiên cứu và Giảng viên, Sinh viên: Dùng làm tài liệu chuẩn trong đào tạo các môn Phương pháp định lượng trong kinh doanh, Vận trù học (Operations Research), và Quản lý chuỗi cung ứng.
• Chuyên gia Logistics và Quản lý Chuỗi cung ứng: Ứng dụng trực tiếp vào việc lập kế hoạch phân phối hàng hóa từ các trung tâm phân phối (DC) đến các đại lý nhằm cắt giảm chi phí nhiên liệu và kho bãi.
• Kỹ sư Hạ tầng và Hoạch định Mạng lưới: Ứng dụng mô hình dòng chảy tối đa để thiết kế, mở rộng công suất mạng lưới ống dẫn dầu khí, hệ thống cấp thoát nước đô thị và điều tiết lưu lượng giao thông thông minh.

---

Câu hỏi thường gặp (FAQ)

1. Phát hiện quan trọng nhất của nghiên cứu này là gì?

Nghiên cứu chứng minh rằng việc kết hợp giữa thuật giải toán học (Hungarian, Ford-Fulkerson, Stepping-Stone) và công cụ số (Simplex LP Solver) không chỉ giúp tìm ra nghiệm tối ưu tuyệt đối mà còn xác định được ngưỡng an toàn của chi phí thông qua phân tích độ nhạy, giúp doanh nghiệp duy trì kế hoạch tối ưu ngay cả khi thị trường biến động.

2. Phương pháp tiếp cận trong báo cáo có điểm gì nổi bật so với cách giải thông thường?

Điểm nổi bật là tính kiểm chứng kép ($1:1$) giữa phương pháp giải tích tay từng bước (cho phép hiểu rõ cơ chế vận hành của dòng dữ liệu và chu trình cải tiến) và giải pháp tự động hóa bằng Excel Solver, kèm theo phân tích định lượng chi tiết về các kịch bản đứt gãy mạng lưới (Network Failure Simulation).

3. Kết quả của mô hình có thể tổng quát hóa (generalize) cho các bài toán thực tế quy mô lớn không?

Hoàn toàn có thể. Cấu trúc mô hình quy hoạch tuyến tính và các ràng buộc mạng lưới trong nghiên cứu có tính mở rộng cao (scalable). Khi số lượng điểm cung-cầu hoặc số nút mạng lên tới hàng ngàn, cùng cấu trúc đại số này có thể được nạp vào các solver thương mại quy mô lớn như Gurobi, CPLEX hoặc Python PuLP/OR-Tools.

4. Hướng phát triển tiếp theo (Next Steps) của nghiên cứu là gì?

Nghiên cứu có thể mở rộng sang các bài toán Quy hoạch nguyên hỗn hợp (MILP), bài toán vận tải đa phương thức có xét đến chi phí cố định (Fixed-charge Transportation Problem), và bài toán dòng chảy cực đại trong điều kiện dung lượng mạng mang tính ngẫu nhiên (Stochastic Dynamic Max Flow).

5. Doanh nghiệp vừa và nhỏ (SMEs) có thể ứng dụng kết quả này như thế nào mà không tốn chi phí phần mềm?

Doanh nghiệp có thể tận dụng ngay công cụ Microsoft Excel Solver (tích hợp sẵn, miễn phí) theo đúng quy trình 3 bước được chuẩn hóa trong nghiên cứu để giải quyết bài toán giao việc hàng ngày cho nhân viên hoặc tối ưu hóa tuyến đường giao hàng của đội xe.

---

Kết luận

Báo cáo nghiên cứu đã giải quyết trọn vẹn và chuẩn xác ba bài toán nền tảng của quy hoạch tuyến tính chuyên biệt: Vận tải, Phân công và Dòng chảy Tối đa. Thông qua việc kết hợp hài hòa giữa toán học giải tích và công nghệ tính toán hiện đại, nghiên cứu đã minh chứng sức mạnh vượt trội của các phương pháp định lượng trong việc tiết giảm chi phí, tối ưu hóa công suất và kiểm soát rủi ro vận hành.

Trong tương lai, việc tích hợp các mô hình tối ưu hóa mạng lưới này với dữ liệu thời gian thực (IoT, GPS tracking) và thuật toán học máy dự báo nhu cầu (Machine Learning Forecasting) sẽ mở ra hướng đi mới cho các hệ thống tự hành ra quyết định trong chuỗi cung ứng thông minh. Doanh nghiệp và các nhà nghiên cứu được khuyến khích áp dụng ngay khung phương pháp luận này để nâng cao năng lực cạnh tranh và hiệu quả vận hành.

Trích đoạn nội dung tài liệu

ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA BÁO CÁO BÀI TẬP LỚN Môn: PHƯƠNG PHÁP ĐỊNH LƯỢNG Đề tài : MỘT SỐ BÀI TOÁN ĐẶC BIỆT CÓ LIÊN QUAN ĐẾN QUY HOẠCH TUYẾN TÍNH GVHD: Ths. Võ Thị Ngọc Trân Lớp: L04 – HK232 STT Họ và Tên MSSV Mức độ hoàn thành 1 Nguyễn Tất Phú 2212591 100% Ngô Tấn Tiền 2213479 100% 2 Nguyễn Anh Nhân 2212360 100% 3 Phan Thị Kim Chi 2210372 100% 4 Trương Thị Kim Ngọc 2212277 100% 5 Ngô Hồng Ánh 2210160 100% 6 Võ Gia Lạc 2211805 100% 7 TP.Hồ Chí Minh, T4/2024 MỤC LỤC Phần 1. BÀI TOÁN VẬN TẢI .1 Bài toán vận tải: .2 Giải bài toán vận tải bằng phương pháp chi phí bé nhất .3 Tìm nghiệm tối ưu của bài toán vận tải .2 Xây dựng mô hình và giải bài toán bằng phương pháp truyền thống .3 Dùng phần mềm để giải toán.4 Phân tích rủi ro.

BÀI TOÁN PHÂN CÔNG .1 Bài toán phân công .2 Giải bài toán phân công bằng phương pháp Hungarian .2 Xây dựng mô hình và giải bài toán bằng phương pháp truyền thống .3 Dùng phần mềm để giải toán.4 Phân tích rủi ro. BÀI TOÁN DÒNG CHẢY TỐI ĐA .1 Bài toán dòng chảy tối đa .2 Giải bài toán bằng thuật gán nhãn Ford-Fulkerson .2 Xây dựng mô hình và giải bằng phương pháp truyền thống .3 Dùng phần mềm để giải toán.4 Phân tích rủi ro. 53 TÀI LIỆU THAM KHẢO. BÀI TOÁN VẬN TẢI 1.1 Bài toán vận tải: Giả sử có m điểm cung cấp hàng và n điểm tiêu thụ hàng.

Khả năng cung cấp tối đa của điểm cung cấp thứ cấp i (i=1, 2,. Nhu cầu tối thiểu của điểm tiêu thụ thứ j (j=1, 2,. Giả sử rằng khả năng vận chuyển trên mọi tuyến đường nối liền các điểm cung cấp và điểm tiêu thụ là vô hạn và chi phí vận chuyển một đơn vị sản phẩm từ điểm cung cấp i đến điểm tiêu thụ j là cij. Xác định kế hoạch vận chuyển hàng hóa sao cho chi phí vận chuyển là thấp nhất., n) là lượng hàng vận chuyển từ điểm cung cấp i đến điểm tiêu thụ j.

Bài toán tối ưu được thiết lập như sau: m n Hàm mục tiêu: Minimize chi phí Z=  cij xij i =1 j =1 Các ràng buộc: +Lượng hàng vận chuyển từ một điểm cung cấp không thể vượt quá khả năng tối đa của nó: 1 n x  s i =1 ij i  i=1, 2, .,m +Lượng hàng vận chuyển đến một điểm tiêu thụ phải thỏa mãn nhu cầu tại điểm tiêu thụ đó: m x  s i =1 ij i  j=1, 2, .,m +Ràng buộc về vùng giá trị của biến: Xij ≥0  i=1, 2, .,m Bài toán trên có (m+n) ràng buộc chính, (m×n) biến quyết định và có thể biểu diễn tóm tắt như sau: m n Min Z=  cij xij i =1 j =1 n s.,m Lưu ý: Điều kiện bài toán vận tải chỉ có vùng nghiệm khả dĩ khi tổng lượng cung cấp m n không nhỏ hơn tổng lượng cung yêu cầu:  si   d j i =1 j =1 1.2 Giải bài toán vận tải bằng phương pháp chi phí bé nhất -Ô ứng với chi phí vận chuyển đơn vị nhỏ nhất trong bảng vận tải sẽ được ưu tiên đáp ứng tối đa. -Loại bỏ điểm nguồn đã hết khả năng hoặc điểm đích đã được cung cấp đủ cùng các ô liên quan và xác định lại ô có chi phí nhỏ nhất. -Thực hiện lặp lại hai bước trên cho đến khi toàn bộ nhu cầu đã được thỏa mãn.3 Tìm nghiệm tối ưu của bài toán vận tải Bước 1: Tính toán chỉ số cải tiến Iij cho tất cả các ô rỗng (i,j) trong bảng vận tải. Chỉ số này được tính như sau: +Ứng với mỗi ô rống (i,j) nào đó, vẽ một đường đi kín nối ô này với các ô có gán giá trị trong bảng vận tải bằng các đoạn nằm ngang hoặc thẳng đứng.

+Gán dấu cho các đỉnh của đường đi vẽ trong phần trên sao cho 2 đỉnh thuộc cùng một đoạn có dấu khác nhau, bắt đầu bằng dấu cộng cho ô rỗng nhận xét. + Tính toán chỉ số cải tiến Iij cho ô đang xét. Chỉ số này bằng tổng đại số chi phí vận chuyển của các ô liên quan đến đường đi tương ứng với dấu là dấu được gán trong b. Bước 2: Nếu chỉ sô Iij của mỗi ô rỗng đều có giá trị không âm, lời giải trên là tối ưu.

Nếu tồn tại một số giá trị Iij âm, chọn ra ô có Iij nhỏ nhất và điều chỉnh lượng hàng vận chuyển trên các ô liên quan như sau: 𝑚𝑖𝑛 +Xác định giá trị nhỏ nhất 𝑥𝑖𝑗 trong các ô được gán dấu trừ. 𝑚𝑖𝑛 +Lượng hàng vận chuyển trên các ô được gán dấu trừ sẽ trừ đi một lượng 𝑥𝑖𝑗. +Lượng hàng vận chuyển trên các ô được gán dấu cộng sẽ được cộng thêm một 𝑚𝑖𝑛 lượng 𝑥𝑖𝑗. Bước 3: Xác định lại bảng vận tải và quay trở lại bước 1.1 Bài toán 1 Bài 3 trang 454, Chapter 10, Sách Quantitative Methods for Business, 12th ed Công ty Cơ sở Hạ tầng Tri-County, Inc., cung cấp khí đốt tự nhiên cho khách hàng trong khu vực ba quận.

Công ty mua khí đốt tự nhiên từ hai công ty: Southern Gas và Northwest Gas. Dự báo nhu cầu cho mùa đông sắp tới như sau: Quận Hamilton 400 đơn vị; Quận Butler 200 đơn vị; và Quận Clermont 300 đơn vị; Hợp đồng cung cấp theo như sau: Southern Gas cung cấp 500 đơn vị, và Northwest Gas, 400 đơn vị. Chi phí phân phối cho các 3 quận thay đổi tùy theo vị trí của các nhà cung cấp. Chi phí phân phối trên mỗi đơn vị (tính bằng nghìn đô la) như sau: Từ/Đến Hamilton Butler Clermont Southern Gas 10 20 15 Northwest Gas 12 15 18 a.

Hãy phát triển một biểu đồ mạng lưới đại diện cho bài toán này. Phát triển một mô hình quy hoạch tuyến tính có thể được sử dụng để xác định kế hoạch nhằm giảm thiểu tổng chi phí phân phối. Mô tả kế hoạch phân phối và tính toán tổng chi phí phân phối. Sự tăng trưởng dân số và công nghiệp gần đây ở Quận Butler có khả năng tăng thêm nhu cầu lên đến 100 đơn vị.

Nhà cung cấp nào mà Công ty Tri-County nên ký hợp đồng để cung cấp thêm khả năng phân phối này? 1.2 Xây dựng mô hình và giải bài toán bằng phương pháp truyền thống Câu a) 4 Câu b) *Mô hình hóa bài toán i = 1, 2 với 1 = Southern Gas, 2 = Northwest Gas j = 1, 2, 3 với 1 = Hamilton, 2 = Butler, 3 = Clermont xij: Lượng hàng chuyên chở từ điểm nguồn i đến điểm đích j Hàm mục tiêu: Minimize 𝑍 = 10x11 + 20x12 + 15x13 + 12x21 + 15x22 + 18x23 Ràng buộc hàm: Nguồn cung: 𝑥11 + 𝑥12 + 𝑥13 ≤ 500 𝑥21 + 𝑥22 + 𝑥23 ≤ 400 Nhu cầu: 𝑥11 + 𝑥21 = 400 𝑥12 + 𝑥22 = 200 𝑥13 + 𝑥23 = 300 Ràng buộc biến: 𝑥𝑖𝑗 ≥ 0 i=1, 2; j=1, 2, 3 Câu c) Giải bằng phương pháp chi phí bé nhất ta được lời giải ban đầu Nhà cung Khu vực cấp Hamilton Butler Clermont Southern 10 20 15 500 Gas 400 100 Northwest 12 15 18 400 Gas 200 200 400 200 300 900 Trước tiên ô (1,1) được xét do ô có chi phí thấp nhất, giá trị phân phối được gán cho ô này với bằng với nhu cầu của Hamilon là 400. Sau khi gán giá trị cho ô (1,1), khu vực Hamilton không còn nhu cầu nên ô (2,1) sẽ không được xem xét tiếp. 5 Ô có chi phí thấp nhất kế tiếp là ô (1,3) và (2,2): giá trị cung cấp tối đa được gán cho 2 ô này là 100 và 200 nên ô (2,2) được ưu tiên gán giá trị 200 trước. Sau khi gán, khu vực Butler đã được cung cấp đủ nhu cầu nên ô (1,2) sẽ bị loại bỏ trong bước tiếp theo Trong 2 ô còn lại là (1,3) và (2,3), các giá trị của lượng hàng duy nhất có thể gán được là 100 và 200 Sau khi ta được bảng lời giải ban đầu, ta tiếp tục thực hiện bước cải thiện nghiệm ban đầu cho đến khi đạt được điều kiện tối ưu Xét ô (1,2): đường đi ứng với ô (1,2) được trình bày như trong hình vẽ ở bảng : Nhà cung Khu vực cấp Hamilton Butler Clermont Southern 10 20 15 500 Gas 400 100 Northwest 12 15 18 400 Gas 200 200 400 200 300 900 Chỉ số cải tiến ứng với ô (1,2) là : I12 = +20 – 15 +18 -15 = 8 => Thỏa điều kiện tối ưu Xét ô (2,1): đường đi ứng với ô (2,1) được trình bày như trong hình vẽ ở bảng : Nhà cung Khu vực cấp Hamilton Butler Clermont Southern 10 20 15 500 Gas 400 100 Northwest 12 15 18 400 Gas 200 200 400 200 300 900 6 I21 = +12 -10 +15 -18 = -1 => Chưa thỏa điều kiện tối ưu Như vậy ô (2,1) là ô rỗng duy nhất mà tại đó điều kiện tối ưu bị vi phạm.

Việc cải tiến nghiệm được thực hiện như sau: 𝑚𝑖𝑛 Ta có : 𝑥21 = 𝑚𝑖𝑛(400,200) = 200 Do vậy, các giá trị gán mới tại các ô là: 𝑥11 = 400 − 200 = 200 𝑥23 = 200 − 200 = 0 𝑥13 = 100 + 200 = 300 𝑥21 = 0 + 200 = 200 Bảng vận tải sau điều chỉnh có dạng sau : Nhà cung Khu vực cấp Hamilton Butler Clermont Southern 10 20 15 500 Gas 200 300 Northwest 12 15 18 400 Gas 200 200 400 200 300 900 Kiểm tra chỉ số cải tiến tại ô (1,2) ta được 𝐼12 = 7 => Thỏa điều kiện tối ưu Nhà cung Khu vực cấp Hamilton Butler Clermont Southern 10 20 15 500 Gas 200 300 Northwest 12 15 18 400 Gas 200 200 400 200 300 900 7 Tương tự tại ô (2,3) ta được 𝐼23 = 1=> thỏa điều kiện tối ưu Như vậy kết quả này là kết quả cuối cùng của bài toán Số lượng Chi phí Southern Gas – Hamilto 200 2000 Southern Gas – Clermon 300 4500 Northwest Gas – Hamilto 200 2400 Northwest Gas – Butle 200 3000 Tổng chi phí $11900 Câu d) Để giải quyết bài toán này, ta tăng nhu cầu ở khu vực Butler thêm 100 và tăng nguồn cung của cả 2 nhà cung cấp Southern Gas và Northwest Gas thêm 100.