The Simplex Method

Problem

You know how to make two items out of cloths: aprons and bookbags. Aprons require 2 hours of cutting time and 4 hours of sewing time. Bookbags require 3 hours of cutting time and 3 hours of sewing time. You sell the aprons for $18 and the bookbags for $20. How many of each item should you make if you spend 12 hours cutting and 18 hours sewing?

Part 1: Solve using the dictionary method.

Part 2: Solve using the tableau method.

Solution

Part 1: Dictionary method

Let $a$ represent aprons and $b$ represent bookbags.

The linear programming problem we wish to solve is to maximize the revenue (objective function) $18a+20b$ subject to the cutting time constraint $2a+3b\leq 12$ and the sewing time constraint $4a+3b\leq 18$.

${\begin{aligned}Max\quad 18a+20b\\2a+3b\leq 12\\4a+3b\leq 18\\a,b\geq 0\end{aligned}}$

Step 1: Constructing a dictionary

Introduce the slack variables for the number of constraints and construct a dictionary.

Dictionary 1

${\begin{aligned}Z&=0+18a+20b\\s_{1}&=12-2a-3b\\s_{2}&=18-4a-3b\end{aligned}}$

Note that throughout the entire process $a,b,s_{1},s_{2}\geq 0$.

The basic solution is determined by setting the variables in the objective function equal to zero and reading the constant terms for each variable in the dictionary.

Basic solution

$(a,b,s_{1},s_{2})=(0,0,12,18)$

Objective value

$Z=0$

Step 2: Pivoting process

1) Selecting the entering variable.

The variable $b$ is the entering variable since its coefficient, 20, is the largest non-negative coefficient in the objective function.

2) Find the tightest constraint by comparing which ratio is lowest.

For $s_1$: $12/3 = 4$

For $s_2$: $18/3=6$

The ratio for $s_1$ is smaller than the ratio for $s_2$, thus $s_1$ is the leaving variable.

3) Calculate via swapping and substitution.

${\begin{aligned}Z&=0+18a+20(4-(2/3)a-(1/3)b)\\b&=4-(2/3)a-(1/3)b\\s_{2}&=18-4a-3(4-(2/3)a-(1/3)b)\end{aligned}}$

Dictionary 2

${\begin{aligned}Z&=80+(14/3)a-(20/3)s_{1}\\b&=4-(2/3)a-(1/3)b\\s_{2}&=6-2a+s_{1}\end{aligned}}$

Basic solution

$(a,b,s_{1},s_{2})=(0,4,0,6)$

Objective value

$Z=80$

The coefficient of variable $a$ is positive, so there is a more optimal solution.

1) The variable $a$ is the entering variable.

2) The variable $s_2$ is the leaving variable.

For $b$: $4/(2/3)=6$

For $s_2$: $6/2=3$

${\begin{aligned}Z&=80+(14/3)(3-(1/2)s_{2}+(1/2)s_{1})-(20/3)s_{1}\\b&=4-(2/3)(3-(1/2)s_{2}+(1/2)s_{1})-(1/3)b\\a&=3-(1/2)s_{2}+(1/2)s_{1}\end{aligned}}$

Dictionary 3

${\begin{aligned}Z&=94-(13/3)s_{1}-(7/3)s_{2}\\b&=2-(2/3)s_{1}+(1/3)s_{2}\\a&=3+(1/2)s_{1}-(1/2)s_{2}\end{aligned}}$

Notice the coefficients in the objective function are negative; hence, the pivoting process ends here because the objective function cannot be increased any further.

Basic solution

$(a,b,s_{1},s_{2})=(3,2,0,0)$

Objective value

$Z=94$

Therefore you should make 3 aprons and 2 bookbags. The maximum revenue is $94.

Part 2: Tableau Method

Tableau 1

	x	y	s1	s2	Z
s1	2	3	1	0	0	12
s2	4	3	0	1	0	18
Z	-18	-20	0	0	1	0

Select the column with the most negative entry in row 3. This is column 2 (y enters).

Divide the rightmost entry with their respective entries in column 2.

$12/3 = 4$

$18/3=6$

Select the row with the lower quotient in column 2. This is row 1 (s1 leaves).

Row reduce to make the other entries of column 2 zero.

$R_{2}-R_{1}$

$R_{3}+(20/3)R_{1}$

Tableau 2

	x	y	s1	s2	Z
y	2	3	1	0	0	12
s2	2	0	-1	1	0	6
Z	-14/3	0	20/3	0	1	80

              Select the column with the most negative entry in row 3. This is column 1 (x enters).

Divide the rightmost entry with their respective entries in column 1.

$12/2=6$

$6/2=3$

Select the row with the lower quotient in column 1. This is row 2 (s2 leaves).

Row reduce to make the other entries of column 1 zero.

$R_{1}-R_{2}$

$R_{3}+(7/3)R_{2}$

Tableau 3

	x	y	s1	s2	Z
y	0	3	2	-1	0	6
x	2	0	-1	1	0	6
Z	0	0	13/3	7/3	1	94

No more negative entries in row 3! Done!             

Solution

$(x,y)=(6/2,6/3)=(3,2)$             

$Z=94/1=94$