2
$\begingroup$

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.

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .