338 ACTIVITY 13: - Saint Mary's College



Math438 ACTIVITY 14: More on the simplex algorithm – and why it works

WHY: The stopping condition for the simplex algorithm (see theorem 3.3.7) is based on the effects our manipulations have on the bottom row of the simplex tableau, but the discussion of these effects requires the identification of several parts of the tableau – these parts are also necessary for discussion of later work (sensitivity analysis).

One condition for use of the simplex algorithm is that the bottom row (like other rows) must always have 0 entries below the pivot 1’s of the tableau – this may require one of more pivot operations before the use of the simplex algorithm.

LEARNING OBJECTIVES:

1. Understand how to form the initial tableau for a problem in which one or more columns of the identity submatrix do not correspond to slack variables.

2. Discover how to label the initial tableau (using D, B, B-1, CB, CD ) and the current tableau (using B-1D ,

CBTB-1b, CBTB-1D - CD T CBTB-1b ) based on a particular basis matrix for further work with the simplex algorithm.

3. Understand why the optimality test (in theorem 3.3.7) works and what the bottom row of the simplex tableau is showing.

3. Gain experience with the simplex algorithm.

CRITERIA:

1. Quality of the answers to the Critical Thinking Questions.

2. Success with the task using Maple.

RESOURCES:

1. Section 3.3: Strategic Mathematics, especially examples 3.3.4 – 3.3.6.

2. 40 minutes

3. The Maple worksheet Activity14.mw on the Public server

PLAN:

1. Look over the model

2. Complete the Exercise, using the Maple Worksheet

3. Answer the Critical Thinking Questions

MODEL: Standard form:

minimize 2x1 + x2 + x3 - x4 minimize 2x1 + x2 + x3 - x4

subj to: 6x1 - x2 + x3 ≤ 10 subj to: 6x1 - x2 + x3 + x5 = 10

x1 + x2 - x3 ≤ 4 x1 + x2 - x3 + x6 = 4

x1 + 5x2-2x3+ x4 = 5 x1 + 5x2 -2x3 + x4 = 5

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 xi ≥ 0 for all i

A = [pic] , b =[pic], basic variables: x5, x6, x4, nonbasic variables: x1, x2, x3,

We did not have to add slack variables to all the constraints, but the third constraint is the only one that contains x4 , so when we form the tableau we do have a pivot 1 in each row: [pic]

The initial basic feasible solution is [0 0 0 5 10 4 ]T but our tableau does not correctly express z in terms of the non-basic variables.. We see this in the fact that in the bottom row (the coefficient row) there are non-zero entries below some of the 1's [in the “basic variable” columns] of the identity matrix.

We must pivot to make all bottom row entries under the basis columns ( 5, 6 and 4 ) zero. If we do not do this, we will not be able to make a correct choice of entering variable and will not locate the correct entry for the first pivot operation..

Clearing under x4 gives: [pic] This will be our “initial tableau“ from which we begin the simplex algorithm.

Our basic variables at this step are x5, x6, x4 in that order (to get a true identity matrix) so the basis matrix at this step is [pic] (so [pic] ) and [pic] (order (x5, x6, x4) remember) so [pic] - so that when we subtract the objective function coefficients we get [pic] - the first part of the bottom row of the tableau.

We also see that [pic] - the last entry in the bottom row, and we can see that the value of the objective function for this basic feasible solution is –5.

After this adjustment, we can start the simplex process:

There is a 1 in the bottom row at the x3 column. The minimum positive ratio is 10/1 (row 1) so we pivot on a13 to get [pic] (x5 leaves the basis because row 1 was the x5 row)

Now the bottom row is ≤ 0, so we are finished. The basic variables [we read from the top row row down] are, x3 (=10), x6 (=14), x4 (=25) , nonbasic variables: x1, x2, x5. The final basic feasible solution is

[0 0 10 25 0 14]T. According to our theorem, the optimal solution is x1= 0, x2= 0, x3= 10 ,x4 = 25, and the minimum value for the objective is -15.

With this, our final basic feasible solution, we have our final basis (x3, x6, x4) , and so

B = [pic], B-1 = [pic], CBT = [1 0 -1], [pic] - so that when we subtract the objective function coefficients we get [pic] - the bottom row of the tableau [up to the z entry].

We also see that [pic] - the last entry in the bottom row, and we can see that the value of the objective function for this basic feasible solution is –5.

To illustrate the proof of theorem 3.3.7, we only need to identify the columns with the non-basic variables [not in final basis, that is] (representing matrix D) - in this case x1, x2, x5

Then we have D = [pic], CD T= [2 1 0] and we find that B-1D = [pic] , B-1b = [10 14 25 ]T , CBTB-1D - CD T= [-9 -5 -0] and CBTB-1b = -15 - all as they should be for Theorem 3.3.4. - that is, the final tableau can be written [pic] .

EXERCISE:

1. Put into standard form and write out the initial tableau for the following problem:

minimize x1 + x2 + x3 + x4

subject to: – 8x2 + 4x4 ≤ 8

x1 + 2x2 + x3 + 4x4 = 19

x1 – 4x2 + 2x4 ≤ 5

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0

2. Call up Maple , and use the file Activity14..mw (in Public>Courses>Math>Math438) to solve the problem.

3. Identify (from the initial tableau for simplex – after the “clean-up{“ pivot operation) the initial basic variables and initial basis matrix Binit and calculate – for this basis – B–1, CBT, CBTB-1A – CT, B-1b and CBTB-1-b - show that they match the corresponding pieces of the initial tableau (that’s after the bottom row is adjusted)

4. For each step (each tableau) do the same calculations as in 3 – you will be using a different basis matrix each time.

5. Use the final tableau to identify the basic and non-basic variables and the final basis matrix B, and identify D, B, b, CB, and CD. Rearrange the variables to write the tableau in the form [pic] used in theorem 3.3.7

6. Calculate B-1D, B-1b, and CBTB-1D-CDT based on the final tableau and verify that if we rewrite the final tableau with the columns in the order given in #5, we obtain [pic] (as claimed in the proof of 3.3..7).

CRITICAL THINKING QUESTIONS:

1. How do we use the final simplex tableau to find B ?

2. Why are the entries in the bottom row of the new tableau that correspond to the new non-basic variables obtained by computing CBTB-1D - CD T? If we extend this formula to the basic columns, why does this require us to force all the entries in the bottom row under the Identity columns to become zero?

3. Why is it true that the last column of the new tableau is obtained by computing B-1b and that the value of the objective function in the lower right hand corner is CBTB-1b ?

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download