1) The idea in the simplex method is to start with a feasible solution, and iteratively improve it until no further improvements are possible.
2) We call the variables that appear on the left hand side of the dictionary basic variables.
3) The variables that appear on the right hand side of the dictionary are nonbasic variables.
4) Together, the basic variables are said to constitute a basis.
5) The process of going from one dictionary to the next is called pivoting.
6) Suppose our problem is in standard form,
Max cTx
s.t.
Ax = b, x ³ 0
and assume we have an initial basic feasible solution. Then let xB denote our basic variables and xN the nonbasic variables. If we look at our constraints, the dictionary approach corresponds to doing the following:
ABxB + ANxN = b
ABxB = b - ANxN
xB = AB-1b - AB-1ANxN
7) Looking at the objective function, z = cT x = cBTxB + cNTxN
Substituting xB, we get z = cBTxBAB-1bANxn + cNTxN
= cBTA-1b + (cNT - cBTAB-1AN)xn
Since we set xN = 0, our solution can be read as
xB = AB-1b, xn = 0 and z = cBAB-1b
8) AB-1 is called the basis inverse and usually denoted by B-1 (i.e. B = AB)
9) An elementary row operation on a matrix A is one of the following operations:
(1) Row i and Row j are interchanged.
(2)Row i is multiplied by a nonzero scalar k.
(3) Row i is replaced by row i plus k times row j.
10) The system Ax=b is invariant under elementary row operations
11) Let A be a square n´n matrix. If B is an n´n matrix such that AB = I, then B is called the inverse of A.
12) The inverse matrix of A, if it exists, is unique and is denoted by A-1.
13) If A has an inverse, A is called nonsingular, otherwise it is called singular.
14) Given an n´n matric A, it has an inverse if and only if the rows of A are linearly independent, or equivalently if the columns are linearly independent.
15) In order to calculate the inverse, we adjoin the identity to A. The matrix A is reduced to the identity by elementary row operations. This will result in teducing the identity to A-1.
16) If A is nonsingular, then AT is also nonsingular and (AT)-1 = (A-1)T
17) If A and B are both n´n nonsingular matrices, then AB is nonsingular and (AB)-1 = B-1A-1
18) A triangular matris (either lower or upper tirangular with nonzero diagonal elements has an inverse.
19) Let A be partitioned as follows, where D is nonsignular: A = [[I, C][0, D]].
Then A is nonsingular and A-1 = [[I, CD^[-1]], 0, D-1]
20) The simplex tableau is a format for keeping track of the iterations of the Simplex method, first used by Dantzig.
21) Given a LP,
max z = cTx
s.t. Ax = b, x³ 0
The first row of the tableau corresponds to the constraint: -z + cTx = 0, and -z is a basic variable.
22) If we had a column for (-z) in the same way as for the xi's, we'd have a column that does not change throughout the iterations on the tableau. It is therefore left out.
23) The Right hand side value for the (-z) row is initially zero. In General, the RHS in the (-z) row is the negative of the current objective value.
24) To select the entering variable, we want the largest possible number in the (-z) row (since we're maximizing z). We call this column the pivot column.
25) The pivot column becomes our focus for picking the leaving variable. If the pivot column is column j, we form ratios: {(bi / aij) | i Î [1, n]} and pick the minimum to determine the pivot row.
26) The pivot column and pivot row intersect at the pivot element. This number must be changed to 1 and no ther 1's should appear in the pivot column in the next dictionary.
27) The pivoting operation is performed by multiplying the pivot row by (1/aij) and addiing appropriate mltiples of this row to all other tows to "zero out" the other entries in the pivot column.
28) To determine the feasibility of a standard form LP
max cTx
s.t. Ax = b, x ³ 0 (WLOG assume b ³ 0)
We create the following new problem
max -åeTw
s.t. Ax + Iw = b, x ³ 0, w ³ 0.
The variables w form an initial basis for the feasibility problem. When we solve this problem, if the objective is > 0 then the original problem is infeasible. If the objective is = 0, then the original problem is feasible.
29) The idea behind the lexicographic method is to perturb the RHS of the initial problem ever so slightly. In this way we want to ensure that the basic variables would never have zero vales and avoid degeneracy in the perturbed problem.
30) To execute the lexicographic method, we will add a pertubarion
e1 to the first equality of the dictionary
e2 to the second equality of the dictionary
e3 to the third equality of the dictionary
and so on until we add
em to the mth equality of the dictionary.
Further these pertubarions have the property 0 < em << em-1 << ... << e2 << e1 << 1
31) We can impliment this pertubation idea by looking at the lexicographic order of the perturbation to the RHS in the presence of degeneracy.
32) If r is lexicographically smaller than s, and s is lexicographically smaller than t, then r is lexicographically smaller than t.
33) If there are m distinct numbers r1, r2, ..., rm of the form ri = r1ie1 + r2ie2 + ... + rmiem then one of them is lexicographically smaller than the others.
34) When we have a tie for the leaving variable in the simplex method without perturbation, the same situation in the simplex method with perturbation chooses amongst the variables tied for leaving the basis by the lexicographic ordering of the perturbation.
35) When we apply the simplex method with respect to the perturbed problem degeneracy cannot occur.
36) Degeneracy occurs when a basic variable has a value zero.
37) Pertubing the initial problem is equivalent to solving
max cTx
s.t. Ax = b + Ie, x ³ 0, where e = [e1, e2, ..., em]T
38) In matrix notation the lexicographic method dictionary is equivalent to xB = AB-1b + AB-1e - AB-1ANxN
39) Since the perturbation for any dictionary is given by the basis inverse times the e vector,
- Every row has a nonzero perturbation.
Perturbations are distinct (i.e. no two rows will have exactly the same perturbation)
40) Since in the perturbation for any dictionary, every row has a nonzero perturbation, degeneracy cannor occur within the perturbed problem.
41) Since in the pertubation for any dictionary pertubations are distinct, there are no ties for the leaving variable.
42) We don't need to calculare the pertubations explicitly as long as we go from dictionary to dictioary. We simply need to keep track of the basis inverse.
43) The lexicographic rule for choosing leaving variable in case of ties: look at the basis inverse and choose between the tied variables by selecting the one with the lexicographically smallest row.
44) The simplex method terminates so long as the leaving variable is selected by the lexicographic rule.
45) Bland's rule says that if there is a tie, then, both in the case of entering variable and in the case of leaving variable, choose the variable with the smallest subscript.
46) Bland's rule is also called the smallest subscript rule.
47) If the simplex method follows Bland's rule, cycling cannot occur.
48) We call a variable fickle if it is nonbasic in some of the dictionaries and basic in others.
49) *If at the end of the simplex algorithm to the feasibility problem we find:
Case 1: The artificial variables are all nonbasic. This implies that the problem is feasible and we have a feasible dictionary for our original problem.
Case 2: There is a basic artificial variable with a positive value. This implies that our problem is infeasible.
Case 3: There is an artificial variable which is basic and equal to zero. This case cannot happen.
50) In the simplex method with tableau, we usually keep track o the original objective function in addition to the objective function for the feasibility problem. Once the objective for the feasibility problem is zero and the artificial variables are nonbasic we simply remove the row corresponding to the feasibility problem and the columns corresponding to the artificial variables, and continue with the original objective function.
51) A polyhedron is a set of the form {x | x Î 
n | Ax £ b} where A Î m x n and b Î m. Note Ax £ b can be equivalently replaced by Ax ³ b.
52) A set S Ì n is bounded if there exists a constant k such that "x Î, "i Î [1, n], |xi| < k
53) Let a Î n and b Î m be given. The set {x Î n | aTx = b} is a hyperplane.
54) Let a Î n and b Î m be given. The set {x Î n | aTx ³ b} is a halfspace.
55) The vector a is orhogonal to the hyperplane it defines.
56) A set S Í n is convex if "x, y Î S 0 £ l £ 1, l Î , we have lx + (1-l)y Î S.
57) Let x1, ..., xk Î n and lT = [ l1, ..., ll] ] be given such that l1 + ... + lk = 1, li ³ 0 for all i. The vector åi=1 to k lixi is said to be a convex combination of x1, ..., xk.
58) The convex hull of x1, ..., xk is the set of all convex combinations of these vectors.
59) The intersection of convex sets is convex.
60) Every polyhedron is a convex set.
61) The convex combination of a finite number of elements of a convex sets also belongs to that set.
62) The convex hull of a finite number of vectors is a convex set.
63) Let P Í n be a given polyhedron. A vector x Î P is an extreme point of P if "y, z Î P, "l Î (0, 1) x ¹ ly + (1-l)z
64) Let P Í n be a given polyhedron. A vector x Î P i a vertexof P if $ c Î n such that cTx < cTy for all y Î P with x ¹ y.
65) A vector space satisfies the following properties:
x + y = y + x
x + (y + z) = (x + y) + z
There is a unique zero vector s.t. x + 0 = x
for each xi there is a unique vector -x such that x + (-x) = 0
1*x = x
(c1c2)x = c1(c2x)
c(x+y) = cx + cy
(c1 + c2)x = c1x + c2x
66) A subspace of a VS is a subset that satisfies the following two requirements:
- If we add any vectos x and y in the subset, their sum is also in the subset.
- If we multiply any vector x in the subset y any scalar c, the multiple cx is in the subset.
67) A finite collection of vectors x1, ..., xk Î n is linearly independent if the unique solution ot åi = 1 to klixi = 0 is li = 0 for i = 1, ..., k. Otherwise the vectors are called linearly dependent.
68) A linear combination of a collection of vectors x1, ..., xk Î n is any vector y Î n s.t. y = åi = 1 to klixi for some l Î k
69) The span of a collection of vectors x1, ..., xk is the set of all linear combinations of those vectors.
70) A basis for a vector space is a set of vectors having two properties at once:
- it is linearly independent
- it spans the vector space.
71) The number of vectors in the basis is the dimension of the VS.
72) The system Ax = b is solvable if and only if the vector B can be expressed as a linear combination of the columns of A.
73) The column space of A is the span (i.e. all linear combinations) of the columns of A.
74) The row space of A is the span (i.e. all linear combinations) of the rows of A.
75) The null space of A is the set of solutions ot Ax = 0.
76) A vector space does not have a unique basis.
77) For a given basis, a given vector v can be expressed in one and only one way as a combination of two basis vectors.
78) Any two bases for a vector space contain the same number of elements, this is called the dimension of the vS.
79) The rank of a matrix A is the number of linearly independent columnd of A.
80) If rank(A) = min{m, n}, where A is a m´n matrix, then A is said to have full rank.
81) Any linearly independent set of vectors of a VS can be extended to a basis by adding more vectors if necessary.
82) x* is a basic solution to the polyhedron P = {x | Ax = b, x ³ 0} if there exist n linearly independent inequality constraints (from Ax = b, x ³ 0) at x*
83) x* is a basic feasible solution with respect to P = {x | Ax=b, x ³ 0} if it is a basic solution and it is feasible.
84) For the polyhedron P = {x | Ax=b, x ³ 0}, m constraints are already satisfid at equality, So n - m constraints from x ³ 0 must be satisfied at equality for a basic solution. Bu we must also ave the m constraints Ax = b are linearly independent.
85) For a basic solution, x, lets call the n-m variables set to zero nonbasic and denote them by xN. Lets call the remaining variables basic and denote them by xB
86) For a basicsolution xN = 0 and xB satisfies ABxB = b.
87) The m constraints of ABxB are linearly independent if and only AB is invertible, iff the columns of AB are linearly independent.
88) Consider the constraints Ax=b, x³ 0 and assume that the m´n matrix A has linearly independent rows. A vector x Î n s a bsac solution IFF we have Ax=b and there exist indices B(1), ..., B(m), such that
(a) the columns AB(1), ..., AB(m) are linearly independent.
If i ¹ B(1), ..., B(m) , then xi = 0.
then a basic solution is formed by taking
(i) m linearly independent columns of A. Let B denote these indices of these columns.
(ii) Let xi = 0 for i [not in] B.
(iii) Solve the system ABxB = b.
89) If x is a basic feasible solution to P = {x | Ax=b, x ³ 0}, x is an extreme point of P.
90) If x is an extreme point of P = {x | Ax=b, x ³ 0}, x is a basic feasible solution to P.
91) Let A1,A2, ..., Am be a basis for m. let Q ¹ 0 be any m-dimensional vector. Let (l1, ..., lm) be the representation of Q in terms of the basis A1, ..., Am. So Q = åj=1 to mljAj. Then if Q replaces any vector Ar in the basis, with lr ¹ 0, thenew set of vectors is a basis for m.
92) Two bases that differ in only one column are called adjacent and the solutions they give are called adjacent basic solutions.
93) Let P = {x | Ax=b, x ³ 0} be a nonempty polyhedron, where A is a matrix of dimensions m´n, with rows a1T, ..., amT. Suppose that rank(A) = k < m and that rows ai_1T, ..., ai_kT are linearly indepenent. Consider the polyhedron Q = {x | ai_1Tx = bi_1, ai_2Tx = bi_2, ..., ai_kTx = bi_k, x ³ 0. Then Q = P.
This theorem says that if you delete the set of redundant constraints (i.e. the equality constraints that are automatically satisfied when the linearly independent constraints are satisfied, the set of feasible points remains the same. )
94) Phase I of the simplex method eliminates any rows that are not linearly independent.
95) Given a linear program in standard form, Phase I of the simplex method forms the LP
maximize -w1 - w2 - ... - wm
s.t. Ax + Iw = b, x ³ 0, w ³ 0. Call this the feasibility problem.
96) An initial BFS (dictionary) of the feasibility problem is found by setting x = 0 and w = b.
97) If the optimal solution to the feasibility problem is strictly less than zero, the original problem is infeasible.
98) If the optimal solution to the feasibility problem is equal to zero, problem is feasible.
99) At the start of Phase II, we need a BFS with only variables in x being basic (no artificial variables). So if Phase I terminates with an artificial variable being basic, but the optimal objective value of phase I is 0, then the artificial variables all have value zero and we can pivot on any non-basic variable from the original problem that has a non-zero coefficient in the same row as a basic artificial variable, and repeat as necessary.
100) If all the coefficients of xi variables in the row corresponding to a basic artificial variable at the end of phase I are zero, we have a redundant equation and it can be deleted.
101) A basic solution x Î n is said to be degenerate if more than n constraints are active at x.
102) A constraint is active at x if it is satisfied at equality.
103) For a polyhedron in standard form, the m equality constraints are always active, so for a standard form polyhedron more than n constraints being active is the same as more than n-m nonnegativity constraints being active. This means that more than n-m variables are set equal to zero! Since there are n-m nonbasic variables, this implies one of the basic variables is zero.
104) Consider the standard form polyhedron P = {x | Ax=b, x ³ 0} and let x be a basic solution. Let m be the number of rows in A. The vector x is a degenerate basic solution if more than n-m of the components of x are zero.
105) When there is no degeneracy, there is a unique BFS corresponding to an extreme point.
106) When there is degeneracy, there may be more than one BFS corresponding to the same extreme point, but not always.
107) There is a one-to-one correspondence between the extreme points of the canonical form Polyhedron P1 = {x | Ax£b, x ³ 0} and the standard form polyhedron P2 = {x | Ax=b, x ³ 0}
108) We can map every P1 = {x | Ax£b, x ³ 0} uniquely to an (x, s)T Î P2 = {x | Ax=b, x ³ 0, s ³ 0} by setting x = Ix and s = b-Ax so (x, s)T = (0, b)T + (I, -A)TxT
109) We can map every (x, s)T Î P2 = {x | Ax=b, x ³ 0, s ³ 0} uniquely to an x Î P1 = {x | Ax£b, x ³ 0} by mapping (x, s)T to (x)T
110) Let P1 = {x | Ax£b, x ³ 0} and P2 = {x | Ax=b, x ³ 0, s ³ 0} Then P1 is isomorphic to P2.
111) A point x Î P1 = {x | Ax£b, x ³ 0} is extreme if and only if the point (x, s)T = (o, b)T + (I, -A)TxT is extreme to P2.
112) A polyhedron P Ì n contains a line if there exist a vector x Î P and a nonzero vector d Î n s.t. x + ld Î P for all scalars l.
113) A polyhedron P has at least one extreme point if and only if it does not contain a line.
114) Assuming a linear program is feasible and its objective value is bounded, one of the optimal solutions is an extreme point.
115) Any point in a convex polyhedron can be represented by a convex combination of its extreme points.
116) The formula for the simplex multipliers, y, is y = cBTAB-1.
117) The formula for the reduced costs for a nonbasic variable, 
N(i) is given by cN(i) = cN(i) - yAN(i), where y is the vector of simplex multipliers and AN(i) is the ith column of the nonbasic variables of A.
118) The revised simplex method for a max problem is : .....