The first step in solving a linear programming model manually with the simplex method is to convert the model into standard form. At the Beaver Creek Pottery Company Native American artisans produce bowls ( x
We convert this model into standard form by adding slack variables to each constraint as follows .
The slack variables, s
and
Slack variables are added to constraints and represent unused resources. In other words, when we start the problem and nothing is being produced, all the resources are unused. Since unused resources contribute nothing to profit, the profit is zero.
It is at this point that we begin to apply the simplex method. The model is in the required form, with the inequality constraints converted to equations for solution with the simplex method. ## The Solution of Simultaneous EquationsOnce both model constraints have been transformed into equations, the equations should be solved simultaneously to determine the values of the variables at every possible solution point. However, notice that our example problem has two equations and four unknowns (i.e., two decision variables and two slack variables), a situation that makes direct simultaneous solution impossible . The simplex method alleviates this problem by assigning some of the variables a value of zero. The number of variables assigned values of zero is n m , where n equals the number of variables and m equals the number of constraints (excluding the nonnegativity constraints). For this model, n = 4 variables and m = 2 constraints; therefore, two of the variables are assigned a value of zero (i.e., 4 2 = 2). For example, letting x
and
First, solve for x
Then, solve for s
This solution corresponds with point A in Figure A-1. The graph in Figure A-1 shows that at point A , x ## Figure A-1. Solutions at points A , B , and C
A basic feasible solution satisfies the model constraints and has the same number of variables with non-negative values as there are constraints. Consider a second example where x
and
Solve for x
Then solve for s
This basic feasible solution corresponds to point C in Figure A-1, where x Finally, consider an example where s
and
These equations can be solved using 4 x and then subtract the second equation:
Next, substitute this value of x
Row operations are used to solve simultaneous equations where equations are multiplied by constants and added or subtracted from each other. This solution corresponds to point B on the graph, where x All three of these example solutions meet our definition of basic feasible solutions . However, two specific questions are raised by the identification of these solutions. -
In each example, how was it known which variables to set equal to zero? -
How is the optimal solution identified?
The answers to both of these questions can be found by using the simplex method. The simplex method is a set of mathematical steps that determines at each step which variables should equal zero and when an optimal solution has been reached. |

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