计算科学 - 贪婪地解决 LP - 吾爱随笔录

我有以下 LP：

\begin{array}{ll} Minimize & \sum_{j = 1}^{n} x_{j} \\ Subject to & \sum_{j = 1}^{n} a_{i j} x_{j} \geq b_{i}, i \in {1, \dots, M} \\ 0 \leq x_{j} \leq 1, j \in {1, \dots, n} \end{array}

$\begin{array}{ll} \text{Minimize} & \sum_{j=1}^n x_j \\ \text{Subject to} & \sum_{j=1}^n a_{ij} x_j \geq b_i,~~~i\in\{1,\ldots,M\} \\ & 0 \leq x_j \leq 1,~~~j\in\{1,\ldots,n\} \end{array}$ 哪里都有

a_{i j} \geq 0, \forall i, j

$a_{ij} \geq 0, \forall i,j$ 和

b_{i} \geq 0, \forall i

$b_i \geq 0,\forall i$ ，而这些是已知的。

如果它存在，我正在为这个 LP寻找一个快速的直接解决方案。我们知道 $n$ 远小于 $M$ . 这似乎类似于分数多背包问题。我想知道是否存在我可以使用的贪婪解决方案。

任何帮助深表感谢。

谢谢