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 had no idea how to tag this, any help would be great) :)

I am a programmer with little math experience beyond high school - this will be demonstrated by my explanation.

I am developing an application that needs a formula. The formula involves calculating what amounts of food to eat based on factors like calories and concentrations of macronutrients (carbs, protein, fats).

Since there are other calculations need that aren't relevant to main problem, I have abstracted it into the following word problem. Here it is:


Your job is to keep your store, Colorful Widgets, Inc., supplied with widgets. There are four suppliers that you can order from every month. There is a set ratio of colors that must be met as closely as possible to match sales expectations. The ratio is:

Target Color Ratios: 40% Red widgets 40% Blue widgets 20% Yellow widgets

The catch is that each supplier offers shipments of mixed colors in different ratios, with each company specializing in one color. Here are the ratios available from the suppliers:

Mostly Red Widgets, Inc. 86% Red 11% Blue 03% Yellow

Acme Widgets, Inc (Limit 3 boxes) 79% Red 09% Blue 20% Yellow

Mostly Blue Widgets, Inc. 15% Red 77% Blue 08% Yellow

Mostly Yellow Widgets, Inc. 10% Red 00% Blue 90% Yellow

All four companies sell their widgets in boxes containing 100 widgets each. Boxes cannot be split into smaller amounts. You need to order 24,000 widgets, with the total ratio of colors matching the targets laid out above.

Restrictions:

You have a contract with the first three companies - they must be ordered from every month, no exceptions. The fourth (Mostly Yellow Widgets, Inc.) is a stop gap - if your total ratio is low on yellow widgets, you can order from them.

Additionally, Acme Widget, Inc. makes the best widgets, but only in limited quantity. You must order 3 boxes from them each ordering cycle.


I understand that this problem probably will not have a neat and tidy catch-all formula. Even if there is no formula for this problem with it's restrictions, there should be a formula or something that will help with the problem of combining three different ratios in such a way to come as close as possible to the target ratio.

I also understand that if the target ratios or ratios of suppliers change too much, a solution may not be possible.

share|improve this question
    
I don't really understand the restrictions. Are you saying that you must order at least one box from each of the first three companies? What is meant by "best"? –  Qiaochu Yuan Jun 12 '11 at 18:09
    
The numbers for Acme don't add up to 100%. –  Robert Israel Jun 12 '11 at 18:53
    
@Qiaochu: This word problem was my poor attempt to abstract what is actually a food calculation. The "Acme Widget" actually represents green veggies in my real problem - something that cannot be skipped. :) –  Matt Miller Jun 13 '11 at 18:00
    
@Robert: That's what I get for making a last minute change to my question. –  Matt Miller Jun 13 '11 at 18:00

2 Answers 2

up vote 0 down vote accepted

For Acme widgets, you may order either $0$ or $1$ or $2$ or $3$ boxes; this integer will be called $M$. It's just four possibilities and all of them are small numbers of boxes and it is easy to manually check which of these four values will you the best results.

Most of the adjustment is done by and most of the boxes will come from the mostly red, mostly blue, and mostly yellow companies. You must order $R, B, Y$ boxes from each, respectively. The conditions, neglecting $M$ for a while, are $$ R + B + Y = 240,$$ $$0.86 R + 0.15 B + 0.10 Y = 96,$$ $$0.11 R + 0.77 B + 0 Y = 96,$$ $$0.03 R + 0.08 B + 0.90 = 48. $$ The four equations are not independent: the sum of the last three gives the first. So eliminate the first. We have a set of three linear equations for three unknowns $R,B,Y$. Define matrix $A$ as the $3\times 3$ matrix of the entries on the left hand side of the three equations. Then the solution is $$ (R,B,Y) = A^{-1} (96,96,48)^T \approx (87.36,112.20, 40.45) $$ That's the number of boxes you would ideally want to order if $M=0$: you would have to round it to $(87,112,41)$. Now, solve the same equations with the extra terms for $M=1,2,3$ and decide which of them is the best according to your best criteria (which, I guess, is either the sum of the deviation of the three percentages from $.4,.4,.2$ or the sum of the squares of these numbers). At any rate, the number of boxes $R,B,Y$ won't deviate by more than 3 from the numbers written above.

share|improve this answer
    
Thank you both to @Robert and @Luboš. I gave Luboš the answer, but both helped me to get what I needed. I took the info and studied matrices. I found a website that calculates matrices. I took the JS script and reverse engineered it for my app. Thanks! –  Matt Miller Jun 13 '11 at 18:05

It's basically a linear programming problem: if $x_1$, $x_2$, $x_3$, $x_4$ are the numbers of boxes ordered from the four companies, you would like

$$ \eqalign{ x_1 + x_2 + x_3 + x4 &= 240 \cr 86 x_1 + 79 x_2 + 15 x_3 + 10 x_4 &= 40 \times 240\cr 11 x_1 + 9 x_2 + 77 x_3 &= 40 \times 240\cr 3 x_1 + 20 x_2 + 8 x_3 + 90 x_4 &= 20 \times 240\cr x_2 \le 3,\ {\rm all}\ x_i \ge 0}$$

However, this may not be possible to attain precisely, so you allow some slack. One way is to minimize $r$ subject to

$$ \eqalign{ x_1 + x_2 + x_3 + x_4 &= 240 \cr 86 x_1 + 79 x_2 + 15 x_3 + 10 x_4 &\le 40 \times 240 + r \cr 86 x_1 + 79 x_2 + 15 x_3 + 10 x_4 &\ge 40 \times 240 - r \cr 11 x_1 + 9 x_2 + 77 x_3 &\le 40 \times 240 + r\cr 11 x_1 + 9 x_2 + 77 x_3 &\ge 40 \times 240 - r\cr 3 x_1 + 20 x_2 + 8 x_3 + 90 x_4 &\le 20 \times 240 + r\cr 3 x_1 + 20 x_2 + 8 x_3 + 90 x_4 &\ge 20 \times 240 - r\cr x_2 \le 3,\ {\rm all}\ x_i \ge 0}$$

Now usually the solution values will not be integers. If you want integer values, this becomes an integer linear programming problem. Many software packages will solve these.
In this case the optimal solution, as given by Maple's Optimization package, is $x_1 = 85$, $x_2 = 3$, $x_3 = 112$, $x_4 = 40$, $r = 27$.

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.