Associated Topics || Dr. Math Home || Search Dr. Math

### Linear Programming

```Date: 10/15/2003 at 01:24:23
From: Sharleen
Subject: optimization

P and Q are ingredients with composition as shown below:

Ingredient   A (unit/g)  B (unit/g)  C (unit/g)
----------   ----------  ----------  ----------
P                2           1           5
Q                2           4           1

These ingredients are mixed with a filler ingredient weighing at least
85g to make batches with a total of 100g, pressed into one.  Each
batch contains at least 12 units of A, at least 12 units of B and at
least 10 units of C.  Unit costs are \$2.00/g for P and \$3.00/g for Q.

How many grams of each per batch will minimize the production cost?
```

```
Date: 10/15/2003 at 05:12:29
From: Doctor Luis
Subject: Re: optimization

Hi Sharleen,

First, some definitions.

Let the masses of ingredients P and Q be MP and MQ respectively.

Let MF be the mass of the filler ingredient, and let UA, UB, and UC be
the number of units of A, B, C present in a batch.

Finally, let CP and CQ be the unit costs of ingredients P and Q.

Then, we know from the problem that

MF >= 85g
MF + MP + MQ = 100g
UA = 2*MP + 2*MQ >= 12
UB = 1*MP + 4*MQ >= 12
UC = 5*MP + 1*MQ >= 12
CP = \$2.00/g
CQ = \$3.00/g

We can simplify the first two by combining them into

MF + MP + MQ >= 85 + MP + MQ
100 >= 85 + MP + MQ
or

MP + MQ <= 15

To get the net cost, we just multiply the unit (gram) cost of each
ingredient by the mass of each ingredient.

Unit cost C = CP*MP+CQ*MQ = 2MP + 3MQ

To maximize C(MP,MQ) we look at the region bounded by the four
inequalities

MP +  MQ <= 15
2MP + 2MQ >= 12
MP + 4MQ >= 12
5MP +  MQ >= 12

Graphically, it's the shaded region, R, in the following graph:

Since the slope of the cost function does not match the slope of any
of the edges above, then the cost function achieves its minimum at one
of the corners of the shaded region above.

You can visualize how the lines of equal cost sweep through the region
R if you look at the following animated gif:

Can you tell which vertex of R has the least cost associated with it?

Let us know if you have any more questions.

- Doctor Luis, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Linear Equations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search