Engineering Optimization: Theory and Practice, Fourth Edition

128 Linear Programming I: Simplex Method

Definitions

1.Point inn-dimensional space.A pointXin ann-dimensional space is char-

acterized by an ordered set ofnvalues or coordinates(x 1 , x 2 ,... , xn) The.

coordinates ofXare also called thecomponentsofX.

2.Line segment in n dimensions (L).If the coordinates of two pointsAandB

are given byxj(^1 )andxj(^2 )(j = 1 , 2 ,... , n), the line segment(L)joining these

points is the collection of pointsX(λ)whose coordinates are given byxj=

λxj(^1 )+ ( 1 −λ)x(j^2 ), j = 1 , 2 ,... , n, with 0≤λ≤1.

Thus

L= {X|X=λX(^1 )+ ( 1 −λ)X(^2 )} (3.4)

In one dimension, for example, it is easy to see that the definition is in accor-

dance with out experience (Fig. 3.7):

x(^2 )− x(λ)=λ[x(^2 )−x(^1 )], 0 ≤λ≤ 1 (3.5)

whence

x(λ)=λx(^1 ) +( 1 −λ)x(^2 ), 0 ≤λ≤ 1 (3.6)

3.Hyperplane.Inn-dimensional space, the set of points whose coordinates satisfy

a linear equation

a 1 x 1 + · · · +anxn=aTX=b (3.7)

is called a hyperplane. A hyperplane,H, is represented as

H (a, b)= {X|aTX=b} (3.8)

A hyperplane hasn−1 dimensions in ann-dimensional space. For example,

in three-dimensional space it is a plane, and in two-dimensional space it is a

line. The set of points whose coordinates satisfy a linear inequality likea 1 x 1 +

·· · +anxn≤ bis called aclosed half-space, closed due to the inclusion of an

equality sign in the inequality above. A hyperplane partitions then-dimensional

space(En) nto two closed half-spaces, so thati

H+= {X|aTX≥b} (3.9)

H−= {X|aTX≤b} (3.10)

This is illustrated in Fig. 3.8 in the case of a two-dimensional space(E^2 ).

Figure 3.7 Line segment.