Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a simple program that helps with purchasing decisions. The problem being solved is how to most profitably select products for a grocery shelf using competing products in different varieties. I'm looking for some pointers on ways to help me solve the following problem:

My program generates sets of data with three values: {price, value, type}. Each data point contains the absolute price for a resource, its expected value, and a classification. Given a maximum budget, say $1,000, I'd like to maximize my expected value. The tricky part is dealing with the constraints. I want to choose a combination of exactly 10 data points spread out among at least three classifications (diversification), but these 10 selections cannot exceed my budget.

Right now I do the obvious thing and pick the best 10 values and begin trading down until I satisfy my constraints (given the size of the data set, this is pretty fast). What are some mathematical principles I should apply to this problem? I'm not looking for an algorithm so much as some equations that would allow me to represent the problem visually on a graph.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

The usual approach for problems like this is the simplex algorithm. There is a lot of information on the web and whole books about it. For a problem this simple, if you buy all of one type, you make $(\text{value-price})\lfloor \frac {1000}{\text{price}} \rfloor$ and unless they are close you can pick the best, then look if any of the others are cheap enough to buy with the money you have left. If they are close in this criterion, you might do a bit better buying one less of the best item so you can buy more of the next best.

share|improve this answer

Ross Millikan is referring to linear programming to which Dantzig's simplex algorithm is the most commonly used algorithm to reach the optimal solution.

Linear programming requires an objective function to maximize and a set of linear constraints. If your constraints can be formulated as linear inequalities then you can use linear programming. The simplex method only applies to linear programming. If you have nonlinear constraints then you need to use a nonlinear programming algorithm. See this book by Mangasarian or this one.

The constraint that the sum of the 10 prices for the selected resources is less than or equal to the budget value is a linear constraint. But how do you represent the constraint that the selected 10 come from at least 3 of the the classification groups and are there any other constraints.

If all the constraints are linear the set of "feasible" solutions (solutions that satisfy all the constraints) form a simplex with the optimal solution being one of the vertices on the boundary of the simplex. The simplex method got its name because it searches through the vertices in an efficient manner to find the optimum. In this case the geometric figure that is the simplex containing all feasible solutions is a visual way of exhibiting the problem by show the set of points in space that satisfy the constraints. If the problem involves nonlinear constraints this region of feasible solutions will no longer be a simplex.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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