A, B, C and D are standing on the east bank of a river and wish to cross to the west side using a boat. The boat can hold at most two people at a time. A, being the most athletic, can row across the river in 1 minute. B, C and D would take 2, 5, and 10 minutes, respectively. If two people are in the boat, the slower person dictates the crossing time. The objective is for all four people to be on the other side of the river in the shortest time possible.

Formulate a mathematical programming model to find smallest time for moving all four people to the other side of the river?

I can find the solution.

A and B cross, 2

A returns, 1

C and D cross, 10

B returns, 2

A an B cross 2

Total = 17 min.

It is the lowest value I am getting. As there are 4 persons, I can find the total number of feasible ways. But if there are 100 persons, then we can not use this complete enumeration technique.

  • $\begingroup$ Why not dividing 100 persons into 25 groups of 4 ? $\endgroup$ – sirous Nov 16 '19 at 7:37
  • $\begingroup$ Okay!! that is a good point. But what will be the formulation if I consider it as a 0-1 linear integer programming problem. $\endgroup$ – Rwitam Jana Nov 16 '19 at 7:43
  • $\begingroup$ Could you write a 0-1 program for a group of four? if so then you have to adjoin or repeat it for 25 groups. $\endgroup$ – sirous Nov 16 '19 at 9:44
  • $\begingroup$ No! I could not write a 0-1 program for this problem. Forget about 100 people, just write a 0-1 integer program for this problem. $\endgroup$ – Rwitam Jana Nov 16 '19 at 12:57

You can solve this as a shortest path problem, as shown in my answer here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.