Mathematics 263                                  Laboratory 3                             September 15–22, 1993
	  
Name: _____________________________   Lab Partner: ___________________________
	  
Consulted with:  ____________________________________________________________

Geometric Linear Programming

This is a two week lab. You should complete at least Parts 1, 2,  and 3 before next week's lab, so you can work on Part 4 after that.

Part 1:  Introduction: A Two Variable Problem

Consider the following problem:

Farmer Brown is planning his planting for the coming year.  He expects to raise two crops, potatoes and wheat.  He has 100 acres of land available for planting and will be able to devote at most 160 days of labor to his crops.  He expects an acre of wheat to require 4 days of labor while an acre of potatoes requires only 1 day.  He has $1,100 that he can use for the startup costs of planting and cultivating.  It costs $10 an acre to plant and cultivate potatoes, while the corresponding costs for an acre of wheat are $20/acre.

If the farmer expects a revenue of $40 per acre of potatoes and $120 per acre of wheat, how many acres of each should he plant to achieve the maximum possible revenue?

To solve this problem, let x represent the number of acres planted with potatoes and y the number of acres planted with wheat.  The restrictions on the values of x and y are called constraints.  Clearly x and y must be nonnegative.  There are three other constraints given in the statement above; express each of them in terms of x and y below.  Hint:  Next to "The land constraint" you want to express the fact that Farmer Brown can plant up to 100 acres of land.

The land constraint:

The labor constraint:

The capital constraint:

The goal (or objective) in this problem is to maximize the farmer's revenue within the limitations expressed above.  Express the revenue in terms of x and y.  This quantity is called the objective function.

The objective function:
(to be maximized)

This mathematical formulation of the original problem is called a linear programming problem.  The standard form for a linear programming problem is (on the next page):

max (or min) objective function
subject to       constraint1
                       constraint2
                                             .
                                             .
                                             .
                       constraintn
                       nonnegativity constraints

Write Farmer Brown's problem in this form, below.

Part 2: The 2 Variable Problem, Geometrically

The set of points in the xy-plane whose coordinates satisfy all the constraints is called the feasible region.  We will draw a picture of the feasible region.  Each constraint gives a boundary to the feasible region; to find it, change the constraint to an equation (with an = sign), and solve for y.

Land boundary:  y =

Labor boundary:  y =

Capital boundary:  y =

Input your boundaries into Mathematica by completing the commands below:

landy =

labory =

capitaly =

Once you have input your definitions, the command below will plot these boundaries

region = Plot[{landy, labory, capitaly}, {x,0,100},
              PlotRange->{0,100},
              PlotStyle->{Red, Green, Blue}]

Print a copy of this plot and shade the feasible region on your printout. What we must decide now is which of the points in the region will maximize the objective function (the farmer's revenue).  Suppose the farmer could achieve a revenue of $600.  Express this as objective function = 600 and solve for y.  Write your answer below:

Revenue = $600: y =

Input your answer into Mathematica:

y600 =

We can use this definition to plot all the points where the objective function has the value 600 using the following command:

line600 = Plot[y600,{x, 0, 100}]

To see if the line has any points in common with the feasible region, we can look at them on the same plot using the command below:

Show[region, line600]

The fact that line600 does intersect the feasible region means Farmer Brown can generate a revenue of $600.  There are infinitely many feasible choices of x and y that will yield $600.  List three such (x, y) pairs below:

We have no reason to believe that the maximum revenue is $600.  Suppose we wish to generate $R in revenue.  Set the objective function equal to R and solve for y.

Revenue = $R :  y =

Replace R with 600t, so for t = 1, 2, …, 10 we will have R values 600, 1200, …, 6000.

Revenue = $600t :  y =

Use this to define y in Mathematica:

y[t_] =

We can plot some representative revenue lines:

revenues = Table[Plot[y[t],{x, 0, 100}], {t, 1, 10}]

To these these lines with the feasible region, use the following command:

Table[Show[region,revenues[[n]] ], {n, 1, 10}]

We can use Mathematica to create an animation of these plots.  Select the entire group of plots (click on the long blue bracket at the right of the screen), and click on the picture of a filmstrip at the top of the screen.

What you see is the feasible region with the revenue line for various values of R.  The first has R = 600 and the last has R = 6000.  What is the maximum revenue Farmer Brown can generate and how many acres of potatoes and wheat should he plant?  Write your answer here.

Part 3:  A Three Variable Problem

Now suppose Farmer Brown can plant a third crop:  soybeans.  For the time being ignore all constraints except the nonnegativity constraints and the land constraint.  Let z represent the number of acres planted with soybeans, and assume that soybeans generate $90 per acre of revenue.  Write this new linear programming problem in standard form below.

This problem is easy to solve "by inspection."  (That is, look at it carefully.)  How many acres of potatoes, wheat, and soybeans should he plant?  What will the maximum revenue be?

Use Mathematica to solve this problem geometrically.  First, find the boundary given by the land constraint, and solve for z.

Land:  z =

Enter your boundary into Mathematica:

landz =

The following command prepares Mathematica to show the plots that follow in a way that makes them easy to use.  Don't worry too much about what it means, but enter it before going any further.

SetOptions[{Plot3D, Graphics3D}, AxesLabel->{"x","y",
    "z"},BoxRatios->Automatic, SphericalRegion->True,
    ViewPoint->{-1,-1,0},PlotRange->{{0,100},{0,100},
    {0,100}}];

The command below will plot the boundary given by the land constraint:

region = Plot3D[landz, {x,0,100},{y,0,100},
                ColorFunction->(Red&)]

Set the objective function equal to R and solve the resulting equation for z.

Revenue = $R :  z =

Replace R with 2000t:

Revenue = $2000t :  z =

Input this definition into Mathematica by completing the command below.

z[t_] =

Then the next command will plot the planes corresponding to various levels of revenue:

revenues = Table[Plot3D[z[t],{x, 0, 100},{y, 0, 100},
               ColorFunction->(Gren&)], {t,2,6}

Now use the following command to generate five plots of the feasible region and a revenue plane on the same set of axes:

Table[Show[region, revenues[[n]] ], {n,1,5}]

Again we can animate these plots.  According to your animation, what is the maximum revenue Farmer Brown can have, and under what conditions will it occur?  Explain any discrepancy with your original answer.

Part 4:  A Manufacturing Problem

Use geometric programming to solve the following problem:

A manufacturing firm has discontinued production of a certain unprofitable product line.  this has resulted in considerable excess production capacity.  Management is considering devoting this excess capacity to one or more of three products; call them products 1, 2, and 3.  The available capacity on the machines that might limit output is sumarized in the table:

Machine type        Available Time (Machine hours/week)
Milling Machine         500
Lathe                          350
Grinder                       150

The number of machine hours required per unit for each product is given below

Machine type        Product 1        Product 2          Product3 
Milling Machine         3                      5                        9
Lathe                          4                      0                        5
Grinder                       0                      2                        3

The sales department indicates that the sales potential for all three products exceeds the maximum production rate.  The unit profit would be $20, $15, $30, respectively on products 1, 2, and 3.  The objective is to find the weekly production level that will maximize the firms total profit.

Write a brief report solving this problem and explaining your solution technique.