The Simplex algorithm: 

This algorithm solves a linear program -  set of linear equations. It takes a set of linear inequalities and a linear objective function and finds optimal feasible point by the following strategy. 

1. Find a vertex v in the feasible region 

2. While there’s a neighbor v’ of v with better objective value: set v = v’  

A linear equation involving the n dimensions defines a hyperplane when plotted in an n-dimensional space and the corresponding linear inequality defines a half-space, all  points that are precisely hyperplane or lie on one particular side of it. The feasible region of a linear program specified by a set of inequalities is the intersection of the corresponding half-spaces, a convex polyhedron.  

But what do the concepts of vertex and neighbor mean in this general context. Each vertex is the unique point at which some set of hyperplanes meet. 

Each vertex is specified by a set of n inequalities. 

Two vertices are neighbours if they have n-1 defining inequalities in common. 

On each iteration of the algorithm, the simplex has two tasks 

1. Check whether the current vertex is optimal 

2. Determine where to move next 

As we will see, both tasks are easy if the vertex happens to be at the origin. And if the vertex is elsewhere, we will transform the co-ordinate system to move it to the origin.  

When the origin is feasible, it is certainly a vertex, since it is the unique point at which the n inequalities are tight.  

The origin is optimal if and only if all ci <= 0 where ci is the contraint we try to maximize in each dimension 

If all ci <= 0, then considering  the constraints x >= 0, we can’t hope for a better objective value. Conversely if the origin is not optimal, we can improve one of the constraints. 

Thus for task 2 we can move by increasing some xi for which ci > 0. We can keep on increasing it until we hit another constraint. At that point we again have n tight inequalities and hence we arrive at a new vertex. 

For example, given the objective function max 2x1+5x2 

1. 2x1-x2 <= 4 

2. X1 + x2 <= 9 

3. -x1 + x2 <= 3 

4. X1 >= 0 

5. X2 > = 0 

Simplex can start at the origin with inequalities 4) and 5). As x2 is gradually increased, the first constraint is met with equation 3 and therefore it stops at x2 = 3 and the new vertex is given by 3) and 4)  We converge towards the solution in the next step. 

#codingexercise
Double
GetProductNthEveryFourthPower (Double [] A, Double  p)
{
If ( A== null) return 0;
Return A.GetProductNthEveryFourthPower(p);
}