Simplex algorithm: Difference between revisions

Revision as of 05:31, 22 January 2020

Revision as of 10:43, 12 April 2020

Line 18:

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

with <math> \mathbf{xc} = (x_1c_1,\, \dots,\, x_nc_n)</math> the variablescoefficients of the problemobjective function, <math>(\cdot)^\mathrm{T}</math> is the [[matrix transpose]], and <math> \mathbf{cx} = (c_1x_1,\, \dots,\, c_nx_n)</math> the coefficientsvariables of the objective functionproblem, <math>A</math> is a ''p×n'' matrix, and <math> \mathbf{b} = (b_1,\, \dots,\, b_p)</math> 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).