optimization - 福克斯山羊白菜运输

Question

我的问题是关于一个古老的运输问题-用一条船只能在一次运送一件物品的情况下在河上运送三件物品。一个约束是某些项目无法放在一起，例如带有山羊的白菜，带有山羊的狼等。应使用Integer编程或其他优化方法解决此问题。成本函数是所有项目都在河的另一边，到达那条河所需的行程可能是Simplex（？）的输出，它尝试了不同的可行解决方案。我想知道是否有人对这个问题有整数编程（或线性编程）的表述，和/或基于Matlab，Octave，Python的代码可以以编程方式提供解决方案，包括一连串的Simplex尝试了所有路径-我们的乘船之旅。

这里有一些有趣的东西

http://www.zib.de/Publications/Reports/SC-95-27.pdf

谢谢，

Answer 1

我建议使用二进制变量x_i，t来建模物品的位置，即，如果物品在行程t之后位于左岸，则它们为零，否则为1。这些变量最多只能在旅途中更改。可以通过以下方式建模

x_wolf，1 + x_cabbage，1 + x_goat，1 <= 1 + x_wolf，0 + x_cabbage，0 + x_goat，0和

x_wolf，1> = x_wolf，0

x_cabbage，1> = x_cabbage，0

x_goat，1> = x_goat，0

另一个方向的行程也需要类似的约束。

此外，在奇数行程之后，您需要约束以检查左岸的项目，类似地，您必须检查右岸。例如：

x_wolf，1 + x_goat，1> = 0并且

x_wolf，2 + x_goat，2 <= 1 ...

使用t的上限，这样肯定可以解决。

最后，介绍二进制变量z_t并让

z_t <= 1/3（x_wolf，t + x_cabbage，t + x_goat，t）

并最大化sum_t（z_t）。

（很可能sum_t（x_wolf，t + x_cabbage，t + x_goat，t）也会起作用。）