simplex method II

LPs in which all the constraints are (?) with non-negative right-hand sides offer a convenient all-slack starting basic feasible solution. Models involving (=) and/or (?) constraints do not. The procedure for starting "ill-behaved" LPs with (=) and (?) constraints is to use artificial variables that play the role of slacks at the first iteration, and then dispose of them legitimately at a later iteration. Two closely related methods are introduced here: the M-method and the two-phase method.The M-method starts with the LP in equation form, If equation i does not have a slack (or a variable that can play the role of a slack), an artificial variable, Ri, is added to form a starting solution similar to the convenient all-slack basic solution, However, because the artificial variables are not part of the original LP model, they are assigned a very high penalty in the objective function. the objective function can assume the same optimal value at more than one solution point, thus giving rise to alternative optima.