费用分配问题

我有一个问题，我坚持，并且无法找到任何地方开始，所以我无望转向了计算器。费用分配问题

该问题希望我们找出它是np-hard还是多项式，如果它的np-hard证明了np-completeness，则给出算法。

问题如下：

产品存在n个模块。有两家公司可以构建每个模块，但有一些成本（c_ij，i：模块编号，j：公司编号）。如果模块a和b由不同的公司构建，他们也有额外的成本，（p_ab）。模块a和b不必是连续的，相同的额外成本也适用于a和c。如预期的那样，该问题希望我们能够为公司分配模块，从而使总成本最小化。

有什么想法？

来源

2010-11-22 fizboz

是否只有两家公司或两家每个模块？ – jpalecek 2010-12-06 13:33:10

只有两家公司。 – fizboz 2010-12-12 01:41:30

它可以减少到最小切割问题，这可以通过任何最大流量算法找到。那么网络是什么？模块将成为我们图的顶点，并且我们还添加了2个新顶点源和汇。从源码我们添加边缘到每个模块我与容量Ci1。同样，从每个模块我们我们添加边缘到容量Ci2。同样对于任何模块i和j，我们都添加边容量pij （图的方向因此会有两个边（i j）和（j i））。很容易看出最小切割的价值是问题的解决方案（部分切割模块将源分配给第二家公司，其余模块分配给第一家公司）

来源

2010-11-29 01:16:31 MikleB

费用分配问题

回答

相关问题