最小成本的线性规划问题
linear programming problem for minimum cost
一家建筑公司有 6 个项目，每个项目需要 $d_i$ 名工人。项目一开始公司没有工人
每个新工人必须参加安全课程，费用为 300，每个工人还需要 50。
如果没有新工人就没有课程。
解雇工人不花钱，也不能重新雇用工人。
假设工人的工资是每个项目 100，请制定一个线性规划问题，使工人成本最小化。
我尝试了什么：
设 $x_i$ 为项目 $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)$
s.t:
\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解决这个问题，失败了。
我做错了什么？我该如何解决这个问题？
当我正确地看到这个时，你的约束中有两个小错误。
当您使用 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-1} 的基础上增加 y_i 而无需设置任何 x_i。要强制 x_i 增加，您需要翻转不平等。此外，按照您定义 y_i 的方式，此不等式应指代 x_{i-1}。因此你应该以 y_i <= y_{i-1} + x_{i-1} 结束。此外，您需要处理极端情况（即 y_1 = 0）
我认为通过这两个更改应该可以。让我知道它是否对您有帮助。如果它仍然不起作用，我可能错过了一些东西。
一家建筑公司有 6 个项目，每个项目需要 $d_i$ 名工人。项目一开始公司没有工人
每个新工人必须参加安全课程，费用为 300，每个工人还需要 50。 如果没有新工人就没有课程。
解雇工人不花钱，也不能重新雇用工人。
假设工人的工资是每个项目 100，请制定一个线性规划问题，使工人成本最小化。
我尝试了什么：
设 $x_i$ 为项目 $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)$
s.t:
\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解决这个问题，失败了。
我做错了什么？我该如何解决这个问题？
当我正确地看到这个时，你的约束中有两个小错误。
当您使用 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-1} 的基础上增加 y_i 而无需设置任何 x_i。要强制 x_i 增加，您需要翻转不平等。此外，按照您定义 y_i 的方式，此不等式应指代 x_{i-1}。因此你应该以 y_i <= y_{i-1} + x_{i-1} 结束。此外，您需要处理极端情况（即 y_1 = 0）
我认为通过这两个更改应该可以。让我知道它是否对您有帮助。如果它仍然不起作用，我可能错过了一些东西。