Simplex algorithm: Difference between revisions

Revision as of 08:00, 15 January 2021

Revision as of 01:49, 23 January 2021

Line 24:

:subject to <math>A\mathbf{x} \leq \mathbf{b}</math> and <math>\mathbf{x} \ge 0</math>

with <math>\mathbf{c} = (c_1,\, \dots,\, c_n)</math> the coefficients of the objective function, <math>(\cdot)^\mathrm{T}</math> is the [[matrix transpose]], and <math> \mathbf{x} = (x_1,\, \dots,\, x_n)</math> are the variables of the problem, <math>A</math> is a ''p''×''n'' matrix, and <math> \mathbf{b} = (b_1,\, \dots,\, b_p)</math> are nonnegative constants (<math>\forall j, b_j \geq 0\ </math>). There is a straightforward process to convert any linear program into one in standard form, so using this form of linear programs results in no loss of generality.

In geometric terms, the [[feasible region]] defined by all values of <math>\mathbf{x}</math> such that <math display="inline">A\mathbf{x} \le \mathbf{b}</math> and <math>\forall i, x_i \ge 0 </math> is a (possibly unbounded) [[convex polytope]]. An extreme point or vertex of this polytope is known as ''[[basic feasible solution]]'' (BFS).

Line 33:

The solution of a linear program is accomplished in two steps. In the first step, known as Phase I, a starting extreme point is found. Depending on the nature of the program this may be trivial, but in general it can be solved by applying the simplex algorithm to a modified version of the original program. The possible results of Phase I are either that a basic feasible solution is found or that the feasible region is empty. In the latter case the linear program is called ''infeasible''. In the second step, Phase II, the simplex algorithm is applied using the basic feasible solution found in Phase I as a starting point. The possible results from Phase II are either an optimum basic feasible solution or an infinite edge on which the objective function is unbounded above.<ref name="DantzigThapa1">[[George B. Dantzig]] and Mukund N. Thapa. 1997. ''Linear programming 1: Introduction''. Springer-Verlag.</ref><ref name="NeringTucker"/><ref name="Vanderbei">Robert J. Vanderbei, [http://www.princeton.edu/~rvdb/LPbook/ ''Linear Programming: Foundations and Extensions''], 3rd ed., International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008. {{isbn|978-0-387-74387-5}}. <!-- (An on-line second edition was formerly available. Vanderbei's site still contains extensive materials.) --></ref>

==Standard form==