Tag Archives: simplex algorithm

Solving linear programming problem with Nelder-Mead method

For solving linear programming problem, the simplex method is often applied to search for solution. On the other hand, the Nelder-Mead method is mostly applied as a non-linear searching technique. It would be interesting to see how well it is applied to a linear programming problem previously solved using the Simple Method in TI-84.

The Nelder-Mead method is ran under the TI Nspire CX CAS with NM program written in the TI Basic program. The program accepts arguments including the name of the function to maximize as a string and a list of initial parameters to execute the Nelder-Mead algorithm. The function itself is declared using piece-wise function to bound the return value to the function to maximize while giving penalty to values that violate any constraints (as in the inequalities of the standard simplex method).

Previous program in the TI-84 using the simplex method obtained {200,400} as the solution. The Nelder-Mead returned a solution very close to it.

nmsimplex

Advertisements

TI Nspire CX program to generate initial tableau for Simplex Algorithm

The simplex algorithm can be easily performed in TI Nspire CX and also in the TI-84 series. A program is created to provide an intuitive means to construct the initial tableau.

The function prototype takes two arguments, one for a list of expression consisting the constraint inequalities plus the function to maximize (assumed to be the last in the list), and another argument to specify the number of variables. The variables in the inequalities must be named as x[n] where n is a number starting from one.

simplextableau2

Example of the usage of this program showing how the inequalities are set up.simplextableau1a

The program makes use of some string functions, the expr and polyCoeffs functions and also indirection to extract the coefficients in the inequalities and to build the initial tableau matrix.
simplextableau3

simplextableau4

Graphical representation of the example above.
simplexgraphsln1

Simplex Algorithm on the Casio 9860GII

With matrix capable calculator, simplex algorithm for common maximization problem can be solved easily like in the TI-84.

The Casio 9860GII is also equipped with equivalent matrix operations to solve the same problem.

casiosimplex1

casiosimplex2

casiosimplex4

casiosimplex3