Simplex algorithm: Difference between revisions

Revision as of 22:14, 15 December 2020

Revision as of 22:17, 15 December 2020

Line 23:

: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×np''×''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 204:

The equation defining the original objective function is retained in anticipation of Phase II.

By construction, ''u'' and ''v'' are both non-basic variables since they are part of the initial identity matrix. However, the objective function ''W'' currently assumes that ''u'' and ''v'' are both ''&nbsp;0''. In order to adjust the objective function to be the correct value where ''u''&nbsp;=&nbsp;''10'' and ''v''&nbsp;=&nbsp;''15'', add the third and fourth rows to the first row giving

:<math>

\begin{bmatrix}