Generating Extreme Point Solutions

Generating Extreme Point Solutions

V O Thomas

Department of Mathematics, Faculty of Science

V O Thomas Department of Mathematics, Faculty of Science 1

 Generating Extreme Point Solutions

Theorem
If an LPP has a feasible solution, then it has a basic feasible solution.

Proof
Let X = (x1 , x2 , · · ·, xn ) be a feasible solution to the LPP.

M ax z = CX M ax z = CX
s.t OR s.t
x 1 P 1 + x 2 P2 + · · · + x n Pn = P0 AX = b
and and
X≥0 X≥0

V O Thomas Department of Mathematics, Faculty of Science 2

 Generating Extreme Point Solutions

Out of n components of the feasible solution, let k components be

positive and the remaining (n − k) components be zero. Let us
assume that the first k components are positive and the last (n − k)
are zero. Then
X = (x1 , x2 , · · ·, xk , 0, · · ·, 0)

If P1 , P2 , · · ·, Pk be the column vectors corresponding to the variables

x1 , x2 , · · ·, xk , then

x1 P1 + x2 P2 + · · · + xk Pk = P0 (1)

Now there are three cases:

(i) k ≤ m and the column vectors are l.i.
(ii) k > m
(iii) k ≤ m and the column vectors are not l.i.

V O Thomas Department of Mathematics, Faculty of Science 3

 Generating Extreme Point Solutions

Case(i)
If k ≤ m and the column vectors P1 , P2 , · · ·, Pk are linearly
independent, then by definition, the feasible solution is the basic
feasible solution. If k = m, the solution is non-degenerate BFS and if
k < m, the solution is degenerate BFS.

Case(ii)
When k > m the column vectors P1 , P2 , · · ·, Pk are not l.i. and hence
the corresponding solution is not basic.
Let α1 , α2 , · · ·, αk are constants not all zero such that

α1 P1 + α2 P2 + · · · + αk Pk = 0.

Suppose for some r, αr 6= 0, then

1
Pr = − [α1 P1 + · · · + αr−1 Pr−1 + αr+1 Pr+1 + · · · + αk Pk ]. (2)
αr

V O Thomas Department of Mathematics, Faculty of Science 4

 Generating Extreme Point Solutions

Now using (2) in (1), we get

k k
X X αj
xj Pj + xr (− Pj ) = P0
j=1 j=1
αr
j6=r j6=r

k
X αj
(xj − xr )Pj = P0 . (3)
j=1
αr
j6=r
α1 α2 αr−1 αr+1
X = (x1 − xr , x2 − xr , · · · , xr−1 − xr , xr+1 − xr
αr αr αr αr
αk
, · · · , xk − xr , 0, · · ·, 0)
αr
containing not more than (k − 1) non-zero components.

V O Thomas Department of Mathematics, Faculty of Science 5

 Generating Extreme Point Solutions

We are not sure that these components are non-negative. If we select

Pr properly we can make components non-negative. For non-negative
components we must have
αj
xj − xr ≥ 0 (4)
αr
xj xr
i.e. − ≥ 0 f or αj > 0.
αj αr
Select
xr xj
= min
j { : αj > 0},
αr αj
αj
then each of the (k − 1) variables xj − α r xr is non-negative.

V O Thomas Department of Mathematics, Faculty of Science 6

 Generating Extreme Point Solutions

So we have a feasible solution with (k − 1) non-zero and non-negative

components. If the corresponding column vectors are linearly
independent, then we have a basic feasible solution.

If the set containing (k − 1) column vectors are linearly dependent, we

repeat the procedure to arrive at a feasible solution with not more
than (k − 2) non-zero components. Repeat the procedure till we get
linearly independent vectors Pj . The resulting solution will be feasible
and basic solution.

(iii) If k = m and column vectors P1 , P2 , · · ·, Pm are not linearly

independent, then the feasible solution is not a basic solution. In this
case applying the above procedure we can obtain a degenerate basic
feasible solution.

V O Thomas Department of Mathematics, Faculty of Science 7

 Generating Extreme Point Solutions

Corollary
There exists only finite number of basic feasible solutions to a LPP.
We have seen this result earlier also. It is because of the fact that
feasible solutions are finite in number,and hence , obviously, basic
feasible solutions are also finite in number.

Example 1
Let x1 = 2 , x2 = 4 , x3 = 1 be a feasible solution to the system of
equations

2x1 − x2 + 2x3 = 2
x1 + 4x2 = 18.

Reduce the given solution to a basic feasible solution.

V O Thomas Department of Mathematics, Faculty of Science 8

 Generating Extreme Point Solutions

Solution
Here !
2 −1 2
A = . (1)
1 4 0
For matrix A , ρ(A) = 2 and hence there are only two linearly
independent columns of A.
If P1 , P2 , P3 denote the columns of A, then

α1 P1 + α2 P2 + α3 P3 = 0

where not all αi = 0. If we let α3 = −1, then

P3 = α1 P1 + α2 P2

V O Thomas Department of Mathematics, Faculty of Science 9

 Generating Extreme Point Solutions

This can be written in the form

! ! !
2 2 −1
= α1 + α2 .
0 1 4

Or equivalently,
2 = 2α1 − α2 ,

0 = α1 + 4α2 .

Solving these equations we get

8 2
α1 = , α2 = −
9 9
Now
xr xj
= min
j { : αj > 0}
αr αj
2 9
= min{ 8 } = (∵ x1 = 2)
9
4

V O Thomas Department of Mathematics, Faculty of Science 10

 Generating Extreme Point Solutions

Then the new solution becomes

xr 8 9
xˆ1 = x1 − α1 = 2 − . = 0,
αr 9 4
xr 9 2 9
xˆ2 = x2 − α2 = 4 − .(− ) = ,
αr 4 9 2
xr 9 13
xˆ3 = x3 − α3 = 1 − (−1). = .
αr 4 4

Thus we have the basic feasible solution

 
0 , 92 , 134
.

V O Thomas Department of Mathematics, Faculty of Science 11

 Generating Extreme Point Solutions

Example 2
The vector (1, 1, 1)T is a feasible solution to the system

x1 + x2 + 2x3 = 4
2x1 − x2 + x3 = 2 .

Reduce the given feasible solution to a basic feasible solution.

Solution
Here !
1 1 2
A = .
2 −1 1
For matrix A , ρ(A) = 2 and hence there are only two linearly
independent columns of A.
Consider

α1 P1 + α2 P2 + α3 P3 = 0.

V O Thomas Department of Mathematics, Faculty of Science 12

 Generating Extreme Point Solutions

Let α3 = −1, then

P3 = α1 P1 + α2 P2
! ! !
2 1 1
= α1 + α2
1 2 −1
which is equivalent to the system

2 = α1 + α2 ,
1 = 2α1 − α2 .

This system has a solution

α1 = 1 , α2 = 1

V O Thomas Department of Mathematics, Faculty of Science 13

 Generating Extreme Point Solutions

Now
xr xj
= min
j { ; αj > 0 }
αr αj
1 1
= min{ , } = 1
1 1

xr
xˆ1 = x1 − α1 = 1 − 1 = 0
αr
xr
xˆ2 = x2 − α2 = 1 − 1 = 0
αr
xr
xˆ3 = x3 − α3 = 1 + 1 = 2
αr
 
∴ The basic feasible solution is 0, 0, 2

V O Thomas Department of Mathematics, Faculty of Science 14

 Generating Extreme Point Solutions

When α3 = 1, then
P3 = −α1 P1 − α2 P2
! ! !
2 1 1
= −α1 − α2
1 2 −1

2 = −α1 − α2
1 = −2α1 + α2

This system has a solution

α1 = −1 , α2 = −1.

V O Thomas Department of Mathematics, Faculty of Science 15

 Generating Extreme Point Solutions

Now
xr xj
= min
j { ; αj > 0 }
αr αj
1
= = 1.
1

xr
xˆ1 = x1 − α1 = 1 + 1 = 2
αr
xr
xˆ2 = x2 − α2 = 1 + 1 = 2
αr
xr
xˆ3 = x3 − α3 = 1 − 1 = 0.
αr
 
∴ The new basic feasible solution is 2, 2, 0

V O Thomas Department of Mathematics, Faculty of Science 16

 Generating Extreme Point Solutions

Example 3
Consider the system of equations

x1 + 2x2 + 4x3 + x4 = 7
2x1 − x2 + 3x3 − 2x4 = 4.

Given that (1, 1, 1, 0) is a feasible solution. Reduce this feasible

solution to a basic feasible solution.
Solution
Here the coefficient matrix is
!
1 2 4 1
A = .
2 −1 3 −2

For the matrix A , ρ(A) = 2 and hence there are only two linearly
independent column vectors.
Consider
α1 P1 + α2 P2 + α3 P3 + α4 P4 = 0.

V O Thomas Department of Mathematics, Faculty of Science 17

 Generating Extreme Point Solutions

Let α3 = −1, α4 = 0, then

α1 P1 + α2 P2 = P3 .

That is
! ! !
1 2 4
α1 + α2 = .
2 −1 3
which is equivalent to the system

α1 + 2α2 = 4
2α1 − α2 = 3

This system has a solution

α1 = 2 , α2 = 1.

V O Thomas Department of Mathematics, Faculty of Science 18

 Generating Extreme Point Solutions

Now
xr xj
= min
j { ; αj > 0 }
αr αj
1 1 1
= min { , } = .
2 1 2
The new solution is
xr 1
xˆ1 = x1 − α1 = 1 − 2. = 0
αr 2
xr 1 1
xˆ2 = x2 − α2 = 1 − 1. =
αr 2 2
xr 1 3
xˆ3 = x3 − α3 = 1 + 1. =
αr 2 2
xr
xˆ4 = x4 − α4 = 0 − 0 = 0.
αr
∴ The basic feasible solution is
 
1 3
0, 2 , 2 , 0 .

V O Thomas Department of Mathematics, Faculty of Science 19

 Generating Extreme Point Solutions

Example 4
If (2, 3, 1) is a feasible solution of the following LPP

M ax z = x1 + 2x2 + 4x3

subject to

2x1 + x2 + 4x3 = 11 , 3x1 + x2 + 5x3 = 14,

and
x1 , x2 , x3 ≥ 0.

Find a basic feasible solution of the LPP.

Solution !
2 1 4
Here A = and ρ(A) = 2. Hence there are two linearly
3 1 5
independent columns of A.

V O Thomas Department of Mathematics, Faculty of Science 20

 Generating Extreme Point Solutions

Consider
α1 P1 + α2 P2 + α3 P3 = 0.

Take α3 = −1, then

P3 = α1 P1 + α2 P2 .

That is ! ! !
4 2 1
= α1 + α2
5 3 1
which is equivalent to the system

2α1 + α2 = 4
3α1 + α2 = 5.

This system has a solution

α1 = 1 , α2 = 2.

V O Thomas Department of Mathematics, Faculty of Science 21

 Generating Extreme Point Solutions

Now
xr xj
= min
j { ; αj > 0 }
αr αj
2 3 3
= min { , } = .
1 2 2
The new solution is
xr 3 1
xˆ1 = x1 − α1 = 2 − 1. =
αr 2 2
xr 3
xˆ2 = x2 − α2 = 3 − 2. = 0
αr 2
xr 3 5
xˆ3 = x3 − α3 = 1 − (−1). = .
αr 2 2

Hence the new basic feasible solution is

 
1 5
2 , 0, 2
.

.
V O Thomas Department of Mathematics, Faculty of Science 22
 Generating Extreme Point Solutions

Generating other extreme point solutions from a given

extreme point solution
Suppose we know an extreme point solution in terms of m vectors Pj
of the original set of n vectors. The solution vector is taken as

X = (x1 , x2 , · · ·, xm , 0, · · ·, 0)

We, then, have

x 1 P1 + x 2 P2 + · · · + x m Pm = P0 (T ake b = P0 ) (1)

where all xi ≥ 0.
With this information, we want to determine another extreme point
solution. Since P1 , P2 , · · ·, Pm are linearly independent, we can express
every vector of the n vectors as a linear combination of m vectors.

V O Thomas Department of Mathematics, Faculty of Science 23

 Generating Extreme Point Solutions

x1j P1 + x2j P2 + · · · + xmj Pm = Pj (j = 1, 2, · · ·, n) (2)

Assume that some vector not in the basis, say Pm+1 , has at least one
elemet xi,m+1 > 0 in the expression

x1,m+1 P1 + x2,m+1 P2 + · · · + xm,m+1 Pm = Pm+1 (3)

Now
Multiplying (3) by θ and subtracting from (1), we get

(x1 −θx1,m+1 )P1 +(x2 −θx2,m+1 )P2 +···+(xm −θxm,m+1 )Pm +θPm+1 = P0
(4)

V O Thomas Department of Mathematics, Faculty of Science 24

 Generating Extreme Point Solutions

This means that the vector

X 0 = (x1 − θx1,m+1 , x2 − θx2,m+1 , · · ·, xm − θxm,m+1 , θ)

is a feasible solution to the problem if all the elements of X 0 are

non-negative. Since we want a different solution, we restrict θ to be
greater than zero. All the elements of X 0 with negative or zero xi,m+1
will also have non-negative xi − θxi,m+1 . So we need only to concern
ourselves with non-negative xi,m+1 . Therefore, we wish to find θ > 0
such that
xi − θxi,m+1 ≥ 0 (5)

for all xi,m+1 > 0.

V O Thomas Department of Mathematics, Faculty of Science 25

 Generating Extreme Point Solutions

From (5), we have

xi
≥θ (6)
xi,m+1
Hence any θ for which (6) holds will give feasible solution for equation
(4). Since we are looking for extreme point solution, we can not have
more than m positive elements in the solution vector (by theorem).
So we must force one element of X 0 exactly equal to zero. This can be
achieved by selecting
xi
θ = θ0 = min
i ( )
xi,m+1

for xi,m+1 > 0. Let this minimum occurs for i = 1, then

x1
θ = θ0 = (7)
x1,m+1

V O Thomas Department of Mathematics, Faculty of Science 26

 Generating Extreme Point Solutions

Using this value of θ, (4) reduces to

x02 P2 + x03 P3 + · · · + x0m Pm + x0m+1 Pm+1 = P0 (8)

where
x0i = xi − θ0 xi,m+1 i = 2, 3, · · ·, m

x0m+1 = θ0 .

Now to show that X 0 = (x02 , x03 , · · ·, x0m , x0m+1 ) is an extreme point, we

have to prove P2 , P3 , · · ·, Pm , Pm+1 are linearly independent.

On the contrary, assume that they are linearly dependent. We can

then find

d2 P2 + d3 P3 + · · · + dm Pm + dm+1 Pm+1 = 0, (9)

where not all di = 0.

V O Thomas Department of Mathematics, Faculty of Science 27

 Generating Extreme Point Solutions

Since any subset of a linearly independent set is linearly independent,

we have dm+1 6= 0. From equation (9), we have

e2 P2 + e3 P3 + · · · + em Pm = Pm+1 (10)

where
−di
ei = .
dm+1
Subtracting (10) from (3), we get

x1,m+1 P1 +(x2,m+1 −e2 )P2 +(x3,m+1 −e3 )P3 +···+(xm,m+1 −em )Pm = 0
(11)

V O Thomas Department of Mathematics, Faculty of Science 28

 Generating Extreme Point Solutions

Since P1 , P2 , · · ·, Pm are all linearly independent all the coefficients in

(11) must be equal to zero. But x1,m+1 was assumed to be postive.
The assumption of linear dependence of P2 , P3 , · · ·, Pm+1 has led to a
contradiction. Hence the vectors must be linearly independent.

Now we have to express vectors which are not in the new basis in
terms of the vectors P2 , P3 , · · ·, Pm+1 . From (3), we have
1
P1 = (Pm+1 − x2,m+1 P2 − · · · − xm,m+1 Pm )
x1,m+1

V O Thomas Department of Mathematics, Faculty of Science 29

 Generating Extreme Point Solutions

Now (2) becomes

Pj = x1j P1 + x2j P2 + · · · + xmj Pm

1
= xij · (Pm+1 −x2,m+1 P2 −···−xm,m+1 Pm )+x2j P2 +···+xmj Pm
x1,m+1
x1j x1j
= (x2j − x2,m+1 )P2 + (x3j − x3,m+1 )P3 + · · ·
x1,m+1 x1,m+1

x1j x1j
+(xmj − xm,m+1 )Pm + Pm+1 .
x1,m+1 x1,m+1
So any vector Pj can be written in terms of P2 , P3 , · · ·, Pm+1 .
Thus we got a new extreme point solution
(∵ P2 , P3 , · · ·, Pm+1 : are l.i.).

X 0 = (x02 , x03 , · · ·, x0m , x0m+1 ).

V O Thomas Department of Mathematics, Faculty of Science 30

 Generating Extreme Point Solutions

Here
x1j x1j
x02 = x2j − x2,m+1 , x03 = x3j − x3,m+1 , · · · ,
x1,m+1 x1,m+1
x1j x1j
x0m = xmj − xm,m+1 , x0m+1 = ,
x1,m+1 x1,m+1
are the m components of the new extreme point solution.

V O Thomas Department of Mathematics, Faculty of Science 31

 Generating Extreme Point Solutions

Example 1
Given the following set of equations

P1 P2 P3 P4 P5 P6 P0
3x1 −x2 +2x3 +x4 = 7
2x1 −4x2 +x5 = 12
−4x1 −3x2 +8x3 +x6 = 10

We have as an initial extreme point solution

x1 = 0, x2 = 0, x3 = 0, x4 = 7, x5 = 12, x6 = 10 which in vector
notation is given by

7P4 + 12P5 + 10P6 = P0 (1)

V O Thomas Department of Mathematics, Faculty of Science 32

 Generating Extreme Point Solutions

Here the basis vectors are unit vectors. We wish to introduce vector
P1 to obtain another extreme point solution. The representation of P1
in terms of basis vectors is

3P4 + 2P5 − 4P6 = P1 (2)

That is
x41 = 3 , x51 = 2 , x61 = −4

Multiply (2) by θ and subtract from (1) , we get

(7 − 3θ)P4 + (12 − 2θ)P5 + (10 + 4θ)P6 + θP1 = P0 (3)

V O Thomas Department of Mathematics, Faculty of Science 33

 Generating Extreme Point Solutions

Since x41 = 3 and x51 = 2 are both positive, we determine θ0 by

xi 7 12 7
θ = θ0 = min
i ( ) = min{ , }=
xi1 3 2 3
Substituting this value of θ in (3), we get
22 58 7
P5 + P6 + P1 = P0
3 3 3
∴ The new extreme point solution is:
7 22 58
x1 = , x2 = 0 , x3 = 0 , x4 = 0 , x5 = , x6 = .
3 3 3

V O Thomas Department of Mathematics, Faculty of Science 34

 Generating Extreme Point Solutions

Instead of taking P1 , if we take P2 , then

−P4 − 4P5 − 3P6 = P2 (4)

Multiply (4) by θ and subtract from (1), we get

(7 + θ)P4 + (12 + 4θ)P5 + (10 + 3θ)P6 + θP2 = P0

For any θ > 0 yield a feasible solution

x1 = 0 , x2 = 0 , x3 = 0 , x4 = 7 + θ , x5 = 12 + θ , x6 = 10 + 3θ. Here
since all xi2 < 0, we will not get a new solution.

V O Thomas Department of Mathematics, Faculty of Science 35

 Generating Extreme Point Solutions

Example 2
The following set of equations has a given extreme point solution
X = (x1 , x2 , x3 ) = (4, 3, 6). Obtain two basic solutions for the bases
P1 , P2 , P4 and P2 , P3 , P4 . In each case, determine the expression for
P5 and the vector eliminated in terms of the new basis

P1 P2 P3 P4 P5 P0
x1 +2x4 −x5 =4
x2 −x4 +x5 =3
x3 +3x4 −2x5 =6

V O Thomas Department of Mathematics, Faculty of Science 36

 Generating Extreme Point Solutions

Solution
Initial extreme point solution can be taken as
x1 = 4, x2 = 3, x3 = 6, x4 = 0, x5 = 0
which can be written as

4P1 + 3P2 + 6P3 = P0 (1)

Now we want a solution by removing P4 into basis and removing P3

from basis. So we express P4 as

2P1 − P2 + 3P3 = P4 (2)

V O Thomas Department of Mathematics, Faculty of Science 37

 Generating Extreme Point Solutions

Multiply (2) by θ and subtract from (1), we get

(4 − 2θ)P1 + (3 + θ)P2 + (6 − 3θ)P3 + θP4 = P0 (3)

Now we find θ0 using

xi 4 6
θ0 = min
i ( ) = min{ , } = 2.
xi4 2 3
Now for find θ = θ0 , (3) becomes

0P1 + 5P2 + 0P3 + 2P4 = P0

0P1 + 5P2 + 2P4 = P0

V O Thomas Department of Mathematics, Faculty of Science 38

 Generating Extreme Point Solutions

Thus we have the new extreme point solution

x01 = 0 , x02 = 5 , x03 = 0 , x04 = 2 , x05 = 0.

 
1 0 2 
 
0 1 −1=36= 0
 
 
0 0 3 

Hence P1 , P2 , P4 are linearly independent.

V O Thomas Department of Mathematics, Faculty of Science 39

 Generating Extreme Point Solutions

Development of Maximum feasible Solution

Let us assume that every basic feasible solution is non-degenerate and
we are given a basic feasible solution. Let it be denoted by

X0 = (x10 , x20 , · · ·, xm0 )

and associated set of linearly independent vectors be

P1 , P2 , · · ·, Pm

Then we have

x10 P1 + x20 P2 + · · · + xm0 Pm = P0 (1)

x10 c1 + x20 c2 + · · · + xm0 cm = z0 (2)

V O Thomas Department of Mathematics, Faculty of Science 40

 Generating Extreme Point Solutions

where all xi0 > 0 (non-degenerate basic feasible solution), ci are

constants appearing in the objective function and z0 is the value of
the objective function for this solution.

Since P1 , P2 , · · ·, Pm are linearly independent, we can express any

vector from the set {P1 , P2 , · · ·, Pn } in terms of P1 , P2 , · · ·, Pm .

x1j P1 + x2j P2 + · · · + xmj Pm = Pj (j = 1, 2, · · ·, n) (3)

x1j c1 + x2j c2 + · · · + xmj cm = zj (j = 1, 2, · · ·, n) (4)

V O Thomas Department of Mathematics, Faculty of Science 41

 Generating Extreme Point Solutions

Theorem
If for any fixed j, the condition zj − cj < 0 holds, then a set of feasible
solution can be constructed in such a way that z > z0 for any member
of the set, where upper bond of the set z is either finite or infinite.

Proof
Consider the equations

x10 P1 + x20 P2 + · · · + xm0 Pm = P0 (1)

x1j P1 + x2j P2 + · · · + xmj Pm = Pj (2)

Multiply (2) by θ and subtract from (1), we get

(x10 − θx1j )P1 + (x20 − θx2j )P2 + · · · + (xm0 − θxmj )Pm + θPj = P0 (3)

V O Thomas Department of Mathematics, Faculty of Science 42

 Generating Extreme Point Solutions

Now consider the equations

x1j c1 + x2j c2 + · · · + xmj cm = zj (4)

x10 c1 + x20 c2 + · · · + xmo cm = z0 (5)

Multiply (4) by θ and subtract from (5), we get

(x10 −θx1j )c1 +(x20 −θx2j )c2 +···+(xm0 −θxmj )cm +θcj = z0 −θ(zj −cj )
(6)
where θcj has been added on both sides of equation (1).

If all coefficients of Pj are non-negative,we have a new feasible solution

(x10 − θx1j , x20 − θx2j , · · ·, xm0 − θxmj , θ).

V O Thomas Department of Mathematics, Faculty of Science 43

 Generating Extreme Point Solutions

The value of objective function corresponding to this solution is

z0 − θ(zj − cj ).
Since the variables x10 , x20 , · · ·, xm0 in (3) are positive, there exists a
value of θ > 0 for which the coefficients of vectors in (3) remain
positive. By our assumption zj − cj < 0 and hence
z = z0 − θ(zj − cj ) > z0 for θ > 0.

If for some stage, for some j , zj − cj < 0 for all xij ≤ 0, there is no
upper bound for θ and the objective function has an upper bound of
∞. The coefficients of (3), in this case, are all postive. Hence by
taking θ arbitary large the R.H.S. of (6) can be made as large as
possible.

V O Thomas Department of Mathematics, Faculty of Science 44

 Generating Extreme Point Solutions

Theorem
If for any basic feasible solution X = (x10 , x20 , · · ·, xm0 ) the conditions
zj − cj ≥ 0 holds for all j = 1, 2, · · ·, n, then the solution of LPP
M ax z = CX , x1 P1 + x2 P2 + · · ·xn Pn = P0 , X ≥ 0 is optimum.

Proof
Let X0 = (x10 , x20 , · · ·, xm0 ) be an optimum(maximum) solution of
the given LPP. Let us consider.

x10 P1 + x20 P2 + · · · + xn0 Pn = P0 (1)

x10 c1 + x20 c2 + · · · + xn0 cn = z0 (2)

V O Thomas Department of Mathematics, Faculty of Science 45

 Generating Extreme Point Solutions

Let Y0 = (y10 , y20 , · · ·, yn0 ) be any other feasible solution of the LPP.
Then
y10 P1 + y20 P2 + · · · + yn0 Pn = P0 (3)

y10 c1 + y20 c2 + · · · + yn0 cn = z ∗ (4)

where z ∗ is the value of the objective function corresponding to the

solution Y0 . To prove the theorem we have to show that z0 ≥ z ∗ . By
hypothesis, zj − cj ≥ 0 for all j = 1, 2, · · ·, n. Since zj is greater than
or equal to cj , for each j, replacing cj by zj in (4), we get

y10 z1 + y20 z2 + · · · + yn0 zn ≥ z ∗ (5)

V O Thomas Department of Mathematics, Faculty of Science 46

 Generating Extreme Point Solutions

Pm
Since we have Pj = i=1 xij Pi , equation (3) can be written as

Xm Xm m
X
y10 ( xi1 Pi ) + y20 ( xi2 Pi ) + · · · + yn0 ( xin Pi ) = P0
i=1 i=1 i=1

which can be written as

n
X n
X n
X
( yj0 x1j )P1 + ( yj0 x2j )P2 + · · · + ( yj0 xmj )Pm = P0 (6)
j=1 j=1 j=1
Pm
Similary since zj = i=1 xij ci , from (5) we have

Xm m
X Xm
y10 ( xi1 ci ) + y20 ( xi2 ci ) + · · · + yn0 ( xin ci ) ≥ z ∗
i=1 i=1 i=1

V O Thomas Department of Mathematics, Faculty of Science 47

 Generating Extreme Point Solutions

n
X n
X n
X
( yj0 x1j )c1 + ( yj0 x2j )c2 + · · · + ( yj0 xmj )cm ≥ z ∗ (7)
j=1 j=1 j=1

Since the vectors P1 , P2 , · · ·, Pm are l.i, the coefficients of Pi in (1)

and (6) must be same. That is
n
X
xi0 = yj0 xij (i = 1, 2, · · ·, m)
j=1

Therefore from (7), we get

x10 c1 + x20 c2 + · · · + xm0 cm ≥ z ∗

implying that z0 ≥ z ∗ .Thus, we found z0 as the maximum value of the

objective function.

V O Thomas Department of Mathematics, Faculty of Science 48