LINEAR PROGRAMMING

Two Variables, The geometric method, Maximum Problem

Bubba's House of Cheese is having a promotion in which they will price their Special Package at $15 and their Regular Package at $10. The diagram shows how much Cheddar, Swiss and Brie goes into each package and how much cheddar, swiss and brie they have. They wish to make the combination of Special and Regular Packages that will maximixe their revenue. How many of each package should they make?

> restart:with(linalg):with(plots):

Warning, new definition for norm

Warning, new definition for trace

First, set up the constraints.

> Cheddar_constraint:= 30.*x + 12.*y<=6000.;

> Swiss_constraint:=10.*x + 8.*y<=2600.;

> Brie_constraint:=4.*x+8.*y<=2000.;

> Nonnegative_constraint_x:=x>=0;

> Nonnegative_constraint_y:=y>=0;

> Constraints:={Cheddar_constraint,Swiss_constraint,Brie_constraint,Nonnegative_constraint_x, Nonnegative_constraint_y};

This command will compute the feasible set. Note there are five constraints and so the feasible set is a pentagon.

> inequal(Constraints,x=0..300,y=0..300,optionsfeasible=(color=COLOR(RGB,.8,1,.8)), optionsexcluded=(color=white),labels=[`x`,`y`],scaling=CONSTRAINED);

One can see from the graph that there are 5 vertices. The intersections two at a time of the five lines (including x=0 and y=0) results in 10 points, but 5 of them are outside the feasible set. The following computes the 10 intersections and determines which 5 are feasible.

> graph1:=%:

> eq[1]:=lhs(Cheddar_constraint)=6000;

> eq[2]:=lhs(Swiss_constraint)=2600;

> eq[3]:=lhs(Brie_constraint)=2000;

> eq[4]:=x=0;

> eq[5]:=y=0;

> for i from 1 to 5 do for j from i+1 to 5 do print(solve({eq[i],eq[j]},{x,y})); print(subs(solve({eq[i],eq[j]},{x,y}),Constraints)); od; od;

>

> Vertices;V[1]:=[140,150];V[2]:=[200,0];V[3]:=[100,200];V[4]:=[0,250];V[5]:=[0,0];

> Objective_function;`Revenue in dollars`; f:= (x,y)->15*x+10*y;

> printf(" Vertex x y Objective function"); for i from 1 to 5 do printf(" %6.0f %6.0f $ %5.2f", V[i][1], V[i][2], f(V[i][1],V[i][2])); print(); od;

  Vertex      x      y        Objective function

            140    150          $ 3600.00

            200      0          $ 3000.00

            100    200          $ 3500.00

              0    250          $ 2500.00

              0      0          $  0.00

The revenue is maximized ($3600) at x=140, y=150. Thus we should make 140 Special Packages and 150 Normal Packages to max the revenue.

Note that since the feasible set is bounded, there must be a max and it must be at one of the 5 vertices, and so unquestionably we have solved the problem. The following graph, showing contours and the gradient, confirms that. Note that two of the vertices are so near the same level that for practical purposes it would not matter which vertex we used or any point on the segment joining them..

> graph2:=contourplot(f(x,y),x=0..300,y=0..300,color=blue):graph3:=plot([[140,150],[200,0],[100,200],[0,250],[0,0]],style=point,symbol=circle,color=red):

> grad(f(x,y),vector([x,y]));

> graph4:=fieldplot(grad(f(x,y),vector([x,y])),x=0..300,y=0..300,arrows=thin,color=blue):

> display(graph1,graph2,graph4,graph3);

The slack (left over) in each type cheese can be computed this way.

> Slack_cheddar=rhs(eq[1])-subs(x=140, y=150,lhs(eq[1]));

> Slack_swiss=rhs(eq[2])-subs(x=140, y=150,lhs(eq[2]));

> Slack_brie=rhs(eq[3])-subs(x=140, y=150,lhs(eq[3]));

>