A patient in a hospital is required to have at least 84 ...



Section 6-2 Simplex Method (Maximization)

Example 2

If you think about it, the solution to example 1 was rather naive. If you made 40 dining room tables and 40 dining room chairs then each table would have only one chair. In reality, who would buy a dining room suite with only one chair? To make the problem a bit more realistic, assume that the number of chairs must be at least four times the number of tables.

|Furniture | | |

|# | |Table |

| | | |

|Table | |Chair |

|x1 | |Constraint |

| | | |

|Chair | |Assembly |

|x2 | |8x1 |

| | |+ |

| | |2x2 |

| | |≤ 400 |

| | | |

| | |Finishing |

| | |2x1 |

| | |+ |

| | |x2 |

| | |≤ 120 |

| | | |

| | |Ratio |

| | |4x1 |

| | |- |

| | |x2 |

| | |≤ 0 |

| | | |

| | |Profit |

| | |90x1 |

| | |+ |

| | |25x2 |

| | |Maximize |

| | | |

Alternate Mathematical Model

Introducing slack variables and rewriting the objective function leads to this mathematical model:

8x1 + 2x2 + s1 = 400 (assembly)

2x1 + x2 + s2 = 120 (finishing)

4x1 - x2 + s3 = 0 (ratio)

-90x1 - 25x2 + P = 0 (profit)

x1, x2 ,s1, s2, s3 ≥ 0

Maximize P

Initial Simplex Tableau

We can use an augmented matrix to represent the alternate mathematical model. The augmented matrix is indicated by the shaded regions in the table below. The column and row headings help us interpret the matrix. Basic variables correspond to columns in which there is only one nonzero value (typically a value of one). The basic variables have these nonzero values in different rows. The basic variables are listed in the first column of the table.

|Basic Variables |x1 |x2 |s1 |s2 |s3 |P |

|s1 |1 |1 |1 |0 |0 |20 |

s1 |1/3 |0 |1 |-2/3 |0 |6 | |x2 |2/3 |1 |0 |2/3 |0 |14 | |Revenue |4/3 |0 |0 |10/3 |1 |70 | |

Since there are no negative values in the bottom row, we are done. The maximum revenue is 70 million dollars when x1 (a non-basic variable) is 0 and x2 is 14. That is, the maximum revenue is 70 million dollars when no drive-through restaurants and 14 full-service restaurants are built. Note that s1 = 6 means we could have built 6 more restaurants without violating the licensing constraint.

Graphical Interpretation

This simplex algorithm took us from the basic solution at the origin to the optimal solution at (0, 14) in one step:

[pic]

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

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

Google Online Preview   Download