Mathematically speaking, in order to use the simplex method to solve a linear programming problem, we need the standard maximization problem. Although tempting, there are a few things we need to lookout for prior to using it. To handle linear programming problems that contain upwards of two variables, mathematicians developed what is now known as the simplex method. We can visualize in up to three dimensions, but even this can be difficult when there are numerous constraints. This, however, is not possible when there are multiple variables. Later when we read off the final solution from the simplex table, the values of the slack variables will identify the unused amounts.We found in the previous section that the graphical method of solving linear programming problems, while time-consuming, enables us to see solution regions and identify corner points. This is done by adding one slack variable for each inequality. She has determined that for every hour she works at Job I, she needs 2 hours of preparation time, and for every hour she works at Job II, she needs one hour of preparation time, and she cannot spend more than 16 hours for preparation. She never wants to work more than a total of 12 hours a week. Now, we use the simplex method to solve Example 3. This will provide us with some insight into the simplex method and at the same time give us the chance to compare a few of the feasible solutions we obtained previously by the graphical method.īut first, we list the algorithm for the simplex method. We start out with an example we solved in the last chapter by the graphical method. A thorough justification is beyond the scope of this course. We justify the reasoning behind each step during the process. We first list the algorithm, and then work a problem. To learn the simplex method, we try a rather unconventional approach. The process continues until the optimal solution is found. It does not compute the value of the objective function at every point instead, it begins with a corner point of the feasibility region where all the main variables are zero and then systematically moves from corner point to corner point, while improving the value of the objective function at each stage. The simplex method uses an approach that is very efficient. But the simplex method still works the best for most problems. Ina Soviet scientist named Leonid Khachian developed a method called the ellipsoid algorithm which was supposed to be revolutionary, but as it turned out it is not any better than the simplex method. His linear programming models helped the Allied forces with transportation and scheduling problems. The simplex method was developed during the Second World War by Dr. We have just such a method, and it is called the simplex method. The method has to be efficient enough so we wouldn't have to evaluate the objective function at each corner point. So we need a method that has a systematic algorithm and can be programmed for a computer. By choosing all combinations of five equations with five unknowns, we could find all the corner points, test them for feasibility, and come up with the solution, if it exists.īut the trouble is that even for a problem with so few variables, we will get more than corner points, and testing each point will be very tedious. Suppose we were given a problem with, say, 5 variables and 10 constraints. We can solve these problems algebraically, but that will not be very efficient. In real life situations, linear programming problems consist of literally thousands of variables and are solved by computers. In the last chapter, we used the geometrical method to solve linear programming problems, but the geometrical approach will not work for problems that have more than two variables. In this section, you will learn to solve linear programming maximization problems using the Simplex Method.