Optimization Modeling with Spreadsheets, 3rd Edition

Appendix 3THE SIMPLEX METHOD

The simplex method is the algorithm most frequently used in computer programs for solving linear programming problems. The linear solver in Microsoft^® Office Excel^® is an implementation of the simplex method, and the simplex method constitutes part of virtually every successful commercial software package for optimization. In this appendix, we use an example to illustrate the simplex method, and we comment on how the algorithm can be adapted to special situations that arise.

A3.1 AN EXAMPLE

We use a variation of Example 2.1 to illustrate how the simplex method works. For this purpose, we drop the wood constraint and address the following optimization problem:

The simplex method works not with inequalities but rather with equalities, so our first step is to recast the constraints of the model as equations. To do so, we introduce three additional variables that account for unused amounts of the three resources. In other words, these variables represent the difference between the right-hand side (RHS) and left-hand side (LHS) of the constraints, as they are posed above. The constraints may be written as follows:

(A3.1)

(A3.2)

(A3.3)

The variables ...