英文:
How would I go about finding the optimal way to split up an order
问题
我有一个问题（我觉得我可能过于复杂化了），但是我似乎无法解决。
我有两个数据框。一个包含我想购买的物品及其数量的列表。我有另一个数据框，其中包含供应商、单位成本和可用物品数量的列表。除此之外，我还有一个包含每个供应商运费的数据框。
我想找到在供应商之间分配订单以最小化成本的最佳方法。
一些建议：
- 供应商并不总是能够满足物品的全部订单，所以我还想能够在供应商之间分割单个物品，如果这样做更便宜的话。
- 运费每个供应商只会添加一次（从一个供应商购买两件物品意味着我仍然只为该供应商支付一次运费）。
我看到有人提到过在类似问题上使用cvxpy，但我很难找到如何在我的问题中使用它的方法（以前从未使用过它）。
一些建议会很棒。
TIA
英文:
I have a problem (that I think I'm over complicating) but for the life of me I can't seem to solve it.
I have 2 dataframes. One containing a list of items with quantities that I want to buy. I have another dataframe with a list of suppliers, unit cost and quantity of items available. Along with this I have a dataframe with shipping cost for each supplier.
I want to find the optimal way to break up my order among the suppliers to minimise costs.
Some added points:
- Suppliers won't always be able to fulfil the full order of an item so I want to also be able to split an individual item among suppliers if it is cheaper
- Shipping only gets added once per supplier (2 items from a supplier means I still only pay shipping once for that supplier)
I have seen people mention cvxpy for a similar problem but I'm struggling to find a way to use it for my problem (never used it before).
Some advice would be great.
Note: You don't have to write all the code for me but giving a bit of guidance on how to break down the problem would be great.
TIA
答案1
得分: 2
这是一个数学模型的示例。
蓝色符号是数据（外生变量），红色符号是决策变量（内生变量）。第一个约束将需求分配给供应商。第二个约束实施了以下蕴含：
use展开收缩 = 0 ==> buy[i,s] = 0
我们不需要：
use展开收缩 = 1 ==> buy[i,s] > 0
因为目标函数的结构确保我们不会在不从供应商发货的情况下使用供应商。
代码的实现留给读者。这不应该很困难：尽量贴近数学模型。还要注意模型中的细节（这里每一点都很重要，没有多余的内容）。
一个小测试使用以下随机数据：
---- 25 PARAMETER demand 物品的需求
item1 2.000, item2 9.000, item3 6.000, item4 4.000, item5 3.000, item6 3.000, item7 4.000
item8 9.000, item9 1.000, item10 6.000, item11 10.000, item12 6.000, item13 10.000, item14 8.000
item15 2.000, item16 7.000, item17 2.000, item18 3.000, item19 7.000, item20 5.000, item21 4.000
item22 4.000, item23 2.000, item24 2.000, item25 6.000, item26 9.000, item27 3.000, item28 7.000
item29 8.000, item30 4.000, item31 2.000, item32 6.000, item33 2.000, item34 9.000, item35 3.000
item36 3.000, item37 6.000, item38 8.000, item39 7.000, item40 5.000, item41 5.000, item42 2.000
item43 4.000, item44 1.000, item45 4.000, item46 2.000, item47 7.000, item48 6.000, item49 8.000
item50 3.000
---- 25 PARAMETER avail 物品的可用性
供应商1 供应商2 供应商3 供应商4 供应商5 供应商6 供应商7 供应商8 供应商9 供应商10
item1 5.000 6.000 5.000 2.000 5.000 4.000 6.000
item2 1.000 4.000 6.000 1.000 4.000 4.000 3.000 2.000
item3 1.000 1.000 1.000 7.000 3.000 6.000 2.000 1.000 5.000
item4 1.000 2.000 3.000 1.000 1.000 2.000 2.000 2.000 7.000
item5 7.000 2.000 2.000 6.000 3.000 7.000 5.000 4.000
item6 3.000 4.000 5.000 1.000 3.000 2.000 1.000 7.000
item7 3.000 1.000 3.000 2.000 2.000 7.000 1.000 2.000 3.000
item8 3.000
英文:
Here is an example of what a mathematical model can look like.
The blue symbols are data (exogenous) and the red symbols are decision variables (endogenous). The first constraint distributes demand over the suppliers. The second constraint implements the implication:
use展开收缩 = 0 ==> buy[i,s] = 0
We don't need:
use展开收缩 = 1 ==> buy[i,s] > 0
because of the structure of the objective function. The costs make sure we never use a supplier while not shipping from there.
The implementation in code is left to the reader. This should not be very difficult: try to stick as closely as possible to the mathematical model. Also, pay attention to the details in the model (everything counts here, there is no fluff).
A small test uses the following random data:
---- 25 PARAMETER demand demand for items
item1 2.000, item2 9.000, item3 6.000, item4 4.000, item5 3.000, item6 3.000, item7 4.000
item8 9.000, item9 1.000, item10 6.000, item11 10.000, item12 6.000, item13 10.000, item14 8.000
item15 2.000, item16 7.000, item17 2.000, item18 3.000, item19 7.000, item20 5.000, item21 4.000
item22 4.000, item23 2.000, item24 2.000, item25 6.000, item26 9.000, item27 3.000, item28 7.000
item29 8.000, item30 4.000, item31 2.000, item32 6.000, item33 2.000, item34 9.000, item35 3.000
item36 3.000, item37 6.000, item38 8.000, item39 7.000, item40 5.000, item41 5.000, item42 2.000
item43 4.000, item44 1.000, item45 4.000, item46 2.000, item47 7.000, item48 6.000, item49 8.000
item50 3.000
---- 25 PARAMETER avail availability of items
supplier1 supplier2 supplier3 supplier4 supplier5 supplier6 supplier7 supplier8 supplier9 supplier10
item1 5.000 6.000 5.000 2.000 5.000 4.000 6.000
item2 1.000 4.000 6.000 1.000 4.000 4.000 3.000 2.000
item3 1.000 1.000 1.000 7.000 3.000 6.000 2.000 1.000 5.000
item4 1.000 2.000 3.000 1.000 1.000 2.000 2.000 2.000 7.000
item5 7.000 2.000 2.000 6.000 3.000 7.000 5.000 4.000
item6 3.000 4.000 5.000 1.000 3.000 2.000 1.000 7.000
item7 3.000 1.000 3.000 2.000 2.000 7.000 1.000 2.000 3.000
item8 3.000 2.000 1.000 4.000 4.000 6.000 7.000
item9 4.000 4.000 2.000 4.000 5.000 4.000 1.000 5.000 4.000
item10 7.000 1.000 5.000 6.000 7.000 1.000 2.000 1.000 1.000 5.000
item11 5.000 1.000 3.000 1.000 5.000 6.000 1.000 3.000 5.000
item12 6.000 4.000 7.000 1.000 4.000 1.000 5.000
item13 3.000 6.000 3.000 4.000 4.000 3.000 7.000 1.000 1.000
item14 1.000 6.000 4.000 1.000 7.000 2.000
item15 4.000 2.000 5.000 1.000 3.000 3.000 6.000 4.000 3.000 4.000
item16 7.000 2.000 7.000 4.000 2.000 7.000 6.000 7.000
item17 4.000 1.000 5.000 2.000 7.000 7.000 2.000 5.000 4.000
item18 6.000 7.000 4.000 2.000 3.000 6.000 4.000 5.000
item19 5.000 5.000 7.000 5.000 7.000 6.000 4.000 5.000 5.000
item20 6.000 4.000 3.000 5.000 1.000 1.000 6.000 7.000
item21 6.000 5.000 2.000 6.000 6.000 6.000 1.000 3.000
item22 2.000 3.000 2.000 1.000 6.000 3.000 1.000 3.000 2.000 7.000
item23 3.000 2.000 3.000 5.000 5.000 2.000 7.000 1.000
item24 7.000 3.000 2.000 3.000 3.000 6.000 6.000
item25 3.000 2.000 7.000 5.000 7.000 7.000 7.000 6.000 3.000
item26 4.000 6.000 4.000 4.000 4.000 5.000 1.000 2.000 2.000
item27 4.000 2.000 1.000 5.000 4.000 4.000 5.000 5.000 6.000
item28 5.000 1.000 4.000 5.000 1.000 2.000 4.000 5.000 3.000 1.000
item29 7.000 7.000 7.000 6.000 1.000 4.000 1.000
item30 7.000 6.000 2.000 3.000 2.000 4.000 3.000 3.000
item31 7.000 1.000 1.000 4.000 5.000 2.000 1.000 7.000 2.000
item32 2.000 6.000 1.000 3.000 2.000 3.000 5.000 4.000 1.000
item33 1.000 2.000 4.000 2.000 5.000 5.000 2.000 6.000 1.000
item34 5.000 5.000 6.000 4.000 2.000 4.000 3.000 6.000 2.000
item35 4.000 5.000 7.000 4.000 3.000 5.000 4.000 7.000
item36 6.000 1.000 2.000 5.000 3.000 7.000 7.000 7.000 2.000 3.000
item37 4.000 7.000 1.000 5.000 6.000 4.000 6.000 2.000 3.000
item38 2.000 4.000 4.000 4.000 4.000 7.000 2.000 6.000 7.000 7.000
item39 2.000 2.000 1.000 1.000 5.000 2.000 6.000 4.000 2.000 5.000
item40 6.000 3.000 2.000 5.000 3.000 4.000 2.000 5.000
item41 7.000 3.000 1.000 4.000 2.000 7.000 4.000 3.000 1.000
item42 4.000 4.000 2.000 2.000 4.000 4.000 3.000 7.000 3.000
item43 1.000 3.000 3.000 1.000 5.000 4.000 4.000 6.000
item44 6.000 2.000 1.000 3.000 2.000 4.000 7.000
item45 6.000 6.000 5.000 3.000 3.000 6.000 7.000 4.000 2.000 3.000
item46 2.000 3.000 6.000 4.000 5.000 6.000 3.000 7.000 3.000
item47 3.000 5.000 5.000 4.000 1.000 4.000 4.000 5.000 1.000 1.000
item48 7.000 3.000 7.000 2.000 7.000 3.000 4.000 1.000 1.000
item49 5.000 6.000 4.000 7.000 3.000 2.000 6.000 6.000 7.000
item50 4.000 3.000 5.000 4.000 2.000 1.000
---- 25 PARAMETER shipcost shipping cost
supplier1 23.574, supplier2 15.066, supplier3 27.148, supplier4 35.761, supplier5 11.076, supplier6 20.661
supplier7 20.136, supplier8 24.595, supplier9 17.781, supplier10 36.736
---- 25 PARAMETER itemcost cost of items
supplier1 supplier2 supplier3 supplier4 supplier5 supplier6 supplier7 supplier8 supplier9 supplier10
item1 4.397 3.538 4.946 4.032 3.032 4.071 4.329
item2 3.336 3.300 3.227 3.414 4.908 3.216 4.740 2.653
item3 4.226 1.003 2.821 2.677 1.063 1.328 3.395 3.221 3.472
item4 4.540 1.759 2.712 1.666 4.545 3.706 4.453 1.371 4.986
item5 3.467 1.003 3.436 1.695 2.245 3.916 1.339 2.768
item6 3.636 2.938 2.273 4.656 1.737 4.488 2.824 2.836
item7 1.496 1.415 1.940 2.361 4.492 4.379 4.292 2.922 4.655
item8 4.717 1.432 2.402 4.440 2.362 1.852 4.705
item9 2.443 4.504 1.593 2.824 2.073 2.187 1.462 2.599 4.647
item10 2.006 1.412 1.585 2.545 1.186 1.106 1.616 1.291 4.315 2.599
item11 2.669 4.889 1.974 2.448 3.521 1.971 1.404 2.624 2.916
item12 1.580 3.039 4.541 1.222 3.030 4.056 4.916
item13 3.882 4.488 2.198 4.016 4.375 2.873 3.620 2.512 2.435
item14 2.018 2.022 2.802 4.779 2.342 1.194
item15 4.226 3.930 4.680 2.327 1.839 1.189 4.532 1.371 4.348 2.855
item16 1.001 1.626 3.820 2.121 3.542 3.320 4.848 3.057
item17 3.361 3.270 1.120 4.876 3.375 1.238 3.176 1.509 2.682
item18 4.526 3.866 2.254 4.972 1.221 3.476 4.218 2.186
item19 4.836 3.779 3.526 3.464 3.092 1.564 4.347 4.568 3.786
item20 2.247 2.423 4.044 1.545 3.867 4.855 2.768 2.058
item21 2.777 2.587 2.468 3.485 4.439 4.020 4.603 2.752
item22 1.276 4.754 4.376 4.802 3.318 1.141 2.630 1.230 3.128 1.450
item23 4.575 1.967 3.569 2.163 4.254 1.745 3.003 4.755
item24 3.726 1.741 4.492 1.660 2.723 4.087 4.912
item25 4.778 1.995 4.546 4.538 4.860 3.997 3.590 3.994 3.093
item26 3.744 3.764 4.463 4.183 1.870 3.358 4.690 3.412 1.143
item27 4.644 3.260 2.299 2.560 2.197 1.876 4.287 1.611 4.802
item28 1.128 3.938 1.442 2.951 2.444 1.866 4.695 2.800 4.884 1.385
item29 2.916 3.889 2.733 1.633 1.403 4.222 2.595
item30 1.468 4.497 1.579 1.711 3.181 2.874 4.637 3.892
item31 1.665 2.310 3.325 3.310 3.510 1.107 1.518 1.257 2.244
item32 3.314 4.239 3.717 3.943 2.354 1.897 4.600 4.318 2.265
item33 4.809 2.027 3.504 4.885 4.848 2.701 1.422 1.308 3.577
item34 2.249 3.381 3.426 3.535 4.833 1.329 1.501 3.421 3.966
item35 4.390 2.410 3.566 4.583 2.553 2.094 4.882 2.385
item36 2.638 4.759 3.412 4.598 2.139 1.889 3.299 3.038 3.230 2.377
item37 2.593 4.105 1.113 2.450 4.023 2.900 1.305 1.390 2.319
item38 1.802 1.363 2.795 2.851 4.248 2.800 4.817 1.491 2.626 4.545
item39 3.813 4.500 3.221 2.023 2.037 2.420 1.548 4.228 2.304 2.715
item40 1.036 1.897 3.643 2.150 1.524 2.628 1.646 4.447
item41 2.511 4.554 2.080 4.110 2.691 2.719 1.996 2.527 1.284
item42 3.863 3.812 1.281 4.874 2.080 2.273 4.534 3.345 2.528
item43 4.892 3.683 4.805 3.873 2.774 4.519 2.879 2.855
item44 2.486 1.473 4.862 4.374 3.885 4.858 2.458
item45 4.073 2.330 3.168 1.554 2.255 1.320 4.737 2.977 3.716 3.766
item46 1.219 1.961 4.531 1.402 3.713 1.406 1.171 4.014 4.948
item47 1.059 1.587 4.964 1.529 1.342 1.744 4.161 4.458 3.992 2.558
item48 4.180 3.484 4.045 3.321 3.654 1.329 3.267 2.773 2.313
item49 2.322 1.492 3.471 3.136 1.576 2.569 1.059 4.483 1.982
item50 4.213 1.336 4.949 3.233 3.728 4.438
---- 25 PARAMETER totalavail total availability
item1 33.000, item2 25.000, item3 27.000, item4 21.000, item5 36.000, item6 26.000, item7 24.000
item8 27.000, item9 33.000, item10 36.000, item11 30.000, item12 28.000, item13 32.000, item14 21.000
item15 35.000, item16 42.000, item17 37.000, item18 37.000, item19 49.000, item20 33.000, item21 35.000
item22 30.000, item23 28.000, item24 30.000, item25 47.000, item26 32.000, item27 36.000, item28 31.000
item29 33.000, item30 30.000, item31 30.000, item32 27.000, item33 28.000, item34 37.000, item35 39.000
item36 43.000, item37 38.000, item38 47.000, item39 30.000, item40 30.000, item41 32.000, item42 33.000
item43 27.000, item44 25.000, item45 45.000, item46 39.000, item47 33.000, item48 35.000, item49 46.000
item50 19.000
---- 25 PARAMETER short shortages
( ALL 0.000 )
---- 25 PARAMETER maxbuy upperbound on buy
supplier1 supplier2 supplier3 supplier4 supplier5 supplier6 supplier7 supplier8 supplier9 supplier10
item1 2.000 2.000 2.000 2.000 2.000 2.000 2.000
item2 1.000 4.000 6.000 1.000 4.000 4.000 3.000 2.000
item3 1.000 1.000 1.000 6.000 3.000 6.000 2.000 1.000 5.000
item4 1.000 2.000 3.000 1.000 1.000 2.000 2.000 2.000 4.000
item5 3.000 2.000 2.000 3.000 3.000 3.000 3.000 3.000
item6 3.000 3.000 3.000 1.000 3.000 2.000 1.000 3.000
item7 3.000 1.000 3.000 2.000 2.000 4.000 1.000 2.000 3.000
item8 3.000 2.000 1.000 4.000 4.000 6.000 7.000
item9 1.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000
item10 6.000 1.000 5.000 6.000 6.000 1.000 2.000 1.000 1.000 5.000
item11 5.000 1.000 3.000 1.000 5.000 6.000 1.000 3.000 5.000
item12 6.000 4.000 6.000 1.000 4.000 1.000 5.000
item13 3.000 6.000 3.000 4.000 4.000 3.000 7.000 1.000 1.000
item14 1.000 6.000 4.000 1.000 7.000 2.000
item15 2.000 2.000 2.000 1.000 2.000 2.000 2.000 2.000 2.000 2.000
item16 7.000 2.000 7.000 4.000 2.000 7.000 6.000 7.000
item17 2.000 1.000 2.000 2.000 2.000 2.000 2.000 2.000 2.000
item18 3.000 3.000 3.000 2.000 3.000 3.000 3.000 3.000
item19 5.000 5.000 7.000 5.000 7.000 6.000 4.000 5.000 5.000
item20 5.000 4.000 3.000 5.000 1.000 1.000 5.000 5.000
item21 4.000 4.000 2.000 4.000 4.000 4.000 1.000 3.000
item22 2.000 3.000 2.000 1.000 4.000 3.000 1.000 3.000 2.000 4.000
item23 2.000 2.000 2.000 2.000 2.000 2.000 2.000 1.000
item24 2.000 2.000 2.000 2.000 2.000 2.000 2.000
item25 3.000 2.000 6.000 5.000 6.000 6.000 6.000 6.000 3.000
item26 4.000 6.000 4.000 4.000 4.000 5.000 1.000 2.000 2.000
item27 3.000 2.000 1.000 3.000 3.000 3.000 3.000 3.000 3.000
item28 5.000 1.000 4.000 5.000 1.000 2.000 4.000 5.000 3.000 1.000
item29 7.000 7.000 7.000 6.000 1.000 4.000 1.000
item30 4.000 4.000 2.000 3.000 2.000 4.000 3.000 3.000
item31 2.000 1.000 1.000 2.000 2.000 2.000 1.000 2.000 2.000
item32 2.000 6.000 1.000 3.000 2.000 3.000 5.000 4.000 1.000
item33 1.000 2.000 2.000 2.000 2.000 2.000 2.000 2.000 1.000
item34 5.000 5.000 6.000 4.000 2.000 4.000 3.000 6.000 2.000
item35 3.000 3.000 3.000 3.000 3.000 3.000 3.000 3.000
item36 3.000 1.000 2.000 3.000 3.000 3.000 3.000 3.000 2.000 3.000
item37 4.000 6.000 1.000 5.000 6.000 4.000 6.000 2.000 3.000
item38 2.000 4.000 4.000 4.000 4.000 7.000 2.000 6.000 7.000 7.000
item39 2.000 2.000 1.000 1.000 5.000 2.000 6.000 4.000 2.000 5.000
item40 5.000 3.000 2.000 5.000 3.000 4.000 2.000 5.000
item41 5.000 3.000 1.000 4.000 2.000 5.000 4.000 3.000 1.000
item42 2.000 2.000 2.000 2.000 2.000 2.000 2.000 2.000 2.000
item43 1.000 3.000 3.000 1.000 4.000 4.000 4.000 4.000
item44 1.000 1.000 1.000 1.000 1.000 1.000 1.000
item45 4.000 4.000 4.000 3.000 3.000 4.000 4.000 4.000 2.000 3.000
item46 2.000 2.000 2.000 2.000 2.000 2.000 2.000 2.000 2.000
item47 3.000 5.000 5.000 4.000 1.000 4.000 4.000 5.000 1.000 1.000
item48 6.000 3.000 6.000 2.000 6.000 3.000 4.000 1.000 1.000
item49 5.000 6.000 4.000 7.000 3.000 2.000 6.000 6.000 7.000
item50 3.000 3.000 3.000 3.000 2.000 1.000
This is a very easy MIP. It was solved completely during preprocessing, so it took zero branch-and-bound nodes (and about 0.1 seconds). Definitely much easier than the Traveling Salesman problem (TSP). In the comments, it was conjectured this model is about as a difficult as a TSP. That is obviously not the case. Caveat: with different data sets, things may become a bit more difficult.
The solution looks like:
---- 53 VARIABLE totalcost.L = 598.132 to be minimized
---- 53 VARIABLE use.L supplier is used
supplier1 1.000, supplier5 1.000, supplier6 1.000, supplier7 1.000, supplier8 1.000, supplier9 1.000
---- 53 VARIABLE buy.L orders to be placed at suppliers
supplier1 supplier5 supplier6 supplier7 supplier8 supplier9
item1 2.000
item2 1.000 1.000 4.000 3.000
item3 3.000 3.000
item4 1.000 1.000 2.000
item5 3.000
item6 3.000
item7 3.000 1.000
item8 3.000 6.000
item9 1.000
item10 5.000 1.000
item11 1.000 6.000 1.000 2.000
item12 5.000 1.000
item13 3.000 6.000 1.000
item14 6.000 2.000
item15 2.000
item16 7.000
item17 2.000
item18 3.000
item19 1.000 6.000
item20 5.000
item21 1.000 3.000
item22 3.000 1.000
item23 2.000
item24 2.000
item25 6.000
item26 4.000 5.000
item27 3.000
item28 5.000 2.000
item29 1.000 6.000 1.000
item30 4.000
item31 2.000
item32 1.000 2.000 3.000
item33 2.000
item34 2.000 4.000 3.000
item35 3.000
item36 3.000
item37 6.000
item38 2.000 6.000
item39 1.000 6.000
item40 3.000 2.000
item41 1.000 4.000
item42 2.000
item43 4.000
item44 1.000
item45 4.000
item46 2.000
item47 3.000 1.000 3.000
item48 3.000 2.000 1.000
item49 2.000 6.000
item50 3.000
From the 10 suppliers in the data, only 6 are selected.
For large problems with lots of sparsity in the data avail[i,s] we can improve the formulation a bit.
I also tried a run with 1000 items and 50 suppliers. That took about 30 seconds to solve to proven optimality. This model has 50k discrete variables, so it is not small. Some commenters said this problem is as hard as a TSP problem. I hope this experiment debunks the notion that this problem is as difficult as the TSP problem (the TSP problem is not easily stated as a MIP that performs somewhat decently). Secondly, it proves that a MIP model is a viable approach for this problem.
答案2
得分: 0
以下是翻译好的部分：
"cvxpy" is certainly 1 of the options to do the first part with. I'm partial to "pyomo", and "pulp" is also viable. "pulp" also installs with a solver (cbc) which is suitable for this type of problem. In other cases, you may need to install separately.
If you take this approach, look through a text or some online examples on how to formulate a MIP (mixed integer program). You'll have some sets (perhaps items, suppliers, etc.), data that form constraints or limits, some variables indexed by the sets, and an objective....likely to minimize cost.
Forget about the complexities of split-orders and combined shipping at first and just see if you can get something working with toy data, then build out from there.
英文:
Some advice too large for a comment:
As @Erwin Kalvelagen alludes to, this problem can be described as a math program, which is probably the most common-sense approach.
The generalized plan of attack is to figure out how to create an expression of the problem using some modeling package and then turn that problem over to a solver engine which uses diverse techniques to find the optimal answer.
cvxpy is certainly 1 of the options to do the first part with. I'm partial to pyomo, and pulp is also viable. pulp also installs with a solver (cbc) which is suitable for this type of problem. In other cases, you may need to install separately.
If you take this approach, look through a text or some online examples on how to formulate a MIP (mixed integer program). You'll have some sets (perhaps items, suppliers, etc.), data that form constraints or limits, some variables indexed by the sets, and an objective....likely to minimize cost.
Forget about the complexities of split-orders and combined shipping at first and just see if you can get something working with toy data, then build out from there.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论