GIẢI THUẬT VẬN TẢI

Nguyễn Như Phong

Kỹ thuật Hệ thống Công nghiệp

Đại học Bách Khoa TPHCM

Mô hình vận tải là một mô hình LP nên giải thuật vận tải có các bước như các bước của giải thuật đơn hình. Tuy nhiên vì mô hình vận tải có cấu trúc đặc biệt nên giải thuật vận tải nhìn chung là đơn giản hơn giải thuật đơn hình. Giải thuật vận tải sử dụng bảng vận tải thay vì bảng đơn hình ở giải thuật đơn hình.

Các bước của giải thuật vận tải gồm hai bước:

Bước 1. Xác định lời giải cơ bản ban đầu
Bước 2. Xác định lời giải tối ưu.

Với một bài toán vận tải tổng quát có m điểm nguồn và n điểm đích sẽ có m+n phương trình ràng buộc. Vì bài toán cân bằng nên trong m+n phương trình ràng buộc này sẽ có 1 phương trình thừa. Số phương trình độc lập là m+n–1, nên số biến cơ bản của mô hình là m+n–1.

a. Xác định lời giải ban đầu

Cấu trúc đặc biệt của bài toán vận tải giúp xác định lời giải ban đầu mà không phải sử dụng các biến nhân tạo. Các phương pháp xác định lời giải ban đầu:

Phương pháp góc tây bắc
Phương pháp chi phí thấp nhất
Phương pháp xấp xỉ Vogel

Phương pháp góc tây bắc là đơn giản nhất nên thường cho lời giải xấu nhất. Phương pháp xấp xỉ vogel thường cho lời giải tốt nhất.

b. Xác định lời giải tối ưu

Sau khi đã xác định lời giải ban đầu, ta chuyển sang xác định lời giải tối ưu. Bước xác định lời giải tối ưu bao gồm nhiều vòng lặp với hai bước:

Bước 1:
- Kiểm tra điều kiện tối ưu
  - Thỏa điều kiện tối ưu – dừng
  - Không thỏa điều kiện tối ưu –
    - Xác định biến vào từ các biến không cơ bản
    - Chuyển sang bước 2.
Bước 2.
- Sử dụng điều kiện khả thi xác định biến ra từ các biến cơ bản
- Xác định lời giải cơ bản mới.
- Quay về bước 2.