Courtesy of Sommer Gentry. Used with permission Basis theory every basis contains the same number of variables as the number of constraints. The simplex algorithm only searches feasible bases by design but any set of m variables is not guaranteed to form a feasible basis subject to 2/3x2+x3+1/3x5=4 4 x1+2/3x2 +3x5=-2 x1>0,…,x5>0 Find a starting basic feasible solution The simplex algorithm examples shown so far have all less-than inequalities. In these cases the starting feasible basis is obvious: all the slack variables are basic and the others non-basic. How can we find a feasible basis if given equality constraints? Maximize Z=c1x1+…+Cnx Subject to aux +.+aux=b an1x1+…+amxn=bn x1≥0,,xn≥0.Basis theory • as the number of constraints. The simplex algorithm only searches feasible bases by design, but any set of m variables is not guaranteed to form a feasible basis. subject to: -2/3x2+ x3 +1/3x5 = 4 x2 +x4 = 0 x1 +2/3x2 + 3x5 = -2 x1 >0, …, x5 >0 Find a starting basic feasible solution • have all less-than inequalities. In these cases the starting feasible basis is obvious: all the slack variables are basic and the others non-basic. How can we find a feasible basis if given equality constraints? , ... Subject to ... Maximize ... 1 1 1 11 1 1 1 1 1 t t       n m mn n m n n n n x x a x a x b a x a x b Z   Every basis contains the same number of variables The simplex algorithm examples shown so far 0, 0. c x c x Courtesy of Sommer Gentry. Used with permission