Matthew WeltmannMrs. LykosH Pre- Calculus2 March 2017The Graphical and Tableau Procedures for the Simplex MethodHistoryAlthough Fourier in 1824, de la Vallée Poussin in 1911, Kantorovich in 1939, and Hitchcock in 1941 all published papers on special cases of linear programming, these papers stimulated little interest in the world of mathematics. It wasn’t until World War II, while George B. Dantzig worked to synthesize planning methods for the US Army Air Force using only a desk calculator, that work on what came to be known as the Simplex Method was truly underway.
Enticed by his colleague to mechanize the process of planning methodology for the Air Force, Danzig began a yearlong quest that would eventually lead to his fabrication of the simplex method as a way to solve standard maximization problems. While he first formulated this method without the use of an objective, by mid-1947, the mathematics behind Dantzig’s work was more coherent; he went on to write a thesis on this method in order to earn his doctorate. Since then, especially in recent years, Danzig’s simplex method has gained world renown both as a tool for solving standard maximization problems as well as an underlying method on which linear programming of computers can be based. The simplex method is both efficient, taking few iterations to solve, and eloquent, serving the specific proposes of various problems without strife. IntroductionThe simplex method is, by definition, “a standardized method of maximizing a linear function of several variables under several constraints on other linear functions”.
What this means is that the simplex method is a procedure that may be used to find the best possible solution to an objective function given constraints. This is useful in the field of linear programming as it involves solving what is known as a standard maximization problem. In this paper, two ways of utilizing the simplex method will be analyzed: the graphical procedure for the simplex method and the tableau procedure for the simplex method. Both of these procedures follow the same rules and requirements- the only difference is that one requires a graph and is a more logical way of looking at a standard maximization problem, while the other is a more mathematical way of looking at a standard maximization problem. These procedures will be used to solve the same objective function with the same given constraints in order to aid understanding of the topic and its merits and as an efficient and eloquent way with which to approach linear programming. There is a glossary at the end of this paper in which bolded words may be looked up for clarity of definition. Graphical Procedure for the Simplex Method 1.
Change the inequalities to equalities and add a slack variable (s1…sn). These variables will be added to all ? constraints to “take up the slack” and subtracted from all ? constraints to remove the surplus. Use subscripts that correspond to the constraint number for the slack variable. 2.
Create a unique identification of each line by setting one variable, slack or otherwise, equal to 0.×1 + 2×2 = 16 can be written as s1=0x1 + x2 = 9 can be written as s2=0 3×1 + 2×2 = 24 can be written as s3=0 x1 =0 can be written as x1=0 x2 =0 can be written as x2=0 3. Create graphs depicting the feasible region. This is where all the coordinatessatisfy all of the constraints. 4. Since each line can now be identified as a non-basic variable (variable equal to 0), each point of intersection can now be identified by two non-basic variables in the form of an ordered pair.
This means that a chart may be fabricated that lists all the combinations of variables when two of them are equal to 0 at a given time. The two variables in the chart that are equal to 0 at the point of intersection are non-basic, while all the other non-zero variables are termed basic variables. Pt x1 x2 s1 s2 s3 A 0 0 B 0 0 C 0 0 D 0 0 E 0 0 F 0 0 G 0 0 H 0 0 I 0 0 J 0 0 5.
Produce the rest of the numbers in the table by solving systems of equations using the known variables. Point A: x1 = 0, x2 = 0 Therefore, at point A, s1=16, s2=9, and s3=24Point B: x1 = 0, s1 = 0 Find equations that include the variables x1 and s1 and then plug in to solve for values Therefore, at point B: x2 = 8, s2 = 1, and s3 = 16Eventually, upon solving for all of the unknown values, the table from Figure #3 can be reconstructed as the following. Pt x1 x2 s1 s2 s3 A 0 0 16 9 24 B 0 8 0 1 16 C 0 9 -2 0 6 D 0 12 -8 -3 0 E 16 0 0 -7 -24 F 9 0 7 0 -3 G 8 0 8 1 0 H 2 7 0 0 15 I 4 6 0 -1 0 J 6 3 4 0 0 6. Determine which points are feasible by eliminating any point that does not satisfy the constraints. Graphically, this can be deduced using the knowledge that any feasible point must be touching the shaded region. Pt x1 x2 s1 s2 s3 Feasible? A 0 0 16 9 24 Yes B 0 8 0 1 16 Yes C 0 9 -2 0 6 No D 0 12 -8 -3 0 No E 16 0 0 -7 -24 No F 9 0 7 0 -3 No G 8 0 8 1 0 Yes H 2 7 0 0 15 Yes I 4 6 0 -1 0 No J 6 3 4 0 0 Yes Note: since one of the restrictions in the problem was that all variables must be positive, all points with negative variables are not feasible.7.
Calculate the value of the objective function for each feasible point in order to maximize the function! Pt x1 x2 s1 s2 s3 Feasible? P= 40×1 + 30×2 A 0 0 16 9 24 Yes 0 B 0 8 0 1 16 Yes 240 C 0 9 -2 0 6 No N/A D 0 12 -8 -3 0 No N/A E 16 0 0 -7 -24 No N/A F 9 0 7 0 -3 No N/A G 8 0 8 1 0 Yes 320 H 2 7 0 0 15 Yes 290 I 4 6 0 -1 0 No N/A J 6 3 4 0 0 Yes 330 The largest value of the objective function (the optimal and maximized value) is P= 330 when x1=6 and x2=3. Tableau Procedure for the Simplex Method While the graphical procedure for solving a linear programming problem is effective, it often tends to be time consuming. For this reason, the tableau procedure for solving a linear programming problem will now be explained and exemplified using the same maximization problem as before.
Note that a tableau is essentially a matrix.1. Introduce a slack variable to the standard maximization problem in order to convert the inequality constraints into equality constraints. 2. Alter the form of the objective function such that all the terms involving variables are negative and that the equations is set equal to 0. + P = 03. Create a tableau using the system of equations that is the constraints with the revised objective function on the bottom row separated by an augmentation line. 4.
Identify the basic variables in each row of the tableau by 1) finding all of the columns that have only one non-zero element 2) recognizing the row each isolated non-zero element belongs in and 3) labeling the row that contains a basic variable with that basic variable. For example, since the s1 column has only one non-zero element that lies in row 1, row 1 can be labeled s1. Now that the feasible region has been depicted, it must be decided in which direction the mathematician should “move”. The origin of x1= 0 and x2 =0 is where the problem begins, but in order to maximize the objective function, it is now necessary to explore the other points of intersection in which s1, s2, and s3 =0. Imagine the objective function P= 40×1 + 30×2 as though each movement in the x1 direction will increase the value of the function be 40 and each movement in the x2 direction will increase the value of the function by 30.
Furthermore, imagine this scenario as a real life example: let it be said that each movement in the x1 direction will increase the profit of some venture by $40 and each movement in the x2 direction will increase the profit of that same venture by $30, all still subject to the constraints that could be based on materials available, work hours available, rent, etc. 5. Select the pivot column by finding the most negative indicator (element in the bottom row) and using the column corresponding to that indicator as the pivot column. The reason a negative indicator is being chosen is because a negative indicator would correspond to a positive value in the objective function, leading to the increase in the value of the objective function. The most negative of all the indicators is chosen in order to begin maximization at the highest rate. 6. Select the pivot row by dividing the last column by the pivot column for each corresponding entry except the bottom entry and negative entries. Then choose the smallest positive result (the row of this result will be the pivot row).
If there is no positive element, then there will be no optimal solutions!7. Find the pivot element at the intersection of the pivot row and pivot column. Note that the variable that is basic for the pivot row will be exiting the set of basics and will be replaced by the variable from the pivot column, which will be entering the set of basics. Known information prior to pivoting:· The objective function is currently P= 320 because it increases by 40 per added x1 value and 8 x1 values were added (40 × 8 = 320)· The x1 variable will replace the s1 variable in the set of basic variables, while all other basic variables will remain the same· The pivot row will be divided by a number such that the pivot element is 1· The pivot column will be cleared except for the pivot element· The increase in x1 will be 8· Graphically, the values of the variables observed are at point G, where x2 and s3 are non-basic· The s1, s2, and P rows will be cleared, with only their basic elements remaining the same8.
Pivot by using row operations to clear the pivot column such that the only remaining entry in the pivot row will be the pivot element (it was already known that the pivot column would be cleared, but performing the row operations will elucidate the other elements of the tableau). 9. Interpret the tableau by reading across the rows. Basic Non- Basic s1=8, x1 = 8, s2=1, P = 320 x2 = 0, s3 = 0 As can be deduced, these values are the same as those found at point G in Figure #6. This provides evidence that the graphical and tableau simplex methods are linked. 10.
Repeat steps 5-9 using the next most negative indicator in the bottom row. Since there is only one negative value left (-10/3), which lies in the x2 column, the value of the objective function may be increased by moving along the x2 line. This means that a mathematician may move off of the x2=0 line and onto the s3=0 line, thus making x2 a basic variable and s3 a non-basic variable. Known information prior to pivoting:· The objective function will increase by 10 since it increases by 10/3 for every movement in the x2 direction and there will be a movement of 3 unites in ths direction· The x2 variable will replace the s2 variable in the set of basic variables, while all other basic variables will remain the same· The pivot row will be divided by a number such that the pivot element is 1· The pivot column will be cleared except for the pivot element· The increase in x2 will be 3· Graphically, the values of the variables observed are at point J, where s2 and s3 are non-basic· The s1, x1, and P rows will be cleared, with only their basic elements remaining the same Basic Non- Basic x1=6, x2 = 3, s1=4, P = 330 s2 = 0, s3 = 0 This linear programming problem has now been completed! Since there are no negative indicators left, moving to another point on the graph would lower the value of the objective function, not higher it! The final answer for the maximization problem would be at location x1=6, x2 = 3, s1=4, where the value of the function is equal to 330.
Real Life ApplicationsThe simplex method as it has been here shown to solve standard maximization problems may be used in a multitude of scenarios. For example, this method can be used simply to determine the amount of each pastry a baker should make given constraints on his supply of eggs, flour, and milk. However, in a similar (yet more widely used) example, the simplex method can also be used to determine from which sources an oil refinery should buy crude oil. With differing prices of crude oil from each location and varying quantities of aviation fuel, gasoline, and diesel fuel in each batch of oil, it is necessary to consider these variables. Furthermore the simplex method allows for the incorporation of other variables such as the quantity of crude oil available at each source and the capability of the refinery to produce a certain product from the crude oil. In addition to these relatively rudimentary instances, the simplex method may also be used in extremely complex robotic programming. With the rise of artificial intelligence and robots that can make decisions on their won, the simplex method has become the basis for a plethora of computer algorithms for robot motion. The simplex method allows robots to decide, for example, which path to traverse in pursuit of a goal with uneven terrain in the way of its objective.
By considering constraints such as battery level, heat level, and safety (in military situations), the robot may use the simplex method to maximize its energy efficiency and minimize its danger while following its path. It is important to note that danger levels would be ranked from 1-10, 10 being the safest, so that this value could be maximized in the problem while under the given constraints. Conclusion and What I LearnedAlthough the simplex method was finalized 70 years ago, it continues to maintain importance in the world of mathematics today.
George B. Dantzig’s method of linear programming was decades ahead of its time in that it has come to be a part of fields that Danzig probably thought would never exist: computer science and robotic programming. In this paper, the simplex method has been solved in both it’s graphical and tableau form and its eloquence, efficacy, and necessity has ben proven. From completing this project on the simplex method, I have learned much more about the concept that is linear programming. Upon choosing this topic as the object of my mathematical exploration, the idea of learning anything about linear programming and solving what was called a “standard maximization problem” on the university websites I combed seemed daunting. However, researching for this project has honed my skills of graphical analysis as well as added to my previously nonexistent knowledge on the topic of tableaus. Furthermore, in studying the simplex method and writing this paper, my research capabilities as well as my ability to follow intricate mathematical procedures have been augmented.
GlossaryStandard Maximization Problem- a sort of linear programming problem in which the objective function is to be maximized Objective Function- the focus function in any linear programming problem that is set to be either maximized or minimizedSlack Variables- variables added to inequality constraints that make them into equality constraints Basic Variables- variables that are equal to any value other than zero and have a great amount of importanceNon-basic Variables- variables that are equal to zero and have relatively little importance Works Cited”The Simplex Method.” The Simplex Method, www.utdallas.edu/~scniu/OPRE-6201/documents/LP4-Simplex.html.”Linear Programming: Simplex Method.
” Linear Programming: Simplex Method, people.richland.edu/james/ictcm/2006/simplex.html.
“Linear Programming: Table Approach.” Linear Programming: Table Approach, people.richland.
edu/james/ictcm/2006/table.html.” Simplex Method.” Simplex Method – Definition, Dual Simplex Method & Steps | MathCaptain.Com, www.mathcaptain.
com/algebra/simplex-method.html.Merz, Thomas. “The Simplex Method.” University of North Caroline, 1998, pp. 176–186.
, doi:10.1007/978-3-642-72032-1_9.”Guidline to Simplex Method.
” Washington State University, 2017, doi:10.18411/a-2017-023.”What is a standard maximization problem?” Pblpathways.com, pblpathways.com/fm/C4_3_1.pdf.
