Gérard Cornuéjols1, Marshall L. Fisher2, George L. Nemhauser1
1CORE, University of Louvain, Belgium
2University of Pennsylvania,
Tóm tắt
Số ngày cần thiết để thanh toán một tấm séc được rút từ một ngân hàng ở thành phố j phụ thuộc vào thành phố i nơi tấm séc được thanh toán. Do đó, để tối đa hóa số vốn có sẵn, một công ty phải trả hóa đơn cho nhiều khách hàng ở các vị trí khác nhau có thể thấy lợi ích trong việc duy trì tài khoản ở một vài ngân hàng có vị trí chiến lược. Chúng tôi sẽ thảo luận về vấn đề xác định vị trí tối ưu của các tài khoản ngân hàng để tối đa hóa thời gian thanh toán. Tầm quan trọng của vấn đề này phụ thuộc một phần vào sự tương đương toán học của nó với vấn đề xác định vị trí nhà máy không bị hạn chế nổi tiếng. Chúng tôi trình bày một phương pháp đối ngẫu Lagrangian để thu được một giới hạn trên và các quy trình heuristics để có được một giới hạn dưới về giá trị của một giải pháp tối ưu. Kết quả chính của chúng tôi là các phân tích xấu nhất về các giới hạn này. Cụ thể, chúng tôi chỉ ra rằng sai số tương đối của giới hạn đối ngẫu và một quy trình heuristics "tham lam" không bao giờ vượt quá [(K − 1)/K]k < 1/e cho một vấn đề mà tại đó tối đa K địa điểm sẽ được chọn. Hai quy trình heuristics khác được chỉ ra có sai số tương đối trong trường hợp xấu nhất ít nhất là (k − 1)/(2K − 1) < 1/2. Các ví dụ được đưa ra cho thấy rằng tất cả các giới hạn này có thể đạt được. Chúng tôi trình bày các kết quả tính toán rộng rãi cho các xấp xỉ này.
