An Example of Linear Programming

This is an example of how one can use Linear Programming to find the maxium profit.  There are 5 steps needed to complete this tesk.  They are :

1. Read and Understand the problem
2. Make a chart.
3. Write the inequalities
4. a) Graph the inequalities to find the solutions set.  
   b) Use the verticies of the solution set to find the maxium profit.
5. Explain and check your answer.

Step 1   Read and Understand the problem.

The Smith and Jones company makes a $60 profit on each console TV it produces and a $40 profit on each portable TV.  The console TV requires 1 hour of Machine A, 1 hour of Machine B and 4 hours of Machine C.  The productions of a portable TV requires 2 hours of A, 1 hour of B, and 1 hour of C.  In a given day , Machines A, B, and C can work a maximum of 16, 9, and 24 hours respectively.  How many console TV's and how many portable TV's should be produced per day to maximize the profit?

STEP 2  Make a chart
                                                         Total hours 
                   Console             Portable         available per wk
Machine A          1  hour         2 hours           16
Machine B          1  hour         1 hour              9
Machine C          4  hours        1 hour             24 
Profit per TV        $60               $40

Step 3  Write the inequalities.

Let x= number of console TV's    Let y= number of portable TV's
Looking at the chart we come up with the following equations
Find the inequalities described.
 1)  y…-1/2 x + 8   2) y…-x + 9   3) y…-4x+24   4) xæ0    5) yæ0

EXPLAINATIONS OF THE INEQUALITIES

1.  (Refer to Machine A), The console TV need machine A 1 hour (1x) and the portable needs Machine A 2 hours (2y), but machine A can only be used 16 hours THEREFORE 1x+2y…16  or y…-1/2 x + 8
2.   Both TV's need to use machine B  one hour each but the maximum time that machine B can run is 9 hours. THEREFORE x+y…9  or y…-x + 9 
3.   The console TV needs Machine C for 4 hours (4x) and the portable TV needs Machine C for 1 hour (y) THEREFORE  4x + y … 24     or y…-4x + 24  
4.  It is imposssible to make a negative number of console TV's THEREFORE  xæ0
5.  It is imposssible to make a  negative number of portable TV's THEREFORE  yæ0 
The profit expression is  60 x + 40 y because for every console TV maded a 60 dollar profit is maded (60 x)  and for every portable sold a 40 dollar profit is made. (40 y)

Step 4  Graph the inequalities, and find the maxium profit

Now let's graph the inequalities, find the verticies of the intersected region, evaluate those points in the profit expression to find the maxium profit available.
Because x æ 0 and y æ0 we will be graphing in the first quadrant. 
les=less than      gre=greater than
 1)  y<=-1/2 x + 8     ex1= -.5 x + 8     sign1=les      
 2) y<=-x + 9          ex2= -1 x + 9      sign2=les
 3) y<=-4x+24         ex3 = -4 x + 24    sign3=les

The following cell contains the expressions and information mathematica need to run this program.  Enter the next cell and the following empty cell to see the graph.  Later you can change this information to find solutions to a different problem.

ex1=-.5 x + 8 ;
ex2=-1 x + 9;
ex3=-4 x +24;
sign1=les; 
sign2=les;
sign3=les;
profit[x_,y_]=60 x + 40 y;

m1=Coefficient[ex1,x];
m2=Coefficient[ex2,x];
m3=Coefficient[ex3,x];
b1=Coefficient[ex1,x,0];
b2=Coefficient[ex2,x,0];
b3=Coefficient[ex3,x,0];

 
in1:=y<=m1 x +b1;
in2:=y<=m2 x +b2;  
in3:=y<=m3 x+ b3;
Clear[f1,f2,c1,c2,p1,eq1,eq2,x,y]
gre=1;
les=-1;
f3[x_]:=m3 x +b3;
f1[x_]:=m1 x+b1;
f2[x_]:=m2 x+b2

k1=If[sign1==gre,25,-25];
k2=If[sign2==gre,25,-25];
k3=If[sign2==gre,25,-25];
eq1:=y==f1[x];
eq2:=y==f2[x];
eq3:=y==f3[x];
c1:=ContourPlot[y - m1 x,{x,0,10},{y,0,10},
ContourShading->False,
Contours->120,PlotRange->{k1,b1},
DisplayFunction->Identity];

c2:=ContourPlot[y - m2 x,{x,0,10},{y,0,10},
ContourShading->False,
Contours->120,PlotRange->{k2,b2},
DisplayFunction->Identity];

c3:=ContourPlot[y - m3 x,{x,0,10},{y,0,10},
ContourShading->False,
Contours->80,PlotRange->{k3,b3},
DisplayFunction->Identity];


l1:=Plot[{f1[x],f2[x],f3[x]},{x,0,10},PlotRange->{0,10},
PlotStyle->{{RGBColor[1,0,0],Thickness[.009]},
{RGBColor[0,0,1],Thickness[.009]},
{RGBColor[1,0,1],Thickness[.009]}},
DisplayFunction->Identity];
Clear[x,y]
soln1 = Solve[{eq1,eq2},{x,y}];
x1=soln1[[1,1,2]];
y1=soln1[[1,2,2]];
soln2=Solve[{eq2,eq3},{x,y}];
x2=soln2[[1,1,2]];
y2=soln2[[1,2,2]];
Clear[x,y]
soln3=Solve[{eq1,eq3},{x,y}];
x3=soln3[[1,1,2]];
y3=soln3[[1,2,2]];
a1 = Solve[f1[x]==0,x][[1,1,2]];
a2 = Solve[f2[x]==0,x][[1,1,2]];
a3 = Solve[f3[x]==0,x][[1,1,2]];
g=If[a1<a2,a1,a2];
g1=If[g<a3,g,a3];
t=If[b1<b2,b1,b2];
t1=If[t<b3,t,b3];



lis={{x1,y1},{x2,y2},{x3,y3},{g1,0},{0,t1},{0,0}};
Clear[gd,i]
gd={ };


Do[If[(in1 && in2 && in3 && y>=0 && x>=0)/.
{x->lis[[i,1]],y->lis[[i,2]]},AppendTo[gd,lis[[i]]],gd=gd],
{i,1,Length[lis]}]
profit[x_,y_]=60 x + 40 y;

profitlist={};;
Do[AppendTo[profitlist,profit[gd[[i,1]],gd[[i,2]]]],
   {i,1,Length[gd]}]
maxvalue=Max[profitlist];
Show[c1,l1,c2,c3,
PlotRange->{0,10},
DisplayFunction->$DisplayFunction];
Print["Points    ",gd];
Print["Profit         ",profitlist];
Print["Maxium profit  ",maxvalue];

Step 5  Explain the solution
When all the inequalities are graphed the solutions set of answers will be located in the shaded area.  The polygon formed has verticies of (2,7),  (5,4),  (6,0),  (0,8)   and (0,0).   When the profit expression is evaluated at these point the profit is $400, $460, $360, $320, and $0 respectively.  The highest profit is at the point (5,4) this means the highest profit will be obtained when 5 console TV's and 4 portable TV's are produced.

Step 6 (optional)  Go back and change the variable to see what happens.  Have fun!!