PHƯƠNG PHÁP CHI PHÍ THẤP NHẤT

PHƯƠNG PHÁP CHI PHÍ THẤP NHẤT

Nguyễn Như Phong

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

Đại học Bách Khoa TPHCM

Phương pháp góc tây bắc tuy đơn giản nhưng thường không cho lời giải ban đầu tốt vì không tính đến chi phí. Phương pháp chi phí thấp nhất sẽ cho lời giải tốt hơn vì có tính đến chi phí theo các bước sau:

Bước 1:
- Phân bổ nhiều nhất có thể vào ô chưa bị gạch có chi phí đơn vị thất nhất hiện tại.
- Khấu trừ lượng đã phân bổ cho các lượng cung ở nguồn và lượng cầu ở đích tương ứng.
Bước 2:
- Gạch bỏ hàng ứng với điểm nguồn có lượng cung bằng 0 hay cột ứng với điểm đích có lượng cầu bằng 0.
- Nếu cả hàng và cột đều có lượng cung và lượng cầu về 0 thì chỉ gạch hoặc hàng hoặc cột.
Bước 3:
- Nếu chỉ còn 1 hàng hay 1 cột chưa được gạch thì dừng lại, đã có lời giải.
- Nếu còn nhiều hơn 1 hàng hay cột chưa được gạch thì quay về bước 1.