Linear Programming:Simplex Method

MAT 119 FALL 2001

MAT 119

FINITE MATHEMATICS

NOTES

PART 1 – LINEAR ALGEBRA

CHAPTER 4

LINEAR PROGRAMMING:SIMPLEX METHOD

4.1 The Simplex Tableau: Pivoting

Standard form of a Maximum Linear Programming Problem

1.All variables are nonnegative.

2.All other constraints are written as a linear expression that is less than or equal to a positive constant.

Initial simplex tableau – from augmented matrix

objective row –

BV (basic variables) –

RHS (right hand side) -

For a maximum problem is standard form:

1.The constraints are changed from inequalities to equations by the introduction of additional variables – one for each constraint and all nonnegative – slack variables

2.These equations and the objective function are placed in the initial simplex tableau

Pivoting – to pivot a matrix about a given element, called the pivot element, is to apply certain row operations so that the pivot element is replaced by a 1 and all other entries in the same column, the pivot column, becomes 0’s.

Steps for pivoting

1.In the pivot row (where the pivot element appears), divide each entry by the pivot element ( 0). Pivot element becomes 1.

2.Obtain 0’s elsewhere in the pivot column by performing row operations involving the pivot row.

Row operations used in pivoting

1.Replace the pivot row by a positive multiple of that same row.

2.Replace a row by the sum of that row and a multiple of the pivot row.

Analyzing a tableau

To obtain the current values of the objective function and the basic variables in a tableau, follow

1.From the tableau write the equations corresponding to each row.

2.Solve the bottom equation for P and the remaining equations for the basic variables.

3.Set each nonbasic variable equal to 0 to obtain the current values of P and the basic variables.

4.2The Simplex Method: Solving Maximum Problems in Standard Form

Steps

1.Begin with the initial simplex tableau of a maximum problem in standard form.

)

6.The pivot element is the entry in the pivot row and pivot column. (can never be in the objective row. Pivot and repeat the process from step 2 until a stop is obtained.

The choice of pivot column forces us to pivot the variable that apparently improves the value of the objective function most effectively.

The choice of the pivot row prevents us from making this variable too large to be feasible.

4.3Solving Minimum Problems in Standard Form; The Duality Principle

Standard Form of a Minimum Linear Programming Problem

Conditions

1.All the variables are nonnegative.

2.All other constraints are written as linear expressions that are greater than or equal to a constant.

3.The objective function must be expressed as a linear expression with nonnegative coefficients.

Von Neumann Duality Principle

Suppose a minimum linear programming problem is standard form has a solution. The minimum value of the objective function of the minimum problem is standard form equals the maximum value of the objective function of the dual problem, a maximum problem in standard form.

Steps for obtaining the Dual Problem

1.Write the minimum problem in standard form.

2.Construct a matrix that represents the constraints and the objective function.

3.Interchange the rows and columns to form the matrix of the dual problem.

4.Translate this matrix into a maximum problem in standard form.

Solving a Minimum Problem in Standard Form using the Dual Problem

1.Write the dual (maximum) problem.

2.Solve this maximum problem by the simplex method.

3.The minimum value of the objective function (C) will appear in the lower right corner of the final tableau; it is equal to the maximum value of the dual objective function (P). The values of the variables that give ride to the minimum value are located in the objective row in the slack variable columns.

4.4The Simplex Method with Mixed Constraints

Steps

1.Write each constraint, except the nonnegative constraints, as an inequality with the variables on the left side of a  sign.

2.Introduce nonnegative slack variables on the left side of each inequality to form an equality.

3.Set up the initial simplex tableau.

Alternative Pivoting Strategies

4.Whenever negative entries occur in the right hand column RHS of the constraints equations, the pivot element is selected as follows:

Pivot Row:

Identify the negative entries on the RHS and their corresponding basic variables (BV). Ignore the objective row. If any of the basic variables is an x-variable, choose the one with the smallest subscript. Otherwise choose the slack variable with the smallest subscript. The basic variable BV chosen identifies the pivot row. Because the objective row is ignored, it can never be the pivot row.

Pivot Column

Go from left to right along the pivot row until a negative entry is found. Ignore the RHS. This entry identifies the pivot column and is the pivot element. If there are no negative entries in the pivot row except the one in the RHS column, then the problem has no solution.

5.Pivot

1.If, in the new tableau, negative entries appear on the RHS of the constraint equations, repeat step 4.

2.If, in the new tableau, only nonnegative entries appear on the RHS of the constraint equations, then the tableau represents a maximum problem in standard form and the regular method outlined earlier should be used.

Steps for solving a Minimum Problem

1.If z is to be minimized, let P = -z.

2.Solve the linear programming problem: Maximize P subject to the same constraints as the minimum problem.

3.Use the principle thatMinimum of z = - Maximum of P

DOUGLAS A. WILLIAMS, ARIZONA STATE UNIVERSITY, DEPARTMENT OF MATHEMATICS