计算科学 - 在目的地之间分配源 - 吾爱随笔录

在目的地之间分配源

计算科学优化算法

2021-11-27 23:22:23

有 $n$ 具有以下正量的来源： $p_1, ..., p_n$ 并且有 $m$ 具有以下正量的目的地： $q_1, ..., q_m$ . 众所周知 $p_1+ ...+ p_n=q_1+ ...+ q_m$ . 每个源都将使用其体积来填充一个或多个目的地。如果一个来源填满一个目的地，我们支付 $1$ 为了它。如果满了 $k$ 我们支付的目的地 $k$ 为了它。问题是使用来源填充目的地，以使价格尽可能低。

我需要帮助提出解决问题的算法。

坦率地说，我在这里很迷茫，无法想出至少比遍历所有可能的填充物并选择价格最低的算法更好的算法。

我思考的事情是按升序对源进行排序，然后逐个取源，但我无法证明这种方法的正确性。

1个回答

让您的决策变量为 $X \in \mathbb{R}^{n\times m}$ 和 $Z \in \{0,1\}^{n\times m}$ ，在哪里 $X_{ij}$ 是生产者生产的数量 $i$ 发送给消费者 $j$ . $Z_{ij}$ 是一个二进制变量，如果生产者为 1 $i$ 向消费者发送任何东西 $j$ , 否则为 0。

您的目标是最小化成本函数：

c (X, Z) = \sum_{i, j} Z_{i j}

$c(X,Z) = \sum_{i,\,j}Z_{ij}$ 受以下约束：

\begin{aligned} \sum_{i} X_{i j} & = q_{j} \forall j \in {1... m} (Demand satisfied) \\ \sum_{j} X_{i j} & \leq p_{i} \forall i \in {1... n} (Producer supply constraint) \\ X_{i j} & \geq 0 (Nonnegative production) \\ X_{i j} & \leq Z_{i j} p_{i} (Z_{i j} must equal 1 if X_{i j} \neq 0) \\ Z_{i j} & \in {0, 1} \end{aligned}

$\begin{align} \sum_i X_{ij} &= q_j \;\; \forall j\in\{1...m\} \;\; \text{(Demand satisfied)} \\ % \sum_j X_{ij} &\le p_i \;\; \forall i\in\{1...n\}\;\;\text{(Producer supply constraint)} \\ % X_{ij} &\ge 0 \;\;\text{(Nonnegative production)}\\ X_{ij} &\le Z_{ij}p_i \;\; \text{($Z_{ij}$ must equal 1 if $X_{ij} \neq 0$)}\\ Z_{ij} &\in \{0,1\} \end{align}$

通常，整数程序要求您使用分支定界算法。但是，由于这个问题中唯一的整数变量被限制为二进制变量，我相信你可以把 $Z_{ij}$ 作为连续并使用线性规划求解器解决问题。

如果您对用于求解线性程序的算法特别感兴趣，您应该搜索“Dantzig 单纯形算法”，这是解决中等到中等大小的线性程序的最常用方法。对于更大规模的问题，“内点”求解器往往比基于单纯形的求解器执行得更好。

其它你可能感兴趣的问题

上一篇非对称矩阵的共轭梯度下一篇对英特尔 MKL、线程和 MPI 的总体了解