SimplexExample

125 days ago by kmogli

Linear Programming - Simplex Method

A craftsman produces two products, coffee tables and end tables.  Production data is given in the table below:

 

Labor (per table)

Cost of Materials (per table)

Profit (per table)
Coffee Tables 6 hours $200 $240
End Tables 5 hours $100 $160

If the craftsman wants to work no more than 40 hours each week and if  his material resources allow him to pay no more than $1,000 in materials each week, how many coffee tables and how many end tables should he make to maximize his weekly profit?

 
# Set up the first simplex matrix A=matrix(QQ,[[6,5,1,0,0,40],[200,100,0,1,0,1000],[-240,-160,0,0,1,0]]); A 
        
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrr}
6 & 5 & 1 & 0 & 0 & 40 \\
200 & 100 & 0 & 1 & 0 & 1000 \\
-240 & -160 & 0 & 0 & 1 & 0
\end{array}\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrr}
6 & 5 & 1 & 0 & 0 & 40 \\
200 & 100 & 0 & 1 & 0 & 1000 \\
-240 & -160 & 0 & 0 & 1 & 0
\end{array}\right)

The first simplex matrix represents the solution

x=0,\text{   }y=0
and the corresponding profit z=0.
A.rescale_row(1,1/200); A 
        
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrr}
6 & 5 & 1 & 0 & 0 & 40 \\
1 & \frac{1}{2} & 0 & \frac{1}{200} & 0 & 5 \\
-240 & -160 & 0 & 0 & 1 & 0
\end{array}\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrr}
6 & 5 & 1 & 0 & 0 & 40 \\
1 & \frac{1}{2} & 0 & \frac{1}{200} & 0 & 5 \\
-240 & -160 & 0 & 0 & 1 & 0
\end{array}\right)
A.add_multiple_of_row(0,1,-6); A 
        
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrr}
0 & 2 & 1 & -\frac{3}{100} & 0 & 10 \\
1 & \frac{1}{2} & 0 & \frac{1}{200} & 0 & 5 \\
-240 & -160 & 0 & 0 & 1 & 0
\end{array}\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrr}
0 & 2 & 1 & -\frac{3}{100} & 0 & 10 \\
1 & \frac{1}{2} & 0 & \frac{1}{200} & 0 & 5 \\
-240 & -160 & 0 & 0 & 1 & 0
\end{array}\right)
A.add_multiple_of_row(2,1,240); A 
        
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrr}
0 & 2 & 1 & -\frac{3}{100} & 0 & 10 \\
1 & \frac{1}{2} & 0 & \frac{1}{200} & 0 & 5 \\
0 & -40 & 0 & \frac{6}{5} & 1 & 1200
\end{array}\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrr}
0 & 2 & 1 & -\frac{3}{100} & 0 & 10 \\
1 & \frac{1}{2} & 0 & \frac{1}{200} & 0 & 5 \\
0 & -40 & 0 & \frac{6}{5} & 1 & 1200
\end{array}\right)

Second simplex matrix, corresponding to (x,y)=(5,0); z=1200.
A.rescale_row(0,1/2); A 
        
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrr}
0 & 1 & \frac{1}{2} & -\frac{3}{200} & 0 & 5 \\
1 & \frac{1}{2} & 0 & \frac{1}{200} & 0 & 5 \\
0 & -40 & 0 & \frac{6}{5} & 1 & 1200
\end{array}\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrr}
0 & 1 & \frac{1}{2} & -\frac{3}{200} & 0 & 5 \\
1 & \frac{1}{2} & 0 & \frac{1}{200} & 0 & 5 \\
0 & -40 & 0 & \frac{6}{5} & 1 & 1200
\end{array}\right)
A.add_multiple_of_row(1,0,-1/2); A 
        
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrr}
0 & 1 & \frac{1}{2} & -\frac{3}{200} & 0 & 5 \\
1 & 0 & -\frac{1}{4} & \frac{1}{80} & 0 & \frac{5}{2} \\
0 & -40 & 0 & \frac{6}{5} & 1 & 1200
\end{array}\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrr}
0 & 1 & \frac{1}{2} & -\frac{3}{200} & 0 & 5 \\
1 & 0 & -\frac{1}{4} & \frac{1}{80} & 0 & \frac{5}{2} \\
0 & -40 & 0 & \frac{6}{5} & 1 & 1200
\end{array}\right)
A.add_multiple_of_row(2,0,40); A 
        
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrr}
0 & 1 & \frac{1}{2} & -\frac{3}{200} & 0 & 5 \\
1 & 0 & -\frac{1}{4} & \frac{1}{80} & 0 & \frac{5}{2} \\
0 & 0 & 20 & \frac{3}{5} & 1 & 1400
\end{array}\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrr}
0 & 1 & \frac{1}{2} & -\frac{3}{200} & 0 & 5 \\
1 & 0 & -\frac{1}{4} & \frac{1}{80} & 0 & \frac{5}{2} \\
0 & 0 & 20 & \frac{3}{5} & 1 & 1400
\end{array}\right)

This third simplex matrix has no negative entries in the objective function row and so represents an optimal solution:

(x,y)=\left(5,\frac{5}{2}\right); \,\,z=1400.
Of course the 5/2 end tables must be interpreted sensibly.  In two weeks he will make 10 coffee tables and 5 end tables and profit will  be 2800.