Engineering Optimization: Theory and Practice, Fourth Edition

148 Linear Programming I: Simplex Method

At this stage we notice thatx 3 has the most negative cost coefficient and hence

itshould be brought into the next basis. However, since all the coefficientsa′′i 3 are

negative, the value off can be decreased indefinitely without violating any of the

constraints if we bringx 3 into the basis. Hence the problem has no bounded solution.

In general, if all the coefficients of the entering variablexs(a′′is) havenegative or

zero values at any iteration, we can conclude that the problem has an unbounded

solution.

Example 3.6 Infinite Number of Solutions To demonstrate how a problem having

infinite number of solutions can be solved, Example 3.2 is again considered with a

modified objective function:

Minimizef= − 40 x 1 − 001 x 2

subject to

10 x 1 + 5 x 2 ≤ 5002

4 x 1 + 01 x 2 ≤ 0002

2 x 1 + 3 x 2 ≤ 009

x 1 ≥ 0 , x 2 ≥ 0

SOLUTION By adding the slack variablesx 3 ≥ , 0 x 4 ≥ and 0 x 5 ≥ , the equations 0

can be written in canonical form as follows:

10 x 1 + 5 x 2 +x 3 = 5002

4 x 1 + 01 x 2 +x 4 = 0002

2 x 1 + 3 x 2 +x 5 = 009

− 40 x 1 − 001 x 2 −f = 0

The computations can be done in tableau form as shown below:

Basic Variables

variables x 1 x 2 x 3 x 4 x 5 −f b′′i b′′i/ais′′fora′′is> 0

x 3 10 5 1 0 0 0 2,500 500

x 4 4 10

Pivot

element

0 1 0 0 2,000 200←Smaller value

(x 4 leaves the

basis)

x 5 2 3 0 0 1 0 900 300

−f − 40 − 100 0 0 0 1 0

↑

Most negativec′′i(x 2 enters the basis)