Question

Formulate the followings into optimization problems. While you could use the integer constraints, the linear structure should be maintained. However, you shouldn’t use the integer constraints if you can formulate the problem without them. Describe the decision variables, objective function and constraints carefully. You don’t need to solve this problem.

(b) (5 pts) A KAIST student is planning a back-pack trip to Europe for this summer. There are 11 items (1 through n) that she is considering to carry to the trip, where item i has a value vi, and a weight wi. While she wants to maximize the sum of values of the items that she carries to the trip, the maximum weight that she can carry is W. Now, she is trying to decide which items to carry. Formulate her problem into an optimization problem. The problem should maintain the linear structure

Answer 1

Number of items = n

Vi= Value of item i

Wi= Weight of item i

W=Total weight capacity

Decision variable

Xi= amount of carrying for item i

The objective is to maximize the value

Maximize Z=

i=1.....n

に!

Subject to constraint

Total weight of all items taken should not exceed the capacity W

i = 1....n

ー?

Xi>= 0 (Non negativity constraint)

Please comment if any doubt

Rate me

Thanks