Min Ctx

Subject to

Ax = b

x ≥ 0

Where A∈ Mmxn, and rank(A)=m, b∈Rm, C∈Rn

Subject to

Ax = b

x ≥ 0

Where A∈ Mmxn, and rank(A)=m, b∈Rm, C∈Rn

A Linear programming problem in standard formulation is a problem in the form

Min Ctx

Subject to

Ax = b

x ≥ 0

Where A∈ Mmxn, and rank(A)=m, b∈Rm, C∈Rn

Subject to

Ax = b

x ≥ 0

Where A∈ Mmxn, and rank(A)=m, b∈Rm, C∈Rn

From now on we will call P to this problem.

C will be the costs vector, A the constraints matrix and b the constraints vector.

The feasible set

S = {x∈Rn : Ax = b, x≥ 0}

is a polyhedral set (semispaces intersection), in particular is a convex set. The convex theory join linear programming theorems says that if P has finite optimal solution it will be into the extreme points set of S.

C will be the costs vector, A the constraints matrix and b the constraints vector.

The feasible set

S = {x∈Rn : Ax = b, x≥ 0}

is a polyhedral set (semispaces intersection), in particular is a convex set. The convex theory join linear programming theorems says that if P has finite optimal solution it will be into the extreme points set of S.

The feasible Set

S = {x∈Rn : Ax = b, x≥ 0}

Can be characterized in terms of its extreme points and its extreme directions

S = {x∈Rn : Ax = b, x≥ 0}

Can be characterized in terms of its extreme points and its extreme directions

The feasible set, se has at least one extreme point.

If B is submatrix of A with dimension mxm then we can write

A = [B, N] and the linear programming equations system can be write as follows

BXB + NXN = b

and we can write too

x = [XB, XN]

There exists a characterization of the extreme points of feasible Region S, There is a characterization of extreme points of feasible set S, the intuitive idea is that any extreme point is a solution of a linear system of equations constructed from a submatrix of A of range m.

A = [B, N] and the linear programming equations system can be write as follows

BXB + NXN = b

and we can write too

x = [XB, XN]

There exists a characterization of the extreme points of feasible Region S, There is a characterization of extreme points of feasible set S, the intuitive idea is that any extreme point is a solution of a linear system of equations constructed from a submatrix of A of range m.

Lets S = {x∈Rn : Ax = b, x≥ 0} ⊂ Rn.

Where

A∈ Mmxn, con range(A)=m, b∈Rm, C∈Rn

then x is an extreme point if and only if ∃ B submatrix of A with r(B) = m such as

x = [B-1b, 0]t

The following corollary gives us an upper bound for the number of extreme points.

The maximum number of extreme points of S is (n m) = n!/m!(n-m)!

(We apologize for the notation, we have no way to write combinatorial numbers)

As we shall see, not every linear programming problem has finite optimal solution, but if one then there is a characterization for it in the next theorema:

Lets

x1, x2, ... xk los Extreme points of S and lets

d1, d2, ... dr las Extreme directions of S.

P has finite optimal solution if and only if Ctdj ≥ 0, j =1,2, ..., r

And one of the extreme points is the solution for the problem P.

Post here