我有 n 个使用旧系统完成的工作。如果我将它们更改为新系统，我将获得该工作的双重收益。一些工作对 (i,j) 具有依赖关系。改变工作但不改变其依赖对的成本 xij。作业 1 无法在新系统下运行。更改为新系统（当然不包括工作 1）以最大化收益的理想工作集是什么。
这是一个用我自己的话改写的算法问题。它应该减少到某种形式的最大流量或循环。由于成本取决于将其他作业更改为新系统（我似乎无法将静态值与最大流量图设置相关联并有一个可行的解决方案），因此我在提出一种方法时遇到了极大的麻烦。我已经考虑了一段时间，但仍在努力寻找一个体面的方法。任何有关如何考虑解决此问题的建议将不胜感激！