Linear Programming – Simplex Method



Linear Programming – Simplex Method

The simplex method can be used for problems with more than 2 variables. This method iteratively examines corner points of feasible region. This algebraic method can easily be automated by software.

Convert each constraint into an equation:

|Original Format |Variables Introduced In Conversion |

|≤ constraint |Slack variable |

|≥ constraint |Surplus and Artificial variables |

|= constraint |Artificial variable |

Incorporate all variables in all equations. If they don’t appear assign a coefficient of 0.

|Variable Type |Represents |Coefficient in objective function |Used in |

|Slack Variable |Measures unused resources |0 |≤ constraint |

|Surplus Variable |How much solution exceeds the constraint |0 |≥ constraint |

| |resource | | |

|Artificial Variable |Computational tool, ensures non-negativity of|M (some huge cost) |≥ constraint and |

| |surplus variables | |= constraint |

The simplex method:

▪ A basic feasible solution to a system of n equations is found by setting all but n variables equal to 0 and solving for the other variables.

▪ The method considers only feasible solutions and will only touch the corner points of the feasible region.

▪ The numbers in the body of the simplex tableau can be thought of as substitution rates for the variables in the solution mix.

▪ Any variable that appears in the solution mix column must have the number 1 occupying one cell in its column and 0’s in every other place in that column.

▪ The Zj value for the Quantity column provides the total contribution to objective function (frequently gross profit) of the given solution.

▪ The Zj values for the other columns (variables) represent the gross profit given up by adding one unit of this variable into the current solution.

▪ The Cj – Zj number in each column represents the net profit that will result from introducing 1 unit of each product or variable into the solution,

▪ i.e., the profit gained minus the profit given up.

▪ It is not calculated for the quantity column.

▪ A negative number in the Cj - Zj row would tell us that profits would decrease if the corresponding variable were added to the solution mix while a positive number indicates that the profits would increase.

▪ An optimal solution is reached in the simplex method when the Cj - Zj row contains no positive numbers for a maximization problem or no negative numbers for a minimization problem.

▪ After the initial tableau is completed, proceed through a series of five steps to compute all the numbers needed in the next tableau.

The 5 Steps for maximization [minimization]

1. Choose the variable with the greatest positive [negative] Cj - Zj to enter the solution.

2. Determine the row to be replaced by selecting that one with the smallest [non-negative] quantity-to-pivot-column ratio.

3. Calculate the new values for the pivot row: new # = old # / pivot #

4. Calculate the new values for the other row(s): (new #) = (old #) – (# in pivot column)(new # in pivot row) Gauss-Jordan elimination

5. Calculate the Cj and Cj - Zj values for this tableau.

o If there are any Cj - Zj values greater than [less than] zero, return to step 1.

o Otherwise, the final tableau has been created.

[pic]

|Special case |General Description |Indication in Simplex Method |

|Infeasibility |Contradictory constraints |Artificial variable included in the solution mix |

|Unboundedness |Solution approaches infinity |Ratios of pivot column entries are all ≤ 0 |

|Degeneracy |3 constraints pass through 1 point |More than one smallest ratio in pivot column; can cause |

| | |cycling |

|Alternate optimal solutions |Several optimal solutions exist |Cj – Zj = 0 for variable not in the solution mix |

▪ Sensitivity Analysis shows how the optimal solution and the corresponding value of objective function change, given changes in various inputs to the problem.

▪ Computer programs handling LP problems of all sizes provide sensitivity analysis as an important output feature.

▪ Those programs often use the information provided in the final simplex tableau to compute ranges for the objective function coefficients and ranges for the RHS values.

▪ They also provide “shadow prices,” the value of one additional unit of a scarce resource.

▪ The range over which shadow prices remain valid is called right-hand-side ranging which is computed by dividing the quantity by the indicated value of the variable.

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

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

Google Online Preview   Download