University:
California State University, Northridge
Course:
MATH 462 | Advanced Linear Algebra
Academic year:

2024
Views:

227

Pages:

23
Author:

Allioniy9p

SOLVING LINEAR PROGRAMMING PROBLEMS: The Simplex Method Part 3 The Standard Form and the General Concept • m equations (m=4) • n unknowns (n=6) • Sets (n-m) variables to zero and then solves for the remaining m unknowns • The variables set equal to zero are called nonbasic variables. The remaining ones are called basic variables • At point A, x1 =x2=0 which yields s1 =6, s2 =8, s3=1, and s4=2 • At point B, s2 =x2=0, which yields x1 =4, s1 =2, s3=5, and s4=2 Max z=3x1 +2x2+0s1 +0s2 +0s3 +0s4 s.t. x1 +2x2+s1 =6 2x1 +x2 +s2 =8 -x1 +x2 +s3 =1 x2 +s4=2 x1,x2,s1,s2,s3,s4≥0 A B The Simplex Method in Tabular Form z-3x1 -2x2+0s1 +0s2 +0s3 +0 s4 =0 Obj fcn x1 +2x2+s1 =6 2x1 +x2 +s2 =8 Constraint -x1 +x2 +s3 =1 Equations x2 +s4 =2 Initial Tableau Basic x1 x2 s1 z s1 s2 s3 s4 -3 1 2 -1 0 -2 2 1 1 1 0 1 0 0 0 s2 0 0 1 0 0 s3 0 0 0 1 0 s4 0 0 0 0 1 Solution 0 6 8 1 2 • The basic column identifies the current basic variables s1, s2, s3, and s4 • The nonbasic variables x1 and x2 are not present in the basic column and are equal to zero • The value of Obj Fcn is z=3*0+2*0+6*0+8*0+1*0+2*0=0 Example: Basic x1 x2 s1 s2 s3 s4 Solution z s1 s2 s3 s4 -3 1 2 -1 0 -2 2 1 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 6 8 1 2 Ratio 6/1=6 8/2=4 - • The column associated with the entering variable is called entering column • The row associated with leaving variable is called pivot equation • The element at the intersection of the entering column and pivot row is called pivot element Example: Type 1 Computation Basic x1 x2 s1 s2 s3 s4 Solution z s1 x1 s3 s4 1 1/2 0 1/2 0 0 8/2=4 Basic x1 z s1 0 0 1 -0 0 x1 s3 s4 Complete New Tableau x2 s1 s2 s3 s4 Solution -1/2 0 1 0 0 0 3/2 -1/2 1/2 1/2 0 0 0 0 1 0 0 0 0 0 1 12 2 4 5 2 3/2 1/2 3/2 1 • x1 =4, x2=0, and z=12 (point B) • • • • • • Nonbasic variables: x2 and s2 (zero variables) Basic variables: s1, x1, s3, and s4 (nonzero variables) x2 enters the solution s1 leaves the solution The obj fcn can be improved by 4/3*1/2=2/3 Ratio 4/3 8 10/3 2 Basic x1 z x2 0 0 1 0 0 x1 s3 s4 Iteration 3-Optimal x2 0 1 0 0 0 s1 s2 1/3 4/3 2/3 -1/3 -1/3 2/3 -1 1 -2/3 1/3 s3 s4 Solution 0 0 0 1 0 0 0 0 0 1 12 2/3 4/3 10/3 3 2/3 New pivot s1-Equation=old s1-Equation /1.5 New z-Equation=old z-Equation – (-1/2) *new pivot equation New x1 -Equation=old x1 -Equation – (1/2) * new pivot equation New s3 -Equation=old s3 -Equation – (3/2) * new pivot equation New s4 -Equation=old s4-Equation – (1) * new pivot equation x1 =4/3, x2=10/3, and z=38/3 (point C) • • • • • • Interpreting the Simplex Tableau The optimum solution The status of the resources The unit worth of the resources The sensitivity of the optimum solution to changes in the availability of resources, coefficients of the obj fcn, and usage of resources by activities The first three are in optimal solution of the simplex tableau Forth one needs additional computations Summary • Simplex method was introduced as algebraic procedure for solving LP problems • Described how initial tableau of a linear program is a necessary step in the simplex solution procedure, including (≤), (≥), and (=) constraints into tableau form • Discussed how the special cases of infeasibility, unboundedness, multiple optimal solution, and degeneracy can occur with the simplex method Special Cases in the Simplex Method • Special types of LP problems need special attentions • Special types: – More than one optimal solution – Infeasible problems – Unbounded solutions – Ties for pivot column and/or ties for the pivot row – Constraints with negative quantity values Multiple Optimal Solutions • Recall maximization problem • Alter objective function z=40x1+50x2 To z=40x1+30x2 • Makes it parallel to the constraint line 4x1+ 3x2 = 120 • Endpoints B and C, are referred to as alternate optimal solutions Objective function A B C Multiple Solutions from the Simplex Not in solution Tableau • The optimal simplex tableau is: • How do we know that multiple optimal solution exist? • Determined from the row Z • Negative row Z values represent profit • Values of zero indicate no increase or loss • Coefficients of x1and s1 have zero values • Coefficient of x2 has a value of zero and it is not part of basic solution But has a 0 coef. Basic Z x1 x2 s1 s2 Solution Z 1 0 0 0 10 1200 s1 0 0 1.25 1 -0.25 10 x1 0 1 0.75 0 0.25 30 Multiple Solutions from the Simplex Tableau (cont.) • If x2 enters solution, we will have a new solution without changing z • Multiple optimal solution is indicated by a value of zero in row Z for a nonbasic variable • To determine alternate solution, select x2 as the entering variable and then determine pivot row as usual Basic Z x1 x2 s1 s2 Solutio n Z 1 0 0 0 10 1200 s1 0 0 1.2 5 1 0.25 10 x1 0 1 0.7 5 0 0.25 30 Basic Z x1 x2 s1 s2 Solution Z 1 0 0 0 10 1200 x2 0 0 1 0.8 -0.2 8 x1 0 1 0 -0.6 0.4 24 The Infeasible Solution • Special case where a LP has not feasible solution area Max Z=5x1+3x2 s.t. 4x1+2x2<=8 x1>=4 X>=6 • Because no point satisfies all three constraints simultaneously, there is no solution. The Infeasible Solution (cont.) All values are zero or positive indicating that it is optimal • Solution: x2=4, R1=4, and R2=2 – Existence of artificial variables in final tableau makes the solution meaningless • Occur as a result of making errors in defining problem correctly or in formulating the LP problem Basic Z x1 x2 s1 s2 s3 R1 R2 Solution Z 1 M+1 0 M M 0.5M+1.5 0 0 -0.6M+12 x2 0 2 1 0 0 0.5 0 0 4 R1 0 1 0 -1 0 0 1 0 4 R2 0 -2 0 0 -1 -0.5 0 1 2 Unbounded Problems • Occur where feasible solution area is not closed. • Objective function increases indefinitely without ever reaching a maximum value – Never reaches boundary of the feasible solution area Z=4x1+2x2 Subject to x1≥4 x2≤2 x1, x2≥0 Unbounded Problems (cont.) First tableau • In second tableau, s1 is chosen as the entering variable because it has most negative coefficient in row Z • There is no leaving variable because one row value is -4 and the other is undefined • Indicates that solution is unbounded • A solution is unbounded if row value ratios are all negative or undefined • Occurs as a result of making errors in defining problem or in formulating LP problem Basic Z x1 x2 s1 s2 R1 Solution Z 1 M-4 -2 M 0 0 -4M R1 0 1 0 -1 0 1 4 s2 0 0 1 0 1 0 2 Second tableau Basic Z x1 x2 s1 s2 R1 Solution Z 1 0 -2 -4 0 M+4 16 X1 0 1 0 -1 0 1 4 s2 0 0 1 0 1 0 2 Degeneracy • Possible to have a tie for pivot row • A tie should be broken arbitrarily • Other choice for leaving variable will posses a zero value in next tableau • Solution is said to be degenerate – Z value never improves • An example of a degeneracy condition Maximize Z = 4x1+ 6x2 subject to 6x1+ 4x2 ≤ 24 x2 ≤ 3 5x1+10x2 ≤ 40 Tie for the Pivot Row • In second tableau, we will see a tie for pivot row between s1, and s3 rows • S3 row is selected arbitrarily, the resulting third tableau will be shown Basic Z x1 x2 s1 s2 s3 Solution Z 1 -4 0 0 6 0 18 s1 0 6 0 1 -4 0 12 x2 0 0 1 0 1 0 3 s3 0 5 0 0 -10 1 10 S1 ratio: 12/6 =2 S3 ratio: 10/5 =2 Loop in Solutions • A value of zero for s1 indicates a degeneracy condition • s2 is entering variable and s1 as pivot row Basic Z x1 x2 s1 s2 s3 Solution Z 1 0 0 0 -2 4/5 26 s1 0 0 0 1 8 -6/5 0 x2 0 0 1 0 1 0 3 x1 0 1 0 0 -2 1/5 2 Loops in Solutions (Cont.) • Optimal solution did not change • Graphical analysis of this problem is shown in the next slide Basic Z x1 x2 s1 s2 s3 Solution Z 1 0 0 1/4 0 1/2 26 s2 0 0 0 1/8 1 -3/20 0 x2 0 0 1 -1/8 0 3/20 3 x1 0 1 0 1/4 0 -1/10 2 Graphical Analysis • The intersection causes the tie for pivot row and the degeneracy – Simplex process stays at point B • Degeneracy occurs when a problem continually loops back to same solution • Two tableaus represent two different basic feasible solutions with two different model constraint equations B

Solving Linear Programming Problems: The Simplex Method, Part 3

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock