0

一家建筑公司有 6 个项目，每个项目都需要$d_i$工人。公司在项目一开始时没有工人。

每个新工人必须参加安全课程，费用为 300 美元，每位工人还要多 50 美元。如果没有新工人，就没有课程。

解雇工人不花钱，而且工人不能被重新雇用。

假设工人的工资是每个项目 100，请制定一个线性规划问题，以最小化工人成本。

我尝试了什么：

设$x_i$为 project 的新工人数$i$。

让我们$y_i$从以前的项目中剩余的老工人数量直到项目$i$（所有雇用的工人 - 所有被解雇的工人）

让$z_i$成为一个指标，使得$z_i =0 \iff x_i>0$

我要解决的功能是：

$\min(\sum_{i=1}^6 150x_i + 300(1-z_i) + 100y_i)$

英石：

\begin{align}
x_i,y_i,z_i &\ge 0 \\
z_i &\ge 1-x_i \\
y_i + x_i &\ge d_i \\
y_i &\ge y_{i-1} + x_i
\end{align}

我觉得有些不对劲。主要原因是我尝试使用matlab解决这个问题，但失败了。

我做错了什么？我该如何解决这个问题？

4

1 回答 1

1

当我正确地看到这一点时，您的约束中有两个小错误。

第一个出现在您使用z_i >= 1-x_i. 这允许z_i始终取值 1，这永远不会给您 300 的额外成本。您需要设置上限，以z_i使 z_i 在您拥有时不会为 1 x_i>0。对于这个约束，你需要一个叫做big M的东西。对于足够大M，您将使用z_i <= 1-x_i/M. 这样当x_i=0你可以有时z_i=1，右手边小于 1 并且由于完整性z_i必须为零。请注意，您通常希望选择M尽可能紧的。所以在你的情况下d_i可能是一个不错的选择。

第二个小错误在于y_i >= y_{i-1} + x_i。这样您就可以增加y_i超过y_{i-1}而无需设置任何x_i. 要强制x_i增加，您需要翻转不平等。此外，按照您定义y_i此不等式的方式，应参考x_{i-1}. 因此，您应该以y_i <= y_{i-1} + x_{i-1}. 此外，您需要处理极端情况（即y_1 = 0）

我认为通过这两个更改它应该可以工作。让我知道它是否对你有帮助。如果它仍然不起作用，我可能会错过一些东西。

于 2020-11-02T09:25:05.437 回答