OR : Module-2

Dual Simplex Algorithm

In regular simplex algorithm, we start with an Initial Basic Feasible Solution but non-optimal,
then proceed iteratively to reach at the Optimum value.

Prepared by Ranbir Kalita

But in Dual Simplex algorithm, we start with an Initial Basic Infeasible Solution (Dual
Feasible Solution), which is better than optimum solution but infeasible, and then proceed
iteratively to arrive at a Feasible Optimal Solution. This method is applicable to both
maximization and minimization type of problems.

The Solution Steps of Dual Simplex Algorithm are enumerated below:

• Convert the given problem into a Maximization problem of Canonical Form if it is

initially of minimization type.
• Express the inequality constraints into equations by introducing Slack variables.
• Equate all the real decision variables to zero and find the Initial Basic Solution. If the

Prepared by Ranbir Kalita

Initial Basic Solution is Infeasible, then the Dual Simplex Algorithm can be used.
Construct the Initial Dual Simplex Table, in the same manner as the Initial Simplex
Table is formed in the regular Simplex Algorithm.
• Compute the NER (Cj – Zj) values. Observe the NER and bi values.

▪ If all the NER values are ≤ 0 and all bi values are ≥ 0, the current solution is
the Feasible Optimal Solution.
▪ If all the NER values are ≤ 0 and at least one bi value is < 0 (negative), the
current solution is not Basic Feasible and therefore proceed to next iteration.
▪ If any NER value is > 0, the method fails.
• For next iteration, select the Key Row corresponding to the most negative bi value.
This is called Dual Feasibility Condition. The basic variable in the Key Row is the
Prepared by Ranbir Kalita

Leaving Variable.
• Observe the Key Row values:
▪ If all elements are ≥ 0 , the problem does not have a feasible solution.
▪ If at least one element is < 0 (negative), then proceed to identify the Key
Column. For that, find the θ-values corresponding each Negative Key Row
element. No θ-value is to be calculated against any Positive or Zero Key Row
element.

Page - 113
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-2

θ = NER value / corresponding –ve Key Row value

▪ Choose the smallest θ-value (positive) to identify the Key Column and the
corresponding column variable is the Entering Variable. This is called the
Dual Optimality Condition.
• The value at the intersection of Key Row and Key Column is the Key Element.
• Similar to regular Simplex algorithm, perform row operations to make the Key
Element equal to One and Intersectional Elements equal to Zero.

As can be seen, the Dual Simplex Algorithm differs from that of the regular Simplex
algorithm in the manner that the Key Row is identified first and then the Key Column, i.e.,
the Leaving Basic Variable is identified first and then the Entering Non-basic Variable.

The main advantage of Dual Simplex algorithm over the regular Simplex algorithm is
that, it eliminates the need for introducing Artificial Variables into the LPP.

The application areas of Dual Simplex algorithm especially include, Sensitivity

Analysis, Parametric Programming, Integer Programming algorithms (e.g. cutting-plane
algorithm), some Non-linear Programming algorithms etc.

Problem 2.20:

Solve the following LPP using Dual Simplex Method:

Minimize Z = 2x1 + 2x2 + 4x3

Subject to,
2x1 + 3x2 + 5x3 ≥ 2
3x1 + x2 + 7x3 ≤ 3
x1 + 4x2 + 6x3 ≤ 5
Where, x1 , x2 , x3 ≥ 0
Solution: First, convert the given problem in Maximization Canonical form.

Maximize W = –2x1 – 2x2 – 4x3

Subject to,
–2x1 – 3x2 – 5x3 ≤ –2
3x1 + x2 + 7x3 ≤ 3
x1 + 4x2 + 6x3 ≤ 5
Where, x1 , x2 , x3 ≥ 0

Page - 114
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-2

Second, express the inequality constraints into equations by introducing Slack variables.

Maximize W = –2x1 – 2x2 – 4x3 + 0.s1 + 0.s2 + 0.s3

Subject to,

Prepared by Ranbir Kalita

–2x1 – 3x2 – 5x3 + s1 = –2
3x1 + x2 + 7x3 + s2 = 3
x1 + 4x2 + 6x3 + s3 = 5
Where,
x1 , x2 , x3 , s1 , s2 , s3 ≥ 0

Putting x1 = x2 = x3 = 0, we get, s1 = –2 , s2 = 3 , s3 = 5

Since the Initial Basic Solution is Infeasible, therefore, we can use the Dual Simplex
Algorithm.

Initial Dual Simplex Table:

Prepared by Ranbir Kalita

Cj –2 –2 –4 0 0 0
FR CB Basic x1 x2 x3 s1 s2 s3 b
--- 0 s1 –2 (–3) –5 1 0 0 –2
–1/3 0 s2 3 1 7 0 1 0 3
–4/3 0 s3 1 4 6 0 0 1 5

Zj 0 0 0 0 0 0 0

NER: Cj – Zj –2 –2 –4 0 0 0
(–2)/( –2) (–2)/( –3) (–4)/( –5)
θ --- --- ---
=1 = 2/3 = 4/5

• Since all the NER values are ≤ 0 and b1 value is negative, therefore, the current
solution is not Basic Feasible and we should move to the next iteration.
Prepared by Ranbir Kalita

• s1 row is the Key Row corresponding to b1 (only negative value) and s1 is the Leaving
Variable.
• Since the Key Row contains < 0 values (negative), therefore, proceed to identify the
Key Column.
θ = NER value / corresponding –ve Key Row value
• Positive and Zero Key Row values are not to be considered to calculate θ-values.

Page - 115
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-2

• Minimum θ-value is 2/3 corresponding to x2 column. As such, it is the Key Column

and x2 is the Entering Variable in the next iteration.
• For the next iteration, the Key Element is to be made equal to One and the
Intersectional Elements are to be made equal to Zero. For that, following row

Prepared by Ranbir Kalita

operations have been performed (as done is regular LPP).

New elements of x2 row for First Iteration Table:

Divide every element of s1 row of the Initial Dual Simplex Table by (–3).
2/3 1 5/3 –1/3 0 0 2/3

New elements of s2 row for First Iteration Table:

3 – [(–1/3) × (–2)] = 7/3 ; 1 – [(–1/3) × (–3)] = 0
7 – [(–1/3) × (–5)] = 16/3 ; 0 – [(–1/3) × 1] = 1/3
1 – [(–1/3) × 0] = 1 ; 0 – [(–1/3) × 0] = 0
3 – [(–1/3) × (–2)] = 7/3

Prepared by Ranbir Kalita

New elements of s3 row for First Iteration Table:
1 – [(–4/3) × (–2)] = –5/3 ; 4 – [(–4/3) × (–3)] = 0
6 – [(–4/3) × (–5)] = –2/3 ; 0 – [(–4/3) × 1] = 4/3
0 – [(–4/3) × 0] = 0 ; 1 – [(–4/3) × 0] = 1
5 – [(–4/3) × (–2)] = 7/3

First Iteration Table:

Cj –2 –2 –4 0 0 0
FR CB Basic x1 x2 x3 s1 s2 s3 b
–2 x2 2/3 1 5/3 –1/3 0 0 2/3
0 s2 7/3 0 16/3 1/3 1 0 7/3
Prepared by Ranbir Kalita

0 s3 –5/3 0 –2/3 4/3 0 1 7/3

Zj –4/3 –2 –10/3 2/3 0 0 –4/3

NER: Cj – Zj –2/3 0 –2/3 –2/3 0 0

Since all the NER values are ≤ 0 and all bi value are ≥ 0, therefore, the current solution is the
Feasible Optimal Solution.

x1 = 0 , x2 = 2/3 , x3 = 0 and Wmax = –4/3 therefore, Zmin = 4/3

Page - 116
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-2

References

[1] Hamdy A. Taha (2007), Operations Research: An Introduction (8th edition), Pearson,
ISBN 0-13-188923·0, Chapter 4, pp. 174-179.

Prepared by Ranbir Kalita

[2] Prem Kumar Gupta and D. S. Hira (2014), Operations Research (7th revised edition),
S. Chand, ISBN: 81-219-0281-9, Chapter 6, pp. 530-540.

Prepared by Ranbir Kalita

Prepared by Ranbir Kalita

Page - 117
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-2

Problem 2.21:

Solve the following LPP using Dual Simplex Method:

Minimize Z = 3x1 + 2x2

Prepared by Ranbir Kalita

Subject to,
x1 + x2 ≥ 1
x1 + x2 ≤ 7
x1 + 2x2 ≥ 10
x2 ≤ 3
Where,
x1 , x2 ≥ 0

Solution: First, convert the given problem in Maximization Canonical form.

Maximize W = –3x1 – 2x2

Subject to,
–x1 – x2 ≤ –1
x1 + x2 ≤ 7

Prepared by Ranbir Kalita

–x1 – 2x2 ≤ –10
x2 ≤ 3
Where,
x1 , x2 ≥ 0

Second, express the inequality constraints into equations by introducing Slack variables.

Maximize Z = –3x1 – 2x2 + 0.s1 + 0.s2 + 0.s3 + 0.s4

Subject to,
–x1 – x2 + s1 = –1
x1 + x2 + s2 = 7
–x1 – 2x2 + s3 = –10
0.x1 + x2 + s4 = 3
Where,
x1 , x2 , s1 , s2 , s3 , s4 ≥ 0
Prepared by Ranbir Kalita

Putting x1 = x2 = 0, we get, s1 = –1 , s2 = 7 , s3 = –10 , s4 = 3. This Initial Basic

Solution is Infeasible; therefore, Dual Simplex Algorithm can be used.

Page - 118
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-2

Initial Dual Simplex Table:

Cj –3 –2 0 0 0 0
FR CB Basic x1 x2 s1 s2 s3 s4 b

Prepared by Ranbir Kalita

1/2 0 s1 –1 –1 1 0 0 0 –1
–1/2 0 s2 1 1 0 1 0 0 7
--- 0 s3 –1 (–2) 0 0 1 0 –10
–1/2 0 s4 0 1 0 0 0 1 3

Zj 0 0 0 0 0 0 0

NER: Cj – Zj –3 –2 0 0 0 0
(–3)/( –1) (–2)/( –2)
θ --- --- --- ---
=3 =1

• Since all the NER values are ≤ 0 and b1 & b3 values are negative, therefore, the
current solution is not Basic Feasible and we should move to the next iteration.

Prepared by Ranbir Kalita

• s3 row is the Key Row corresponding to maximum negative bi value. As such s3 is the
Leaving Basic Variable for the next iteration.
• Since the Key Row has < 0 value (negative), therefore, proceed to identify the Key
Column.
θ = NER value / corresponding –ve Key Row value
• Positive and Zero Key Row values are not to be considered to calculate θ-values.
• Minimum θ-value is 1 corresponding to x2 column. As such, it is the Key Column and
x2 is the Entering Variable in the next iteration.
• For the next iteration, the Key Element is to be made equal to One and the
Intersectional Elements are to be made equal to Zero. For that, following row
operations have been performed (as done is regular LPP).
Prepared by Ranbir Kalita

New elements of s1 row for First Iteration Table:

–1 – [1/2 × (–1)] = –1/2 ; –1 – [1/2 × (–2)] = 0 ; 1 – [1/2 × 0] = 1
0 – [1/2 × 0] = 0 ; 0 – [1/2 × 1] = –1/2 ; 0 – [1/2 × 0] = 0
–1 – [1/2 × (–10)] = 4

New elements of s2 row for First Iteration Table:

1 – [(–1/2) × (–1)] = 1/2 ; 1 – [(–1/2) × (–2)] = 0
0 – [(–1/2) × 0] = 0 ; 1 – [(–1/2) × 0] = 1

Page - 119
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-2

0 – [(–1/2) × 1] = 1/2 ; 0 – [(–1/2) × 0] = 0

7 – [(–1/2) × (–10)] = 2

New elements of x2 row for First Iteration Table:

Prepared by Ranbir Kalita

Divide every element of s3 row of Initial Dual Simplex Table by (–2).
1/2 1 0 0 –1/2 0 5

New elements of s4 row for First Iteration Table:

0 – [(–1/2) × (–1)] = –1/2 ; 1 – [(–1/2) × (–2)] = 0
0 – [(–1/2) × 0] = 0 ; 0 – [(–1/2) × 0] = 0
0 – [(–1/2) × 1] = 1/2 ; 1 – [(–1/2) × 0] = 1
3 – [(–1/2) × (–10)] = –2

First Iteration Table:

Cj –3 –2 0 0 0 0

Prepared by Ranbir Kalita

FR CB Basic x1 x2 s1 s2 s3 s4 b
1 0 s1 –1/2 0 1 0 –1/2 0 4
–1 0 s2 1/2 0 0 1 1/2 0 2
–1 –2 x2 1/2 1 0 0 –1/2 0 5
--- 0 s4 (–1/2) 0 0 0 1/2 1 –2

Zj –1 –2 0 0 1 0 –10

NER: Cj – Zj –2 0 0 0 –1 0
(–2)/( –1/2)
θ --- --- --- --- ---
=4

• Since all the NER values are ≤ 0 and b4 value is negative, therefore, the current
solution is not Basic Feasible and we should move to the next iteration.
• s4 row is the Key Row corresponding to the only negative bi value. As such s4 is the
Prepared by Ranbir Kalita

Leaving Basic Variable for the next iteration.

• Since the Key Row has < 0 value (negative), therefore, proceed to identify the Key
Column.
θ = NER value / corresponding –ve Key Row value
• Positive and Zero Key Row values are not to be considered to calculate θ-values.
• Minimum θ-value is 4 (only value) corresponding to x1 column. As such, it is the Key
Column and x1 is the Entering Variable in the next iteration.

Page - 120
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-2

• For the next iteration, the Key Element is to be made equal to One and the
Intersectional Elements are to be made equal to Zero. For that, following row
operations have been performed (as done is regular LPP).

Prepared by Ranbir Kalita

New elements of s1 row for Second Iteration Table:
–1/2 – [1 × (–1/2)] = 0 ; 0 – [1 × 0] = 0 ; 1 – [1 × 0] = 1
0 – [1 × 0] = 0 ; –1/2 – [1 × 1/2] = –1 ; 0 – [1 × 1] = –1
4 – [1 × (–2)] = 6

New elements of s2 row for Second Iteration Table:

1/2 – [(–1) × (–1/2)] = 0 ; 0 – [(–1) × 0] = 0 ; 0 – [(–1) × 0] = 0
1 – [(–1) × 0] = 1 ; 1/2 – [(–1) × 1/2] = 1 ; 0 – [(–1) × 1] = 1
2 – [(–1) × (–2)] = 0

New elements of x2 row for Second Iteration Table:

1/2 – [(–1) × (–1/2)] = 0 ; 1 – [(–1) × 0] = 1 ; 0 – [(–1) × 0] = 0

Prepared by Ranbir Kalita

0 – [(–1) × 0] = 0 ; –1/2 – [(–1) × 1/2] = 0
0 – [(–1) × 0] = 0 ; 5 – [(–1) × (–2)] = 3

New elements of x1 row for Second Iteration Table:

Multiply every element of s4 row of First Iteration Table by (–2).
1 0 0 0 –1 –2 4

Second Iteration Table:

Cj –3 –2 0 0 0 0
FR CB Basic x1 x2 s1 s2 s3 s4 b
0 s1 0 0 1 0 –1 –1 6
0 s2 0 0 0 1 1 1 0
Prepared by Ranbir Kalita

–2 x2 0 1 0 0 0 0 3
–3 x1 1 0 0 0 –1 –2 4

Zj –3 –2 0 0 3 6 –18

NER: Cj – Zj 0 0 0 0 –3 –6

Since all the NER values are ≤ 0 and all bi values are > 0 (positive), therefore, the current
solution is the Feasible Optimal Solution.
x1 = 4 , x2 = 3 , Wmax = –18 therefore, Zmin = 18

Page - 121
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-2

Problem 2.22:

Solve the following LPP using Dual Simplex Method:

Minimize Z = x1 + x2

Prepared by Ranbir Kalita

Subject to,
2x1 + x2 ≥ 2
–x1 – x2 ≥ 1
Where,
x1 , x2 ≥ 0

Solution: Since the given problem is of Minimization type, therefore, express it into a
Maximization problem of Canonical Form.

Maximize W = –x1 – x2
Subject to,
–2x1 – x2 ≤ –2
x1 + x2 ≤ –1

Prepared by Ranbir Kalita

Where,
x1 , x2 ≥ 0

Next, express the inequality constraints into equations by introducing Slack variables.

Maximize W = –x1 – x2 + 0.s1 + 0.s2

Subject to,
–2x1 – x2 + s1 = –2
x1 + x2 + s2 = –1
Where,
x1 , x2 , s1 , s2 ≥ 0

Putting x1 = x2 = 0, we ger, s1 = –2 , s2 = –1. This Initial Basic Solution is Infeasible.

Therefore, Dual Simplex Algorithm can be used.
Prepared by Ranbir Kalita

Page - 122
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-2

Initial Dual Simplex Table:

Cj –1 –1 0 0
FR CB Basic x1 x2 s1 s2 b

Prepared by Ranbir Kalita

--- 0 s1 (–2) –1 1 0 –2
–1/2 0 s2 1 1 0 1 –1

Zj 0 0 0 0 0

NER: Cj – Zj –1 –1 0 0
(–1)/( –2) (–1)/( –1)
θ --- ---
= 1/2 =1

• Since all the NER values are ≤ 0 and b1 & b2 values are negative, therefore, the
current solution is not Basic Feasible and we should move to the next iteration.
• s1 row is the Key Row corresponding to maximum negative bi value. As such s1 is the
Leaving Basic Variable for the next iteration.

Prepared by Ranbir Kalita

• Since the Key Row has < 0 value (negative), therefore, proceed to identify the Key
Column.
θ = NER value / corresponding –ve Key Row value
• Positive and Zero Key Row values are not to be considered to calculate θ-values.
• Minimum θ-value is 1/2 corresponding to x1 column. As such, it is the Key Column
and x1 is the Entering Variable in the next iteration.
• For the next iteration, the Key Element is to be made equal to One and the
Intersectional Elements are to be made equal to Zero. For that, following row
operations have been performed (as done is regular LPP).

New elements of x1 row for First Iteration Table:

Divide s1 row of Initial Dual Simplex Table by (–2).
Prepared by Ranbir Kalita

1 1/2 –1/2 0 1

New elements of s2 row for First Iteration Table:

1 – [(–1/2) × (–2)] = 0 ; 1 – [(–1/2) × (–1)] = 1/2
0 – [(–1/2) × 1] = 1/2 ; 1 – [(–1/2) × 0] = 1
–1 – [(–1/2) × (–2)] = –2

Page - 123
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-2

First Iteration Table:

Cj –1 –1 0 0
FR CB Basic x1 x2 s1 s2 b

Prepared by Ranbir Kalita

–1 x1 1 1/2 –1/2 0 1
0 s2 0 1/2 1/2 1 –2

Zj –1 –1/2 1/2 0 –1

NER: Cj – Zj 0 1/2 –1/2 0

Since the Key Row does not have any Negative value (< 0 value), therefore, the problem does
not have a Feasible Solution.

Prepared by Ranbir Kalita

Prepared by Ranbir Kalita

References

[1] Hamdy A. Taha (2007), Operations Research: An Introduction (8th edition), Pearson,
ISBN 0-13-188923·0, Chapter 4, pp. 174-179.

[2] Prem Kumar Gupta and D. S. Hira (2014), Operations Research (7th revised edition),
S. Chand, ISBN: 81-219-0281-9, Chapter 6, pp. 530-540.

Page - 124
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Integer Linear Programming

In Linear Programming Problems (LPPs) discussed so far, the Basic Variables, including the

Prepared by Ranbir Kalita

Slack and Surplus variables are allowed to take any non-negative real values (continuous /
fractional) and the obtained results are practically applicable in many situations, such as,
producing 3 tons of Exterior paint and 1.5 tons of Interior paint as discussed in Problem 2.1
of Module-2; or taking 470.6 lb of Corn and 329.4 lb of Soybean meal to prepare the special
feed mixture as discussed in Problem 2.2 of Module-2. But, in the solution of many real-life
problems, such fractional values are not at all applicable. For example, it is impractical to
manufacture 250.56 numbers (quantity) of a particular product, or selling 5.8 machines per
day etc. In such situations, the optimal values of the variables should be Integers (discrete).

A general approach to obtain an integer value from a fractional value is to round off or
truncate it to the nearest integer value. For larger values, truncating to the nearest integer may

Prepared by Ranbir Kalita

not create any problem (e.g. 46875.76 to 46876). But for smaller values, truncating the
fractional value may produce a solution which is totally different from the True Optimal
Integer Solution. Also, some constraints may be violated if the fractional value of any of the
variables is truncated. For example, consider the following IPP:

Maximize Z = 3x1 + 10x2

Subject to,
x1 + 5x2 ≤ 12
x1 ≤ 3
Where,
x1 , x2 are non-negative integers

The optimal non-integer solution to the above problem is:

x1 = 3 , x2 = 1.8 and Zmax = 27

Prepared by Ranbir Kalita

And the optimal integer solution to the given problem is:

x1 = 2 , x2 = 2 and Zmax = 26

In the optimal non-integer solution, x2 is violating the Integer Restrictions. Therefore,

if we truncate the value of x2 from 1.8 to the nearest integer value of 2, then, it violates the
first constraint [3 + (5×2) = 13 ≮ 12]. Also, if we round off the value of x2 value from 1.8 to

Page - 1
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

1, then it satisfies both the constraints. But Zmax = 19 is far less than the true optimal integer
solution Zmax = 26.

Also, as the number of variables with fractional value increases, the process of hit-and-

Prepared by Ranbir Kalita

trial truncation also increases exponentially.

To tackle such computational difficulties, many algorithms have been developed till
date, but currently, only two algorithms are extensively used. The two prominent methods
(algorithms) to solve Integer Linear Programming (ILP) are:

(1) Branch-and-Bound (B&B) method, and

(2) Cutting Plane method

A linear programming problem in which some or all the variables are restricted to take non-
negative integer (discrete) values is referred to as Integer Linear Programming (ILP)
Problem.

Prepared by Ranbir Kalita

• When all the variables are constrained to be integers, it is called as Pure Integer
Programming Problem (IPP).
• When only some of the variables are restricted to have integer values, the problem is
said to be a Mixed Integer Programming Problem (IPP).

The general computational steps to solve an ILP are:

• Relax the integer restrictions on all the integer variables and solve the problem as a
regular LPP to find the optimum results.
• Now start adding integer restrictions in the form of constraints and iteratively modify
the feasible solution space to get an optimum solution to the problem that also
satisfies the integer restrictions on the variables.
Prepared by Ranbir Kalita

Page - 2
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Branch-and-Bound (B&B) Algorithm

The B&B algorithm was first developed by A. Land and G. Doig in the year 1960.

Prepared by Ranbir Kalita

Another algorithm, called the Additive Algorithm was developed by E. Balas in the year
1965. But later, it was found that the additive algorithm is actually a special case of Land and
Doig B&B algorithm.

The method is named as Branch-and-Bound because, it first decomposes the floating

variable and forms sub-problems (Branching) to obtain a discrete value for the decomposed
variable; and then sets a lower bound or an upper bound (Bound) on the objective function
values obtained from the sub-problems to disregard any non-promising results.

The solution steps are as follows:

• Ignore integer restrictions and treat the given problem as a regular Linear

Prepared by Ranbir Kalita

Programming Problem (LPP). Solve the LPP, either analytically or graphically and
find out the optimum results.

• If the optimum solution satisfies the integer restrictions, then the current solution is
also the optimal solution for the Integer Programming Problem (IPP).

• Otherwise, select one floating variable (xj) and decompose the given problem into

two sub-problems by adding the new constraints xj* ≤ xj and xj ≥ xj*+1 . For

example, if xj = 2.45, then xj* = 2 and xj*+1 = 3. That is, the new constraints are 2 ≤

xj and xj ≥ 3. Here, xj* and xj*+1 are consecutive non-negative integers.

• Now, solve the two sub-problems and observe the optimal values. Among the two
result sets, select the one which satisfies the integer restrictions and gives closest
objective function value to that of the LPP optimum.
Prepared by Ranbir Kalita

• This value of the objective function obtained from the sub-problem sets a lower bound
or upper bound on the objective function values depending on whether the problem is
of maximization type or minimization type respectively.

• These lower or upper bounds helps to identify the non-promising results obtained
from the sub-problems during subsequent iterations and disregard them (fathomed). In
any subsequent iteration, if a better value of objective function is obtained, then these
lower or upper bounds should be upgraded to the improved one.

Page - 3
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

• Follow this process iteratively until every floating variable is decomposed into sub-
problems and each sub-problem is examined.

• Select the result of that particular sub-problem which gives the best value of the

Prepared by Ranbir Kalita

objective function and at the same time meets the integer restrictions on the variables.

Problem 3.1:

Solve the following problem and find the optimum value of the objective function:

Maximize Z = 2x1 + 3x2

Subject to,
6x1 + 5x2 ≤ 25
x1 + 3x2 ≤ 10
Where,
x1 , x2 non-negative integers
Solution:

Prepared by Ranbir Kalita

Step-1: Ignore the integer restrictions and solve the problem as a normal LPP.

Maximize Z = 2x1 + 3x2 + 0.s1 + 0.s2

Subject to,
6x1 + 5x2 + s1 = 25
x1 + 3x2 + s2 = 10
Where,
x1 , x2 , s1 , s2 ≥ 0

Putting x1 = x2 = 0, we get s1 = 25 and s2 = 10. This is a basic feasible solution.

Initial Iteration Table:

Cj 2 3 0 0
FR CB Basic x1 x2 s1 s2 b θ
Prepared by Ranbir Kalita

25/5
5/3 0 s1 6 5 1 0 25
=5
10/3 ← Key
0 s2 1 (3) 0 1 10
= 3.33 Row
Zj 0 0 0 0 0

NER: Cj – Zj 2 3 0 0
↑
Key
Column

Page - 4
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Since the NER contains > 0 values, therefore optimality condition is not reached yet.

New elements of s1 row for the First Iteration Table:

6 – (5/3 × 1) = 13/3 ; 5 – (5/3 × 3) = 0 ; 1 – (5/3 × 0) = 1

Prepared by Ranbir Kalita

0 – (5/3 × 1) = –5/3 ; 25 – (5/3 × 10) = 25/3

New elements of x2 row for the First Iteration Table:

Divide every element of s2 row of initial iteration table by 3.
1/3 1 0 1/3 10/3

First Iteration Table:

Cj 2 3 0 0
FR CB Basic x1 x2 s1 s2 b θ
25/13 ← Key
0 s1 (13/3) 0 1 –5/3 25/3
= 1.92 Row
1/13 3 x2 1/3 1 0 1/3 10/3 10

Prepared by Ranbir Kalita

Zj 1 3 0 1 10

NER: Cj – Zj 1 0 0 –1
↑
Key
Column

Since the NER contains > 0 values, therefore optimality condition is not reached yet.

New elements of x1 row for the Second Iteration Table:

Multiply every element of s1 row of the First Iteration Table by 3/13.
1 0 3/13 5/13 25/13

New elements of x2 row for the Second Iteration Table:

1/3 – (1/13 × 13/3) = 0 ; 1 – (1/13 × 0) = 1 ; 0 – (1/13 × 1) = –1/13
Prepared by Ranbir Kalita

1/3 – [1/13 × (–5/3)] = 6/13 ; 10/3 – (1/13 × 25/3) = 35/13

Page - 5
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Second Iteration Table:

Cj 2 3 0 0
FR CB Basic x1 x2 s1 s2 b θ

Prepared by Ranbir Kalita

--- 2 x1 1 0 3/13 5/13 25/13 ---
--- 3 x2 0 1 –1/13 6/13 35/13 ---
Zj 2 3 3/13 28/13 155/13

NER: Cj – Zj 0 0 –3/13 –28/13

Since the NER does not contains any > 0 value, therefore optimality condition is reached and
the optimum values are:

x1 = 25/13 = 1.92 x2 = 35/13 = 2.69 Zmax = 155/13 = 11.92

The graphical solution is shown below:

Prepared by Ranbir Kalita

Prepared by Ranbir Kalita

Now, the value of x1 and x2 does not conform to the non-negativity integer restriction given in
the original problem. Therefore, in the next step, we have to impose integer restriction on the
floating variables iteratively to find the optimum value of the ILP problem.

Page - 6
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Step-2: Imposing Integer Restrictions iteratively.

First, let us select x2 = 2.69 as the Branching Variable. Therefore, the given problem is
decomposed into two sub-problems imposing constraints x2 ≤ 2 and x2 ≥ 3 on Sub-problem-1

Prepared by Ranbir Kalita

and 2 respectively.
Sub-problem-1 Sub-problem-2
Maximize Z = 2x1 + 3x2 Maximize Z = 2x1 + 3x2
Subject to, Subject to,
6x1 + 5x2 ≤ 25 6x1 + 5x2 ≤ 25
x1 + 3x2 ≤ 10 x1 + 3x2 ≤ 10
x2 ≤ 2 x2 ≥ 3
Where, Where,
x1 , x2 ≥ 0 x1 , x2 ≥ 0
Optimum Results: x1 = 2.50, x2 = 2, Zmax = 11 Optimum Results: x1 = 1, x2 = 3, Zmax = 11

The values of x1 and x2 in Sub-problem-2 conform to the Integer Restrictions (Integer

Feasible solution) and as such the value of Zmax = 11 sets the Lower Bound (LB) for

Prepared by Ranbir Kalita

subsequent iterations.

The value of x1 in the Sub-problem-1 does not conform to the Integer Restrictions; but Zmax =
11 = LB. Therefore, x1 can be further branched with new constraints x1 ≤ 2 and x1 ≥ 3 in Sub-
problem-3 and 4 respectively in the subsequent iteration.
Sub-problem-3 Sub-problem-4
Maximize Z = 2x1 + 3x2 Maximize Z = 2x1 + 3x2
Subject to, Subject to,
6x1 + 5x2 ≤ 25 6x1 + 5x2 ≤ 25
x1 + 3x2 ≤ 10 x1 + 3x2 ≤ 10
x2 ≤ 2 x2 ≤ 2
x1 ≤ 2 x1 ≥ 3
Where, Where,
x1 , x2 ≥ 0 x1 , x2 ≥ 0
Optimum Results: x1 = 2, x2 = 2, Zmax = 10 Optimum Results: x1 = 3, x2 = 1.40, Zmax = 10.20
Prepared by Ranbir Kalita

The values of x1 and x2 in Sub-problem-3 conform to the Integer Restrictions (Integer

Feasible solution); therefore, no further branching required. But the value of Z = 10 < LB.
Therefore, this solution set is to be discarded.

The value of x2 in Sub-problem-4 does not conform to the Integer Restrictions and also the
value of Z = 10.20 < LB. Therefore, this solution set can be discarded directly without further
branching of x2.

Page - 7
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Since both Sub-problem-3 and 4 have been discarded, therefore, the Lower Bound ZL = 11
obtained from Sub-problem-2 remains unchanged.

Also since there are no Sub-problems available which can be branched further, therefore, the

Prepared by Ranbir Kalita

best solution corresponds to the Sub-problem-2 and it is the optimal solution to the given ILP
problem:
x1 = 1 , x2 = 3 , Zmax = 11

The whole process of branching is shown in the following tree diagram:

Prepared by Ranbir Kalita

Prepared by Ranbir Kalita

Page - 8
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

LPP
Maximize Z = 2x1 + 3x2
Subject to,
6x1 + 5x2 ≤ 25

Prepared by Ranbir Kalita

x1 + 3x2 ≤ 10
Where,
x1 , x2 ≥ 0
Optimum Solution:
x1 = 1.92 , x2 = 2.69
Zmax = 11.92

Branching Variable: x2 = 2.69

x2 ≤ 2 x2 ≥ 3

Sub-problem-1 Sub-problem-2
Maximize Z = 2x1 + 3x2 Maximize Z = 2x1 + 3x2
Subject to, Subject to,
6x1 + 5x2 ≤ 25 6x1 + 5x2 ≤ 25

Prepared by Ranbir Kalita

x1 + 3x2 ≤ 10 x1 + 3x2 ≤ 10
x2 ≤ 2 x2 ≥ 3
Where, Where,
x1 , x2 ≥ 0 x1 , x2 ≥ 0
Optimum Solution: Optimum Solution:
x1 = 2.50 , x2 = 2 x1 = 1 , x2 = 3
Zmax = 11 Zmax = 11
Integer Infeasible Solution. Integer Feasible Solution.
∵ Zmax = 11 = LB (ZL) ∴ LB (ZL) = Zmax = 11

∴ Branching Variable: x1 = 2.50

x1 ≥ 3
x1 ≤ 2
Sub-problem-3 Sub-problem-3
Maximize Z = 2x1 + 3x2 Maximize Z = 2x1 + 3x2
Subject to, Subject to,
6x1 + 5x2 ≤ 25 6x1 + 5x2 ≤ 25
Prepared by Ranbir Kalita

x1 + 3x2 ≤ 10 x1 + 3x2 ≤ 10
x2 ≤ 2 x2 ≤ 2
x1 ≤ 2 x1 ≥ 3
Where, Where,
x1 , x2 ≥ 0 x1 , x2 ≥ 0
Optimum Solution: Optimum Solution:
x1 = 2 , x2 = 2 x1 = 3 , x2 = 1.40
Zmax = 10 Zmax = 10.20
Integer Feasible Solution. Integer Infeasible Solution.
∵ Zmax < ZL ∴ Discarded. Also ∵ Zmax < ZL ∴ Discraded.

Page - 9
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Now, let’s see what if we had branched x1 = 1.92 instead of x2 = 2.69.

Therefore, let us select x1 as the Branching Variable. Therefore, the given problem is
decomposed into two sub-problems imposing constraints x2 ≤ 1 and x2 ≥ 2 on Sub-problem-5

Prepared by Ranbir Kalita

and 6 respectively.
Sub-problem-5 Sub-problem-6
Maximize Z = 2x1 + 3x2 Maximize Z = 2x1 + 3x2
Subject to, Subject to,
6x1 + 5x2 ≤ 25 6x1 + 5x2 ≤ 25
x1 + 3x2 ≤ 10 x1 + 3x2 ≤ 10
x1 ≤ 1 x1 ≥ 2
Where, Where,
x1 , x2 ≥ 0 x1 , x2 ≥ 0
Optimum Results: x1 = 1, x2 = 3, Zmax = 11 Optimum Results: x1 = 2, x2 = 2.60, Zmax = 11.80

The values of x1 and x2 in Sub-problem-5 conforms to the Integer Restrictions and therefore,
Zmax = 11 sets the Lower Bound (LB) for subsequent iterations.

Prepared by Ranbir Kalita

The value of x2 in Sub-problem-6 does not conform to the Integer Restrictions. But since Zmax
= 11.80 > LB (ZL), therefore, x2 = 2.60 is further branched into Sub-problem-7 and 8 with
constraints x2 ≤ 2 and x2 ≥ 3.

Sub-problem-7 Sub-problem-8
Maximize Z = 2x1 + 3x2 Maximize Z = 2x1 + 3x2
Subject to, Subject to,
6x1 + 5x2 ≤ 25 6x1 + 5x2 ≤ 25
x1 + 3x2 ≤ 10 x1 + 3x2 ≤ 10
x1 ≥ 2 x1 ≥ 2
x2 ≤ 2 x2 ≥ 3
Where, Where,
x1 , x2 ≥ 0 x1 , x2 ≥ 0
Optimum Results: The problem has no Feasible
Optimum Results: x1 = 2.50, x2 = 2, Zmax = 11
Solution.
Prepared by Ranbir Kalita

Sub-problem-8 does not have a feasible solution. Therefore, this sub-problem is discarded.

The value of x1 in Sub-problem-7 does not conform to the Integer Restrictions. But since Zmax
= 11 = LB (ZL), therefore, x2 = 2.50 can be further branched into Sub-problem-9 and 10 with
constraints x2 ≤ 2 and x2 ≥ 3. But as these two constraints are already imposed in Sub-
problem-7 and 8 respectively, therefore, another iteration (branching) imposing the same
constraints is meaningless. Thus, the Lower Bound ZL = 11 obtained from Sub-problem-5

Page - 10
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

remains unchanged and since no sub-problem is there to be examined further, therefore, the
optimum solution to the ILP problem is obtained from Sub-problem-5:

x1 = 1 , x2 = 3 , Zmax = 11

Prepared by Ranbir Kalita

Hence, we have seen that, whether we take x1 = 1.92 or x2 = 2.69 as the branching variable
and obtain the optimal results for the ILP problem, the optimal results remain the same, and
that is:
x1 = 1 , x2 = 3 , Zmax = 11

NOTE: The detailed analytical / graphical solution to the sub-problems 1 to 8 are not shown
above. But these sub-problems can easily be solved using either Simplex method or
Graphical method as per the suitability.

Prepared by Ranbir Kalita

Prepared by Ranbir Kalita

References

[1] Hamdy A. Taha (2007), Operations Research: An Introduction (8th edition), Pearson,
ISBN 0-13-188923·0, Chapter 9, pp. 349-398.
[2] Prem Kumar Gupta and D. S. Hira (2014), Operations Research (7th revised edition),
S. Chand, ISBN: 81-219-0281-9, Chapter 6, pp. 633-682.

Page - 11
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Problem 3.2:

Solve the following problem using Branch-and-Bound (B&B) method:

Minimize Z = 5x1 + 4x2

Prepared by Ranbir Kalita

Subject to,
3x1 + 2x2 ≥ 5
2x1 + 3x2 ≥ 7
Where,
x1 , x2 ≥ 0 and integer

Solution: Ignoring the Integer Restrictions on x1 and x2 and assuming the given problem to
be a regular LPP, the optimal solution is:
x1 = 0.20 , x2 = 2.20 , Zmin = 9.80

In the above solution, both x1 and x2 are not conforming to the integer restrictions. Therefore,

Prepared by Ranbir Kalita

let us take x2 = 2.20 and the Branching Variable and start the B&B method to obtain the
optimal values of the given ILP problem.

As shown in the B&B Tree:

• Sub-problem-2 solution is integer feasible; but Sub-problem-1 solution is not.

Therefore, Zmin = 12.00 obtained from Sub-problem-2 is set as the Upper Bound
(ZU). Since Zmin = 10.50 obtained from Sub-problem-1 is < ZU , therefore, x1 = 0.50 is
further branched in Sub-problem-3 and 4.

• Sub-problem-3 does not have any feasible solution and therefore discarded. Sub-
problem-4 solution is Integer Infeasible. But, since Zmin = 11.67 < ZU , therefore, x2 =
1.67 is further branched in Sub-problem-5 and 6.

• Since Sub-problem-5 already has x2 ≤ 2, therefore, it is just changed to x2 ≤ 1 and no

Prepared by Ranbir Kalita

new constraint is added. Though the solution is Integer Feasible, but since Zmin > ZU ,
therefore, it is discarded. Sub-problem-6 also has x2 ≤ 2, therefore, adding x2 ≥ 2 as a
new constraint is meaningless. Also, ≤ sign cannot be updated to a ≥ sign in the same
constraint. Therefore, it is discarded.

As no sub-problem remains to be examined, therefore, the integer feasible solution obtained

from Sub-problem-2 is the Integer Optimal Solution. Thus,

x1 = 0 , x2 = 3.00 , Zmin = 12.00

Page - 12
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

LPP Solution
Minimize Z = 5x1 + 4x2
Subject to,
3x1 + 2x2 ≥ 5

Prepared by Ranbir Kalita

2x1 + 3x2 ≥ 7
Where,
x1 , x2 ≥ 0
x1 = 0.20 , x2 = 2.20 , Zmin = 9.80
Branching Variable x2 = 2.20
x2 ≤ 2 x2 ≥ 3

Sub-problem-1 Sub-problem-2
Minimize Z = 5x1 + 4x2 Minimize Z = 5x1 + 4x2
Subject to, Subject to,
3x1 + 2x2 ≥ 5 3x1 + 2x2 ≥ 5
2x1 + 3x2 ≥ 7 2x1 + 3x2 ≥ 7
x2 ≤ 2 x2 ≥ 3
Where, Where,

Prepared by Ranbir Kalita

x1 , x2 ≥ 0 x1 , x2 ≥ 0
x1 = 0.50 , x2 = 2.00 , Zmin = 10.50 x1 = 0 , x2 = 3.00 , Zmin = 12.00
Integer Infeasible Solution Integer Feasible Solution | UB (ZU) = Zmin = 12.00
∵ Zmin < ZU ∴ Branch x1 = 0.50
x1 ≥ 1
x1 ≤ 0

Sub-problem-3 Sub-problem-4
Minimize Z = 5x1 + 4x2 Minimize Z = 5x1 + 4x2
Subject to, Subject to,
3x1 + 2x2 ≥ 5 3x1 + 2x2 ≥ 5
2x1 + 3x2 ≥ 7 2x1 + 3x2 ≥ 7
x2 ≤ 2 x2 ≤ 2
x1 ≤ 0 x1 ≥ 1
Where, Where,
x1 , x2 ≥ 0 x1 , x2 ≥ 0
No Feasible Solution. x1 = 1.00 , x2 = 1.67 , Zmin = 11.67
Prepared by Ranbir Kalita

∴ DISCARDED. x2 ≤ 1 Integer Infeasible Solution

∵ Zmin < ZU ∴ Branch x2 = 1.67

Sub-problem-5 x2 ≥ 2
Update x2 ≤ 2 to x2 ≤ 1.
Sub-problem-6
x1 = 2.00 , x2 = 1.00 , Zmin = 14.00 x2 ≤ 2 is already present.
Integer Feasible Solution. Including x2 ≥ 2 is meaningless.
But ∵ Zmin > ZU
∴ DISCARDED. ∴ DISCARDED.

Page - 13
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Problem 3.3:

Solve the following mixed integer problem using Branch-and-Bound method.

Maximize Z = x1 + x2

Prepared by Ranbir Kalita

Subject to,
2x1 + 5x2 ≤ 16
6x1 + 5x2 ≤ 30
Where,
x2 ≥ 0 , x1 ≥ 0 and integer

Solution: Ignoring the Integer Restrictions on x1 and assuming the given problem to be a
regular LPP, let us first find the optimal solution; and it is:
x1 = 3.50 , x2 = 1.80 , Zmax = 5.30
In the above solution, x1 is not conforming to Integer Restrictions. Therefore, let us branch x1

Prepared by Ranbir Kalita

= 3.5 in Sub-problem-1 and 2. The B&B Tree is shown below:

LPP Solution
Maximize Z = x1 + x2
Subject to,
2x1 + 5x2 ≤ 16
6x1 + 5x2 ≤ 30
Where,
x1 , x2 ≥ 0
x1 = 3.50 , x2 = 1.80 , Zmax = 5.30
Branching Variable x1 = 3.50
x1 ≤ 3 x1 ≥ 4

Sub-problem-1 Sub-problem-2
Maximize Z = x1 + x2 Maximize Z = x1 + x2
Subject to, Subject to,
Prepared by Ranbir Kalita

2x1 + 5x2 ≤ 16 2x1 + 5x2 ≤ 16

6x1 + 5x2 ≤ 30 6x1 + 5x2 ≤ 30
x1 ≤ 3 x1 ≥ 4
Where, Where,
x1 , x2 ≥ 0 x1 , x2 ≥ 0
x1 = 3.00 , x2 = 2.00 , Zmax = 5.00 x1 = 4.00 , x2 = 1.20 , Zmax = 5.20

Integer Feasible Solution Integer Feasible Solution

Page - 14
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

The values of x1 in Sub-problem-1 and 2 are conforming to Integer Restrictions. But, since
Zmax = 5.20 obtained from Sub-problem-2 is > Zmax = 5.00 obtained from Sub-problem-1,
therefore, the optimal solution to the Mixed Integer Problem is:

Prepared by Ranbir Kalita

x1 = 4.00 , x2 = 1.20 , Zmax = 5.20

The detailed Analytical calculations for General LPP, Sub-problem-1 and 2 are shown below:

General LPP Solution

Maximize Z = x1 + x2 + 0.s1 + 0.s2

Subject to,
2x1 + 5x2 + s1 = 16
6x1 + 5x2 + s2 = 30

Prepared by Ranbir Kalita

Where,
x2 , x1 , s1 , s2 ≥ 0

Putting x2 = x1 = 0, we get s1 = 16 and s2 = 30. This is a Basic Feasible Solution.

Iteration-1:
Cj 1 1 0 0
FR CB Basic x1 x2 s1 s2 b θ
1/3 0 s1 2 5 1 0 16 16/2 = 8
← Key
0 s2 (6) 5 0 1 30 30/6 = 5
Row
Zj 0 0 0 0 0

NER: Cj – Zj 1 1 0 0
Prepared by Ranbir Kalita

↑
Key
Column

Since NER has > 0 value, therefore, the current solution is not optimal.

New elements of s1 row for Iteration-2:

2 – (1/3 × 6) = 0 ; 5 – (1/3 × 5) = 10/3 ; 1 – (1/3 × 0) = 1
0 – (1/3 × 1) = –1/3 ; 16 – (1/3 × 30) = 6

Page - 15
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

New elements of x1 row for Iteration-2:

Divide every element of s2 row of Iteration-1 by 6.
1 5/6 0 1/6 5
Iteration-2:

Prepared by Ranbir Kalita

Cj 1 1 0 0
FR CB Basic x1 x2 s1 s2 b θ
← Key
0 s1 0 10/3 1 –1/3 6 1.8
Row
1/4 1 x1 1 5/6 0 1/6 5 6
Zj 1 5/6 0 1/6 5

NER: Cj – Zj 0 1/6 0 –1/6

↑
Key
Column

Prepared by Ranbir Kalita

Since NER has > 0 value, therefore, the current solution is not optimal.

New elements of x2 row for Iteration-3:

Multiply every element of s1 row of Iteration-2 by 3/10.
0 1 3/10 –1/10 9/5

New elements of x1 row for Iteration-3:

1 – (1/4 × 0) = 1 ; 5/6 – (1/4 × 10/3) = 0 ; 0 – (1/4 × 1) = –1/4
1/6 – [1/4 × (–1/3)] = 1/4 ; 5 – (1/4 × 6) = 7/2

Iteration-3:
Cj 1 1 0 0
FR CB Basic x1 x2 s1 s2 b θ
–1/10
Prepared by Ranbir Kalita

--- 1 x2 0 1 3/10 9/5 ---

--- 1 x1 1 0 –1/4 1/4 7/2 ---
Zj 1 1 1/20 3/20 53/10

NER: Cj – Zj 0 0 –1/20 –3/20

Since NER does not have > 0 value, therefore, the current solution is the optimal; and the
optimal values are:
x1 = 7/2 = 3.50 , x2 = 9/5 = 1.80 , Zmax = 53/10 = 5.30
Page - 16
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Sub-problem-1 Solution

Maximize Z = x1 + x2 + 0.s1 + 0.s2 + 0.s3

Subject to,

Prepared by Ranbir Kalita

2x1 + 5x2 + s1 = 16
6x1 + 5x2 + s2 = 30
x1 + s3 = 3
Where,
x2 , x1 , s1 , s2 , s3 ≥ 0

Putting x1 = x2 = 0, we get s1 = 16 , s2 = 30 and s3 = 3. This is a Basic Feasible Solution.

Iteration-1:
Cj 1 1 0 0 0
FR CB Basic x1 x2 s1 s2 s3 b θ
2 0 s1 2 5 1 0 0 16 8

Prepared by Ranbir Kalita

6 0 s2 6 5 0 1 0 30 5
← Key
0 s3 (1) 0 0 0 1 3 3
Row
Zj 0 0 0 0 0 0

NER: Cj – Zj 1 1 0 0 0
↑
Key
Column

Since NER has > 0 value, therefore, the current solution is not optimal.

Iteration-2:
Cj 1 1 0 0 0
FR CB Basic x1 x2 s1 s2 s3 b θ
← Key
Prepared by Ranbir Kalita

0 s1 0 (5) 1 0 –2 10 2
Row
1 0 s2 0 5 0 1 –6 12 2.4
0 1 x1 1 0 0 0 1 3 ∞
Zj 1 0 0 0 1 3

NER: Cj – Zj 0 1 0 0 0
↑
Key
Column

Page - 17
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Since NER has > 0 value, therefore, the current solution is not optimal.

Iteration-3:
Cj 1 1 0 0 0

Prepared by Ranbir Kalita

FR CB Basic x1 x2 s1 s2 s3 b θ
--- 1 x2 0 1 1/5 0 –2/5 2 ---
--- 0 s2 0 0 –1 1 –4 2 ---
--- 1 x1 1 0 0 0 1 3 ---
Zj 1 1 1/5 0 3/5 5

NER: Cj – Zj 0 0 –1/5 0 –3/5

Since NER does not have > 0 value, therefore, the current solution is the optimal solution;
and the optimal values are:

Prepared by Ranbir Kalita

x1 = 3.00 , x2 = 2.00 , Zmax = 5.00

Sub-problem-2 Solution

Maximize Z = x1 + x2 + 0.s1 + 0.s2 + 0.s3 – M.A3

Subject to,
2x1 + 5x2 + s1 = 16
6x1 + 5x2 + s2 = 30
x1 – s3 + A3 = 4
Where,
x2 , x1 , s1 , s2 , s3 , A3 ≥ 0
Prepared by Ranbir Kalita

Putting x1 = x2 = s3 = 0, we get s1 = 16 , s2 = 30 and A3 = 4. This is a Basic Feasible Solution.

Page - 18
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Iteration-1:
Cj 1 1 0 0 0 –M
FR CB Basic x1 x2 s1 s2 s3 A3 b θ

Prepared by Ranbir Kalita

2 0 s1 2 5 1 0 0 0 16 8
6 0 s2 6 5 0 1 0 0 30 5
← Key
–M A3 (1) 0 0 0 –1 1 4 4
Row
Zj –M 0 0 0 M –M –4M

NER: Cj – Zj 1+M 1 0 0 –M 0
↑
Key
Column

Since NER has > 0 value, therefore, the current solution is not optimal.

Iteration-2:

Prepared by Ranbir Kalita

Cj 1 1 0 0 0
FR CB Basic x1 x2 s1 s2 s3 b θ
1 0 s1 0 5 1 0 2 8 1.6
← Key
0 s2 0 (5) 0 1 6 6 1.2
Row
0 1 x1 1 0 0 0 –1 4 ∞
Zj 1 0 0 0 –1 4

NER: Cj – Zj 0 1 0 0 1
↑
Key
Column

Since NER has > 0 value, therefore, the current solution is not optimal.
Prepared by Ranbir Kalita

Page - 19
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Iteration-3:
Cj 1 1 0 0 0
FR CB Basic x1 x2 s1 s2 s3 b θ

Prepared by Ranbir Kalita

--- 0 s1 0 0 1 –1 –4 2 ---
--- 1 x2 0 1 0 1/5 6/5 6/5 ---
--- 1 x1 1 0 0 0 –1 4 ---
Zj 1 1 0 1/5 1/5 26/5

NER: Cj – Zj 0 0 0 –1/5 –1/5

Since NER does not have > 0 value, therefore, the current solution is the optimal solution;
and the optimal values are:

x1 = 4.00 , x2 = 1.20 , Zmax = 5.20

Prepared by Ranbir Kalita

Prepared by Ranbir Kalita

References

[1] Hamdy A. Taha (2007), Operations Research: An Introduction (8th edition), Pearson,
ISBN 0-13-188923·0, Chapter 9, pp. 349-398.
[2] Prem Kumar Gupta and D. S. Hira (2014), Operations Research (7th revised edition),
S. Chand, ISBN: 81-219-0281-9, Chapter 6, pp. 633-682.

Page - 20
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Cutting-Plane Algorithm
Similar to Branch-and-Bound (B&B) algorithm, the Cutting-Plane Algorithm also starts with
a Continuous Optimum LP Solution. But, unlike B&B algorithm where the problem is

Prepared by Ranbir Kalita

branched w.r.t. a non-integer variable into sub-problems and new constraints are added in
each sub-problem to eliminate the region within the feasible solution space which does not
have an integer value of the variable; in Cutting-plane algorithm, no such branching is done.
Instead, special constraints, called the Cuts, are added to modify the solution space and
produce an optimal integer extreme point. Care should be taken while slicing off a portion
of solution space that the sliced portion should not contain any feasible integer solution to the
original problem.

The process of deriving these special constraints (Cuts) was developed by Gomory and
therefore, these cuts are also called as Gomory’s constraints. These cuts are also referred to
as the Fractional Cuts because each cut is constructed from the fractional components of the

Prepared by Ranbir Kalita

coefficients of the source row.

The solution procedure in Gomory’s Cutting-Plane algorithm is given below:

• Find out the continuous optimal solution of the given LPP ignoring the Integer
Restrictions.
• From the Final Simplex Table of the LPP, select a Source Row corresponding to the
Non-integer Real Decision Variable with the largest Fractional Value (part) under
Solution Column (b-column) and construct the Gomory’s Constraint (cut).
• Tie-breaking rule: choose the Gomory’s constraint with the maximum value
of following ratio:
RHS constant of Gomory ′ s constraint 𝑏𝑖
max [ ] = max [ ]
∑ 𝑎ij in Gomory ′ s constraint ∑ 𝑎𝑖𝑗
Prepared by Ranbir Kalita

• Add the Gomory’s Constraint in the Final Simplex Table of the LPP and solve it using
the Dual Simplex Algorithm.
• If the Feasible Optimal Solution obtained from the Final Dual Simplex Table is
again integer infeasible, then again select a Source Row from the Final Dual Simplex
Table to construct another Gomory’s constraint. Add this constraint in the Final Dual
Simplex Table and again find out another Feasible Optimal Solution. Repeat this
process till an Integer Feasible Solution is obtained.

Page - 21
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

IMORTANT: For application of Cutting-Plane Algorithm, all the coefficients and constants
in each constraint must be whole numbers.

The solution procedure is explained using a numerical problem.

Prepared by Ranbir Kalita

Problem 3.4:

Solve the following problem using Gomory’s Cutting-Plane algorithm.

Maximize Z = 7x1 + 10x2

Subject to,
–x1 + 3x2 ≤ 6
7x1 + x2 ≤ 35
Where,
x1 , x2 ≥ 0 and integer

Solution: Ignoring the Integer Restrictions, first find out the continuous optimal solution of

Prepared by Ranbir Kalita

the given LP.
Maximize Z = 7x1 + 10x2 + 0.s1 + 0.s2
Subject to,
–x1 + 3x2 + s1 = 6
7x1 + x2 + s2 = 35
Where, x1 , x2 , s1 , s2 ≥ 0 and integer
Putting x1 = x2 = 0, we get, s1 = 6 and s2 = 35

Initial Simplex Table:

Cj 7 10 0 0
FR CB Basic x1 x2 s1 s2 b θ
← Key
0 s1 –1 (3) 1 0 6 6/3 = 2
Prepared by Ranbir Kalita

Row
1/3 0 s2 7 1 0 1 35 35/1 = 35
Zj 0 0 0 0 0

NER: Cj – Zj 7 10 0 0
↑
Key
Column

Page - 22
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

New elements of x2 row for First Iteration Table:

Divide s1 row of Initial Iteration Table by 3.
–1/3 1 1/3 0 2

Prepared by Ranbir Kalita

New elements of s2 row for First Iteration Table:
7 – [1/3 × (–1)] = 22/3 ; 1 – [1/3 × 3] = 0 ; 0 – [1/3 × 1] = –1/3

1 – [1/3 × 0] = 1 ; 35 – [1/3 × 6] = 33

First Iteration Table:

Cj 7 10 0 0
FR CB Basic x1 x2 s1 s2 b θ
–1/22 10 x2 –1/3 1 1/3 0 2 –6
← Key
0 s2 (22/3) 0 –1/3 1 33 9/2
Row
Zj –10/3 10 10/3 0 20

Prepared by Ranbir Kalita

NER: Cj – Zj 31/3 0 –10/3 0
↑
Key
Column

New elements of x2 row for Second Iteration Table:

–1/3 – [(–1/22) × 22/3] = 0 ; 1 – [(–1/22) × 0] = 1
1/3 – [(–1/22) × (–1/3)] = 7/22 ; 0 – [(–1/22) × 1] = 1/22
2 – [(–1/22) × 33] = 7/2

New elements of x1 row for Second Iteration Table:

Multiply every element of s2 row of the First Iteration Table by (3/22).
1 0 –1/22 3/22 9/22
Prepared by Ranbir Kalita

Page - 23
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Second Iteration Table:

Cj 7 10 0 0
FR CB Basic x1 x2 s1 s2 b θ

Prepared by Ranbir Kalita

--- 10 x2 0 1 7/22 1/22 7/2 ---
--- 7 x1 1 0 –1/22 3/22 9/2 ---
Zj 7 10 63/22 31/22 133/2

NER: Cj – Zj 0 0 –63/22 –31/22

Therefore, the Continuous Optimal Solution is:

x1 = 9/2 = 4½ ; x2 = 7/2 = 3½ ; Zmax = 133/2 = 66½

The above optimal solution is Integer Infeasible in both x1 and x2. Now, we will construct the
First Gomory’s Constraint (Cut-1).

Prepared by Ranbir Kalita

As can be seen, the fractional part of x1 and x2 are the same, i.e. 1/2. Therefore, we have to
use the Tie-breaking rule.

Gomory’s constraint from x1 row of the Final Simplex Table:

1 3 9
𝑥1 − 𝑠1 + 𝑠2 =
22 22 2

Factor out all the non-integer coefficients of the above equation into an integer value
(+ve / –ve) and a fractional component (strictly +ve). Therefore,

21 3 1
𝑥1 + (−1 + ) 𝑠1 + (0 + ) 𝑠2 = (4 + )
22 22 2

21 3 1
⇒ 𝑥1 − 𝑠1 − 4 = (− 𝑠1 − 𝑠2 + )
22 22 2
Prepared by Ranbir Kalita

As done above, all the fractional parts are brought to the RHS and all the integer parts are
brought to the LHS. Therefore, the Desired Cut is:

21 3 1 𝟐𝟏 𝟑 𝟏
− 𝑠1 − 𝑠2 + ≤ 0 ⇒ − 𝒔𝟏 − 𝒔𝟐 ≤ −
22 22 2 𝟐𝟐 𝟐𝟐 𝟐

Page - 24
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Gomory’s constraint from x2 row of the Final Simplex Table:

7 1 7
𝑥2 + 𝑠1 + 𝑠2 =
22 22 2
7 1 1

Prepared by Ranbir Kalita

⇒ 𝑥2 + (0 + ) 𝑠1 + (0 + ) 𝑠2 = (3 + )
22 22 2
7 1 1
⇒ 𝑥2 − 3 = (− 𝑠1 − 𝑠2 + )
22 22 2

Therefore, the Desired Cut is:

7 1 1 𝟕 𝟏 𝟏
− 𝑠1 − 𝑠2 + ≤ 0 ⇒ − 𝒔𝟏 − 𝒔𝟐 ≤ −
22 22 2 𝟐𝟐 𝟐𝟐 𝟐

Tie Breaking: From the Cuts obtained from x1 and x2 Source Rows, we get,

1 1
𝑏𝑖 𝑏𝑖 −2 −2 11 11
max [( ) ,( ) ] = max [ , ] = max [ , ]
∑ 𝑎𝑖𝑗 ∑ 𝑎𝑖𝑗 21 3 7 1 24 8

Prepared by Ranbir Kalita

𝑥1 𝑥2 − 22 − 22 − 22 − 22

𝟏𝟏
= corresponding to 𝑥2
𝟖

Therefore, the cut obtained from the x2 Source Row has been selected to initiate the Dual
Simplex Algorithm. The constraint is expressed in equation form by introducing the Slack
Variable s3.
𝟕 𝟏 𝟏
− 𝒔𝟏 − 𝒔𝟐 + 𝒔𝟑 = −
𝟐𝟐 𝟐𝟐 𝟐

Now, the Initial Basic Solution obtained from this constraint equation is s3 = –1/2, which
makes the solution Infeasible. As such, the Dual Simplex Algorithm can be used here.
Prepared by Ranbir Kalita

Page - 25
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Initial Dual Simplex Table:

Cj 7 10 0 0 0
FR CB Basic x1 x2 s1 s2 s3 b

Prepared by Ranbir Kalita

–1 10 x2 0 1 7/22 1/22 0 7/2
1/7 7 x1 1 0 –1/22 3/22 0 9/2
← Key
0 s3 0 0 (–7/22) –1/22 1 –1/2
Row
Zj 7 10 63/22 31/22 0 133/2

NER: Cj – Zj 0 0 –63/22 –31/22 0

θ --- --- 63/7 31
↑
Key
Column

New elements of x2 row for First Iteration Table:

Prepared by Ranbir Kalita

0 – [(–1) × 0] = 0 ; 1 – [(–1) × 0] = 1
7/22 – [(–1) × (–7/22)] = 0 ; 1/22 – [(–1) × (–1/22)] = 0
0 – [(–1) × 1] = 1 ; 7/2 – [(–1) × (–1/2)] = 3

New elements of x1 row for First Iteration Table:

1 – [1/7 × 0] = 1 ; 0 – [1/7 × 0] = 0
–1/22 – [1/7 × (–7/22)] = 0 ; 3/22 – [1/7 × (–1/22)] = 1/7
0 – [1/7 × 0] = –1/7 ; 9/2 – [1/7 × (–1/2)] = 32/7

New elements of s1 row for First Iteration Table:

Multiply every element of Initial Dual Simplex Table by (–22/7).
0 0 1 1/7 –22/7 11/7
Prepared by Ranbir Kalita

Page - 26
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

First Iteration Table:

Cj 7 10 0 0 0
FR CB Basic x1 x2 s1 s2 s3 b

Prepared by Ranbir Kalita

10 x2 0 1 0 0 1 3
7 x1 1 0 0 1/7 –1/7 32/7
0 s1 0 0 1 1/7 –22/7 11/7
Zj 7 10 0 1 9 62

NER: Cj – Zj 0 0 0 –1 –9

All bi values are > 0. Therefore, the current solution is the Feasible Optimal Solution.
x1 = 32/7 = 4(4/7) ; x2 = 3 ; Zmax = 62

In the above solution set, only x1 is Integer Infeasible, i.e. only x1 has the fractional part.
Therefore, x1 row is chosen as the Source Row to construct the Second Gomory’s

Prepared by Ranbir Kalita

Constraint from the above final dual simplex table.
[s1 row is not selected because it is a Slack Variable.]

1 1 32 1 6 4
𝑥1 + 𝑠2 − 𝑠3 = ⇒ 𝑥1 + (0 + ) 𝑠2 + (−1 + ) 𝑠3 = (4 + )
7 7 7 7 7 7

1 6 4
⇒ 𝑥1 − 𝑠3 − 4 = (− 𝑠2 − 𝑠3 + )
7 7 7

Therefore, the Desired Cut is:

1 6 4 𝟏 𝟔 𝟒
− 𝑠2 − 𝑠3 + ≤ 0 ⇒ − 𝒔𝟐 − 𝒔𝟑 ≤ −
7 7 7 𝟕 𝟕 𝟕

The constraint is expressed in equation form by introducing the Slack Variable s4.
Prepared by Ranbir Kalita

𝟏 𝟔 𝟒
− 𝒔𝟐 − 𝒔𝟑 + 𝒔𝟒 = −
𝟕 𝟕 𝟕

Now, the Initial Basic Solution obtained from this constraint equation is s4 = –4/7, which
makes the solution Infeasible. As such, the Dual Simplex Algorithm can be used here.

Page - 27
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Initial Dual Simplex Table:

Cj 7 10 0 0 0 0
FR CB Basic x1 x2 s1 s2 s3 s4 b

Prepared by Ranbir Kalita

0 10 x2 0 1 0 0 1 0 3
–1 7 x1 1 0 0 1/7 –1/7 0 32/7
–1 0 s1 0 0 1 1/7 –22/7 0 11/7
← Key
--- 0 s4 0 0 0 –1/7 –6/7 1 –4/7
Row
Zj 7 10 0 1 9 0 62

NER: Cj – Zj 0 0 0 –1 –9 0
θ --- --- --- 7 21/2 ---
↑
Key
Column

Prepared by Ranbir Kalita

New elements of x2 row for First Iteration Table:
0 – [0 × 0] = 0 ; 1 – [0 × 0] = 1 ; 0 – [0 × 0] = 0
0 – [0 × (–1/7)] = 0 ; 1 – [0 × (–6/7)] = 1 ; 0 – [0 × 1] = 0
3 – [0 × (–4/7)] = 3

New elements of x1 row for First Iteration Table:

1 – [(–1) × 0] = 1 ; 0 – [(–1) × 0] = 0 ; 0 – [(–1) × 0] = 0
1/7 – [(–1) × (–1/7)] = 0 ; –1/7 – [(–1) × (–6/7)] = –1
0 – [(–1) × 1] = 1 ; 32/7 – [(–1) × (–4/7)] = 4

New elements of s1 row for First Iteration Table:

0 – [(–1) × 0] = 0 ; 0 – [(–1) × 0] = 0 ; 1 – [(–1) × 0] = 1
1/7 – [(–1) × (–1/7)] = 0 ; –22/7 – [(–1) × (–6/7)] = –4
Prepared by Ranbir Kalita

0 – [(–1) × 1] = 1 ; 11/7 – [(–1) × (–4/7)] = 1

New elements of s2 row for First Iteration Table:

Multiply every element of s4 row of Initial Dual Simplex Table by (–7).
0 0 0 1 6 –7 4

Page - 28
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

First Iteration Table:

Cj 7 10 0 0 0 0
FR CB Basic x1 x2 s1 s2 s3 s4 b

Prepared by Ranbir Kalita

--- 10 x2 0 1 0 0 1 0 3
--- 7 x1 1 0 0 0 –1 1 4
--- 0 s1 0 0 1 0 –4 1 1
--- 0 s2 0 0 0 1 6 –7 4

Zj 7 10 0 0 3 7 58

NER: Cj – Zj 0 0 0 0 –3 –7

Since all bi values are > 0, therefore, the current solution is the Feasible Optimal Solution.
x1 = 4 ; x2 = 3 ; Zmax = 58

The above solution set is Integer Feasible. Therefore, this is the Optimal Integer Solution for

Prepared by Ranbir Kalita

the given ILP.

Prepared by Ranbir Kalita

References

[1] Hamdy A. Taha (2007), Operations Research: An Introduction (8th edition), Pearson,
ISBN 0-13-188923·0, Chapter 9, pp. 379-384.
[2] Prem Kumar Gupta and D. S. Hira (2014), Operations Research (7th revised edition),
S. Chand, ISBN: 81-219-0281-9, Chapter 6, pp. 645-660.

Page - 29
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Problem 3.5:

Solve the following problem using Gomory’s Cutting-Plane algorithm.

Minimize Z = –5x1 – 7x2

Prepared by Ranbir Kalita

Subject to,
2x1 – 3x2 ≥ –6
–6x1 – x2 ≥ –30
Where, x1 , x2 ≥ 0 and integer

Solution: Since, in Cutting-Plane algorithm, we need to use the Dual Simplex Algorithm,
therefore, the given problem is converted to a Maximization problem in Canonical Form.
Maximize W = 5x1 + 7x2
Subject to,
–2x1 + 3x2 ≤ 6
6x1 + x2 ≤ 30

Prepared by Ranbir Kalita

Where, x1 , x2 ≥ 0 and integer
Now first, find out the continuous optimal solution of the given problem ignoring the integer
restrictions.
Maximize W = 5x1 + 7x2 + 0.s1 + 0.s2
Subject to,
–2x1 + 3x2 + s1 = 6
6x1 + x2 + s2 = 30
Where, x1 , x2 , s1 , s2 ≥ 0
Putting x1 = x2 = 0, we get, s1 = 6 and s2 = 30. This an Initial Basic Feasible Solution.

Initial Simplex Table:

Cj 5 7 0 0
Prepared by Ranbir Kalita

FR CB Basic x1 x2 s1 s2 b θ
← Key
--- 0 s1 –2 (3) 1 0 6 6/3 = 2
Row
1/3 0 s2 6 1 0 1 30 30/1 = 30
Zj 0 0 0 0 0

NER: Cj – Zj 5 7 0 0
↑
Key
Column

Page - 30
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

New elements of x2 row for First Iteration Table:

Divide every element of s1 row of the Initial Simplex Table by 3.
–2/3 1 1/3 0 2

Prepared by Ranbir Kalita

New elements of s2 row for First Iteration Table:
6 – [1/3 × (–2)] = 20/3 ; 1 – [1/3 × 3] = 0 ; 0 – [1/3 × 1] = –1/3
1 – [1/3 × 0] = 1 ; 30 – [1/3 × 6] = 28

First Iteration Table:

Cj 5 7 0 0
FR CB Basic x1 x2 s1 s2 b θ
–1/10 7 x2 –2/3 1 1/3 0 2 –3
← Key
--- 0 s2 (20/3) 0 –1/3 1 28 21/5

Prepared by Ranbir Kalita

Row
Zj –14/3 7 7/3 0 14

NER: Cj – Zj 29/3 0 –7/3 0

↑
Key
Column

New elements of x2 row for Second Iteration Table:

–2/3 – [(–1/10) × 20/3] = 0 ; 1 – [(–1/10) × 0] = 1
1/3 – [(–1/10) × (–1/3)] = 3/10 ; 0 – [(–1/10) × 1] = 1/10
2 – [(–1/10) × 28] = 24/5

New elements of x1 row for Second Iteration Table:

Multiply every element of s2 row of First Iteration Table by (3/20)
–1/20
Prepared by Ranbir Kalita

1 0 3/20 21/5

Page - 31
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Second Iteration Table:

Cj 5 7 0 0
FR CB Basic x1 x2 s1 s2 b θ

Prepared by Ranbir Kalita

--- 7 x2 0 1 3/10 1/10 24/5 ---
--- 5 x1 1 0 –1/20 3/20 21/5 ---
Zj 5 7 37/20 29/20 273/5

NER: Cj – Zj 0 0 –37/20 –29/20

Therefore, the Continuous Optimal Solution is:

x1 = 21/5 = 4(1/5) ; x2 = 24/5 = 4(4/5) ; Wmax = 273/5 = 54(3/5)

The above solution set is integer infeasible in both x1 and x2. Since x2 has the larger Fraction
Part (4/5), therefore, x2 row is selected to construct the Gomory’s Constraint (Cut-1).

3 1 24 3 1 4

Prepared by Ranbir Kalita

𝑥2 + 𝑠1 + 𝑠2 = ⇒ 𝑥2 + (0 + ) 𝑠1 + (0 + ) 𝑠2 = (4 + )
10 10 5 10 10 5

3 1 4
⇒ 𝑥2 − 4 = (− 𝑠1 − 𝑠2 + )
10 10 5

Therefore, the desired cut is:

3 1 4 𝟑 𝟏 𝟒
− 𝑠1 − 𝑠2 + ≤ 0 ⇒ − 𝒔𝟏 − 𝒔𝟐 ≤ −
10 10 5 𝟏𝟎 𝟏𝟎 𝟓

The above constraint is converted into an equation by introduction Slack Variable s3.

3 1 4
− 𝑠1 − 𝑠2 + 𝑠3 = −
10 10 5

The initial basic solution obtained from the above constraint is infeasible (since s3 = –4/5).
Prepared by Ranbir Kalita

Therefore, the Dual Simplex Algorithm can be used.

Page - 32
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Initial Dual Simplex Table:

Cj 5 7 0 0 0
FR CB Basic x1 x2 s1 s2 s3 b

Prepared by Ranbir Kalita

–1 7 x2 0 1 3/10 1/10 0 24/5
1/6 5 x1 1 0 –1/20 3/20 0 21/5
← Key
0 s3 0 0 (–3/10) –1/10 1 –4/5
Row
Zj 5 7 37/20 29/20 0 273/5

NER: Cj – Zj 0 0 –37/20 –29/20 0

θ --- --- 37/6 29/2 ---
↑
Key
Column

New elements of x2 row for the First Iteration Table:

Prepared by Ranbir Kalita

0 – [(–1) × 0] = 0 ; 1 – [(–1) × 0] = 1
3/10 – [(–1) × (–3/10)] = 0 ; 1/10 – [(–1) × (–1/10)] = 0
0 – [(–1) × 1] = 1 ; 24/5 – [(–1) × (–4/5)] = 4

New elements of x1 row for the First Iteration Table:

1 – [1/6 × 0] = 1 ; 0 – [1/6 × 0] = 0
–1/20 – [1/6 × (–3/10)] = 0 ; 3/20 – [1/6 × (–1/10)] = 1/6
0 – [1/6 × 1] = –1/6 ; 21/5 – [1/6 × (–4/5)] = 13/3

New elements of s1 row for the First Iteration Table:

Multiply every element of s1 row of the Initial Dual Simplex Table by (–10/3).
0 0 1 1/3 –10/3 8/3
Prepared by Ranbir Kalita

Page - 33
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

First Iteration Table:

Cj 5 7 0 0 0
FR CB Basic x1 x2 s1 s2 s3 b

Prepared by Ranbir Kalita

--- 7 x2 0 1 0 0 1 4
--- 5 x1 1 0 0 1/6 –1/6 13/3
--- 0 s1 0 0 1 1/3 –10/3 8/3
Zj 5 7 0 5/6 37/6 149/3

NER: Cj – Zj 0 0 0 –5/6 –37/6

Since all the bi values are > 0, therefore, the current solution is the Feasible Optimal Solution.

x1 = 13/3 = 4(1/3) ; x2 = 4 ; Wmax = 149/3 = 49(2/3)

This solution set is also integer infeasible w.r.t. variable x1. Therefore, x1 row is selected to

Prepared by Ranbir Kalita

construct the Gomory’s Constraint (Cut-2).

1 1 13 1 5 1
𝑥1 + 𝑠2 − 𝑠3 = ⇒ 𝑥1 + (0 + ) 𝑠2 + (−1 + ) 𝑠3 = (4 + )
6 6 3 6 6 3

1 5 1
⇒ 𝑥1 − 𝑠3 − 4 = (− 𝑠2 − 𝑠3 + )
6 6 3

Therefore, the desired cut is:

1 5 1 𝟏 𝟓 𝟏
− 𝑠2 − 𝑠3 + ≤ 0 ⇒ − 𝒔𝟐 − 𝒔𝟑 ≤ −
6 6 3 𝟔 𝟔 𝟑

The above constraint is converted into an equation by introduction Slack Variable s4.

1 5 1
− 𝑠2 − 𝑠3 + 𝑠4 = −
Prepared by Ranbir Kalita

6 6 3

The initial basic solution obtained from the above constraint is infeasible (since s4 = –1/3).
Therefore, the Dual Simplex Algorithm can be used.

Page - 34
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Initial Dual Simplex Table:

Cj 5 7 0 0 0 0
FR CB Basic x1 x2 s1 s2 s3 s4 b

Prepared by Ranbir Kalita

0 7 x2 0 1 0 0 1 0 4
–1 5 x1 1 0 0 1/6 –1/6 0 13/3
–2 0 s1 0 0 1 1/3 –10/3 0 8/3
← Key
--- 0 s4 0 0 0 (–1/6) –5/6 1 –1/3
Row
Zj 5 7 0 5/6 37/6 0 149/3

NER: Cj – Zj 0 0 0 –5/6 –37/6 0

θ --- --- --- 5 37/5 ---
↑
Key
Column

Prepared by Ranbir Kalita

New elements of x2 row for First Iteration Table:
0 – [0 × 0] = 0 ; 1 – [0 × 0] = 1 ; 0 – [0 × 0] = 0
0 – [0 × (–1/6)] = 0 ; 1 – [0 × (–5/6)] = 1 ; 0 – [0 × 1] = 0
4 – [0 × (–1/3)] = 4

New elements of x1 row for First Iteration Table:

1 – [(–1) × 0] = 1 ; 0 – [(–1) × 0] = 0 ; 0 – [(–1) × 0] = 0
1/6 – [(–1) × (–1/6)] = 0 ; –1/6 – [(–1) × (–5/6)] = –1
0 – [(–1) × 1] = 1 ; 13/3 – [(–1) × (–1/3)] = 4

New elements of s1 row for First Iteration Table:

0 – [(–2) × 0] = 0 ; 0 – [(–2) × 0] = 0 ; 1 – [(–2) × 0] = 1
1/3 – [(–2) × (–1/6)] = 0 ; –10/3 – [(–2) × (–5/6)] = –5
Prepared by Ranbir Kalita

0 – [(–2) × 1] = 2 ; 8/3 – [(–2) × (–1/3)] = 2

New elements of s2 row for First Iteration Table:

Multiply every element of s4 row of Initial Dual Simplex Table by (–6).
0 0 0 1 5 –6 2

Page - 35
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

First Iteration Table:

Cj 5 7 0 0 0 0
FR CB Basic x1 x2 s1 s2 s3 s4 b

Prepared by Ranbir Kalita

--- 7 x2 0 1 0 0 1 0 4
--- 5 x1 1 0 0 0 –1 1 4
--- 0 s1 0 0 1 0 –5 2 2
--- 0 s2 0 0 0 1 5 –6 2

Zj 5 7 0 0 2 5 48

NER: Cj – Zj 0 0 0 0 –2 –5

Since all bi values are > 0, therefore, the current solution is the Feasible Optimal Solution.

x1 = 4 ; x2 = 4 ; Wmax = 48 ; ∴ Zmin = –48

Prepared by Ranbir Kalita

The above solution set is Integer Feasible. Therefore, this is the Optimal Integer Solution for
the given ILP.

Prepared by Ranbir Kalita

References

[1] Hamdy A. Taha (2007), Operations Research: An Introduction (8th edition), Pearson,
ISBN 0-13-188923·0, Chapter 9, pp. 379-384.
[2] Prem Kumar Gupta and D. S. Hira (2014), Operations Research (7th revised edition),
S. Chand, ISBN: 81-219-0281-9, Chapter 6, pp. 645-660.

Page - 36
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

TRANSPORTATION MODELS

Transportation Model is also known as Distribution Model. It deals with the

Prepared by Ranbir Kalita

transportation of a product available at several sources to a number of different destinations.
This model can be used for a wide variety of situations such as scheduling, production,
investment, plant location, inventory control, employment scheduling, personnel assignment,
product mix problems and many others. Therefore, the model is really not confined to
transportation or distribution only.

In 1941, F. L. Hitchcock first presented the idea of transportation model in his study
“The Distribution of a Product from Several Sources to Numerous Localities”. Later, in the
year 1947, T. C. Koopmans presented his study on transportation model entitled “Optimum
Utilization of the Transportation System”.

The transportation model involves a number of shipping sources and a number of

Prepared by Ranbir Kalita

destinations. Each shipping source has a certain capacity and each destination has a certain
requirement associated with a certain cost of shipping from the sources to the destinations.
The objective is to minimize the cost of transportation while meeting the requirements at the
destinations. Transportation problems may also involve movement of a product from plants
to warehouses, warehouses to wholesalers, wholesalers to retailers and retailers to customers.

Assumptions in the Transportation Model

1. Availability at the sources is equal to requirement at the destinations.

2. Convenient transportation from all sources to all destinations.
3. Unit transportation cost from all sources to all destinations is certain and precisely
Prepared by Ranbir Kalita

known.
4. On a given route, total transportation cost is directly proportional to the number of
items shipped.
5. The objective is to minimize the Total Transportation Cost for the organization as a
whole and not for individual supply and distribution centres.

Page - 37
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Definition of the Transportation Model

The distinct feature of transportation model is that the sources and destinations must be
expressed in terms of only one kind of unit (product),

Prepared by Ranbir Kalita

Transportation Model is a case of LPP

Let,

There are m-number of sources and n-number of destinations.

ai is the number of supply units available at source i , where i = 1, 2, 3, ......... , m

bj is the number of demand units required at destination j , where j = 1, 2, 3, ......... , n

cij is the unit transportation cost from source i to destination j

xij is the number of units shipped from source i to destination j [xij ≥ 0]

Prepared by Ranbir Kalita

The objective is to determine the number of units to be transported (Z) from source i to
destination j so that the total transportation cost is minimum.

𝒎 𝒏

𝐌𝐢𝐧𝐢𝐦𝐢𝐳𝐞 𝐙 = ∑ ∑ 𝒄𝒊𝒋 𝒙𝒊𝒋

𝒊=𝟏 𝒋=𝟏

Subject to the constraints,

𝒏

∑ 𝒙𝒊𝒋 = 𝒂𝒊 , 𝑖 = 1, 2, 3, … … … , 𝑚
𝒋=𝟏

∑ 𝒙𝒊𝒋 = 𝒃𝒋 , 𝑗 = 1, 2, 3, … … … , 𝑛
𝒊=𝟏
Prepared by Ranbir Kalita

Where,
𝒙𝒊𝒋 ≥ 𝟎

The two constraints shown above can be interpreted respectively as:

• Total number of units shipped to all the destinations (j) must be equal to the total
number of units available in all the sources (i) combined.
• Total number of units shipped from all the sources (i) must be equal to the total
number of units required in all the destinations (j) combined.

Page - 38
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

When,
𝒎 𝒏

∑ 𝒂𝒊 = ∑ 𝒃𝒋
𝒊=𝟏 𝒋=𝟏

Prepared by Ranbir Kalita

=> Availability = Demand

The problem is called a Balanced / Standard Transportation problem and only a balanced
transportation problem can have a Feasible Solution. This means, the above condition is the
necessary as well as the sufficient condition for a transportation problem to have a feasible
solution.

Also since,

𝒎 𝒏

∑ 𝒂𝒊 = ∑ 𝒃𝒋
𝒊=𝟏 𝒋=𝟏

Prepared by Ranbir Kalita

One of the constraints is redundant and hence can be deleted. Therefore, the problem will
have (m + n – 1) constraints and (m × n) unknowns.

Solution techniques are available only to solve Balanced Transportation problems. In an

un-balanced transportation problem, i.e. where supply and demand are not equal, must
be converted into a balanced transportation problem by using Dummy Source/Destination.

The general matrix form of a transportation problem is:

Destinations
1 2 3 j n
C11 C12 C13 C1j C1n
1 a1
x11 x12 x13 x1j x1n
C21 C22 C23 C2j C2n
Sources / Origins

2 a2
x21 x22 x23 x2j x2n
Prepared by Ranbir Kalita
Supply

C31 C32 C33 C3j C3n

3 a3
x31 x32 x33 x3j x3n
Ci1 Ci2 Ci3 Cij Cin
i ai
xi1 xi2 xi3 xij xin
Cm1 Cm2 Cm3 Cmj Cmn
m am
xm1 xm2 xm3 xmj xmn
b1 b2 b3 bj bn
Demand

Page - 39
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Some Basic Definitions

• Feasible Solution: It is a set of non-negative allocations (xij) that satisfies the row and
column restrictions.

Prepared by Ranbir Kalita

• Basic Feasible Solution: A feasible solution is said to be a basic feasible solution if it
contains no more than (m + n – 1) non-negative allocations (xij), where m is the
number of rows and n is the number of columns in the transportation table.
▪ Non-degenerate Basic Feasible Solution: A basic feasible solution to a
(m × n) transportation problem is said to be non-degenerate if:
✓ The total number of non-negative allocations (xij) is exactly equal to
(m + n – 1), and
✓ These (m + n – 1) allocations are in independent positions.
▪ Degenerate Basic Feasible Solution: A basic feasible solution in which the
total number of non-negative allocations (xij) is less than (m + n – 1) is called a

Prepared by Ranbir Kalita

degenerate basic feasible solution.
• Optimal Solution: A feasible solution that minimizes (maximizes) the transportation
cost (profit) is called an optimal solution.

Solution of a Transportation Model

We will study the following FIVE methods to solve a transportation model:

(1) North-West Corner method (NWCM)

(2) Row Minima method
(3) Column Minima method
(4) Least-Cost method (or Matrix Minima method / Lowest Cost Entry method)
Prepared by Ranbir Kalita

(5) Vogel’s Approximation method (VAM) / Penalty method / Regret method

Page - 40
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Problem 3.6:

A dairy firm has three plants located in a state. Daily milk production at each plant is as
follows:

Prepared by Ranbir Kalita

Plant 1: 6 million litres Plant 2: 1 million litres Plant 3: 10 million litres

Each day, the firm must fulfil the needs of its four distribution centres. Milk requirement at
each centre is as follows:

Distribution Centre 1: 7 million litres Distribution Centre 3: 3 million litres

Distribution Centre 2: 5 million litres Distribution Centre 4: 2 million litres

Cost of shipping one million litres of milk from each plant to each distribution centre is given
in the following table in hundreds of rupees:
Distribution Centres

Prepared by Ranbir Kalita

1 2 3 4
1 2 3 11 7
Plants 2 1 0 6 1
3 5 8 15 9

The dairy firm wishes to determine as to how much should be shipped from which milk plant
to which distribution centre so that the total cost of shipment is the minimum. Determine the
initial basic feasible solution to the problem.

Solution:

Stept-1: Make the transportation table with the help of the given data in the question.

Destination
Prepared by Ranbir Kalita

1 2 3 4 Supply
1 2 3 11 7 6
Source 2 1 0 6 1 1
3 5 8 15 9 10
Demand 7 5 3 2

Step-2: Check whether the given problem is a Balanced Transportation Problem or not; i.e.
whether the total supply and demand are equal or not.

Page - 41
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Destination
1 2 3 4 Supply
1 2 3 11 7 6
Source 2 1 0 6 1 1

Prepared by Ranbir Kalita

3 5 8 15 9 10
Demand 7 5 3 2 17 (total)

Total supply = 6 + 1 + 10 = 17 Total Demand = 7 + 5 + 3 + 2 = 17

Since the problem is balances, therefore, there is no requirement of dummy row or column
and now the problem can be solved.

Step-3: Find a Basic Feasible Solution

(1) North-West Corner Method

Prepared by Ranbir Kalita

Destination
1 2 3 4 Supply
2 3 11 7
1 6/0
(6)
1 0 6 1
Source 2 1/0
(1)
5 8 15 9
3 10/5/2/0
(5) (3) (2)
Demand 7/1/0 5/0 3/0 2/0

Start from the North-West corner (upper left corner) of the transportation table and proceed
row-wise. Let, S1, S2, S3 are the Sources 1, 2 & 3 respectively. Similarly, D1, D2, D3, D4
are the Destinations 1, 2, 3 & 4 respectively.
Prepared by Ranbir Kalita

Row S1

D1 has a demand of 7 units and S1 can supply 6 units. Therefore, ship 6 units from S1
to D1, shown as (6). After shipping 6 units to D1, S1 does not have any units left and it
is indicated as 6/0. After receiving 6 units from S1, D1 still needs 1 more unit and it is
indicated as 7/1.

Page - 42
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Row S2

D1 still require 1 unit and S2 can ship 1 unit to D1. Therefore, 1 unit has been shipped
from S2 to D1. S1 is now empty, indicated as 1/0. Requirement of D1 is now fulfilled,

Prepared by Ranbir Kalita

indicated as 7/1/0.

Row S3

S3 has total 10 units. Ship 5 units to D2, 3 units to D3 and remaining 2 units to D4. S3
is now empty, indicated as 10/5/2/0. This means,

• After shipping 5 units to D2, S3 is left with 5 units (10/5).

• After shipping 3 units to D3, S3 is left with 2 units (10/5/2).
• After shipping 2 units to D4, S3 is now empty (10/5/2/0).

Again, the demands of D2, D3 and D4 have been fulfilled and are indicated

Prepared by Ranbir Kalita

respectively as 5/0, 3/0 and 2/0.

NOTE: Total units shipped from a source to any destination can never be more than the
requirement of that destination.

The initial basic feasible solution is:

x11 = 6 ; x21 = 1 ; x32 = 5 ; x33 = 3 ; x34 = 2

Calculation of Total Transportation Cost

6 units have been shipped from S1 to D1. This means [6×unit transportation cost] =
[6×2] = 12.

Similarly,
Prepared by Ranbir Kalita

Z = Rs. [(6×2) + (1×1) + (8×5) + (15×3) + (9×2)] × 100 => Z = Rs. 11,600

Page - 43
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

(2) Row Minima Method

Destination
1 2 3 4 Supply

Prepared by Ranbir Kalita

2 3 11 7
1 6/0
(6)
1 0 6 1
Source 2 1/0
(1)
5 8 15 9
3 10/9/5/3/0
(1) (4) (3) (2)
Demand 7/1/0 5/4/0 3/0 2/0
The start is to be made from the first row (upper most). Allocate maximum possible units to
the least cost cell in the first row so that either the capacity of the first Source (S1) is
exhausted or the requirement of the j-th destination (Dj) is fulfilled.

Three cases may arise:

Prepared by Ranbir Kalita

• If the capacity of S1 is completely exhausted, cross off (---) the S1 row and proceed to
the S2 row.
• If the requirement of the j-th Destination is completely fulfilled and S1 still has
leftover units, then cross off the j-th Column and reconsider the S1 row with
remaining capacity.
• If the capacity of the S1 is completely exhausted as well as requirement of the j-th
Destination is completely fulfilled, then cross off the S1 row and j-th column. Move
down to the second row and consider the remaining columns.

Continue this process until the requirement of all the destinations is completely fulfilled.

In reference to the given transportation table:

Prepared by Ranbir Kalita

• S1 row has minimum cost at call (1, 1). Therefore, 6 units has been shipped from S1
to D1 since supply unit 6 < demand unit 7. Now S1 is completely exhausted and
therefore cross off the S1 row and move down to the S2 row. D1 still require 1 more
unit.
• S2 row has minimum cost at cell (2, 2). Therefore, 1 unit from S2 has been shipped to
D2 since supply unit 1 < demand unit 5. Now S2 is completely exhausted and
therefore cross off the S2 row and move down to the S3 row. D2 still require 4 units.

Page - 44
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

• S3 has minimum cost at cell (1, 1). Therefore, 1 unit has been shipped from S3 to D1
which completely fulfils the requirement of D1, and as such cross of D1. S3 still has 9
units left. Again, looking at the least cost cells of S3 row, 4 units have been shipped to
D2, 2 units to D4 and 3 units to D3 respectively.

Prepared by Ranbir Kalita

The initial basic feasible solution is:

x11 = 6 ; x22 = 1 ; x31 = 1 ; x32 = 4 ; x32 = 3 ; x34 = 2

And, the total transportation cost is:

Z = Rs. [(6×2) + (1×0) + (1×5) + (4×8) + (3×15) + (2×9)] × 100 => Z = Rs. 11,200

It is to be noted that, Total Transportation Cost obtained from Row Minima method is less
than that obtained from North-West Corner method.

(3) Column Minima Method

Prepared by Ranbir Kalita

Destination
1 2 3 4 Supply
2 3 11 7
1 6/0
(6)
1 0 6 1
Source 2 1/0
(1)
5 8 15 9
3 10/5/2/0
(5) (3) (2)
Demand 7/6/0 5/0 3/0 2/0
The start is to be made from the first column (left most). Allocate maximum possible units to
the least cost cell in the first column so that either the requirement of the first Destination
(D1) is completely fulfilled or the capacity of the i-th Source (Sj) is completely exhausted.
Prepared by Ranbir Kalita

Three cases may arise:

• If the requirement of D1 is completely satisfied, cross off (---) the D1 column and
proceed to D2 column.
• If the capacity of the i-th Source is completely exhausted and D1 still require more
units, then cross off the i-th Row and reconsider D1 column with remaining
requirements.

Page - 45
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

• If the requirement of D1 is completely fulfilled as well as the capacity of the i-th

Source is completely exhausted, then cross off D1 column and the i-th row. Move
right to the second column and consider the remaining rows.

Prepared by Ranbir Kalita

Continue this process until the requirement of all the destinations is completely fulfilled.

In reference to the given transportation table:

• D1 has minimum cost at cell (2, 1). Therefore, 1 unit has been shipped from S2 to D1.
Now S2 is completely exhausted. Therefore, cross off S2 and reconsider D1 with the
remaining requirement of 6 units.
• Among the remaining rows S1 and S3, D1 column has minimum cost at cell (1, 1).
Therefore, 6 units have been shipped from S1 to D1. Now S1 is completely exhausted
requirement of D1 is completely fulfilled. Therefore, cross off D1 and S1 both and
move to D2 column.
•

Prepared by Ranbir Kalita

D2, D3 and D4 have only one cell left each in the S3 row. As such 5 units, 3 unit and
2 units have been shipped from S3 to D2, D3 and D4 respectively.

The initial basic feasible solution is:

x11 = 6 ; x21 = 1 ; x32 = 5 ; x33 = 3 ; x34 = 2

Therefore, the total transportation cost is:

Z = Rs. [(6×2) + (1×1) + (5×8) + (3×15) + (2×9)] × 100 => Z = Rs. 11,600

It is to be noted that, Total Transportation Cost obtained from Column Minima method is the
same as that obtained from North-West Corner method. Prepared by Ranbir Kalita

Page - 46
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

(4) Least Cost Method (Matrix Minima method / Lowest Cost Entry
method)
Destination

Prepared by Ranbir Kalita

1 2 3 4 Supply
2 3 11 7
1 6/0
(6)
1 0 6 1
Source 2 1/0
(1)
5 8 15 9
3 10/9/5/3/0
(1) (4) (3) (2)
Demand 7/1/0 5/4/0 3/0 2/0
In this method, the cell containing the lowest cost in the whole transportation matrix is
selected and maximum possible units are allocated to that cell; and then further allocations
are made in the cell with the second lowest cost and so on. In case of tie among the cost,
select the cell in which maximum allocation can be made.

Prepared by Ranbir Kalita

In reference to the given transportation table:

• Cell (2, 2) has the least cost. Therefore, 1 unit has been shipped from S2 to D2. Now,
S2 is completely exhausted and hence crossed off.
• From the remaining rows, i.e. S1 and S3, cell (1, 1) has the least cost. Therefore, 6
units have been shipped from S1 to D1. Now S1 is completely exhausted and hence
crossed off. D1 still require 1 more unit.
• Now, the only remaining row is S3. Therefore, 1 unit, 4 units, 2 units and 3 units have
been shipped to cell (3, 1) , (3, 2) , (3, 4) and (3, 3) respectively.

The initial basic feasible solution is:

x11 = 6 ; x22 = 1 ; x31 = 1 ; x32 = 4 ; x32 = 3 ; x34 = 2

Prepared by Ranbir Kalita

Therefore, the total transportation cost is:

Z = Rs. [(6×2) + (1×0) + (1×5) + (4×8) + (3×15) + (2×9)] × 100 => Z = Rs. 11,200

It is to be noted that, Total Transportation Cost obtained from Least Cost method is equal to
that obtained from the Row Minima method but less than that obtained from the North-West
Corner method.

Page - 47
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Problem 3.6:

A dairy firm has three plants located in a state. Daily milk production at each plant is as
follows:

Prepared by Ranbir Kalita

Plant 1: 6 million litres Plant 2: 1 million litres Plant 3: 10 million litres

Each day, the firm must fulfil the needs of its four distribution centres. Milk requirement at
each centre is as follows:

Distribution Centre 1: 7 million litres Distribution Centre 3: 3 million litres

Distribution Centre 2: 5 million litres Distribution Centre 4: 2 million litres

Cost of shipping one million litres of milk from each plant to each distribution centre is given
in the following table in hundreds of rupees:
Distribution Centres

Prepared by Ranbir Kalita

1 2 3 4
1 2 3 11 7
Plants 2 1 0 6 1
3 5 8 15 9

The dairy firm wishes to determine as to how much should be shipped from which milk plant
to which distribution centre so that the total cost of shipment is the minimum. Determine the
initial basic feasible solution to the problem.

Solution:

Stept-1: Make the transportation table with the help of the given data in the question.

Destination
Prepared by Ranbir Kalita

1 2 3 4 Supply
1 2 3 11 7 6
Source 2 1 0 6 1 1
3 5 8 15 9 10
Demand 7 5 3 2

Step-2: Check whether the given problem is a Balanced Transportation Problem or not; i.e.
whether the total supply and demand are equal or not.

Page - 48
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Destination
1 2 3 4 Supply
1 2 3 11 7 6
Source 2 1 0 6 1 1

Prepared by Ranbir Kalita

3 5 8 15 9 10
Demand 7 5 3 2 17 (total)

Total supply = 6 + 1 + 10 = 17 Total Demand = 7 + 5 + 3 + 2 = 17

Since the problem is balances, therefore, there is no requirement of dummy row or column
and now the problem can be solved.

Step-3: Find a Basic Feasible Solution

(5) Vogel’s Approximation Method (VAM) (Penalty Method / Regret

Method)

Prepared by Ranbir Kalita

VAM is a heuristic method and is preferred over the other four methods already
described. Here, the allocations are made looking at the Higher Opportunity Cost / Penalty.

In a transportation matrix, if an allocation is made to a cell containing the second

lowest cost instead of the lowest cost cell, then the difference between these two costs is the
Opportunity Cost or the Penalty for that allocation. This difference is called as the
Opportunity Cost because we have lost the opportunity to take advantage of allocating in the
least cost cell. This is also thought of as the Penalty associated with the allocation made in the
second lowest cost cell instead of the lowest cost cell; i.e. this difference indicates the unit
penalty incurred by failing to make an allocation to the smallest cost cell within a particular
row or column.
Prepared by Ranbir Kalita

• The start is made by calculating the Opportunity Costs for each row and column and
indicated within “[ ]” against the respective row and column.
• The row or column containing the highest Opportunity Cost is selected and maximum
possible allocation is made to the least cost cell of the selected row or column.
• Cross off the row or column which is completely satisfied and re-construct the
transportation table again eliminating the crossed off row or column. Re-calculate the

Page - 49
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Opportunity Cost again and select the row or column having the highest Opportunity
Cost.
▪ In case of tie among highest Penalties, select the row or column having the
Minimum Cost cell.

Prepared by Ranbir Kalita

▪ In case of tie among the Minimum Cost also, select the cell which can have
Maximum Allocations.
▪ In case of tie among Maximum Allocation Cells also, select any one arbitrarily
for allocation.

In reference to the given transportation problem:

Destination
1 2 3 4 Supply
2 3 11 7
1 6 [1]

Prepared by Ranbir Kalita

1 0 6 1
Source 2 1/0 [1]
(1)
5 8 15 9
3 10 [3]
7 5 3 2/1
Demand
[1] [3] [5] [6]
The Penalties are calculated for each row and column and indicated in “[ ]” against the
respective rows and columns as shown in the above table.

• Since D4 has the highest Penalty, therefore, D4 column is selected. Cell (2, 4) has the
least cost in D4 column; hence, 1 unit has been shipped from S2 to D4. Now S2 is
completely exhausted and hence crossed off.
• The allocation table is re-constructed, without the S2 row and the Penalties are
Prepared by Ranbir Kalita

calculated again.

Page - 50
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Destination
1 2 3 4 Supply
2 3 11 7
1 6/1 [1]
(5)

Prepared by Ranbir Kalita

Source
5 8 15 9
3 10 [3]
7 5/0 3 1
Demand
[3] [5] [4] [2]
• Since D2 has the highest Penalty, therefore, D2 column is selected. Cell (1, 2) has the
least cost in D2 column; hence, 5 units have been shipped from S1 to D2. Now S1 has
1 unit left and requirement of D2 is fulfilled. As such D2 is crossed off.
• The allocation table is re-constructed, without D2 column and the Penalties are
calculated again.

Prepared by Ranbir Kalita

Destination
1 3 4 Supply
2 11 7
1 1/0 [5]
(1)
Source
5 15 9
3 10 [4]
7/6 3 1
Demand
[3] [4] [2]
• Since S1 has the highest Penalty, therefore, S1 row is selected. Cell (1, 1) has the least
cost in S1 row; hence, 1 unit has been shipped from S1 to D1. Now S1 is completely
exhausted and D1 still require 6 more units to fulfil its requirements. As such S1 is
crossed off.
• The allocation table is re-constructed, without S1 row and the Penalties are calculated
Prepared by Ranbir Kalita

again

Page - 51
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Destination
1 3 4 Supply
5 15 9
Source 3 10/4/3/0 [4]
(6) (3) (1)

Prepared by Ranbir Kalita

6/0 3/0 1/0
Demand
[5] [15] [9]
6 units, 1 unit and 3 units have been shipped from S3 to D1, D4 and D3 respectively.

The following allocation matrix shows all the allocations made in the above steps:

Destination
1 2 3 4 Supply
2 3 11 7
1 6/1/0
(1) (5)
1 0 6 1
Source 2 1/0
(1)

Prepared by Ranbir Kalita

5 8 15 9
3 10/4/3/0
(6) (3) (1)
Demand 7/6/0 5/0 3/0 2/1/0
The initial basic feasible solution is:
x11 = 1 ; x12 = 5 ; x24 = 1 ; x31 = 6 ; x33 = 3 ; x34 = 1
Therefore, the total transportation cost is:
Z = Rs. [(1×2) + (3×5) + (1×1) + (6×5) + (3×15) + (1×9)] × 100 => Z = Rs. 10,200
Instead of solving the problem by reconstructing the allocation matrix repeatedly in steps, the
calculations can be made in a single table as shown below:

Destination
1 2 3 4 Supply
2 3 11 7
1 6/1/0 [1][1][5]
Prepared by Ranbir Kalita

(1) (5)
1 0 6 1
Source 2 1/0 [1]
(1)
5 8 15 9
3 10/4/3/0 [3][3][4]
(6) (3) (1)
7/6/0 5/0 3/0 2/1/0
[1] [3] [5] [6]
Demand
[3] [5] [4] [2]
[3] [4] [2]

Page - 52
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

It is to be noted that, the Total Transportation Cost found using VAM is the least among all
the costs calculated using the previous four methods. Hence, VAM gives the most
economical Initial Basic Feasible Solution.

Prepared by Ranbir Kalita

NOTE: The solutions obtained using all the above discussed methods are the Initial Basic
Feasible Solutions only. It may not be Optimal. The next step is to perform optimality test on
the obtained solution and if not optimal, we need to move iteratively towards the optimal
solution.

Un-balanced Transportation Problem

In a transportation problem, if total availability at all the origins is not equal to the total
demand from all the destinations, i.e. when ∑𝑚 𝑛
𝑖=1 𝑎𝑖 ≠ ∑𝑗=1 𝑏𝑗 , such problems are called

Unbalanced Transportation Problems. In these problems, either some available resources

Prepared by Ranbir Kalita

remain unused or some requirements remain unfulfilled.

But, to find a feasible solution to the given transportation problem, it must be a

balanced one, i.e. total supply must be equal to demand.

• If total supply capacity > total demand and no cost is associated with the failure to use
the excess capacity, we add a Dummy (fictitious) destination (column) to take up the
excess capacity with ZERO Shipping Cost to these dummy destinations.
• If total demand > total supply capacity, we add a Dummy source (row) to fill the
balance requirement with ZERO Shipping cost from these dummy sources.

Prepared by Ranbir Kalita

Page - 53
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Problem 3.7:

A product is produced by four factories A, B, C and D. The unit production cost in them are
Rs. 2, 3, 1 & 5 respectively. Their production capacities are: factory A – 50 units, B – 70

Prepared by Ranbir Kalita

units, C – 30 units and D – 50 units. These factories supply the products to four stores,
demand of which are 25, 35, 105 and 20 units respectively. Unit transportation cost in rupees
from each factory to each store is given in the table below:

Stores
1 2 3 4
A 2 4 6 11
B 10 8 7 5
Factories
C 13 3 9 12
D 4 6 8 3

Find out the basic feasible solution to determine the extent of deliveries from each of the

Prepared by Ranbir Kalita

factories to each of the stores so that the total production and transportation cost is minimum.

Solution: Unit production cost for each of the factories is added to the given unit
transportation cost and the following table is constructed.

Stores
1 2 3 4 Supply
A 2+2 4+2 6+2 11+2 50
B 10+3 8+3 7+3 5+3 70
Factories
C 13+1 3+1 9+1 12+1 30
D 4+5 6+5 8+5 3+5 50
Demand 25 35 105 20

Therefore, the cost matrix becomes:

Prepared by Ranbir Kalita

Stores
1 2 3 4 Supply
A 4 6 8 13 50
B 13 11 10 8 70
Factories
C 14 4 10 13 30
D 9 11 13 8 50
Demand 25 35 105 20

Page - 54
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

From the above table,

Total production capacity (supply) = 50 + 70 + 30 + 50 = 200 units
Total demand = 25 + 35 + 105 + 20 = 185 units
Therefore, Surplus supply capacity = (200 – 185) = 15 units.

Prepared by Ranbir Kalita

Since, Production capacity > Total demand, hence, this is an unbalanced Transportation
Problem. To balance it, add one dummy destination (column d) with 15 units demand and
ZERO cost coefficients.

The final cost matrix is:

Stores
1 2 3 4 d Supply
A 4 6 8 13 0 50
B 13 11 10 8 0 70
Factories
C 14 4 10 13 0 30

Prepared by Ranbir Kalita

D 9 11 13 8 0 50
Demand 25 35 105 20 15
We will use the VAM to find out the Basic Feasible Solution:
Stores
1 2 3 4 d Supply
4 6 8 13 0
A 50/25/20/0 [4][2][2][2][5]
(25) (5) (20)
13 11 10 8 0
B 70/55/0 [8][2][2][2][2][2]
(55) (15)
Factories
14 4 10 13 0
C 30/0 [4][6]
(30)
9 11 13 8 0
D 50/30/0 [8][1][1][3][5][5]
Prepared by Ranbir Kalita

(30) (20)
Demand 25/0 35/5/0 105/85/30/0 20/0 15/0
[5] [2] [2] [5] [0]
[5] [2] [2] [5]
[5] [5] [2] [5]
[5] [2] [5]
[2] [5]
[3] [0]

• Penalty costs have been calculated. Row-B & D has the same highest penalty cost of
[8] and same minimum cost cell value of (0). The maximum number of units that can
Page - 55
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

be shipped to these two minimum cost cells is also the same. Therefore, Row-B has
been selected at random and 15 units have been shipped from Factory-B to Store-d.
Requirement of Store-d is now fulfilled and can be crossed off.
• Penalty costs have been calculated again. Row-C has the highest penalty cost of [6]

Prepared by Ranbir Kalita

and cell (C, 2) is the minimum cost cell in that row. Therefore, 30 units have been
shipped from Factory-C to Store-2. Factory-C is now empty and hence, Row-C can be
crossed off.
• Penalty costs have been calculated again. Columns-1, 2 & 4 has the same highest
penalty cost of [5]. But, Column-1 has the least value of the minimum cost cell
corresponding to cell (A, 1). Therefore, 25 units have been shipped from Factory-A to
Store-1. Requirement of Store-1 is now fulfilled and hence can be crossed off.
• Penalty costs have been calculated again. Clumns-2 & 4 has the same highest penalty
cost of [5]. But, Column-2 has the least value of the minimum cost cell corresponding
to cell (A, 2). Therefore, 5 units have been shipped from Factory-A to Store-2.

Prepared by Ranbir Kalita

Requirement of Store-2 is now fulfilled and hence can be crossed off.
• Penalty costs have been calculated again. Rows-A & D and Column-4 has the same
highest penalty cost of [5] and minimum cost cell value in both the rows and the
column is also the same, which is (8). Also, the maximum number of units that can be
shipped in the minimum cost cell is also the same in both the rows and the column,
which is 20 units. Therefore, we can select any row or column at random. Row-A has
been selected because, after shipping 20 units from Factory-A to Store-3, Factory-A
becomes empty and as such Row-A can be crossed off.
• Penalty costs have been calculated again. Row-D has the highest penalty cost of [5].
Therefore, 20 units have been shipped from Factory-D to Store-4. Requirement of
Store-4 is now fulfilled and hence can be crossed off.
• Now, 55 units have been shipped from Factory-B to Store-3 and 30 units have been
Prepared by Ranbir Kalita

shipped from Factory-D to Store-3. This completes the allotment process.

The initial basic feasible solution is:

x11 = 25 ; x12 = 5 ; x13 = 20 ; x23 = 55 ; x25 = 15 ; x32 = 30 ; x43 = 30 ; x44 = 20
And, the total transportation cost is:
Z = [(4×25) + (6×5) + (8×20) + (10×55) + (0×15) + (4×30) + (13×30) + (8×20)]

=> Z = [100 + 30 + 160 + 550 + 0 + 120 + 390 + 160] => Z = 1510

Page - 56
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

References
[1] Prem Kumar Gupta and D. S. Hira (2014), Operations Research (7th revised edition),
S. Chand, ISBN: 81-219-0281-9, Chapter 3, pp. 248-286.

Prepared by Ranbir Kalita

Prepared by Ranbir Kalita
Prepared by Ranbir Kalita

Page - 57
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Problem 3.8:
Consider the following unbalanced transportation problem:
To
1 2 3 Supply

Prepared by Ranbir Kalita

1 5 1 7 10
From 2 6 4 6 80
3 3 2 5 15
Demand 75 20 50

Since, there is not enough supply, some of the demands at these destinations may not be
satisfied. Suppose there are penalty costs for every unsatisfied demand unit which are given
by 5, 3 and 2 for destinations 1, 2, and 3 respectively. Find the initial basic feasible solution
to the given transportation problem.

Solution: In the given problem,

Total Supply = 105 units

Prepared by Ranbir Kalita

Total Demand = 145 units
Slack = 40 units
Since, supply is < demand, therefore, add one dummy source which can supply 40 units. As
given in the question, unit transportation cost from this dummy source (d) to destinations 1, 2
& 3 are 5, 3 & 2 respectively. The modified transportation table is shown below:

The problem is solved using VAM.

To
1 2 3 Supply
1 5 1 7 10
From 2 6 4 6 80
3 3 2 5 15
d 5 3 2 40
Prepared by Ranbir Kalita

Demand 75 20 50

Page - 58
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

1 2 3 Supply
5 1 7
1 10/0 [4]
(10)
6 4 6
2 80/70/10/0 [2][2][2]

Prepared by Ranbir Kalita

(60) (10) (10)
From
3 2 5
3 15/0 [1][1][1]
(15)
5 3 2
d 40/0 [1][1]
(40)
75/60/0 20/10/0 50/10/0
[2] [1] [3]
Demand
[2] [1] [3]
[3] [2] [1]

• Source-1 has the highest Penalty and Cell (1, 2) has the least unit transportation cost
in that row. As such, 10 units have been shipped from source-1 to destination-2.
• Destination-3 has the highest Penalty and Cell (d, 3) has the least unit transportation

Prepared by Ranbir Kalita

cost in that column. As such, 40 units have been shipped from source-d to destination-
3.
• Destination-1 has the highest Penalty and Cell (3, 1) has the least unit transportation
cost in that column. As such, 15 units have been shipped from source-3 to destination-
1.
• Now, only row-2 is left. Therefore, 10 units, 60 units and 10 units have been shipped
from source-2 to destinations-2, 1 & 3 respectively.

The initial basic feasible solution is:

x12 = 10 ; x21 = 60 ; x22 = 10 ; x23 = 10 ; x31 = 15 ; x43 = 40

And, the total transportation cost is,

Prepared by Ranbir Kalita

Z = Rs. [(1×10) + (6×60) + (4×10) + (6×10) + (3×15) + (2×40)]

=> Z = Rs. [10 + 360 + 40 + 60 + 45 + 80] => Z = Rs. 595

Page - 59
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

Problem 3.9:

Find an initial basic feasible solution to the following T.P. using Vogel’s approximation
method:

Prepared by Ranbir Kalita

Destination
1 2 3 4 Availability
A 7 2 5 5 30
B 4 4 6 5 15
Origin
C 5 3 3 2 10
D 4 –1 4 2 20
Requirement 20 25 15 15

Solution:

Here, Total Availability = Total Requirement = 75 units. Therefore, it is a Balanced

Transportation Problem.

Prepared by Ranbir Kalita

Destination
1 2 3 4 Availability
7 2 5 5
A 30/25/20/5/0 [3][3][3][2]
(5) (5) (15) (5)
4 4 6 5
B 15/0 [1][1][1][1]
(15)
Origin
5 3 3 2
C 10/0 [1][1]
(10)
4 –1 4 2
D 20/0 [3]
(20)
20/5/0 25/5/0 15/0 15/5/0
[1] [3] [1] [3]
Requirement [1] [1] [2] [3]
[3] [2] [1] [0]
[3] [1] [0]
Prepared by Ranbir Kalita

• Penalty costs have been calculated. Rows-A&D and Column-2&4 have the same
penalty cost of [3]. But, Row-D and Column-2 has the same minimum cost cell
having minimum cost of (–1). Therefore, Row-D has been selected arbitrarily and 20
units have been shipped from D to Destination-2. Now, Origin-D is empty and can be
crossed off.
• Penalty costs have been calculated again. Row-A and Column-4 has the same
maximum penalty cost of [3]. The value of the minimum cost cell is also (2) in both

Page - 60
Mechanical Engineering Department Jorhat Engineering College
 OR : Module-3

of them. But, if we select column-4, then more number of units could be shipped to
cell (C, 4) than that of (A, 2) if Row-A had been selected. Therefore, Column-4 has
been selected and 10 units have been shipped from C to Destination-4. Origin-C is
now empty and can be crossed off.

Prepared by Ranbir Kalita

• Penalty costs have been calculated again. Row-A and Column-1 has the same
maximum penalty cost of [3]. But, since the minimum cell cost value of Row-A is <
Column-1, therefore, Row-A has been selected and 5 units have been shipped from A
to Destination-2. Requirement of Destination is now fulfilled and can be crossed off.
• Penalty costs have been calculated again. Column-1 has the maximum penalty cost of
[3]. Therefore, 15 units have been shipped from B to Destination-1. Origin-B is now
empty and can be crossed off.
• Now, 5 units, 15 units and 5 units have been shipped from A to Destinations-1, 3 & 4
respectively. This completes the allocation process.

Prepared by Ranbir Kalita

The initial basic feasible solution is:

x11 = 5 ; x12 = 5 ; x13 = 15 ; x14 = 5 ; x21 = 15 ; x34 = 10 ; x42 = 20

And, the total transportation cost is:

Z = [(7×5) + (2×5) + (5×15) + (5×5) + (4×15) + (2×10) + (– 1×20)]

=> Z = [35 + 10 + 75 + 25 + 60 + 20 – 20] => Z = 205

Prepared by Ranbir Kalita

References

[1] Prem Kumar Gupta and D. S. Hira (2014), Operations Research (7th revised edition),
S. Chand, ISBN: 81-219-0281-9, Chapter 3, pp. 248-286.

Page - 61
Mechanical Engineering Department Jorhat Engineering College