Transportation Problem

Transportation Method

A transportation tableau is given below. Each cell represents a shipping route (which is an arc on the network and a decision variable in the LP formulation), and the unit shipping costs are given in an upper right hand box in the cell.

To solve the transportation problem by its special purpose algorithm, the sum of the supplies at the origins must equal the sum of the demands at the destinations (Balanced transportation problem).

• If the total supply is greater than the total demand, a dummy destination is added with demand equal to the excess supply, and shipping costs from all origins are zero.

• Similarly, if total supply is less than total demand, a dummy origin is added. The supply at the dummy origin is equal to the difference of the total supply and the total demand. The costs associated with the dummy origin are equal to zero.

When solving a transportation problem by its special purpose algorithm, unacceptable shipping routes are given a cost of +M (a large number).

Develop an Initial Solution

Two methods to get the initial solution:

• Northwest Corner Rule

• Minimum Cell-Cost Method

Northwest Corner Rule

1. Starting from the northwest corner of the transportation tableau, allocate as much quantity as possible to cell (1,1) from Origin 1 to Destination 1, within the supply constraint of source 1 and the demand constraint of destination 1.

2. The first allocation will satisfy either the supply capacity of Source 1 or the destination requirement of Destination 1.

ƒ If the demand requirement for destination 1 is satisfied but the supply capacity for Source 1 is not exhausted, move on to cell (1,2) for next allocation.

ƒ If the demand requirement for destination 1 is not satisfied but the supply capacity for Source 1 is exhausted, move to cell (2,1)

ƒ If the demand requirement for Destination 1 is satisfied and the supply capacity for Source 1 is also exhausted, move on to cell (2,2).

3. Continue the allocation in the same manner toward the southeast corner of the transportation tableau until the supply capacities of all sources are exhausted and the demands of all destinations are satisfied.

Initial tableau developed using Northwest Corner Method

Total Cost = 12(400)+13(100)+4(700)+9(100)+12(200)+4(500)= 142,000

Minimum Cell-Cost Method

Although the North-west Corner Rule is the easiest, it is not the most attractive because our objective is not included in the process.

Steps of Minimum Cell-Cost Method

1. Select the cell with the minimum cell cost in the tableau and allocate as much to this cell as possible, but within the supply and demand constraints.

2. Select the cell with the next minimum cell-cost and allocate as much to this cell as possible within the demand and supply constraints.

3. Continue the procedure until all of the supply and demand requirements are satisfied. In a case of tied minimum cell-costs between two or more cells, the tie can be broken by selecting the cell that can accommodate the greater quantity.

Initial tableau developed using Minimum Cell-Cost Method

Total Cost = 12(300)+4(200)+4(700)+10(100)+9(200)+4(500)= 120,000

MODI Method (for obtaining reduced costs)

Associate a number, ui, with each row and vj with each column.

• Step 1: Set u1 = 0.

• Step 2: Calculate the remaining ui's and vj's by solving the relationship cij

= ui + vj for occupied cells.

• Step 3: For unoccupied cells (i,j), the reduced cost = cij - ui - vj.

Step 1: For each unoccupied cell, calculate the reduced cost by the MODI method. Select the unoccupied cell with the most negative reduced cost. (For maximization problems select the unoccupied cell with the largest reduced cost.) If none, STOP.

Step 2: For this unoccupied cell, generate a stepping stone path by forming a closed loop with this cell and occupied cells by drawing connecting alternating horizontal and vertical lines between them. Determine the minimum allocation where a subtraction is to be made along this path.

Step 3: Add this allocation to all cells where additions are to be made, and subtract this allocation to all cells where subtractions are to be made along the stepping stone path. (Note: An occupied cell on the stepping stone path now

becomes 0 (unoccupied). If more than one cell becomes 0, make only one unoccupied; make the others occupied with 0's.)

GO TO STEP 1.

Example: Acme Block Co. (ABC)

Acme Block Company has orders for 80 tons of concrete blocks at three suburban locations as follows: Northwood -- 25 tons, Westwood -- 45 tons, and Eastwood -- 10 tons. Acme has two plants, each of which can produce 50 tons per week. Delivery cost per ton from each plant to each suburban location is shown below.

How should end of week shipments be made to fill the above orders?

Since total supply = 100 and total demand = 80, a dummy destination is created with demand of 20 and 0 unit costs.

Iteration 1: Tie for least cost (0), arbitrarily select x14. Allocate 20. Reduce s1 by 20 to 30 and delete the Dummy column.

Iteration 2: Of the remaining cells the least cost is 24 for x11. Allocate 25. Reduce s1 by 25 to 5 and eliminate the Northwood column.

Iteration 3: Of the remaining cells the least cost is 30 for x12. Allocate 5. Reduce the Westwood column to 40 and eliminate the Plant 1 row. Iteration 4: Since there is only one row with two cells left, make the final allocations of 40 and 10 to x22 and x23, respectively.

1. Set u1 = 0

2. Since u1 + vj = c1j for occupied cells in row 1, then v1 = 24, v2 = 30, v4 = 0.

3. Since ui + v2 = ci2 for occupied cells in column 2, then u2 + 30 = 40, hence u2 = 10.

4. Since u2 + vj = c2j for occupied cells in row 2, then 10 + v3 = 42, hence v3 = 32.

Calculate the reduced costs (circled numbers on the previous slide) by cij - ui - vj.

Unoccupied Cell Reduced Cost (1,3) 40 - 0 - 32 = 8 (2,1) 30 - 24 -10 = -4 (2,4) 0 - 10 - 0 = -10

Iteration 1:

The stepping stone path for cell (2,4) is (2,4), (1,4), (1,2), (2,2). The allocations in the subtraction cells are 20 and 40, respectively. The minimum is 20, and hence reallocate 20 along this path. Thus for the next tableau:

x24 = 0 + 20 = 20 (0 is its current allocation) x14 = 20 - 20 = 0 (blank for the next tableau) x12 = 5 + 20 = 25

x22 = 40 - 20 = 20

The other occupied cells remain the same.

1. Set u1 = 0.

2. Since u1 + vj = cij for occupied cells in row 1, then v1 = 24, v2 = 30.

3. Since ui + v2 = ci2 for occupied cells in column 2, then u2 + 30 = 40, or u2 =

10.

4. Since u2 + vj = c2j for occupied cells in row 2, then 10 + v3 = 42 or v3 = 32;

and, 10 + v4 = 0 or v4 = -10.

Iteration 2

Calculate the reduced costs (circled numbers on the previous slide) by cij - ui - vj.

Unoccupied Cell Reduced Cost (1,3) 40 - 0 - 32 = 8 (1,4) 0 - 0 - (-10) = 10 (2,1) 30 - 10 - 24 = -4

The most negative reduced cost is = -4 determined by x21. The stepping stone path for this cell is (2,1),(1,1),(1,2),(2,2). The allocations in the subtraction cells are 25 and 20 respectively. Thus the new solution is obtained by reallocating 20 on the stepping stone path. Thus for the next tableau:

x21 = 0 + 20 = 20 (0 is its current allocation)

x11 = 25 - 20 = 5

x12 = 25 + 20 = 45

x22 = 20 - 20 = 0 (blank for the next tableau)

The other occupied cells remain the same.

1. Set u1 = 0

2. Since u1 + vj = c1j for occupied cells in row 1, then v1 = 24 and v2 = 30.

3. Since ui + v1 = ci1 for occupied cells in column 2, then u2 + 24 = 30 or u2 =6.

4. Since u2 + vj = c2j for occupied cells in row 2, then 6 + v3 = 42 or v3 = 36, and 6 + v4 = 0 or v4 = -6.

Iteration 3

Calculate the reduced costs (circled numbers on the previous slide) by cij - ui - vj.

Unoccupied Cell Reduced Cost

(1,3)	40 - 0 - 36 =	4
(1,4)	0 - 0 - (-6) =	6
(2,2)	40 - 6 - 30 =	4

Since all the reduced costs are non-negative, this is the optimal tableau.

Assignment Problem

What is Assignment Problem ?

The assignment problem is a special type of linear programming problem where assignees are being assigned to perform tasks or Jobs. For example, the assignees might be employees who need to be given work assignments. Assigning people to jobs is a common application of the assignment problem. However, the assignees need not be people. They could be machines, or vehicles, or plants, or even time slots to be assigned tasks.

To fit the definition of an assignment problem, these kinds of applications need to be formulated in a way that satisfies the following assumptions:

(i) The number of assignees and the number of tasks are the same (Balanced).

(ii) Each assignee is to be assigned to exactly one task.

(iii) Each task is to be performed by exactly one assignee.

(iv) There is a cost associated with assignee i performing task j

(v) The objective is to determine how all assignments should be made to minimize the total cost.

The general assignment model with n assignees and n tasks is presented as follows:

	Tasks
		1	2	……	n	1
Assignee	1					1
	2
	: : :	: : :	: : :	: : :	: : :	: : :
	n					1
	1	1	1		1

The assignment model is actually a special case of the transportation model in which the assignees represent the sources, and the tasks represent the destinations. In effect, the assignment model can be solved directly as a regular transportation model. Nevertheless, the fact that all supply and demand amounts equal 1 has led to the development of a simple solution algorithm called the Hungarain method. Although the new method appears totally unrelated to the transportation model, the algorithm is actually rooted in the simplex method, just as the transportation model is.

Mathematical Formulation of the problem

Let = 0, if the task not assigned to assignee

= 1, if the task assigned to assignee

The objective of the model is to determine the unknowns that minimize the overall cost:

Minimize

Subject to the constraints

for all i and j

The Assignment Algorithm – Hungarian method

The steps of the assignment algorithm are as follows:

Step 1: For the original cost matrix, identify each row’s minimum, and subtract it from all the entries of the row.

Step 2: For the matrix resulting from step 1, identify each column’s minimum, and subtract it from all the entries of the column.

Step 3: Assign the zeroes:

(a) Examine the rows of the current matrix successively until a row with exactly one unmarked zero is found. Circle this zero, indicating that an assignment will be made there. Cross out all other zeroes lying in the column of above encircled zero. The crossed cells will not be considered for any future assignment. Continue this manner until all the rows have been taken care of.

(b) Similarly for column.

Step 4: Check for Optimality: Repeat step 3 successively till one of the following occurs.

(a) There is no row and no column without assignment. In such a case, the current assignment is optimal.

(b) There may be some row or column without assignment. In this case, the current solution is not optimal. Proceed to next step.

Step5: Draw minimum number of lines crossing all zeroes as follows: If the number of lines equal to the order of the matrix, then the current solution is optimal, otherwise it is not optimal. Proceed to the next step.

Step6: Examine the elements that do not have a line through them. Select the smallest of these elements and subtract the same from all the elements that do not have a line through them, and add this element to every element that lies in the intersection of the two lines. Repeat this until an optimal assignment is reached.

Example 3.4:

Joe’s three children – John, Karen and Terri – want to earn some money to take care of personal expenses during a school trip to the local zoo. Joe has chosen three tasks for his children: mowing the lawn, painting the garage, and washing the family cars. To avoid anticipated sibling competition, he asked them to summit (secret) bids for what they feel was a fair pay for each of the three tasks. The understanding then was that all three children would abide their father’s decision as to who gets which tasks. The following table summarizes the bids received.

	Mow	Paint	Wash
John	15	10	9
Karen	9	15	10
Terri	10	12	8

Based on this information, how should Joe assign the tasks?

Solution:

Let and be row i and column j minimum costs as defined in step 1 and 2 respectively.

	Mow	Paint	Wash	Row minimum
John	15	10	9
Karen	9	15	10
Terri	10	12	8

	Mow	Paint	Wash
John	6	1	0
Karen	0	6	1
Terri	2	4	0
Column minimum

	Mow	Paint	Wash
John	6	0	0
Karen	0	5	1
Terri	2	3	0

The cells with underscored zero entries provide the optimum solution. The total cost is 9 + 10 + 8 = 27. This amount also will always equal .

Unbalanced Assignment Problem

When the cost matrix of an assignment problem is not a square matrix (# of assignees is not equal to the # of tasks), the assignment is called an unbalanced assignment problem. In such problems, dummy rows or columns are added in the matrix so as to complete it to form a square matrix.

Linear Programming Problems

Definition :   Suppose that one is given a linear function of n real variables

z = f (x₁, x₂,..., x_n) = c₁x₁ + c₂x₂ +...+ c_nx_n

and a set of linear inequalities and/or equations, called constraints

(1.1)

where in each line either , = or occurs. The problem of finding  (x₁, x₂,..., x_n), that satisfies the constraints (1.1) and makes z a maximum (or minimum) is called a Linear Programming Problem .

We shall assume that every Linear Programming Problem has included in its constraints, the non-negativity restrictions

x_j0   
(1.2)

and these will be written separately from the other constraints. These non-negativity constraints are sometimes known as reality constraints. In examples they typically represent quantities that for physical reasons are non-negative.

Any set of values of x₁, x₂,..., x_n satisfying the constraints (1.1) and inequalities (1.2) is called a feasible solution. The set of feasible solutions is the feasible region. Somewhat perversely, any set of values of x₁, x₂,..., x_n satisfying the constraints (1.1) but not (1.2) is called a non-feasible solution.

The function f is called the objective function and z the objective variable. If set of values of x₁, x₂,..., x_n  is a feasible solution that makes f (x₁,..., x_n) a maximum (or minimum) then x is an optimal solution and the corresponding value of z is the optimal value.

Mathematical Formulation of Linear Programming Problems

There are mainly four steps in the mathematical formulation of linear programming problem as a mathematical model. We will discuss formulation of those problems which involve only two variables.

(1) Identify the decision variables and assign symbols x and y to them. These decision variables are those quantities whose values we wish to determine.

(2) Identify the set of constraints and express them as linear equations/inequations in terms of the decision variables. These constraints are the given conditions.

(3) Identify the objective function and express it as a linear function of decision variables. It might take the form of maximizing profit or production or minimizing cost.

(4) Add the non-negativity restrictions on the decision variables, as in the physical problems, negative values of decision variables have no valid interpretation.

There are many real life situations where an LPP may be formulated. The following examples will help to explain the mathematical formulation of an LPP.

01. A diet is to contain at least 4000 units of carbohydrates, 500 units of fat and 300 units of protein. Two foods A and B are available. Food A costs 2 dollars per unit and food B costs 4 dollars per unit. A unit of food A contains 10 units of carbohydrates, 20 units of fat and 15 units of protein. A unit of food B contains 25 units of carbohydrates, 10 units of fat and 20 units of protein. Formulate the problem as an LPP so as to find the minimum cost for a diet that consists of a mixture of these two foods and also meets the minimum requirements.

Suggested answer:

The above information can be represented as

Let the diet contain x units of A and y units of B.

    Total cost = 2x + 4y

The LPP formulated for the given diet problem is

Minimize Z = 2x + 4y

subject to the constraints

02. In the production of 2 types of toys, a factory uses 3 machines A, B and C. The time required to produce the first type of toy is 6 hours, 8 hours and 12 hours in machines A, B and C respectively. The time required to make the second type of toy is 8 hours, 4 hours and 4 hours in machines A, B and C respectively. The maximum available time (in hours) for the machines A, B, C are 380, 300 and 404 respectively. The profit on the first type of toy is 5 dollars while that on the second type of toy is 3 dollars. Find the number of toys of each type that should be produced to get maximum profit.

Suggested answer:

Mathematical Formulation

The data given in the problem can be represented in a table as follows.

Let x = number of toys of type-I to be produced

y = number of toys of the type - II to be produced

     Total profit = 5x + 3y

The LPP formulated for the given problem is:

Maximise Z = 5x + 3y subject to the constraints

Graphical Solution of Linear Programming Problem :

Let us take the following example :

minimise
    Z  =  180x + 160y
subject to
      6x + y >= 12
      3x + y >= 8
      4x + 6y >= 24
      x <= 5
      y <= 5
      x,y >= 0

Since there are only two variables in this LP problem we have the graphical representation of the LP given below with the feasible region (region of feasible solutions to the constraints associated with the LP) outlined.

To draw the diagram above we turn all inequality constraints into equalities and draw the corresponding lines on the graph (e.g. the constraint 6x + y >= 12 becomes the line 6x + y = 12 on the graph). Once a line has been drawn then it is a simple matter to work out which side of the line corresponds to all feasible solutions to the original inequality constraint (e.g. all feasible solutions to 6x + y >= 12 lie to the right of the line 6x + y = 12).

We determine the optimal solution to the LP by plotting (180x + 160y) = K (K constant) for varying K values (iso-profit lines). One such line (180x + 160y = 180) is shown dotted on the diagram. The smallest value of K (remember we are considering a minimisation problem) such that 180x + 160y = K goes through a point in the feasible region is the value of the optimal solution to the LP (and the corresponding point gives the optimal values of the variables).

Hence we can see that the optimal solution to the LP occurs at the vertex of the feasible region formed by the intersection of 3x + y = 8 and 4x + 6y = 24. Note here that it is inaccurate to attempt to read the values of x and y off the graph and instead we solve the simultaneous equations

• 3x + y = 8
• 4x + 6y = 24

to get x = 12/7 = 1.71 and y = 20/7 = 2.86 and hence the value of the objective function is given by 180x + 160y = 180(12/7) + 160(20/7) = 765.71

Hence the optimal solution has cost 765.71

It is clear that the above graphical approach to solving LP's can be used for LP's with two variables but most LP's have more than two variables. This brings us to the simplex algorithm for solving LP's.