Linprog.html

LINEAR PROGRAMMING

Two Variables, The geometric method

Problems (slightly modified) from

Wheeler and Peeples

Modern Mathematics for Business Students

Problem. We have 960 oz of pecans and 1760 oz of peanuts. We wish to package these in small 1 lb packages with two different mixtures. Mixture 1 contains 6 oz of pecans and 10 oz of peanuts, while Mixture 2 contains 5 oz of pecans and 11 oz of peanuts. Mixture 1 sells for $3.50 while Mixture 2 sells for $1.80 Obviously with the resources available we are limited to a finite number of each mixture. (This is known as an allocation of resources problem.) How many of each mixture should we make to maximize the revenue?

Let x be the number of Mix1 and y the number of Mix2. The function g(x,y) = 3.50x + 1.80y gives the revenue obtained for the combination of mixtures (x, y). This function is called the OBJECTIVE FUNCTION.

The limited resources put constraints on which combinations (x, y) of mixtures is possible. The set of all mixtures which can be made is called the FEASIBLE SET. The feasible set is found in the geometric method by graphing the CONSTRAINTS and using this graph to construct the set of all combinations (x, y) which satisfy all of the constraints.

This problem has 4 constraints:

1. Imposed by the limited amount of pecans.

2. Imposed by the limited amount of peanuts.

3. and 4. Imposed by the fact that neither of x nor y may be negative.

The graphing is often done by hand, but Maple allows the graphing to be done by the use of the command inequal( { constraints }, range of x , range of y , options )

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

Warning, new definition for norm

Warning, new definition for trace

> Pecan_constraint:= 6*x + 5*y<=960;

> Peanut_constraint:=10*x + 11*y<=1760;

> Nonnegative_constraint_x:=x>=0;

> Nonnegative_constraint_y:=y>=0;

> Constraints:={Pecan_constraint,Peanut_constraint,Nonnegative_constraint_x, Nonnegative_constraint_y};

> inequal(Constraints,x=0..200,y=0..200,optionsfeasible=(color=cyan), optionsexcluded=(color=white),labels=[`x`,`y`],scaling=CONSTRAINED);

The part of the plane colored cyan represents the set of all combinations (x, y) which can actually be made, that is, it is the feasible set. The "corner points" of the feasible set are called the VERTICES. There are four vertices in this case (including (0,0) ).

> `OBJECTIVE FUNCTION`;g:= unapply(3.50*x+1.80*y,x,y);

> g1:=plot3d(g(x,y),x=0..170,y=0..170,style=wireframe,shading=ZHUE,gridstyle=rectangular,labels=[`#Mix1`,`#Mix2`,`Revenue`]):

> g2:=spacecurve({[0*(1-t)+0*t,160*(1-t)+160*t,0*(1-t)+g(0,160)*t],[0*(1-t)+110*t,160*(1-t)+60*t,0*(1-t)+0*t],[110*(1-t)+160*t,60*(1-t)+0*t,0*(1-t)+0*t],[160*(1-t)+0*t,0*(1-t)+0*t,0*(1-t)+0*t],[0*(1-t)+0*t,0*(1-t)+160*t,0*(1-t)+0*t],[110*(1-t)+110*t,60*(1-t)+60*t,0*(1-t)+g(110,60)*t],[160*(1-t)+160*t,0*(1-t)+0*t,0*(1-t)+g(160,0)*t],[0*(1-t)+0*t,0*(1-t)+160*t,0*(1-t)+g(0,160)*t],[0*(1-t)+160*t,0*(1-t)+0*t,0*(1-t)+g(160,0)*t],[160*(1-t)+110*t,0*(1-t)+60*t,g(160,0)*(1-t)+g(110,60)*t],[0*(1-t)+110*t,160*(1-t)+60*t,g(0,160)*(1-t)+g(110,60)*t]} ,t=0..1,shading=zhue,axes=normal,orientation=[-65,62],thickness=2):

> g3:=spacecurve({[0,160,0],[0,0,0],[160,0,0],[110,60,0]},t=0..1,color=red,style=point,symbol=box,color=COLOR(RGB,1,0,0)):

> display(g1,g2,g3);

The graph of g(x,y), which is linear, is a plane seen as a wireframe plane in this graph. The option scaling = ZHUE causes the color to run through the spectrum from magenta to red as points get higher above the x,y plane. The boundary of the feasible set can be seen as a magenta-colored quadrilateral in the x,y plane. Its vertices appear as red boxes.

It is fairly clear that since a plane cannot have a local maximum, that the max value of g(x,y) must occur on the magenta-colored boundary of the feasible set, and a little further reflection will convince you that the max has to occur at a vertex. It appears from this graph that the plane representing g(x,y) is at its highest for feasible points (x,y) at (160,0).

FUNDAMENTAL THEOREM OF LINEAR PROGRAMMING
If the objective function has a maximum value subject to the constraints, this maximum value is at a vertex of the feasible set.
If the objective function has a minimum value subject to the constraints, this minimum value is at a vertex of the feasible set.
If the feasible set is bounded, the objective function has a max and a min.

Obviously the possible vertices are the intersection points of four lines taken two at a time. There are 6 such intersections. One can see from the graph that two of them are not feasible. The following commands finds all six intersections and substitutes them into the constraints to eliminate any which are not feasible.

> eq[1]:=lhs(Pecan_constraint)=960;

> eq[2]:=lhs(Peanut_constraint)=1760;

> eq[3]:=x=0;

> eq[4]:=y=0;

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

>

> Vertices;V[1]:=[110,60];V[2]:=[160,0];V[3]:=[0,160];V[4]:=[0,0];

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

  Vertex      x      y        Objective function

            110     60          $ 493.00

            160      0          $ 560.00

              0    160          $ 288.00

              0      0          $  0.00

The answer to the problem is : Make 160 Mix1 and 0 Mix2 for a max revenue of $560.00.

> subs(x=160,y=0,Pecan_constraint);

> subs(x=160,y=0,Peanut_constraint);

Substituting (160, 0) into the Peanut_constraint shows that the amount of peanuts used was 1600 oz when 1760 oz were available. The 160 oz of peanuts left over is referred to as the SLACK in the peanuts. There was no slack in the pecans; all 960 oz were used.

Problem. GO FAR OIL CO needs 800, 1400 and 500 barrels respectively of low medium and high grade oil. Refinery I produces 200, 300 and 100 barrels per day respectively of low, medium and high grade while Refinery II produces 100, 200 and 100 barrels per day. Refinery I costs 250 dollars per day to operate while Refinery II costs 200 dollars per day. How many days should each refinery run to satisfy the demand at minimal cost?

Let x be the number of days to run Ref I and y the number of days to run Ref II. The objective function is

z = 250x + 200y.

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

Warning, new definition for norm

Warning, new definition for trace

> Low_Grade_constraint:= 200.*x + 100.*y>=800.;

> Med_Grade_constraint:=300.*x + 200.*y>=1400.;

> High_Grade_constraint:=100.*x+100.*y>=500.;

> Nonnegative_constraint_x:=x>=0;

> Nonnegative_constraint_y:=y>=0;

> Constraints:={Low_Grade_constraint,Med_Grade_constraint,High_Grade_constraint,Nonnegative_constraint_x, Nonnegative_constraint_y};

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

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

> graph1:=%:

> eq[1]:=rhs(Low_Grade_constraint)=800;

> eq[2]:=rhs(Med_Grade_constraint)=1400;

> eq[3]:=rhs(High_Grade_constraint)=500;

> 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]:=[2,4];V[2]:=[0,8];V[3]:=[4,1];V[4]:=[5,0];

> Objective_function;`unit: dollars`; f:= (x,y)->250.*x+200.*y;

> printf(" Vertex x y Objective function"); for i from 1 to 4 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

              2      4          $ 1300.00

              0      8          $ 1600.00

              4      1          $ 1200.00

              5      0          $ 1250.00

The cost is minimized ($1200.00) at x=4, y=1. Thus we should operate Ref I for 4 days and Ref II for 1 day to minimize cost.

Note that since the feasible set is not bounded, there might not be a max or min. The following graph, showing contours and the gradient, shows that there is indeed a min and thus we have it. There is no max, but no one wants to maximize cost anyway.

> graph2:=contourplot(f(x,y),x=0..9,y=0..9,contours=[500,1000,1500,2000,2500,3000,3500],color=blue):graph3:=plot([[2,4],[0,8],[4,1],[5,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..9,y=0..9,arrows=thin,color=blue):

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

Next is just a demonstration of how much more complicated nonlinear programming can be. Suppose the same constraints as in the Go FAR OIL problem, but an objective function h defined below that is not linear. Because such a function can have a local minimum, the minimum may not be at a vertex or even on the boundary.

> `Objective function`;h:=unapply(100*x^2+60*y^2-1000*x-360*y+3190,x,y);

> Constraints;

> graph2:=contourplot(h(x,y),x=0..9,y=0..9,contours=[200,500,1000,1500,2000,2500,3000,3500],color=blue):graph3:=plot([[2,4],[0,8],[4,1],[5,0]],style=point,symbol=circle,color=red):

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

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

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

You can see from the gradient and level curves that the min is in the interior of the feasible set.

> `We need to solve for x and y this system of equations to find where the local min occurs:`;Diff(h(x,y),x)=0;Diff(h(x,y),y)=0;

> solve({diff(h(x,y),x)=0,diff(h(x,y),y)=0},{x,y});

The function h would be a rather strange cost function, but if it were, we would need to run Ref I 5 days and RefII 3 days to min the cost.