THE CARPENTER PROBLEM

(toy problem introducing linear programming)

Variables:

T = tables produced

B = bookcases produced

P = profit = 25T + 30B

Constraints:

T >= 4 (contract)

B >= 2 (contract)

5T + 4B <= 40 (hours)

20T + 30B <= 200 (lumber)

Mathematical problem to be solved:

Determine T and B that maximizes P, subject to the given constraints

Approach 1: Graphical solution

>

restart:

>	with(plots):

Warning, the name changecoords has been redefined

Sketch the feasible region ...

>	implicitplot( {T=4,B=2,5*T+4*B=40,20*T+30*B=200}, T=0..12, B=0..10, color=red );

Sketch the level curves for the profit function ...

>	contourplot( 25*T+30*B, T=0..12, B=0..10, colour=blue, contours=20 );

Zoom in on the feasible region and show the two plots together ...

>	graph1 := implicitplot( {T=4,B=2,5*T+4*B=40,20*T+30*B=200}, T=3..8, B=1..6, color=red, thickness=2 ):

>	graph2 := contourplot( 25*T+30*B, T=3..8, B=1..6, colour=blue, contours=20 ):

>	display( graph1, graph2 );

We see that profit is maximized at the vertex given by the intersection of the two slanted contraint functions.  Let's solve for its coordinates ...

>	solve( {5*T+4*B=40,20*T+30*B=200}, {T,B} );

CONCLUSION: The carpenter should produce 40/7 tables and 20/7 bookcases per week to optimize profit.  In practical terms, this means making 40 tables and 20 bookcases in any 7-week period.

Approach 2: Algebraic solution using slack variables to find all feasible extreme points.

Define all the constraint equations ...

>

restart:

>	eqn1 := 20*T + 30*B + y1 = 200:

>	eqn2 := 5*T + 4*B + y2 = 40:

>	eqn3 := T - y3 = 4:

>	eqn4 := B - y4 = 2:

Find all possible intersections ...

>	sol1 := solve( {eqn1,eqn2,eqn3,eqn4,y1=0,y2=0}, {T,B,y1,y2,y3,y4} );

>	sol2 := solve( {eqn1,eqn2,eqn3,eqn4,y1=0,y3=0}, {T,B,y1,y2,y3,y4} );

>	sol3 := solve( {eqn1,eqn2,eqn3,eqn4,y1=0,y4=0}, {T,B,y1,y2,y3,y4} );

>	sol4 := solve( {eqn1,eqn2,eqn3,eqn4,y2=0,y3=0}, {T,B,y1,y2,y3,y4} );

>	sol5 := solve( {eqn1,eqn2,eqn3,eqn4,y2=0,y4=0}, {T,B,y1,y2,y3,y4} );

>	sol6 := solve( {eqn1,eqn2,eqn3,eqn4,y3=0,y4=0}, {T,B,y1,y2,y3,y4} );

sol3 and sol4 have negative values for the slack variables, so they are not feasible intersections.

We accept sol1, sol2, sol5, and sol6 as the only four feasible intersections.

Evaluate the profit function at these extreme points ...

>	Profit := 25*T + 30*B:

>	evalf( subs( sol1, Profit ) );

>	evalf( subs( sol2, Profit ) );

>	evalf( subs( sol5, Profit ) );

>	evalf( subs( sol6, Profit ) );

Profit is maximized with sol1.  That is, the carpenter should produce 40/7 tables and 20/7 bookcases per week, as before.

Approach 3: Simplex method.

We're solving the transformed problem, which reads as follows:

Maximize P(t,b) = 25t + 30b + 160,

subject to the two constraints 20t + 30b + y1 = 60 and 5t + 4b + y2 = 12,

and t, b, y1, y2 >= 0.

>

restart:

>	with( linalg ):

Warning, the protected names norm and trace have been redefined and unprotected

We start with the tableau for corner 1, characterized by t=b=0.

>	mat := matrix(3,5, [20, 30, 1, 0, 60, 5, 4, 0, 1, 12, 25, 30, 0, 0, P-160] );

The largest positive coefficient in the objective (bottom) row is 30, so the pivot column is column 2.

That is, b will lose status as corner variable.

Determine the ratios ...

>	evalf( 60/30 ); evalf( 12/4 );

The smallest positive ratio is 2, so the pivot row is row 1.

That is, s1 will gain status as corner variable.

Proceed with a row operation that turns the pivot into a 1 (divide row 1 by 30), and then do the pivot:

>	mat1 := mulrow( mat, 1, 1/30 );

>	mat2 := pivot( mat1, 1, 2 );

Column 2 has been transformed.

The above matrix is the tableau for corner 2, characterized by t=s1=0.

Look for the largest positive coefficient in the objective row, which is 5, in column 1.

So the pivot column is column 1.

That is, t will lose status as corner variable.

Determine the ratios ...

>	evalf( mat2[1,5]/mat2[1,1] ); evalf( mat2[2,5]/mat2[2,1] );

The smallest positive ratio occurs in row 2.  

So the pivot row is row 2.

That is, s2 will gain status as corner variable.

Proceed with ops that turn column 1 into an elementary column ...

>	mat3 := mulrow( mat2, 2, 3/7 );

>	mat4 := pivot( mat3, 2, 1 );

Column 1 has been transformed.

The above tableau is for corner 3, characterized by s1=s2=0.

Look for the largest positive coefficient in the objective row.

Since there are none, we're done, and we can read off the optimal solution

from the tableau.  It says that the optimal solution occurs at t=12/7 and b=6/7,

and the max profit obtained there is 1600/7=228+4/7.