Basic Concepts
Consider the linear programming problem in standard form $$ \min \left\{ {cx:Ax = b,x \geqslant 0} \right\} $$ (LP) where A is a m x n matrix of full rank, i.e, r(A =m. We denote by $$ \chi = \left\{ {x \in \mathbb{R}^n :Ax = b,x \geqslant 0} \right\} $$
- PDF / 1,138,064 Bytes
- 8 Pages / 547 x 686 pts Page_size
- 40 Downloads / 253 Views
Consider the linear programming problem in standard form min{cx : Ax = b,« 2:: O}
(LP)
where A is a m x n matrix of full rank, i.e., r( A) = m. We denote by X = {x E IRn
:
Ax = b, x 2:: O}
the solution set of (LP). A vector x E X is calledjeasible solution, while x (j. X is called injeasible. Let N = {I , . . . ,n}. Given a feasible solution x E X we denote by Ix
= {j
EN : X j > O}
and
N - t;
= {j
E N:
Xj
= O} ,
the set of the positive and the zero components of x , respectively. Then x satisfies the system of linear equations Ax = b, X j = 0 for all j E N - I x or Alx A N-Ix) (XIx ) ( o I n - kx XN-Ix
=(
b ) where kx = 0
IIxl and n = INI.
(3.1)
A lx is a m x k x submatrix and A N- Ix a m x (n - k x ) submatrix of A and we compute r
Alx IA N-Ix) -- r (A) Ix + n - k x ' ( 0 n - kx
The system (3.1) is uniquely solvable if and only if r( AIJ + n - k x = n, l.e ., if and only if r( A IJ = IIxl, since by assumption a solution to (3.1) exists. For the system (3.1) to be solvable uniquely, we thus need in particular that the number of rows of (3.1) satisfies m + n - kx 2:: n, t.e., IIxI:::; m. We shall use the following definitions. x is called basicjeasible solution if r( AIJ = IIxl. x is called degenerate basicjeasible solution if r (A lx) = IIxl < m. An m x m submatrix B of A is called basis if r (B) = m. A basis B is calledjeasible if B - 1b 2: O. A feasible solution x E X is optimal if ex ::; ex for all x E X . An optimal solution x is finite or bounded if there exists a K > 0 such that Xj ::; K for all j E N . For any finite optimal solution x , ex > - 00. Given a basis B we partition A and write Ax = BXB + Rx R, where R is the "rest" of A, t.e ., the columns of A not in the basis B. Rather than denoting I B the columns of B and thus X I B the subvector of x corresponding to the columns of B, etc. we write x B and x R for short. Multiplying the equation system B XB + Rx R = b on both sides by B - 1 we get the equivalent system of equations XB + B - 1 Rx R = B - 1b. If a basis B is feasible then it defines a basic feasible solution to A x = b, x 2:: 0 by XB = B - 1b , XR = O. The following remarks, lemma and theorem are proven in detail in the book. Several of the exerc is es below illustrate the proof techniques employed there. D. Alevras et al., Linear Optimization and Extensions © Springer-Verlag Berlin Heidelberg 2001
48
3. BASIC CONCEPTS
if b = 0, then either x bounded from below.
Remark 3.1
= 0 is an optimal solution to (LP) or the minimum oj (LP) is not
if x is a basic feasible solution, then x has at most m positive components and the submatrix AI", defined in (3.1) can be extended to afeasible basis B that defines x by adjoining to AI", suitable columns oj AN-I", .
Lemma 1
Remark 3.2 For every basic feasible solution x E X there exists at least one feasible basis B of A that defines x and every feasible basis defines a basic feasible solution x EX.
x is a basic feasible solution if and only if there exists a vector e E lRn with integer components such that min {ex: x E X} = ex
Data Loading...
