Chapter-2

Simplex Method for Solving Linear

Programming Problems

The Simplex method is similar to the graphical method in that it uses the extreme points
of the feasible region to search for the solution. The main difference is that with the Simplex
method, once the initial vertex has been chosen, movement from one vertex to another is in
such a way that the value of the objective function improves with each move. Although there
are n + m variables in m equations, the solution of the problem concerns the n variables
in the original constraints. If m < n then some of the decision variables will have zero
values.

Before we can employ the Simplex method, we need to rewrite the problem in its
standard form in which the constraints are equations rather than inequalities. First let us see
the form of a general LPP in standard form. Then we will study how to convert an LPP into
its standard form.

Linear Programmes in Standard Form

The standard form of a linear programming problem with ݉ constraints and ݊ variables can
be represented as follows:

Maximize (or Minimize): Z = c1 x1 + c2 x2 + ... + cn xn

Subject to:
a11 x1 + a12 x2 + ... + a1n xn = b1

a21 x1 + a22 x2 + ... + a2 n xn = b2

……………………………………..

29
 ……………………………………..

am1 x1 + am 2 x2 + ... + amn xn = bm

x1 , x2 ,..., xn ³ 0

b1 , b2 ,..., bm ³ 0

Equivalently we can write:

n
Maximize (or Minimize): Z = å ci xi
i =1

Subject to:
n

åa
i =1
x = bk ; bk ³ 0, xi ³ 0; k = 1, 2,..., m
ki i


The Features of the Standard Form of an LPP

The main features of the standard form are:

i. The objective function is of maximization or minimization type

ii. All constraints are expressed as equations
iii. All variables are restricted to be non-negative
iv. The right-hand side constant of each constraint is nonnegative

In matrix-vector notation, the standard LPP can be expressed in compact form as:

Maximize (or Minimize): Z = CX

Subject to: AX = b

X ³0

b³0

30
where A is an m ´ n matrix, X is an n ´ 1 column vector, b is an m ´ 1 column vector and
C is a 1 ´ n row vector.

That is,

é a11 ... a1n ù

A = êê ... ... ... úú ,
êë am1 ... amn úû

é x1 ù é b1 ù
X = êê úú , b = êê úú and
êë xn úû êëbm úû

C = [ c1 cn ]

In practice, A is called the coefficient matrix, X is called the decision vector, b is called the
requirement vector and C is called the profit (cost) vector of the programme.

Example-2.1

Represent the following LPP given in standard form in matrix-vector notation:

Maximize Z = 2 x1 + 4 x2 - 3x3 + x4
Subject to x1 + 2 x2 + x3 + 5 x4 = 10
x2 - 2 x3 + x4 =7
x1 + 7 x2 + 3x3 + x4 = 2
 x1 , x2 , x3 , x4 ³ 0

Solution

The matrix-vector notation of the given standard LPP is:

Maximize Z = CX
Subject to: AX = b
X ³0
b³0
31
 é x1 ù
é1 2 1 5ù êx ú é10 ù
where ê ú
A = ê0 1 - 2 1ú , X = ê ú , b = êê 7 úú
2

ê x3 ú
êë1 7 3 1úû ê ú êë 2 úû
ë x4 û

and C = [2 4 - 3 1]

Reduction of an LPP to the Standard Form

Handling Inequality Constraints

Since the standard form requires all the constraints to be equations, inequality constraints
have to be converted to equations. For this we use two types of variables, called slack
variables and surplus variables.

Consider a constraint of the form:

x1 - 3x2 + x3 £ 10 …………. (1)

We can add a new variable, say x4 ³ 0 in the LHS of (1) so that the LHS of (1) equals 10.

That is,

x1 - 3x2 + x3 + x4 = 10

The variable ‫ݔ‬ସ which we have added to the LHS of (1) is called a Slack Variable.

Now consider another constraint of the form:

3x1 + 2 x2 - x3 + 2 x4 ³ 25 …………. (2)

Here, we can subtract a new variable, say x5 ³ 0 from the LHS of (2) so that the LHS of

(2) equals 25.

That is, 3x1 + 2 x2 - x3 + 2 x4 - x5 = 25

32
The variable x5 which we have subtracted from the LHS of (2) is called a Surplus Variable.

It should be emphasized here that slack and surplus variables are as much a part of the
original problem as the variables used in the formulation of the linear program. These
variables can remain positive throughout and their values in the optimal solution give useful
information about the problem. Slack variable corresponds to unused resource whereas
surplus variable corresponds to the amount by which a solution value exceeds a resource.

Handling Variables with Unrestricted Sign

In some situations, it may become necessary to introduce a variable that that can assume
both positive and negative values. For example, consider an investment problem where an
investor has $100 cash on hand and can borrow money if necessary for investment. If x1

denotes the amount invested, then the investment constraint can be written as:

‫ݔ‬ଵ ൅ ‫ݔ‬ଶ ൌ ͳͲͲ

Here, x2 can assume positive or negative values depending on whether x2 represents money

saved or money borrowed. In this case, x2 is called an unrestricted variable.

Since the standard form requires all the variables to be nonnegative, an unrestricted variable
is generally replaced by the difference of two nonnegative variables. In other words, x2 may

be replaced using the following transformation,

x2 = x2¢ - x2¢¢ ; with x2¢ , x2¢¢ ³ 0

Then the value of x2 is positive or negative depending on whether x2¢ is larger or smaller

than x2¢¢ .

Handling Right-Hand Side Constants with Negative Sign

Since the standard form requires the right hand side constants of each constraint to be
nonnegative, we multiply each term of a constraint with –1, if a constraint is having negative

33
right hand side constant. It is to be noted that when either sides of an inequality is multiplied
by –1, the inequality will change to its opposite.

Consider a constraint of the form:

2 x1 - x2 + 5 x3 ³ -8 …………. (3)

Right hand side constant of (3) is negative. When we multiply each term of (3) by –1, it
becomes,

-2 x1 + x2 - 5x3 £ 8

Example-2.2

Write the following LPP in the standard form:

Minimize Z = x1 + 2 x2 - 3x3
Subject to 3x1 + x2 + 5 x3 £ 2

x2 - x3 =5

5 x1 + 3x2 + 8 x3 ³ 10

x1 + 2 x2 + 3x3 ³ -6

x1 , x3 ³ 0 ; x2 unrestricted

Solution:

Constraint (i) may be written as:

3x1 + x2 + 5 x3 + x4 = 2 , where x4 is a slack variable

Constraint (ii) is given as equation itself.

Constraint (iii) may be written as:

5 x1 + 3x2 + 8 x3 - x5 = 10 , where x5 is a surplus variable

Constraint (iv) may be written as:

34
 - x1 - 2 x2 - 3x3 + x6 = 6 , where x6 is a slack variable

Since the variable x2 is unrestricted, it may be replaced as x2 = x2¢ - x2¢¢ , where both x2¢

and x2¢¢ are nonnegative. Corresponding change may be done throughout the problem. That

is, x2 should be replaced by x2¢ - x2¢¢ in the objective function as well as in the constraints.

Thus, the standard form will be:

Minimize Z = x1 + 2 x2¢ - 2 x2¢¢ - 3x3

Subject to 3 x1 + x2¢ - x2¢¢ + 5 x3 + x4 = 2

x2¢ - x2¢¢ - x3 = 5

5 x1 + 3 x2¢ - 3 x2¢¢ + 8 x3 - x5 = 10

- x1 - 2 x2¢ + 2 x2¢¢ - 3x3 + x6 = 6

x1 , x2¢ , x2¢¢ , x3 , x4 , x5 , x6 ³ 0

Basic Variables

Consider a system of linear equations. A variable x1 is called a basic variable in a given

equation if it appears with a unit coefficient in that equation and zero in all other equations.
Those variables which are not basic are called non-basic variables.

By applying the elementary row operations, a given variable can be made a basic variable.
In order to get a canonical system, a sequence of such elementary row operations must be
performed on the system of equations so that there exists at least one basic variable in each
equation. The number of basic variables is decided by the number of equations in the system.

Basic Solution

The solution obtained from a canonical system by setting the non-basic variables to zero and
solving for the basic variables is called a basic solution. Since the values of all the variables

35
are nonnegative, this basic solution is also a feasible solution. We call such basic solutions
basic feasible solutions.

Basic Feasible Solution

A basic feasible solution is a basic solution in which the values of the basic variables are
nonnegative.

Note that a basic feasible solution may not necessarily optimise the objective function.

The standard LPP contains ݉ simultaneous linear equations in ݊ variables. If the ݉

equations yield a unique solution, then the associated ݉ variables are called basic variables
and the remaining n - m variables are called non-basic variables. in this case, the resulting
unique solution comprises a basic solution. If all the variables assume non-negative values,
then the basic solution is called basic feasible solution. The maximum number of possible
n!
basic solution for ݉ equations in ݊ variables is nCm =
m !( n - m )!

Example-2.3

Consider the equations:

x1 + x2 + 4 x3 + 2 x4 + 3x5 = 8
4 x1 + 2 x2 + 2 x3 + x4 + 6 x5 = 4
(i) A Basic Feasible Solution

Let x1 and x3 are basic variables and x2 , x4 , x5 are non-basic variables.

Hence we get:
x1 + 4 x3 = 8

4 x1 + 2 x3 = 4

The solution is unique with x1 = 0, x3 = 2 . Since the basic variables are non-negative, this

solution is a basic feasible solution.

36
 (ii) An Infeasible Basic Solution

Let x1 and x2 are basic variables and x3 , x4 , x5 are non-basic variables.

Hence we get:

x1 + x2 = 8

4 x1 + 2 x2 = 4

The solution is unique with x1 = -6, x2 = 14

Since the basic variable x1 is negative, this solution is a basic infeasible solution.

Simplex Method
A naïve approach to solve a linear program (which has an optimal solution) would be to
generate all possible basic feasible solutions through canonical reduction and determine the
basic feasible solution which optimizes the objective function. But this is tiresome and
sometimes awful. We use simplex method which is more efficient in finding the optimal
solution by examining only a fraction of the total number of basic feasible solutions.

The simplex method is developed by G.B.Dantzig. It uses an iterative procedure for solving
linear programming problems expressed in standard form. Here, the basic objective is to find
a basic feasible solution to a given LP problem.

The general steps of the simplex method are as follows:

i. Start with an initial basic feasible solution

ii. Improve the initial solution if possible by finding another basic feasible solution with
a better objective function value.
iii. Continue to find better basic feasible solutions improving the objective function
values. When a particular basic feasible solution cannot be improved further, it
becomes an optimal solution and the method terminates.

Before starting with the simplex tableau, the following requirements are to be met.

37
 a. All the constraints should be expressed as equations
b. The RHS of each constraint should be non-negative
c. All the decision variables must be non-negative
d. The objective function should be in maximization form

Notes:

a. The first three conditions given above make the LPP in standard form. The fourth
condition is not necessary; simplex method may be used to LPP with objective
functions in minimization form as well. But, the condition is insisted for convenience
sake. If the given problem is of minimization type, it may be converted to the
maximization type by changing the sign of the objective function, without making
any change in the constraints. For example, if the problem is to Minimize
Z = 3x1 + 2 x2 , then it may be converted to a problem of maximization type as:
Maximize -Z = -3x1 - 2 x2
b. Three types of additional variables are used in simplex method. Two of them,
namely, slack variable and surplus variable, had mentioned earlier. Another type of
additional variables, called artificial variables, is used independently or along with
surplus variables to get an initial feasible solution.

The Simplex Procedure

Let us consider now the case with maximisation type problems. The Simplex procedure
involves the following steps:

Step 1: Finding the initial basic feasible solution

The simplest choice of an initial feasible basic is to assume that none of the decision
variables are basic. Hence we initially assume that the basic solution consists only of the
slack variables. For that set xi = 0; i = 1, 2,..., n and xn+ k ¹ 0; k = 1, 2,..., m. This

choice of the initial solution means that we initially assume that objective functional value
is zero. In terms of the graphical method we start at the origin so as to move along the best
possible route to the optimal solution.

38
Step 2: Setting up the initial Simplex tableau

In this step we arrange the various matrices and vectors involved in the matrix form of the
linear programming problem in the simplex tableau. This tableau contains all the information
about the current basic variables and their corresponding values, the optimality status of the
solution. The method then continues to use the principle of the Gauss-Jordan procedure to
compute the next improved solution.

A typical initial simplex tableau has the form shown in Table 2.2

Table-2.2 Initial Simplex Tableau

Basic  Coeff.  x1 x2 … xn xn+1 xn+ 2 …. xn+ m b
XB CB …
xn+1 0 a11 a12 … a1n 1 0 …. 0 b1

xn+ 2 0 a21 a22 … a2n 0 1 …. 0 b2

… … … … … … … … … … …

xn+ m 0 am1 … … amn 0 … … 1 bm

Zj 0 0 … 0 0 0 … 0

Cj c1 c2 … cn 0 0 … 0
0
Z j - Cj -c1 -c2 … -cn 0 0 … 0

In the tableau:
i. The top row shows both the n + m decision and slack/surplus/artificial variables 
x1 , x2 ,..., xn+1 , ..., xn+ m as labels for the corresponding columns
ii. The middle rows shows the coefficients of the constraints
iii. The last but second row shows the coefficients of the objective function
39
 iv. The last but first row shows the sum of the products of the entries in the second
column with the entries in the corresponding columns
v. The last row is Z j - C j , obtained by subtracting corresponding entry in the last but

second row from the corresponding entry in the last but first row
vi. The extreme left column shows the basic variables
vii. The second column shows the coefficients of the basic variables in the objective
function; and
viii. The last column shows the constant term in the RHS of each constraint.

Note that:

a. Each basic variable appears in exactly one equation in which it has a coefficient 1.
b. The column it labels has all zeros except in the row in which it is shown as a basic
variable.
c. Each basic variable has a value shown on the extreme right column.

Step 3: Testing for optimality

At any stage of the procedure we can check whether the current basic solution is optimal.
This information is contained in the last row of the tableau. If all the entries in the last row
are nonnegative, then the current basic solution is optimal. In particular all the columns
associated with the basic solution will have zero coefficients in the last row while the
columns associated with the nonbasic variables will have positive coefficients.

Step 4: Choosing the incoming / outgoing vector

First we decide which of the nonbasic variables will bring about the best improvement on
the objective value if entered into the basic set. That is, if it is increased from zero. The
nonbasic variables corresponding to the negative coefficients in the objective row are
candidates for entry into the basic set. The entering variable is the one associated with the
column with the most negative coefficient in the last row. This column is known as the pivot
column. Since this variable will become basic, one of the basic variables will have to become
nonbasic (or will leave the basic set) and be reduced to zero. The leaving variable is
determined by the ratio of the last column and the pivot column. We first compute quotients

40
of the last column and positive coefficients of the pivot column. Thus we compare only
positive ratios. Once we have computed all positive ratios, we choose the row which has the
minimum ratio. This is called the pivot row. The leaving variable is the one which
corresponds to the pivot row on the left hand side of the tableau (among the basic variables).
The element at the intersection of the pivot row and pivot column is called the pivot element.
It is normally highlighted by circling it (we will highlight it by enclosing by a square). It is
necessary to identify this element in order to move on to the next step.

Step 5: Updating the Simplex tableau

The next step is to update the tableau by reducing it using the Gauss reduction principle. By
updating the tableau we are essentially determining the effect of the introduction of the new
basic variable and discarding the one that has left the basis. By Gauss reduction, we reduce
the pivot element to one and all other entries in that column to zero.

Step 6: Repeating Steps 3 – 5

Test for optimality again until the optimal solution is obtained or some other conclusion is
made of the problem.

The Optimal Solution

Once the optimality test is met (that is, all the coefficients in the Z j - C j row are

nonnegative), we can extract the solution from the final tableau. The optimal solution
consists of the basic decision variables appearing in the extreme left column. The
corresponding values appear in the extreme right column. Any decision variable which is
not in the basic set has a zero value.
We will now solve the following linear programming problems to illustrate the
implementation of the complete Simplex algorithm.

Some Variants in the Simplex Method

i. Infeasibility
If, when the final solution reached, one or more artificial variables are still
positive, then there will be no feasible solution to the problem. The reason for
41
 this situation is that the model is either improperly formulated or two or more of
the constraints are incompatible. When an infeasible solution exists, the problem
should be re-formulated.

ii. Unboundedness
If all the elements in the key column are negative, then it indicates the existence
of unbounded solution. In general, an unbounded solution occurs due to the
wrong formulation of a problem within the constraints set, and thus needs
reformulation.

iii. Alternate Solution

In an optimal simplex table, if zero occurs for non-basic variables in the Z j - C j

row, it indicates that the LPP has alternate solution.

iv. Tie in incoming/ outgoing vectors

If there comes a tie in selecting the incoming vector, we may select one of them
arbitrarily, preferably the left most. If the tie is between a decision variable and
an additional variable (slack or surplus or artificial), the decision variable should
be selected.

v. Problem of Degeneracy
In order to get a basic feasible solution for an LPP, the number of non-zero valued
variables should be equal to the number of constraints. If one of the basic
variables is zero, this cannot be achieved. In such cases, we cannot go to the next
simplex table, as the variable to be replaced is already zero. This situation is
called degeneracy. That is, a basic feasible solution of an LPP is said to be
degenerate if at least one of the basic variables is zero. Degeneracy may appear
in an LPP either in the first iteration or in any subsequent iteration. In some cases,
the degeneracy that appeared in the first iteration may disappear in the subsequent
stages. The degeneracy that appear in later iterations can be get avoided by
properly choosing the minimum ratio.

42
Example-2.4
Solve the following LPP using Simplex Method

Maximize Z = 7 x1 + 5 x2
Subject to
x1 + 2 x2 £ 6
4 x1 + 3x2 £ 12
x1 , x2 ³ 0
Solution:
The standard form is:
Maximize Z = 7 x1 + 5 x2 + 0 x3 + 0 x4
Subject to x1 + 2 x2 + x3 = 6
4 x1 + 3x2 + x4 = 12
 x1 , x2 , x3 , x4 ³ 0

Table-1
XB CB x1 x2 x3 x4 b b / x1

x3 0 1 2 1 0 6 6

x4 0 4 3 0 1 12 3®

Zj 0 0 0 0

Cj 7 5 0 0

Z j - Cj -7 ­ –5 0 0

In table-1, all Z j - C j ³ 0 .Hence the solution is not optimal. x1 enters the basis and x4

leaves the basis.

43
 Table-2

XB CB x1 x2 x3 x4 b

x3 0 0 5/4 1 –1/4 3

x1 7 ͳ 3/4 0 1/4 3

Zj 7 21/4 0 7/4

Cj 7 5 0 0

Z j - Cj Ͳ 1/4 0 7/4

In table-2, all Z j - C j ³ 0 . Hence the solution is optimal.

Solution is: x1 = 3, x2 = 0; Z = 21

Example-2.5

Solve the following LPP using Simplex Method

Maximize Z = 3x1 + 2 x2

Subject to

x1 + x2 £ 4

x1 - x2 £ 2

x1 , x2 ³ 0

Solution:

The standard form is:

Maximize Z = 3x1 + 2 x2 + 0 x3 + 0 x4
44
Subject to x1 + x2 + x3 = 4
x1 - x2 + x4 = 2
 x1 , x2 , x3 , x4 ³ 0

Table-1
XB CB x1 x2 x3 x4 b b / x1

x3 0 1 1 1 0 4 4

x4 0 1 –1 0 1 2 2®

Zj 0 0 0 0

Cj 3 2 0 0

Z j - Cj -3 ­ –2 0 0

In table-1, all Z j - C j ³ 0 .Hence the solution is not optimal. x1 enters the basis and x4

leaves the basis.

Table-2
XB CB x1 x2 x3 x4 b b / x2

x3 0 0 2 1 –1 2 1®

x1 3 1 –1 0 1 2 –

Zj 3 –3 0 3

Cj 3 2 0 0

Z j - Cj 0 -5 ­ 0 3

In table-2, all Z j - C j ³ 0 .Hence the solution is not optimal. x2 enters the basis and x3

leaves the basis.

45
 Table-3
XB CB x1 x2 x3 x4 b

x2 2 0 1 1/2 –1/2 1

x1 3 1 0 1/2 1/2 3

Zj 3 2 5/2 1/2

Cj 3 2 0 0

Z j - Cj Ͳ 0 5/2 1/2

In table-3, all Z j - Cj ³ 0 . Hence the solution is optimal. Solution is:

x1 = 3, x2 = 1; Z = 11

Example-2.6

Solve the following LPP using Simplex Method

Maximize Z = 6 x1 + 4 x2

Subject to

-2 x1 + x2 £ 2

x1 - x2 £ 2

3x1 + 2 x2 £ 9

x1 , x2 ³ 0

Solution:

The standard form is:

Maximize Z = 6 x1 + 4 x2 + 0 x3 + 0 x4 + 0 x5
Subject to -2 x1 + x2 + x3 = 2
x1 - x2 + x4 = 2

46
 3x1 + 2 x2 + x5 = 9
 x1 , x2 , x3 , x4 , x5 ³ 0

Table-1
XB CB x1 x2 x3 x4 x5 b b / x1

x3 0 –2 1 1 0 0 2 –

x4 0 1 –1 0 1 0 2 2®

x5 0 3 2 0 0 1 9 3

Zj 0 0 0 0 0

Cj 6 4 0 0 0

Z j - Cj -6 ­ –4 0 0 0

In table-1, all Z j - C j ³ 0 .

Hence the solution is not optimal. x1 enters the basis and x4 leaves the basis.

Table-2
XB CB x1 x2 x3 x4 x5 b b / x2

x3 0 0 –1 1 2 0 6 –

x1 6 1 –1 0 1 0 2 –

x5 0 0 5 0 –3 1 3 3/ 5 ®

Zj 6 –6 0 6 0

Cj 6 4 0 0 0

Z j - Cj 0 -10 ­ 0 6 0

In table-2, all Z j - C j ³ 0 .Hence the solution is not optimal. x2 enters the basis and x5

leaves the basis.

47
 Table-3
XB CB x1 x2 x3 x4 x5 b

x3 0 0 0 1 7/5 1/5 33/5

x1 6 1 0 0 2/5 1/5 13/5

x2 4 0 1 0 –3/5 1/5 3/5

Zj 6 4 0 0 2

Cj 6 4 0 0 0

Z j - Cj 0 0 0 0 2

In table-3, all Z j - C j ³ 0 . Hence the solution is optimal.

Solution is: x1 = 13/ 5, x2 = 3/ 5; Z = 18

Example-2.7

Solve the following LPP using Simplex Method

Maximize Z = 3x1 + 5 x2 + 4 x3

Subject to
2 x1 + 3x2 £ 8
2 x2 + 5 x3 £ 10
3x1 + 2 x2 +4x3 £ 15
x1 , x2 , x3 ³ 0

Solution:

The standard form is:

48
 Maximize Z = 3x1 + 5 x2 + 4 x3 + 0 x4 + 0 x5 + 0 x6
Subject to 2 x1 + 3x2 + x4 =8
2 x2 + 5 x3 + x5 = 10
3x1 + 2 x2 + 4 x3 + x6 = 15
 x1 , x2 , x3 , x4 , x5 , x6 ³ 0

Table-1
XB CB x1 x2 x3 x4 x5 x6 b b / x1

x4 0 2 3 0 1 0 0 8 8/3 ®

x5 0 0 2 5 0 1 0 10 5

x6 0 3 2 4 0 0 1 15 15/2

Zj 0 0 0 0 0 0

Cj 3 5 4 0 0 0

Z j - Cj –3 -5 ­ –4 0 0 0

In table-1, all Z j - C j ³ 0 . Hence the solution is not optimal. x2 enters the basis and x4

leaves the basis.

Table-2
XB CB x1 x2 x3 x4 x5 x6 b b / x3

x2 5 2/3 1 0 1/3 0 0 8/3 –

x5 0 –4/3 0 5 –2/3 1 0 14/3 14 /15 ®

x6 0 5/3 0 4 –2/3 0 1 29/3 29/12

Zj 10/3 5 0 5/3 0 0

Cj 3 5 4 0 0 0

Z j - Cj 1/3 0 -4 ­ 5/3 0 0

In table-2, all Z j - C j ³ 0 . Hence the solution is not optimal. x3 enters the basis and x5

leaves the basis.

49
 Table-3
XB CB x1 x2 x3 x4 x5 x6 b b / x1

x2 5 2/3 1 0 1/3 0 0 8/3 4

x3 4 –4/15 0 1 –2/15 1/5 0 14/15 –

x6 0 41/15 0 0 –2/15 –4/5 1 89/15 89 / 41 ®

Zj 34/15 5 4 17/15 4/5 0

Cj 3 5 4 0 0 0

Z j - Cj -11/15 ­ 0 0 17/15 4/5 0

In table-3, all Z j - C j ³ 0 . Hence the solution is not optimal. x1 enters the basis and x6

leaves the basis.

Table-4
XB CB x1 x2 x3 x4 x5 x6 b

x2 5 0 1 0 15/41 8/123 –10/41 50/41

x3 4 0 0 1 –6/41 107/615 4/15 62/41

x1 3 1 0 0 –2/41 –4/41 15/41 89/41

Zj 3 5 4 45/41 448/615 581/615

Cj 3 5 4 0 0 0

Z j - Cj 0 0 0 45/41 448/615 581/615

In table-4, all Z j - Cj ³ 0 . Hence the solution is optimal. Solution is:

x1 = 89 / 41, x2 = 50 / 41, x3 = 62 / 41; Z = 765/ 41

50
Example-2.8

Solve the following LPP using Simplex Method

Maximize Z = 2 x1 + x2

Subject to
x1 - x2 £ 2
2 x1 - x2 £ 3
x1 , x2 ³ 0

Solution:
The standard form is:
Maximize Z = 2 x1 + x2 + 0 x3 + 0 x4
Subject to x1 - x2 + x3 =2
2 x1 - x2 + x4 =3
 x1 , x2 , x3 , x4 ³ 0

Table-1

XB CB x1 x2 x3 x4 b b / x1

x3 0 1 –1 1 0 2 2

x4 0 2 –1 0 1 3 3
®
2
Zj 0 0 0 0

Cj 2 1 0 0

Z j - Cj -2 ­ –1 0 0

In table-1, all Z j - C j ³ 0

Hence the solution is not optimal. x1 enters the basis and x4 leaves.

51
 Table-2
XB CB x1 x2 x3 x4 b b / x1

x3 0 0 –1/2 1 –1/2 1/2 –

x1 2 1 –1/2 0 1/2 3/2 –

Zj 2 –1 0 1

Cj 2 1 0 0

Z j - Cj 0 -2 ­ 0 1

Since there is no outgoing vector, the solution is unbounded.

Example-2.9
Solve the following LPP using Simplex Method
Maximize Z = 4 x1 + 4 x2
Subject to
x1 + 2 x2 £ 10
x1 + x2 £6
x1 £4
x1 , x2 ³ 0
Solution:
The standard form is:
Maximize Z = 4 x1 + 4 x2 + 0 x3 + 0 x4 + 0 x5
Subject to x1 + 2 x2 + x3 = 10
x1 + x2 + x4 =3
x1 + x5 =4
 x1 , x2 , x3 , x4 , x5 ³ 0

52
 Table-1
XB CB x1 x2 x3 x4 x5 b b / x1

x3 0 1 2 1 0 0 10 10

x4 0 1 1 0 1 0 6 6

x5 0 1 0 0 0 1 4 4®

Zj 0 0 0 0 0

Cj 4 4 0 0 0

Z j - Cj -4 ­ –4 0 0 0

In table-1, all Z j - C j ³ 0 . Hence the solution is not optimal. x1 enters the basis and x5

leaves.
Table-2
XB CB x1 x2 x3 x4 x5 b b / x2

x3 0 0 2 1 0 –1 6 3

x4 0 0 1 0 1 –1 2 2®

x1 4 1 0 0 0 1 4 –

Zj 4 0 0 0 4

Cj 4 4 0 0 0

Z j - Cj 0 -4 ­ 0 0 4

In table-2, all Z j - C j ³ 0 .

Hence the solution is not optimal. x2 enters the basis and x4 leaves.

53
 Table-3
XB CB x1 x2 x3 x4 x5 b

x3 0 0 0 1 –2 1 2

x2 4 0 1 0 1 –1 2

x1 4 1 0 0 0 1 4

Zj 4 4 0 4 0

Cj 4 4 0 0 0

Z j - Cj 0 0 0 4 0

In table-3, all Z j - Cj ³ 0 . Hence the solution is optimal. Solution is:

x1 = 4, x2 = 2; Z = 24 [Since the Z j - C j value of the non-basic variable x5 is zero,

the LPP has alternate solutions].

Exercise 2
1. What is simplex method? What is it used for?
2. Write a general LPP in standard form.
3. Write the main features of an LPP in standard form.
4. Write a general LPP in the standard form in its matrix-vector form.
5. Define slack and surplus variables.
6. Define the terms:
i. Basic variable
ii. Basic solution
iii. Feasible solution
iv. Basic feasible solution

54
7. Write the simplex procedure.
8. Explain the terms:
i. Pivot column
ii. Pivot row
iii. Minimum ratio
iv. Pivot element
v. Incoming vector
vi. Outgoing vector
9. Explain the following with respect to a simplex table:
i. Infeasibility
ii. Unboundedness
iii. Degeneracy
iv. Alternate solution
10. Transform the following linear programs to the standard form:

i. Maximize Z = x1 + 2 x2
Subject to x1 + 2 x2 £ 4

x1 + 7 x2 £ 14

x1 - x2 £1

x1 , x2 ³ 0 
ii. Minimize Z = 3x1 + 2 x2 + 10 x3

Subject to - x1 + x2 + 4 x3 ³ 4

x1 + 4 x3 ³1

x1 - x2 + 2 x3 £ 6

x1 , x2 , x3 ³ 0 
iii. Minimize Z = x1 + x2 + 2 x3 + x4 + x5

Subject to - x1 + x2 + x4 + x5 = 10

3x1 - x2 - 2 x3 + 4 x4 + 2 x5 ³ 3

55
 x1 , x2 , x3 , x4 , x5 ³ 0 

iv. Maximize Z = 3x1 + 4 x2

Subject to - x1 - 2 x2 £ -3

3x1 - 2 x2 ³ 3

x1 - 4 x2 ³ -2

x1 ³ 10

x1 , x2 ³ 0 

v. Minimize Z = 2 x1 + 2 x2 + 7 x3

Subject to 8 x1 + 2 x2 + 5 x3 £1

3x1 + 10 x2 + 10 x3 £ -5

2 x1 - x2 + 4 x3 ³ -7

4 x1 - x2 ³1

x1 , x2 , x3 ³ 0 

vi. Maximize Z = 4 x1 + 7 x2

Subject to 3x1 + x2 £ 4

x1 + x2 £ 2

x1 - 2 x2 £ 10

x1 ³ 0, x2 unrestricted

11. Consider a system of two equations in five unknowns as follows:

x1 + 2 x2 + 10 x3 + 4 x4 - 2 x5 = 5
x1 + x2 + 4 x3 + 3x4 + x5 = 8
x1 , x2 , x3 , x4 , x5 ³ 0 

56
 i. Reduce the system to canonical form with respect to ( x1 , x2 ) as basic variables.

Write down the basic solution. Is it feasible? Why or why not?

ii. What is the maximum number of basic solutions possible?
iii. Find a canonical system which will give a basic feasible solution to the above
system by trial and error.

12. Consider the following linear program:

Maximize Z = x1 + x2 + 2 x3 + x4 + x5
Subject to - x1 + x2 + x3 + x5 = 1
x1 + x2 + x4 =2
2 x1 + x2 + x3 + x6 = 6
x1 , x2 , x3 , x4 , x5 , x6 ³ 0 
i. Write down the initial basic feasible solution by inspection
ii. Find a feasible solution by increasing the non-basic variable x1 by 1 unit, while

holding x2 and x3 zero. What will be the net change in the objective function?

iii. What is the maximum increase in x1 possible, subject to the constraints?

iv. Find the new basic feasible solution when x1 is increased to its maximum value

found in (iii).
v. Is the new basic feasible solution obtained in (iv) optimal? Why or why not?

13. Solve the following LP problems using Simplex Method:

i. Maximize ܼ ൌ ͵‫ݔ‬ଵ ൅ ʹ‫ݔ‬ଶ

Subject to െ‫ݔ‬ଵ ൅ ʹ‫ݔ‬ଶ  ൑ Ͷ
͵‫ݔ‬ଵ ൅ ʹ‫ݔ‬ଶ  ൑ ͳͶ
‫ݔ‬ଵ െ ‫ݔ‬ଶ  ൑ ͵
‫ݔ‬ଵ ǡ ‫ݔ‬ଶ  ൒ Ͳ
[‫ݏ݊ܣ‬Ǥ‫ݔ‬ଵ ൌ ʹǡ ‫ݔ‬ଶ ൌ ͳǡ ܼ ൌ ͺ]

ii. Minimize ܼ ൌ ͶͲ‫ݔ‬ଵ ൅ ͵͸‫ݔ‬ଶ

57
 Subject to ‫ݔ‬ଵ  ൑ ͺ
‫ݔ‬ଶ  ൑ ͳͲ
ͷ‫ݔ‬ଵ ൅ ͵‫ݔ‬ଶ  ൒ Ͷͷ
‫ݔ‬ଵ ǡ ‫ݔ‬ଶ  ൒ Ͳ

iii. Minimize ܼ ൌ ʹ‫ݔ‬ଵ ൅ ͵‫ݔ‬ଶ

Subject to ʹ‫ݔ‬ଵ ൅ ‫ݔ‬ଶ  ൑ ʹ
‫ݔ‬ଵ ൅ ʹ‫ݔ‬ଶ  ൑ ͷ
‫ݔ‬ଵ ǡ ‫ݔ‬ଶ  ൒ Ͳ
[‫ݏ݊ܣ‬Ǥ‫ݔ‬ଵ ൌ Ͳǡ ‫ݔ‬ଶ ൌ ʹǡ ܼ ൌ ͸]
iv. Maximize ܼ ൌ ʹ‫ݔ‬ଵ ൅ ͵‫ݔ‬ଶ
Subject to ‫ݔ‬ଵ െ ‫ݔ‬ଶ  ൑ ʹ
െ͵‫ݔ‬ଵ ൅ ‫ݔ‬ଶ  ൑ Ͷ
‫ݔ‬ଵ ǡ ‫ݔ‬ଶ  ൒ Ͳ
[‫ݏ݊ܣ‬Ǥ‫]݀݁݀݊ݑ݋ܾ݊ݑ‬
v. Maximize ܼ ൌ ‫ݔ‬ଵ ൅ ͵‫ݔ‬ଶ
Subject to ‫ݔ‬ଵ  ൑ ͷ
‫ݔ‬ଵ ൅ ʹ‫ݔ‬ଶ  ൑ ͳͲ
‫ݔ‬ଶ  ൑ Ͷ
‫ݔ‬ଵ ǡ ‫ݔ‬ଶ  ൒ Ͳ
[‫ݏ݊ܣ‬Ǥ‫ݔ‬ଵ ൌ ʹǡ ‫ݔ‬ଶ ൌ Ͷǡ ܼ ൌ ͳͶ]
14. Use the simplex method to solve:
Minimize ܼ ൌ ͵‫ݔ‬ଵ ൅ ‫ݔ‬ଶ ൅ ‫ݔ‬ଷ ൅ ‫ݔ‬ସ
Subject to െʹ‫ݔ‬ଵ ൅ ʹ‫ݔ‬ଶ ൅ ‫ݔ‬ଷ  ൌ Ͷ
͵‫ݔ‬ଵ ൅ ‫ݔ‬ଶ ൅ ‫ݔ‬ସ ൌ ͸
‫ݔ‬ଵ ǡ ‫ݔ‬ଶ ǡ ‫ݔ‬ଷ ǡ ‫ݔ‬ସ  ൒ Ͳ
Find an alternative optimal solution if one exists.
15. Use the simplex method to solve:
Maximize ܼ ൌ ‫ݔ‬ଵ ൅ ʹ‫ݔ‬ଶ ൅ ͵‫ݔ‬ଷ ൅ Ͷ‫ݔ‬ସ
Subject to ‫ݔ‬ଵ ൅ ʹ‫ݔ‬ଶ ൅ ʹ‫ݔ‬ଷ ൅ ͵‫ݔ‬ସ  ൑ ʹͲ
ʹ‫ݔ‬ଵ ൅ ‫ݔ‬ଶ ൅ ͵‫ݔ‬ଷ ൅ ʹ‫ݔ‬ସ  ൑ ʹͲ
‫ݔ‬ଵ ǡ ‫ݔ‬ଶ ǡ ‫ݔ‬ଷ ǡ ‫ݔ‬ସ  ൒ Ͳ
Is the optimal solution unique? Why or why not?

58
16. Use the big ‫ ܯ‬simplex method to show that the following LPP is infeasible:
Minimize ܼ ൌ ʹ‫ݕ‬ଵ ൅ Ͷ‫ݕ‬ଶ
Subject to Ͷ‫ݕ‬ଵ െ ͵‫ݕ‬ଶ  ൒ ʹ
െ‫ݕ‬ଵ ൅ ‫ݕ‬ଶ  ൒ ͵
‫ݕ‬ଵ ǡ ‫ݕ‬ଶ  ൒ Ͳ
17. Consider the following linear program:
Minimize ܼ ൌ ʹ‫ݔ‬ଵ െ ‫ݔ‬ଶ ൅ ʹ‫ݔ‬ଷ
Subject to െ‫ݔ‬ଵ ൅ ‫ݔ‬ଶ ൅ ‫ݔ‬ଷ  ൌ Ͷ
െ‫ݔ‬ଵ ൅ ‫ݔ‬ଶ െ ‫ݔ‬ଷ  ൑ ͸
‫ݔ‬ଵ  ൑ Ͳǡ ‫ݔ‬ଶ  ൒ Ͳǡ ‫ݔ‬ଷ unrestricted in sign
i. Convert the problem to a standard linear program in non-negative variables
ii. Solve the standard linear program obtained in (i) using big ‫ ܯ‬simplex method.
18. Consider the following set of constraints:
‫ݔ‬ଵ ൅ ʹ‫ݔ‬ଶ െ ʹ‫ݔ‬ଷ ൅ Ͷ‫ݔ‬ସ  ൑ ͶͲ
ʹ‫ݔ‬ଵ െ ‫ݔ‬ଶ ൅ ‫ݔ‬ଷ ൅ ʹ‫ݔ‬ସ  ൑ ͺ
Ͷ‫ݔ‬ଵ െ ʹ‫ݔ‬ଶ ൅ ‫ݔ‬ଷ െ ‫ݔ‬ସ  ൑ ͳͲ
‫ݔ‬ଵ ǡ ‫ݔ‬ଶ ǡ ‫ݔ‬ଷ ǡ ‫ݔ‬ସ  ൒ Ͳ

Solve the problem for each of the following objective functions:

i. Maximize ܼ ൌ ʹ‫ݔ‬ଵ ൅ ‫ݔ‬ଶ െ ͵‫ݔ‬ଷ ൅ ͷ‫ݔ‬ସ
ii. Maximize ܼ ൌ ͺ‫ݔ‬ଵ ൅ ͸‫ݔ‬ଶ ൅ ͵‫ݔ‬ଷ െ ʹ‫ݔ‬ସ
iii. Maximize ܼ ൌ ͵‫ݔ‬ଵ െ ‫ݔ‬ଶ ൅ ͵‫ݔ‬ଷ ൅ Ͷ‫ݔ‬ସ
iv. Minimize ܼ ൌ ͷ‫ݔ‬ଵ െ Ͷ‫ݔ‬ଶ ൅ ͸‫ݔ‬ଷ െ ͺ‫ݔ‬ସ
v. Minimize ܼ ൌ െͶ‫ݔ‬ଵ ൅ ͸‫ݔ‬ଶ െ ʹ‫ݔ‬ଷ ൅ Ͷ‫ݔ‬ସ

============= =============

59