Engineering Optimization: Theory and Practice, Fourth Edition

3.5 Definitions and Theorems 131

10.Basic feasible solution.This is a basic solution that satisfies the nonnegativity

conditions of Eq. (3.3).

11.Nondegenerate basic feasible solution.This is a basic feasible solution that has

got exactlympositivexi.

1 2.Optimal solution.A feasible solution that optimizes the objective function is

called an optimal solution.

13.Optimal basic solution.This is a basic feasible solution for which the objective

function is optimal.

Theorems. The basic theorems of linear programming can now be stated and proved
†.

Theorem 3.1The intersection of any number of convex sets is also convex.

Proof: Let the given convex sets be represented asRi(i = 1 , 2 ,... , K)and their
intersection asR, so that‡

R=

⋂K

i= 1

Ri

If the pointsX(^1 ),X(^2 )∈ R,then from the definition of intersection,

X=λX(^1 ) +( 1 −λ)X(^2 )∈Ri (i = 1 , 2 ,... , K)

0 ≤λ≤ 1

Thus

X∈R=

⋂K

i= 1

Ri

and the theorem is proved. Physically, the theorem states that if there are a number of
convex sets represented byR 1 , R 2 ,... ,the set of pointsRcommon to all these sets
will also be convex. Figure 3.12 illustrates the meaning of this theorem for the case
of two convex sets.

Theorem 3.2The feasible region of a linear programming problem is convex.

Figure 3.12 Intersection of two convex sets.

†The proofs of the theorems are not needed for an understanding of the material presented in subsequent
sections.
‡The symbol∩represents the intersection of sets.