Category Archives: simplex algorithm

Observations on effect of initial parameter of Nelder-Mead to solve linear problem

Out of curiosity a test program is created to iterate the initial parameters for the Nelder-Mead program in TI Nspire to see if there is any effects or patterns to the outcome of the algorithm. The Nelder-Mead program is to solve the following inequalities:

nmsimplexparmest1

The test case will iterate test variables x and y from 1 to 10, resulting in 100 tests. Absolute error value of the Nelder-Mead program result to the known optimal value (33) is plotted in the below chart.

nmsimplexparmest2

nmsimplexparmest3

Advertisements

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

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

TI-84 Plus Pocket SE and the Simplex Algorithm

The TI-84+ Pocket SE is the little brother of the TI-84 Plus. They are almost identical in terms of screen resolution, processor architecture and speed, and also the OS. The Pocket version measured only 160 x 80 x 21mm in dimension and weighted at 142g, considerably more compact than the classic version.

TI84+PSE1

This little critter is full of features from the 2.55 MP OS. It will easily blow away the mainstream Casio series of the same size like the fx991 and even fx5800P with TI’s built-in advanced functions like ANOVA. Nevertheless, the TI-84 Plus series is still considered a stripped down version of the TI Nspire and TI-89 Titanium, and as such personally I do not expect or intent to run on it sophisticated calculations or programs like the Nelder-Mead algorithm that fits comfortably on the Nspire or Titanium.

Having said that, many complex calculation can easily be accomplished with the rich set of advanced features available out-of-the box in the TI-84, even without programming. One such example is the linear programming method implemented in the simplex algorithm for optimization. Consider the following example: In order to maximize profit, number of products to be produced given a set of constraints can be determined by linear programming. This set of constraints can be expressed in linear programming as system of equations as

8x + 7y ≤ 4400   :Raw Material P
2x + 7y ≤ 3200   :Raw Material Q
3x + y ≤ 1400    :Raw Material R
x,y ≥ 0

In the above, two products are considered by variable x and y, representing the constraints for product A and B respectively. Each of the first three equations denote the raw material requirements to manufacture each product, for material P, Q, and R. Specifically, product A requires 8 units of raw material P, 2 units of raw material Q, and 3 units of raw material R. The total available units for these three raw materials in a production run are 4400, 3200, and 1400 units respectively. When using the Simple Algorithm to maximize the function

P = 16x + 20y

which represents the profits for product A and B are $16 and $20 each, the tableau below is set up initially with slack variables set as

  8   7 1 0 0 0 4400
  2   7 0 1 0 0 3300
  3   1 0 0 1 0 1400
-16 -20 0 0 0 1    0

TI84+PSE3

Using the *row() and *row+() matrix function, the Simplex Algorithm can be implemented without even one line of code. The final answer is obtained as 11200 which is the maximum profit by producing 200 Product A and 400 Product B.

TI84+PSE4