1

我有一个线性模型，它试图以最佳方式在“单元”之间移动“单元”。每次转账费用为 2 美元，另加转账单位金额的 1%。

假设一个目标单元需要 100 个单元，并且可以从 10 个源单元中的任何一个接收它。我如何鼓励优化器从一个源单元格（总成本 2+1）单次转移 100 个单位，而不是从每个有效源单元格转移 10 个单位（总成本 20+1）？

如果重要的话，我已经在 matlab 中使用 mosek 实现了这一点。

（抱歉，如果问题有点模糊，这都是自学的，我不知道如何用正确的术语明确地提出这个问题。如果有的话，很高兴在更合适的 SE 上重新发布这个问题。）

4

2 回答 2

3

这是一个标准的整数规划，称为固定电荷传输问题。

假设有S供应商和D客户有需求。每个供应商i都有S_i单位，每个客户j都有需求D_j

您需要两种类型的决策变量。

  • Xij是从供应商 i 到客户 j 的金额。
  • 但是还有一个我们必须处理的固定成本。Fij = 2（每个运送单位的供应商 2 美元。）设固定成本变量为
    • Y_ij = 1如果供应商 i 向客户 j 发送非零数量的单位。
    • Y_ij = 0否则。

公式

Objective Minimize sum of all Subsets.
 Min sum (F_ij Yij) + sum Cij*Xij

Subject to:

    Sum over i Xij >= D_j for each customer j //Demand satisfaction
    Sum over j Xij <= S_i for each supplier i //Supply limitation

    // if you use a supplier for a customer, Yij has to become 1.
    Yij >= Xij for each i and each j 

Yij binary, Xij >=0

您将在任何标准 OR 教科书中找到有关固定电荷整数编程问题的更多信息。查找介绍整数编程的章节。

希望能帮助你前进。

于 2014-04-25T17:42:52.923 回答
1

关键是您要最小化或最大化的目标函数。如果只想减少传输次数，则必须最小化非零传输次数：假设您有一个变量 $x_{ij}$ 用于从 $i$ 到 $j$ 的传输，那么您应该最小化 $ \sum y_{ij}$ 其中 $y_{ij}$ 是一个二进制变量，当 $x_{ij}=0$ 时取值为 $0$，否则取值为 $1$。

我想您可以将整个模型表述为单元之间的最小成本流，可能带有额外的约束和非平凡的目标函数。

（顺便说一句，如果您需要帮助，您也可以在我们的谷歌论坛上的 mosek 联系我们......）

于 2014-04-24T17:14:46.713 回答