# 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
Premium Mix:       30% peanuts, 30% cashews and 40% macadamias


This can be represented as a matrix:

Peanuts    0.6   0.4   0.3
Cashews    0.4   0.4   0.3
Macadamias  0    0.2   0.4


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?

Thanks in advance!! :)

-
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

## 1 Answer

Erm, depends on whether or not you consider your ingredients to be fractionally divisible.

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.

-
NP-complete it may be, but for a problem this small that's not really an issue. – Gerry Myerson Oct 4 '12 at 5:52
@shitikanth I guess the three ingredients would be fractionally divisible as they are measured in kilo's/grams etc... I am not very advanced in mathematics, and am still struggling to understand what numbers to sub-in where in the equation you have given. Would you be able to give me a practical example of how to use it? – Maddy Oct 4 '12 at 9:18
For your specific problem, you can take x,y,z be the quantities of the three mixes produced. You are given the maximum amount of peanuts, cashews, and macadamias you can use. This will give you three linear inequalities on x,y and z. Since the target function (the amount of wastage) is linear it will be minimized at a vertex of the feasible region. Find all the vertices of the feasible region and compute the amount of wastage in each and choose the minimum. – Shitikanth Oct 5 '12 at 23:42