Читать книгу Optimizations and Programming - Bouchaib Radi, Ghias Kharmanda, Michel Ledoux - Страница 21

Consider the problem

where and A is an m × n matrix. We may assume without loss of generality that rank A = m < n.

DEFINITION 1.9.– Let A = (a1, a2, . . . , an) (where aj is the jth column of A), and, for J ⊂ {1, 2, . . . , n}, let AJ = {aj, j ∈ J}.

 – J ⊂ {1, 2, . . . , n} is a basis of (P) if |J| = m and if rank AJ = rank (aj, j ∈ J) = m;

 – let x = (x1, . . . , xn)T ∈ Then xj is a basic variable (respectively, non-basic variable) if j ∈ J (respectively, j ∉ J). We write xJ = (xj, j ∈ J);

 – basic feasible solution: x = (x1, . . . , xn)T ∈ such that xj = 0 for j ∉ J and such that Ax = AJ xJ = b.

REMARK.– The advantage of passing from the canonical form to the standard form is that we immediately obtain a basic feasible solution that can be used as a starting point for the simplex algorithm. The basic variables are the slack variables.