Allen Only

sudchi
topic_3_-_student2.ppt
Home>Computer Science homework help>Allen Only

Topic III
The Simplex Method

Setting up the Method

Tabular Form

Chapter(s): 4

Key Concepts

  • The simplex method focuses solely on CPF solutions
  • For any problem with at least one optimal solution, finding one only requires finding a best CPF solution

  • The simplex method is an iterative algorithm
  • Initialization
  • Optimality Test
  • If no, perform an iteration to find a better solution
  • If yes, stop

  • Whenever possible, the initialization of the simplex method chooses the origin to be initial CPF solution

Key Concepts

  • Given a CPF solution, it is much quicker computationally to gather information about its adjacent CPF solutions that about other solutions

  • After the current CPF solution is identified, the method identifies the rate of improvement in Z that would be obtained by moving along an edge to an adjacent solution
  • Chooses to move along the one with the largest rate of improvement in Z

  • If none of the edges give a positive rate of improvement, then the current CPF solution is optimal

Setting up the Simplex Method

  • Convert the functional inequality constraints to equivalent equality constraints
  • Accomplished by introducing slack variables

  • An augmented solution is a solution for the original (decision) variables that has been augmented by the corresponding values of the slack variables
  • Example

x1 ≤ 4

  • Adding slack variable gives x1 + x3 = 4
  • Note that these are equivalent iff x3 ≥ 0

Setting up the Simplex Method

  • Original Model (from Topic II)
  • Maximizing Total profit, Z

Maximize Z = 3x1 + 5x2

  • Constraints

x1 ≤ 4

2x2 ≤ 12

3x1 + 2x2 ≤ 18

  • Other constraints

x1 ≥ 0

x2 ≥ 0

Setting up the Simplex Method

  • Augmented form of the model
  • Maximizing Total profit, Z

Maximize Z = 3x1 + 5x2

  • Constraints

x1 + x3 = 4

2x2 + x4 = 12

3x1 + 2x2 + x5 = 18

  • Other constraints

xj ≥ 0, for j = 1, 2, 3, 4, 5

Setting up the Simplex Method

  • The system of functional constraints has 5 variables and 3 equations
  • Number of variables – number of equations = 5 – 3 = 2
  • 2 Degrees of freedom in solving the system (as long as there aren’t any redundant equations)

  • Set any two variables to an arbitrary value to solve the three equation system
  • The simplex method uses zero for this arbitrary value

  • The two variables set to zero are the nonbasic variables

  • The other three variables are the basic variables

Basic Solution

  • A basic solution is an augmented corner-point solution
  • Properties of a basic solution
  • Each variable is designated as either a nonbasic variable or a basic variable

  • The number of basic variables equals the number of functional constraints

  • The number of nonbasic variables equals the total number of variables minus the number of functional constraints

Basic Solution

  • A basic solution is an augmented corner-point solution
  • Properties of a basic solution
  • The nonbasic variables are set to zero

  • The values of the basic variables are obtained as the simultaneous solution of the system of equations (functional constrains in augmented form)
  • The set is often referred to as the basis

  • If the basic variables satisfy the nonnegativity constraints, the basic solution is a BF solution
  • A basic feasible (BF) solution is an augmented CPF solution

Basic Feasible (BF) Solutions

  • Two BF solutions are adjacent if all but one of their nonbasic variables are the same
  • Note that all but one of their basic variables are also the same

  • Moving from the current BF solution to an adjacent one involves switching one variable from nonbasic to basic (and vice versa for one other variable)
  • Adjust the values of the basic variables to satisfy the system of equations

The Simplex Method

  • Step 1: Initialization
  • Choose x1 and x2 to be the nonbasic variables (the variables set to zero)
  • Using system of equations, x3, x4, x5 equal 4, 12, 18

  • Thus, the initial BF solution is (0, 0, 4, 12, 18)

The Simplex Method

  • Step 2: Optimality Test
  • The objective function is Z = 3x1 + 5x2
  • Z = 0 for the initial BF solution

  • Rate of improvement for x2 is more than x1 (5 > 3)
  • Increase x2

Minimum Ratio Test

  • Step 2: Optimality Test
  • Minimum Ratio Test
  • Objective is to determine which basic variable drops to zero first as the entering basic variable is increased

  • The system of equations

x1 + x3 = 4

No upper bound on increasing x2

2x2 + x4 = 12

x4 = 12 – 2x2

Thus, x2 ≤ 6

3x1 + 2x2 + x5 = 18

x5 = 18 – 2x2

Thus, x2 ≤ 9

  • Since the 2nd equation restricts x2 to 6, x4 is the leaving basic variable for this iteration

Solve for New Solution

  • Step 3: Solving for the new BF Solution
  • Original System

Z – 3x1 – 5x2 = 0

x1 + x3 = 4

2x2 + x4 = 12

3x1 + 2x2 + x5 = 18

  • x2 has replaced x4 as the basic variable
  • The pattern of coefficients of x4 (0, 0, 1, 0) need to become the coefficients of x2

Solve for New Solution

  • Step 3: Solving for the new BF Solution
  • How
  • Divide constraint equation 2 by 2

x2 + ½x4 = 6

  • Add 5 times this new equation to the objective function

Z – 3x1 + 5/2 x4 = 30

  • Subtract 2 times new equation to constraint equation 3

3x1 – x4 + x5 = 6

Solve for New Solution

  • Step 3: Solving for the new BF Solution
  • New System

Z – 3x1 + 5/2 x4 = 30

x1 + x3 = 4

x2 + ½x4 = 6

3x1 – x4 + x5 = 6

  • New BF Solution

(0, 6, 4, 0, 6)

Next Iteration

  • Next Iteration: Return to Step 2

Z = 30 + 3x1 – 5/2 x4

  • Z can be increased by increasing x1, but not x4
  • Thus, x1 needs to be the next entering basic variable

  • Minimum Ratio Test

x1 + x3 = 4

x1 ≤ 4

x2 + ½x4 = 6

No upper bound on x1

3x1 – x4 + x5 = 6

x1 ≤ 2

  • x5 is the leaving basic variable

Next Iteration

  • The pattern of coefficients of x5 (0, 0, 0, 1) needs to become the pattern for x1
  • Divide constraint equation 3 by 3

x1 – 1/3 x4 + 1/3 x5 = 2

  • Add 3 times this equation to objective function

Z + 3/2 x4 + x5 = 36

  • Subtract new equation from constraint equation 1

x3 + 1/3 x4 – 1/3 x5 = 2

Next Iteration

  • The pattern of coefficients of x5 (0, 0, 0, 1) needs to become the pattern for x1
  • New System

Z + 3/2 x4 + x5 = 36

x3 + 1/3 x4 – 1/3 x5 = 2

x2 + ½x4 = 6

x1 – 1/3 x4 + 1/3 x5 = 2

  • New BF Solution

(2, 6, 2, 0, 0)

Final Iteration

  • Next iteration

Z = 36 – 3/2 x4 – x5

  • If either nonbasic variable x4 or x5 is increased, Z would decrease
  • Thus, the current BF solution is optimal

  • Original variables: x1 and x2

x1 = 2

x2 = 6

  • Maximum value of Z: 36

Tabular Form

Start with initial equations

Basic Var Eq Z x1 x2 x3 x4 x5 Right Side
Z 0 1 -3 -5 0 0 0 0
x3 1 0 1 0 1 0 0 4
x4 2 0 0 2 0 1 0 12
x5 3 0 3 2 0 0 1 18

Tabular Form

  • Iterations
  • Determine entering basic variable
  • Select variable with negative coefficient with largest absolute value
  • If none, the algorithm is finished

  • Draw box around column below this variable as the pivot column

Tabular Form

  • Iterations
  • Minimum ratio test
  • Select each coefficient in pivot column that is positive

  • Divide each coefficient into corresponding right side entry

  • Identify smallest ratio

  • Basic variable for that row is leaving basic variable
  • Replace it by entering basic variable column of table

  • Box the row and call it the pivot row

  • The number in both pivot row and pivot column is pivot number

Tabular Form

  • Iterations
  • New BF solution
  • Divide pivot row by pivot number (use this total in next two steps)

  • For each other row (including row 0) that has a negative coefficient in the pivot column
  • Add to this row the product of absolute value of this coefficient and new pivot row

  • For each other row that has a positive coefficient in the pivot column
  • Subtract from this the product of its coefficient and the new pivot row