Explanation of Simplex Method
The Simplex method is an approach to solving linear programming models by hand using slack variables, tableaus,
and pivot variables as a means to finding the optimal solution of an optimization problem. A linear program is a
method of achieving the best outcome given a maximum or minimum equation with linear constraints. Most linear
programs can be solved using an online solver such as MatLab, but the Simplex method is a technique for solving
linear programs by hand. To solve a linear programming model using the Simplex method the following steps are
necessary:
Standard form Introducing slack variables Creating the tableau Pivot variables Creating a new tableau
Checking for optimality Identify optimal values
This document breaks down the Simplex method into the above steps and follows the example linear programming
model shown below throughout the entire document to find the optimal solution.
Conclusion
The Simplex method is an approach for determining the optimal value of a linear program by hand. The method
produces an optimal solution to satisfy the given constraints and produce a maximum zeta value. To use the
Simplex method, a given linear programming model needs to be in standard form, where slack variables can then be
introduced. Using the tableau and pivot variables, an optimal solution can be reached. From the example worked
throughout this document, it can be determined that the optimal objective value is 64 and can be found when x 1=8,
x2=0, and x3=0.
Powell's method, strictly Powell's conjugate direction method, is an algorithm proposed by Michael J. D. Powell for finding
a local minimum of a function. The function need not be differentiable, and no derivatives are taken.
The function must be a real-valued function of a fixed number of real-valued inputs. The caller passes in the initial point. The
caller also passes in a set of initial search vectors. Typically N search vectors (say ) are passed in which are simply the
normals aligned to each axis.[1]
The method minimises the function by a bi-directional search along each search vector, in turn. The bi-directional line search
along each search vector can be done by Golden-section search or Brent's method. Let the minima found during each bi-
directional line search be , where is the initial starting point and is the scalar determined during bi-
directional search along . The new position ( ) can then be expressed as a linear combination of the search
vectors i.e. . The new displacement vector ( ) becomes a new search vector, and is added to the end of the
search vector list. Meanwhile, the search vector which contributed most to the new direction, i.e. the one which was most
successful ( ), is deleted from the search vector list. The new set of N search vectors is . The algorithm
iterates an arbitrary number of times until no significant improvement is made. [1]
The method is useful for calculating the local minimum of a continuous but complex function, especially one without an
underlying mathematical definition, because it is not necessary to take derivatives. The basic algorithm is simple; the complexity
is in the linear searches along the search vectors, which can be achieved via Brent's method.