3.6 Solution of a System of Linear Simultaneous Equations 133
a feasible solution andfC= λfA+ ( 1 −λ)fB. In this case, the value off decreases
uniformly fromfAtofB, and thus all points on the line segment betweenAandB
(including those in the neighborhood ofA) havefvalues less thanfAand correspond
to feasible solutions. Hence it is not possible to have a local minimum atAand at the
same time another pointBsuch thatfA>fB. This means that for allB,fA≤fB, so
thatfAis the global minimum value.
The generalized version of this theorem is proved in Appendix A so that it can be
applied to nonlinear programming problems also.
Theorem 3.4Every basic feasible solution is an extreme point of the convex set of
feasible solutions.
Theorem 3.5LetSbe a closed, bounded convex polyhedron withXei, i = 1 top, as
the set of its extreme points. Then any vectorX∈Scan be written as
X=
∑p
i= 1
λiXei
λi≥ 0
∑p
i= 1
λi= 1
Theorem 3.6LetS be a closed convex polyhedron. Then the minimum of a linear
function overSis attained at an extreme point ofS.
The proofs of Theorems 3.4 to 3.6 can be found in Ref. [3.1].
3.6 Solution of a System of Linear Simultaneous Equations
Before studying the most general method of solving a linear programming problem, it
will be useful to review the methods of solving a system of linear equations. Hence
in the present section we review some of the elementary concepts of linear equations.
Consider the following system ofnequations innunknowns:
a 11 x 1 +a 12 x 2 + · · · +a 1 nxn =b 1 (E 1 )
a 21 x 1 +a 22 x 2 + · · · +a 2 nxn =b 2 (E 2 )
a 31 x 1 +a 32 x 2 + · · · +a 3 nxn =b 3 (E 3 )
..
.
..
.
an 1 x 1 +an 2 x 2 + · · · +annxn =bn (En)
(3.14)
Assuming that this set of equations possesses a unique solution, a method of solving
the system consists of reducing the equations to a form known ascanonical form.
It is well known from elementary algebra that the solution of Eqs. (3.14) will not be
altered under the following elementary operations: (1) any equationEris replaced by
