Here the number of rows and columns are equal.
∴ The given assignment problem is balanced.
Step 1: Select a minimum element in each row and subtract this from all the elements in its row.

Step 2: Select the minimum element in each column and subtract this from all the elements in its column

Since each row and column contains atleast one zero, assignments can be made.
Step 3: (Assignment)
Examine the rows with exactly one zero. Mark the zero by ׈ and draw a vertical line.
After examining the rows, examine the columns with exactly one zero. Mark the zero by ׈ and draw a horizontal line.

Only 4 assignments are made
Number not lying on the line are

and minimum of these numbers are 1.
This number 1 should be subtracted from the above number and 1 should be added to the numbers which are on the intersecting lines (ie. 52,43,59,30,21)and the other numbers remains the same.
A new cost matrix is as follows and repeat step 3.
New cost matrix is

Thus, all the six assignments have been made.
∴ The optimal assignment schedule and total cost is

Here the number of rows and columns are equal.
∴ The given assignment problem is balanced.
Step 1: Select a minimum element in each row and subtract this from all the elements in its row.
∴ The cost matrix of the given assignment problem is

Here column c, d and e have no zeros. Go to step 2.
Step 2 : Select the minimum element in each column and subtract this from all the elements in its column.

Since each row and column contains exactly atleast one zero, assignments can be made.
Step 3: (Assignment)
Examine the rows with exactly one zero. Mark that zero by ׈ and draw a vertical line.

Also examine the columns with exactly one zero. Mark that zero by ׈ and draw a horizontal line.
Here, numbers not lying on the line are and minimum of these number is 15.


Now, subtract 15 from all these numbers and numbers lying on the line remains the same.
Hence, the new cost matrix is as follows.
Again repeat step 3 (Assignment)

Thus, all the 5 assignments have been made.
The optimal assignment schedule and total cost is

Here total supply = 6 + 1 + 10 = 7
total demand = 7 + 5 + 3 + 2 = 17
total supply = total demand
∴ The given problem is a balanced transportation problem.
Hence, there exists a feasible solution for the given transportation problem.
NWC:
I. allocation:

[∵ highest penalty = 6. 1 & min (1, 2) = 1]
II. allocation:

[∵ highestpenalty= 5. In D₂, leastcost= 3&min (5,6) = 5]
III. allocation:

[∵ highest penalty = 5. In O₁, & least cost = 2 &min (7, 1) = 1]
IV. allocation:

[∵ highest penalty = 4. In O₃, least cost is 5 &min (6, 10) = 6]
V. allocation:

[In O₃ least cost = 9 & min (1,4) = 1]
VI. allocation:


[∵ min (3, 3) = 3]
Thus, the allocations are

∴ The transportation schedule is
O₁ → D₁, O₁ → D₂, O₂ → D₄, O₃ → D₃  O₃ → D₁ and O₃ → D₄
Hence, the total transportation cost
= 1(2) + 5(3) + 1(1) + 6(5) + 3(15) + 1(9)
= 2 + 15 + 1 + 30 + 45 + 9 = Rs. 102

Here total supply = 25 + 35 + 40 = 100
total requirement = 30 + 25 + 45 100
total supply = total requirement
∴ The given problem is a balanced transportation problem.
Hence, there exists a feasible solution for the given transportation problem.
North West Corner Rule:
I - allocation:

[∵ min (25, 30) = 25]
II - allocation:

[∵ min (5, 35) = 5]
III - allocation:

[∵ min (25, 30) = 25]
IV - allocation:

[∵ min (5, 45) = 5]
V - allocation:

[∵ min (40, 40) = 40]
Thus, the allocations are

∴ The transportation schedule is
S₁ → D₁, S₂ → D₁, S₂ → D₂, S₂ → D₃, S₃ → D₃
Hence, the total transportation cost
= 25(9) + 5(6) + 25(8) + 5(4) + 40(9)
= 225 + 30 + 200 + 20 + 360
= Rs. 835

Here total availability= 30 + 50 + 20 = 100
total requirement = 30 + 40 + 20 + 10 = 100
total availability = total requirement
∴ The given problem is a balanced transportation problem.
Hence, there exists a feasible solution to the given problem,
(a) Least Cost Method :
I - allocation:

[∵ Least cost is 2 & min (20, 40) = 20]
II - allocation:

[∵ Least cost is 3 & min (20, 30) = 20]
III - allocation:

[∵ Least cost is 4 & min (50, 30) = 30]
IV - allocation:

[∵ Least cost is 4 & min (10, 20) = 10]
V - allocation:

[∵ Least cost is 5 & min (10, 20) = 10]
VI - allocation:

[∵ min (10, 10) = 10]
Thus, the allocations are

∴ The transportation schedule is
O₁ → D₂, O₁ → D₃, O₂ → D₁, O₂ → D₂, O₂ → D_4, O₃ → D₂
Hence, the total transportation cost
= 10(81) + 20(3) + 30(4) + 10(5) +10(4) +20(2)
= 80 + 60 + 120 + 50 + 40 + 40 = Rs. 390
(b) North West Corner method :
I - allocation:

[∵ Highest penalty = 3. In D₂, least cost is 2 & min (20,40) = 20]
II - allocation:

[∵ Highest penalty = 4. In D₃, least cost is 3 & min (20, 30) = 20]
III - allocation:

[∵ Highest penalty = 3. In D₂, least cost is 5 & min (20, 50) = 20]
IV - allocation:

[∵ Highest penalty = 2. In D₄, least cost is 4 & min (10, 30) = 10]
V - allocation:

[∵ Highest penalty = 4. In D₁, least cost is 4 & min (20, 30) = 20]
VI - allocation:

[∵ min (10, 10) = 20]
Thus, the allocations are

∴ The transportation schedule is
O₁ → D₁, O₁ → D₃, O₂ → D₁, O₂ → D₂, O₃ → D₂, and O₂ → D₄
Hence, the total transportation cost
= 10(5) + 20(3) + 20(4) + 20 (5) + 10(4) + 20(2)
= 50 + 60 + 80 + 100 + 40 + 40 = Rs. 370

Since the number of columns is less than the number of rows, given assignment problem is unbalanced one.
To balance it, introduce dummy columns with all the entries zero.
∴ The revised assignment problem is

Step 1 : Select the smallest element in each row and subtract this from all the elements in its row.

Since each row and column has atleast one zero, assignments can be made.
Step 2 : Examine the rows with atleast one row.
Row A & B have exactly one row. Mark them by ׈ and mark X by other zeros in its column.
Row C & F also has only one zero.
Here only 4 vacant space can be assigned to 4 trucks.
∴ The optimal assignments schedule and total cost is

∴ The optimal assignment (minimum) cost = Rs. 12

Here, the number of rows and columns are equal.
∴ The given assignment problem is balanced.
Step 1 : Select a smallest element in each row and subtract this from all the elements in its row.
∴ The cost matrix: of the given assignment problem is

Column 1 contains no zero. Go to step 2.
Step 2 : Select the smallest element (1) in column 1 and subtract this from all the elements in its column.

Since each row and column contains atleast one zero, assignments can be made.
Step 3 : Examine the rows with only one zero.
Row P, Q and S contains exactly one zero, mark them by 0 and mark the other zeros in the column byX.
Thus, all the four assignments have been made.
∴ The optimal assignment schedule and total cost is

Here the number of rows and columns are equal
∴ The given assignment problem is balanced.
Step 1 : Select a minimum element in each row and subtract this from all the elements in its row.
∴ The cost matrix of the given assignment problem is

Column 2 has no zero. Go to Step 2.
Step 2 : Select the minimum element in each column and subtract this from all the elements in its column.

Since each row and column contains atleast one zero, assignments can be made.
Step 3 : Examine the rows with exactly one zero, mark it by ׈ and draw a vertical line.
After examining the rows, examine the columns with exactly one zero.
Mark it by ׈ and draw a horizontal line.

Only 3 assignments have been made.
The numbers not lying on the line are and min. is 1. Subtract 1 from all these numbers and add 1 to 23 which lies on the intersecting lines. Other numbers remain the same.
A new cost matrix is formed and repeat step 3.
∴ The new cost matrix is

Thus, all the 4 assignments have been made.
∴The optimal assignment schedule and total cost is

Here, the number of rows and columns are equal
∴ The given assignment problem is balanced.
Step I : Select a smallest element in each row and subtract this from all the elements in its row.
∴ The given assignment problem is

Here column 2 has no zero. Go to Step 2.
Step 2 : Select the smallest element (10) and subtract it from all the elements in its column.

Step 3 : Examine the rows with only one zero mark that zero by Ԡ. Mark other zeros in its column by X.
Row 1 and Row 3 contains only one zero. Mark the other zeros by X
Column 2 contains exactly one zero. Mark it by Ԡ
Thus, all the 3 assignments have been made.
Hence, the optimal assignment schedule and total cost is

Total cost = Rs. 280
Thus, the optimal assignment (minimum) cost  =  Rs. 280

First allocation :

Second allocation :

Third allocation :

Fourth allocation :

Fifth allocation :

The transportation cost is 
\( =(200 \times 11)+(50 \times 13)+(175 \times 18)+ (125 \times 14)+(150 \times 13)+(250 \times 10) \)
= 2200 + 650 + 3150 + 1750 + 650 + 2500 
= 10900

Here the number of rows and columns are equal.
\(\therefore\) The given assignment problem is balanced.
Now let us find the solution.
Step 1: Select a smallest element in each row and subtract this from all the elements in its row.
The cost matrix of the given assignment problem is

Column 3 contains no zero. Go to Step 2.
Step 2: Select the smallest element in each column and subtract this from all the elements in its column.

Since each row and column contains atleast one zero, assignments can be made.
Step 3: (Assignment):
Examine the rows with exactly one zero. Row B contains exactly one zero. Mark that zero by \(\square\) (i.e) Person B is assigned to Job 1. Mark other zeros in its column by ×.

Now, Row C contains exactly one zero. Mark that zero by \(\square\). Mark other zeros in its column by × .

Now, Row D contains exactly one zero. Mark that zero by \(\square\) . Mark other zeros in its column by × .

Row E contains more than one zero, now proceed column wise. In column 1, there is an assignment. Go to column 2. There is exactly one zero. Mark that zero by \(\square\) . Mark other zeros in its row by × .

There is an assignment in Column 3 and column 4. Go to Column 5. There is exactly one zero. Mark that zero by \(\square\) . Mark other zeros in its row by × .

Thus all the five assignments have been made. The Optimal assignment schedule and total cost is

The optimal assignment (minimum) cost = Rs. 9

Here the number of rows and columns are equal.
\(\therefore\)The given assignment problem is balanced.
Now let us find the solution.
Step 1: Select a smallest element in each row and subtract this from all the elements in its row.

Look for atleast one zero in each row and each column.Otherwise go to step 2.
Step 2 : Select the smallest element in each column and subtract this from all the elements in its column.

Since each row and column contains atleast one zero, assignments can be made.
Step 3 (Assignment):
Examine the rows with exactly one zero. First three rows contain more than one zero. Go to row D.
There is exactly one zero. Mark that zero by \(\square\) (i.e) job D is assigned to machine
I . Mark other zeros in its column by\(\text { X }\).

Step 4: Now examine the columns with exactly one zero. Already there is an assignment in column I. Go to the column II. There is exactly one zero. Mark that zero by \(\square\) . Mark other zeros in its row by\(\text { X }\).

Column III contains more than one zero. Therefore proceed to Column IV, there is exactly one zero. Mark that zero by \(\square\) . Mark other zeros in its row by \(\text { X }\).

Step 5: Again examine the rows. Row B contains exactly one zero. Mark that zero by \(\square\).

Thus all the four assignments have been made. The optimal assignment schedule and total cost is
\(\begin{array}{|c|c|c|} \hline \text { Job } & \text { Machine } & \text { cost } \\ \hline \text { A } & \text { II } & 12 \\ \hline \text { B } & \text { III } & 7 \\ \hline \text { C } & \text { IV } & 11 \\ \hline \text { D } & \text { I } & 8 \\ \hline {\text { Total cost }} \ && 38 \\ \hline \end{array}\)
The optimal assignment (minimum) cost
= Rs. 38

Here \(\sum { { a }_{ i }=\sum { { b }_{ j } } =80 } \)
(i.e) Total Availability = Total Requirement
\(\therefore\) The given problem is balanced transportation problem.
Hence there exists a feasible solution to the given problem.
First Allocation:

Second Allocation:

Third Allocation:

Fourth Allocation:

Fifth Allocation:

Sixth Allocation:

Thus we have the following allocations:


Transportation schedule :
A⟶I, A⟶II, A⟶III, A⟶IV, B⟶I, C⟶IV, D⟶II
Total transportation cost:
= (6×5)+(6+1)+(17×3)+(5×3)+(15×3)+(12×3)+(19×1)
= 30+6+51+15+45+36+19
= Rs.202

Here \(\sum { { a }_{ i }=\sum { { b }_{ j } } =950 } \)
(i.e) Total Availability = Total Requirement
\(\therefore\) The given problem is balanced transportation problem.
Hence there exists a feasible solution to the given problem.
First let us find the difference (penalty) between the first two smallest costs in each row and column and write them in brackets against the respective rows and columns

Choose the largest difference. Here the difference is 5 which corresponds to column D₁ and D₂. Choose either D₁ or D₂ arbitrarily.
Here we take the column D₁. In this column choose the least cost. Here the least cost corresponds to (S₁, D₁). Allocate min (250, 200) = 200 units to this Cell.
The reduced transportation table is 

Choose the largest difference. Here the difference is 5 whichcorresponds to column D₂. In this column choose the least cost. Here the least cost corresponds to (S₁, D₂) . Allocate min(50,175) = 50 units to this Cell.
The reduced transportation table is

Choose the largest difference. Here the difference is 6 which corresponds to column
D₂. In this column choose the least cost. Here the least cost corresponds to (S₂, D₂). Allocate min(300,175) =175 units to this cell.
The reduced transportation table is

Choose the largest difference. Here the difference is 4 corresponds to row S2. In this row choose the least cost. Here the least cost corresponds to (S2, D4). Allocate min(125, 250) = 125 units to this Cell.
The reduced transportation table is

The Allocation is

Thus we have the following allocations:

Transportation schedule :
S₁⟶D₁,S₁⟶D₂,S₂⟶D₂,S₂⟶D₄,S₃⟶D₃,S₃⟶D₄
This initial transportation cost
= (200 x 11)+(500 x 13)+(175 x 18)+(125 x 10)+(275 x 12)+(1255 x 10)
= Rs.12,075