比較價格的方法

Question

我將創建一個我希望購買的產品清單。假設他們都有一個獨特的參考代碼。我有我可以從中購買的供應商清單，爲方便起見，每個供應商對每種產品都使用相同的參考碼。

部分供應商收取運費。如果您花費少於一定金額，其他人只收取運費。某些供應商如果多次購買某些產品，則可能會有所折扣，但可能會有一些限制（例如，免費獲得1次）。

把我想要購買的產品清單和購買所有這些產品的總成本計算在一起非常容易。我想要做的是創建一個腳本來確定分割訂單是否更好。

例如：

零售商A費用：
產品A - £5
產品B - 10£
產品C - 10£
產品d - 10£
送貨 - £5

零售商乙電荷：
產品A - £5
產品B - £12
產品C - £12
產品d - £30
送貨 - £5 - 免費的，如果花£20以上

在這種情況下，如果我想只買產品C，最便宜的是從零售商A.

如果我想購買：
1X產品A
2X產品B
1X產品d

最便宜的是零售商B（因爲可免費送貨）的產品和B然後拆分訂單並從零售商A購買產品D（因爲即使在交貨時，即使交貨價格也顯着較低）。

所以在我的腦海裏，這不是一項複雜的工作，我可以在紙上很容易地完成。問題是，我如何將其轉換爲代碼。我不是在尋找代碼來實現它 - 只是一些關於如何實現它的理論的指導。

Answer 1

如果我們將問題侷限於簡單地選擇從哪個供應商購買每個產品，並且如果您花費供應商依賴的金額獲得供應商依賴的運輸成本降低，那麼您可以將您的問題制定爲整數線性程序（IP或ILP），這對懷疑是NP難題的問題是一個很好的策略，因爲已經開發了很多研究和軟件包，試圖在實踐中快速解決ILP。你可以在線閱讀線性規劃和ILP。 ILP問題實例包含變量，變量的線性約束以及要最小化或最大化的線性目標。以下是針對您的問題設置的ILP：

對於供應商銷售的每種產品，您都有一個供應商產品變量，它告訴您將從供應商處購買多少產品。對於這些變量中的每一個，您都有一個約束條件，即變量必須> = 0。對於您希望購買的每種產品，您都有一個約束條件，即該產品的所有供應商產品變量的總和必須等於你想購買的產品。

然後，對於提供運費折扣的每個供應商，您都有一個運費折扣變量，如果您沒有獲得折扣，則該變量爲0，如果您這樣做，則爲1。對於這些運輸折扣變量中的每一個，您都有約束條件，即該變量必須> = 0且< = 1;您還有一個約束條件，即當您將供應商的每個供應商產品變量乘以該供應商的該產品的價格並將其全部添加給供應商（這樣您可以獲得您在供應商處花費的總金額）時，此金額> =供應商的運輸折扣變量乘以供應商獲得折扣所需花費的最低金額。

對於每個供應商，您也有供應商變量，如果您使用供應商，則爲1;如果您不使用供應商變量，則爲0。對於這些供應商變量A中的每一個，您都有約束條件1> = A> = 0，並且對於供應商的每個供應商產品變量B，您都有一個約束A> = B/N，其中N是項目的總數你想買。

最後，您想要最大化的目標是通過將每個供應商產品變量乘以該產品的供應商價格，將其全部加起來（將此部分稱爲目標X），然後將每個供應商的運輸折扣變量通過降低運輸成本，您可以獲得折扣，將其全部加起來（稱爲目標Y的這一部分），然後將每個供應商變量乘以供應商的未折扣運輸成本，然後將其全部加起來（將此部分稱爲目標Z），那麼你的目標就是儘量減少X - Y + Z.這就是你需要定義ILP的全部內容，然後你可以將它提供給一個ILP解算器，並希望能夠快速得到解決方案。

Answer 2

混合整數線性規劃適用於您的問題。

您可以使用免費的解算器，如Coin Clp。如果你想知道商業MILP求解器的性能，你可以在這裏找到一些基準：http://plato.asu.edu/bench.html。

如果您想大致瞭解解決問題所需的時間，可以在NEOS服務器上運行問題：http://www.neos-server.org/neos/。

當你有很多0-1變量時，你也可以考慮使用Constraint Programming，它通常適用於重組合問題。

MILP和CP算法都使用分支定界技術，這比快速枚舉更快。

乾杯