- Completeness
- Clarity
- Depth
RESOURCES:
- Section 3.3: Strategic Mathematics, especially example 3.7.
- 30 minutes
PLAN:
- Choose roles if you have not already done so.
- Look over the model and answer the Critical Thinking Questions.
- Put into standard form and write out the initial tableau for the
following problem:
minimize x1 + x2 + x3 + x4 subject to: x1 - 5x2 + x3 + 3x4 = 19 x1 - 4x2 2x4 <= 5 - 5x2 15x4 <= 10 x1 >= 0, x2 >= 0, x3 >= 0, x4 >= 0
- Call up Maple V, and use the ACT13 Maple Text file in the
directory p:\courses\math\math338 to solve the
problem given in step 2.
- Using the solution to this problem to identify the basic and
non-basic variables and the final basis matrix B,
rearrange the initial tableau for the problem in step 2 so that the
3 non-basic variable columns come first and
the 3 basic variable columns (in the correct order) come after the
non-basic ones. I.e., your tableau should have the form:
| D | B | 0 | b | |-----------------| |-CD |-CB | 1 | 0 |
Put the final tableau in the same column order as the new arrangement of the initial tableau. Then verify (by calculating and comparing) that the final form of the tableau is as claimed in the proof of theorem 3.3.4. I.e.,
| B^(-1)D | I | 0 | B^(-1)b | |-----------------------------------| (*) |CB'B^(-1)D-CD' | 0 | 1 |CB'B^(-1)b |
MODEL:
Standard form:
minimize 2x1 + x2 + x3 - x4 minimize 2x1 + x2 + x3 - x4
subj to: subj to:
6x1 - x2 + x3 <= 10 6x1 - x2 + x3 + x5 = 10
x1 + 5x2 <= 4 x1 + 5x2 + x6 = 4
x1 + 5x2 + x4 = 5 x1 + 5x2 + x4 = 5
x1 >= 0, x2 >= 0, x3 >= 0, x4 >= 0 xi >= 0 for all i
Initial simplex tableau:
| 6 -1 1 0 1 0 | 0 | 10 | | 6 -1 1 0 1 0 |
| 1 5 0 0 0 1 | 0 | 4 | A = | 1 5 0 0 0 1 |
| 1 1 0 1 0 0 | 0 | 5 | | 1 1 0 1 0 0 |
|---------------------------|
|-2 -1 -1 1 0 0 | 1 | 0 | b = [10 4 5]'
The basic variables: x3, x6, x4 and non-basic variables: x1, x2, x5.
The initial bfs is [0 0 10 5 0 4]'
but our tableau does not correctly show the value of the objective
function because one of the basic variables appears
in the objective function. We must make all bottom row entries under
the basis columns 3, 4, and 6 zero by pivoting.
The initial simplex tableau becomes:
| 6 -1 1 0 1 0 | 0 | 10 | | 6 -1 1 0 1 0 | 0 | 10 | | 1 5 0 0 0 1 | 0 | 4 | | 1 5 0 0 0 1 | 0 | 4 | | 1 1 0 1 0 0 | 0 | 5 | ~ | 1 1 0 1 0 0 | 0 | 5 | |---------------------------| |---------------------------| | 4 -2 0 1 1 0 | 0 | 10 | | 3 -3 0 0 1 0 | 1 | 5 |
Now, we can start the simplex process: Bring in x5; min ratio 10/1; take
out x3; The new tableau is:
| 6 -1 1 0 1 0 | 0 | 10 | | 1 5 0 0 0 1 | 0 | 4 | | 1 1 0 1 0 0 | 0 | 5 | |---------------------------| |-3 -2 -1 0 0 0 | 0 | -5 |
Since the bottom row is <= 0, we are finished. The basic variables are x5, x6, x4, non-basic variables are x1, x2, x3. The final bfs is [0 0 0 5 10 4]'. According to the Optimality Theorem, the optimal solution is x1 = 0, x2 = 0, x3 = 0, x4 = 5, x5 = 10, x6 = 4, and the minimum value of the objective function is -5. To better illustrate the proof, we compute the matrices B, D, CB, CD, B^(-1), B^(-1)D, B^(-1)b, CB'B^(-1)D-CD', and CB'B^(-1)b and check to see that they correspond to the partitions in the final tableau as indicated by * above.
| 1 0 0 | | 1 0 0 | | 6 -1 1 | CD = [2 1 1 ]'
B = | 0 1 0 |, B^(-1) = | 0 1 0 |, D = | 1 5 0 |
| 0 0 1 | | 0 0 1 | | 1 1 0 | CB = [0 0 -1]'
B^(-1)D = D, B^(-1)b = b, CB'B^(-1)D-CD' = [-1 -1 0] - [2 1 1] = [-3 -2 -1], and CB'B^(-1)b = -5
CRITICAL THINKING QUESTIONS:
These will be provided in class.
Math 338 Activity 13 -- Revised 10/2/98
