Formulate linear programming problem

I need help using either the linprog or intlinprog function. Suppose a person dies and you have to split what this person owns between his two sons in a fair way. The person owned 14 objects, each worth a certain amount, in total 183000$. How can I formulate this with LP to find the partition that minimizes the difference between the values of the two parts?

Or in other words, minimize the inheritance assigned to one of the brothers with the constraint that it should not be less than the sum of all objects divided by 2.

Answer 1

[John D'Errico]

Can you use linprog? If you split an item 60-40, would that be acceptable? If not, then linprog is not possible.

This is essentially a binary integer linear programming problem. Use intlinprog, with INTEGER variables (vector x) from the set [0,1].

So minimize the product f*x, such that f*x>=sum(f)/2.

To be honest, it is just as easy to use exhaustive enumeration here. All possible sets are given by

dec2bin(0:2^14-1) - '0'

Choose the row that satisfies your goal, which will require all of one matrix*vector multiply, followed by a quick test.

This seems too much probably homework though, so I'll go no further.

Answer 2

[Alan Weiss]

I think that you can formulate this as an integer problem. Let each object be either assigned a +1 to mean it goes to son A, or a 0 to mean it goes to son B. Set a linear inequality that the total value to son A is at least half the total value, and set an objective function to minimize the value that son A gets. At least, I think that this will solve the problem.

Alan Weiss

MATLAB mathematical toolbox documentation