福克斯山羊白菜运输 [英] Fox-Goat-Cabbage Transportation

问题描述

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

My question is about an old transportation problem -- carrying three items across a river with a boat only capable of tranferring one item at a time. A constraint is certain items cannot be left together, such as the cabbage with the goat, wolf with the goat etc. This problem should be solveable using Integer programming, or another optimization approach. The cost function is all items being on the other side of the river, and the trips required to get there could be the output from Simplex (?) that tries out different feasible solutions. I was wondering if anyone has the Integer Programming (or Linear Programming) formulation of this problem, and / or Matlab, Octave, Python based code that can offer the solution programmatically, including a trace of Simplex trying out all paths -- our boat rides.

这里有一些有趣的东西

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

谢谢

推荐答案

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

I recommend using binary variables x_i,t to model the positions of your items, i.e. they are zero if the item is located on the left shore after trip t and one otherwise. At most one of these variables can change during a trip. This can be modeled by

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

x_wolf,1 + x_cabbage,1 + x_goat,1 <= 1 + x_wolf,0 + x_cabbage,0 + x_goat,0 and

x_wolf，1> = x_wolf，0

x_wolf,1 >= x_wolf,0

x_cabbage，1> = x_cabbage，0

x_cabbage,1 >= x_cabbage,0

x_goat，1> = x_goat，0

x_goat,1 >= x_goat,0

另一个方向的行程也需要类似的约束条件.

Similar constraints are required for trips in the other direction.

此外，在奇数次旅行之后，您需要约束以检查左侧海岸上的物品，并且类似地，您还必须检查右侧海岸.例如:

Furthermore, after an odd number of trips you nedd constraints to check the items on the left shore, and similarily you have to check the right shore. For instance:

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

x_wolf,1 + x_goat,1 >= 0 and

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

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

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

Use an upper bound for t, such that a solution is surely possible.

最后，引入二进制变量z_t并让

Finally, introduce the binary variable z_t and let

z_t< = 1/3(x_wolf，t + x_cabbage，t + x_goat，t)

z_t <= 1/3 (x_wolf,t + x_cabbage,t + x_goat,t)

并最大化sum_t(z_t).

and maximize sum_t (z_t).

(很有可能sum_t(x_wolf，t + x_cabbage，t + x_goat，t)也会起作用.)

(Most probably sum_t (x_wolf,t + x_cabbage,t + x_goat,t) shold work too.)

这篇关于福克斯山羊白菜运输的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！