1

这里的任务是定义从供应商处订购物品（零件）的最佳（如下详述）方式。

表模式的相关部分（带有一些示例数据）是

项目

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的结算折扣（百分比，即上述的 2.5% ）。ID=2

供应商物品

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

这是供应商和项目之间的多对多连接，供应商为该项目收取的价格（以美元为单位）。每个项目至少有 1 个供应商，但有些有多个。供应商可能没有项目。

零件请求

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 小提琴。这个有 100 个项目，10 个供应商和 100 个请求。这个有 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 列表，部分用于唯一标识每个解决方案，部分用于检查，因此我得到组合而不是排列。

仍在研究细节，此更新的目的是让社区说“是的，看起来那会起作用”，或者“你这个白痴，那不会起作用，因为......”

谢谢

4

1 回答 1

3

这是一个更一般的答案（如，而不是 sql），因为我认为解决这个问题需要更强大的东西。您的第一个方案是选择最少数量的供应商。当您试图通过供应商满足每个站点的所有需求时，可以将此问题视为集合覆盖问题。这个问题已经是NP完全的。

您的第三种情况似乎与第二种情况基本相同。假设您按时支付每笔订单，您只需在价格中考虑折扣。

第二种情况至少是 NP 难的，因为我看到与设施位置问题有很多相似之处。您正在尝试根据价格和交付成本（开放成本）来决定使用（开放）哪些供应商（设施）来满足您的订单（需求）。

列举你可能的解决方案似乎是不可行的，因为有 10 个供应商，你有 2^10 种使用它们的可能性，内部需求分布进一步复杂化。

我建议进行一些动态编程来首先选择您必须使用的供应商（=他们是唯一交付特定物品的供应商），消除一些可能性（如果供应商 A 的成本 + 交付成本 A < 供应商 B 的成本）然后尝试扩展您的一组可能的解决方案。线性规划也是一种有效的思路。

于 2013-01-28T16:08:23.003 回答