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 was given a Excel spreadsheet with this table:

enter image description here

The user wants to find the lowest price mix amongst the various suppliers. The user wants to constrain the number of products that each supplier gets using this table:

enter image description here

Is there a tool (Excel addin) or technique (algorithm) that would help me in trying to solve this problem?

Note: My original question was posted on Programmers.

share|improve this question

2 Answers 2

up vote 6 down vote accepted

In this case, what you have can be considered as a "network flow problem", and there is an Integrality Theorem that tells you that if the capacities and the required amounts of products are integers, the basic optimal solutions of the linear programming program will be in integers. So there's no need for integer programming here.

share|improve this answer

This is an instance of Integer Programming, which is NP-hard in general. In practice people solve such problems exactly or approximately using heuristics. In your case you can just enumerate over all possibilities.

If you allowed fractional solutions (i.e. you could pick $2.5$ units) then this becomes Linear Programming which you can solve using lots and lots of packages widely available.

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.