狐狸-山羊-卷心菜运输

Question

我的问题是关于一个古老的运输问题——用一艘只能运送一件物品的船运送三件物品过河。一个约束是某些物品不能放在一起，例如卷心菜和山羊，狼和山羊等。这个问题应该可以使用整数编程或其他优化方法来解决。成本函数是河对岸的所有物品，到达那里所需的行程可能是尝试不同可行解决方案的 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) 也应该起作用。）

Answer 2

你是对的，这个公式需要整数变量。解决此类问题的传统方法是制定二元变量模型并将该公式传递给求解器。在这种情况下，除非您有权访问 Optimization Toolbox，否则 MATLAB 将无法工作。

http://www.mathworks.com/products/optimization/index.html

在您的公式中，您需要解决以下问题：

决策变量

在您的情况下，这看起来像：

x_it （选择 [yes=1 no=0] 在乘船旅行期间运输物品 i t）

目标函数

我不是根据您的描述，我很确定这是什么，但每次乘船旅行都应该有成本 c_t。如果您想最小化总时间，则每次行程的成本恒定为 1。因此您的目标应该类似于：

最小化 SUM((i,t),c_t*x_it) （这样您就可以最小化所有行程的总成本)

约束

这是您的问题的棘手部分。复杂的限制是您所确定的排他性。请记住，x_it 是二进制的。

对于每对相互冲突的项目 (i1,i2)，您有一个如下所示的约束

x_(i1 t) + x_(i2 t) <= 1

例如：

x_("cabbage" "1") + x_("山羊" "1") <= 1

x_("狼" "1") + x_("山羊" "1") <= 1

x_(“卷心菜”“2”) + x_(“山羊”“2”) <= 1

x_(“狼”“2”) + x_(“山羊”“2”) <= 1

等。

您会看到这如何防止冲突。将“卷心菜”和“山羊”分配给同一行程的船期将违反此二元排他性约束，因为“1+1 > 1”

像 GAMS、AMPL 和 GLPK 这样的工具将允许您非常简洁地表达这组约束。

希望有帮助。