我的问题是关于一个老的运输问题——带着三件物品过河，一艘船一次只能转移一件物品。约束是指某些物品不能放在一起，例如卷心菜和山羊，狼和山羊等。这个问题应该可以使用整数规划或其他优化方法来解决。成本函数是所有物品都在河的另一边，到达那里所需的行程可能是尝试不同可行解决方案的单纯形函数(?)的输出。我想知道是否有人有这个问题的整数编程(或线性编程)公式，和/或Matlab, Octave，基于Python的代码，可以以编程方式提供解决方案，包括Simplex尝试所有路径的跟踪-我们的船。
这里有一些有趣的东西
http://www.zib.de/publications/reports/sc - 95 - 27. - pdf
谢谢,
我建议使用二进制变量x_i,t来模拟物品的位置，即如果物品位于行程t后的左岸，它们为零，否则为1。在旅行期间，这些变量中最多有一个可以改变。这可以通过
来建模狼，1 +白菜，1 +山羊，1 <= 1 +狼，0 +白菜，0 +山羊，0 and
x_wolf,1>= x_wolf,0
x_白菜，1>= x_白菜，0
大羊，1>=大羊，0
其它方向的行程也需要类似的约束。
此外，在奇数次旅行之后，您需要约束来检查左岸的项目，同样地，您必须检查右岸的项目。例如:
狼，1 +羊，1>= 0 and
狼，2 +山羊，2 <= 1…
使用t的上界，使得解肯定是可能的。
最后，引入二进制变量z_t，令
z_t & lt; = 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在你的提法中，你需要解决以下问题:
<标题>决策变量h1> 你的例子中，它看起来像:x_it (choose [yes=1 no=0] to transport item I at the boat trip number t)
<标题>目标函数我不太确定这是你的描述，但应该有一个成本，c_t，与每次乘船旅行有关。如果你想最小化总时间，每次旅行的成本将是1。所以你的目标应该是这样的:
最小化SUM((i,t)，c_t*x_it)(这样你就最小化了所有行程的总成本)
<标题> 约束这是你的问题的棘手部分。复杂的约束是您确定的排他性。记住，x_it是二进制的。
对于每一对相互冲突的项目(i1,i2)，你有一个如下所示的约束
x_(i1 t) + x_(i2 t) <= 1
例如:间("cabbage"1") + x_("1") <= 1
间("wolf"1") + x_("1") <= 1
间("cabbage"2") + x_("山羊"2") <= 1
间("wolf"2") + x_("山羊"2") <= 1
等。
您可以看到这是如何防止冲突的。分配"卷心菜"的船期表;和";goat"因为"1+1"违反了二元排他性约束。1"
像GAMS,AMPL和GLPK这样的工具将允许您非常简洁地表达这组约束。希望对你有帮助。