Understanding The Simplex Method for Linear Programming

Slide Note
Embed
Share

The simplex method is an algebraic procedure used to solve linear programming problems by maximizing or minimizing an objective function subject to certain constraints. This method is essential for dealing with real-life problems involving multiple variables and finding optimal solutions. The process involves formulating the problem, applying the simplex algorithm, and interpreting the results to make informed decisions. This comprehensive guide covers the formulation of LP problems, manual application of the simplex algorithm, and various cases encountered during optimization. Explore the graphical and algebraic approaches for solving LP problems efficiently.

alistairj
alistairj Follow

Uploaded on Jul 16, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

  1. The Simplex Method Susana Barreiro 17 March 2021

  2. The Simplex Method The Simplex Method The Simplex Method - formulation (standard form) The Simplex Method - procedure The Simplex Method - particular cases o Tie for the Entering BV o Tie for the Leaving BV - degenerate o No leaving BV Unbounded Z o Multiple optimal solutions The Simplex Method - other cases o Minimization of the objective function o Negative Right Hand Sides o Eliminating negative variables o Functional constraints in and = form o Eliminating unconstrained variables The Simplex Method Exercises

  3. Simplex Method The graphical approach can be used for two-variable LP problems Unfortunately, most real-life LPs problems require a method to find optimal solutions capable of dealing with several variables: the simplex algorithm In the classes we will focus on the manual application of the simplex algorithm (using EXCEL), although computer packages to apply the simplex algorithm have been developed (LINDO and LINGO)

  4. Simplex Method Formulation

  5. Simplex Method - Formulation In LP problem, the decision maker usually wants to: maximize (usually revenue or profit) mminimize (usually costs) Poets Problem ( /yr) Max: Z = 90 x1+ 120 x2 the objective function (Z) is expressed by a set of decision variables Certain limitations are often imposed to these decision variables (expressed in the form of , = or ). These restrictions are called constraints Subject to: x1 40 x2 50 2x1+ 3x2 180 (ha of pine) (ha of eucalypt) (days of work) and x1 0; x2 0

  6. Simplex Method - Formulation The Simplex algorithm is an algebraic procedure to solve LP problems based on geometric concepts that requires LP problems to be presented in the standard form: 1) Objective function is maximized ( /yr) Max: Z = 90 x1+ 120 x2 2) Constraints in the form of inequalities Subject to: x1 40 x2 50 2x1+ 3x2 180 (ha of pine) (ha of eucalypt) (days of work) 3) All values on the right handside are 4) All variables are nonnegative ( ) and x1 0; x2 0

  7. Simplex Method - Formulation The Simplex algorithm is an algebraic procedure to solve LP problems based on geometric concepts that must be translated into algebraic language to allow solving systems of equations. 1st- transform all inequalities into equalities by introducing one additional variable to each constraint (the slack variables: S1, S2, S3). Original form: Standard or augmented form: Max: Z = 90 x1+ 120 x2 Max: Z = 90 x1+ 120 x2 Subject to: Subject to: x1 + S1 x2 + S2 2x1+ 3x2 + S3= 180 = 40 = 50 x1 + S1 x2 + S2 2x1+ 3x2 + S3 180 40 50 and x1 x2 S1S2 S3 0 and x1 x2 S1 S2 S3 0

  8. Simplex Method - Formulation The Simplex algorithm is an algebraic procedure to solve LP problems based on geometric concepts that must be translated into algebraic language to allow solving systems of equations. 1st- transform all inequalities into equalities by introducing one additional variable to each constraint (the slack variables: S1, S2, S3). 2nd- transform the objective function into an additional constraint Max: Z = 90 x1+ 120 x2 Z - 90 x1- 120 x2 x1 + S1 = 0 = 40 = 50 Subject to: x1 + S1 x2 + S2 2x1+ 3x2 + S3= 180 = 40 = 50 x2 + S2 2x1+ 3x2 + S3= 180 and x1 , x2 , S1 , S2 , S3 0

  9. Simplex Method - Formulation The Simplex algorithm is an algebraic procedure to solve LP problems based on geometric concepts that must be translated into algebraic language to allow solving systems of equations. 1st- transform all inequalities into equalities by introducing one additional variable to each constraint (the slack variables: S1, S2, S3). 2nd- transform the objective function into an additional constraint 3rd- build the Simplex tabular form where only the essential information is recorded Z - 90 x1- 120 x2 x1 + S1 = 0 = 40 = 50 x2 + S2 2x1+ 3x2 + S3= 180

  10. Simplex Method - Formulation The Simplex algorithm is an algebraic procedure to solve LP problems based on geometric concepts that must be translated into algebraic language to allow solving systems of equations. 1st- transform all inequalities into equalities by introducing one additional variable to each constraint (the slack variables: S1, S2, S3). 2nd- transform the objective function into an additional constraint 3rd- build the Simplex tabular form where only the essential information is recorded Each basic feasible solution has basic or non-basic variables - non-basic variables are set to ZERO - basic variables are directly obtained from the table initialize the procedure setting x1 =x2 = 0 Basic variables Non-basic variables (X1, X2, S1, S2, S3 ) =( 0, 0, 40, 50, 180)

  11. Simplex Method - Graphical analysis The Simplex algorithm is a search procedure that: - shifts through the set of basic feasible solutions, one at a time, until the optimal basic feasible solution (whenever it exists) is identified. - the method is an efficient implementation the Corner Points Procedure. Corner point feasible solutions vertices of the feasible region B= (0,50) C= (15,50) Optimal solution(s) vertice(s) of the feasible region that maximize Z, ie solution that gives the best favorable value to the objective function D= (40,33) A= (0,0) E= (40,0)

  12. Simplex Method - Graphical analysis The Simplex algorithm is a search procedure that: - shifts through the set of basic feasible solutions, one at a time, until the optimal basic feasible solution (whenever it exists) is identified. - the method is an efficient implementation the Corner Points Procedure. Replacing X1and X2by the values of A, B, C, D and E in the objective function: B= (0,50) C= (15,50) ZA= 0 ZB= 6000 ZC= 7350 ZD= 7600 ZE= 3600 D= (40,33) Z = 90 x1+ 120 x2 A= (0,0) E= (40,0)

  13. Simplex Method - Graphical analysis The Simplex algorithm is a search procedure that: - shifts through the set of basic feasible solutions, one at a time, until the optimal basic feasible solution (whenever it exists) is identified. - the method is an efficient implementation the Corner Points Procedure. Feasible solutions within or on the border of the feasible region ie solutions for which the constraints are satisfied B= (0,50) C= (15,50) D= (40,33) Infeasible solution outside the feasible region, ie solution for which at least one constraint is violated A= (0,0) E= (40,0)

  14. Simplex Method - Formulation Bring the LP problem to the standard form -> obtain a BFS ie set A= (x1, x2) = (0, 0) Optimality check No Find another feasible solution Find in which direction to move towards the algebraic equivalent of an extreme point ie a Basic Feasible Solution with a single different basic variable B= (0,50) C= (15,50) Swap the non-basic variable with one of the basic variables A = (X1, X2, S1, S2, S3 ) = ( 0, 0, 40, 50, 180) B = (X1, X2, S1, S2, S3 ) = ( 0, 50, 40, 0, 30) basic A is adjacent to B but not to C B is adjacent to both A and C Apply Gaussian elimination to transform the new basic variable to (0,1) while solving for Z D= (40,33) A B C A= (0,0) E= (40,0) S1, S2, S3 S1, X2, S3 X1, X2, S2 C = (X1, X2, S1, S2, S3 ) = (15, 50, 0, 25, 0 ) non-basic X1, X2 X1, S2 S1, S3

  15. Simplex Method Procedure

  16. Simplex Method - Procedure Bring the LP problem to the standard form -> obtain a BFS ie set (x1, x2) = (0, 0) Optimality check: The current BFS is optimal (in a max LP) if every coefficient in Row 0 is 0. Find another feasible solution No Entering variable: Choose the entering variable (in a max problem) to be the NBV with the most negative coefficient in Row 0. Ties may be broken in an arbitrary fashion. Yes Leaving BV: apply minimum ratio test - identify the row with the smallest ratio RHS /aij (the most restrictive Row); the BV for this row is the leaving BV (it becomes nonbasic). Apply Gauss-Jordan elimination procedure to solve the system of linear equations. Optimal feasible solution found STOP SIMPLEX

  17. Simplex Method - Procedure coefficients of: Row basic var. Z x1 x2 S1 S2 S3 right side -120 -> 0 R0 Z 1 -90 -120 0 0 0 0 0 R1 S1 1 0 1 0 0 40 R2 x2 0 0 1 0 1 0 50 3 -> 0 R3 S3 0 2 3 0 0 1 180 (1+120*0) (-90+120*0) (-120+120*1) (0+120*0) (0+120*1) (0+120*0) (0+120*50) R0 R0-(-120)*R2 1 -90 0 0 120 0 6000 R1 0 1 0 1 0 0 40 R2 0 0 1 0 1 0 50 (0-3*0) (2-3*0) (3-3*1) (0-3*0) (0-3*1) (1-3*0) (180-3*50) R3 R3-(3)*R2 0 2 0 0 -3 1 30

  18. Simplex Method - Procedure coefficients of: Row basic var. Z x1 x2 S1 S2 S3 right side -120 -> 0 R0 Z 1 -90 -120 0 0 0 0 0 R1 S1 1 0 1 0 0 40 R2 x2 0 0 1 0 1 0 50 3 -> 0 R3 S3 0 2 3 0 0 1 180 (1+120*0) (-90+120*0) (-120+120*1) (0+120*0) (0+120*1) (0+120*0) (0+120*50) R0 R0-(-120)*R2 1 -90 0 0 120 0 6000 R1 0 1 0 1 0 0 40 R2 0 0 1 0 1 0 50 (0-3*0) (2-3*0) (3-3*1) (0-3*0) (0-3*1) (1-3*0) (180-3*50) R3 R3-(3)*R2 0 2 0 0 -3 1 30

  19. Simplex Method - Procedure coefficients of: Row basic var. Z x1 x2 S1 S2 S3 right side -120 -> 0 R0 Z 1 -90 -120 0 0 0 0 0 R1 S1 1 0 1 0 0 40 R2 x2 0 0 1 0 1 0 50 3 -> 0 R3 S3 0 2 3 0 0 1 180 (1+120*0) (-90+120*0) (-120+120*1) (0+120*0) (0+120*1) (0+120*0) (0+120*50) R0 R0-(-120)*R2 1 -90 0 0 120 0 6000 R1 0 1 0 1 0 0 40 R2 0 0 1 0 1 0 50 (0-3*0) (2-3*0) (3-3*1) (0-3*0) (0-3*1) (1-3*0) (180-3*50) R3 R3-(3)*R2 0 2 0 0 -3 1 30

  20. Simplex Method - Procedure coefficients of: Row basic var. Z x1 x2 S1 S2 S3 right side -120 -> 0 R0 Z 1 -90 -120 0 0 0 0 0 R1 S1 1 0 1 0 0 40 R2 x2 0 0 1 0 1 0 50 3 -> 0 R3 S3 0 2 3 0 0 1 180 (1+120*0) (-90+120*0) (-120+120*1) (0+120*0) (0+120*1) (0+120*0) (0+120*50) R0 R0-(-120)*R2 1 -90 0 0 120 0 6000 R1 0 1 0 1 0 0 40 R2 0 0 1 0 1 0 50 (0-3*0) (2-3*0) (3-3*1) (0-3*0) (0-3*1) (1-3*0) (180-3*50) R3 R3-(3)*R2 0 2 0 0 -3 1 30

  21. Simplex Method - Procedure coefficients of: Row basic var. Z x1 x2 S1 S2 S3 right side -120 -> 0 R0 Z 1 -90 -120 0 0 0 0 0 R1 S1 1 0 1 0 0 40 R2 x2 0 0 1 0 1 0 50 3 -> 0 R3 S3 0 2 3 0 0 1 180 (1+120*0) (-90+120*0) (-120+120*1) (0+120*0) (0+120*1) (0+120*0) (0+120*50) R0 R0-(-120)*R2 1 -90 0 0 120 0 6000 R1 0 1 0 1 0 0 40 R2 0 0 1 0 1 0 50 (0-3*0) (2-3*0) (3-3*1) (0-3*0) (0-3*1) (1-3*0) (180-3*50) R3 R3-(3)*R2 0 2 0 0 -3 1 30

  22. Simplex Method - Procedure coefficients of: Row basic var. Z x1 x2 S1 S2 S3 right side -120 -> 0 R0 Z 1 -90 -120 0 0 0 0 0 R1 S1 1 0 1 0 0 40 R2 x2 0 0 1 0 1 0 50 3 -> 0 R3 S3 0 2 3 0 0 1 180 (1+120*0) (-90+120*0) (-120+120*1) (0+120*0) (0+120*1) (0+120*0) (0+120*50) R0 R0-(-120)*R2 1 -90 0 0 120 0 6000 R1 0 1 0 1 0 0 40 R2 0 0 1 0 1 0 50 (0-3*0) (2-3*0) (3-3*1) (0-3*0) (0-3*1) (1-3*0) (180-3*50) R3 R3-(3)*R2 0 2 0 0 -3 1 30

  23. Simplex Method - Procedure coefficients of: Row basic var. Z x1 x2 S1 S2 S3 right side -120 -> 0 R0 Z 1 -90 -120 0 0 0 0 0 R1 S1 1 0 1 0 0 40 R2 x2 0 0 1 0 1 0 50 3 -> 0 R3 S3 0 2 3 0 0 1 180 (1+120*0) (-90+120*0) (-120+120*1) (0+120*0) (0+120*1) (0+120*0) (0+120*50) R0 R0-(-120)*R2 1 -90 0 0 120 0 6000 R1 0 1 0 1 0 0 40 R2 0 0 1 0 1 0 50 (0-3*0) (2-3*0) (3-3*1) (0-3*0) (0-3*1) (1-3*0) (180-3*50) R3 R3-(3)*R2 0 2 0 0 -3 1 30

  24. Simplex Method - Procedure coefficients of: Row basic var. Z x1 x2 S1 S2 S3 right side -120 -> 0 R0 Z 1 -90 -120 0 0 0 0 0 R1 S1 1 0 1 0 0 40 R2 x2 0 0 1 0 1 0 50 3 -> 0 R3 S3 0 2 3 0 0 1 180 (1+120*0) (-90+120*0) (-120+120*1) (0+120*0) (0+120*1) (0+120*0) (0+120*50) R0 R0-(-120)*R2 1 -90 0 0 120 0 6000 R1 0 1 0 1 0 0 40 R2 0 0 1 0 1 0 50 (0-3*0) (2-3*0) (3-3*1) (0-3*0) (0-3*1) (1-3*0) (180-3*50) R3 R3-(3)*R2 0 2 0 0 -3 1 30

  25. Simplex Method - Procedure coefficients of: Row basic var. Z x1 x2 S1 S2 S3 right side -120 -> 0 R0 Z 1 -90 -120 0 0 0 0 0 R1 S1 1 0 1 0 0 40 R2 x2 0 0 1 0 1 0 50 3 -> 0 R3 S3 0 2 3 0 0 1 180 (1+120*0) (-90+120*0) (-120+120*1) (0+120*0) (0+120*1) (0+120*0) (0+120*50) R0 R0-(-120)*R2 1 -90 0 0 120 0 6000 R1 0 1 0 1 0 0 40 R2 0 0 1 0 1 0 50 (0-3*0) (2-3*0) (3-3*1) (0-3*0) (0-3*1) (1-3*0) (180-3*50) R3 R3-(3)*R2 0 2 0 0 -3 1 30

  26. Simplex Method - Procedure coefficients of: Row basic var. Z x1 x2 S1 S2 S3 right side -120 -> 0 R0 Z 1 -90 -120 0 0 0 0 0 R1 S1 1 0 1 0 0 40 R2 x2 0 0 1 0 1 0 50 3 -> 0 R3 S3 0 2 3 0 0 1 180 (1+120*0) (-90+120*0) (-120+120*1) (0+120*0) (0+120*1) (0+120*0) (0+120*50) R0 R0-(-120)*R2 1 -90 0 0 120 0 6000 R1 0 1 0 1 0 0 40 R2 0 0 1 0 1 0 50 (0-3*0) (2-3*0) (3-3*1) (0-3*0) (0-3*1) (1-3*0) (180-3*50) R3 R3-(3)*R2 0 2 0 0 -3 1 30

  27. Simplex Method - Procedure coefficients of: Row basic var. Z x1 x2 S1 S2 S3 right side -120 -> 0 R0 Z 1 -90 -120 0 0 0 0 0 R1 S1 1 0 1 0 0 40 R2 x2 0 0 1 0 1 0 50 3 -> 0 R3 S3 0 2 3 0 0 1 180 (1+120*0) (-90+120*0) (-120+120*1) (0+120*0) (0+120*1) (0+120*0) (0+120*50) R0 R0-(-120)*R2 1 -90 0 0 120 0 6000 R1 0 1 0 1 0 0 40 R2 0 0 1 0 1 0 50 (0-3*0) (2-3*0) (3-3*1) (0-3*0) (0-3*1) (1-3*0) (180-3*50) R3 R3-(3)*R2 0 2 0 0 -3 1 30

  28. Simplex Method - Procedure coefficients of: Row basic var. Z x1 x2 S1 S2 S3 right side -120 -> 0 R0 Z 1 -90 -120 0 0 0 0 0 R1 S1 1 0 1 0 0 40 R2 x2 0 0 1 0 1 0 50 3 -> 0 R3 S3 0 2 3 0 0 1 180 (1+120*0) (-90+120*0) (-120+120*1) (0+120*0) (0+120*1) (0+120*0) (0+120*50) R0 R0-(-120)*R2 1 -90 0 0 120 0 6000 R1 0 1 0 1 0 0 40 R2 0 0 1 0 1 0 50 (0-3*0) (2-3*0) (3-3*1) (0-3*0) (0-3*1) (1-3*0) (180-3*50) R3 R3-(3)*R2 0 2 0 0 -3 1 30

  29. Simplex Method - Procedure coefficients of: Row basic var. Z x1 x2 S1 S2 S3 right side -120 -> 0 R0 Z 1 -90 -120 0 0 0 0 0 R1 S1 1 0 1 0 0 40 R2 x2 0 0 1 0 1 0 50 3 -> 0 R3 S3 0 2 3 0 0 1 180 (1+120*0) (-90+120*0) (-120+120*1) (0+120*0) (0+120*1) (0+120*0) (0+120*50) R0 R0-(-120)*R2 1 -90 0 0 120 0 6000 R1 0 1 0 1 0 0 40 R2 0 0 1 0 1 0 50 (0-3*0) (2-3*0) (3-3*1) (0-3*0) (0-3*1) (1-3*0) (180-3*50) R3 R3-(3)*R2 0 2 0 0 -3 1 30

  30. Simplex Method - Procedure coefficients of: Row basic var. Z x1 x2 S1 S2 S3 right side -120 -> 0 R0 Z 1 -90 -120 0 0 0 0 0 R1 S1 1 0 1 0 0 40 R2 x2 0 0 1 0 1 0 50 3 -> 0 R3 S3 0 2 3 0 0 1 180 (1+120*0) (-90+120*0) (-120+120*1) (0+120*0) (0+120*1) (0+120*0) (0+120*50) R0 R0-(-120)*R2 1 -90 0 0 120 0 6000 R1 0 1 0 1 0 0 40 R2 0 0 1 0 1 0 50 (0-3*0) (2-3*0) (3-3*1) (0-3*0) (0-3*1) (1-3*0) (180-3*50) R3 R3-(3)*R2 0 2 0 0 -3 1 30

  31. Simplex Method - Procedure coefficients of: Row basic var. Z x1 x2 S1 S2 S3 right side -120 -> 0 R0 Z 1 -90 -120 0 0 0 0 0 R1 S1 1 0 1 0 0 40 R2 x2 0 0 1 0 1 0 50 3 -> 0 R3 S3 0 2 3 0 0 1 180 (1+120*0) (-90+120*0) (-120+120*1) (0+120*0) (0+120*1) (0+120*0) (0+120*50) R0 R0-(-120)*R2 1 -90 0 0 120 0 6000 R1 0 1 0 1 0 0 40 R2 0 0 1 0 1 0 50 (0-3*0) (2-3*0) (3-3*1) (0-3*0) (0-3*1) (1-3*0) (180-3*50) R3 R3-(3)*R2 0 2 0 0 -3 1 30

  32. Simplex Method - Procedure coefficients of: Row basic var. Z x1 x2 S1 S2 S3 right side R0 Z 1 -90 0 0 120 0 6000 R1 S1 0 1 0 1 0 0 40 R2 x2 0 0 1 0 1 0 50 R3 S3 0 2 0 0 -3 1 30 (1+120*0) (-90+120*0) (-120+120*1) (0+120*0) (0+120*1) (0+120*0) (0+120*50) R0 R0-(-120)*R2 1 -90 0 0 120 0 6000 R1 0 1 0 1 0 0 40 R2 0 0 1 0 1 0 50 (0-3*0) (2-3*0) (3-3*1) (0-3*0) (0-3*1) (1-3*0) (180-3*50) R3 R3-(3)*R2 0 2 0 0 -3 1 30

  33. Simplex Method - Procedure coefficients of: Row basic var. Z x1 x2 S1 S2 S3 right side R0 Z 1 -90 0 0 120 0 6000 Z = 6000 S1 = 40 X2 = 50 S3 = 30 X1 = 0 S2 = 0 R1 S1 0 1 0 1 0 0 40 R2 x2 0 0 1 0 1 0 50 R3 S3 0 2 0 0 -3 1 30 (x1, x2, S1, S2, S3) = (0, 50, 40, 0, 30) (x1, x2) = (0,50) X1 = 0 Plant 0 ha of pine X2 = 50 Plant 50 ha of eucalypt S1 = 40 40 ha of area available for pine plant. S2 = 0 no ha of area available for eucalypt plant. S3 = 30 30 working hours still available

  34. Simplex Method - Procedure (x1, x2, S1, S2, S3) = (0, 0, 40, 50, 180) (x1, x2) = (0,0) coefficients of: Row basic var. Z x1 x2 S1 S2 S3 right side R0 Z 1 -90 0 0 120 0 6000 Z = 6000 S1 = 40 X2 = 50 S3 = 30 X1 = 0 S2 = 0 R1 S1 0 1 0 1 0 0 40 R2 x2 0 0 1 0 1 0 50 R3 S3 0 2 0 0 -3 1 30 (x1, x2) = (0,50) (x1, x2, S1, S2, S3) = (0, 50, 40, 0, 30) The basic variables in these solutions differ in one single variable (S1 and S3 are maintained as basic variables) These are adjacent solutions

  35. Simplex Method - Procedure (x1, x2, S1, S2, S3) = (0, 0, 40, 50, 180) (x1, x2) = (0,0) coefficients of: Row basic var. Z x1 x2 S1 S2 S3 right side R0 Z 1 -90 0 0 120 0 6000 Z = 6000 S1 = 40 X2 = 50 S3 = 30 X1 = 0 S2 = 0 R1 S1 0 1 0 1 0 0 40 R2 x2 0 0 1 0 1 0 50 R3 S3 0 2 0 0 -3 1 30 (x1, x2) = (0,50) (x1, x2, S1, S2, S3) = (0, 50, 40, 0, 30) B= (0,50) C= (15,50) D= (40,33) A= (0,0) E= (40,0)

  36. Optimality check: The current BFS is optimal (in a max LP) if every coefficient in Row 0 is 0. Simplex Method - Procedure X1 will become basic S3 will become non-basic variable coefficients of: Row ratio basic var. Z x1 x2 S1 S2 S3 right side R0 Z 1 -90 0 0 120 0 6000 (X1 column will have to take the shape of S3: (0, 0, 0, 1) R1 S1 0 1 0 1 0 0 40 40/1= 40 R2 x2 0 0 1 0 1 0 50 - R3 S3 0 2 0 0 -3 1 30 30/2= 15

  37. coefficients of: Row ratio basic var. Z x1 x2 S1 S2 S3 right side R0 Z 1 -90 0 0 120 0 6000 Simplex Method - Procedure R1 S1 0 1 0 1 0 0 40 40/1= 40 R2 x2 0 0 1 0 1 0 50 - R3 S3 0 2 0 0 -3 1 30 -30/-2= 15 coefficients of: Row ratio basic var. Z x1 x2 S1 S2 S3 right side R0 Z 1 -90 0 0 120 0 6000 R1 S1 0 1 0 1 0 0 40 40/1= 40 R2 x2 0 0 1 0 1 0 50 - R3 S3 0 2 0 0 -3 1 30 -30/-2= 15 R3 R3*(1/2) (0*(1/2)) (2*(1/2)) (0*(1/2)) (0*(1/2)) (-3*(1/2)) (1*(1/2)) (30*(1/2)) 0 1 0 0 -1.5 0.5 15

  38. coefficients of: Row ratio basic var. Z x1 x2 S1 S2 S3 right side R0 Z 1 -90 0 0 120 0 6000 Simplex Method - Procedure R1 S1 0 1 0 1 0 0 40 40/1= 40 R2 x2 0 0 1 0 1 0 50 - R3 S3 0 2 0 0 -3 1 30 -30/-2= 15 coefficients of: Row basic var. Z 1 0 0 0 x1 -90 1 0 1 x2 0 0 1 0 S1 0 1 0 0 S2 120 0 1 -1.5 S3 0 0 0 0.5 right side R0 R1 R2 R3 Z S1 x2 x1 6000 40 50 15 -90 -> 0 1 -> 0 R0 R0-(-90)*R3 (1+90*0) (-90+90*1) (0+90*0) (0+90*0) (120+90*-1.5) (0+90*0.5) (6000+90*15) 1 0 0 0 -15 45 7350 R1 R1-(1)*R3 (0-1*0) (1-1*1) (0-1*0) (1-1*0) (0-1*-1.5) (0-1*0.5) (40-1*40) 0 0 0 1 1.5 -0.5 25

  39. coefficients of: Row ratio basic var. Z x1 x2 S1 S2 S3 right side R0 Z 1 -90 0 0 120 0 6000 Simplex Method - Procedure R1 S1 0 1 0 1 0 0 40 40/1= 40 R2 x2 0 0 1 0 1 0 50 - R3 S3 0 2 0 0 -3 1 30 -30/-2= 15 coefficients of: Row basic var. Z 1 0 0 0 x1 0 0 0 1 x2 0 0 1 0 S1 0 1 0 0 S2 -15 1.5 1 -1.5 S3 45 -0.5 0 0.5 right side R0 R1 R2 R3 Z S1 x2 x1 7350 25 50 15 Z = 7350 S1 = 25 X2 = 50 x1 = 15 S2 = 0 S3 = 0 (x1, x2) = (0,0) (x1, x2, S1, S2, S3) = (0, 0, 40, 50, 180) z=0 (A) (x1, x2) = (0,50) (x1, x2, S1, S2, S3) = (0, 50, 40, 0, 30) z=6000 (B) (x1, x2) = (15,50) (x1, x2, S1, S2, S3) = (15, 50, 25, 0, 0) z=7350 (C) B= (0,50) C= (15,50) X1 = 15 Planted 15 ha of pine X2 = 50 Planted 50 ha of eucalypt S1 = 25 25 ha of area available for pine plant. S2 = 0 no ha of area available for eucalypt plant. S3 = 0 no working hours available D= (40,33) A= (0,0) E= (40,0)

  40. Optimality check: The current BFS is optimal (in a max LP) if every coefficient in Row 0 is 0. Simplex Method - Procedure coefficients of: Row basic var. Z 1 0 0 0 x1 0 0 0 1 x2 0 0 1 0 S1 0 1 0 0 S2 -15 1.5 1 -1.5 S3 45 -0.5 0 0.5 right side ratio R0 R1 R2 R3 Z S1 x2 x1 7350 25 50 15 25/1.5= - 15/-1.5= -10 17 Entering variable: the most negative coefficient in Row 0 S2 will become basic S1 will become non-basic variable Leaving BV: the smallest positive ratio RHS /aij (S2 column will have to take the shape of S1: (0, 1, 0, 0) R1 R1*(1/1.5) (0*(1/1.5)) (0*(1/1.5)) (0*(1/1.5)) (1*(1/1.5)) (1.5*(1/1.5)) (-0.5*(1/1.5)) (25*(1/1.5)) 0 0 0 0.67 1 -0.33 16.67

  41. Optimality check: The current BFS is optimal (in a max LP) if every coefficient in Row 0 is 0. Simplex Method - Procedure coefficients of: S2 will become basic S1 will become non-basic variable Row basic var. Z 1 0 0 0 x1 0 0 0 1 x2 0 0 1 0 S1 0 0.67 0 0 S2 -15 1 1 -1.5 S3 45 right side R0 R1 R2 R3 Z S2 x2 x1 7350 16.67 50 15 -0.33 0 0.5 (S2 column will have to take the shape of S1: (0, 1, 0, 0) R0 R0-(-15)*R1 (1+15*0) (0+15*0) (0+15*0) (0+15*0.67) (-15+15*1) (45+15*-0.33)(7350+15*16.67) 1 0 0 10 0 40 7600 R2 R2-(1)*R1 (0-1*0) (0-1*0) (1-1*0) (0-1*0.67) (1-1*1) (0-1*-0.33) (50-1*16.67) 0 0 1 -0.67 0 0.33 33.33 R3 R3-(-1.5)*R1 (0+1.5*0) (1+1.5*0) (0+1.5*0) (0+1.5*0.67) (-1.5+1.5*1)(0.5+1.5*-0.33)(15+1.5*16.67) 0 1 0 1 0 0 40

  42. Optimality check: The current BFS is optimal (in a max LP) if every coefficient in Row 0 is 0. Simplex Method - Procedure OPTIMAL SOLUTION! coefficients of: Row basic var. Z 1 0 0 0 x1 0 0 0 1 x2 0 0 1 0 S1 10 0.67 -0.67 1 S2 0 1 0 0 S3 40 right side R0 R1 R2 R3 Z S2 x2 x1 7600 16.67 33.33 40 Z = 7600 S2 = 16.67 X2 = 33.33 x1 = 40 S1 = 0 S3 = 0 -0.33 0.33 0 (x1, x2) = (0,0) (x1, x2, S1, S2, S3) = (0, 0, 40, 50, 180) z=0 (A) (x1, x2) = (0,50) (x1, x2, S1, S2, S3) = (0, 50, 40, 0, 30) z=6000 (B) (x1, x2) = (15,50) (x1, x2, S1, S2, S3) = (15, 50, 25, 0, 30) z=7350 (C) (x1, x2) = (40,33.33) (x1, x2, S1, S2, S3) = (40, 33.33, 0, 16.67, 0) z=7600 (D) B= (0,50) C= (15,50) X1 = 40 Planted 40 ha of pine X2 = 33.33 Planted 33.33 ha of eucalypt S1 = 0 0 ha of area available for pine plant. S2 = 16.67 16.67 ha of area available for eucalypt plant. S3 = 0 no working hours available D= (40,33) A= (0,0) E= (40,0)

  43. Simplex Method Graphical approach Graphical Method Simplex Method Replace each inequality by an equality Find the set of points satisfying the equality (allows to draw a line that cuts the plane into 2 half-planes) Find which half-plane satisfies the inequality Intercept all the half-plane areas to find the feasible region (FR) feasible solutions = (x1, x2) corners Draw iso-lines for the objective function to find the optimal solution: (x1, x2) corner point of the FR

  44. Simplex Method Graphical approach Graphical Method Simplex Method Replace each inequality by an equality adding a slack variable Transform the objective function into an equality Build a table for the constraints only specifying the coefficients Replace each inequality by an equality Set x1 and x2 to ZERO =>x1=0; x2=0; S1=40; S2=50; S3=180 Find the set of points satisfying the equality (allows to draw a line that cuts the plane into 2 half-planes) Non-basic variables Basic variables Test different combinations of basic variables Select the non-basic var. that results in a bigger increase in Z (the smallest coefficient in R0) Select the basic var. that guarantees the biggest increase in Z without leaving the feasible region and that all basic variables are nonnegative (smallest positive ratio) Gaussian elimination so that the new basic var. only has: 0,1 Test optimality: all coeff. in R0 >=0? If not, test new combination Find which half-plane satisfies the inequality Intercept all the half-plane areas to find the feasible region (FR) feasible solutions = (x1, x2) corners Draw iso-lines for the objective function to find the optimal solution: (x1, x2) corner point of the FR

  45. Simplex Method Particular cases

  46. Simplex Method Particular cases Tie for the Entering BV: Entering variable: Choose the entering variable (in a max problem) to be the NBV with the most negative coefficient in Row 0. What to do when there is a tie for the entering basic variable ? Selection made arbitrarily. coefficients of: Row basic var. Z 1 0 0 0 x1 -3 1 0 3 x2 -3 0 2 2 S1 0 1 0 0 S2 0 0 1 0 S3 0 0 0 1 right side R0 R1 R2 R3 Z 0 4 S1 S2 S3 12 18

  47. Simplex Method Particular cases Tie for the Leaving BV - Degenerate: Leaving BV: apply minimum ratio test - identify the row with the smallest positive ratio bi /aij (the most restrictive Row); the BV for this row is the leaving BV (it becomes nonbasic). - Choose the leaving variable arbitrary coefficients of: right side Row basic var. Z 1 0 0 0 0 1 0 0 0 0 x1 -3 1 2 1 0 -3 1 2 1 0 x2 -4 1 3 0 1 0 0 0 0 1 S1 0 1 0 0 0 0 1 0 0 0 S2 0 0 1 0 0 0 0 1 0 0 S3 0 0 0 1 0 0 0 0 1 0 S4 0 0 0 0 1 4 -1 -3 0 1 R0 R1 R2 R3 R4 R0 R1 R2 R3 R4 Z 0 10 18 8 6 24 4 0 8 6 S1 S2 S3 S4 Z S1 S2 S3 X2 10 / 1 = 10 18 / 3 = 6 - 6 / 1 = 6 - basic variables with a value of zero are called degenerate - continue the Simplex procedure until optimality is reached

  48. Simplex Method Particular cases No leaving BV Unbounded Z: Occurs if all the coefficients in the pivot column (where the entering basic variable is) are either negative or zero (excluding row 0) No solution when the constraints do not prevent improving the objective function indefinitely coefficients of: Row basic var. Z 1 0 0 0 x1 0 1 0 0 x2 -1 0 -3 -1 S1 1 1 -1 -1 S2 0 0 1 0 S3 0 0 0 1 right side R0 R1 R2 R3 Z 10 10 5 10 x1 S2 S3 - 5 / -3 10/ -1 < 0 < 0

  49. Simplex Method Particular cases Multiple optimal solutions: When a NBV has a zero coefficient in row 0, then we perform one more iteration to identify the other optimal BF solution. coefficients of: Row basic var. Z 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 x1 -3 1 0 3 0 1 0 0 0 1 0 0 0 1 0 0 x2 -2 0 2 2 -2 0 2 2 0 0 0 1 0 0 0 1 S1 0 1 0 0 3 1 0 -3 0 1 3 -1.5 0 0 1 0 S2 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0.33 1 S3 0 0 0 1 0 0 0 1 1 0 -1 0.5 1 0 -0.33 0 right side R0 R1 R2 R3 R0 R1 R2 R3 R0 R1 R2 R3 R0 R1 R2 R3 Z 0 4 X1 S2 S3 Z X1 S2 S3 Z X1 S2 X2 Z X1 S1 X2 12 18 12 4 12 6 18 4 6 3 18 2 2 6 - 12 / 2 = 6 6 / 2 = 3 4 / 1 = 4 6 / 3 = 2 -

  50. Simplex Method Other cases To be continued

Related


Converting Left Linear Grammar to Right Linear Grammar

Converting Left Linear Grammar to Right Linear Grammar

maub
Decision Analysis and Operations Research in Management

Decision Analysis and Operations Research in Management

senara
Understanding Linear Reservoir Baseflow Method

Understanding Linear Reservoir Baseflow Method

alanis
Understanding Linear Programming: An Introduction to Optimization

Understanding Linear Programming: An Introduction to Optimization

thomasin
Formulation of Linear Programming Problems in Decision Making

Formulation of Linear Programming Problems in Decision Making

nixon
Linear Programming: A Tool for Optimizing Business Operations

Linear Programming: A Tool for Optimizing Business Operations

kaydence
A Faster Algorithm for Linear Programming and the Maximum Flow Problem

A Faster Algorithm for Linear Programming and the Maximum Flow Problem

yuria
Linear Programming Models for Product-Mix Problems and LP Problem Solutions

Linear Programming Models for Product-Mix Problems and LP Problem Solutions

aodh
Understanding Linear Discrimination for Classification

Understanding Linear Discrimination for Classification

harlan
Automatic Optimization of Basis Set Parameters for Enhanced Quality

Automatic Optimization of Basis Set Parameters for Enhanced Quality

ftim
Linear Programming - Graphical Method in Operations Research

Linear Programming - Graphical Method in Operations Research

alonzo
Linear Programming for Recreational Site Planning

Linear Programming for Recreational Site Planning

gjak
Understanding Linear Transformations and Matrices in Mathematics

Understanding Linear Transformations and Matrices in Mathematics

adalwolf
Understanding Linear Dependent and Independent Vectors

Understanding Linear Dependent and Independent Vectors

cpurd
Understanding Linear Optimization in MS&E 214

Understanding Linear Optimization in MS&E 214

dseng
Gate Scheduling at Airports: Optimization and Solutions

Gate Scheduling at Airports: Optimization and Solutions

cid_452
Understanding Gaussian Elimination and Homogeneous Linear Systems

Understanding Gaussian Elimination and Homogeneous Linear Systems

ha_bey
Understanding OSeMOSYS: Energy System Modelling and Linear Programming

Understanding OSeMOSYS: Energy System Modelling and Linear Programming

rchan
Understanding Linear Functions in Mathematics

Understanding Linear Functions in Mathematics

tav_k
Linear Programming Models for Fertilizer Production, Metal Stamping, and Coffee Blending

Linear Programming Models for Fertilizer Production, Metal Stamping, and Coffee Blending

zaeem_s
Sensitivity Analysis and Duality in Linear Programming

Sensitivity Analysis and Duality in Linear Programming

fin_tie
Linear Programming Applications in Production and Marketing

Linear Programming Applications in Production and Marketing

delman_d
Comprehensive Overview of Numerical Linear Algebra Methods for Solving Linear Systems

Comprehensive Overview of Numerical Linear Algebra Methods for Solving Linear Systems

esperanza
Adapting Linear Hashing for Flash Memory Constrained Embedded Devices

Adapting Linear Hashing for Flash Memory Constrained Embedded Devices

quaranta_k

More Related Content