Giải bài toán vận tải bằng phương pháp fogels

PHƯƠNG PHÁP XẤP XĨ VOGEL

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 xấp xỉ vogel là phương pháp cải tiến phương pháp chi phí thấp nhất thương cho lời giải ban đầu tốt hơn hai phương pháp trên và có thể cho được lời giải tối ưu. Phương pháp gồm các bước:

• Bước 1:
  • Xác định lượng chi phí phạt cho mỗi hàng [cột] bằng cách trừ chi phí nhỏ nhất kế tiếp cho chi phí nhỏ nhất của mỗi hàng [cột].
• Bước 2:
  • Xác định hàng hoặc cột có lượng phạt lớn nhất, tùy chọn nếu có lượng phạt bằng nhau.
  • Phân bổ nhiều nhất có thể vào ô có chi phí nhỏ nhất trong hàng hay cột đã chọn này.
  • 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.
  • 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.
  • Nếu 1 hàng [cột] với lượng cung [cầu] dương và chưa được gạch, xác định các biến cơ bản trong hàng [cột] theo phương pháp chi phí thấp nhất. Dừng lại.
  • Nếu mọi hàng cột chưa gạch đều có lượng cung và lượng cầu bằng 0 thì xác định các biến cơ bản có gía trị không bằng phương pháp chi phí thấp nhất. Dừng lại.
  • Trường hợp khác, quay lại bước 1.

TLTK

Nguyễn Như Phong. Vận trù xác định. NXBĐHQG. 2010