-2

帮助，有人可以帮助我吗？具有固定成本的最小成本流和饱和字符串的奖励。

考虑以下最小成本流问题的变体，其中除了网络 G = (V, A)，其值 bi 与节点 i ∈ V 相关联，因此 Pi∈V bi = 0 并且单位成本的成本 cij沿弧 (i, j) ∈ A 运输 我们也有：

• 在每个拱门中都与一个容量值相关联，该容量值指示沿拱门可传输的最大流量dij；• 此处发送严格正流的弧的数量不超过弧总数的 100p1%，并且对于这些弧中的每一个，您支付 K 的固定成本；• 饱和弧的数量（沿其发送与其容量相等的流量的弧）至少占弧总数的 100p2%（p2

为这个问题制定数学模型，用 AMPL 编写并定义特定实例的数据，解决它。如果您更改某些实例数据，还必须注意分析会发生什么。特别是，您可能会发现区间 [p1, p2] 尽可能小，以便解决问题。

4

1 回答 1

1

我不确定我是否清楚地理解了您的问题，我尝试为每个问题提供可能的解决方案：

  • 您应该有一个正变量，我们将其称为每个弧的 Xij，它定义了在节点 i 和 j 之间的弧上传递的电流。

  • 使用此变量和给定参数 Dij，您可以添加一个约束来表示容量边界：Xij<=Dij ForEach (i,j) 属于 A。

  • 关于其他约束，我建议您使用 sum{ i in N , j in N } used[i,j] * k 的最小化目标函数。其中 used[i,j] 是一个二进制变量，表示相应的流是否等于零。要将流与此二进制变量相关联，您应该添加一个额外的约束，如下所示：

x[i,j] <= d[i,j] * 使用[i,j]

  • 就饱和弧的数量而言，您可以解决最大流量问题，其中解决方案由增广流算法的连续迭代给出。

如果我不放心发布您的决策问题（目标函数和约束是什么），我不确定我是否会回答您的问题

于 2015-02-05T23:27:03.570 回答