# How to 'minimise' matrices

I have a question relating to the following problem in my maths investigation:

A nut store orders nuts in bulk, and the mix ratios are as follows:

Budget Mix:        60% peanuts, 40% cashews
Entertainers MiX:  40% peanuts, 40% cashews and 20% macadamias


This can be represented as a matrix:

Peanuts    0.6   0.4   0.3
Cashews    0.4   0.4   0.3


One week, they are given an order of 1360kg of peanuts, 1260kg of cashews and 2000kg of macadamias. How many packs of each type of mix could be made if they aimed to use all of the nuts supplied? Or by minimising the number of nuts left over.

Using $X=A^{-1}B$,

To use all nuts, they would make 500 packs Budget, -1760 packs Entertainers and 5880 packs of Premium. This is impossible however, as you obviously cannot make -1760 packs.

How would I go about finding the least amount left over? Is there a technique or formula I could use? Or is trial and error the only option?

-
Please consider registering your account. This one you will be reliably able to comment on your own questions, and avoid the problem of the server "losing track" of you. – Willie Wong Oct 4 '12 at 13:47

Let us say we have $n$ ingredients and total quantity of the $i^{th}$ ingredient is $R_i$. Suppose also that we have $m$ different products, and the $j^{th}$ product requires the ingredients in the proportion $a_{ij}$.
We want to maximize the total amount of ingredients used: $O= \sum_{i,j} a_{ij}w_j$, subject to the constraints: $\sum_j a_{ij}w_j \le R_i, w_i\geq0.$ This is a linear program and there are efficient algorithms to solve linear programs.
However, in addition you require $w_i$ to be integral, the problem is famously NP-complete.