Problem

Linear Programming Feasible Region.svg

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 represent aprons and represent bookbags.

The linear programming problem we wish to solve is to maximize the revenue (objective function) subject to the cutting time constraint and the sewing time constraint .

Step 1: Constructing a dictionary

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

Dictionary 1

Note that throughout the entire process .

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

Objective value

Step 2: Pivoting process

1) Selecting the entering variable.

The variable 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 :

For :

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

3) Calculate via swapping and substitution.

Dictionary 2

Basic solution

Objective value

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

1) The variable is the entering variable.

2) The variable is the leaving variable.

For :

For :

Dictionary 3

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

Objective value

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.

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.

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.

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.

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

             
            
Community content is available under CC-BY-SA unless otherwise noted.