0

我遇到了特定问题。我必须安排 5 名员工工作超过 14 天。每个员工在 14 天中只能工作 9 天，并且每天必须安排 3 名员工。关键部分是每个员工在某一天工作都会受到惩罚。因此，如果他们在那天不能工作，如果他们可以工作并且不介意，则罚款 10，最后如果他们可以但不想罚款，则罚款 5。

我有每个员工每天的罚款值矩阵。我正在尝试找到一种方法来写出我的约束。

我想到了矩阵 A（惩罚矩阵）和矩阵 B（调度矩阵）和矩阵 C，其中 C（i，j）= A（i，j）*B（i，j）。鉴于此设置，如果 A(i,j) 等于 0（员工不工作），则不考虑处罚，反之亦然。

那么我可以说作为我的约束：

A(1,1) + A(1,m) + A(1,n) <= 9

和

A(1,1) + A(m,1) + A(n,1) = 3

我正在最小化：C(1,1) + C(m,m) + C(n,n)

我这样看待它的问题是试图在优化算法中使用它。单纯形算法应该能够解决任何 LP 问题，但它可能是最慢的。我被卡住了，现在我确定我看错了。如果有人能给我一个全新的视角，并可能解释我为什么以错误的方式看待这个问题，我将不胜感激。

4

1 回答 1

0

我认为您犯了一个建模错误，使您的问题变得比需要的更困难。

为什么要使用惩罚函数对“有能力和愿意”、“有能力但不愿意”和“不能”进行建模？您不只是想尽量减少员工被分配一个员工有能力但不愿意工作的时间段的次数吗？（当然，没有分配任何他们无法工作的员工位置？）

如果您像我上面提出的那样修改问题，则可以将其建模为直接的最小成本流问题。您有一组用于员工的节点和一组用于时隙的节点。如果员工能够在该时间段工作，则将员工连接到容量边缘为 1 的时间段。如果员工当时愿意工作，给它成本 0，如果员工不愿意工作，给它成本 1。添加源和接收器；源应该对每个容量为 9（他们可以工作的天数）和零成本的员工有一个优势，而每个时间段应该对容量为 3 和零成本的接收器有一个优势。

从头开始编写最小成本流求解器相对简单。

如果您想禁止时隙由两个或更多不愿意的员工配备，我认为您将问题建模为整数程序。 GLPK是一个免费的线性和整数程序求解器。它不是最先进的，但它确实可以很好地解决很多问题。我怀疑它在解决像你这样的小规模实例时会遇到麻烦。

于 2013-02-19T18:58:22.593 回答