爲多個供應商（供應商）訂購多個物料（零件）的最佳選擇

Question

此處的任務是定義供應商訂購物料（零件）的最佳方式（如下所述）。

表模式的相關部分（有一些樣本數據）

項目

ID NUMBER 
1 Item0001 
2 Item0002 
3 Item0003 

供應商

ID NAME   DELIVERY DISCOUNT 
1 Supplier0001 0  0 
2 Supplier0002 0  0.025 
3 Supplier0003 20  0 

DELIVERY是送貨費（以美元）在每次交貨時由該供應商徵收。 DISCOUNT是該供應商允許按時支付的結算折扣（作爲百分比，即上面的ID=2的2.5％）。

SupplierItems

SUPPLIER_ID ITEM_ID PRICE 
1   2  21.67 
1   5  45.54 
1   7  32.97 

這是供應商和項目之間的許多一對多連接的價格，對於該項目（以美元計）的供應商費用。每件產品至少有1個供應商，但有些供應商不止一個。供應商可能沒有物品。

PartsRequests

ID ITEM_ID QUANTITY LOCATION_ID ORDER_ID 
1 59  4  2   (null) 
2 89  5  2   (null) 
3 42  4  2   (null) 

此表是從野外現場的請求進行排序，由供應商到該網站提供的部分。向網站交付任何數量的物品都會吸引運費。當零件訂購，ORDER_ID被插入到表中，所以我們只關注那些ORDER_ID IS NULL

的問題是，什麼是最佳的方式來訂購這些零件每個'位置」，其中有3級優化的解決方案需要呈現給用戶進行選擇。

1. 訂單與供應商的數量最少的組合
2. 訂單與即QUANTITY*PRICE每個項目的總和加上最低的總成本DELIVERY爲求和每個訂單的組合的所有訂單忽略DISCOUNT
3. 如項2，但佔DISCOUNT

顯然我需要確定可用的訂單的組合，然後確定最佳的人變得微不足道但我有點卡在一個有效的方式來處理構建組合。

我在SQL Server 2008中用隨機數據構建了一些SQL小提琴。 This one共有100個產品，10個供應商和100個請求。 This one有1000個產品，50個供應商和250個請求。表格模式是相同的。

更新

我的理由是，該解決方案必須是遞歸和我建了一個漂亮的表值函數來獲取，但我遇到了在SQL Server上的遞歸32硬性限制。無論如何，我感到不舒服，因爲它暗示了更多的程序語言解決方案，而不是RDMS。

所以我現在CTE遞歸玩。

根查詢：

SELECT DISTINCT 
     '' SOLUTION_ID 
     ,LOCATION_ID 
     ,SUPPLIER_ID 
     ,(subquery I haven't quite worked out) SOLE_SUPPLIER 
FROM PartsRequests pr 
    INNER JOIN 
    SupplierItems si ON pr.ITEM_ID=si.ITEM_ID 
WHERE pr.ORDER_ID IS NULL 

這得到了所有可提供所需物品和肯定是一個解決方案，可能不是最佳的供應商。如果供應商是該地點所需的任何產品的唯一供應商，子查詢會設置一個標誌;如果是的話，他們必須是任何解決方案的一部

遞歸部分是通過CTE.SUPPLIER_ID <> CTE.SUPPLIER_ID逐個移除供應商，如果他們仍然覆蓋所有項目，則添加它們。該SOLUTION_ID將被刪除供應商的CSV列表，部分唯一標識每個解決方案，部分對證，所以我得到的組合，而不是排列。

仍在研究細節，此更新的目的是爲了讓社區說「Yay，看起來像那樣會工作」，或者，也可以選擇「You muron，因爲...不會工作」

謝謝

Answer 1

這是一個更一般的答案（因爲在，而不是SQL），因爲我認爲解決這個問題需要更強大的東西。你的第一個場景是選擇最少數量的供應商。這個問題可以看作是set cover problem，因爲您試圖覆蓋供應商每個站點的所有需求。這個問題已經是NP完成了。

你的第三個場景似乎是基本相同的第二位。假設您按時支付每筆訂單，您只需在價格中考慮折扣。

第二種情況是至少NP難，因爲我看到了很多與facility location problem相似的。您正試圖根據其價格和交付成本（開倉成本）來決定使用（開放）哪些供應商（設施）來支付您的訂單（需求）。

歷數你可能的解決方案似乎是不可行的，與10個供應商，你有2^10的可能性使用它們的，由需求的分佈內部進一步複雜化。

我會建議一些動態規劃以首先選擇您必須使用的供應商（=他們是唯一提供特定事物的供應商），從而消除一些可能性（如果供應商A +的交貨成本A <成本對於供應商B），然後試圖擴大你可能的解決方案。線性規劃也是一個有效的思路。