Revised simplex method: Difference between revisions

Revision as of 09:18, 9 February 2018

Latest revision as of 08:04, 11 February 2025

(7 intermediate revisions by 6 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 87:

:<math>\frac{\partial (\boldsymbol{c}^{\mathrm{T}} \boldsymbol{x})}{\partial x_q} = s_q,</math>

i.e., every unit increase in {{math|''x_q''}} will results in a decrease by {{math|−''s_q''}} in {{math|'''''c'''''^T'''''x'''''}}.{{sfn|Nocedal|Wright|2006|p=369|loc=Eq.&nbsp;13.24}} Since

:<math>\boldsymbol{B x_B} + \boldsymbol{A}_q x_q = \boldsymbol{b},</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''₃}} will 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,

Line 186:

==Practical issues==

===Degeneracy===

{{seealso|Simplex method#Degeneracy: Stallingstalling and cycling}}

Because the revised simplex method is mathematically equivalent to the simplex method, it also suffers from degeneracy, where a pivot operation does not result in a decrease in {{math|'''''c'''''^T'''''x'''''}}, and a chain of pivot operations causes the basis to cycle. A perturbation or lexicographic strategy can be used to prevent cycling and guarantee termination.{{sfn|Nocedal|Wright|2006|p=381|loc=§13.5}}

Line 218:

|year=1997

|url=http://www.cise.ufl.edu/research/sparse/Morgan/index.htm

|archiveurlarchive-url=https://web.archive.org/web/20110807134509/http://www.cise.ufl.edu/research/sparse/Morgan/index.htm

|archivedatearchive-date=7 August 2011

}}

|ref=harv}}

* {{cite book

|last1=Nocedal

Line 240:

|isbn=978-0-387-30303-1

|url=https://www.springer.com/mathematics/book/978-0-387-30303-1

}}

|ref=harv}}

{{refend}}