我的问题是关于一个古老的运输问题——用一艘船一次只能运送一件物品，带着三件物品过河。一个约束是某些项目不能放在一起，例如卷心菜和山羊，狼和山羊等。这个问题应该可以使用整数规划或其他优化方法来解决。成本函数是河对岸的所有项目，到达那里所需的行程可能是 Simplex (?) 的输出，它尝试了不同的可行解决方案。我想知道是否有人有这个问题的整数规划（或线性规划）公式，和/或基于 Matlab、Octave、Python 的代码可以以编程方式提供解决方案，包括尝试所有路径的 Simplex 的踪迹——我们的乘船游览.
这里有一些有趣的东西
http://www.zib.de/Publications/Reports/SC-95-27.pdf
谢谢，
我建议使用二进制变量 x_i,t 来模拟您的项目的位置，即如果项目在行程 t 之后位于左岸，则它们为零，否则为一。在旅途中，这些变量中最多有一个可以改变。这可以建模为
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) 也可以工作。）
你是对的，这个公式需要整数变量。解决此类问题的传统方法是制定二元变量模型并将该公式传递给求解器。在这种情况下，除非您有权访问优化工具箱，否则 MATLAB 将无法工作。
http://www.mathworks.com/products/optimization/index.html
在您的配方中，您需要解决以下问题：
在您的情况下，这看起来像：
x_it（选择 [yes=1 no=0] 在乘船次数 t 期间运输项目 i）
根据您的描述，我不太确定这是什么，但每次乘船旅行都应该有一个成本 c_t。如果您想最小化总时间，每次旅行的成本恒定为 1。所以您的目标应该类似于：
最小化 SUM((i,t),c_t*x_it) （这样您就可以最小化所有行程的总成本）
这是您的问题的棘手部分。复杂的约束是您确定的排他性。请记住，x_it 是二进制的。
对于每对相互冲突的项目（i1，i2），您有一个看起来像这样的约束
x_(i1 t) + x_(i2 t) <= 1
例如：
x_("卷心菜" "1") + x_("山羊" "1") <= 1
x_("狼" "1") + x_("山羊" "1") <= 1
x_("卷心菜" "2") + x_("山羊" "2") <= 1
x_("狼" "2") + x_("山羊" "2") <= 1
等等。
您会看到这如何防止冲突。将“cabbage”和“goat”分配给同一行程的船计划将违反此二元排他性约束，因为“1+1 > 1”
像 GAMS、AMPL 和 GLPK 这样的工具可以让你非常简洁地表达这组约束。
希望有帮助。