The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
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

  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 

   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 
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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.