Improved simplex method for LP

General solution

For the standard LP question:

Min CX

Subject to: AX=b and X>=0

 

Based on the simplex method, A is split into (B,N), B is coefficient for bass variable (supporting there are m basic variable from X(1)-X(m)) , N for non-based variable (from X(m+1) to X(n)). Corresponded X is also separated into (Xb,Xn).

So AX=b comes into (B,N)*(Xb,Xn)’=b.

ð     B*Xb+N*Xn=b

ð    

if let Xn (non-basic variable) equal zero,

So,

 

The following discussion will be based on this equation.

How to decide the termination condition

Now we will think about the optimization for Z. Let  . If we want to make Z more minimize, we must hope to find the negative elements of W because all elements of Xn are positive. From the previous discussion, we can get the terminate rule for iterative process to find optimization.

 

  1. If  all elements of W >=0, then we find the optimization solution for the question, that is the current solution.
  2. if there exists at least one element of W negative, continue to search optimization solution. we try to find one element of Xn which has maximization distribution to minimize the value of Z. it is clearly that the element of Xn having the minimize negative value is the best candidate. State , let X(m+k) is the enter variable (entering the basic variable set from non-basic variable).
  3. If , no solution (k is the enter variable index, A=(P1,…Pn), here , belonging to , is coefficient for non-basic variable X(m+k).

Prof:

From , supporting X(m+k) is not 0, let it equal  and greater than 0, then

 

because , Xb still are greater than 0, are feasible solution for question. let us see objective function:

 

Because Wk is less than 0, if , .

So there is no minimization for objective function.

 

Based on the previous discussion, there will have three conditions during the iterative procedure:

  1. finding the solution
  2. continuing to try new the point
  3. no minimization solution

 

How to determine the leaving variable

Let  Xb a feasible solution. so B*Xb=b. B=(P1,…,Pm). we know B nonsingular,  so the P1 to Pm are the independent vectors, other vectors Pm+1 to Pn can be linear dependence with P1 to Pm. then we can get

=>

 

From B*Xb=b, we got

(P1,…,Pm)*Xb=b

Let  a positive real number.

=>

=>

Let X(m+j) replace a variable in Xb, we can get a new feasible solution if we set suitable values for X and make sure X>=0. Directly we can see a suitable solution from the previous formulation through setting the new Xb to equal . We will let one element equal 0 to be replaced by X(m+j). To assure the other Xb positive, we can arrive this aim through choosing the suitable. let

 

we can get the solution. so X(l) is leaving variable and .

Now we can apply this result to the real equation. based on

we know X(m+k) is the entering variable. we will determine the leaving variable through choosing the minimization  using equation

supporting it arrives the minimization when i equals l, the leaving variable is Xl.

Decreasing Computing

The simplex method is a good way to solution linear programming. But we can see it’s very complex for computing, especially, it calculates much computing which is not related to the question and takes much memory.

 

From the previous discussion, we can see the main computing is focus on the inverse matrix B. if we can find the better way to improve it, we can get the better efficiency.  A simple idea is to find what’s the relationship between B in the closing step. If we can use the previous B to speed the computing the next step B, we will speed the computing. We find the original B=(P1,…,Pm), the new B is (P1,…,P(l-1),P(m+k),P(l+1),…,Pm). There is only one column different. It means the coefficient of the leaving variable is replaced with the entering variable. There is a relationship between these two B.

then

so if we can find the inverse of C, we will speed the computing of the inverse of B.

and

here , i=1…m.

 

Through this way, we can use the previous inverse matrix to calculate the new inverse matrix.

Applying method (idea???)

For our case:

Min CX

Subject to: AX=b and X>=0

 

Importing article variables X..=(X(n+1)…X(n+m)),  So equation becomes AX+IX..=b.

Let Con is very big positive real number basing on Big-M method, changing objective Z=CX+Con*Sum(X(n+i))

 

Based on the previous discussion, X are non-basic variables. B equals I. It is easy to computing. So it’s not needed to inverse matrix. But we found the article variables are in the objective function. We will remove them from objective function. So if the article variable is removed from basic variable, we will remove it from the objective function. It means the coefficient of article variable becomes zero not Con. And remove all the other coefficient of article variable from the responding N. we can think this article variable never exists.

 

If the finial optimization arrives, the coefficient of article variables must be zero. Otherwise, optimization is not correct.