🔒 Locked

Integer Linear Programming

Started by bowsandhearts May 23, 2007 at 2:58 AM 4 replies 850+ views

Original Post

May 23, 2007 at 2:58 AM

Hi guys..this is an operations research question. I have been having problems formulating the objective function. Hopefully, I can get some help on it. I am required to formulate and solve an integer programming problem. The question is as follows: There are 5 helicopters available to transport a list of items from 1 place to another. Each helicopter can carry up to 200kg. Each helicopter has 4 seats. All items must be transported. The weights of items are listed in the list below: Item No Weight 1 20 2 16 3 6 4 6 5 101 6 10 7 8 8 95 9 111 10 120 The constraints are Item No.1 must be carried in the first helicopter. Items No. 9 and 10 are not allowed to be on the same helicopter. Items No.6 and 7 need to be on the same helicopter. I would think that the objective function is to minimize the number of helicopters used since a cost is associated with the hiring of each helicopter. Hence, the objective function will be something like minimise no of helicopters used. Just stuck on formulating the part after that. Hopefully someone can help. Thanks!

XXX_Andrew_XXX

May 23, 2007 at 6:05 AM

Smells like homework.

You might want to check out lpsolve which is free, or CPLEX which is supposed to be a really great product.

Wikipedia has some other good links.

bowsandhearts

May 23, 2007 at 6:26 AM

It is part of my final assignment formulation.

We are using Excel Solver to formulate it and solve it. I am not expecting ppl to formulate the entire problem for me. I just hope that perhaps someone can nudge me in the right direction regarding the objective function and decision variables and I can do the rest on my own. I can't really do anything without realising what the objective function or decision variables are...a few pointers will really be helpful.

Thanks for your reply though.

Raghar

May 23, 2007 at 7:54 AM

The answer is three helicopters.

It's just a bin packing problem.

bowsandhearts

May 23, 2007 at 8:00 AM

Yes, I know that the minimum amount of helicopters required is 3 as 3 helicopters can carry 3x200=600kg worth of stuff and our items/people only weigh 493kg in total.

This is why I don't know what the question is asking(what the objective function is). Even if I successfully assign each item/people to a helicopter within the 3 helicopters by logical reasoning, there will be numerous alternative optimal solutions.

Can anyone nudge me in the right direction?

Zipster

May 23, 2007 at 11:41 AM

I don't think you want to directly minimize the number of helipcopters using an IP formulation, but rather you would want to minimize the number of helicopters by maximizing the amount of weight you put on each helicopter, subject to your constraints. Then it essentially becomes a series of knapsack problems, where the number of helicopters is equal to the number of times you need to solve the problem before all items are transported.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.