In the previous section the simplex method for solving linear programming problems was demonstrated for a maximization problem. In general, the steps of the simplex method outlined at the end of this section are used for any type of linear programming problem. However, a minimization problem requires a few changes in the normal simplex process, which we will discuss in this section. In addition, several exceptions to the typical linear programming problem will be presented later in this module. These include problems with mixed constraints (=, , and ); problems with more than one optimal solution, no feasible solution, or an unbounded solution; problems with a tie for the pivot column; problems with a tie for the pivot row; and problems with constraints with negative quantity values. None of these kinds of problems require changes in the simplex method. They are basically unusual results in individual simplex tableaus that the reader should know how to interpret and work with. ## Standard Form of a Minimization ModelConsider the following linear programming model for a farmer purchasing fertilizer.
where x x Z = farmer's total cost ($) of purchasing fertilizer This model is transformed into standard form by subtracting surplus variables from the two constraints as follows .
The surplus variables represent the extra amount of nitrogen and phosphate that exceeded the minimum requirements specified in the constraints. However, the simplex method requires that the initial basic feasible solution be at the origin, where x
The idea of"negative excess pounds of nitrogen" is illogical and violates the nonnegativityrestriction of linear programming. The reason the surplus variable does not work is shown in Figure A-4. The solution at the origin is outside the feasible solution space. ## Figure A-4. Graph of the fertilizer example
Transforming a model into standard form by subtracting surplus variables will not work in the simplex method. To alleviate this difficulty and get a solution at the origin, we add an artificial variable ( A 2 x An artificial variable allows for an initial basic feasible solution at the origin, but it has no real meaning. The artificial variable, A
The artificial variable is somewhat analogous to a booster rocket its purpose is to get us off the ground; but once we get started, it has no real use and thus is discarded. The artificial solution helps get the simplex process started, but we do not want it to end up in the optimal solution, because it has no real meaning. When a surplus variable is subtracted and an artificial variable is added, the phosphate constraint becomes 4 x The effect of surplus and artificial variables on the objective function must now be considered . Like a slack variable, a surplus variable has no effect on the objective function in terms of increasing or decreasing cost. For example, a surplus of 24 pounds of nitrogen does not contribute to the cost of the objective function, because the cost is determined solely by the number of bags of fertilizer purchased (i.e., the values of x By assigning a "cost" of $0 to each surplus variable, we are not prohibiting it from being in the final optimal solution. It would be quite realistic to have a final solution that showed some surplus nitrogen or phosphate. Likewise, assigning a cost of $0 to an artificial variable in the objective function would not prohibit it from being in the final optimal solution. However, if the artificial variable appeared in the solution, it would render the final solution meaningless. Therefore, we must ensure that an artificial variable is not in the final solution. As previously noted, the presence of a particular variable in the final solution is based on its relative profit or cost. For example, if a bag of Super-gro costs $600 instead of $6 and Crop-quick stayed at $3, it is doubtful that the farmer would purchase Super-gro (i.e., x minimize Z = 6 x The completely transformed minimization model can now be summarized as
Artificial variables are assigned a large cost in the objective function to eliminate them from the final solution. ## The Simplex Tableau for a Minimization Problem The initial simplex tableau for a minimization model is developed the same way as one for a maximization model, except for one small difference. Rather than computing c The c The initial simplex tableau for this model is shown in Table A-17. Notice that A ## Table A-17. The Initial Simplex Tableau
Artificial variables are always included as part of the initial basic feasible solution when they exist. In Table A-17 the x Once an artificial variable is selected as the leaving variable, it will never reenter the tableau, so it can be eliminated. The second simplex tableau is developed using the simplex formulas presented earlier. It is shown in Table A-18. Notice that the A ## Table A-18. The Second Simplex Tableau
The third simplex tableau, with x ## Table A-19. The Third Simplex Tableau
The fourth simplex tableau, with s x s x s Z = $24, total cost of purchasing fertilizer ## Table A-20. Optimal Simplex Tableau
## Simplex Adjustments for a Minimization ProblemTo summarize, the adjustments necessary to apply the simplex method to a minimization problem are as follows: -
Transform all constraints to equations by subtracting a surplus variable and adding an artificial variable. -
Change the c _{ j }z_{ j }row to z_{ j }c_{ j }.
Although the fertilizer example model we just used included only constraints, it is possible for a minimization problem to have and = constraints in addition to constraints. Similarly, it is possible for a maximization problem to have and = constraints in addition to constraints. Problems that contain a combination of different types of inequality constraints are referred to as |

Introduction to Management Science (10th Edition)

ISBN: 0136064361

EAN: 2147483647

EAN: 2147483647

Year: 2006

Pages: 358

Pages: 358

Authors: Bernard W. Taylor

Similar book on Amazon

flylib.com © 2008-2017.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net