Fox-Goat-Cabbage Transportation

问题:

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.

There was some interesting stuff here

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

Thanks,

回答1:

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 and

x_wolf,1 >= x_wolf,0

x_cabbage,1 >= x_cabbage,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 and

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

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

Finally, introduce the binary variable z_t and let

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

and maximize sum_t (z_t).

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

回答2:

You are right that this formulation will require integer variables. The traditional way of solving a problem like this would be to formulate a binary variable model and pass the formulation onto a solver. MATLAB in this case would not work unless you have access to the Optimization Toolbox.

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

In your formulation you would need to address the following:

Decision Variables

In your case this would look something like:

x_it (choose [yes=1 no=0] to transport item i during boat trip number t)

Objective Function

I'm not quite sure what this is from your description but there should be a cost, c_t, associated with each boat trip. If you want to minimize total time, each trip would have a constant cost of 1. So your objective should look something like:

minimize SUM((i,t),c_t*x_it) (so you are minimizing the total cost over all trips)

Constraints

This is the tricky part for your problem. The complicating constraint is the exclusivity that you identified. Remember, x_it is binary.

For each pair of items (i1,i2) that conflict with each other you have a constraint that looks like this

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

For example:

x_("cabbage" "1") + x_("goat" "1") <= 1

x_("wolf" "1") + x_("goat" "1") <= 1

x_("cabbage" "2") + x_("goat" "2") <= 1

x_("wolf" "2") + x_("goat" "2") <= 1

ect.

You see how this prevents conflict. A boat schedule that assigns "cabbage" and "goat" to the same trip will violate this binary exclusivity constraint since "1+1 > 1"

Tools like GAMS,AMPL and GLPK will allow you to express this group of constraints very concisely.

Hope that helps.