14-11-2012, 01:18 PM
The Simplex Method
The Simplex Method.pdf (Size: 118.2 KB / Downloads: 170)
In this chapter, you will learn how to solve linear programs. This will give you insights into
what SOLVER and other commercial linear programming software packages actually do. Such an
understanding can be useful in several ways. For example, you will be able to identify when a
problem has alternate optimal solutions (SOLVER never tells you this: it always give you only one
optimal solution). You will also learn about degeneracy in linear programming and how this could
lead to a very large number of iterations when trying to solve the problem.
SOLUTION OF LINEAR PROGRAMS BY THE SIMPLEX METHOD
Note that the equations are already in the form that we expect at the last step of the Gauss-
Jordan procedure. Namely, the equations are solved in terms of the nonbasic variables x1, x2.
The variables (other than the special variable z) which appear in only one equation are the basic
variables. Here the basic variables are x3 and x4. A basic solution is obtained from the system of
equations by setting the nonbasic variables to zero. Here this yields
ALTERNATE OPTIMAL SOLUTIONS, DEGENERACY, UNBOUDEDNESS, INFEASIBILITY95
If there is an optimal solution, there is a basic optimal solution. Remember that the number of
basic variables in a basic solution is equal to the number of constraints of the problem, say m. So,
even if the total number of variables, say n, is greater than m, at most m of these variables can
have a positive value in an optimal basic solution.
Exercise 63 The following tableaus were obtained in the course of solving linear programs with 2
nonnegative variables x1 and x2 and 2 inequality constraints (the objective function z is maximized).
Slack variables s1 and s2 were added. In each case, indicate whether the linear program