Unit II

Assignment and Transportation Models

2.1 Assignment Problem – Hungarian Method      

Allocation problems are a special sort of applied mathematics problem that handles the one-to-one allocation of various resources to different activities. It does it during a way that minimizes the value or time involved within the process and maximizes profits or sales. The issues are often solved by the simplex or transport method, but the allocation model provides an easier approach to those problems.

At the factory, supervisors have access to six workers and may dismiss 6 jobs. He will need to make a choice on which job should tend to which worker. The matter forms a one-to-one foundation. This is often a matter of allocation.

1. Assignment model:

Given n promotion and n jobs, it's clear that there are n allocations during this case. Each facility or worker can perform each job, one at a time. However, certain steps are required to form the allocation so as to maximise profits or minimize costs or time.

In this table, Coij is defined because the cost when the jth job is assigned to the ith worker. Note that this is often a special case of transportation problems when the amount of rows is adequate to the amount of columns.

Mathematical formulation:

The basic viable solution to the allocation problem consists of (2n – 1) variables, where the (n – 1) variable is zero and n is that the number of jobs or facilities. thanks to this high degree of degeneracy, solving problems with normal shipping methods are often a posh and time-consuming task. Therefore, another method springs . it's vital to formulate the matter before proceeding to absolutely the law.

Suppose xjj may be a variable defined as follows:

If the primary job is assigned to the jth machine or facility

0 if the i-th job isn't assigned to the j-th machine or facility.                       

Here, the matter is made one-to-one, or one job is assigned to at least one facility or machine.

The total allocation cost is

The above definition is often evolved into a mathematical model as follows:

Determine xij> 0 (i, j = 1,2,3… n),

Be constrained

xij is either 0 or 1.

How to solve the matter (Hungarian technique):

Consider a minimization type objective function. Resolving this allocation issue involves the subsequent steps:

1. Find the littlest cost element in each row of the required cost table, starting with the primary row. Here, this smallest element is subtracted from each element therein row. Therefore, get a minimum of one zero in each row of this new table.

2. After creating the table (as in step 1), get the columns of the table. Start with the primary column and find rock bottom cost think about each column. Then subtract this smallest element from each element therein column. After performing steps 1 and a couple of, you'll see a minimum of one zero in each column of the reduced cost table.

3. The reduced table is now allocated within the following way:

(I) Rows are continuously inspected until a row with just one zero is found. This assignment to one zero is formed by placing a square □ around it, with all other zeros being strikethrough (x) within the corresponding column. this is often because they're not used for other assignments during this column. The steps are performed for every row.

(Ii) Step 3 (i) am performed on the column as follows: -Columns are continuously inspected until a column with just one zero is found. Now, by placing a square around it, this single zero is assigned, and at an equivalent time all other zeros within the corresponding row are erased (x) A step is performed on each column. I will.

(Iii) Steps 3, (i), and three (ii) are repeated until all zeros are marked or strikethrough is drawn. Here, if the amount of zeros marked or the amount of allocations made is adequate to the amount of rows or columns, the simplest solution is achieved. There’s exactly one assignment for every column or column, with none assignment. During this case, attend step 4.

4. At this stage, draw the minimum number of lines (horizontal and vertical) needed to hide all the zeros within the matrix obtained in step 3. Use the subsequent procedure.

(i) Put a check on all unassigned lines.

(ii) Now mark of these columns that have zeros within the graduated rows (iii) Now check all rows that haven't yet been marked and are assigned to the marked columns.

(iv) All steps, namely (4 (i), 4 (ii), 4 (iii), are repeated until no row or column are often marked.

(V) Draw a line through all unmarked rows and marked columns. Also note that in an n x n matrix, lines but "n" always cover all zeros if there's no solution between them.

5. In step 4, the amount of lines drawn is n or the number of lines, it's the best solution. If not, go to step 6.

6. Select the smallest element from all uncovered elements. Here, this element is subtracted from all uncovered elements and added to the element at the intersection of the two lines. This is the new allocation matrix.

7. Repeat step (3) until the number of allocations is equal to the number of rows or columns.

• Maximization & Minimization Type Problems.

For maximizing allocation problems

There may be situations where allocation issues require maximization of profits.

Such a problem can be solved by transforming a given maximization problem into a minimization problem by subtracting all the elements of a given matrix from the highest elements.

Example

Find a solution to the allocation problem using the Hungarian method (for MAX)

Solution:

Number of rows = 4 and number of columns = 4

The problem here is the Maximization type, which translates to minimization by subtracting from the maximum value of 42.

The issues given here are balanced.

Step-1: Find the smallest element in each row and subtract from that row

Step-2: Find the smallest element in each column and subtract from that column.

Step-3: Make an allocation in the opportunity cost table

(1) Since the cells in the row direction (A, I) are assigned, the cells in the column direction (B, I), (C, I), and (D, I) intersect.

(2) Since the cells (D, II) in the column direction are assigned, the cells (D, III) and (D, IV) in the row direction intersect.

Row and column orientations shown in the table

Step-4: Number of allocations = 2, Number of rows = 4

The solution is not optimal because this is not equal.

Step-5: Cover 0 with minimum number of rows

(1) Since there is no assignment in line B, mark (✓) line B

(2) Since there is no assignment, mark line C (✓).

(3) Mark (✓) column I because column B in row B is 0.

(4) Mark (✓) row A because column I has an assignment for this row A.

(5) Draw a straight line through unmarked row D and marked column I because no other row or column can be marked.

Check unassigned rows and assigned columns

Step-6: Create a new revised table by selecting the smallest element from cells that are not covered by any line (eg k = 1).

Subtract k = 1 from all the elements in the cell that are not covered by the line.

Add k = 1 to all elements of the intersection cell of the two lines.

Repeat steps 3-6 until you get the best solution.

Step-3: Make an allocation in the opportunity cost table

(1) Since the cells in the row direction (A, I) are assigned, the cells (B, I) and (C, I) in the column direction intersect.

(2) Since the cells in the row direction (B, II) are assigned, the cells (C, II) and (D, II) in the column direction intersect.

(3) Since the cells in the column direction (D, III) are assigned, the cells in the row direction (D, IV) intersect.

• Balanced and Unbalanced Problems.

Whenever the cost matrix of an allocation problem is not a square matrix, that is, the number of sources is not equal to the number of destinations, the allocation problem is called an imbalanced allocation problem. In such problems, dummy rows (or columns) are added to the matrix to make a matrix. The dummy row or column contains all cost elements as zero. The Hungarian method could also be wont to solve the matter.

Example: A company has 5 machines used for 4 jobs. Each job can only be given to one machine. The following table shows the cost of each job on each machine.

Example of an unbalanced maximization allocation problem

Solution: Add dummy row D5 to convert the 4x5 matrix to a square matrix.

Dummy line D5 has been added

Matrix row direction reduction

No per-column reduction is required as every column contains a single zero. Then draw the minimum number of lines that cover all zeros, as shown in the table.

All zeros in the matrix of interest

Number of lines drawn ≠ Matrix order. Therefore, it is not optimal.

As shown in the table, select the least covered element, that is, 1, subtract it from the other uncovered elements, add it to the element at the intersection of the lines, and cover it with a single line. Do not change the element.

Subtract or add to an element

Number of lines drawn ≠ Matrix order. Therefore, it is not optimal.

Add or subtract 1 again from the element

Number of lines drawn = degree of matrix. Therefore, optimality is reached. Then assign the job to the machine, as shown in the table.

Assigning jobs to machines

Example: In a plant layout, four different machines M1, M2, M3, and M4 are installed in a machine shop. There are five missing areas: A, B, C, D and E. Due to limited space, Machine M2 cannot be installed in Area C and Machine M4 cannot be installed in Area A. The installation cost of the machine is shown in the table.

Allocation problem

Find the best allocation plan.

Solution: Add a dummy row D5 with a cost value of zero because the specified matrix is out of balance. Assign high-cost H to (M2, C) and (M4, A). Ignore the assigned high-cost H when selecting the lowest cost element, as shown in the table below.

Dummy line D5 has been added

The table shows the reduction of each row of the matrix.

Row-by-row reduced matrix

Note: There is at least one zero in each column, so no per-column reduction is needed. Now draw the minimum number of lines that cover all zeros. See table.

Lines drawn to cover all zeros

Number of lines drawn ≠ Matrix order. Therefore, it is not optimal. Select the smallest uncovered element (1 in this case). Subtract 1 from all other uncovered elements and add 1 to the intersection element. The elements covered by a single line do not change. These changes are shown in the table. Next, try drawing the minimum number of lines to cover all zeros.

Add or subtract 1 from the element

You now reach the number of lines drawn = the order of the matrix, and thus the optimality. The table shows the optimal allocation of machines to the area.

Optimal allocation

Key takeaways:

1. Allocation problems are a special sort of applied mathematics problem that handles the one-to-one allocation of various resources to different activities.
2. It does it during a way that minimizes the value or time involved within the process and maximizes profits or sales.
3. Given n promotion and n jobs, it's clear that there are n allocations during this case.
4. Each facility or worker can perform each job, one at a time.
5. The basic viable solution to the allocation problem consists of (2n – 1) variables, where the (n – 1) variable is zero and n is that the number of jobs or facilities.
6.  Thanks to this high degree of degeneracy, solving problems with normal shipping methods are often a posh and time-consuming task.
7. Such a problem can be solved by transforming a given maximization problem into a minimization problem by subtracting all the elements of a given matrix from the highest elements.
8. Whenever the cost matrix of an allocation problem is not a square matrix, that is, the number of sources is not equal to the number of destinations, the allocation problem is called an imbalanced allocation problem.
9. No per-column reduction is required as every column contains a single zero.

• Prohibited assignment problems, unique or multiple optimal solutions.

An Assignment problem may have more than one optimal solution, which is called multiple optimal solutions. Multiple optimal solutions mean that the total cost or total profit will remain same for different sets or combinations of allocations. It is sometimes seen that a certain task cannot be performed by a person or a machine. A restricted assignment problem is the one in which one or more allocations are prohibited or not possible. The solution should be found taking into consideration these restrictions. For such allocations we assign “M”, which is infinitely high cost. No allocation is given in M.

Example: Five jobs are to be assigned to five men. The cost (in Rs.) of performing the jobs by each man is given in the matrix. There are restrictions in the assignment that Job 4 cannot be performed by Man 1 and Job 3 cannot be performed by Man 4. Find the optimal assignment of job and its cost involved.

Assignment Problem

Solution: Assign a large or infinite value to the restricted combinations or introduce ‘M’, see table.

Large Value Assignment to Restricted Combinations

Reducing the matrix row-wise

Reducing the matrix column-wise

Draw minimum number of lines so as to cover all zeros, see Table below.

All Zeros Covered

Now, number of lines drawn = Order of matrix, hence optimality is reached.
Allocating Jobs to Men.

Job Allocation to Men

Assignment Schedule and Cost

As per the prohibited conditions given in the problem, Man 1 and man 4 are not assigned to Job 4 and Job 3 respectively.

Key Takeaways:

1. An assignment problem can have more than one optimal solution.
2. While solving a prohibited problem, all restrictions should be taken into account and for the restricted allocation, no value is given while finding the solution.

• Simple Formulation of Assignment Problems.

Meaning of allocation problem:

Allocation problems are specific cases of transportation problems where the goal is to allocate an outsized number of resources to an equivalent number of activities so as to attenuate the entire cost or maximize the entire profit of the allocation.

Allocation issues arise because available resources like men, machines, etc. have different degrees of efficiency for performing different activities. Therefore, there are different costs, benefits, or losses to perform different activities.

Definition of assignment problem:

Suppose you've got n jobs to run and n people can run these jobs. Efficiency varies, but assumes that every person can run each job in just one occasion period. However, if the i-th person is assigned to the j-th job, cij are going to be the value. The matter is finding an assignment (which job should be assigned to which person on a one-to-one basis). This sort of problem is understood as an allocation problem in order that the entire cost of running all jobs is minimized.

Assignment issues are often expressed within the sort of real members of the n xn cost matrix C, as shown within the following table.

Mathematical formulation of assignment problems:

Hungarian thanks to solve the allocation problem:

The Hungarian allocation method provides an efficient thanks to find the simplest solution without having to match all the solutions directly. It works on the principle of reducing a given cost matrix to a chance cost matrix.

Opportunity cost indicates the relative penalty related to allocating resources to an activity, instead of allocating the simplest or least cost. Optimal allocation are often achieved if a minimum of one zero in each row and column can reduce the value matrix to some extent.

The Hungarian method are often summarized within the following steps.

Step 1: Create a price table from the given problem.

If the amount of rows isn't adequate to the amount of columns, or the other way around, you would like to feature dummy rows or columns. The value of allocating dummy cells is usually zero.

Step 2: Find the chance Cost Table:

(A) Find the littlest element in each row of the required cost table and subtract it from each element therein row.

(B) Within the reduction matrix obtained from 2 (a), find the littlest element in each column and subtract it from each element. Each row and column has a minimum of one zero value.

 Step 3: Make an allocation within the cost Matrix:

The allocation procedure is as follows:

(A) Examine the rows continuously until you get a row with just one unmarked zero. Make the assignment one zero by creating a square around it.

(B) For every zero value assigned, delete (cancel) all other zeros within the same row and / or column.

(C) Repeat steps 3 (a) and three (b) for every column, leaving just one unassigned zero value.

(D) If there are two or more unmarked zeros within the rows and / or columns and therefore the check cannot select one, select any assigned zero cell.

(E) Continue this process until all zeros within the matrix are enclosed (assigned) or deleted (x).

Step 4: Optimal criteria:

If the assigned cell members are adequate to the row sequence that is the best solution. The entire cost related to this solution is obtained by adding the first cost figure to the occupied cell.

If zero cells are arbitrarily selected in step (3), an alternate optimal solution exists. However, if you can't find the simplest solution, attend step (5).

Step 5: Modify the chance cost table.

Use the subsequent procedure to draw a group of horizontal and vertical lines that cover all zeros within the revised cost table obtained in step (3).

(A) Add a check (√) to every row that has not been assigned.

(B) Examine the marked line. If zeros occur in these columns, check each row that contains the assigned zeros.

(C) Repeat this process until you'll not mark rows or columns.

(D) Draw a line through each marked column and every unmarked row.

If the amount of drawn lines is adequate to the amount (or columns), then the present solution is that the best solution otherwise, attend step 6.

Step 6: Create a newly revised cost Table.

(A) Select the littlest element from the cells that aren't covered by the road, and call this value K.

(B) Draw K from all the weather within the cell that isn’t covered by the road.

(C) Add K to the element within the cell covered by the 2 lines, that is, the intersection of the 2 lines.

(D) The weather of the cell covered by one row aren't changed.

Step 7: Repeat steps 3-6 close up the lights for the simplest solution

Example:

1. At the Computer Center, after careful study of the three expert programs responsible for the Computer Center, the experts estimate the computer time required for the application program in minutes as follows:

Assign programmers to the program to minimize the total computer time.

Solution:

Hungarian law is used to obtain the optimal solution.

Steps (1) & (2):

The minimum time elements for lines 1, 2, and 3 are 80, 80, and 110. Subtract these elements from all the elements in each row.

The shortened time matrix is   shown in Table (1) below table 1:

In the reduced table (1), the minimum time elements in columns A, B, and C are 0, 10, and 0, and these elements are subtracted from all of these elements columns for getting the shortened time matrix, as shown in Table 2.

Step 3 (a):

Examine all rows, starting with the first row and until you find a row that contains only a single zero element. Here, rows 1 and 3 have only one zero in each of cells (1, C) and (3, A) assigned these zeros. All zeros in the assigned column are erased, as shown in Table 3.

(B) Now look at each column starting with A in Table 3. There is one zero in column B of cell (2, B). Allocate this cell as shown in Table 4.

(C) The number of allocations (= 3) is equal to the number of rows (= 3), so the optimal solution is obtained. The pattern of allocation between the programmer and the program and each line (in minutes) is  shown below.

Example 2:

The department has five employees and needs to perform five tasks. The time it takes for each man to perform each task (in hours) is shown in the effectiveness matrix.

How do I need to assign one job to each employee to minimize total man-hours?

Solution:

Applying step (1) and step (2) of the algorithm (2) gives an opportunity reduction time matrix as shown in Table (1).

In the reduced table (1), the minimum time elements in columns I, II, III, IV, and V are 0, 0, 0, 0, 0, respectively, and we subtract these from each element. The columns get the same reduced matrix.

Step 3 (a):

Examine all rows one at a time, starting with A and until you find a row that contains only a single zero element H.. All zeros in the assigned column are deleted, as shown in Table 2.

(B) Now, start with the columns and examine each column. 1. There is one zero in column III. Cell (C, III) Allocation is made in this cell. Therefore, cells (C, V) are crossed off. As shown in Table 2, all zeros in the table are assigned or cleared.

The solution is not optimal as only four assignments are made.

Step 4:

Cover zeros with the minimum number of rows (= 4), as described below.

(A) Line D has no assignment, so mark line (√) line D.

(B) Mark (√) columns I and IV because row D has zero elements in these columns.

(C) Mark (√) rows B and E because (c) columns 1 and (IV) have assignments for rows B and E, respectively.

(D) Draw a straight line through unmarked rows A and C and marked columns I and IV, as other rows or columns cannot be marked, as shown in Table 3.

Step 5:

Create a new revised table by selecting the smallest element from all the uncovered elements in the rows of Table 3. , 1), (A, IV), (C, 1) <and (E, IV) respectively. It is at the intersection of the two lines. Table 4 shows another revised table thus obtained.

Step 7:

Repeat steps (3) through (5) to find a new solution. The new assignments are shown in Table 5                   

The solution is best if the number of allocations (= 5) is equal to the number of rows (or columns).

The patterns of allocation between jobs and employees and their respective hours (in hours) are shown below.

Variations on the assignment problem:

Disproportionate allocation problem:

If the cost matrix is   not a square matrix, that is, the number of rows and columns are not equal, the allocation problem is said to be imbalanced. Add a dummy row or column with all entries zero for balance.

Example 3:

There are four jobs assigned to the machine. In the following matrix, you can assign only one job to a machine.           

Find the best job assignments for machines, minimize total processing time, and also find out which machines have no jobs assigned. What is the total processing time to complete all jobs?

Solution:

The problem is imbalanced because the cost matrix is   not a square matrix. Add dummy job 5 with zero corresponding entry modified matrix.

Steps 1 & 2:

Subtract the smallest element from all the elements in each row and column.

Steps 3 & 4:

Now, do the zero allocation in the usual way and get the next matrix.

However, the solution is not optimal because there are only four allocations.

Step 5:

In this step, draw the minimum number of the line that covers zeros.

Rows covering all zeros = 4 <matrix order. The minimum uncovered element (i) is subtracted from the remaining uncovered elements and added to the element at the intersection of the lines to form the second modified matrix.

Step 6:

Repeat steps (3) and (4) again to find the next matrix.

 Here, the total number of allocations (= 5) is equal to the number of rows or columns. Then this is the best solution.

The allocation pattern is shown below.

For machine E, no jobs have been assigned. Optimal (minimum)

Cost = 10 + 3 + 6 + 1 = Rs.20

Example 4:

(Airline crew assignment)

Below is a timetable for airlines that operate seven days a week. Crew members must have a flight interval of at least 6 hours. Get a pair of flights that minimizes transit time from home. With any pairing, the crew is based in one city, resulting in fewer connections.

Solution:

If your crew is based in Delhi, first create a table of possible connections between flights. The time difference between Flight I and Flight 101 is 24 hours. That is 1,440 minutes, but the minimum transfer required is 6 hours or 360 minutes.

If the crew is based in Delhi, the layover table would look like this:

Similarly, create a transit table for Calcutta-based crew members.      

According to the given constraints, the minimum layover times are shown in the following table.     

The circled numbers indicate the connections of the Calcutta-based crew, while the encircled numbers indicate the Delhi-based crew.

Step 1:

Subtracting the minimum element of each row from all the elements of the corresponding row gives:

Step 2:

Subtract the column that is minimum from all elements of the column.

Step 3:

Since optimal allocation is not possible in a given situation, assigning to a zero element draws a minimum number of horizontal or vertical lines to cover all zeros, and three as shown below. Get the line. 

This number is not equal to the number of rows / columns, so 3 rows are retrieved. The solution is not optimal. Proceed to step (4).

Step 4:

Identify the smallest uncovered element and subtract it from all uncovered elements. In addition to the intersection elements, the matrix is ​​modified as follows (minimum element = 60).

Step 5:

(Repeat step 3) Draw a horizontal vertical line to cover all zeros:

The number of rows is now equal to the row sequence (that is, 4). Therefore, the solution is optimal. Proceed to step (6).

Step 6:

Assign to zero element

• Maximum 5 x 5 Matrix. Up to Maximum Two Iterations after Row and Column Minimization.

Solve the given assignment problem

Sol:

Row Minimization

Column Minimization

The least value in the cell is 1, it is subtracted for the uncrossed cell and added for intersection of the vertical line and horizontal.

 Here, it satisfies our condition N=n

Now, the assignment for the optimum table

Assignment

1                                                             I      = 11

2                                                             IV   =   6

3                                                             V    = 16

4                                                             III   = 17

5                                                             II    = 10

6                                                                          40 

Key takeaways:

1. Allocation problems are specific cases of transportation problems where the goal is to allocate an outsized number of resources to an equivalent number of activities so as to attenuate the entire cost or maximize the entire profit of the allocation.
2. Assignment issues are often expressed within the sort of real members of the n xn cost matrix C
3. The Hungarian allocation method provides an efficient thanks to find the simplest solution without having to match all the solutions directly.
4. It works on the principle of reducing a given cost matrix to a chance cost matrix.
5. If the cost matrix is   not a square matrix, that is, the number of rows and columns are not equal, the allocation problem is said to be imbalanced. Add a dummy row or column with all entries zero for balance.

2.2 Transportation Problems

• Maximization & Minimization Type Problems.

There are certain types of transport problems that need to be maximized rather than minimized in the objective function. These problems can be solved by converting the maximization problem to the minimization problem.

Example: A manufacturing company has four factories in different locations, all producing the same product. Manufacturing costs vary from factory to factory due to internal and external factors. Since each factory is different in scale, so is the production capacity. The following table shows the cost and capacity at different locations.

Cost and capacity of various plants

The company has five warehouses. The table below shows the demand in these warehouses and the shipping costs per unit. The selling price per unit is Rs 30 /-

Maximize imbalanced transportation problems

Transportation problems

1. Formulate the problem to maximize profits.
2. Use TORA to determine the solution.
3. Find total profit

Solution:

The purpose is to maximize profits. The formulation of the transportation problem as a profit matrix table is shown in the table. The profit value is obtained as follows.

Profit = Selling Price-Manufacturing Cost-Transportation Cost

Profit matrix

Convert the profit matrix to an equivalent loss matrix by subtracting all profit values ​​from the highest value of 13 subtracting all the values ​​from 13 shows the resulting loss matrix in the table.

Loss matrix

(Ii) Use TORA to determine the initial solution

Input screen:

TORA, TP Max problem input screen

Output screen

TORA output screen (Vogel method)

It's optimal because the first iteration itself is optimal.

(iii) To find the total cost:

The total maximized profit associated with the solution

Total profit

= (6 × 10) + (4 × 20) + (10 × 120) + (3 × 180) + (9 × 70) + (10 × 20) + (13 × 80) + (15 × 70)

= 60 + 80 + 1200 + 540 + 630 + 200 + 1040 + 1050

= Rs 4800.00

Example:

Surya Roshni Ltd. has three factories, X, Y and Z. We supply products to four dealers nationwide. The production capacity of these plants is 200, 500 and 300 per month, respectively.

Determine the appropriate allocation to maximize your total net income.

Solution

You can translate the maximum transportation problem into a minimum transportation problem by subtracting each transportation cost from the maximum transportation cost.

Here, the maximum shipping cost is 25. Therefore, subtract each value from 25. The fixed shipping issues are listed below.

Table 1

The initial basic feasible solution is obtained by the matrix minimization method and is shown in the final table.

Final table

Maximum net profit

25 X 200 + 8 X 80 + 7 X 320 + 10 X 100 + 14 X 100 + 20 X 200 = 14280.

• Balanced and Unbalanced problems.

Balanced transportation issues:

For shipping issues:

Minimize z =

Be constrained

If the aggregate supply from all sources is equal to the aggregate demand of all destinations, then x11 of all i and j is said to be a balanced transport problem, otherwise the problem is an imbalanced transport problem is said to be.

There may be a solution that can only be implemented if the transportation problem is a balanced problem. Imbalanced issues can be balanced by adding dummy supply centers (rows) or dummy demand centers, depending on your requirements.

Disproportionate transportation problem:

If you have a transportation problem where the sum of the supplies available from all sources is not equal to the sum of the demands of all the destinations, that is, the problem is said to be an imbalanced transportation problem.

However, these imbalanced T.P.S needs to be transformed because the aggregate supply must be equal to the aggregate demand for a viable solution to exist for a well-balanced one.

There are two possibilities:

If supply exceeds demand, introduce a dummy demand center (additional destination column) in the transportation problem to absorb the excess supply. The unit cost of shipping cells in this dummy destination column is set to all zeros to represent items that have not been created and sent.

Working rules:

That is, whenever aggregate demand exceeds aggregate supply, we introduce a dummy supply center (additional supply column) in the transportation problem to meet the additional demand. The unit cost of transportation for cells in the dummy row is set to zero.

Second type example:

It solves the transportation problem when the transportation unit price, supply and demand, and supply are as follows.

Solution:

The problem is an imbalanced T.P. because aggregate demand ∑bj = 215 is greater than aggregate supply ∑ai = 195.

Convert this to a balanced T.P by introducing a zero cost dummy origin 04 and giving an equal supply of 215 – 195 = 20 units. Therefore, there is a problem transformed as follows:

Because of the balance of this issue, there is a viable solution to this issue. Using the lowest cost method, you get the following initial solution:

There are seven independent non-negative assignments equal to m + n-1. Therefore, the solution is non-degenerate.

Total shipping cost

= (6 x 65) + (5 x 1) + (30 x 5) + (25 x 2) + (4 x 25) + (7 x 45) + (20 x 0)

= Rs. 1010

To find the best solution:

Apply the MODI method steps to the table above.

First, calculate u1 vj & Δij.

Use the cij = ui + vj relationship for the occupied cell

For unoccupied cells, Δij = cij – (ui + vj).

The solution is not optimal because not all Δijs are greater than or equal to zero.

... this cell introduces cells (O3, D1) because the value of Δij is the most negative. Therefore, select this cell as the reference.

For cell O3D1, create a closed path as follows:

O3D1 → O3D3 → O2D3 → O2D2 → O1D2 → OxD1 → O1D1 → O3D3

If you alternate the cycle start (+) of all selected O2D1s with (+) and minus (-) and adjust the associated supply and demand positions, the modified assignments are in the following table.

The number of independent allocations is equal to m + n – 1, so check the optimality of this and recalculate ue uj & Δij.

First type example:

The products are produced in four factories, F1, F2, F3 and F4. Their unit production costs are Rs2, 3, 1, and 5, respectively. The production capacity of the factory is 50, 70, 30 and 50 respectively. Products are supplied to four stores: S1, S2, S3, and S4. The requirements for these stores are 25, 35, 105, and 20, respectively. The transportation unit price is as follows.

Find a transportation plan that minimizes total production and transportation costs.

Solution:

It forms a transport table consisting of both production and transport. cost.

The table is as follows:

Here, total cost = production unit price + transportation cost

Therefore, the problem is imbalance. Convert to a balanced store by adding a zero cost dummy store S5. Oversupply is given as a rim requirement for this store (220 — 185) = 15 units.

To find the first basic viable solution:

The initial basic feasible solution was obtained by the minimum cost method, and the following initial basic feasible solution was found.

The first basic viable solution that includes a non-negative independent allocation of m + n – 1 = 8. Therefore, the solution is a non-degenerate solution.

Total shipping cost

= (4 x 25) + (6 x 5) + (8 x 20) + (10 x 50) + (8 x 20) + (4 x 30) + (13 x 35) + (15 x 0)

= Rs. 1525

To find the best solution:

To do this, apply the MODI method to the table above. Since it has an independent non-negative assignment of m + n – 1, we first calculate ui, vj, and Δij with the following relationship:

Occupied cell Cij = ui + vj

Δij = cij – (ui + vj) For unoccupied cells

This solution is not optimal because the net rating of cells (F4, S4) is negative. That is, Δ44 = -3

Then draw the closed path from the cell and add it to change the assignment

nd subtraction min = (35,20) = 20.

This closed path is F4S4 → F4S3 → F2S4 → F2S4 → F4S4.

The following table shows this modified assignment.

Again, we are checking the optimality for calculating ui, vj, and Δij.

The solution is optimal because all values of Δij ≥ o.

The best solution is

• Prohibited Transportation Problems, Unique or Multiple Optimal Solutions.

Sometimes, there may be situations when a particular route cannot be used for transportation, for example, when road is being constructed, accidents, floods, etc. These problems are known as prohibited transportation problems. These can be solved by two methods:

• By assigning a very high or infinite cost value represented by M to the unavailable route.
• By blocking allocation to the cell which has the prohibited route, thus helping cancel the cell.

Consider the following transportation problem.

Solution:

As can be seen in the question, we have some restrictions.

An initial solution is obtained by the matrix minimum method 

Final Table

Initial basic feasible solution

16 X 50 + 12 X 150 + 14 X 40 + 8 X 120 + 26 X 90 = 6460.

The minimum transportation cost is Rs. 6460.

Key Takeaways:

1. Problems where some routes are prohibited for transportation can be solved by assigning an infinite cost to the restricted route.
2. A transportation problem can have multiple optimal solutions which can give the most feasible solution for different route

• Simple Formulation of Transportation Problems.

While solving a problem, the key part lies in formulating the model by decoding the problem. For a transportation problem, usually, the problem will be given in a tabular form or matrix form called transportation table or cost-effective matrix.

Let’s check an example below.

An example for transportation problem with Source {A, B, C} with total supply as 70 and Destinations {1,2,3} with total demand as 70.

 Here,

Source = {A, B, C}

They represent sources with supply capacity 10,35,25 units of commodities respectively (given in orange)

Hence, total supply=10+35+25=70

Destinations= {1,2,3}

They represent destinations that require 20,25,25 units of commodities respectively (given in green).

Hence, total demand=20+25+25=70

The elements represented in the matrix are called cost. i.e., the unit cost involved in moving unit commodity from one origin to another destination.

For example,

The cost incurred in moving 1 unit of the commodity from source A to destination 1= ₹2/-

The cost incurred in moving 1 unit of the commodity from source A to destination 1= ₹2/- (here, we are looking at the cross-section of source A and destination 1)

Likewise,

The cost incurred in moving one unit of the commodity from source B to destination 2= ₹4 and so on. [Here, we are looking at the cross-section of source and destination]

Key Takeaways:

1. The main part while solving a problem is the formation of the model to find the solution.
2. The data in a transportation problem is usually given in a tabular or matrix form.

• Initial Feasible Solution (IFS) by:

North West Corner Rule (NWCR)

Northwest corner rule

1. In this part, we'll look at the Northwest Corner rules to find the first basic viable solution. There are three steps.
2. Find the cell in the northwest corner of the transport tableau. Allocate as much as possible to the selected cells and subtract the allocated amount to adjust the associated supply and demand amount.
3. Cancels a row or column with zero supply or demand. If both the row and column have 0s, then the row or column is randomly cancelled.
4. If one cell does not intersect, cancel the cell and stop. Otherwise, go to step 1.

Example

Start with an empty matrix with supply at the bottom and supply at the right.

When you get the cell in the northwest corner, its values ​​are the minimum d1 and s1. Since s₁ is smaller than d₁, cancel the first line.

In the next iteration, do the same steps.

We come up with such a table and a basic viable solution.

Programming

Write a function that receives supply and demand. The function updates supply and demand on each iteration, so first copy the arguments and make i and j equal to zero. At each iteration, add 1 to i or j and place the new variable in the resulting list. Crossing all rows and columns returns a basic variable in the form of a tuple containing positions and values.

In [5]:

Def north_west_corner (supply, demand):

    Supply copy = supply. Copy ()

    Demand copy = demand. Copy ()

    i = 0

    j = 0

    bfs = []

    While len (bfs) < len(supply) + len(demand) - 1:

        s = supply_copy[i]

        d = demand_copy[j]

        v = min(s, d)

        supply_copy[i] -= v

        demand_copy[j] -= v

        bfs.append(((i, j), v))

        if supply_copy[i] == 0 and i < len(supply) - 1:

            i += 1

        elif demand_copy[j] == 0 and j < len(demand) - 1:

            j += 1

    return bfs

In [6]:

Supply = [30, 70, 50]

Demand = [40, 30, 40, 40]

bfs = north_west_corner (supply, demand)

Print (bfs)

[((0, 0), 30), ((1, 0), 10), ((1, 1), 30), ((1, 2), 30), ((2, 2), 10), ((2, 3), 40)]

 Least Cost Method (LCM)

There are several methods available to get the first basic viable solution to your shipping problem. Only the following three are discussed here. To find the first basic viable solution, the total supply should be equal to the total demand.

Method: Least common multiple method (LCM)

The lowest cost method is more economical than the northwest corner rule because it starts with a low starting cost. The various steps involved in this method are summarized below.

Step 1: Find the cell with the lowest (minimum) cost in the transport table.

Step 2: Assign the maximum amount that can be executed in this cell.

Step: 3: Delete the row or column to which the assignment will be made.

Step: 4: Repeat the above steps for the reduced transport table until all allocations are complete.

Example

Use the lowest cost method to get the first basic viable solution to the next shipping problem.

Here, Oi and Dj indicate the i-th starting point and the j-th destination, respectively.

Solution:

Total supply = total demand = 24

The problem given is a balanced transportation problem.

Therefore, there is a viable solution to the given problem.

The transportation issues given are:

The minimum cost is 1, which corresponds to cells (O1, D1) and (O3, D4).

Get cells (O1, D1) arbitrarily.

Allocatemin (6,4) = 4 units in this cell.

The shrunk table

The lowest cost corresponds to the cell (O3, D4). Allocate a minimum (10,6) = 6 units to this cell.

The shrunk table

Minimum cost 2 corresponds to cells (O1, D2), (O2, D3), (O3, D2), (O3, D3).

Allocate min (2,6) = 2 units to this cell.

The shrunk table

The minimum cost is 2, which corresponds to cells (O2, D3), (O3, D2), (O3, D3).

Allocate a minimum (8,8) = 8 units to this cell.

The shrunk table

Here we assign 4 units to the cell (O3, D2)

Therefore, it has the following assignments:

Transport schedule:

O1 → D1, O1 → D2, O2 → D3, O3 → D2, O3 → D4

Total shipping cost

= (4 × 1) + (2 × 2) + (8 × 2) + (4 × 2) + (6 × 1)

= 4 + 4 + 16 + 8 + 6

= Rs. 38.

Example

Use the lowest cost method to determine the quantity that needs to be stepped from the factory to different destinations for the next shipping problem:

The cost is expressed in rupees per unit shipped.

Solution:

Total capacity = total demand

 The problem given is a balanced transportation problem.

Therefore, there is a viable solution to the given problem.

Given the transportation problem

First assignment:

Second assignment:

Third assignment:

Fourth assignment:

 Fifth assignment:

6th assignment:

Transport schedule:

T → H, T → P, B → C, B → H, M → H, M → K

Total shipping cost = (5 × 8) + (25 × 5) + (35 × 5) + (5 × 11) + (18 × 9) + (32 × 7)

= 40 + 125 + 175 + 55 + 162 + 224

= £ 781

• Vogel’s Approximation Method (VAM)

The Vogel’s Approximation Method or VAM can be defined as an iterative procedure which is used to find out the initial feasible solution of the transportation problem. The initial basic feasible solution obtained by VAM is either optimal solution or very nearer to the optimal solution. Let’s go through the procedure with an example.

Example:
A mobile phone manufacturing company has three branches which are located in three different regions, say Jaipur, Udaipur and Mumbai. The company is supposed to transport mobile phones to three destinations, say Kanpur, Pune and Delhi. The availability from Jaipur, Udaipur and Mumbai is 40, 60 and 70 units respectively. The demand at Kanpur, Pune and Delhi are 70, 40 and 60 respectively. The transportation cost is shown in the matrix below (in Rs). Use the Vogel’s Approximation Method to find a basic feasible solution (BFS).

Solution:

Step 1: Balance the problem

Balance the problem meaning we need to check that if;

∑ Supply=∑ Demand

​If this condition is satisfied, then we will consider the given problem as a balanced problem.

Now, what if it’s not balanced?

i.e., Σ Supply≠ Σ Demand

​If such a condition occurs, then we have to add a dummy source or market; whichever makes the problem balanced.

Step 2: Find out the Row difference and the Column difference

Now, we will find out the row and the column difference of the provided matrix.

For the same we will solve this as follows:

Here as you can see in the first row, we need to find out cell containing smallest value (least cost), and the second least.

Hence, we find 1 and 4 as the two lowest values in the first row.
Take the difference of these two numbers, i.e. (4−1)=3.

In a similar manner, find out differences for all the rows as shown above.

The same procedure is to be done with columns.
So, for the first column, you will get, (4−3)=1.
Find out difference for all columns as done above.

Step 3: Select the row/column with highest difference

As we can see above, the highest difference value is 4 which is for the last row.

So we will select that row, and find out the minimum cost in that row.
You will find that, minimum cost is 2.

Now, compare the supply and demand for this row and column respectively.
We find that, we have supply as 70 and demand as 40 for the selected cell.

Compare both and select the minimum of them for the allocation in the cell, as shown below.

Cross out the column whose demand is fulfilled.

Step 4: Remove the row/column whose supply or demand is fulfilled and prepare new matrix and repeat the same procedure

As it can be seen, we now have a new matrix with second column removed (as its demand was 40 which was fulfilled)

Now, we will repeat the same procedure until we're done with all allocations.
i.e.,

• Find row and column difference.
• Select highest difference.
• Allocate cell with minimum cost, associated with selected highest row or column difference.
• Check out row/column, if demand or supply is fulfilled.

Step 5: After all the allocations are completed, write all the allocations in the matrix and find Transportation cost

We have all allocations with their respective cell now.

Find transportation cost as follows:

Transportation cost= (1x40)+(3x40)+(3x20)+(6x30)+(2x40)=Rs 480.

Key Takeaways:

1. VAM is an iterative method used to find the initial feasible solution.
2. It is preferred as it provides optimal or near optimal solution.

• Maximum 5 x 5 Transportation Matrixes.

Table 1. An example of 5x5 transportation problem

Initial basic solution for this problem was obtained by using the VAM and given in Table 2. Using the values in Table 2, initial cost was calculated as 68804.

Table 2. Initial solution tableau of VAM

Optimal solution can be achieved using transportation simplex algorithm [4] within five iterations and final cost calculated was 59356. Optimal solution tableau is given in Table 3. Solution of proposed method (IVAM) for the same problem is illustrated in the following section.

Table 3. Optimal solution tableau

• Finding Optimal Solution by Modified Distribution (MODI) Method. (u, v and ∆)

There are two steps to solving a transportation problem. The first phase requires finding the first basic viable solution, and the second phase optimizes the first basic viable solution obtained in the first phase. There are three ways to find the first basic viable solution.

• Northwest corner method
• Minimum cost cell method
• Vogel approximation

This article describes how to optimize your first basic viable solution through the examples provided. Consider the following transportation problem.

Solution:

Step 1: Check if the problem is balanced.

If the sum of all supplies from sources O1, O2, and O3 is equal to the sum of all demands for destinations D1, D2, D3, and D4, then the shipping problem is a balanced shipping problem.

Note: If the problem is not imbalanced, you can follow the concept of dummy rows or columns to transform an imbalanced problem into equilibrium, as described in this article.

Step 2: Find the first basic viable solution.

You can use one of the three methods described above to find the first basic viable solution. Here we use the Northwest Corner method. And according to the Northwest Corner Method, this is the final first basic viable solution.

Now the total shipping cost is (200 * 3) + (50 * 1) + (250 * 6) + (100 * 5) + (250 * 3) + (150 * 2) = 3700.

Step 3: U-V method to optimize the first basic viable solution.

Below is the first basic viable solution.

– For U-V methods, you need to find the row and column values ​​ui and vj, respectively. Since we have 3 rows, we need to find 3 ui values. That is, u1 on the first row, u2 on the second row, and u3 on the third row.

Similarly, for four columns, you need to find the four vj values, v1, v2, v3, and v4. Please check the image below.

There is another formula for finding ui and vj.

ui + vj = Cij where Cij is the cost value of the assigned cell only. Please check this out for details.

Before applying the above formula, we need to make sure that m + n – 1 is equal to the total number of cells allocated. Where m is the total number of rows and n is the total number of columns.

In this case, m = 3, n = 4, and the total number of cells allocated is 6, so m + n – 1 = 6. Later post if m + n – 1 is not equal to the total number of allocated cells.

Now assign any of the three u or any of the four v as 0 to find the values ​​for u and v. In this case, assign u1 = 0. Then, using the above formula, we get v1 = 3 as u1 + v1 = 3 (that is, C11) and v2 = 1 as u1 + v2 = 1 (that is, C12). Similarly, we got the value of v2 = 1, so we get the value of u2 = 5, which means v3 = 0. From the value of v3 = 0, we get u3 = 3, which means v4 = -1. See the image below.

Now use the formula Pij = ui + vj – Cij to calculate the penalty only for unallocated cells. There are two unallocated cells in the first row, two in the second row and two in the third row. Let's calculate this one by one.

For C13, P13 = 0 + 0 – 7 = -7 (here C13 = 7, u1 = 0 and v3 = 0)

For C14, P14 = 0 + (-1) -4 = -5

For C21, P21 = 5 + 3 – 2 = 6

For C24, P24 = 5 + (-1) – 9 = -5

For C31, P31 = 3 + 3 – 8 = -2

For C32, P32 = 3 + 1 – 3 = 1

Rule: If all penalty values ​​are taken as zero or negative, it means that optimality has been reached and this answer is the final answer. However, if you get a positive value, it means that you need to continue the sum in the next step.

Find the biggest positive penalty here. The maximum value here is 6, which corresponds to cell C21. This cell is now the new base cell. This cell is also included in the solution.

Rules for drawing closed paths or loops. Start with a new base cell and draw a closed path so that only the assigned cell or the new base cell has a right-angle rotation. See the image below.

Assign an alternative plus or minus sign to all cells that bend (or corner) at right angles in the loop, and assign a plus sign to the new base cell.

Consider a cell with a negative sign. Compare the assigned values ​​(200 and 250 in this case) and select the minimum value (that is, select 200 in this case). Then subtract 200 from the cells with the minus sign and add 200 to the cells with the plus sign. Then draw a new iteration. Now that we're done with the loop, the new solution looks like this:

Make sure that the total number of allocated cells is equal to (m + n – 1). Again, use the expression ui + vj = Cij to find the u and v values. Where Cij is the cost value for the assigned cell only. Assigning u1 = 0 yields v2 = 1. Similarly, for ui and vj you get the following values:

Use the formula Pij = ui + vj – Cij to find penalties for all unassigned cells.

For C11, P11 = 0 + (-3) – 3 = -6

For C13, P13 = 0 + 0 – 7 = -7

For C14, P14 = 0 + (-1) – 4 = -5

For C24, P24 = 5 + (-1) – 9 = -5

For C31, P31 = 0 + (-3) – 8 = -11

For C32, P32 = 3 + 1 – 3 = 1

There is one positive value. That is, 1 for C Now this cell becomes new basic cell.

Then draw a loop starting from the new base cell. Assign alternative plus and minus signs using the new base cell assigned as a plus sign.

Select the minimum value from the values ​​assigned to the cells marked with a minus sign. Subtract this value from the cell with the minus sign and add it to the cell with the plus sign. The solution now looks like the following image. Check if the total number of allocated cells is equal to (m + n – 1). Find the values ​​of u and v as above.

Now find the penalty for the unallocated cell again, as described above.

When P11 = 0 + (-2) – 3 = -5

When P13 = 0 + 1 – 7 = -6

When P14 = 0 + 0 – 4 = -4

When P22 = 4 + 1 – 6 = -1

When P24 = 4 + 0 – 9 = -5

When P31 = 2 + (-2) – 8 = -8

All penalty values ​​are negative. Therefore, optimality is reached.

Here you find the total cost, that is, (250 * 1) + (200 * 2) + (150 * 5) + (50 * 3) + (200 * 3) + (150 * 2) = 2450.

• Maximum Two Iterations (i.e., Maximum Two Loops) after IFS.

Use Vogel’s method to find an initial basic feasible solution and then find the minimum transportation cost for the following transportation problem by Modi method.

Solution:

Step I: Find the initial basic feasible solution

The initial basic feasible solution obtained by applying Vogel’s approximation method is shown below.

Step II Perform Optimality Test

Required number of allocations = m+n-1= 3+4-1 =6=Actual number of allocations. Therefore, optimality test can be performed. 

Now, we use Modi for the optimality test.

Now we find the value uj and vj by the relation uj+vj=Cj

For the basic cell (1,1): u1+ v1=1

For the basic cell (1,3): u1+ v3=1

For the basic cell (2,2): u2+ v2=3

For the basic cell (2,3): u2+ v3=2

For the basic cell (2,4): u2+ v4=1

For the basic cell (3,2): u3+ v2=2

   Then, let v1=0, then we get 

V2 =1; v3=0; v4=-1; u1=1; u2=2; u3=1.Now displaying these values in the table and calculate the cell evaluation.

Iteration 1

Now, subtracting the cell values of the above matrix from the original cost matrix;

Iteration 2

Step III:  Since all cell evaluations are positive, the initial basic feasible solution is optimal.

The minimum transportation cost is given by=1x20+1x10+3x20+2x20+1x10+2x20=180.

Key takeaways:

1. There are certain types of transport problems that need to be maximized rather than minimized in the objective function. These problems can be solved by converting the maximization problem to the minimization problem.
2. There may be a solution that can only be implemented if the transportation problem is a balanced problem.
3. Imbalanced issues can be balanced by adding dummy supply centers (rows) or dummy demand centers, depending on your requirements.
4. However, these imbalanced T.P.S needs to be transformed because the aggregate supply must be equal to the aggregate demand for a viable solution to exist for a well-balanced one.
5. If supply exceeds demand, introduce a dummy demand center (additional destination column) in the transportation problem to absorb the excess supply.
6. The unit cost of transportation for cells in the dummy row is set to zero.
7. There are several methods available to get the first basic viable solution to your shipping problem.
8. Only the following three are discussed here. To find the first basic viable solution, the total supply should be equal to the total demand.
9. There are two steps to solving a transportation problem. The first phase requires finding the first basic viable solution, and the second phase optimizes the first basic viable solution obtained in the first phase.
10.  There are three ways to find the first basic viable solution.
11. Vogel’s method can be used to find an initial basic feasible solution.
12. Modi method can be used to find the minimum transportation cost

References:

1. Hakim, Akmal. (2019). Solving Transportation Problem using Vogel's Approximation Method, Stepping Stone Method & Modified Distribution Method.
2. N. Balakrishnan, Modified Vogel’s Approximation method for unbalanced transportation problem. Applied Mathematics Letters 3 (2), 9-11, 1990
3. Shweta Singh, G.C. Dubey, Rajesh Shrivastava, Optimization and analysis of some variants through Vogel’s approximation method (VAM). IOSR Journal of Engineering (IOSRJEN) Volume 2, Issue 9 (September 2012), PP 20-30.
4. Abdul Sattar Soomro, Muhammad Junaid, Gurudeo Anand Tularam, Modified Vogel’s Approximation Method for Solving Transportation Problems. Mathematical Theory and Modelling ISSN 2224-5804 (Paper)Vol.5, No.4, 2015
5. Koliński, Adam & Koliński, Marek. (2013). The use of Hungarian method in the evaluation of production efficiency.