Content deleted Content added
Mehmetgencer (talk | contribs) mNo edit summary |
|||
Line 19:
::<math>\mathbf{c}^T \cdot \mathbf{x}</math>
:Subject to
::<math>\mathbf{A}\mathbf{x}
with <math>x = (x_1,\, \dots,\, x_n)</math> the variables of the problem, <math>c = (c_1,\, \dots,\, c_n)</math> are the coefficients of the objective function, ''A'' a ''p×n'' matrix, and <math>b = (b_1,\, \dots,\, b_p)</math> constants with <math>b_j\geq 0</math>. There is a straightforward process to convert any linear program into one in standard form so this results in no loss of generality.
In geometric terms, the [[feasible region]]
::<math>\mathbf{A}\mathbf{x}
is a (possibly unbounded) [[convex polytope]]. There is a simple characterization of the extreme points or vertices of this polytope, namely <math>x = (x_1,\, \dots,\, x_n)</math> is an extreme point if and only if the subset of column vectors <math>A_i</math> corresponding to the nonzero entries of ''x'' (<math>x_i \ne 0</math>) are [[Linear independence|linearly independent]].<ref>{{harvtxt|Murty|1983|loc=Theorem 3.1}}</ref> In this context such a point is known as a ''basic feasible solution'' (BFS).
| |||