Unit - 1c OR

C h a p t e r 4
Linear Programming:
The Simplex Method
“Checking the results of a decision against its expectations shows executives what their
strengths are, where they need to improve, and where they lack knowledge or information.”
– Peter Drucker
PREVIEW
The purpose of this chapter is to help you gain an understanding of how the simplex method works.
Understanding the underlying principles help to interpret and analyze solution of any LP problem.
LEARNING OBJECTIVES
After studying this chapter, you should be able to

z understand the meaning of the word ‘simplex’ and logic of using simplex method.
z convert an LP problem into its standard form by adding slack, surplus and/or artificial variables.
z set-up simplex tables and solve LP problems using the simplex algorithm.
z interpret the optimal solution of LP problems.
z recognize special cases such as degeneracy, multiple optimal solution, unbounded and infeasible
solutions.
CHAPTER OUTLINE
4.1 Introduction 4.6 Types of Linear Programming Solutions
4.2 Standard Form of an LP Problem • Conceptual Questions
4.3 Simplex Algorithm (Maximization Case) • Self Practice Problems B
4.4 Simplex Algorithm (Minimization Case) • Hints and Answers
• Self Practice Problems A Chapter Summary
• Hints and Answers Chapter Concepts Quiz
4.5 Some Complications and their Resolution Case Study
Linear Programming: The Simplex Method 101
4.1 INTRODUCTION
Most real-life problems when formulated as an LP model have more than two variables and therefore need
a more efficient method to suggest an optimal solution for such problems. In this chapter, we shall discuss
a procedure called the simplex method for solving an LP model of such problems. This method was
developed by G B Dantzig in 1947.
The simplex, an important term in mathematics, represents an object in an n-dimensional space,
connecting n + 1 points. In one dimension, the simplex represents a line segment connecting two points;
in two dimensions, it represents a triangle formed by joining three points; in three dimensions, it represents
a four-sided pyramid.
The concept of simplex method is similar to the graphical method. In the graphical method, extreme
points of the feasible solution space are examined in order to search for the optimal solution that lies at
one of these points. For LP problems with several variables, we may not be able to graph the feasible region,
but the optimal solution will still lie at an extreme point of the many-sided, multidimensional figure (called
an n-dimensional polyhedron) that represents the feasible solution space. The simplex method examines
these extreme points in a systematic manner, repeating the same set of steps of the algorithm until an optimal
solution is found. It is for this reason that it is also called the iterative method.
Since the number of extreme points of the feasible solution space are finite, the method assures an
improvement in the value of objective function as we move from one iteration (extreme point) to another
and achieve the optimal solution in a finite number of steps. The method also indicates when an unbounded
solution is reached.
4.2 STANDARD FORM OF AN LP PROBLEM

The use of the simplex method to solve an LP problem requires that the problem be converted into its
Simplex method
standard form. The standard form of the LP problem should have the following characteristics: examines corner
(i) All the constraints should be expressed as equations by adding slack or surplus and/or artificial points of the
feasible region,
variables. using matrix row
(ii) The right-hand side of each constraint should be made non-negative (if not). This is done by operations, until an
multiplying both sides of the resulting constraint by – 1. optimal solution is
found.
(iii) The objective function should be of the maximization type.
The standard form of the LP problem is expressed as:
Optimize (Max or Min) Z = c1 x1 + c2 x2 + . . . + cn xn + 0s1 + 0s2 + . . . + 0sm
subject to the linear constraints
a11 x1 + a12 x2 + . . . + a1n xn + s1 = b1
a21 x1 + a22 x2 + . . . + a2n xn + s2 = b2
. . .
. . .
. . .
am1 x1 + am2 x2 + . . . + amn xn + sm = bm
and x1, x2, . . . , xn, s1, s2, . . ., sm ≥ 0
This standard form of the LP problem can also be expressed in the compact form as follows:
n m
Optimize (Max or Min) Z = ∑ cj xj + ∑ 0 si (Objective function)
j =1 i =1

n
∑ a ij xj + si = bi ; i = 1, 2, . . ., m (Constraints)
j =1
and xj, si ≥ 0, for all i and j (Non-negativity conditions)
102 Operations Research: Theory and Applications
In matrix notations the standard form is expressed as:

Optimize (Max or Min) Z = cx + 0s
Ax + s = b, and x, s ≥ 0
where, c = (c1, c2, . . ., cn ) is the row vector, x = (x1, x2, . . ., xn )T, b = (b1, b2, . . ., bm )T and s = (s1, s2, . . ., sm ) are
column vectors, and A is the m × n matrix of coefficients, aij of variables x1, x2, . . ., xn in the constraints.
Remarks Any LP problem (maximization or minimization) may have
1. (a) no feasible solution, i.e. value of decision variables, xj ( j = 1, 2, . . ., n) may not satisfy every constraint.
(b) a unique optimum feasible solution.
(c) more than one optimum feasible solution, i.e. alternative optimum feasible solutions.
(d) a feasible solution for which the objective function is unbounded (value of the objective function can
be made as large as possible in a maximization problem or as small as possible in a minimization
problem).
2. Any minimization LP problem can be converted into an equivalent maximization problem by changing the
sign of cj’s in the objective function. That is,
n n
Minimize ∑ cj xj = Maximize ∑ ( − cj ) xj
j =1 j =1
3. Any constraint expressed by equality (=) sign may be replaced by two weak inequalities. For example,
a11 x1 + a12 x2 + . . . + a1n xn = b1 is equivalent to following two simultaneous constraints,
Slack variable
represents an a11 x1 + a12 x2 + . . . + a1n xn ≤ b1 and a11 x1 + a12 x2 + . . . + a1n xn ≥ b1
unused quantity of
resource; it is 4. Three types of additional variables, namely (i) slack variables (s) (ii) surplus variables (– s), and
added to less-than (iii) artificial variables (A) are added in the given LP problem to convert it into the standard form for the
or equal-to type following reasons:
constraints in order
to get an equality (a) These variables allow us to convert inequalities into equalities, thereby converting the given LP
constraint. problem into its standard form. Such form will help in getting solution of the LP problem.
(b) These variables help decision-makers to draw economic interpretation from the final solution.
(c) These variables are used to get an initial feasible solution represented by the columns of the identity
matrix.
The summary of the additional variables to be added in the given LP problem in order to convert it
into a standard form is given in Table 4.1.
Types of Constraint Extra Variable Coefficient of Additional Presence of Additional

Needed Variables in the Variables in the
Objective Function Initial Solution
Max Z Min Z
• Less than or A slack variable 0 0 Yes
equal to (≤) is added
• Greater than or A surplus variable 0 0 No
Table 4.1 equal to (≥) is subtracted, and
Summary of an artificial variable –M +M Yes
Additional is added
Variables Added • Equal to (=) Only an artificial –M +M Yes
in an LP Problem variable is added
Remark A slack variable represents an unused resource, either in the form of time on a machine, labour
hours, money, warehouse space, etc. Since these variables don’t yield any profit, therefore such variables
are added to the objective function with zero coefficients.
A surplus variable represents the amount by which solution values exceed a resource. These variables
are also called negative slack variables. Surplus variables, like slack variables carry a zero coefficient in
the objective function.
Definitions
Basic solution Given a system of m simultaneous linear equations with n (> m) variables: Ax = B, where A
is an m × n matrix and rank (A) = m. Let B be any m × m non-singular submatrix of A obtained by reordering m
linearly independent columns of A. Then, a solution obtained by setting n – m variables not associated with the
columns of B, equal to zero, and solving the resulting system is called a basic solution to the given system of
equations.
The m variables (may be all non zero) are called basic variables. The m × m non-singular sub-matrix B is
called a basis matrix and the columns of B as basis vectors.
If B is the basis matrix, then the basic solution to the system of equations will be xB = B–1b.
Basic feasible solution A basic solution to the system of simultaneous equations, Ax = b is called basic
feasible if xB ≥ 0.
Degenerate solution A basic solution to the system of simultaneous equations, Ax = b is called degenerate
if one or more of the basic variables assume zero value.
Cost vector Let xB be a basic feasible solution to the LP problem.
Maximize Z = cx
subject to the constraints
Ax = b, and x ≥ 0.
Then the vector cB = (cB1, cB2, . . ., cBm), is called cost vector that represents the coefficient of basic variable,
xB in the basic feasible solution.
4.3 SIMPLEX ALGORITHM (MAXIMIZATION CASE)

The steps of the simplex algorithm for obtaining an optimal solution (if it exists) to a linear programming
problem are as follows:
Step 1: Formulation of the mathematical model
(i) Formulate the LP model of the given problem.
Surplus variable
(ii) If the objective function is of minimization, then convert it into equivalent maximization, by using represents the
the following relationship amount of resource
usage above the
Minimize Z = – Maximize Z * , where Z * = – Z. minimum required
and is added to
(iii) Check whether all the bi (i = 1, 2, . . . , m) values are positive. If any one of them is negative, then greater-than or
multiply the corresponding constraint by – 1 in order to make bi > 0. In doing so, remember to equal-to constraints
change a ≤ type constraint to a ≥ type constraint, and vice versa. in order to get
equality constraint.
(iv) Express the given LP problem in the standard form by adding additional variables in constraints
(as per requirement) and assign a zero-cost coefficient to these variables in the objective function.
(v) Replace each unrestricted variable (if any) with the difference of the two non-negative variables.
Step 2: Set-up the initial solution Write down the coefficients of all the variables in the LP problem
in a tabular form, as shown in Table 4.2, in order to get an initial basic feasible solution [xB = B–1 b].
cj → c1 c2 ... cn 0 0 ... 0
Basic Variables Basic Basic Variables Variables
Coefficient Variables Value x1 x2 ... xn s1 s2 . . . sm
(cB) B b (= xB)
cB1 s1 xB1 = b1 a 11 a 12 ... a 1n 1 0 ... 0
cB2 s2 xB2 = b2 a 21 a 22 ... a 2n 0 1 ... 0
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
cBm sm xBm = bm a m1 a m2 ... a mn 0 0 ... 1
Table 4.2
Z = Σ cBi xBi zj = Σ cBi xj 0 0 ... 0 0 0 ... 0 Initial Simplex
cj – z j c1 – z1 c 2 – z2 . . . c n – zn 0 0 ... 0 Table
After having set up the initial simplex table, locate the identity matrix (contains all zeros except
positive elements 1’s on the diagonal). The identity matrix so obtained is also called a basis matrix
[because basic feasible solution is represented by B = I ].
The columns of identity matrix represent the coefficients of slack variables that have been added to
the constraints. Each column of the identity matrix also represents a basic variable.
Assign values of the constants (bi’s) to the column variables in the identity matrix [because
Degeneracy arises xB = B –1 b = I b = b].
when there is a tie The variables corresponding to the columns of the identity matrix are called basic variables and the
in the minimum ratio remaining ones are called non-basic variables. In general, if an LP model has n variables and m (< n)
value that
determines the constraints, then m variables would be basic and n – m variables non-basic. In certain cases one or more
variable to enter than one basic variables may also have zero values. It one or more basic variables have zero value, then
into the next this situation is called degeneracy and will be discussed later.
solution.
The first row in Table 4.2 indicates the coefficients cj of variables in the objective function. These
values represent the cost (or profit) per unit associated with a variable in the objective function and these
are used to determine the variable to be entered into the basis matrix B.
The column ‘cB’ lists the coefficients of the current basic variables in the objective function. These
values are used to calculate the value of Z when one unit of any variable is brought into the solution.
Column ‘xB’ represents the values of the basic variables in the current basic solution.
Basis is the set of Numbers, aij in the columns under each variable are also called substitution rates (or exchange
variables present in coefficients) because these represent the rate at which resource i (i = 1, 2, . . ., m) is consumed by each unit
the solution, have
positive non-zero of an activity j ( j = 1, 2, . . ., n).
value; these The values zj represent the amount by which the value of objective function Z would be decreased
variables are also (or increased ) if one unit of the given variable is added to the new solution. Each of the values in the
called basic
variables.
cj – zj row represents the net amount of increase (or decrease) in the objective function that would occur
when one unit of the variable represented by the column head is introduced into the solution. That is:
cj – zj (net effect) = cj (incoming unit profit/cost) – zj (outgoing total profit/cost)
where zj = Coefficient of basic variables column × Exchange coefficient column j
Step 3: Test for optimality Calculate the cj – zj value for all non-basic variables. To obtain the value
of zj multiply each element under ‘Variables’ column (columns, aj of the coefficient matrix) with the
corresponding elements in cB-column. Examine values of cj – zj. The following three cases may arise:
(i) If all cj – zj ≤ 0, then the basic feasible solution is optimal.
(ii) If at least one column of the coefficients matrix (i.e. ak ) for which ck – zk > 0 and all other elements
are negative (i.e. aik < 0), then there exists an unbounded solution to the given problem.
(iii) If at least one cj – zj > 0, and each of these columns have at least one positive element (i.e. aij )
for some row, then this indicates that an improvement in the value of objective function Z is
possible.
Non-basic Step 4: Select the variable to enter the basis If Case (iii) of Step 3 holds, then select a variable
variables are those
which are not in the
that has the largest cj – zj value to enter into the new solution. That is,
‘basis’ and have ck – zk = Max {(cj – zj); cj – zj > 0}
zero-value.
The column to be entered is called the key or pivot column. Obviously, such a variable indicates the
largest per unit improvement in the current solution.
Step 5: Test for feasibility (variable to leave the basis) After identifying the variable to become
the basic variable, the variable to be removed from the existing set of basic variables is determined. For
this, each number in xB-column (i.e. bi values) is divided by the corresponding (but positive) number in
the key column and a row is selected for which this ratio is non-negative and minimum. This ratio is called
the replacement (exchange) ratio. That is,
xBr R| x U|
= Min S| a
Bi
; a rj > 0 V|
arj
T rj W
This ratio restricts the number of units of the incoming variable that can be obtained from the exchange. Infeasibility is the
It may be noted that the division by a negative or by a zero element in key column is not permitted. situation in which no
The row selected in this manner is called the key or pivot row and it represents the variable which solution satisfies all
constraints of an LP
will leave the solution. problem.
The element that lies at the intersection of the key row and key column of the simplex table is called
key or pivot element.
Step 6: Finding the new solution

(i) If the key element is 1, then the row remains the same in the new simplex table.
(ii) If the key element is other than 1, then divide each element in the key row (including the elements
in xB-column ) by the key element, to find the new values for that row.
(iii) The new values of the elements in the remaining rows of the new simplex table can be obtained
by performing elementary row operations on all rows so that all elements except the key element
in the key column are zero. In other words, for each row other than the key row, we use the formula:
FG IJ LMF Number above or belowI F Corresponding number in I OP

MNGH key element JK × GGH the new row, that is row J
Number in Number in
new row = old row H ±
K JP
replaced in Step 6 (ii) K Q
The new entries in cB and xB columns are updated in the new simplex table of the current solution.
Step 7: Repeat the procedure Go to Step 3 and repeat the procedure until all entries in the cj – zj row values
cj – zj row are either negative or zero. represent net profit
or loss resulting
Remark The flow chart of the simplex algorithm for both the maximization and the minimization LP from introducing
one unit of any
problem is shown in Fig. 4.1. variable into the
‘basis’ or solution
Example 4.1 Use the simplex method to solve the following LP problem.
mix.
Maximize Z = 3x1 + 5x2 + 4x3
(i) 2x1 + 3x2 ≤ 8, (ii) 2x2 + 5x3 ≤ 10, (iii) 3x1 + 2x2 + 4x3 ≤ 15
and x1, x2, x3 ≥ 0
[Rewa MSc (Maths), 1995; Meerut MSc (Stat.), 1996; MSc (Maths), 1998;
Kurukshetra, MSc (Stat.), 1998]
Solution Step 1: Introducing non-negative slack variables s1, s2 and s3 to convert the given LP problem
into its standard form:
Maximize Z = 3x1 + 5x2 + 4x3 + 0s1 + 0s2 + 0s3
(i) 2x1 + 3x2 + s1 = 8, (ii) 2x2 + 5x3 + s2 = 10, (iii) 3x1 + 2x2 + 4x3 + s3 = 15
and x1, x2, x3, s1, s2, s3 ≥ 0
Step 2: Since all bi (RHS values) > 0, (i = 1, 2, 3), therefore choose the initial basic feasible solution as:
x1 = x2 = x3 = 0; s1 = 8, s2 = 10, s3 = 15 and Max Z = 0
This solution can also be read from the initial simplex Table 4.3 by equating row-wise values in the basis
(B) column and solution values (xB ) column.
Step 3: To see whether the current solution given in Table 4.3 is optimal or not, calculate
cj – zj = cj – cB B– 1 aj = cj – cB yj
for non-basic variables x1, x2 and x3 as follows.
zj = (Basic variable coefficients, cB ) × ( jth column of data matrix)
That is, z1 = 0 (2) + 0 (0) + 0 (3) = 0 for x1-column
z2 = 0 (3) + 0 (2) + 0 (2) = 0 for x2-column
z3 = 0 (0) + 0 (5) + 0 (4) = 0 for x3-column
These zj values are now subtracted from cj values in order to calculate the net profit likely to be gained
by introducing (performing) a particular variable (activity) x1, x2 or x3 into the new solution mix. This is
done by introducing one unit of each variable x1, x2 and x3 into the new solution mix.
c1 – z1 = 3 – 0 = 3, c2 – z2 = 5 – 0 = 5, c3 – z 3 = 4 – 0 = 4
The zj and cj – zj rows are added into the Table 4.3.
The values of basic variables, s1, s2 and s3 are given in the solution values (xB ) column of Table 4.3.
The remaining variables that are non-basic at the current solution have zero value. The value of objective
function at the current solution is given by
Z = (Basic variables coefficient, cB ) × (Basic variables value, xB )
= 0 (8) + 0 (10) + 0 (15) = 0
cj → 3 5 4 0 0 0
Basic Variables Basic Basic Variables x1 x2 x3 s1 s2 s3 Min Ratio
Coefficient Variables Value xB /x2
cB B b (= xB )
0 s1 8 2 3 0 1 0 0 8/3 →
0 s2 10 0 2 5 0 1 0 10/2
0 s3 15 3 2 4 0 0 1 15/2
Z = 0 zj 0 0 0 0 0 0
Table 4.3 cj – zj 3 5 4 0 0 0
Initial Solution ↑
Since all cj – zj ≥ 0 ( j = 1, 2, 3), the current solution is not optimal. Variable x2 is chosen to enter into
the basis because c2 – z2 = 5 is the largest positive number in the x2-column, where all elements are positive.
This means that for every unit of variable x2, the objective function will increase in value by 5. The x2-
column is the key column.
Step 4: The variable that is to leave the basis is determined by dividing the values in the xB -column by
the corresponding elements in the key column as shown in Table 4.3. Since the ratio,
8/3 is minimum in row 1, the basic variable s1 is chosen to leave the solution (basis).
Step 5 (Iteration 1): Since the key element enclosed in the circle in Table 4.3 is not 1, divide all elements
of the key row by 3 in order to obtain new values of the elements in this row. The new values of the elements
in the remaining rows for the new Table 4.4 can be obtained by performing the following elementary row
operations on all rows so that all elements except the key element 1 in the key column are zero.
R1 (new) → R1 (old) ÷ 3 (key element)
→ (8/3, 2/3, 3/3, 0/3, 1/3, 0/3, 0/3) = (8/3, 2/3, 1, 0, 1/3, 0, 0)
R2 (new) → R2 (old) – 2R1 (new) R3 (new) → R3 (old) – 2R1 (new)

10 – 2 × 8/3 = 14/3 15 – 2 × 8/3 = 29/3
0 – 2 × 2/3 = – 4/3 3 – 2 × 2/3 = 5/3
2 – 2 × 1= 0 2 – 2 × 1= 0
5 – 2 × 0= 5 4 – 2 × 0= 4
0 – 2 × 1/3 = – 2/3 0 – 2 × 1/3 = – 2/3
1 – 2 × 0= 1 0 – 2 × 0= 0
0 – 2 × 0= 0 1 – 2 × 0= 1
cj → 3 5 4 0 0 0
Basics Variables Basic Basic Variables x1 x2 x3 s1 s2 s3 Min Ratio

Coefficient Variables Value xB/x3
cB B b (= xB)
5 x2 8/3 2/3 1 0 1/3 0 0 –

0 s2 14/3 – 4/3 0 5 – 2/3 1 0 (14/3)/5 →
0 s3 29/3 5/3 0 4 – 2/3 0 1 (29/3)/4
Z = 40/3 zj 10/3 5 0 5/3 0 0

cj – zj – 1/3 0 4 – 5/3 0 0 Table 4.4
↑ Improved Solution
The improved basic feasible solution can be read from Table 4.4 as: x2 = 8/3, s2 = 14/3, s3 = 29/3 and
x1 = x3 = s1 = 0. The improved value of the objective function becomes:
Z = (Basic variable coefficients, cB ) × (Basic variable values, xB )
= 5 (8/3) + 0 (14/3) + 0 (29/3) = 40/3
Once again, calculate values of cj – zj to check whether the solution shown in Table 4.4 is optimal or
not. Since c3 – z3 > 0, the current solution is not optimal.
Iteration 2: Repeat Steps 3 to 5. Table 4.5 is obtained by performing following row operations to enter
variable x3 into the basis and to drive out s2 from the basis.
R2 (new) = R2 (old) ÷ 5 (key element) = (14/15, – 4/15, 0, 1, – 2/15, 1/5, 0)
R3 (new) → R3 (old) – 4R2 (new)
29/3 – 4 × 14/15 = 89/15

5/3 – 4 × – 4/15 = 41/15
0 – 4 × 0= 0
4 – 4 × 1= 0
– 2/3 – 4 × – 2/15 = – 2/15
0 – 4 × 1/5 = – 4/5
1 – 4 × 0= 0
Table 4.5 is completed by calculating the new zj and cj – zj values and the new value of objective
function:
z1 = 5 (2/3) + 4 (– 4/15) + 0 (41/15) = 34/15 c1 – z1 = 3 – 34/15 = 11/15 for x1 -column
z4 = 5 (1/3) + 4 (– 2/15) + 0 (2/15) = 17/15 c4 – z4 = 0 – 17/15 = – 17/15 for s1 -column
z5 = 5 (0) + 4 (1/5) + 0 (– 4/5) = 4/5 c5 – z5 = 0 – 4/5 = – 4/5 for s2 -column
The new objective function value is:
Z = (Basic variables coefficient, cB ) × (Basic variables value, xB )
= 5 (8/3) + 4 (14/15) + 0 (89/15) = 256/15
The improved basic feasible solution is shown in Table 4.5.
cj → 3 5 4 0 0 0

cB B b (= xB)
5 x2 8/3 2/3 1 0 1/3 0 0 (8/3)/(2/3) = 4

4 x3 14/15 – 4/15 0 1 – 2/15 1/5 0 –
0 s3 89/15 41/15 0 0 2/15 – 4/5 1 (89/15)/(41/15) = 2.17 →
Z = 256/15 zj 34/15 5 4 17/15 4/5 0

cj – zj 11/15 0 0 – 17/15 – 4/5 0 Table 4.5
Iteration 3: In Table 4.5, since c1 – z1 is still a positive value, the current solution is not optimal. Thus,
the variable x1 enters the basis and s3 leaves the basis. To get another improved solution as shown in Table
4.5 perform the following row operations in the same manner as discussed earlier.
R3 (new) → R3 (old) × 15/41 (key element)
→ (89/15 × 15/41, 41/15 × 15/41, 0 × 15/41, 0 × 15/41,
– 2/15 × 15/41, – 4/5 × 15/41, 1 × 15/41)
→ (89/41, 1, 0, 0, – 2/41, – 12/41, 15/41)
R1 (new) → R1 (old) – (2/3) R3 (new) R2 (new) → R2 (old)+ (4/15) R3 (new)
8/3 – 2/3 × 89/3 = 50/41 14/15 + 4/15 × 89/41 = 62/41

2/3 – 2/3 × 1 = 0 – 4/15 + 4/15 × 1 = 0
1 – 2/3 × 0 = 1 0 + 4/15 × 0 = 0
0 – 2/3 × 0 = 0 1 + 4/15 × 0 = 1
1/3 – 2/3 × – 2/41 = 15/41 – 2/15 + 4/15 × – 2/41 = – 6/41
0 – 2/3 × – 2/41 = 8/41 1/5 + 4/15 × – 12/41 = 5/41
0 – 2/3 × 15/41 = – 10/41 0 + 4/15 × 15/41 = 4/41
cj → 3 5 4 0 0 0
Basic Variables Basic Basic Variables x1 x2 x3 s1 s2 s3
Coefficient Variables Value
cB B b (= xB)
5 x2 50/41 0 1 0 15/41 8/41 – 10/41

4 x3 62/41 0 0 1 – 6/41 5/41 4/41
3 x1 89/41 1 0 0 – 2/41 – 12/41 15/41
Table 4.6 Z = 765/41 zj 3 5 4 45/41 24/41 11/41

Optimal Solution cj – zj 0 0 0 – 45/41 – 24/41 – 11/41
In Table 4.6, all cj – zj < 0 for non-basic variables. Therefore, the optimal solution is reached with,
x1 = 89/41, x2 = 50/41, x3 = 62/41 and the optimal value of Z = 765/41.
Example 4.2 A company makes two kinds of leather belts, belt A and belt B. Belt A is a high quality
belt and belt B is of lower quality. The respective profits are Rs 4 and Rs 3 per belt. The production of
each of type A requires twice as much time as a belt of type B, and if all belts were of type B, the company
could make 1,000 belts per day. The supply of leather is sufficient for only 800 belts per day (both A and
B combined). Belt A requires a fancy buckle and only 400 of these are available per day. There are only
700 buckles a day available for belt B.
What should be the daily production of each type of belt? Formulate this problem as an LP model and
solve it using the simplex method.
Solution Let x1 and x2 be the number of belts of type A and B, respectively, manufactured each day.
Then the LP model would be as follows:
Maximize (total profit) Z = 4x1 + 3x2
(i) 2x1 + x2 ≤ 1,000 (Time availability), (ii) x1 + x2 ≤ 800 (Supply of leather)
(iii) x1 ≤ 400 
 (Buckles availability)
x2 ≤ 700 
and x1, x2 ≥ 0
Standard form Introducing slack variables s1, s2, s3 and s4 to convert given LP model into its standard form
as follows.
Maximize Z = 4x1 + 3x2 + 0s1 + 0s2 + 0s3 + 0s4

(i) 2x1 + x 2 + s1 = 1,000, (ii) x1 + x2 + s2 = 800
(iii) x1 + s3 = 400, (iv) x2 + s 4 = 700
and x1, x2, s1, s2, s3, s4 ≥ 0
Solution by simplex method An initial feasible solution is obtained by setting x1 = x2 = 0. Thus, the
initial solution is: s1 = 1,000, s2 = 800, s3 = 400, s4 = 700 and Max Z = 0. This solution can also be read
from the initial simplex Table 4.7.
cj → 4 3 0 0 0 0
Basic Variables Basic Basic Variables x1 x2 s1 s2 s3 s4 Min Ratio
cB B b (= xB )
0 s1 1,000 2 1 1 0 0 0 1,000/2 = 500
0 s2 800 1 1 0 1 0 0 800/1 = 800
0 s3 400 1 0 0 0 1 0 400/1 = 400 →
0 s4 700 0 1 0 0 0 1 not defined
Z = 0 zj 0 0 0 0 0 0
cj – zj 4 3 0 0 0 0 Table 4.7
↑ Initial Solution
In Table 4.7, since c1 – z1 = 4 is the largest positive number, we apply the following row operations
in order to get an improved basic feasible solution by entering variable x1 into the basis and removing
variable s3 from the basis.
R3 (new) → R3 (old) ÷ 1 (key element) R1 (new) → R1 (old) – 2R3 (new)
R2 (new) → R2 (old) – R3 (new)
The new solution is shown in Table 4.8.
cj → 4 3 0 0 0 0
Basic Variables Basis Basic Variables x1 x2 s1 s2 s3 s4 Min Ratio
cB B b (= xB)
0 s1 200 0 1 1 0 – 2 0 200/1 = 200 →
0 s2 400 0 1 0 1 – 1 0 400/1 = 400
4 x1 400 1 0 0 0 1 0 –
0 s4 700 0 1 0 0 0 1 700/1 = 700
Z = 1,600 zj 4 0 0 0 4 0 Table 4.8
cj – zj 0 3 0 0 – 4 0 An Improved
↑ Solution
The solution shown in Table 4.8 is not optimal because c2 – z2 > 0 in x2 -column. Thus, again applying
the following row operations to get a new solution by entering variable x2 into the basis and removing
variable s1 from the basis, we get
R1 (new) → R1 (old) ÷ 1 (key element) R2 (new) → R2 (old) – R1 (new)
The improved solution is shown in Table 4.9.
cj → 4 3 0 0 0 0
Basic Variables Basic Basic Variables x1 x2 s1 s2 s3 s4 Min Ratio
Coefficient Variables Value xB /s3
cB B b(= xB)
3 x2 200 0 1 1 0 –2 0 —
0 s2 200 0 0 –1 1 1 0 200/1 = 200 →
4 x1 400 1 0 0 0 1 0 400/1 = 400
0 s4 500 0 0 –1 0 2 1 500/2 = 250
Z = 2,200 zj 4 3 3 0 –2 0
Table 4.9 cj – zj 0 0 –3 0 2 0
Improved Solution ↑
The solution shown in Table 4.9 is not optimal because c5 – z5 > 0 in s3-column. Thus, again applying
the following row operations to get a new solution by entering variable s3, into the basis and removing
variable s2 from the basis, we get
R2 (new) → R2 (old) ÷ 1 (key element) R1 (new) → R1 (old) + 2R2 (new)
R3 (new) → R3 (old) – R2 (new); R4 (new) → R4 (old) – 2R2 (new)
The new improved solution is shown in Table 4.10.
cj → 4 3 0 0 0 0
Basic Variables Basic Basic Variables x1 x2 s1 s2 s3 s4
cB B b (= xB)
3 x2 600 0 1 – 1 2 0 0
0 s3 200 0 0 – 1 1 1 0
4 x1 200 1 0 1 – 1 0 0
0 s4 100 0 0 1 – 2 0 1
Table 4.10 Z = 2,600 zj 4 3 1 2 0 0
Optimal Solution cj – zj 0 0 – 1 – 2 0 0
Since all cj – zj < 0 correspond to non-basic variables columns, the current basic feasible solution is
also the optimal solution. Thus, the company must manufacture, x1 = 200 belts of type A and x2 = 600 belts
of type B in order to obtain the maximum profit of Rs 2,600.
Example 4.3 A pharmaceutical company has 100 kg of A, 180 kg of B and 120 kg of C ingredients
available per month. The company can use these materials to make three basic pharmaceutical products
namely 5-10-5, 5-5-10 and 20-5-10, where the numbers in each case represent the percentage of weight of
A, B and C, respectively, in each of the products. The cost of these raw materials is as follows:
Ingredient Cost per kg (Rs)

A 80
B 20
C 50
Inert ingredients 20
The selling prices of these products are Rs 40.5, Rs 43 and 45 per kg , respectively. There is a capacity
restriction of the company for product 5-10-5, because of which the company cannot produce more than 30 kg
per month. Determine how much of each of the products the company should produce in order to maximize its
monthly profit. [Delhi Univ., MBA, 2004, AMIE, 2005]
Solution Let the P1, P2 and P3 be the three products to be manufactured. The data of the problem can
then be summarized as follows:
Product Product Ingredients

Inert
A B C
P1 5% 10% 5% 80%
P2 5% 5% 10% 80%
P3 20% 5% 10% 65%
Cost per kg (Rs) 80 20 50 20
Cost of P1 = 5% × 80 + 10% × 20 + 5% × 50 + 80% × 20 = 4 + 2 + 2.50 + 16 = Rs 24.50 per kg

Cost of P2 = 5% × 80 + 5% × 20 + 10% × 50 + 80% × 20 = 4 + 1 + 5 + 16 = Rs 26 per kg
Cost of P3 = 20% × 80 + 5% × 20 + 10% × 50 + 65% × 20 = 16 + 1 + 5 + 13 = Rs 35 per kg
Let x1, x2 and x3 be the quantity (in kg) of P1, P2 and P3, respectively to be manufactured. The LP
problem can then be formulated as
Maximize (net profit) Z = (Selling price – Cost price) × (Quantity of product)
= (40.50 – 24.50) x1 + (43 – 26) x2 + (45 – 35) x3 = 16x1 + 17x2 + 10x3
1 1 1
x1 + x 2 + x 3 ≤ 100 or x1 + x2 + 4x3 ≤ 2,000
20 20 5
1 1 1
x + x + x ≤ 180 or 2x1 + x2 + x3 ≤ 3,600
10 1 20 2 20 3
1 1 1
x1 + x2 + x ≤ 120 or x1 + 2x2 + 2x3 ≤ 2,400
20 10 10 3
x1 ≤ 30
and x1, x2, x3 ≥ 0.
Standard form Introducing slack variables s1, s2 and s3 to convert the given LP model into its standard
form as follows:
Maximize Z = 16x1 + 17x2 + 10x3 + 0s1 + 0s2 + 0s3 + 0s4
(i) x1 + x2 + 4x3 + s1 = 2,000, (ii) 2x1 + x2 + x3 + s2 = 3,600
(iii) x1 + 2x2 + 2x3 + s3 = 2,400, (iv) x1 + s4 = 30
and x1, x2, x3, s1, s2, s3, s4 ≥ 0
Solution by simplex method An initial basic feasible solution is obtained by setting x1 = x2 = x3 = 0. Thus,
the initial solution shown in Table 4.11 is: s1 = 2,000, s2 = 3,600, s3 = 2,400, s4 = 30 and Max Z = 0.
cj → 16 17 10 0 0 0 0
Basic Variables Basis Basic Variables x1 x2 x3 s1 s2 s3 s4 Min Ratio
cB B b (= xB )
0 s1 2,000 1 1 4 1 0 0 0 2,000/1 = 2,000
0 s2 3,600 2 1 1 0 1 0 0 3,600/1 = 3,600
0 s3 2,400 1 2 2 0 0 1 0 2,400/2 = 1,200 →
0 s4 30 1 0 0 0 0 0 1 —
Z = 0 zj 0 0 0 0 0 0 0
Table 4.11
cj – zj 16 17 10 0 0 0 0
Initial Solution
↑
Since c2 – z2 = 17 in x2 -column is the largest positive value, we apply the following row operations
in order to get a new improved solution by entering variable x2 into the basis and removing variable s3
from the basis.
R3 (new) → R3 (old) ÷ 2 (key element) R1 (new) → R1 (old) – R3 (new)
cj → 16 17 10 0 0 0 0
Basic Variables Basic Basic Variables x1 x2 x3 s1 s2 s3 s4 Min Ratio
cB B b (= xB )
0 s1 800 1/2 0 3 1 0 – 1/2 0 800/(1/2) = 1,600
0 s2 2,400 3/2 0 0 0 1 – 1/2 0 2,400/(3/2) = 1,600
17 x2 1,200 1/2 1 1 0 0 1/2 0 1,200/(1/2) = 2,400
0 s4 30 1 0 0 0 0 0 1 30/1 = 30 →
Z = 20,400 zj 17/2 17 17 0 0 17/2 0
Table 4.12
cj – zj 15/2 0 – 7 0 0 – 17/2 0
Improve Solution
↑
The solution shown in Table 4.12 is not optimal because c1 – z1 > 0 in x1 -column. Thus, applying the
following row operations to get a new improved solution by entering variable x1 into the basis and removing
the variable s4 from the basis, we get
R4 (new) → R4 (old) ÷ 1 (key element); R1 (new) → R1 (old) – (1/2) R4 (new)
R2 (new) → R2 (old) – (3/2) R4 (new); R3 (new) → R3 (old) – (1/2) R4 (new)
cj → 16 17 10 0 0 0 0
Basic Variables Basic Basic Variables x1 x2 x3 s1 s2 s3 s4

cB B b (= xB )
0 s1 785 0 0 3 1 0 – 1/2 – 1/2
0 s2 2,355 0 0 0 0 1 – 1/2 – 3/2
17 x2 1,185 0 1 1 0 0 1/2 – 1/2
16 x1 30 1 0 0 0 0 0 1
Table 4.13 Z = 20,625 zj 16 17 17 0 0 17/2 15/2
Optimal Solution cj – zj 0 0 –7 0 0 – 17/2 – 15/2
Since all cj – zj < 0 corresponding to non-basic variables columns, the current solution is an optimal
solution. Thus, the company must manufacture, x1 = 30 kg of P1, x2 = 1,185 kg of P2 and x3 = 0 kg of
P3 in order to obtain the maximum net profit of Rs 20,625.
4.4 SIMPLEX ALGORITHM (MINIMIZATION CASE)
In certain cases, it is difficult to obtain an initial basic feasible solution of the given LP problem. Such cases
arise
(i) when the constraints are of the ≤ type,
n
∑ a ij x j ≤ bi , xj ≥ 0
j =1
and value of few right-hand side constants is negative [i.e. bi < 0]. After adding the non-negative
slack variable si (i = 1, 2, . . ., m), the initial solution so obtained will be si = – bi for a particular
resource, i. This solution is not feasible because it does not satisfy non-negativity conditions of
slack variables (i.e. si ≥ 0).
(ii) when the constraints are of the ≥ type,
n
∑ a ij x j ≥ bi , xj ≥ 0
j =1
After adding surplus (negative slack) variable si, the initial solution so obtained will be – si = bi or
si = – bi
n
∑ aij x j − si = bi , xj ≥ 0, si ≥ 0
j =1
This solution is not feasible because it does not satisfy non-negativity conditions of surplus variables (i.e. si
≥ 0). In such a case, artificial variables, Ai (i = 1, 2, . . ., m) are added to get an initial basic feasible solution. The
resulting system of equations then becomes:
n
∑ a ij x j − si + Ai = bi
j =1
xj, si, Ai ≥ 0, i = 1, 2, . . ., m
These are m simultaneous equations with (n + m + m) variables (n decision variables, m artificial variables
and m surplus variables). An initial basic feasible solution of LP problem with such constraints can be
obtained by equating (n + 2m – m) = (n + m) variables equal to zero. Thus the new solution to the given
LP problem is: Ai = bi (i = 1, 2, . . . , m), which is not the solution to the original system of equations because
the two systems of equations are not equivalent. Thus, to get back to the original problem, artificial
variables must be removed from the optimal solution. There are two methods for removing artificial variables
from the solution.
• Two-Phase Method
• Big-M Method or Method of Penalties
The simplex method, both for the minimization and the maximization LP problem, may be summarized through
a flow chart shown in Fig. 4.1.
Fig. 4.1
Flow Chart of
Simplex Algorithm
Remark Artificial variables have no meaning in a physical sense and are only used as a tool for
generating an initial solution to an LP problem. Before the optimal solution is reached, all artificial variables
must be dropped out from the solution mix. This is done by assigning appropriate coefficients to these
variables in the objective function. These variables are added to those constraints with equality (=) and
greater than or equal to (≥) sign.
4.4.1 Two-Phase Method

In the first phase of this method, the sum of the artificial variables is minimized subject to the given
constraints in order to get a basic feasible solution of the LP problem. The second phase minimizes the
original objective function starting with the basic feasible solution obtained at the end of the first phase.
Since the solution of the LP problem is completed in two phases, this method is called the two-phase
method.
Advantages of the method

1. No assumptions on the original system of constraints are made, i.e. the system may be redundant,
inconsistent or not solvable in non-negative numbers.
2. It is easy to obtain an initial basic feasible solution for Phase I.
3. The basic feasible solution (if it exists) obtained at the end of phase I is used as initial solution for
Phase II.
Steps of the Algorithm: Phase I

An artificial
variable is added to Step 1 (a): If all the constraints in the given LP problem are ‘less than or equal to’ (≤) type, then
the constraints to
get an initial solution Phase II can be directly used to solve the problem. Otherwise, the necessary number of surplus and artificial
to an LP problem. variables are added to convert constraints into equality constraints.
(b) If the given LP problem is of minimization, then convert it to the maximization type by the usual method.
Step 2: Assign zero coefficient to each of the decision variables (xj) and to the surplus variables; and
assign – 1 coefficient to each of the artificial variables. This yields the following auxiliary LP problem.
m
Maximize Z* = ∑ ( −1) Ai
i =1

n
∑ a ij x j + Ai = bi , i = 1, 2, . . ., m
i =1
and xj, Aj ≥ 0
Step 3: Apply the simplex algorithm to solve this auxiliary LP problem. The following three cases may arise
at optimality.
(a) Max Z * = 0 and at least one artificial variable is present in the basis with positive value. This means
that no feasible solution exists for the original LP problem.
(b) Max Z * = 0 and no artificial variable is present in the basis. This means that only decision variables
(xj’s) are present in the basis and hence proceed to Phase II to obtain an optimal basic feasible
solution on the original LP problem.
(c) Max Z * = 0 and at least one artificial variable is present in the basis at zero value. This means
that a feasible solution to the auxiliary LP problem is also a feasible solution to the original LP
problem. In order to arrive at the basic feasible solution, proceed directly to Phase II or else
eliminate the artificial basic variable and then proceed to Phase II.
Remark Once an artificial variable has left the basis, it has served its purpose and can, therefore, be
removed from the simplex table. An artificial variable is never considered for re-entry into the basis.
Phase II: Assign actual coefficients to the variables in the objective function and zero coefficient to the
artificial variables which appear at zero value in the basis at the end of Phase I. The last simplex table of
Phase I can be used as the initial simplex table for Phase II. Then apply the usual simplex algorithm to the
modified simplex table in order to get the optimal solution to the original problem. Artificial variables that
do not appear in the basis may be removed.
Example 4.4 Use two-phase simplex method to solve the following LP problem:
Minimize Z = x1 + x2
(i) 2x1 + x2 ≥ 4, (ii) x1 + 7x2 ≥ 7
and x1, x2 ≥ 0
Solution Converting the given LP problem objective function into the maximization form and then adding
surplus variables s1 and s2 and artificial variables A1 and A2 in the constraints, the problem becomes:
Maximize Z * = – x1 – x2
(i) 2x1 + 4x2 – s1 + A1 = 4, (ii) x1 + 7x2 – s2 + A2 = 7
and x1, x2, s1, s2, A1, A2 ≥ 0
where Z * = – Z
Phase I: This phase starts by considering the following auxiliary LP problem:
Maximize Z * = – A1 – A2
(i) 2x1 + 4x2 – s1 + A1 = 4, (ii) x1 + 7x2 – s2 + A2 = 7
and x1, x2, s1, s2, A1, A2 ≥ 0
The initial solution is presented in Table 4.14.
cj → 0 0 0 0 – 1 – 1
Basic Variables Basic Basic Variables x1 x2 s1 s2 A1 A2
cB B b(= xB )
–1 A1 4 2 1 –1 0 1 0
–1 A2 7 1 7 0 –1 0 1→
Z * = – 11 zj –3 –8 1 1 –1 –1
cj – zj 3 8 –1 –1 0 0 Table 4.14
Artificial variables A1 and A2 are now removed, one after the other, maintaining the feasibility of the solution.
Iteration 1: Applying the following row operations to get an improved solution by entering variable x2
in the basis and first removing variable A2 from the basis. The improved solution is shown in Table 4.15.
Note that the variable x1 cannot be entered into the basis as this would lead to an infeasible solution.
R2 (new) → R2 (old) ÷ 7 (key element); R1 (new) → R1 (old) – R2 (new)
cj → 0 0 0 0 – 1 – 1
Basic Variables Basic Basic Variables x1 x2 s1 s2 A1 A2 *
cB B b( = xB )
–1 A1 3 13/7 0 – 1 1/7 1 – 1/7 →
0 x2 1 1/7 1 0 – 1/7 0 1/7
Z* = – 3 zj – 13/7 0 1 – 1/7 – 1 1/7 Table 4.15
cj – zj 13/7 0 – 1 1/7 0 – 8/7 Improved
Solution
↑
* This column can permanently be removed at this stage.

Iteration 2: To remove A1 from the solution shown in Table 4.15, we enter variable s2 in the basis by
applying the following row operations. The new solution is shown in Table 4.16. It may be noted that if
instead of s2, variable x1 is chosen to be entered into the basis, it will lead to an infeasible solution
R1 (new) → R1 (old) × 7; R2 (new) → R2 (old) + (1/7) R1 (new)
cj → 0 0 0 0 – 1 – 1
Basic Variables Basic Basic Variables x1 x2 s1 s2 A1* A2*
cB B b( = xB )
0 s2 21 13 0 –7 1 7 –1
0 x2 4 2 1 –1 0 1 0
Table 4.16 Z* = 0 zj 0 0 0 0 0 0
Improved Solution cj – zj 0 0 0 0 –1 –1
* Remove columns A1 and A2 from Table 4.16.

Since all cj – zj ≤ 0 correspond to non-basic variables, the optimal solution: x1 = 0, x2 = 4,
s1 = 0, s2 = 21, A1 = 0, A2 = 0 with Z * = 0 is arrived at. However, this solution may or may not be the basic
feasible solution to the original LP problem. Thus, we have to move to Phase II to get an optimal solution
to our original LP problem.
Phase II: The modified simplex table obtained from Table 4.16 is represented in Table 4.17.
cj → – 1 – 1 0 0
Basic Variables Basic Basic Variables x1 x2 s1 s2 Min Ratio
cB B b( = xB )
0 s2 21 13 0 – 7 1 21/13 →
–1 x2 4 2 1 – 1 0 4/2
Z* = – 4 zj – 2 – 1 1 0
cj – zj 1 0 – 1 0
Table 4.17
↑
Iteration 1: Introducing variable x1 into the basis and removing variable s2 from the basis by applying the
following row operations:
R1 (new) → R1 (old) ÷ 13 (key element); R2 (new) → R2 (old) – 2R1 (new)
The improved basic feasible solution so obtained is given in Table 4.18. Since in Table 4.18, cj – zj ≤ 0
for all non-basic variables, the current solution is optimal. Thus, the optimal basic feasible solution to the given
LP problem is: x1 = 21/13, x2 = 10/13 and Max Z * = – 31/13 or Min Z = 31/13.
cj → –1 –1 0 0
Basic Variables Basic Basic Variables x1 x2 s1 s2

cB B b( = xB )
–1 x1 21/13 1 0 – 7/13 1/13

–1 x2 10/13 0 1 1/13 – 2/13
Table 4.18 Z * = – 31/13 zj –1 –1 6/13 1/13

Optimal Solution cj – zj 0 0 – 6/13 – 1/13
Example 4.5 Solve the following LP problem by using the two-phase simplex method.
Minimize Z = x1 – 2x2 – 3x3
(i) – 2x1 + x2 + 3x3 = 2, (ii) 2x1 + 3x2 + 4x3 = 1
and x1, x2, x3 ≥ 0. [Meerut, MSc (Math), 2003]
Solution After converting the objective function into the maximization form and by adding artificial
variables A1 and A2 in the constraints, the given LP problem becomes:
Maximize Z * = – x1 + 2x2 + 3x3
(i) – 2x1 + x2 + 3x3 + A1 = 2, (ii) 2x1 + 3x2 + 4x3 + A2 = 1
and x1, x2, x3, A1, A2 ≥ 0
where Z * = – Z
Phase I: This phase starts by considering the following auxiliary LP problem:
Maximize Z * = – A1 – A2
(i) – 2x1 + x2 + 3x3 + A1 = 2 (ii) 2x1 + 3x2 + 4x3 + A2 = 1
and x1, x2, x3, A1, A2 ≥ 0
The initial solution is presented in Table 4.19.
cj → 0 0 0 – 1 – 1
Basic Variables Basic Basic Variables x1 x2 x3 A1 A2
cB B b ( = xB )
–1 A1 2 –2 1 3 1 0
–1 A2 1 2 3 4 0 1 →
Z* = – 3 zj 0 –4 –7 –1 –1
cj – zj 0 4 7 0 0 Table 4.19
Initial Solution
↑
To first remove the artificial variable A2 from the solution shown in Table 4.19, introduce variable
x3 into the basis by applying the following row operations:
R1 (new) → R2 (old) ÷ 4 (key element) ; R1 (new) → R1 (old) – 3R2 (new)
The improved solution so obtained is given in Table 4.20. Since in Table 4.20, cj – zj ≤ 0 corresponds
to non-basic variables, the optimal solution is: x1 = 0, x2 = 0, x3 = 1/4, A1 = 5/4 and A2 = 0 with
Max Z * = – 5/4. But at the same time, the value of Z * < 0 and the artificial variable A1 appears in the
basis with positive value 5/4. Hence, feasible solution to the given original LP problem does not exist.
cj → 0 0 0 –1
Basic Variables Basic Basic Variables x1 x2 x3 A1
cB B b( = xB )
–1 A1 5/4 –7/2 –5/4 0 1
0 x3 1/4 1/2 3/4 1 0
Table 4.20
Z * = – 5/4 zj 7/2 5/4 0 –1 Optimal but not
cj – zj – 7/2 – 5/4 0 0 Feasible Solution
Example 4.6 Use two-phase simplex method to solve following LP problem.

(i) 5x1 + 7x2 + 4x3 ≤ 7, (ii) – 4x1 + 7x2 + 5x3 ≥ – 2, (iii) 3x1 + 4x2 – 6x3 ≥ 29/7
and x1, x2, x3 ≥ 0. [Punjab Univ., BE (E & C) 2006 ; BE (IT) 2006]
Solution Since RHS of constraint 2 is negative, multiplying it by – 1 on both sides and express it as:
4x1 – 7x2 – 5x3 ≤ 2.
Phase I: Introducing slack, surplus and artificial variables in the constraints, the standard form of LP
problem becomes:
Minimize Z* = A1
(i) 5x1 + 7x2 + 4x3 + s1 = 7, (ii) 4x1 – 7x2 – 5x3 + s2 = 2, (iii) 3x1 + 4x2 – 6x3 – s3 + A1 = 29/7
and x1, x2, x3, s1, s2, s3, A1 ≥ 0.
Setting variables x1 = x2 = x3 = s3 = 0, the basic feasible solution shown in Table 4.21 to the auxiliary LP
problem is: s1 = 7, s2 = 2, A1 = 29/7
cj Æ 0 0 0 0 0 0 1
Basic Variables Basic Basic Variables x1 x2 x3 s1 s2 s3 A1 Min Ratio
cB B b (= xB)
0 s1 7 5 7 4 1 0 0 0 1 →
0 s2 2 4 –7 –5 0 1 0 0 —
1 A1 29/7 3 4 –6 0 0 –1 1 29/28
Table 4.21 Z = 29/7 zj 3 4 –6 0 0 –1 1

Initial Solution cj – zj –3 –4 6 0 0 1 0
↑
Since c2 – z2 = – 4 is the largest negative value under x2-column in Table 4.21, replacing basic variable s1
with the non-basic variable x2 into the basis. For this, apply following row operations:
R1(new) → R1(old) ÷ 7(key element); R2(new) → R2(old) + 7R1(new);
R3(new) → R3(old) – 4R1(new)
to get an improved solution as shown in Table 4.22.
cj Æ 0 0 0 0 0 0 1
Basic Variables Basic Basic Variables x1 x2 x3 s1 s2 s3 A1 Min Ratio
cB B b (= xB)
0 x2 1 5/7 1 4/7 1/7 0 0 0 7/5
0 s2 9 9 0 –1 1 1 0 0 1 
 Tie
1 A1 1/7 1/7 0 – 58/7 – 4/7 0 –1 1 1 
Table 4.22
An Improved Z = 1/7 zj 1/7 0 – 58/7 – 4/7 0 –1 1
Solution cj – zj –1/7 0 58/7 4/7 0 1 0
↑
Solution shown in Table 4.22 is not optimal and there is a tie between the s2 and A1-rows for the key row.
The A1-row is selected as the key row because preference is given to the artificial variable. Thus (1/7) is the key
element. Replace basic variable A1 in the basis with the non-basic variable x1. Applying following row opera-
tions to get the new solution as shown in Table 4.23.
R3(new) → R3(old) ÷ (1/7) key element; R1(new) → R1(old) – (5/7) R3 (new);
R2(new) → R2(old) – 9 R3(new)
cj → 0 0 0 0 0 0
Basic Variables Variables Basic Variables x1 x2 x3 s1 s2 s3
Coefficient in Basis Value
cB B b (= xB)
0 x2 2/7 0 1 42 3 0 5
0 s2 0 0 0 521 37 1 63
Table 4.23 0 x1 1 1 0 – 58 –4 0 –7
Basic Feasible
Solution Z=0 zj 0 0 0 0 0 0
c j – zj 0 0 0 0 0 0
In Table 4.23, all cj – zj = 0 under non-basic variable columns. Thus, the current solution is optimal. Also
Min Z* = 0 and no artificial variable appears in the basis, and hence this solution is the basic feasible
solution to the original LP problem.
Phase II: Using the solution shown in Table 4.23 as the initial solution for Phase II and carrying out
computations to get optimal solution as shown in Table 4.24.
cj → 3 2 2 0 0 0
cB B b (= xB)
2 x2 2/7 0 1 42 3 0 5 1/147
0 s2 0 0 0 521 37 1 63 0 →
3 x1 1 1 0 – 58 –6 0 –7 —
Z = 25/7 zj 3 2 – 90 –6 0 – 11 Table 4.24
c j – zj 0 0 92 6 0 11 Initial Solution
↑
In Table 4.24, c3 – z3 = 92 is the largest positive value corresponding non-basic variable x3, replacing basic
variable s2 with non-basic variable x3 into the basis. For this apply necessary row operations as usual. The new
solution is shown in Table 4.25.
cj → 3 2 2 0 0 0
Basic Variables Basic Basic Variables x1 x2 x3 s1 s2 s3
cB B b (= xB)
2 x2 2/7 0 1 0 9/521 – 42/521 – 41/521
2 x3 0 0 0 1 37/521 1/521 63/521
3 x1 1 1 0 0 62/521 58/521 7/521
Z = 25/7 zj 3 2 2 278/521 92/521 65/521 Table 4.25
c j – zj 0 0 0 –278/521 – 92/521 – 65/521 Optimal Solution
Since all cj – zj ≤ 0 in Table 4.25, the current solution is the optimal basic feasible solution: x1 = 1, x2 = 2/7,
x3 = 0 and Max Z = 25/7.
4.4.2 Big-M Method

Big-M method is another method of removing artificial variables from the basis. In this method, large
undesirable (unacceptable penalty) coefficients to artificial variables are assigned from the point of view
of the objective function. If the objective function Z is to be minimized, then a very large positive price
(called penalty) is assigned to each artificial variable. Similarly, if Z is to be maximized, then a very large
negative price (also called penalty) is assigned to each of these variables. The penalty is supposed to be
designated by – M, for a maximization problem, and + M, for a minimization problem, where M > 0. The
Big-M method for solving an LP problem can be summarized in the following steps:
Step 1: Express the LP problem in the standard form by adding slack variables, surplus variables and/or
artificial variables. Assign a zero coefficient to both slack and surplus variables. Then assign a very large
coefficient + M (minimization case) and – M (maximization case) to artificial variable in the objective function.
Step 2: The initial basic feasible solution is obtained by assigning zero value to decision variables, x1,
x2, ..., etc.
Step 3: Calculate the values of cj – zj in last row of the simplex table and examine these values.
(i) If all cj – zj ≥ 0, then the current basic feasible solution is optimal.
(ii) If for a column, k, ck – zk is most negative and all entries in this column are negative, then the
problem has an unbounded optimal solution.
(iii) If one or more cj – zj < 0 (minimization case), then select the variable to enter into the basis
(solution mix) with the largest negative cj – zj value (largest per unit reduction in the objective
function value). This value also represents the opportunity cost of not having one unit of the
variable in the solution. That is,
ck – zk = Min {cj – zj : cj – zj < 0}
Step 4: Determine the key row and key element in the same manner as discussed in the simplex algorithm
for the maximization case.
Step 5: Continue with the procedure to update solution at each iteration till optimal solution is obtained.
Remarks At any iteration of the simplex algorithm one of the following cases may arise:
1. If at least one artificial variable is a basic variable (i.e., variable that is present in the basis) with zero
value and the coefficient it M in each cj – zj ( j = 1, 2, . . ., n) values is non-negative, then the given
LP problem has no solution. That is, the current basic feasible solution is degenerate.
2. If at least one artificial variable is present in the basis with a positive value and the coefficients M in
each cj – zj ( j = 1, 2, . . ., n) values is non-negative, then the given LP problem has no optimum basic
feasible solution. In this case, the given LP problem has a pseudo optimum basic feasible solution.
Example 4.7 Use penalty (Big-M) method to solve the following LP problem.
Minimize Z = 5x1 + 3x2
(i) 2x1 + 4x2 ≤ 12, (ii) 2x1 + 2x2 = 10, (iii) 5x1 + 2x2 ≥ 10
and x1, x2 ≥ 0.
Solution Adding slack variable, s1; surplus variable, s2 and artificial variables, A1 and A2 in the
constraints of the given LP problem, the standard form of the LP problem becomes.
Minimize Z = 5x1 + 3x2 + 0s1 + 0s2 + MA1 + MA2
(i) 2x1 + 4x2 + s1 = 12, (ii) 2x1 + 2x2 + A1 = 10 (iii) 5x1 + 2x2 – s2 + A2 = 10
and x1, x2, s1, s2, A1, A2 ≥ 0
An initial basic feasible solution: s1 = 12, A1 = 10, A2 = 10 and Min Z = 10M + 10M = 20M is obtained
by putting x1 = x2 = s2 = 0. It may be noted that the columns that correspond to the current basic variables
and form the basis (identity matrix) are s1 (slack variable), A1 and A2 (both artificial variables). The initial basic
feasible solution is given in Table 4.26.
Since the value c1 – z1= 5 – 7M is the smallest value, therefore variable x1 is chosen to enter into the basis
(solution mix). To decide a current basic variable to leave the basis, calculate minimum ratio as shown in
Table 4.26.
cj → 5 3 0 0 M M
Basic Variables Basic Basic Variables x1 x2 s1 s2 A1 A2 Min Ratio
cB B b (= xB )
0 s1 12 2 4 1 0 0 0 12/2 = 6
M A1 10 2 2 0 0 1 0 10/2 = 5
M A2 10 5 2 0 –1 0 1 10/5 = 2 →
Z = 20M zj 7M 4M 0 – M M M
Table 4.26 cj – zj 5 – 7M 3 – 4M 0 M 0 0
Iteration 1: Introduce variable x1 into the basis and remove A2 from the basis by applying the following
row operations.
R3 (new) → R3 (old) ÷ 5 (key element); R2 (new) → R2 (old) – 2R3 (new).
R1 (new) → R1 (old) – 2R3 (new).
cj → 5 3 0 0 M
Basic Variables Basic Basic Variables x1 x2 s1 s2 A1 Min Ratio
cB B b (= xB )
0 s1 8 0 16/5 1 2/5 0 8/(16/5) = 5/2 →

M A1 6 0 6/5 0 2/5 1 6/(6/5) = 5
5 x1 2 1 2/5 0 – 1/5 0 2/(2/5) = 5
Z = 10 + 6M zj 5 (6M/5) + 2 0 (2M/5) – 1 M
cj – zj 0 (– 6M/5) + 1 0 (– 2M/5) + 1 0 Table 4.27
Iteration 2: Since the value of c2 – z2 in Table 4.27 is the largest negative value, variable x2 is chosen
to replace basic variable s1 in the basis. Thus, to get an improved basic feasible solution, apply, the
following row operations:
R1 (new) → R1 (old) × 5/16 (key element); R2 (new) → R2 (old) – (6/5) R1 (new).
R3 (new) → R3 (old) – (2/5) R1 (new).
cj → 5 3 0 0 M
Basic Variables Basic Basic Variables Min Ratio
Coefficient Variables Value x1 x2 s1 s2 A1 xB /s2
cB B b (= xB )
3 x2 5/2 0 1 5/16 1/8 0 (5/2)/(1/8) = 40
M A1 3 0 0 – 3/8 1/4 1 3/(1/4) = 12 →
5 x1 1 1 0 – 1/8 – 1/4 0
Z = 25/2 + 3M zj 5 3– 3M/8 + 5/16 M/4 – 7/8 M
cj – zj 0 03M/8 – 5/16 – M/4 + 7/8 0 Table 4.28
Improved Solution
↑
Iteration 3: Since c4 – z4 < 0 (negative) in s2-column, the current solution is not optimal. Thus, non-basic
variable s2 is chosen to replace artificial variable A1 in the basis. To get an improved basic feasible solution,
apply the following row operations:
R2 (new) → R2 (old) × 4 (key element); R1 (new) → R1 (old) – (1/8) R2 (new)
R3 (new) → R3 (old) + (1/4) R2 (new).
cj → 5 3 0 0
cB B b(= xB )
3 x2 1 0 1 1/2 0
0 s2 12 0 0 – 3/2 1
5 x1 4 1 0 – 1/2 0
Z = 23 zj 5 3 – 1 0 Table 4.29
cj – zj 0 0 1 0 Optimal Solution
In Table 4.24, all cj – zj ≥ 0. Thus an optimal solution is arrived at with the value of variables as:
x1 = 4, x2 = 1, s1 = 0, s2 = 12 and Min Z = 23.
Example 4.8 Use penalty (Big-M) method to solve the following LP problem.
Maximize Z = x1 + 2x2 + 3x3 – x4
(i) x1 + 2x2 + 3x3 = 15, (ii) 2x1 + x2 + 5x3 = 20, (iii) x1 + 2x2 + x3 + x4 = 10
and x1, x2, x3, x4 ≥ 0 [Calicut, BTech. (Engg), 2000; Bangalore BE (Mech.), 2000; AMIE, 2009]
Solution Since all constraints of the given LP problem are equations, therefore only artificial variables A1
and A2 are added in the constraints to convert given LP problem to its standard form. The standard form
of the problem is stated as follows:
Maximize Z = x1 + 2x2 + 3x3 – x4 – MA1 – MA2
(i) x1 + 2x2 + 3x3 + A1 = 15, (ii) 2x1 + x2 + 5x3 + A2 = 20
(iii) x1 + 2x2 + x3 + x4 = 10
and x1, x2, x3, x4, A1, A2 ≥ 0
An initial basic feasible solution is given in Table 4.30.
cj → 1 2 3 –1 – M – M
Coefficient Variables Value x1 x2 x3 x4 A1 A2 xB /x3
cB B b (= xB )
– M A1 15 1 2 3 0 1 0 15/3 = 5
– M A2 20 2 1 5 0 0 1 20/5 = 4 →
– 1 x4 10 1 2 1 1 0 0 10/1 = 10
Z = – 35M – 10 zj – 3M – 1 – 3M – 2 – 8M – 1 –1 – M – M
Table 4.30 cj – zj 3M + 2 3M + 4 8M + 4 0 0 0
Since value of c3 – z3 in Table 4.30 is the largest positive value, the non-basic variable x3 is chosen to replace
the artificial variable A2 in the basis. Thus, to get an improved solution, apply the following row operations.
R2 (new) → R1 (old) ÷ 5 (key element) ; R1 (new) → R1 (old) – 3 R2 (new).
cj → 1 2 3 –1 –M

Coefficient Variables Value x1 x2 x3 x4 A1 xB /x2
cB B b (= xB )
3 15
– M A1 3 – 1/5 7/5 0 0 1 = →
7/5 7
4
3 x3 4 2/5 1/5 1 0 0 = 20
15
/
6 30
– 1 x4 6 3/5 9/5 0 1 0 =
9/5 9
Z = – 3M + 6 zj M/5 + 3/5 – 7M/5 – 6/5 3 – 1 – M

Table 4.31 cj – zj – M/5 – 2/5 7M/5 + 16/5 0 0 0
Improved Solution
↑
Since value of c2 – z2 > 0 (positive) in Table 4.31, the non-basic variable x2 is chosen to replace the
artificial variable A1 in the basis. Thus, to get an improved basic feasible solution, apply the following row
operations:
R1 (new) → R1 (old) × (5/7) (key element); R2 (new) → R2 (old) – (1/5) R1 (new).

R3 (new) → R3 (old) – (9/5) R1 (new).
c j→ 1 2 3 – 1
Basic Variables Basic Basic Variables x1 x2 x3 x4 Min Ratio
cB B b(= xB )
2 x2 15/7 – 1/7 1 0 0 –
3 x3 25/7 3/7 0 1 0 25/7 × 7/3 = 25/3
–1 x4 15/7 6/7 0 0 1 15/7 × 7/6 = 15/6 →
Z = 90/7 zj 1/7 2 3 –1
cj – zj 6/7 0 0 0 Table 4.32
Improved Solution
↑
Once again, the solution shown in Table 4.32 is not optimal as c1 – z1 > 0 in x1-column. Thus, applying
the following row operations for replacing non-basic variable x1 in the basis with basic variable x4:
R3 (new) → R3 (old) × (7/6) (key element) ; R1 (new) → R1 (old) + (1/7) R3 (new).

R2 (new) → R2 (old) – (3/7) R3 (new).

cj → 1 2 3 – 1
Basic Variables Basic Basic Variables x1 x2 x3 x4
cB B b (= xB )
2 x2 15/6 0 1 0 1/6
3 x3 15/6 0 0 1 – 3/6
1 x1 15/6 1 0 0 7/6
Z = 15 zj 1 2 3 0 Table 4.33
cj – zj 0 0 0 – 1 Optimal Solution
In Table 4.28, since all cj – zj ≤ 0, therefore, an optimal solution is arrived at with value of variables
as: x1 = 15/6, x2 = 15/6, x3 = 15/6 and Max Z = 15.
Example 4.9 ABC Printing Company is facing a tight financial squeeze and is attempting to cut costs
wherever possible. At present it has only one printing contract, and luckily, the book is selling well in both the
hardcover and the paperback editions. It has just received a request to print more copies of this book in either
the hardcover or the paperback form. The printing cost for the hardcover books is Rs 600 per 100 books while
that for paperback is only Rs 500 per 100. Although the company is attempting to economize, it does not wish
to lay off any employee. Therefore, it feels obliged to run its two printing presses – I and II, at least 80 and 60
hours per week, respectively. Press I can produce 100 hardcover books in 2 hours or 100 paperback books in 1
hour. Press II can produce 100 hardcover books in 1 hour or 100 paperbacks books in 2 hours. Determine how
many books of each type should be printed in order to minimize costs.
Solution Let x1 and x2 be the number of batches containing 100 hard cover and paperback books, to
be printed respectively. The LP problem can then be formulated as follows.
Minimize Z = 600x1 + 500x2
(i) 2x1 + x2 ≥ 80, (ii) x1 + 2x2 ≥ 60 (Printing press hours)
and x1, x2 ≥ 0
Standard form Adding surplus variables s1, s2 and artificial variables A1, A2 in the the constraints, the
standard form of the LP problem becomes
Minimize Z = 600x1 + 500x2 + 0s1 + 0s2 + MA1 + MA2

(i) 2x1 + x2 – s1 + A1 = 80, (ii) x1 + 2x2 – s2 + A2 = 60
and x1, x2, s1, s2, A1, A2 ≥ 0
Solution by simplex method The initial basic feasible solution: A1 = 80, A2 = 60 and Min Z = 80M + 60M = 140M
obtained by putting x1 = x2 = s1 = s2 = 0 is shown in Table 4.34.
cj → 600 500 0 0 M M
Basic Variables Basic Basic Variables x1 x2 s1 s2 A1 A2 Min Ratio
cB B b(= xB )
M A1 80 2 1 – 1 0 1 0 80/1
M A2 60 1 2 0 – 1 0 1 60/2 →
Z = 140M zj 3M 3M – M – M M M
Table 4.34 cj – zj 600 – 3M 500 – 3M M M 0 0
Initial Solution
↑
Since c2 – z2 value in x2-column of Table 4.34 is the largest negative, therefore non-basic variable x2
is chosen to replace basic variable A2 in the basis. For this, apply following row operations.
R2 (new) = R2 (old) ÷ 2 (key element); R1 (new) → R1 (old) – R2 (new)
to get an improved basic feasible solution as shown in Table 4.35.
cj → 600 500 0 0 M
cB B b (= xB )
M A1 50 3/2 0 – 1 1/2 1 100/3 →
500 x2 30 1/2 1 0 – 1/2 0 60
Z = 15,000 + 50M zj 3M/2 + 250 500 –M M/2 – 250 M
Table 4.35 cj – zj 350 – 3M/2 0 M 250 – M/2 0
Improved Solution
↑
Again, since value c1 – z1 of in x1-column of Table 4.35 is the largest negative, non-basic variable x1
is chosen to replace basic variable A1 in the basis. For this, apply following row operations:
R1 (new) → R1 (old) × (2/3) (key element) ; R2 (new) → R2 (old) – (1/2) R1 (new)
to get an improved basic feasible solution as shown in Table 4.36.
cj → 600 500 0 0
cB B b (= xB )
600 x1 100/3 1 0 – 2/3 1/3
500 x2 40/3 0 1 1/3 – 2/3
Table 4.36 Z = 80,000/3 zj 600 500 – 700/3 – 400/3
Optimal Solution cj – zj 0 0 700/3 400/3
In Table 4.36, all cj – zj ≥ 0 and no artificial variable is present in the basis (solution mix). Hence, an
optimum solution is arrived at with x1 = 100/3 batches of hardcover books, x2 = 40/3 batches of paperback
books, at a total minimum cost, Z = Rs. 80,000/3.
Example 4.10 An advertising agency wishes to reach two types of audiences: Customers with annual
income greater than Rs 15,000 (target audience A) and customers with annual income less than Rs 15,000
(target audience B). The total advertising budget is Rs 2,00,000. One programme of TV advertising costs
Rs 50,000; one programme on radio advertising costs Rs 20,000. For contract reasons, at least three
programmes ought to be on TV, and the number of radio programmes must be limited to five. Surveys
indicate that a single TV programme reaches 4,50,000 customers in target audience A and 50,000 in target
audience B. One radio programme reaches 20,000 in target audience A and 80,000 in target audience B.
Determine the media mix to maximize the total reach. [Delhi Univ., MBA, 2000]
Solution Let x1 and x2 be the number of insertions in TV and radio, respectively. The LP problem can
then be formulated as follows:
Maximize (total reach) Z = (4,50,000 + 50,000) x1 + (20,000 + 80,000) x2
= 5,00,000 x1 + 1,00,000 x2 = 5x1 + x2
(i) 50,000 x1 + 20,000 x2 ≤ 2,00,000 or 5x1 + 2x2 ≤ 20 (Advt. budget)
(ii) x1 ≥ 3 (Advt. on TV) (iii) x2 ≤ 5 (Advt. on Radio)
and x1, x2 ≥ 0.
Standard form Adding slack/surplus and/or artificial variables in the constraints of LP problem. Then
standard form of given LP problem becomes
Maximize Z = 5x1 + x2 + 0s1 + 0s2 + 0s3 – MA1
(i) 5x1 + 2x2 + s1 = 20, (ii) x1 – s2 + A1 = 3, (iii) x2 + s3 = 5
and x1, x2, s1, s2, s3, A1 ≥ 0
Solution by simplex method An initial basic feasible solution: s1 = 20, A1 = 3, s3 = 5 and Max Z = – 3M
obtained by putting x1 = x2 = s2 = 0 is shown in simplex Table 4.37.
cj → 5 1 0 0 0 –M
Basic Variables Basic Basic Variables x1 x2 s1 s2 s3 A1 Min Ratio
cB B b(= xB )
0 s1 20 5 2 1 0 0 0 20/5 = 4
–M A2 3 1 0 0 –1 0 1 3/1 = 3 →
0 s3 5 0 1 0 0 1 0 —
Z = – 3M zj –M 0 0 M 0 –M
Table 4.37
cj – zj M+5 1 0 –M 0 0
Initial Solution
↑
The c1 – z1 value in x1-column of Table 4.37 is the largest positive value. The non-basic variable x1
is chosen to replace basic variable A1 in the basis. For this apply following row operations
R2 (new) → R2 (old) ÷ 1 (key element); R1 (new) → R1 (old) – 5R2 (new)
to get the improved basic feasible solution as shown in Table 4.38.
cj → 5 1 0 0 0
Basic Variables Basic Basic Variables x1 x2 s1 s2 s3 Min Ratio

Coefficient Variable Value xB /s2
cB B b( = xB )
0 s1 5 0 2 1 5 0 5/5 = 1 →
5 x1 3 1 0 0 – 1 0 —
0 s3 5 0 1 0 0 1 —
Z = 15 zj 5 0 0 – 5 0
cj – zj 0 1 0 5 0 Table 4.38
Improved Solution
↑
Again in Table 4.38, c4 – z4 value in s2-column is the largest positive. Thus non-basic variable s2 is
chosen to replace basic variable s1 into the basis. For this apply the following row operations:
R1 (new) → R1 (old) ÷ 5 (key element); R2 (new) → R2 (old) + R1 (new)
cj → 5 1 0 0 0
Basic Variables Basic Basic Variables x1 x2 s1 s2 s3
cB B b(= xB )
0 s2 1 0 2/5 1/5 1 0
5 x1 4 1 2/5 1/5 0 0
0 s3 5 0 1 0 0 1
Table 4.39 Z = 20 zj 5 2 1 0 0
Optimal Solution c j – zj 0 – 1 – 1 0 0
Since all cj – zj ≥ 0 in Table 4.39, the total reach of target audience cannot be increased further. Hence,
the optimal solution is: x1 = 4 insertions in TV and x2= 0 in radio with Max (total audience) Z = 20,00,000.
Example 4.11 An Air Force is experimenting with three types of bombs P, Q and R in which three kinds of
explosives, viz., A, B and C will be used. Taking the various factors into account, it has been decided to use the
maximum 600 kg of explosive A, at least 480 kg of explosive B and exactly 540 kg of explosive C. Bomb P requires
3, 2, 2 kg, bomb Q requires 1, 4, 3 kg and bomb R requires 4, 2, 3 kg of explosives A, B and C respectively. Bomb
P is estimated to give the equivalent of a 2 ton explosion, bomb Q, a 3 ton explosion and bomb R, a 4 ton
explosion respectively. Under what production schedule can the Air Force make the biggest bang?
Solution Let x1, x2 and x3 be the number of bombs of type P, Q and R to be experimented, respectively.
Then the LP problem can be formulated as:
(i) Explosive A : 3x1 + x2 + 4x3 ≤ 600, (ii) Explosive B : 2x1 + 4x2 + 2x3 ≥ 480,
(iii) Explosive C : 2x1 + 3x2 + 3x3 = 540,
and x1, x2, x3 ≥ 0.
Standard form Adding slack, surplus and artificial variables in the constraints of LP problem, the standard
form of LP problem becomes:
Maximize Z = 2x1 + 3x2 + 4x3, + 0s1 + 0s2 – MA1 – MA2
(i) 3x1 + x2 + 4x3 + s1 = 600, (ii) 2x1 + 4x2 + 2x3 – s2 + A1 = 480, (iii) 2x1 + 3x2 + 3x3 + A2 = 540,
and x1, x2, x3 s1, s2, A1, A2 ≥ 0.
Solution by simplex method The initial basic feasible solution: s 1 = 600, A 1 = 480, A 2 = 540,
Max Z = –1,020 M obtained by putting basic variables x1 = x2 = s2 = 0 is shown in Table 4.40.
cj Æ 2 3 4 0 0 –M –M
Basic Variables Basic Basic Variables x1 x2 x3 s1 s2 A1 A2 Min Ratio
cB B b (= xB)
0 s1 600 3 1 4 1 0 0 0 600/1
–M A1 480 2 4 2 0 –1 1 0 480/4 →
–M A2 540 2 3 3 0 0 0 1 540/3
Z = 1,020 M zj – 4M – 7M – 5M 0 M –M –M
Table 4.40 cj – zj 2 + 4M 3 + 7M 4 + 5M 0 –M 0 0
Since in Table 4.40, c2 – z2 value in x2–column is largest positive, non-basic variable x2 is chosen to replace
basic variable A1 in the basis. For this, apply the following row operations:
R2(new) → R2(old) × (1/4) (key element); R1(new) → R1(old) – R2(new);
R3(new) → R3(old) – 3R2(new)
cj Æ 2 3 4 0 0 –M
Basic Variables Basic Basic Variables x1 x2 x3 s1 s2 A1 Min Ratio
cB B b (= xB)
0 s1 480 5/2 0 7/2 1 1/4 0 960/7
3 x2 120 1/2 1 1/2 0 –1/4 0 240
–M A1 180 1/3 0 3/2 0 3/4 1 120 →
Z = 360 – 180M zj 3/2 – M/2 3 3/2 – 3M/2 0 –3/4 – 3M/4 –M
cj – zj 1/2 + M/2 0 5/2 + 3M/2 0 3/4 + 3M/4 0 Table 4.41
In Table 4.41, c3 – z3 value in x3-column is largest positive, non-basic variable x3 is chosen to replace basic
variable A2 into the basis. For this, apply following row operations:
R3(new) → R3(old) × (2/3) (key element); R1(new) → R1(old) – (7/2) R3(new);
R2(new) → R2(old) – (1/2) R3(new).
cj Æ 2 3 4 0 0
Basic Variables Basic Basic Variables x1 x2 x3 s1 s2

cB B b (= xB )
0 s1 60 4/3 0 0 1 –3/2
3 x2 60 1/3 1 0 0 –1/2
4 x3 120 1/3 0 1 0 1/2
Z = 660 zj 7/3 3 4 0 1/2 Table 4.42
cj – zj –1/3 0 0 0 –1/2 Optimal Solution
In Table 4.42, all cj – zj ≤ 0 and artificial variables A1 and A2 have been removed from the basis (solution
mix). Thus, an optimal solution is arrived at with x1 = 0 bombs of type P, x2 = 60 bombs of type Q, x3 = 120 bombs
of type R, at largest benefit of Z = 660.
SELF PRACTICE PROBLEMS A
1. A television company has three major departments for manufac- M3 and Belt C requires 5 hours on machine M2 and 4 hours on
turing two of its models – A and B. The monthly capacities of machine M3. There are 8 hours of time per day available on
the departments are given as follows: machine M1, 10 hours of time per day available on machine M2
and 15 hours of time per day available on machine M3. The profit
Per Unit Time gained from belt A is Rs 3.00 per unit, from Belt B is Rs 5.00
Requirement (hours) Hours Available per unit, from belt C is Rs 4.00 per unit. What should be the daily
Model A Model B this Month production of each type of belt so that the products yield the
maximum profit?
Department I 4.0 2.0 1,600 3. A company produces three products A, B and C. These
Department II 2.5 1.0 1,200 products require three ores O1, O2 and O3. The maximum
Department III 4.5 1.5 1,600 quantities of the ores O1, O2 and O3 available are 22 tonnes,
14 tonnes and 14 tonnes, respectively. For one tonne of each
The marginal profit per unit from model A is Rs 400 and from of these products, the ore requirements are:
model B is Rs 100. Assuming that the company can sell any
quantity of either product due to favourable market conditions, A B C
determine the optimum output for both the models, the highest
O1 3 – 3
possible profit for this month and the slack time in the three
departments. O2 1 2 3
O3 3 2 3
2. A manufacturer of leather belts makes three types of belts A,
Profit per tonne 1 4 5
B and C which are processed on three machines M1, M2 and
(Rs in thousand)
M3. Belt A requires 2 hours on machine M1 and 3 hours on
machine M2 and 2 hours on machine M3. Belt B requires 3 hours The company makes a profit of Rs 1,000, 4,000 and 5,000 on
on machine M1, 2 hours on machine M2 and 2 hours on machine each tonne of the products A, B and C, respectively. How many
tonnes of each product should the company produce in order 7. Mr Jain, the marketing manager of ABC Typewriter Company is
to maximize its profits. trying to decide how he should allocate his salesmen to the
4. A manufacturing firm has discontinued the production of a company’s three primary markets. Market I is in the urban area
certain unprofitable product line. This has created considerable and the salesman can sell, on the average, 40 typewriters a
excess production capacity. Management is considering to week. Salesmen in the other two markets, II and III can sell, on
devote this excess capacity to one or more of three products; the average, 36 and 25 typewriters per week, respectively. For
call them product 1, 2 and 3. The available capacity on the the coming week, three of the salesmen will be on vacation,
machines that might limit output is summarized in the following leaving only 12 men available for duty. Also because of lack of
table: company care, a maximum of 5 salesmen can be allocated to
market area I. The selling expenses per week for salesmen in
Machine Type Available Time each area are Rs 800 per week for area I, Rs 700 per week
(in Machine-hours per Week) for area II, and Rs 500 per week for area III. The budget for
the next week is Rs 7,500. The profit margin per typewriter is
Milling Machine 250 Rs 150. Determine how many salesmen should be assigned to
Lathe 150 each area in order to maximize profits?
Grinder 50 8. Three products – A, B and C – are produced in three machine
centres X, Y and Z. All three products require a part of their
The number of machine-hours required for each unit of the manufacturing operation at each of the machine centres. The
respective product is as follows: time required for each operation on various products is indicated
in the following table. Only 100, 77 and 80 hours are available
Machine Type Productivity at machine centres X, Y and Z, respectively. The profit per unit
(in Machine-hours per Unit) from A, B and C is Rs 12, Rs 3 and Re 1, respectively.
Product Product Product

Products Machine Centres Profit per
1 2 3
Unit (Rs)
X Y Z
Milling Machine 8 2 3
Lathe 4 3 0 A 10 7 2 12
B 2 3 4 3
Grinder 2 – 1
C 1 2 1 1
The profit per unit would be Rs 20, Rs 6 and Rs 8, respectively Available hours 100 77 80
for product 1, 2 and 3. Find how much of each product the firm
(a) Determine suitable product mix so as to maximize the
should produce in order to maximize its profit.
profit. Comment on the queries (b) and (c) from the solution
[Delhi Univ., MBA 2006]
table obtained.
5. A farmer has 1,000 acres of land on which he can grow corn, (b) Satisfy that full available hours of X and Y have been
wheat or soyabean. Each acre of corn costs Rs 100 for utilized and there is surplus hours of Z. Find out the surplus
preparation, requires 7 men-days of work and yields a profit of hours of Z.
Rs 30. An acre of wheat costs Rs 120 to prepare, requires 10 (c) Your aim is to utilize surplus capacity of Z. Can you say
men-days of work and yields a profit of Rs 40. An acre of from the table that the introduction of more units of Y is
soyabean costs Rs 70 to prepare, requires 8 men-days of work required ?
and yields a profit of Rs 20. If the farmer has Rs 1,00,000 for 9. A certain manufacturer of screw fastenings found that there is
preparation and can count on 8,000 men-days of work, deter- a market for packages of mixed screw sizes. His market
mine how many acres should be allocated to each crop in order research data indicated that two mixtures of three screw types
to maximize profits? [Delhi Univ., MBA, 2004] (1, 2 and 3), properly priced, could be most acceptable to the
6. The annual handmade furniture show and sale is supposed to public. The relevant data is:
take place next month and the school of vocational studies is
also planning to make furniture for this sale. There are three Mixture Specifications Selling Price (Rs/kg)
wood-working classes – I year, II year and III year, at the school
A ≥ 50% type 1 5
and they have decided to make styles of chairs – A, B and C.
Each chair must receive work in each class. The time in hours ≤ 30% type 2
required for each chair in each class is: and quantity of type 3
B ≥ 35% type 1 4
Chair I Year II Year III Year ≤ 45% type 2
and quantity of type 3
A 2 4 3
B 3 3 2 For these screws, the plant capacity and manufacturing cost
C 2 1 4 are as follows:
During the next month there will be 120 hours available to the
Screw Type Plant Capacity Manufacturing Cost
I year class, 160 hours to the II year class, and 100 hours to
(kg/day × 100) (Rs/kg)
the III year class for producing the chairs. The teacher of the
wood-working classes feels that a maximum of 40 chairs can 1 10 4.50
be sold at the show. The teacher has determined that the profit 2 10 3.50
from each type of chair will be: A, Rs 40; B, Rs 35 and C, Rs. 3 6 2.70
30. How many chairs of each type should be made in order to
maximize profits at the show and sale? What production shall this manufacturer schedule for greatest
profit, assuming that he can sell all that he manufactures?
10. A blender of whisky imports three grades A, B and C. He mixes 15. A marketing manager wishes to allocate his annual advertising
them according to the recipes that specify the maximum or budget of Rs 2,00,000 to two media vehicles – A and B. The
minimum percentages of grades A and C in each blend. These unit cost of a message in media A is Rs 1,000 and that of B
are shown in the table below. is Rs 1,500. Media A is a monthly magazine and not more than
one insertion is desired in one issue, whereas at least five
Blend Specification Price per Unit messages should appear in media B. The expected audience for
(Rs) unit messages in media A is 40,000 and that of media B is
55,000. Develop an LP model and solve it for maximizing the
Blue Dot Not less than 60% of A 6.80
total effective audience.
Not more than 20% of C
16. A transistor radio company manufactures four models A, B, C
Highland Not more than 60% of C 5.70
and D. Models A, B and C, have profit contributions of Rs 8, Rs
Fling Not less than 15% of A 15 and Rs 25 respectively and has model D a loss of Re 1.
Old Frenzy Not more than 50% of C 4.50 Each type of radio requires a certain amount of time for the
manufacturing of components, for assembling and for packing.
Following are the supplies of the three whiskies along with their
A dozen units of model A require one hour for manufacturing,
cost.
two hours for assembling and one hour for packing. The
Whisky Maximum Quantity Cost per corresponding figures for a dozen units of model B are 2, 1 and
Available per Day Unit (Rs) 2, and for a dozen units of C are 3, 5 and 1. A dozen units of
model D however, only require 1 hour of packing. During the
A 2,000 7.00 forthcoming week, the company will be able to make available
B 2,500 5.00 15 hours of manufacturing, 20 hours of assembling and 10
C 1,200 4.00 hours of packing time. Determine the optimal production sched-
ule for the company.
Show how to obtain the first matrix in a simplex computation of
a production policy that will maximize profits. 17. A transport company is considering the purchase of new
11. An animal feed company must produce on a daily basis 200 kg vehicles for providing transportation between the Delhi Airport
of a mixture that consists ingredients x1 and x2 ingredient. x1 and hotels in the city. There are three vehicles under consid-
costs Rs 3 per kg and x2 costs Rs 8 per kg. Not more than eration: Station wagons, minibuses and large buses. The pur-
80 kg of x1 can be used and at least 60 kg of x2 must be used. chase price would be Rs 1,45,000 for each station wagon, Rs
Find out how much of each ingredient should be used if the 2,50,000 for each minibus and Rs 4,00,000 for each large bus.
company wants to minimize costs. The board of directors has authorized a maximum amount of Rs
50,00,000 for these purchases. Because of the heavy air travel,
12. A diet is to contain at least 20 ounces of protein and 15 ounces
the new vehicles would be utilized at maximum capacity,
of carbohydrate. There are three foods A, B and C available in the
regardless of the type of vehicles purchased. The expected net
market, costing Rs 2, Re 1 and Rs 3 per unit, respectively. Each
annual profit would be Rs 15,000 for the station wagon,
unit of A contains 2 ounces of protein and 4 ounces of carbohy-
Rs 35,000 for the minibus and Rs 45,000 for the large bus. The
drate; each unit of B contains 3 ounces of protein and 2 ounces
company has hired 30 new drivers for the new vehicles. They
of carbohydrate; and each unit of C contains 4 ounces of protein
are qualified drivers for all three types of vehicles. The mainte-
and 2 ounces of carbohydrate. How many units of each food
nance department has the capacity to handle an additional 80
should the diet contain so that the cost per unit diet is minimum?
station wagons. A minibus is equivalent to 1.67 station wagons
13. A person requires 10, 12 and 12 units of chemicals A, B and C, and each large bus is equivalent to 2 station wagons in terms
respectively for his garden. A typical liquid product contains 5, 2 of their use of the maintenance department. Determine the
and 1 unit of A, B and C, respectively per jar. On the other hand number of each type of vehicle that should be purchased in
a typical dry product contains 1, 2 and 4 units of A, B and C per order to maximize profit.
unit. If the liquid product sells for Rs 3 per jar and the dry product
18. Omega Data Processing Company performs three types of activi-
for Rs 2 per carton, how many of each should be purchased in
ties: Payroll, accounts receivables, and inventories. The profit and
order to minimize the cost and meet the requirement?
time requirement for keypunch, computation and office printing, for
14. A scrap metal dealer has received an order from a customer a standard job, are shown in the following table:
for a minimum of 2,000 kg of scrap metal. The customer
requires that at least 1,000 kg of the shipment of metal be of Job Profit/ Time Requirement (Min)
high quality copper that can be melted down and used to Standard
produce copper tubing. Furthermore, the customer will not
Job (Rs) Keypunch Computation Printing
accept delivery of the order if it contains more than 175 kg metal
that he deems unfit for commercial use, i.e. metal that contains Payroll 275 1,200 20 100
an excessive amount of impurities and cannot be melted down
A/c Receivable 125 1,400 15 60
and refined profitably.
Inventory 225 800 35 80
The dealer can purchase scrap metal from two different suppli-
ers in unlimited quantities with following percentages (by weight) Omega guarantees overnight completion of the job. Any job
of high quality copper and unfit scrap. scheduled during the day can be completed during the day or
night. Any job scheduled during the night, however, must be
Supplier A Supplier B
completed during the night. The capacities for both day and night
Copper 25% 75% are shown in the following table:
Unfit scrap 5% 10%
Capacity (Min) Keypunch Computation Print
The cost per kg of metal purchased from supplier A and B are Re 1
and Rs 4, respectively. Determine the optimal quantities of metal to Day 4,200 150 400
be purchased for the dealer from each of the two suppliers. Night 9,200 250 650
Determine the mixture of standard jobs that should be accepted The sales revenue per unit of waste cans, filing cabinets,
during the day and night. correspondence boxes and lunch boxes are Rs 20, Rs 400,
Rs 90 and Rs 20, respectively. There are 225 units of sheet
19. A furniture company can produce four types of chairs. Each chair
metal A available in the company’s inventory, 300 of sheet metal
is first made in the carpentry shop and then furnished, waxed and
B, and a total of 190 units of manual labour. What is the
polished in the finishing shop. The man-hours required in each are:
company’s optimal sales revenue?
Chair Type [Delhi Univ., MBA, 2003, 2005]
21. A company mined diamonds in three locations in the country. The
1 2 3 4
three mines differed in terms of their capacities, number, weight
Carpentry shop 4 9 7 10 of stones mined, and costs. These are shown in the table below:
Due to marketing considerations, a monthly production of exactly
Finishing shop 1 1 3 40
1,48,000 stones was required. A similar requirement called for at
Contribution per chair (Rs) 12 20 18 40 least 1,30,000 carats (The average stone size was at least 130/148
= 0.88 carats). The capacity of each mine is measured in cubic
The total number of man-hours available per month in carpentry meter. The mining costs are not included from the treatment costs
and finishing shops are 6,000 and 4,000, respectively. and assume to be same at each mine. The problem for the company
Assuming an abundant supply of raw material and an abundant was to meet the marketing requirements at the least cost.
demand for finished products, determine the number of each
type of chairs that should be produced for profit maximization. Capacity Treatment Crude Stone Count
20. A metal products company produces waste cans, filing cabinets, (M 3 of Costs (Carats (Number of
file boxes for correspondence, and lunch boxes. Its inputs are Mine earth (Rs. per M 3) per M 3) stone per
sheet metal of two different thickness, called A and B, and processed) M 3)
manual labour. The input-output relationship for the company are
shown in the table given below: Plant 1 83,000 0.60 0.360 0.58
Plant 2 3,10,000 0.36 0.220 0.26
Waste Filing Correspondence Lunch Plant 3 1,90,000 0.50 0.263 0.21
Cans Cabinets Boxes Boxes
Formulate a linear programming model to determine how much
Sheet metal A 6 0 2 3 should be mined at each location.
Sheet metal B 0 10 0 0
Manual labour 4 8 2 3
HINTS AND ANSWERS
1. Let x1 and x2 = units of models A and B to be manufactured, 4. Let x1, x2 and x3 = number of units of products 1, 2 and 3
respectively. to be produced per week, respectively.
Max Z = 400x1 + 400x2 Max Z = 20x1 + 6x2 + 8x3
subject to 4x1 + 2x2 ≤ 1,600 subject to 8x1 + 2x2 + 3x3 ≤ 250
5x1/2 + x2 ≤ 1,200 4x1 + 3x2 ≤ 150
9x1/2 + 3x2/2 ≤ 1,600 2x1 + x3 ≤ 50
and x1 , x 2, x3 ≥ 0
and x1 , x 2 ≥ 0
Ans. x1 = 0, x2 = 50, x3 = 50 and Max Z = 700.
Ans. x1 = 355.5, x2 = 0 and Max Z = 1,42,222.2.
5. Let x1, x2 and x3 = acreage of corn, wheat and soyabean,
2. Let x1, x2 and x3 = units of types A, B and C belt to be
respectively.
manufactured, respectively.
Max Z = 30x1 + 40x2 + 20x3
Max Z = 3x1 + 5x2 + 4x3
subject to 10x1 + 12x2 + 7x3 ≤ 10,000
subject to 2x1 + 3x2 ≤ 8
7x1 + 10x2 + 8x3 ≤ 8,000
2x2 + 5x3 ≤ 10
3x1 + 2x2 + 4x3 ≤ 15 x1 + x2 + x3 ≤ 1,000
and x1, x2, x 3 ≥ 0 and x1 , x 2, x3 ≥ 0
Ans. x1 = 89/41, x2 = 50/41 x3 = 64/41 and Max Z = 775/41. Ans. x1 = 250, x2 = 625, x3 = 0 and Max Z = Rs 32,500.
6. Let x1, x2 and x3 = number of units of chair of styles A, B
3. Let x1, x2 and x3 = quantity of products A, B and C to be and C, respectively.
produced, respectively.
Max Z = 40x1 + 35x2 + 30x3
Max Z = x1 + 4x2 + 5x3
subject to 2x1 + 3x2 + 2x3 ≤ 120
subject to 3x1 + 3x2 ≤ 22 4x1 + 3x2 + x3 ≤ 160
x1 + 2x2 + 3x3 ≤ 14 3x1 + 2x2 + 4x3 ≤ 100
3x1 + 2x2 ≤ 14 x1 + x2 + x3 ≤ 40
and x1, x2, x 3 ≥ 0 and x1 , x 2, x3 ≥ 0
Ans. x1 = 0, x2 = 7, x3 = 0 and Max Z = Rs 28,000. Ans. x1 = 20, x2 = 20, x3 = 0 and Max Z = Rs 1,500.
7. Let x1, x2 and x3 = salesman assigned to area, 1, 2 and 3, subject to (i) x1 + 2x2 + 3x3 = 15; (ii) 2x1 + x2 + 5x3 = 20
respectively. (iii) x1 + 2x2 + x3 + x4 = 10
Max. Z = 40 × 150x1 + 36 × 150x2 + 25 × 150x3 and x1, x 2, x 3 , x 4 ≥ 0
– (800x1 + 700x2 + 500x3) Ans. x1 = 5/2, x2 = 5/2, x3 = 5/2, x4 = 0 and Max Z = 120.
subject to (i) x1 + x2 + x3 ≤ 12; (ii) x1 ≤ 5;
17. Let x1, x2 and x3 = number of station wagons, minibuses and
(iii) 800x1 + 700x2 + 500x3 ≤ 7,500 large buses to be purchased, respectively.
and x1, x 2, x3 ≥ 0 Max Z = 15,000x1 + 35,000x2 + 45,000x3
11. Let x and y = number of kg of ingredients x1, x2, respectively. subject to x1 + x2 + x3 ≤ 30
Min (total cost) Z = 3x + 8y 1,45,000x1 + 2,50,000x2 + 4,00,000x3 ≤ 50,00,000
subject to (i) x + y = 200; (ii) x ≤ 80; (iii) y ≥ 60 x1 + 1.67x2 + 0.5x3 ≤ 80
and x, y ≥ 0 and x1, x2 , x3 ≥ 0
Ans. x = 80, y = 120 and Min Z = Rs 1,200.
18. Let xij represents ith job and jth activity
12. Let x1, x2 and x3 = number of units of food A, B and C,
Max Z = 275 (x11 + x12 ) + 125(x21 + x22 ) + 225 (x31 + x32 )
respectively which a diet must contain.
subject to
Min (total cost ) Z = 2x1 + x2 + x3
1,200 (x11 + x12 ) + 1,400 (x21 + x22 )
subject to 2x1 + 2x2 + 4x3 ≥ 20
+ 800 (x31 + x32 ) ≤ 13,400
4x1 + 2x2 + 2x3 ≥ 15
20 (x11 + x12 ) + 15 (x21 + x22 ) + 35 (x31 + x32 ) ≤ 400
and x1, x2, x3 ≥ 0
100 (x11 + x12 ) + 60 (x21 + x22 ) + 80 (x31 + x32 ) ≤ 1,050
13. Let x1 and x2 = number of units of liquid and dry product
produced, respectively. 1,200x12 + 1,400x22 + 800x32 ≤ 9,200
Min (total cost) Z = 3x1 + 2x2 20x12 + 15x22 + 35x32 ≤ 250
subject to (i) 5x1 + x2 ≥ 10; (ii) 2x1 + 2x2 ≥ 12; 100x12 + 60x22 + 80x32 ≤ 650
(iii) x1 + 4x2 ≥ 12 and xij ≥ 0 for all i, j
and x1, x 2 ≥ 0 19. Let x1, x2, x3 and x4 = chair types 1, 2, 3 and 4 to be produced,
Ans. x1 = 1, x2 = 5 and Min Z = 13. respectively.
14. Let x1 and x2 = number of scrap (in kg) purchased from Max Z = 12x1 + 20x2 + 18x3 + 40x4
suppliers A and B, respectively.
subject to 4x1 + 9x2 + 7x3 + 10x4 ≤ 6,000
Min (total cost) Z = x1 + 4x2
x1 + x2 + 3x3 + 40x4 ≤ 4,000
subject to 2.25x1 + 0.75x2 ≥ 1,000
0.05x1 + 0.10x2 ≥ 175 and x1, x2, x3 , x4 ≥ 0
x1 + x2 ≥ 2,000 Ans. x1 = 4,000/3, x2 = x3 = 0, x4 = 200/3 and Max Z =
and x1, x 2 ≥ 0 Rs 56,000/3.
Ans. x1 = 2,500, x2 = 500 and Min Z = 4,500. 21. Let x1, x2 and x3 = cubic metric of earth processed at plants
15. Let x1 and x2 = number of insertions messages for media A and 1, 2 and 3, respectively.
B, respectively. Min Z = 0.60x1 + 0.36x2 + 0.50x3
Min (total effective audience) Z = 40,000x1 + 55,000x2 subject to
subject to (i) 1,000x1 + 1500x2 ≤ 2,00,000; 0.58x1 + 0.26x2 + 0.21x3= 1,48,000 (Stone count requirement)
(ii) x1 ≤ 12; (iii) x2 ≥ 5
0.36x1 + 0.22x2 + 0.263x3≤ 1,30.000 (Carat requirement)
and x1, x 2 ≥ 0
x1 ≤ 83,000; x2 ≤ 3,10,000;
Ans. x1 = 12, x2 = 16/3 and Max Z = 77,3333.33.
16. Let x1, x2, x3 and x4 = unit of models A, B, C and D to be x3 ≤ 1,90,000 (Capacity requirement)
produce, respectively. Ans. x1 = 61,700; x2 = 3,10,000; x3 = 1,50,500
Max (total income) Z = 8x1 + 15x2 + 25x3 – x4 and Min Z = Rs 2,23,880.
4.5 SOME COMPLICATIONS AND THEIR RESOLUTION

In this section, some of the complications that may arise in applying the simplex method for solving both
maximization and minimization LP problems and their resolution are discussed.
4.5.1 Unrestricted Variables

In actual practice, decision variables, xj ( j = 1, 2, . . ., n) should have non-negative values. However, in many
situations, one or more of these variables may have either positive, negative or zero value. Variables that can
assume positive, negative or zero value are called unrestricted variables. Since use of the simplex method
requires that all the decision variables must have non-negative value at each iteration, therefore in order to
convert an LP problem involving unrestricted variables into an equivalent LP problem having only non-
negative variables, each of unrestricted variable is expressed as the difference of two non-negative variables.
Let variable xr be unrestricted in sign. We define two new variables say xr′ and xr′′ such that
xr = xr′ – xr′′ ; xr′ , xr′′ ≥ 0
If xr′ ≥ xr′′ , then xr ≥ 0, but and if xr′ ≤ xr′′ , then xr ≤ 0. Also if xr′ = xr′′ , then xr = 0. Hence depending on the
value of xr′ and xr′′ , the variable xr can have either positive or negative sign. For example, the following LP
problem
n
Maximize Z = ∑ c j x j + cr xr
j≠r
An unrestricted subject to the constraints
variable in an LP
model can have n
either positive, ∑ a ij x j + air xr = bi , i = 1, 2, . . ., m
negative or zero j≠r
value. and xj ≥ 0, and xr unrestricted in sign; j = 1, 2, . . ., n, j ≠ r;
can be converted into its equivalent standard form as follows:
n
Maximize Z = ∑ cj xj + c r ( x r′ + x r′′ )
j≠r

n
∑ a ij x j + a ir ( x r′ − x r′′ ) = bi , i = 1, 2, . . ., m
j≠r
and xj , xr′ , xr′′ ≥ 0; j = 1, 2, . . ., n, j ≠ r.

Variables xr′ and xr′′ simultaneously cannot appear in the basis (since the column vectors correspond-
ing to these variables are linearly dependent). Thus any of the following three cases may arise at the optimal
solution:
(i) xr′ = 0 ⇒ xr = – xr′′ (ii) xr′′ = 0 ⇒ xr = xr′ (iii) xr′ = xr′′ = 0 ⇒ xr = 0
This indicates that the value of xr′ and xr′′ uniquely determines the values of the variable xr.
Example 4.12 Use the simplex method to solve the following LP problem.
Maximize Z = 3x1 + 2x2 + x3
(i) 2x1 + 5x2 + x3 = 12, (ii) 3x1 + 4x2 = 11
and x2, x3 ≥ 0, and x1 unrestricted [Bombay, BSc (Maths), 2001]
Solution Introducing an artificial variable A1 in the second constraint of the given LP problem in order
to obtain the basis matrix as shown in Table 4.43. Since x1 is unrestricted in sign, introducing the non-
negative variables x1′ and x 2′′ so that x1 = x1′ – x1′′ , where x1′ , x1′′ ≥ 0. The standard form of the LP
problem now becomes:
Maximize Z = 3 ( x1′ – x1′′ ) + 2x2 + x3 – MA1
(i) 2 ( x1′ − x1′′ ) + 5x2 + x3 = 12, (ii) 3 ( x1′ − x1′′ ) + 4x2 + A1 = 11
and x1′ , x1′′ , x2, x3 , A1 ≥ 0
The initial solution is shown in Table 4.43.
cj → 3 – 3 2 1 – M
Basic Variables Basic Basic Variables x1′ x1′′ x2 x3 A1 Min Ratio

B b(= xB)
1 x3 12 2 –2 5 1 0 12/5 →
– M A1 11 3 –3 4 0 1 11/4
Z = – 11M + 12 zj – 3M + 2 3M – 2 – 4M + 5 1 – M
Table 4.43
cj – zj 3M + 1 – 3M – 1 4M – 3 0 0 Initial Solution
↑
In Table 4.43, c3 – z3 is the largest positive value, the non-basic variable x2 is chosen to enter into
the basis to replace basic variable x3 in the basis. For this, apply the following row operations:
R1 (new) → R1 (old)/5 (key element) R2 (new) → R2 (old) – 4R1 (new).
to get an improved solution shown in Table 4.44.
cj → 3 –3 2 1 –M
Basic Variables Basic Basic Variables x1′ x1′′ x2 x3 A1 Min Ratio

Coefficient Variables Value xB / x1′
B b(= xB)
12 5
2 x2 12/5 2/5 –2/5 1 1/5 0 × =6
5 2
7 5
– M A1 7/5 7/5 –7/5 0 – 4/5 1 × =1→
5 7
Z = – 7M/5 + 24/5 zj – 7M/5 + 4/5 7M/5 – 4/5 2 4M/5 + 2/5 – M
Table 4.44
cj – zj 7M/5 + 11/5 – 7M/5 – 11/5 0 – 4M/5 + 3/5 0
Improved Solution
↑
In Table 4.44, as c1 – z1 in x'1-column is positive, the non-basic variable x'1 is chosen to enter into
the basis to replace basic variable A1 in the basis. For this, apply the following row operations:
R2 (new) → R2 (old) × (5/7) (key element); R1 (new) → R1 (old) – (2/5) R2 (new).
to get an improved solution shown in Table 4.45.
cj → 3 –3 2 1
Basic Variables Basic Basic Variables x1′ x1′′ x2 x3 Min Ratio

B b(= xB )
2 x2 2 0 0 1 3/7 2/(3/7) = 14/3 →

3 x1′ 1 1 –1 0 – 4/7 —
Z = 7 zj 3 – 3 2 – 6/7
cj – zj 0 0 0 13/7 Table 4.45
Improved Solution
↑
Further, in order to improve the solution given in Table 4.45, the non-basic variable x3 is chosen to
enter into the basis and remove basic variable x2 from the basis. For this, apply the following row
operations:
R1 (new) → R1 (old ) × (7/3) (key element); R2 (new) → R2 (old) + (4/7) R1 (new)
to get an improved solution given in Table 4.46.

cj → 3 – 3 2 1
Basic Variables Basic Basic Variables x1′ x1′′ x2 x3

. B b(= xB )
1 x3 14/3 0 0 7/3 1
3 x1′ 11/3 1 –1 4/3 0
Table 4.46 Z = 47/3 zj 3 –3 19/3 1
Optimal Solution cj – zj 0 0 – 13/3 0
Since in Table 4.46 all cj – zj ≤ 0, an optimal solution: x1′ = 11/3 or x1 = x1′ – x1′′ = 11/3 – 0 = 11/3;
x3 = 14/3 is arrived with Max Z = 47/3.
4.5.2 Tie for Entering Basic Variable (Key Column)

While solving an LP problem using simplex method two or more columns of simplex table may have same
cj – zj value (positive or negative depending upon the type of LP problem). In order to break this tie, the
selection for key column (entering variable) can be made arbitrary. However, the number of iterations
required to arrive at the optimal solution can be minimized by adopting the following rules:
(i) If there is a tie between two decision variables, then the selection can be made arbitrarily.
(ii) If there is a tie between a decision variable and a slack (or surplus) variable, then select the
decision variable to enter into basis.
(iii) If there is a tie between two slack (or surplus) variables, then the selection can be made arbitrarily.
4.5.3 Tie for Leaving Basic Variable (Key Row) – Degeneracy

While solving an LP problem a situation may arise where either the minimum ratio to identify the basic
variable to leave the basis is not unique or value of one or more basic variables in the xB becomes zero.
This causes the problem of degeneracy.
Usually, the problem of degeneracy arises due to redundant constraint, i.e. one or more of the constraints
of LP problem are not part of feasible solution space. For example, constraints such as x1 ≤ 5, x2 ≤ 5 and x1
+ x2 ≤ 5 in the LP problem make constraint x1 + x2 ≤ 5 unnecessary (redundant).
Degeneracy may occur at any iteration of the simplex method. In order to break the tie in the minimum
ratios, the selection can be made arbitrarily. However, the number of iterations required to arrive at the
optimal solution can be minimized by adopting the following rules.
(i) Divide the coefficients of slack variables in the simplex table where degeneracy is seen by the
corresponding positive numbers of the key column in the row, starting from left to right.
(ii) Compare the ratios in step (i) from left to right columnwise, select the row that contains the smallest
ratio.
Remark When there is a tie between a slack and artificial variable to leave the basis, preference should
be given to the artificial variable for leaving the basis.
Example 4.13 Solve the following LP problem

Maximize Z = 3x1 + 9x2
(i) x1 + 4x2 ≤ 8, (ii) x1 + 2x2 ≤ 4
and x1, x2 ≥ 0
Solution Adding slack variables s1 and s2 to the constraints, the problem can be expressed as
Maximize Z = 3x1 + 9x2 + 0s2 + 0s2
(i) x1 + 4x2 + s1 = 8, (ii) x1 + 2x2 + s2 = 4
and x1, x2, s1, s2 ≥ 0
The initial basic feasible solution is given in Table 4.47. Since c2 – z2 = 9 is the largest positive value,
therefore, variable x2 is selected to be entered into the basis. However, both variables s1 and s2 are eligible
to leave the basis as the minimum ratio is same, i.e. 2, so there is a tie among the ratio in rows s1 and s2.
This causes the problem of degeneracy. To obtain the key row for resolving degeneracy, apply the following
procedure:
(i) Write the coefficients of the slack variables as shown in Table 4.47.
cj → 3 9 0 0
Basic Variables Basic Basic Variables x1 x2 s1 s2 Min Ratio
B b(= xB )
0 s1 8 1 4 1 0 8/4 = 2 

0 s2 4 1 2 0 1 4/2 = 2 
Z = 0 zj 0 0 0 0
cj – zj 3 9 0 0 Table 4.47
x2-column Column
Row (Key Column) s1 s2
s1 4 1 0
s2 2 0 1
(ii) Dividing the coefficients of slack variables s1 and s2 by the corresponding elements in the key
column as shown below in the table.
x2-column Column
Row (Key Column) s1 s2
s1 4 1/4 = 1/4 0/4 = 0

s2 2 0/2 = 0 1/2 = 1/2
(iii) Comparing the ratios of Step (ii) from left to right columnwise, the minimum ratio (i.e., 0/2 = 0)
occurs in the s2-row. Thus, variable s2 is selected to leave the basis. The new solution is shown
in Table 4.48.
cj → 3 9 0 0
B b(= xB)
0 s1 0 –1 0 1 –2
9 x2 2 1/2 1 0 1/2
Z = 18 zj 9/2 9 0 9/2 Table 4.48
cj – zj – 3/2 0 0 – 9/2 Optimal Solution
In Table 4.48, all cj – zj ≤ 0. Hence, an optimal solution is arrived at. The optimal basic feasible solution
is: x1 = 0, x2 = 2 and Max Z = 18.
4.6 TYPES OF LINEAR PROGRAMMING SOLUTIONS

While solving any LP problem using simplex method, at the stage of optimal solution, the following three
types of solutions may exist:
4.6.1 Alternative (Multiple) Optimal Solutions

The cj – zj values in the simplex table indicates the contribution in the objective function value by each unit of
a variable chosen to enter into the basis. Also, an optimal solution to a maximization LP problem is reached
when all cj – zj ≤ 0. But, if cj – zj = 0 for a non-basic variable column in the optimal simplex table and such non-
basic variable is chosen to enter into the basis, then another optimal solution so obtained will show no
improvement in the value of objective function.
Example 4.14 Solve the following LP problem.

Alternative optimal Maximize Z = 6x1 + 4x2
solutions arise
when cj – zj = 0 for subject to the constraints
non-basic variable (i) 2x1 + 3x2 ≤ 30, (ii) 3x1 + 2x2 ≤ 24, (iii) x1 + x2 ≥ 3
columns in the
and x1, x2 ≥ 0.
simplex table.
Solution Adding slack variables s1, s2, surplus variable s3 and artificial variable A1 in the constraint set,
the LP problem becomes
Maximize Z = 6x1+ 4x2 + 0s1 + 0s2 + 0s3 – MA1
(i) 2x1 + 3x2 + s1 = 30, (ii) 3x1 + 2x2 + s2 = 24 (iii) x1 + x2 – s3 + A1 = 3
and x1, x2, s1, s2, s3, A1 ≥ 0
The optimal solution: x1 = 8, x2 = 0 and Max Z = 48 for this LP problem is shown in Table 4.49.
cj → 6 4 0 0 0
Basic Variables Basic Basic Variables x1 x2 s1 s2 s3 Min Ratio

B b(= xB )
0 s1 14 0 5/3 1 – 2/3 0 14/(15/3) = 42/5 →

0 s3 5 0 – 1/3 0 1/3 1 —
6 x1 8 1 2/3 0 1/3 0 8/(2/3) = 12
Z = 48 zj 6 4 0 2 0
Table 4.49 cj – zj 0 0 0 – 2 0
Optimal Solution
↑
In Table 4.49, c2 – z2 = 0 corresponds to a non-basic variable, x2. Thus, an alternative optimal solution
can also be obtained by entering variable x2 into the basis and removing basic variable, s1 from the basis.
cj → 6 4 0 0 0
Basic Variables Basic Basic Variables x1 x2 s1 s2 s3
B b(= xB )
4 x2 42/5 0 1 3/5 – 2/5 0

0 s3 39/5 0 0 1/5 1/5 1
6 x1 12/5 1 0 – 2/5 3/5 0
Table 4.50
Alternative Z = 48 zj 6 4 0 2 0
Solution c j – zj 0 0 0 –2 0
The optimal solution shown in Table 4.50 is: x1 = 12/5, x2 = 42/5 and Max Z = 48. Since this optimal
solution shows no change in the value of objective function, it is an alternative solution.
Once again, c3 – z3 = 0 corresponds to non-basic variable, s1. This again indicates that an alternative
optimal solution exists. The infinite number of solutions that can be obtained for this LP problem are as
follows:
Variables Solution Values General Solution
1 2
x1 8 12/5 x1 = 8λ + (12/5) (1 – λ)
x2 0 42/5 x2 = 0λ + (42/5) (1 – λ)
s1 14 0 s1 = l4 λ + (0) (1 – λ)
s3 5 39/5 s3 = 5λ + (39/5) (1 – λ)
For each arbitrary value of λ, the value of objective function will remain same.
4.6.2 Unbounded Solution

In a maximization LP problem, if cj – zj > 0 (cj – zj < 0 for a minimization case) corresponds to a non-basic
variable column in simplex table, and all aij values in this column are negative, then minimum ratio to decide
basic variable to leave the basis can not be calculated. It is because negative value in denominator would
indicate the entry of a non-basic variable in the basis with a negative value (an infeasible solution). Also,
a zero value in the denominator would result in a ratio having an infinite value and would indicate that the
value of non-basic variable could be increased infinitely with any of the current basic variables being
removed from the basis.
Example 4.15 Solve the following LP problem.
(i) x1 – 2x2 ≤ 6, (ii) x1 ≤ 10, (iii) x2 ≥ 1
and x1, x2 ≥ 0
Solution Adding slack variables s1, s2, surplus variable s3 and artificial variable A1 in the constraint set. Unbounded
Then the standard form of LP problem becomes solution occurs
when value of
Maximize Z = 3x1 + 5x2 + 0s1 + 0s2 + 0s3 – MA1 decision variables in
the solution of LP
subject to the constraints problem becomes
(i) x1 – 2x2 + s1 = 6, (ii) x1 + s2 = 10, (iii) x2 – s3 + A1 = 1 infinitely large
without violating any
and x1, x2, s1, s2, s3, A1 ≥ 0 given constraints.
The initial solution to this LP problem is shown in Table 4.51.
cj → 3 5 0 0 0 – M
Basic Variables Basic Basic Variables x1 x2 s1 s2 s3 A1 Min Ratio

B b (= xB)
0 s1 6 1 – 2 1 0 0 0 –
0 s2 10 1 0 0 1 0 0 –
– M A1 1 0 1 0 0 – 1 1 1 →
Z = – M zj 0 – M 0 0 M – M
c j – zj 3 5 + M 0 0 – M 0 Table 4.51
Initial Solution
↑
Iteration 1: Since c2 – z2 ≥ 0, non-basic variable x2 is chosen to enter into the basis in place of basic variable
A1. The new solution is shown in Table 4.52.
cj → 3 5 0 0 0 –M
Basic Variables Basic Basic Variables x1 x2 s1 s2 s3 A1

B b (= xB)
0 s1 8 1 0 1 0 – 2 2
0 s2 10 1 0 0 1 0 0
5 x2 1 0 1 0 0 – 1 1
Z = 5 zj 0 5 0 0 – 5 5
Table 4.52 cj – zj 3 0 0 0 5 – M – 5
In Table 4.52, c5 – z5 = 5 is largest positive, so variable s3 should enter into the basis. But, coefficients
in the ‘s3’ column are all negative or zero. This indicates that s3 cannot be entered into the basis. However,
the value of s3 can be increased infinitely without removing any one of the basic variables. Further, since
s3 is associated with x2 in the third constraint, x2 will also be increased infinitely because it can be expressed
as x2 = 1 + s3 – A1. Hence, the solution to the given problem is unbounded.
4.6.3 Infeasible Solution

If LP problem solution does not satisfy all of the constraints, then such a solution is called infeasible
solution. Also, infeasible solution occurs when all cj – zj values satisfy optimal solution condition but at
least one of artificial variables appears in the basis with a positive value. This situation may occur when
an LP model is either improperly formulated or more than two of the constraints are incompatible.
Example 4.16 Solve the following LP problem
(i) x1 + x2 ≤ 5, (ii) x2 ≥ 8
and x1, x2 ≥ 0.
Solution Adding slack, surplus and artificial variables, the standard form of LP problem becomes
Maximize Z = 6x1+ 4x2 + 0s1 + 0s2 – MA1
(i) x1 + x2 + s1 = 5, (ii) x2 – s2 + A1 = 8
and x1, x2, s1, s2, A1 ≥ 0
The initial solution to this LP problem is shown in Table 4.53.
cj → 6 4 0 0 – M

B b (= xB)
6 s1 5 1 1 1 0 0 5/1 →
– M A1 8 0 1 0 –1 1 8/1
Z = 30 – 8M zj 6 6 – M 0 M – M
Table 4.53 cj – zj 0 – 2 + M 0 – M 0
Initial Solution
↑
Iteration 1: Since c2 – z2 = M – 2 (≥ 0), non-basic variable x2 is chosen to enter into the basis to replace basic
variable x1. The new solution is shown in Table 4.58.
cj → 6 4 0 0 – M
Basic Variables Basic Basic Variables x1 x2 s1 s2 A1

Coefficients Variables Values
B b (= xB )
4 x2 5 1 1 1 0 0
–M A1 3 –1 0 –1 –1 1 Table 4.54
Optimal but
Z = 20 – 3M zj 4 + M 4 4 + M M –M Infeasible
c j – zj 2 – M 0 – 4 – M –M 0 Solution
In table 5.44, since all cj – zj ≤ 0, the current solution is optimal. But this solution is not feasible for
the given LP problem because values of decision variables are: x1 = 0 and x2 = 5 violates second constraint,
x2 ≥ 8. The presence of artificial variable A1 = 3 in the solution also indicates that the optimal solution
violates the second constraint (x2 ≥ 8) by 3 units.
CONCEPTUAL QUESTIONS
1. Define slack and surplus variables in a linear programming 7. Explain what is meant by the terms degeneracy and cycling in
problem. linear programming? How can these problems be resolved?
2. Explain the various steps of the simplex method involved in the 8. Explain the term artificial variables and its use in linear programming.
computation of an optimum solution to a linear programming problem. 9. What are artificial variables? Why do we need them? Describe the
3. (a) Give outlines of the simplex method in linear programming. two-phase method of solving an LP problem with artificial variables.
(b) What is simplex? Describe the simplex method of solving 10. What is the significance of cj – zj numbers in the simplex table?
linear programming problem. Interpret their economic significance in terms of marginal worth.
(c) What do you understand by the term two-phase method of
11. What is meant by the term opportunity cost? How is this concept
solving linear programming problem?
used in designing a test for optimality?
(d) Outline the simplex method in linear programming. Why is
it called so? 12. How do the graphical and simplex methods of solving LP
(e) Explain the purpose and procedure of the simplex method. problems differ from each other? In what ways are they same?
4. What do you mean by an optimal basic feasible solution to a 13. How do maximization and minimization problems differ when
linear programming problem? applying the simplex method?
5. Given a general linear programming problem, explain how you 14. What is the reason behind the use of the minimum ratio test in
would test whether a basic feasible solution is an optimal solution selecting the key row? What might happen without it?
or not. How would you proceed to change the basic feasible 15. What conditions must exist in a simplex table to establish the
solution in case it is not optimal? existence of an alternative solution? No feasible solution? Un-
6. Explain the meaning of basic feasible solution and degenerate bounded solution? Degeneracy?
solution in a linear programming problem.
SELF PRACTICE PROBLEMS B

1. Solve the following LP problems using the simplex method.
(i) Max Z = 3x1 + 2x2 (ii) Max Z = 5x1 + 3x2 (iii) Max Z = 3x1 + 2x2 + 5x3
subject to x1 + x2 ≤ 4 subject to x1 + x2 ≤ 2 subject to x1 + 2x2 + x3 ≤ 430
x1 – x2 ≤ 2 5x1 + 2x2 ≤ 10 3x1 + 2x3 ≤ 460
and x1, x2 ≥ 0 3x1 + 8x2 ≤ 12 x1 + 4x3 ≤ 420
and x 1, x 2 ≥ 0 and x1, x2, x3 ≥ 0
[Shivaji, MSc (Maths), 1995]
(iv) Max Z = x1 – 3x2 + 2x3 (v) Max Z = 4x1 + 5x2 + 9x3 + 11x4 (vi) Max Z = x1 + x2 + x3
subject to 3x1 – x2 + 3x3 ≤ 7 subject to subject to 4x1 + 5x2 + 3x3 ≤ 15
–2x1 + 4x2 ≤ 12 x1 + x2 + x3 + x4 ≤ 15 10x1 + 7x2 + x3 ≤ 12
– 4x1 + 3x2 + 8x3 ≤ 10 7x1 + 5x2 + 3x3 + 2x4 ≤ 120 and x1, x2, x3 ≥ 0
and x1, x2, x3 ≥ 0 3x1 + 5x2 + 10x3 + 15x4 ≤ 100
[Meerut, MSc (Maths), 1997; and x1, x2, x3, x4 ≥ 0
Bhathiar MSc (Maths), 1996]
(vii) Max Z = x1 + x2 + x3 (viii) Max Z = 2x1 + 4x2 + 3x + x4 (i x ) Max Z = 107x1 + x2 + 2x3

subject to 3x1 + 2x2 + x3 ≤ 3 subject to x1 + 3x2 + x4 ≤ 4 subject to 14x1 + x2 – 6x3 + 3x4 ≤ 7
2x1 + x2 + 2x3 ≤ 2 2x1 + x2 ≤ 3 16x1 + 0.5x2 + 6x3 ≤ 5
and x1, x2, x3 ≥ 0 x2 + 4x3 + x4 ≤ 3 3x1 – x2 – x3 ≤ 10
and x1, x2, x3, x4 ≥ 0 and x1, x2, x3, x4 ≥ 0
[Sambalpur, MSc (Maths), 2003 ]
(x) Max Z = 4x1 + 10x2 (xi) Max Z = x1 – x2 + 3x3 (xii) Max Z = 4x1 + x2 + 3x3 + 5x4
subject to 2x1 + x2 ≤ 50 subject to x1 + x2 + x3 ≤ 10 subject to
2x1 + 5x2 ≤ 100 2x1 – x3 ≤ 2 4x1 – 6x2 – 5x3 + 4x4 ≥ – 20
2x1 + 3x2 ≤ 90 2x1 – 2x2 + 3x3 ≤ 0 3x1 – 2x2 + 4x3 + x4 ≤ 10
and x1, x2 ≥ 0 and x 1, x 2 ≥ 0 8x1 – 3x2 + 3x3 + 2x4 ≤ 20
[Karnataka, MSc (Maths), 2004 ] and x 1, x 2 , x 3, x 4 ≥ 0
has an unbound solution.
2. Use the two-phase method to solve the following LP problems:
(i) Max Z = 3x1 – x2 (ii) Min Z = 3x1 – x2 – x3 (iii) Min Z = 7.5x1 – 3x2
subject to 2x1 + x2 ≥ 2 subject to x1 – 2x2 + x3 ≤ 11 subject to 3x1 – x2 – x3 ≥ 3
x1 + 3x2 ≤ 2 – 4x1 + x2 + 2x3 ≥ 3 x1 – x 2 + x 3 ≥ 2
x2 ≤ 4 – 2x1 + x3 = 1 and x 1 , x 2, x 3 ≥ 0
and x1 , x 2 ≥ 0 and x 1, x 2, x 3 ≥ 0
(iv) Min Z = 3x1 – x2 (v) Min Z = 5x1 + 8x2 (vi) Min Z = 3x1 + 2x2
subject to 2x1 + x2 ≥ 2 subject to 3x1 + 2x2 ≥ 3 subject to 2x1 + x2 ≥ 2
x1 + 3x2 ≤ 2 x1 + 4x2 ≥ 4 3x1 + 4x2 ≥ 12
x2 ≤ 4 x1 + x 2 ≤ 5 and x1 , x 2 ≥ 0
and x 1, x 2 ≥ 0 and x1 , x 2 ≥ 0
3. Use penalty (Big-M) method to solve the following LP problems:
(i) Min Z = 3x1 – x2 (ii) Min Z = 2x1 + x2 (iii) Max Z = 3x1 + 2x2 + 3x3
subject to 2x1 + x2 ≥ 2 subject to 3x1 + x2 = 3 subject to 2x1 + x2 + x3 ≤ 2
x1 + 3x2 ≤ 3 4x1 + 3x2 ≥ 6 3x1 + 4x2 + 2x3 ≤ 8
x2 ≥ 4 x1 + 2x2 ≤ 4 and x 1 , x 2, x 3 ≥ 0
x 1, x 2 ≥ 0 x 1, x 2 ≥ 0
(i v) Max Z = x1 + x2 + x4 (v) Min Z = x1 – 3x2 + 2x3 (vi) Min Z = 5x1 + 2x2 + 10x3
subject to x1 + x2 + x3 + x4 = 4 subject to 3x1 – x2 + 2x3 ≤ 7 subject to x1 – x3 ≤ 10
x1 + 2x2 + x3 + x4 = 4 –2x1 + 4x2 + ≤ 12 x2 + x3 ≥ 10
x1 + 2x2 + x3 = 4 – 4x1 + 3x2 + 8x3 ≤ 10 and x 1 , x 2, x 3 ≥ 0
and x 1, x 2, x 3 ≥ 0
[Meerut MSc (Maths), 2005]
4. Solve the following LP problems and remove the complication (if any).
(i) Max Z = 2x1 + 3x2 + 10x3 (ii) Max Z = 5x1 – 2x2 + 3x3 (iii) Max Z = 5x1 + 3x2
subject to x1 + 2x3 = 2 subject to 2x1 + 2x2 – x3 ≥ 2 subect to x1 + x 2 ≤ 2
x2 + x 3 = 1 3x1 – 4x2 ≤ 3 5x1 + 2x2 ≤ 10
and x 1, x 2, x 3 ≥ 0 x2 + 3x3 ≤ 5 3x1 + 8x2 ≤ 12
and x 1, x 2, x 3 ≥ 0 and x 1, x 2 ≥ 0
(iv) Max Z = 22x1 + 30x2 + 25x3 (v) Max Z = 8x2
subject to 2x1 + 2x2 + ≤ 100 subject to x1 – x 2 ≥ 0
2x1 + x2 + x3 ≥ 100 2x1 + 3x2 ≤ – 6
x1 + 2x2 + 2x3 ≤ 100 and x1, x2 unrestricted.
and x 1 , x 2, x 3 ≥ 0
5. Solve the following LP problems to show that these have alternative optimal solutions.
(i) Max Z = 6x1 + 3x2 (ii) Min Z = 2x1 + 8x2 (iii) Max Z = x1 + 2x2 + 3x3 – x4
subject to 2x1 + x2 ≤ 8 subject to 5x1 + x2 ≥ 10 subject to x1 + 2x2 + 3x3 = 15
3x1 + 3x2 ≤ 18 2x1 + 2x2 ≥ 14 2x1 + x2 + 5x3 ≥ 20
x2 ≤ 3 x1 + 4x2 ≥ 12 x1 + x2 + x3 + x4 ≥ 10
and x1 , x 2 ≥ 0 and x 1, x 2 ≥ 0 and x 1, x 2 , x 3, x 4 ≥ 0
6. Solve the following LP problems to show that these have an unbounded solution.
(i) Max Z = – 2x1 + 3x2 (ii) Max Z = 3x1 + 6x2 (iii) Max Z = 107x1 + x2 + 2x3
subject to x1 ≤ 5 subject to 3x1 + 4x2 ≥ 12 subject to 14x1 + x2 – 6x3 + 3x4 = 7
2x1 – 3x2 ≤ 6 – 2x1 + x2 ≤ 4 16x1 + 0.5x2 – 6x3 ≤ 5
and x1 , x 2 ≥ 0 and x 1, x 2 ≥ 0 3x1 – x2 – x3 ≤ 0
and x1 , x 2 ≥ 0
(iv) Max Z = 6x1 – 2x2
subject to 2x1 – x2 ≤ 2
x1 ≤ 4
and x 1, x 2 , x 3, x 4 ≥ 0
7. Solve the following LP problems to show that these have no feasible solution.
(i) Max Z = 2x1 + 3x2 (ii) Max Z = 4x1 + x2 + 4x3 + 5x4 (iii) Max Z = x1 + 3x2
subject to x1 – x 2 ≥ 4 subject to 4x1 + 6x2 – 5x3 + 4x4 ≥ – 20 subject to x1 – x 2 ≥ 1
x1 + x 2 ≤ 6 3x1 – 2x2 + 4x3 + x4 ≤ 10 3x1 – x2 ≤ – 3
x1 ≤ 2 3x1 – 2x2 + 4x3 + x4 ≤ 10 and x1 , x 2 ≥ 0
and x 1, x 2 ≥ 0 8x1 – 3x2 – 3x3 + 2x4 ≤ 20
and x 1, x 2, x 3, x 4 ≥ 0
(iv) Max Z = 3x1 + 2x2
subject to 2x1 + x2 ≤ 2
3x1 + 4x2 ≥ 12
and x 1, x 2 ≥ 0
[Meerut, MSc (Maths), 2006]
HINTS AND ANSWERS
1. (i) x1 = 3, x2 = 1 and Max Z = 11 (ii) x1 = 3/5, x2 = 6/5 and Min Z = 12/5

(ii) x1 = 2, x2 = 0 and Max Z = 10 (iii) All cj – zj ≥ 0 artificial variable A1 = 0 appears in the
(iii) x1 = 0, x2 = 100, x3 = 230 and Max Z = 1,350 basis with zero value. Thus an optimal solution to the
(iv) Max Z * = – x1 + 3x2 – 2x3 where Z * = – Z given LP problem exists.
x1 = 4, x2 = 5, x3 = 0 and Z * = 11. (iv) Introduce artificial variable only in the third constraint.
(v) x1 = 50/7, x2 = 0, x3 = 55/7 and Max Z = 695/7 x1 = 0, x2 = 0, x3 = 0, x5 = 0 and Max Z = 4.
(vi) x1 = 0, x2 = 0, x3 = 5 and Max Z = 5 (v) x1 = 4, x2 = 5 and Min Z = – 11
(vii) x1 = 0, x2 = 0, x3 = 1 and Max Z = 3 (vi) x1 = 0, x2 = 10, x3 = 0 and Min Z = 20
(viii) x1 = 1, x2 = 1, x3 = 1/2 and Max Z = 13/2 4. (i) x1 = 0, x2 = 1, x3 = 0 and Max Z = 3
(ix) Divide the first equation by 3 (coefficient of x4 ) (ii) Degeneracy occurs at the initial stage. One of the variable
eligible to leave the basis is artificial variable, therefore,
(x) x1 = 0, x2 = 0 and Max Z = 200
there is no need of resolving degeneracy. Remove the
(xi) x1 = 0, x2 = 6, x3 = 4 and Max Z = 6 artificial variable from the basis.
2. (i) x1 = 1, x2 = 0, and Max Z = 6 x1 = 23/3, x2 = 5, x3 = 0 and Max Z = 85/3
(ii) All cj – zj ≤ 0 but Z = – 5/4 (< 0) and artificial variable (iii) x1 = 2, x2 = 0 and Max Z = 10
A1 = 5/4 appears in the basis with positive value. Thus (iv) x1 = 100/3, x2 = 50/3, x3 = 50/3 and Max Z = 1,650
the given LP problem has no feasible solution.
(v) x1′′ = 6/5 or x1 = – 6/5 or x 2′′ = 6/5 or x2 = – 6/5 and
(iii) x1 = 5/4, x2 = 0, x3 = 0 and Min Z = 75/8 Max Z = – 48/5.
(iv) x1 = 2, x2 = 0 and Max Z = 6 5. (i) (a) x1 = 4, x2 = 0 and Max Z = 24
(v) x1 = 0, x2 = 5 and Max Z = 40 (b) x1 = 5/2, x2 = 3, and Max Z = 24
(vi) All cj – zj ≥ 0, but Z = – 4 (< 0) and artificial variable (ii) (a) x1 = 32/6, x2 = 10/6 and Min Z = 24
A1 = 4 appears in the basis with a positive value. Thus (b) x1 = 12, x2 = 0 and Min Z = 24
the given LP problem has no feasible solution. 6. (i) At the current solution: x1 = 5, x2 = 9 and Max Z = 15,
3. (i) x1 = 3, x2 = 0 and Max Z = 9 it may be observed that c2 – z2 = 3/2 but all elements
in the second column are negative. Solution is unbounded.
(ii) At the current solution: x2 = 4, s1 = 4 and Max Z = 24, (iv) Optimal solution: x1 = 4, x2 = 6 and Max Z = 12. Since
it may be observed that c2 – z2 = 15 but all elements in in the initial simplex table all the elements are negative
the second column are negative. Solution is unbounded. in the second column, the feasible solution is unbounded
(iii) At second best solution, c3 – z3 = 113/3 but all elements but the optimal solution is bounded.
in the third column are negative. Solution is unbounded; 7. (i) x1 = 2, x2 = 0, A1 = 2 and M Max Z = 9 – 4M; Infeasible
x1 = 0, x4 = 7/3, s1 = 5 and Max Z = 0. solution.
(iv) x1 = 0, x2 = 2, A1 = 2 and Max Z = 4 – 4M; Infeasible
solution.
CHAPTER SUMMARY
The simplex method is an interactive procedure for reaching the optimal solution to any LP problem. It consists of a series of
rules that, in effect, algebraically examine corner (extreme) points of the solution space in a systematic way. Each step moves
towards the optimal solution by increasing profit or decreasing cost, while maintaining feasibility. The simplex method consists
of five steps: (i) identifying the pivot column, (ii) identifying the pivot row and key element, (iii) replacing the pivot row, (iv)
computing new values for each remaining row; and (v) computing the zj and cj – zj values and examining for optimality. Each
step of this iterative procedure is displayed and explained in a simplex table both for maximization and minimization LP problems.
CHAPTER CONCEPTS QUIZ
True or False
1. The major difference between slack and artificial variables is that 15. The value for the replacing row must be ————— before
an artificial can never be zero. computing the values for the ————— rows.
2. If an optimal solution is degenerate, then there are alternate 16. Entries in the cj – zj rows are known as ————— costs.
optimal solutions of the LP problem. 17. Optimality is indicated for a maximization problem when all
3. An infeasible solution is characterized as one where one elements in the cj – zj rows are —————, while for a
constraint is violated. minimization problem all elements must be —————.
4. If the objective function coefficient in the cj row above an artificial 18. In Big-M method, ————— basic feasible solution is obtained
variable is – M, then the problem is a minimization problem. by assigning ————— value to the original value.
19. In the two-phase method, an ————— variable is never
5. In the simplex method, the initial solution contains only slack
considered for re-entry into the basis.
variable in the product mix.
20. ————— occurs when there is no finite solution in the LP
6. If there is a tie between decision variable and a slack (or
problem.
surplus) variable, then select the decision variable to enter into
the first basis.
Multiple Choice
7. An optimal solution to the maximized LP problem is reached if
all cj – zj ≥ 0. 21. The role of artificial variables in the simplex method is
8. Variables which can assume negative, positive or zero value are (a) to aid in finding an initial solution
called unrestricted variables. (b) to find optimal dual prices in the final simplex table
9. All the rules and procedures of the simplex method are identical (c) to start phases of simplex method
whether solving a maximization or minimization LP problem. (d) all of the above
10. Artificial variables are added to a linear programming problem to 22. For a maximization problem, the objective function coefficient for
aid in the finding an optimal solution. an artificial variable is
(a) + M (b) – M
(c) Zero (d) none of the above
Fill in the Blanks 23. If a negative value appears in the solution values (xB )
column of the simplex table, then
11. In the simplex method, the ————— column contains the (a) the solution is optimal
variables which are currently in the solution; the values of these (b) the solution is infeasible
variables can be read from the ————— column. (c) the solution is unbounded
12. A ————— variable represents amounts by which solution (d) all of the above
values exceed a resource. 24. At every iteration of the simplex method, for minimization
13. The simplex method examines the ————— points in a problem, a variable in the current basis is replaced with another
systematic manner, repeating the same set of steps of the variable that has
algorithm until an ————— solution is reached. (a) a positive cj – zj value
14. ————— occurs when there is no solution that satisfies all of (b) a negative cj – zj value
the constraints in the linear programming problem. (c) cj – zj = 0
(d) none of the above
25. In the optimal simplex table, cj – zj = 0 value indicates (d) none of the above
(a) unbounded solution (b) cycling 31. If any value in xB – Column of final simplex table is negative, then
(c) alternative solution (d) infeasible solution the solution is
26. For maximization LP model, the simplex method is terminated (a) unbounded (b) infeasible
when all values (c) optimal (d) none of the above
(a) cj – zj ≤ 0 (b) cj – zj ≥ 0 32. If all aij values in the incoming variable column of the simplex
(c) cj – zj = 0 (d) zj ≤ 0 table are negative, then
27. A variable which does not appear in the basic variable (B) (a) solution is unbounded (b) there are multiple solutions
column of simplex table is (c) there exist no solution (c) the solution is degenerate
(a) never equal to zero (b) always equal to zero 33. If an artificial variable is present in the ‘basic variable’ column
(c) called a basic variable (d) none of the above of optimal simplex table, then the solution is
28. If for a given solution a slack variable is equal to zero then (a) infeasible (b) unbounded
(c) degenerate (d) none of the above
(a) the solution is optimal (b) the solution is infeasible
(c) the entire amount of resource with the constraint in which 34. The per unit improvement in the solution of the minimization
the slack variable appears has been consumed. LP problem is indicated by the negative value of
(d) all of the above (a) cj – zj in the decision-variable column
29. If an optimal solution is degenerate, then (b) cj – zj in the slack variable column
(a) there are alternative optimal solutions (c) cj – zj in the surplus variable column
(b) the solution is infeasible
(d) none of the above
(c) the solution is of no use to the decision-maker
(d) none of the above 35. To convert ≥ inequality constraints into equality constraints, we
must
30. To formulate a problem for solution by the simplex method, we (a) add a surplus variable
must add artificial variable to
(b) subtract an artificial variable
(a) only equality constraints (c) substract a surplus variable and an artificial variable
(b) only ‘greater than’ constraints (d) add a surplus variable and substract an artificial variable
(c) both (a) and (b)
Answers to Quiz
1. F 2. F 3. T 4. F 5. F 6. T 7. T 8. T 9. F 10. T
11. product mix; quantity 12. Suplus 13. Extreme; optimal 14. Infeasibility 15. Computed; remaining
16. reduced 17. non positive, non negative 18. Initial; zero 19. Artificial 20. Unboundedness
21. (d) 22. (b) 23. (b) 24. (b) 25. (c) 26. (a) 27. (b) 28. (c) 29. (d) 30. (c)
31. (b) 32. (a) 33. (a) 34. (d) 35. (c)
CASE STUDY
Case 4.1: New Bharat Bank
New Bharat Bank is planning its operations for the next year. The bank makes five types of loans. These are listed
below, together with the annual return (in per cent);
Type of Loan Annual Return (per cent)
Education 15
Furniture 12
Automobile 9
Home Construction 10
Home repair 7
Legal requirements and bank policy place the following limits on the amounts of the various types of loans:
Education loans cannot exceed 10 per cent of the total amount of loans. The amount of education and furniture loans
together cannot exceed 20 per cent of the total amount of loans. Home construction loan must be at least 40 per cent
of the total amount of home loans and at least 20 per cent of the total amount of loans. Home construction loan must
not exceed 25 per cent of the total amount of loans.
The bank wishes to maximize its revenue from loan interest, subject to the above restrictions. The bank can lend
a maximum of Rs 75 crore. You are expected to suggest to the management of the bank for maximizing revenue keeping
in view operational restrictions.
Case 4.2: Accurate Transformers

Accurate Transformers produces electric transformers. The company has orders for transformer for the next six months.
The cost of manufacturing a transformer is expected to somewhat vary over the next few months due to expected
changes in materials costs and in labor rates. The company can produce up to 50 units per month in regular time
and up to an additional 20 units per month during overtime. The costs for both regular and overtime production are
shown in the table below:
Month
Jan. Feb. Mar. April May June
Orders (units) 58 36 34 69 72 43
Cost per unit at 180 170 170 185 190 190
regular time (in '000 Rs)
Cost per unit at 200 190 190 210 220 220
overtime (in '000 Rs)
The cost of carrying an unsold transformer in stock is Rs 25,000 per month. As on January 1 the company has
15 transformers in stock on and it wishes to have no less than 5 in stock on June 30. Suggest to the management
of the company to determine the optimal production schedule.
Case 4.3: Nationwide Air lines*

Nationwide Airlines, faced with a sharply escalating cost of jet fuel, is interested in optimizing its purchase of jet
fuel at its various locations around the country. Typically, there is some choice concerning the amount of fuel that
can be placed on board any aircraft for any flight segment, as long as minimum and maximum limits are not violated.
The flight schedule is considered as a chain of flight segments, or legs, that each aircraft follows. The schedule ultimately
returns the aircraft to its starting point, resulting in a ‘rotation’. Consider the following rotation:
Delhi – Hyderabad – Cochin – Chennai – Delhi
Fuel Requirements and Limits (1,000 gallons unless specified otherwise)
City Flight Sequence Minimum Fuel Maximum Fuel Regular Fuel Additional Fuel
Required Allowed Consumption if Burned per
Minimum Fuel Gallon of
Boarded Tankered Fuel
(i.e. fuel above
minimum Price per
– in gallons) Gallons (Rs)
1. Delhi to Hyderabad 23 33 12.1 0.040 8,200

2. Hyderabad to Cochin 8 19 2.0 0.005 7,500
3. Cochin to Chennai 19 33 9.5 0.025 7,700
4. Chennai to Delhi 25 33 13.0 0.045 8,900
The fuel for any one of these flight segments may be bought at its departure city, or it may be purchased at a previous
city in the sequence and ‘tankered’ for the flight. Of course, it takes fuel to carry fuel, and thus an economic trade-off
between purchasing fuel at the lowest-cost location and tankering it all around the country must be made.
In the table above the column ‘Regular Fuel Consumption’ takes into account fuel consumption if the minimum
amount of fuel is on board, and the column ‘Additional Fuel Burned’ indicates the additional fuel burned in each flight
segment per gallon of ‘tankered’ fuel carried; tankered fuel refers to fuel above the minimum amount.
The fuel originally carried into Delhi should equal fuel carried into Delhi on the next rotation, in order for the
system to be in equilibrium.
If l1= Leftover fuel inventory coming into city i (1,000 gallons) and xi = Amount of fuel purchased at city i (1,000
gallons) then, (li + xi) is the amount of fuel on board the aircraft when it departs city i.
Suggest the optimal fuel quantity to be purchased by the Airlines.
*
This case is based on ‘D. Wayne Darnell and Carln Loflin, National Airlines Fuel Management and Allocation
Model, Interfaces’ Feburary, 1977.

Unit - 1c OR

Uploaded by

Copyright:

Available Formats

Unit - 1c OR

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit - 1c OR

Uploaded by

Copyright:

Available Formats

C h a p t e r 4

After studying this chapter, you should be able to

4.2 STANDARD FORM OF AN LP PROBLEM

subject to the linear constraints

In matrix notations the standard form is expressed as:

Types of Constraint Extra Variable Coefficient of Additional Presence of Additional

4.3 SIMPLEX ALGORITHM (MAXIMIZATION CASE)

Step 6: Finding the new solution

FG IJ LMF Number above or belowI F Corresponding number in I OP

R2 (new) → R2 (old) – 2R1 (new) R3 (new) → R3 (old) – 2R1 (new)

Basics Variables Basic Basic Variables x1 x2 x3 s1 s2 s3 Min Ratio

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

Z = 40/3 zj 10/3 5 0 5/3 0 0

R3 (new) → R3 (old) – 4R2 (new)

29/3 – 4 × 14/15 = 89/15

Basic Variables Basic Basic Variables x1 x2 x3 s1 s2 s3 Min Ratio

5 x2 8/3 2/3 1 0 1/3 0 0 (8/3)/(2/3) = 4

Z = 256/15 zj 34/15 5 4 17/15 4/5 0

R1 (new) → R1 (old) – (2/3) R3 (new) R2 (new) → R2 (old)+ (4/15) R3 (new)

8/3 – 2/3 × 89/3 = 50/41 14/15 + 4/15 × 89/41 = 62/41

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

Table 4.6 Z = 765/41 zj 3 5 4 45/41 24/41 11/41

Maximize Z = 4x1 + 3x2 + 0s1 + 0s2 + 0s3 + 0s4

Ingredient Cost per kg (Rs)

Product Product Ingredients

Cost of P1 = 5% × 80 + 10% × 20 + 5% × 50 + 80% × 20 = 4 + 2 + 2.50 + 16 = Rs 24.50 per kg

The new solution is shown in Table 4.12.

Basic Variables Basic Basic Variables x1 x2 x3 s1 s2 s3 s4

4.4 SIMPLEX ALGORITHM (MINIMIZATION CASE)

4.4.1 Two-Phase Method

Advantages of the method

Steps of the Algorithm: Phase I

subject to the constraints

* This column can permanently be removed at this stage.

* Remove columns A1 and A2 from Table 4.16.

Basic Variables Basic Basic Variables x1 x2 s1 s2

–1 x1 21/13 1 0 – 7/13 1/13

Table 4.18 Z * = – 31/13 zj –1 –1 6/13 1/13

Example 4.6 Use two-phase simplex method to solve following LP problem.

Table 4.21 Z = 29/7 zj 3 4 –6 0 0 –1 1

4.4.2 Big-M Method

0 s1 8 0 16/5 1 2/5 0 8/(16/5) = 5/2 →

Basic Variables Basic Basic Variables Min Ratio

Z = – 3M + 6 zj M/5 + 3/5 – 7M/5 – 6/5 3 – 1 – M

R1 (new) → R1 (old) × (5/7) (key element); R2 (new) → R2 (old) – (1/5) R1 (new).

R3 (new) → R3 (old) × (7/6) (key element) ; R1 (new) → R1 (old) + (1/7) R3 (new).

The improved basic feasible solution is shown in Table 4.33.

Minimize Z = 600x1 + 500x2 + 0s1 + 0s2 + MA1 + MA2

Basic Variables Basic Basic Variables x1 x2 s1 s2 s3 Min Ratio

Basic Variables Basic Basic Variables x1 x2 x3 s1 s2

SELF PRACTICE PROBLEMS A

Product Product Product

HINTS AND ANSWERS

4.5 SOME COMPLICATIONS AND THEIR RESOLUTION

4.5.1 Unrestricted Variables

subject to the constraints

and xj , xr′ , xr′′ ≥ 0; j = 1, 2, . . ., n, j ≠ r.

Basic Variables Basic Basic Variables x1′ x1′′ x2 x3 A1 Min Ratio

Basic Variables Basic Basic Variables x1′ x1′′ x2 x3 A1 Min Ratio