Consider programming problem (2) and a basic program nondegenerated _{}. After some rearrangement and renumbering we can consider _{}; so, the variables _{} are main and therefore _{} secundary, and columns vectors _{} form the base B of a basic programm _{}. _{Let be}
Writing:
_{} the problem (2) could be writed as:
_{}
Multiplying _{} on the left with _{}we can obtain:
_{}
representing transcription system restrictions under B for if we write _{} (expression vectors based on the vectors base column B) we have:
_{}
So though _{} are the vector component L based on B.
_{}
So the relation (8) becomes:
_{} from where
_{} and then
: _{}
or, more explicit:
_{}
Writing: _{} then:
_{}
We notice that _{}
Now we can associate the problem PLmin following table:
_{} 
c^{1} c^{2} c^{n} 
_{} 

a^{1} a^{2} a^{n} 


the vectors of the base 
_{} 
Unnull components of _{} 

_{} 
......................................... 
_{} 

Theorem II.4.1. If_{}is a nondegenerate basic program for PL  min and in the associated table (S) have _{} then _{} is optimal program..
Proof: We have the expression (13) and then:
_{} for any admissible program X. So _{}is optimal.
Theorem II.4.2. If_{}is a nondegenerate basic program and in associated simplex table (S) we have a t, _{} such as _{} then PL  min doesn't have a finite optimal.
Proof: Let be: _{}where:
_{}
Such as we have _{}
For _{} we got:
_{}_{}
_{} So though _{} is an admissible solution. We have:
_{}
from the _{} definition.
Because _{} then _{}, i.e. the objective function has not an optimal finished.
Theorem II.4.3. If_{}is a nondegenerate basic program for PL  min and in the associated table (S) and in the simplex table associated (S) exists t, _{} and at least one index i, _{}, such as _{} then if we choose _{} with criteria:
_{}
may be substituted on the basis B the vector _{}with the vector _{}, obtaining a base _{}corresponding to the basic program _{}which improves the objective function value.
Proof. Because _{} using Lemma substitution, replacing that _{} with B and _{} vectors system new obtained _{} is a base. Corresponding to the basic solution_{} it is given all the substitution lemma:
_{}
with all nonnegative components (for _{} if _{} then
_{}, so the sum of nonnegative numbers; and if _{} _{we got }and taking into account (14) means that _{} it is the product of two nonnegative numbers).
So though _{}is a basic solution. The value of the objectiv function for _{}is:
_{}
Now we can present a problem for the simplex algorithm PL  min in standard form.
 Step 1^{0}: There is a core(basic) program nondegenerated _{}having the base B; It is build the simplex table (S).
 Step 2^{0}: Check whether differences _{}for any _{}. If YES got to step 5; if NO, of all negative differences _{}, it is choosen the smallest one. J index corresponding to denote by t. (If there are several t choose first from left to right). The vector _{}will be in the base. It assesses whether _{} for _{} If YES, it goes to step 4, if NO, it goes to step 3.
_{ }Step_{ }3^{0}: It choose s, such as _{}.
The vector _{}will come out from the base. The item _{} becomes pivot. It will be build a new simplex table using the rectangle rule:
a) The line of the pivot divides through the pivot
b) in the pivot's column the items _{} are replaced by 0
c) the items are replaced by _{}.
It will be obtained another core program _{}with the base _{}and a new value of the objectiv function.
You come back to step 2^{0} with _{} and _{}
 Step 4^{0} .Conclusion: “PL  min has not an finite optimal” and the algorithm stops.
 Step 5^{0}. Conclusion: “PL  min has an optimal _{}and the minimum value is _{}". STOP.
Example II.4.1. Let be the problem:
_{}
We choose _{}. We got:
_{}
The coordonates of the vector _{}wit the base B are _{}, _{and}. To find the coordinates of _{} proceed as follows: we put _{} , so:
_{} which give us _{}. So though, in base B, _{}. The same way we can have: _{}
So corresponding simplex table base B has the form:

5 7 9 2 1 



_{} 



_{} 
1 0 1 1 1
0 1 1 1 
_{} 

_{} 
0 0 11 10 15 
_{} 

So _{}comes in the base B, _{} comes out from the base, z_{25}  pivot. Run and get:


_{} 
1 1/3 2/3 0
0 1/3 1/3 1/3 1 
_{} 

_{} 
0 5 6 5 0 
_{} 
Enter the base _{} and comes out _{}.
_{} 
_{} 
_{} 
_{} 
_{} 
15/4 25/4 17/2 0 0 
_{} 
And we got _{}So, the optimal program is _{}.
The algorithm applies problems PL  max in standard form with the observation that _{} . The algorithm applies if the objective function has the form _{}, because of its extreme points are the same extreme points of the function: _{}
It is not mandatory to be logged in on this forum but it is nice to have an account. You can ask about mathematics just with your name and your email.
This maths forum is one of the easiest forums to use it.