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

2024
Views:

96

Pages:

22
Author:

sinead3ms

SOLVING LINEAR PROGRAMMING PROBLEMS: The Simplex Method Part 1 Simplex Method • Used for solving LP problems will be presented • Put into the form of a table, and then a number of mathematical steps are performed on the table • Moves from one extreme point on the solution boundary to another until the best one is found, and then it stops • A lengthy and tedious process but computer software programs are now used easily instead • Programs do not provide an in-depth understanding of how those solutions are derived • Can greatly enhance one's understanding of LP First Step • First step is to convert model into standard form • s1 and s2, represent amount of unused labor and wood • No chairs and tables are produced, s1=40 and s2=120 • Unused resources contribute nothing to profit, Z=0 • Decision variables as well as profit at origin are: Assigning (n-m) Variables Equal to Zero • Determine values of variables at every possible solution point • Have two equations and four unknowns, which makes direct simultaneous solution impossible • Assigns n-m variables=0 – n=number of variables – m=number of constraints • Have n = 4 variables and m = 2 constraints • x1 = 0 and s1 = 0 and substituting them results in x2 = 20 and s2=60 Feasible and Basic Feasible Solution • Solution corresponds to A • Referred to as a basic feasible solution • Feasible solution is any solution that satisfies the constraints • Basic feasible solution not only satisfies the constraints but also contains as many variables with nonnegative values as there are model constraints – m variables with nonnegative values and n-m values equal to zero A X1=0 chairs S1=0 X2=20 tables S2=60 B C Feasible and Basic Feasible Solution • x2=0 and s2=0, results in x1=30 and s1=10 • Corresponds to point C • s1=0 and s2=0, results in two equations with two unknown variables • Get a solution which corresponds to point B, where x1=24, x2=8, s1=0, and s2= 0 • Previously identified as optimal solution point A B C X1=30 chairs S1=10 X2=0 tables S2=0 Two Questions • Two questions can be raised by the identification of solutions at points O, A, B, and C • How was it known which variables to set equal to zero? • How is the optimal solution identified? • Answers these questions by performing a set of mathematical steps • Determines at each step which variables should equal zero and when an optimal solution has been reached A X1=0 chairs S1=0 X2=20 tables S2=60 X1=24 chairs S1=0 X2=8 tables S2=0 B C X1=30 chairs S1=10 X2=0 tables S2=0 Initial Tableau • Model is put into the form of a table, or tableau • Our maximization model • Z = 40x1 + 50x2 + 0s1 + 0s2 Subject to x1 + 2x2+ s1 = 40 4x1 + 3x2 + s2 =120 x 1 , x 2 , s1 , s2 ≥ 0 • • • • Initial simplex tableau with various column and row headings Record the model decision variables, followed by the slack variables Bottom rows represent constraint equations whose right-hand sides are given in the “solution” column z-row is obtained from z -40x1-50x2=0 Basic Z x1 x2 s1 s2 Solution Z 1 -40 -50 0 0 0 s1 0 1 2 1 0 40 s2 0 4 3 0 1 120 Determining Basic Feasible Solution • Determine a basic feasible solution • Know which two variables will form the basic feasible solution and which will be assigned a value of zero? • Selects the origin as the initial basic feasible solution • x1= 0 and x2= 0; variables in basic feasible solution are s1 and s2 which are listed under column "Basic" and their values, 40 and 120, are listed under column “solution“ • Z=0 under column “solution” Basic Z x1 x2 s1 s2 Solution Z 1 -40 -50 0 0 0 s1 0 1 2 1 0 40 s2 0 4 3 0 1 120 Entering Variable • • • • • • • Interested in giving us either some chairs or some tables Want nonbasic variables will enter solution and become basic z-row values represent increase per unit of entering a nonbasic variable into the basic solution Make as much money as possible Select variable x2 as the entering basic variable – has the greatest increase in profit per unit, $50—the most negative value in the z-row x2 column is highlighted and is referred to as the pivot column Referred to in mathematical terminology as pivot operations Basic Z x1 x2 s1 s2 Solution Z 1 -40 -50 0 0 0 s1 0 1 2 1 0 40 s2 0 4 3 0 1 120 Entering Variable by Graphical Solution • Demonstrated by the graph • At the origin nothing is produced • Moves from one solution point to an adjacent point • Move along either the x1 axis or the x2 axis • Chooses x2 as the entering variable A X1=0 chairs X2=20 tables X1=24 chairs X2=8 tables B O X1=30 chairs X2=0 tables C Leaving Basic Variable • One of s1 or s2 has to leave and R become zero • Produce tables as many as possible • Check availability of our resources A • Using labor constraint, maximum we can produce table is 20 • Enough labor is available to produce 20 tables • Using wood, maximum we can produce is 40 • Limited to 20 tables • Point A is feasible, whereas point R is infeasible Wood constraint Labor constraint B C Leaving Variable • Determined by dividing RHS values by pivot column values Basic • • • • • • x 2 Solution Ratio S1 2 40 40/2=20 s2 3 120 120/3=40 Leaving basic variable is variable with minimum nonnegative ratio s1 is leaving variable s1 row is referred to as pivot row Value of 2 is called pivot number or pivot element Entering variable, x2, in the new solution also equals 20 Z also increases from 0 to 1000 Basic Z x1 x2 s1 s2 Solution Z 1 -40 -50 0 0 0 s1 0 1 2 1 0 40 s2 0 4 3 0 1 120 Second Tableau • Nonbasic and basic variables at solution point Nonbasic: x1 and s1 Basic: x2 and s2 • Various values are computed using pivot row and all other rows • First, x2 row, is computed by using every value in pivot row of first (old) tableau and divide it by pivot number, or (0/2 1/2 2/2 1/2 0/2 40/2) • New row values are shown in Table Basic Z x1 x2 s1 s2 Solution Z 1 -40 -50 0 0 0 x2 0 1/2 1 1/2 0 20 s2 0 4 3 0 1 120 0-(3)*0=0 4-(3)*1/2=-5/2 3-(3)*1=0 0-(3)*1/2=--3/2 1-(3)*0=1 120-(3)*20=60 Second Tableau-Cont. • For the remaining row values, use New row=(current row)-(its pivot column coefficient) x (New pivot row) • Requires use of both old tableau and new one • Various values for new zrow and s2-row: Z-row= current z-row – (-50)x new pivot row S2-row=current s2-row – (3)x new pivot row • Values are inserted in Table 1-(-50)*0=1 -40-(-50)*1/2=--15 -50-(-50)*1=0 0-(-50)*1/2=25 0-(-50)*0=0 0-(-50)*20=1000 Basic Z x1 x2 s1 s2 Solution Z 1 -15 0 25 0 1000 x2 0 1/2 1 1/2 0 20 s2 0 5/2 0 -3/2 1 60 Basic Z x1 x2 s1 s2 Solutio n Z 1 -40 -50 0 0 0 s1 0 1 2 1 0 40 s2 0 4 3 0 1 120 Checking Optimal Solution • • • • • • Set nonbasic variables x1 and s1 to zero, solution column provides new basic solution x2=20, s2=60 and z=1000 Is not optimal – x1 has a negative coefficient Select variable x1 as entering basic variable Ratio computations, show that s2 is the leaving variable Basic x1 Solution Ratio x2 1/2 20 20/0.5=40 s2 5/2 60 60/2.5=24 Steps are repeated to develop the third tableau Pivot row, pivot column, and pivot number are indicated in Table Basic Z x1 x2 s1 s2 Solution Z 1 -15 0 25 0 1000 x2 0 1/2 1 1/2 0 20 s2 0 5/2 0 -3/2 1 60 Third Tableau • New pivot row, x1, is computed using the same formula • All old pivot row values are divided by 5/2 • Values for z-row and s2-row are computed here and shown in Table Basic Z x1 x2 s1 s2 Solution Z 1 0 0 16 6 1360 x2 0 0 1 4/5 -1/5 8 x1 0 1 0 -3/5 2/5 24 Basic Z x1 x2 s1 s2 Solutio n Z 1 -15 0 25 0 1000 x2 0 1/2 1 1/2 0 20 s2 0 5/2 0 -3/2 1 60 Checking Optimal Solution • Coefficient of nonbasic variables are positive • Optimal solution has been reached • x1 = 24 chairs, x2= 8 tables and z= $1,360 profit – Corresponds to point B shown previously Basic Z x1 x2 s1 s2 Solution Z 1 0 0 16 6 1360 x2 0 0 1 4/5 -1/5 8 x1 0 1 0 -3/5 2/5 24 Summary of the Simplex 1. Transform constraint inequalities into equations 2. Set up the initial tableau 3. Determine the pivot column (entering nonbasic solution variable) 4. Determine the pivot row (leaving basic solution variable) 5. Compute the new pivot row values 6. Compute all other row values 7. Determine whether or not the new solution is optimal 1. If these coefficients are zero or positive, the solution is optimal 2. If a negative value exists, return to step 3 and repeat the simplex steps Simplex Tableaus by TORA • Used manually to solve relatively small problems • Can be so time-consuming and subject to error that manual computation • Computer solution has become so important • Many computer programs use the simplex method • Computer output includes option to display simplex tableaus • Simplex tableaus provided by TORA software Minimization Problem • Demonstrated simplex method for a maximization problem • A minimization problem requires a few changes • Recall the minimization model minimize Z = 6 x1 + 3 x2 subject to 2 x1 + 4 x2 ≥ 16 4 x1 + 3 x2 ≥ 24 x1 and x2 ≥ 0 • Transformed this model into standard form by subtracting surplus variables 2 x1 + 4 x2 – s1 = 16 4 x1 + 3 x2 – s2 = 24 Introducing Artificial Variable • • • • • • • • Simplex method requires initial basic solution at the origin Test this solution at origin Violates the non-negativity restriction Reason is shown in Figure Solution at origin is outside feasible solution space Add an artificial variable (R1) to the constraint equation Create an artificial positive solution at the origin Artificial solution helps get the simplex process started – • Not want it to end up in the optimal solution Our phosphate constraint becomes 2 x1 + 4 x2 – s1 + R1= 16 A Feasible area B C

Solving Linear Programming Problems: The Simplex Method, Part 1

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock