Revised simplex method: Difference between revisions

Revision as of 15:54, 12 March 2014

Revision as of 16:00, 12 March 2014

Line 29:

where {{math|'''''λ'''''}} and {{math|'''''s'''''}} are the [[Lagrange multiplier]]s associated with the constraints {{math|'''''Ax''''' {{=}} '''''b'''''}} and {{math|'''''x''''' ≥ '''0'''}}, respectively.{{sfn|Nocedal|Wright|2006|p=358|loc=Eq.&nbsp;13.4}} The last condition, which is equivalent to {{math|''s_ix_i'' {{=}} 0}} for all {{math|1 < ''i'' < ''n''}}, is called the ''complementary slackness condition''.

By what is sometimes known as the ''fundamental theorem of linear programming'', a vertex {{math|'''''x'''''}} of the feasible polytope can be identified by be a basis {{math|'''''B'''''}} of {{math|'''''A'''''}} chosen from the latter's columns.{{efn|The same theorem also states that the feasible polytope has at least one vertex and that there is at least one vertex which is optimal.{{sfn|Nocedal|Wright|2006|p=363|loc=Theorem&nbsp;13.2}}}} Since {{math|'''''A'''''}} has full rank, {{math|'''''B'''''}} is nonsingular. Without loss of generality, assume that {{math|'''''A''''' {{=}} &#91;'''''B''''' &ensp;'''''N'''''&#93;}}. Then {{math|'''''x'''''}} is given by

:<math>