Revised simplex method: Difference between revisions

Revision as of 02:18, 26 March 2021

Latest revision as of 08:04, 11 February 2025

(3 intermediate revisions by 3 users not shown)

Line 11:

\end{array}

</math>

where {{math|'''''A''''' ∈ '''R'''ℝ^''m''×''n''}}. Without loss of generality, it is assumed that the constraint matrix {{math|'''''A'''''}} has full row rank and that the problem is feasible, i.e., there is at least one {{math|'''''x''''' ≥ '''0'''}} such that {{math|'''''Ax''''' {{=}} '''''b'''''}}. If {{math|'''''A'''''}} is rank-deficient, either there are redundant constraints, or the problem is infeasible. Both situations can be handled by a presolve step.

==Algorithmic description==

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 being 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>

Line 131:

</math>

initially, which corresponds to a feasible vertex {{math|'''''x''''' {{=}} &#91;[0&ensp; 0&ensp; 0&ensp; 10&ensp; 15&#93;]^T}}. At this moment,

:<math>

Line 146:

</math>

Choose {{math|''q'' {{=}} 3}} as the entering index. Then {{math|'''''d''''' {{=}} &#91;[1&ensp; 3&#93;]^T}}, which means a unit increase in {{math|''x''₃}} results in {{math|''x''₄}} and {{math|''x''₅}} being decreased by {{math|1}} and {{math|3}}, respectively. Therefore, {{math|''x''₃}} is increased to {{math|5}}, at which point {{math|''x''₅}} is reduced to zero, and {{math|''p'' {{=}} 5}} becomes the leaving index.

After the pivot operation,