Operations Research

Unit 2
• Assignment based Problem- Hungarian Method
• Transportation Based Problem:

Assignment Problem
Assignment – one to one Allocation
In Assignment Problem, We allocate resources to activities on one
to one basis.
Hungarian Method is used to solve AP

1. In a Plant, 4 employees are to be assigned 4 jobs on one to one

basis. The Cost (in Rs Thousands) for each employee to do each
job is given below:
Cost Matrix (in Rs Thousands)
Employee / Job P Q R S
A 60 50 40 45
B 40 45 55 30
C 55 70 60 50
D 45 45 40 45

Find the optimal assignment of employees and jobs to minimize the

total cost.
Step 1: Check If problem is balanced or unbalanced.
If no of Resources = No of Activities , it is balanced type problem.
If no of Rows = No of Columns it is balanced type problem.
It is balanced type problem, since No of employees = No of Jobs
Step 2: Check if problem is minimization type or maximization type
It is Minimization Type Problem
Employee / Job P Q R S
A 60 50 40 45
B 40 45 55 30
C 55 70 60 50
D 45 45 40 45

Step 3: Check if problem is Prohibited type or Unprohibited type

It is Unprohibited type Problem

Step 4: Row Minimization – Minimize or Reduce the given Cost

matrix Row wise.

Employee / Job P Q R S
A 20 10 0 5
B 10 15 25 0
C 5 20 10 0
D 5 5 0 5

Step 5: Column Minimization – Minimize or Reduce the given

Cost matrix Column wise.
Employee / Job P Q R S
A 15 5 0 5
B 5 10 25 0
C 0 15 10 0
D 0 0 0 5
Step 6: Test of Optimality
Employee / Job P Q R S
A 15 5 0 5
B 5 10 25 0
C 0 15 10 0
D 0 0 0 5

It is an optimal solution, since minimum number of lines drawn = Size of

the matrix = 4
Step 7: Assignment
Employee / Job P Q R S
A 15 5 0 5
B 5 10 25 0
C 0 15 10 0
D 0 0 0 5

Step 8: Assignment Schedule

Employee Job Cost in Rs
A R 40
B S 30
C P 55
D Q 45
170
2. A Company has 4 Machines to do 3 Jobs. Each Job can be assigned to one
machine only. The cost of each Job- Machine is given in the table below:
Cost Matrix (in Rs Thousands)
Job / Machine I II III IV
A 9 12 14 18
B 4 6 8 9
C 5 7 9 11

Find an optimal Assignment of Job & Machine which will minimize the total
cost.

Solution
Step 1: It is not a balanced type problem, No. of rows (Jobs) are not equal to
No. of Columns (Machines)
Job / Machine I II III IV
A 9 12 14 18
B 4 6 8 9
C 5 7 9 11
Dummy D 0 0 0 0

Now It is a balanced type problem, No. of rows (Jobs) are equal to No. of
Columns (Machines)
Step 2: It is a minimization type problem
Step 3: Check Whether it is a prohibited type Problem or not
It is not a prohibited type problem
Step 4 : Row Minimization
Job / Machine I II III IV
A 0 3 5 9
B 0 2 4 5
C 0 2 4 6
Dummy D 0 0 0 0
Step 5 : Column Minimization
Job / Machine I II III IV
A 0 3 5 9
B 0 2 4 5
C 0 2 4 6
Dummy D 0 0 0 0

Step 6: Test of Optimality

Job / Machine I II III IV
A 0 3 5 9
B 0 2 4 5
C 0 2 4 6
Dummy D 0 0 0 0

Minimum No. of lines drawn = 2

Size of the Matrix = 4
Hence, It is not an optimal solution.
What to do if Solution is not optimal
• Find the least uncovered value
Least uncovered value = 2
• Subtract this least uncovered value from all the uncovered values
respectively
• Add this least uncovered value to the point of intersection of lines
• Keep all the other values as it is.
Modified Solution
Job / Machine I II III IV
A 0 1 3 7
B 0 0 2 3
C 0 0 2 4
Dummy D 2 0 0 0
Test of Optimality
Job / Machine I II III IV
A 0 1 3 7
B 0 0 2 3
C 0 0 2 4
Dummy D 2 0 0 0

Minimum No of lines drawn = 3

Size of the Matrix = 4
It is not an optimal Solution
What to do if Solution is not optimal
• Find the least uncovered value
Least uncovered value = 2
• Subtract this least uncovered value from all the uncovered values
respectively
• Add this least uncovered value to the point of intersection of lines
• Keep all the other values as it is.

Modified Solution
Job / Machine I II III IV
A 0 1 1 5
B 0 0 0 1
C 0 0 0 2
Dummy D 4 2 0 0

Optimality Test
Job / Machine I II III IV
A 0 1 1 5
B 0 0 0 1
C 0 0 0 2
Dummy D 4 2 0 0

Minimum No of lines drawn = 4

Size of the Matrix = 4
Hence it is an Optimal Solution
Step 7 : Assignment
Job / Machine I II III IV
A 0 1 1 5
B 0 0 0 1
C 0 0 0 2
Dummy D 4 2 0 0

Job / Machine I II III IV

A 0 1 1 5
B 0 0 0 1
C 0 0 0 2
Dummy D 4 2 0 0

Unique Optimal Solution Vs Multiple (Alternate) optimal Solution

Step 8 : Assignment Schedule
Job Machine Cost (in Rs Thousands)
A I 9
B II 6
C III 9
Dummy D IV 0
24

Job Machine Cost (in Rs Thousands)

A I 9
B III 8
C II 7
Dummy D IV 0
24
3. A Sales Manager has to assign salesman to four territories. He has four
salesman of varying experience and capabilities. The manager assesses the
possible sales for each salesman in each territory as given below:
Sales matrix (in Rs Lakhs)
Salesman /Territory T1 T2 T3 T4
S1 35 27 28 37
S2 28 34 29 40
S3 35 24 32 33
S4 24 32 25 28

Find the optimal assignment of salesman to the territories so that total sales is
maximum.
Step 1 : It is balanced type problem.
Step 2: It is unprohibited type problem
Step 3: It is Maximization Type Problem
Convert maximization type problem into Minimization type problem by
calculating Regret or Opportunity Loss / Opportunity cost Matrix.
Highest value (sales) from the given Table
Subtract all the respective values of respective cell from this highest value.
Regret or Opportunity cost Matrix
Salesman /Territory T1 T2 T3 T4
S1 5 13 12 3
S2 12 6 11 0
S3 5 16 8 7
S4 16 8 15 12

Step 4: Row Minimization

Regret or Opportunity cost Matrix
Salesman /Territory T1 T2 T3 T4
S1 2 10 9 0
S2 12 6 11 0
 S3 0 11 3 2
S4 8 0 7 4

Step 5: Column Minimization

Regret or Opportunity cost Matrix
Salesman /Territory T1 T2 T3 T4
S1 2 10 6 0
S2 12 6 8 0
S3 0 11 0 2
S4 8 0 4 4

Step 6: Optimality Test

Salesman /Territory T1 T2 T3 T4
S1 2 10 6 0
S2 12 6 8 0
S3 0 11 0 2
S4 8 0 4 4

Minimum number of lines drawn = 3

Size of the matrix = 4
It is not optimal solution
Modified Solution
Salesman /Territory T1 T2 T3 T4
S1 0 8 4 0
S2 10 4 6 0
S3 0 11 0 4
S4 8 0 4 6

Optimality Test
Salesman /Territory T1 T2 T3 T4
S1 0 8 4 0
S2 10 4 6 0
S3 0 11 0 4
S4 8 0 4 6
Minimum number of lines drawn = 4
Size of the matrix = 4
It is optimal solution
Step 7 : Assignment
Salesman / T1 T2 T3 T4
Territory
S1 0 8 4 0
S2 10 4 6 0
S3 0 11 0 4
S4 8 0 4 6

Step 8: Assignment Schedule

Salesman Territory Sales (in Rs Lakhs)
S1 T1 35
S2 T4 40
S3 T3 32
S4 T2 32
Total 139
4. The following is the cost matrix (Cost in Rs Thousands) of assigning 4
employees to 4 key Jobs. Employee 1 Cannot be assigned to Job 1:
Cost Matrix (in Rs Thousands)
Employee / Job J1 J2 J3 J4
1 - 5 2 0
2 4 7 5 6
3 5 8 4 3
4 3 6 6 2

Find an optimal Assignment of Employees to jobs to minimize the total cost.

Find the Alternate optimal Solution also
Step 1 : It is balanced type problem
Step 2 : It is minimization type problem
Step 3: It is Prohibited Type Problem.
The cost of Employee 1 doing job 1 is infinite and It is denoted by symbol
M.
Employee / Job J1 J2 J3 J4
1 M 5 2 0
2 4 7 5 6
3 5 8 4 3
4 3 6 6 2

Row Minimization

Employee / Job J1 J2 J3 J4
1 M 5 2 0
2 0 3 1 2
3 2 5 1 0
4 1 4 4 0
Column Minimization

Employee / Job J1 J2 J3 J4
1 M 2 1 0
2 0 0 0 2
3 2 2 0 0
4 1 1 3 0

Optimality Test
Employee / Job J1 J2 J3 J4
1 M 2 1 0
2 0 0 0 2
3 2 2 0 0
4 1 1 3 0

Modified Solution
Employee / Job J1 J2 J3 J4
1 M 1 0 0
2 0 0 0 3
3 2 2 0 1
4 0 0 2 0

Optimality Test
Employee / Job J1 J2 J3 J4
1 M 1 0 0
2 0 0 0 3
3 2 2 0 1
4 0 0 2 0

It is optimal Solution
Assignment and Assignment Schedule

Employee / Job J1 J2 J3 J4
1 M 1 0 0
2 0 0 0 3
3 2 2 0 1
4 0 0 2 0
Employee Job Cost (in Rs
Thousands)
1 J4 0
2 J1 or J2 4 or 7
3 J3 4
4 J2 or J1 6 or 3

RS 14000
5. The quantity of different products (in units) produced by the workers per day
are given in the following matrix along with profit in Rs per unit. Formulate a
profit matrix and find the optimal assignment of workers to product which will
maximise the profit.
Quantity of Products (in Units)
Workers / Quantity of Pencil Rubber Pen Ink
Products
Amit 30 40 100 50
Sumit 25 70 140 30
Vinit 40 90 130 60
Punit 35 45 120 40
Profit in Rs per unit 4 2 1 3

Profit Matrix = profit per unit * no of units

Workers / Quantity of Pencil Rubber Pen Ink
Products
Amit 120 80 100 150
Sumit 100 140 140 90
Vinit 160 180 130 180
Punit 140 90 120 120

It is a balanced type Problem.

It is unprohibited type problem
It is a maximization type problem. Convert it into minimization type
problem
Regret Matrix / Opportunity cost matrix
Workers / Quantity of Pencil Rubber Pen Ink
Products
Amit 60 100 80 30
Sumit 80 40 40 90
Vinit 20 0 50 0
Punit 40 90 60 60

Row Minimization
Workers / Quantity of Pencil Rubber Pen Ink
Products
Amit 30 70 50 0
Sumit 40 0 0 50
Vinit 20 0 50 0
Punit 0 50 20 20

Column Minimization
Workers / Quantity of Pencil Rubber Pen Ink
Products
Amit 30 70 50 0
Sumit 40 0 0 50
Vinit 20 0 50 0
Punit 0 50 20 20

Optimality Test
Workers / Quantity of Pencil Rubber Pen Ink
Products
Amit 30 70 50 0
Sumit 40 0 0 50
Vinit 20 0 50 0
Punit 0 50 20 20

Minimum no of lines drawn = 4

Size of the matrix = 4
Hence it is optimal solution

Assignment
Workers / Quantity of Pencil Rubber Pen Ink
Products
Amit 30 70 50 0
Sumit 40 0 0 50
Vinit 20 0 50 0
Punit 0 50 20 20

Assignment Schedule
Workers Type of Product Profit in Rs

Amit Ink 150

Sumit Pen 140
Vinit Rubber 180
Punit Pencil 140
Total Profit 610
 Transportation Problem
(1) Transportation Cost (in Rs)
Plant/Market Mum Nashik Lucknow Delhi Supply

Ahm 42 32 50 26 11

Bangalore 34 36 28 46 13

Calcutta 64 54 36 82 19

Demand 6 10 12 15 43\43

Objective :
To Find out how many units to be transported / supplied from respective
Supply centre to Demand centre in such a way that the total transportation
cost is minimum or least,
Structure of Transportation Problem:
• The number of supply centres are finite and known .
• The number of Demand centres are finite and known .
• The Supply capacity from each supply centre is constant for the given
problem
• The Supply capacity of each Demand centre is constant for the given
problem
• Cost of transporting goods from respective supply centre to respective
demand centre is constant for the given problem.

OR Techniques to Find IBFS of Transportation Problem:

• North West Corner rule (NWCR) Method
• Least Cost Method (LCM)
• Vogel’s Approximation Method (VAM)
Step 1: it is balanced type problem or Unbalanced type Problem
Check Total Supply and Total Demand
If Total Supply = Total Demand, then it is balanced type problem
Total Supply = 11 +13+19 = 43
Total Demand = 6 +10+12+15 = 43
It is a balanced type problem
Step 2: Check whether it is Minimization type problem or Maximization
type Problem
it is Minimization type problem
Step 3: Check whether it is Prohibited type problem or Unprohibited type
Problem
It is Unprohibited type Problem
Step 4 : Find Initial Feasible Solution (IFS) by applying respective method
IBFS by NWCR Method
Plant/Market M1 M2 M3 M4 Supply

F1 42 32 50 26 11 5
5
6

F2 34 36 28 46 13 8
5 8

F3 64 54 36 82 19 15
4 155
555
Demand 6 10 12 555 15 43\43
5 4 555
5
Transportation Schedule based on IFS of NWCR method:
Allocation Cell Units Allocated TC/ Unit Total TC (in RS)

F1 - M1 6 42 252
F1- M2 5 32 160
F2-M2 5 36 180
F2 -M3 8 28 224
F3-M3 4 36 144
F3-M4 15 82 1230
2190

IFS by Least Cost Method:

Plant/Market M1 M2 M3 M4 Supply

F1 42 32 50 26 11
11

F2 34 36 28 46 13 1
1 12

F3 64 54 36 82 19 9 4
5 10 4

Demand 6 10 12 15 43\43
5 4

Transportation Schedule based on IFS of Least Cost Method:

Allocation Cell Units Allocated TC/ Unit Total TC (in RS)

F1- M4 11 26 286
F2 - M1 1 34 34
F2 – M3 12 28 336
F3- M1 5 64 320
F3- M2 10 54 540
F3- M4 4 82 328
1844
IFS by Vogel’s Approximation Method (VAM):
Row Wise Penalties
Plant/Market M1 M2 M3 M4 Supply P1 P2 P3 P4

F1 42 32 50 26 11 6
11

F2 34 36 28 46 13 9 3 6 6 6 8
6 3 4
F3 64 54 36 82 19 7 18 18 18 18
7 12
Demand 6 10 12 15 43\43
4
P1 8 4 8 20

P2 30 18 8 36

P3 30 18 8

P4 18 8

Row Penalty = Difference between two lowest costs for a Row

Column Penalty = Difference between two lowest costs for a Column

Transportation Schedule based on IFS of VAM:

Allocation Cell Units Allocated TC/ Unit Total TC (in RS)

F1- M4 11 26 286
F2 - M1 6 34 204
F2 – M2 3 36 108
F2- M4 4 46 184
F3- M2 7 54 378
F3- M3 12 36 432
1592

Before carrying out optimality, You should always check for Non –
Degeneracy Condition.
Condition for Non – Degeneracy, m+n-1 = No of allocations
Where m =no of rows and n= No of columns
m+n-1 = 3+4-1 = 6
No of allocations =6
There is no degeneracy

MODI (Modified Distribution) Method : To find an Optimal Solution

• We find check whether it is possible to reduce the present cost of solution
or not.
• If it is not possible to reduce cost further , then solution obtained is
optimal.
• If it is possible to reduce cost further, then solution obtained is not
optimal. We have to find new or Modified solution and have to check
again the optimality of modified solution. Keep repeating the procedure
until we get optimal solution.

Optimality Test:
V1=14 V2=16 V3 = -2 V4= 26
Plant/Market M1 M2 M3 M4 Supply
U1=0 F1 42 32 50 26 11
11
U2= 20 F2 34 36 28 46 13
6 3 4
U3 = 38 F3 64 54 36 82 19
7 12
Demand 6 10 12 15 43\43
For occupied cells , Cost ij = Ui+ Vj
occupied Cost Cost ij = Ui+ Vj
cells ij
F1- M4 26 26 = U1+V4 26 = 0+V4 V4 = 26
F2 - M1 34 34 = U2+V1 34 = 20+V1 V1 = 34-20=14
F2 – M2 36 36 = U2+V2 36 = 20+V2 V2 = 36-20 =16
F2- M4 46 46 = U2+V4 46 = U2+ 26 U2 = 46-26 = 20
F3- M2 54 54 = U3+V2 54 = U3+ 16 U3 = 54-16 =38
F3- M3 36 36 = U3 + V3 36 = 38 +V3 V3 = 36-38 = -2

We will calculate ∆( Delta) = Opportunity cost or Change in cost for an

unoccupied cell
∆ij = Cost ij – (Ui+ Vj) for Unoccupied Cell

Unoccupied ∆ij = Costij – (Ui+Vj) ∆ij

Cell

i j
F1 – M1 ∆11 = Cost 11 – (U1+V1) 42 – (0+14) =28
F1 – M2 ∆12 = Cost 12 – (U1+V2) 32 – (0+16) = 16
F1 – M3 ∆13 = Cost 13 – (U1+V3) 50 – (0-2) =52
F2 – M3 ∆23 = Cost 23 – (U2+V3) 28-(20-2) = 10
F3 – M1 ∆31 = Cost 31 – (U3+V1) 64 – (38+14) =12
F3– M4 ∆34 = Cost 34 – (U3+V4) 82 – (38+26) = 18

Since No ∆ value is negative . Hence this is an optimal Solution

Optimal Transportation Schedule
Plant Market Units Allocated( in Unit Cost in Rs Total Cost in
000’s) Rs(000’s)
F1 M4 11 26 286
F2 M1 6 34 204
F2 M2 3 36 108
F2 M4 4 46 184
 F3 M2 7 54 378
F3 M3 12 36 432
Rs 15,92,000

2
Find IFS by applying NWCR, LCM and VAM.
Step 1: it is not balanced.
Total Supply = 152+164+154 =470
Total Demand = 144+204+82 = 430

Plant/ Market M1 M2 M3 Supply

A 16 24 24 152
B 48 72 48 164
C 24 48 72 154
Demand 144 204 82
Plant/ M1 M2 M3 Dummy Supply
Market M4
A 16 24 24 0 152
B 48 72 48 0 164
C 24 48 72 0 154
Demand 144 204 82 40

It is balanced now.
Step 2 : it is minimization type problem
Step 3 : it is Unprohibited
Step 4 : IFS based on NWCR , LCM and VAM (any one)
IFS by NWCR
Plant/ M1 M2 M3 Dummy Supply
Market M4
A 16 24 24 0 152
144 8

B 48 72 48 0 164
42 82 40

C 24 48 72 0 154
154

Demand 144 204 82 40

IFS by LCM

Plant/ M1 M2 M3 Dummy Supply

Market M4
A 16 24 24 0 152 8
144 8

B 48 72 48 0 164
164

C 24 48 72 0 154
32 82 40

Demand 144 204 82 40

196
32

Plant/ M1 M2 M3 Dummy Supply

Market M4
IFS by VAM
Plant/ M1 M2 M3 Dummy Supply P1 P2 P3 P4 P5
Market M4
A 16 24 24 0 152 16 8 * * *
152

B 48 72 48 0 164 48 0 0 24
42 82 40
124

C 24 48 72 0 154 24 24 24 24
144 10

Demand 144 204 82 40

52

P1 8 24 24 0
P2 8 24 24 *
P3 24 24 24 *
P4 * 24 24 *
P5 * *
3.
IBFS of a Transportation Problem is given as below: Find the optimal
Transportation Cost

Plant/Market M1 M2 M3 M4 Supply

A 10 11 7 4 25

14
11
B 7 13 6 11 28

17
11
C 4 9 8 10 17

15 2

Demand 15 30 11 14 70/70

Check for Non – degeneracy

m+n-1 = 3+4-1 = 6
No of allocations =6
There is no degeneracy
Optimality Test

V1 = 6 V2 = 11 V3 = 4 V4 = 4

Plant/Market M1 M2 M3 M4 Supply

U1=0 A 10 11 7 4 25

14
11
U2=2 B 7 13 6 11 28

17
11
U3=-2 C 4 9 8 10 17

15 2

Demand 15 30 11 14 70/70

From Allocated cells, Ui +Vj =Cost ij

A-M2_____U1+V2 = 11______0 +V2=11
A-M4______ U1+V4 = 4______0+V4 = 4
B-M2________U2+V2 = 13_____U2+11=13
B-M3_______U2+V3 = 6________2+V3 =6
C-M1________U3+V1 = 4_______-2+V1=4
C-M2________U3+V2 = 9_______U3+11=9
Opportunity cost ∆ of Unallocated Cells: ∆ij = Cost ij – ( Ui +Vj)
It represents by how much will the cost change (increase or decrease) if 1
unit is transported to Unallocated / empty cell
Unallocated Cells ∆ij = Cost ij – ( Ui +Vj)
A-M1 10– (U1+V1) = 10 – (6) = 4
A-M3 7– (U1+V3) = 7 – (4) = 3
B – M1 7 – (U2+V1)= 7-(8) = -1
B-M4 11– (U2+V4) = 11 – (6) = 5
C-M3 8– (U3+V3) = 8 – (2) = 6
C-M4 10– (U3+V4) = 10 – (2) = 8

This is not an Optimal Solution, Since ∆ of B-M1 is negative.

Modified Solution / New Solution

Plant/Market M1 M2 M3 M4 Supply

A 10 11 7 4 25

14
11
B 7 13 6 11 28

15 2
11
C 4 9 8 10 17

17
Demand 15 30 11 14 70/70

Check for Non – degeneracy

m+n-1 = 3+4-1 = 6
No of allocations =6
There is no degeneracy
Optimality Test of Modified Solution / New Solution

V1 = 5 V2 = 11 V3 = 4 V4 = 4

Plant/Market M1 M2 M3 M4 Supply

U1=0 A 10 11 7 4 25

14
11
U2=2 B 7 13 6 11 28

15 2
11
U3=-2 C 4 9 8 10 17

17
Demand 15 30 11 14 70/70

From Allocated cells, Ui +Vj =Cost ij

A-M2_____U1+V2 = 11______0 +V2=11
A-M4______ U1+V4 = 4______0+V4 = 4
B-M1________U2+V1 = 7______2+V1=7
B-M2________U2+V2 = 13_____U2+11=13
B-M3_______U2+V3 = 6________2+V3 =6
C-M2________U3+V2 = 9_______U3+11=9
U1=0
U2=2
U3=-2

V1 = 5 V2 = 11 V3 = 4 V4 = 4
Opportunity cost ∆ of Unallocated Cells: ∆ij = Cost ij – ( Ui +Vj)
It represents by how much will the cost change (increase or decrease) if 1
unit is transported to Unallocated / empty cell
Unallocated Cells ∆ij = Cost ij – ( Ui +Vj)
A-M1 10– (U1+V1) = 10 – (5) = 5
A-M3 7– (U1+V3) = 7 – (4) = 3
B-M4 11– (U2+V4) = 11 – (6) = 5
C-M1 4– (U3+V1) = 4 – (3) = 1
C-M3 8– (U3+V3) = 8 – (2) = 6
C-M4 10– (U3+V4) = 10 – (2) = 8

This is an optimal Solution, Since there is no negative ∆.

4
Transportation Cost per unit (in Rupees)

Plant / Mumbai Delhi Hyderabad Calcutta Supply

Warehouses
Chennai 17 28 M 8 1600
Nagpur 68 M 38 58 1200
Udaipur 38 6 68 18 1700

Demand 1000 1200 800 1200

The shipments from Chennai to Hyderabad and Nagpur to Delhi are not
possible due to certain Operational Constraints/Problems.

Find the IFS by LCM, VAM and obtain Optimal Transportation Cost.

Total Supply = 1600+1200+1700 = 4500

Total Demand = 1000+1200+800+1200 + 300 = 4500
It is a balanced type Problem.
Step 2: It is minimization type problem
Step 3: It is Probihited type problem.

Plant / Mumbai Delhi Hyderabad Calcutta Supply

Warehouses
Chennai 17 28 15 8 1600
Nagpur 68 14 38 58 1200
Udaipur 38 6 68 18 1700

Demand 1000 1200 800 1200

M stands for Infinity, which Indicated Highest Cost.

Step 4 IFS by LCM

Plant / Mumbai Delhi Hydrabad Calcutta Dummy Supply

Warehouses
Chennai 17 28 M 8 0 1600
400 1200
400
Nagpur 68 M 38 0 58 0 1200
800 300
400
100

Udaipur 38 6 68 18 0 1700
500
500
1200
0

Demand 1000 1200 800 1200 300

600
100

Step 4 IFS by VAM

 P1 P2 P3 P4
Pla M D H C Dum Supply
nt / my
War
eho
uses
Ch 17 28 M 8 0 1600 600 8 9 9 9
1000 600
00

N 68 M 38 58 0 1200 900 38 20 10 10
800 100
100
300

U 38 6 68 18 0 1700 500 6 12 12 20
500
1200
0
De 1000 1200 800 1200 300
man 600 600
d 100
P1 21 22 30 10 0
P2 21 22 30 10 *
P3 21 22 * 10 *
P4 21 * * 10 *
Whether there is degeneracy in the table
How to check whether degeneracy exist in the table or not
No of occupied cells = 7
m+n -1, m = no of rows, n= no of columns-------- 3 + 5 -1 = 7
Condition for Non – Degeneracy, No of Occupied Cells = m+n -1
There is no degeneracy
Optimality Test
 V1=17 V2=-4 V3=-12 V4 =8 V5 = -50
Pla M D H C Dummy Supply
nt /
WH
U1 = 0 Ch 17 28 M 8 0 1600
1000 600
00

U2=50 N 68 M 38 58 0 1200
800 100 300

U3=10 U 38 6 68 18 0 1700
1200 500

De 1000 1200 800 1200 300

man
d
From Occupied cells, Ui + Vj =Costij
U1 + V1 = 17--------- 0+V1 = 17 , V1 = 17
U1 + V4 = 8_______ 0 +V4 = 8, V4 = 8
U2 + V3 = 38______50 + V3 = 38, V3 = -12
U2 +V4 = 58______ U2+8 =58, U2 =50
U2+V5 = 0________ 50 + V5 =0, V5 = -50
U3+V2 =6__________10 +V2 = 6, V2 =-4
U3+V4 = 18_________U3 +8 =10, U3 = 10
Unoccupied Cells ∆ij = Costij - (Ui+Vj)
Ch – D 28 – (U1 + V2) = 28 – (0- 4) = 32
Ch – H M – (U1 + V3)= M – (0-12)= M
Ch - Dummy 0 – (U1+V5)= 0 – (0-50)= 50
N- M 68 – (U2+V1)= 68 – (50+17) = 1
N- D M – (U2+V2= M – (50-4) = M
U- M 38 – (U3+V1) = 38 – (10+17) = 11
 U– H 68- (U3+V3)= 68 – (10-12)= 70
U - Dummy 0 – (U3+V5) = 0- (10-50)=40

Since no ∆ is negative. It means there is no further scope of cost reduction. The

obtained solution is optimal.
Transportation Schedule:
Occupied Cells No of Units TC/Unit Total TC
Ch – M 1000 17 17000
Ch – C 600 8 4800
N- H 800 38 30400
N- C 100 58 5800
N- Dummy 300 0 0
U- D 1200 6 7200
U– C 500 18 9000
74200
5. Maximization Type Problem
Profit Matrix (in Rs)
WH/ Mkt M1 M2 M3 Supply
W1 25 22 23 2000
W2 15 20 18 1500
W3 18 17 16 1000
Demand 1200 1800 1000

Find Optimal Transportation cost to maximize total Profit.

Step 1: It is not Balanced type problem.

Total Supply = 2000 +1500+1000 = 4500
Total Demand = 1200 + 1800+1000 = 4000
WH/ Mkt M1 M2 M3 Dummy Supply
M4
W1 25 22 23 0 2000
W2 15 20 18 0 1500
W3 18 17 16 0 1000
Demand 1200 1800 1000 500

Now it is balanced.

Step 2: It is not prohibited type problem

Step 3: Maximization Type problem. Convert Maximization type problem into
minimization type problem by calculating Regret matrix or Opportunity cost
Matrix
Regret Matrix or Opportunity cost matrix
WH/ Mkt M1 M2 M3 Dummy Supply
M4
W1 0 3 2 25 2000
W2 10 5 7 25 1500
W3 7 8 9 25 1000
Demand 1200 1800 1000 500
Step 4: Find IFS by VAM
WH/ M1 M2 M3 Dummy Supply P1 P2 P3
Mkt M4
W1 0 3 2 25 2000 2 1 *
1200 800 800

W2 10 5 7 25 1500 2 2 2
1500

W3 7 8 9 25 1000 1 1 1
300 200 500

Dem 1200 1800 1000 500

and 300 200

P1 7 2 5
P2 * 2 5
P3 * 3 2

Whether there is degeneracy or not.

No Degeneracy case, m+n-1 = No of allocations
M = no of Rows
N= No of Columns
M+n-1 =3+4-1 =6
No of allocations = 6
Optimality Test

V1 = 0 V2=1 V3 = 2 V4=18
WH/ M1 M2 M3 Dummy Supply
Mkt M4
U1= 0 W1 0 3 2 25 2000
1200 800

U2 =4 W2 10 5 7 25 1500
1500

U3 = 7 W3 7 8 9 25 1000
300 200 500

Deman 1200 1800 1000 500

d 300 200

From Occupied cells, Ui + Vj =Costij

W1- M1 _______ U1 + V1 = 0
W1-M3_______U1 + V3 = 2, 0 +V3 = 2
W2-M2________U2 + V2 = 5,
W3-M2________U3+V2= 8, 7 + V2 = 8
W3-M3________U3+V3= 9, U3+2 = 9
W3- M4________U3+V4 = 25, 7+V4 = 25 , V4 = 18

Unoccupied Cells ∆ij = Costij - (Ui+Vj)

W1-M2 3– (U1 + V2) =3-1 = 2
W1-M4 25– (U1 + V4)= 25-18 = 7
W2-M1 10– (U2+V1)= 10-4 = 6
W2-M3 7 – (U2+V3)= 7 – 6 =1
W2-M4 25 – (U2+V4)= 25-22 =3
W3-M1 7 – (U3+V1) = 7 – (7) = 0

Unique Optimal Solution

Alternate Optimal Solution

Transportation Schedule:
Occupied Cells No of Units Profit/Unit Total Profit
W1-M1 1200 25 30000
W1-M3 800 23 18400
W2-M2 1500 20 30000
W3-M2 300 17 5100
W3-M3 200 16 3200
W3-M4 500 0 0
86700

6. Profit /unit

W1 W2 W3 Supply
P1 18 20 16 2000
P2 26 22 30 2000
P3 6 2 0 2000
Demand 1500 3000 1500

Find Optimal solution and Optimal Profit.

Step 1 it is balanced type problem.
Total supply = 6000, Total demand = 6000
Step 2 : It is Unprohibited type problem
Step 3 : It is Maximization type Problem. Convert maximization Type
Problem into Minimization Type by calculating Regret Matrix or
Opportunity Cost Matrix.
Step 4 : IFS by VAM
 W1 W2 W3 Supply P1 P2 P3
P1 18 20 16 2000 2 2 2
500 1500
500

P2 26 22 30 2000 4 4 4
1000 1000

P3 6 2 0 2000 2 * *
2000

Demand 1500 3000 1500

1000 1000

P1 12 18 16
P2 8 2 14
P3 8 2 *

Optimality Test
V1 = V2= V3 =
Plant/ W1 W2 W3 Supply
WH
U1= P1 18 20 16 2000
500 1500

U2 = P2 26 22 30 2000
1000
1000

U3 = P3 6 2 0 2000
2000

Deman 1500 3000 1500

d
Allocated Cells, Ui + Vj = Cost ij
P1-W1______U1+V1 =18_______0+V1=18
P1-W3_______U1+V3 = 16______0+V3=16
P2-W1________U2+V1=26_______U2+18=26
P2-W2_________U2+V2=22______8+V2=22
P3-W2_________U3+V2= 2_______U3+14=2

Unoccupied Cells ∆ij = Costij - (Ui+Vj)

P1-W2 20– (U1 + V2) =20 – (14) = 6
P2-W3 30– (U2 + V3)= 30 – (24) = 6
P3-W1 6– (U3+V1)= 6 – (6) = 0
P3 -W3 0 – (U3+V3)= 0 – (4) =-4

Since ∆ of P3 -W3 is -ve. It is not an optimal solution.

Modified Solution / New Solution

Plant/ W1 W2 W3 Supply
WH
P1 18 20 16 2000
1500 500

P2 26 22 30 2000
2000

P3 6 2 0 2000
1000 1000

Demand 1500 3000 1500

Optimality Test of Modified Solution / New Solution

V1 = 18 V2=18 V3 = 16
Plant/ W1 W2 W3 Supply
WH
U1= 0 P1 18 20 16 2000
1500 500

U2 =4 P2 26 22 30 2000
2000

U3 = -16 P3 6 2 0 2000
1000 1000

Deman 1500 3000 1500

d

Unoccupied Cells ∆ij = Costij - (Ui+Vj)

P1-W2 20– (U1 + V2) =20 – (18) = 2
P2-W1 26– (U2 + V1)= 26 – (22) = 4
P2-W3 30 - (U2+V3)= 30 – (20) = 10
P3 -W1 6 – (U3+V1)= 6– (2) =4

Since No ∆ is Negative. It is an optimal solution

Transportation Schedule:
Occupied Cells No of Units Profit/Unit Total Profit
P1-W1 1500 58 87000
P1-W3 500 60 30000
P2-W2 2000 54 108000
P3-W2 1000 74 74000
P3-W3 1000 76 76000
375000
7. IFS for a transportation problem is given in the table below. Find
the optimal transportation cost
V1=5 V2=7 V3=7 V4=11
Plant/ I II III IV Supply
WH
U1 =0 X 9 7 6 11 6000
6000

U2=-2 Y 11 12 5 9 7000
5000 2000
U3=2 Z 7 9 11 13 13000
8000 1000 4000

Deman 8000 7000 5000 6000

d
Condition for non degeneracy, m+n-1 = No of allocations
3+4-1= 6
Optimality Test
From Occupied cells, find Ui and Vj______ Costij = Ui+Vj
X-II_______ U1+V2 = 7
Y-III_______U2+V3=5________-2+V3=5
Y-IV________U2+V4 = 9________U2+11=9
Z-I_________U3+V1=7_________2+V1=7
Z-II_________U3+V2=9________U3+7=9
Z-IV________U3+V4=13________2+V4=13
 Unoccupied Cells ∆ij = Costij - (Ui+Vj)
X-I 9– (U1 + V1) = 9- (5) = 4
X-III 6– (U1 + V3)= 6- (7) = -1
X-IV 11– (U1+V4)= 11 – (11) =0
Y-I 11– (U2+V1)= 11 – (3) = 8
Y-II 12-(U2+V2)=12 – (5) = 7
Z-III 11-(U3+V3)= 11- (9) = 2

Since we have - ∆. This is not an optimal Solution

Modified Solution
Plant/ I II III IV Supply
WH
X 9 7 6 11 6000
2000 4000
Y 11 12 5 9 7000
1000
6000
Z 7 9 11 13 13000
8000 5000

Demand 8000 7000 5000 6000

Check No degeneracy Condition

Optimality Test of Modified Solution
V1=5 V2=7 V3=6 V4=10
Plant/ I II III IV Supply
WH
U1 =0 X 9 7 6 11 6000
2000 4000

U2=-1 Y 11 12 5 9 7000
1000 6000
U3=2 Z 7 9 11 13 13000
8000 5000
 Deman 8000 7000 5000 6000
d

Optimality test
Unoccupied Cells ∆ij = Costij - (Ui+Vj)
X-I 9– (U1 + V1) = 9- (5) = 4
X-IV 11– (U1+V4)= 11 – (10) =1
Y-I 11– (U2+V1)= 11 – (4) = 7
Y-II 12-(U2+V2)=12 – (6) = 6
Z-III 11-(U3+V3)= 11- (8) = 3
Z-IV 13 – (U3+V4) =13-12 =1

Since no ∆ is negative. This is an optimal Solution.

Transportation Schedule:
Occupied Cells No of Units TC/Unit Total TC
Note: Before carrying out optimality, You should always check for Non –
Degeneracy Condition.

Plant/ L1 L2 L3 Supply
Market
P1 2 7 4 5000
5000

P2 3 3 1 8000
8000

P3 5 4 7 7000
2000 5000

P4 M 6 2 10000
100000
0

P5 0 0 0 4000
4000

Demand 7000 9000 18000

Condition for Non – Degeneracy Or Rim Condition

M+N-1= No of allocations
M+n-1 = 5 +3 – 1 =7
No of allocations = 6
There is Degeneracy.
Epsilon will be placed in an Independent least cost cell. A cell where it does
not form a closed loop with other allocations