Engineering Optimization: Theory and Practice, Fourth Edition

132 Linear Programming I: Simplex Method

Proof: The feasible regionSof a standard linear programming problem is defined as

S= {X|aX=b,X≥ 0 } (3.11)

Let the pointsX 1 andX 2 belong to the feasible setSso that

aX 1 =b, X 1 ≥ 0 (3.12)

aX 2 =b, X 2 ≥ 0 (3.13)

Multiply Eq. (3.12) byλand Eq. (3.13) by( 1 −λ)and add them to obtain

a[λX 1 + ( 1 −λ)X 2 ]=λb+( 1 −λ)b=b

that is,

aXλ=b

where

Xλ=λX 1 + ( 1 −λ)X 2

Thus the pointXλsatisfies the constraints and if

0 ≤λ≤ 1 , Xλ≥ 0

Hence the theorem is proved.

Theorem 3.3Any local minimum solution is global for a linear programming problem.

Proof: In the case of a function of one variable, the minimum (maximum) of a function

f (x)is obtained at a valuexat which the derivative is zero. This may be a point like

A(x=x 1 ) Fig. 3.13, wherein f (x)is only a relative (local) minimum, or a point like

B(x=x 2 ) where, f (x)is a global minimum. Any solution that is a local minimum

solution is also a global minimum solution for the linear programming problem. To see

this, letAbe the local minimum solution and assume that it is not a global minimum

solution so that there is another pointBat whichfB< fA. Let the coordinates ofA

andBbe given by{x 1 , x 2 ,... , xn}Tand{y 1 , y 2 ,... , yn}T, respectively. Then any point

C={z 1 , z 2 ,... , zn}Tthat lies on the line segment joining the two pointsAandBis

Figure 3.13 Local and global minima.