Course 5 : Transportation Problem

Author: OptimizationCity Group

Introduction

So far, we have studied the problem of linear programming in general. In this section, we will examine specific types of linear programming problems. In this section, we first examined the general model of minimum cost flow, and then we will examine the specific model of flow in the network, here the transportation problem.

Minumum cost flow problem

In the problem of minimum cost flow, we are looking for homogeneous product distribution from the factory (origin) to the sales market (destination). Suppose the number of products manufactored in each factory and the number of required products are known. Also, it is not necessary to send the products directly to the destinations, but it is possible to send it to the distribution centers through an intermediate point. In addition, transportation lines are limited in terms of line capacity. The goal in this issue is to minimize the cost of transporting products.

Consider a numerical example of the minimum cost flow problem in the figure below. Nodes are represented by numbered circles and arcs by arrows. Arcs are directional. For example, materials can be sent from node 1 to node 2, but this is not possible from node 2 to node 1. We denote the arc from node i to node j as i-j.

In the above figure, each arc is given a capacity and cost per unit of transportation, which is given next to each arc. For example, in arc (2-4), the flow can be from 0 to 4 units, and the cost of each unit passing through this arc is $2. The symbol ∞ means unlimited capacity. Finally, the numbers in parentheses next to the nodes show the amount of supply and demand. In this figure, node 1 is the origin and the amount of supply is equal to 20 units, and nodes 4 and 5 are the destinations that need 5 and 15 units, and it is the demand that is indicated by the sign -.

In the minimum cost flow problem, the goal is to find the flow pattern with minimum cost. To transform the problem into linear programming, suppose:

x_ij: is the number of units transported from node i to node j using arc i-j.

The linear programming model of minimum cost flow is presented as follows.

Equations 1 to 5 are the flow balance equations in the network. For example, the balance flow equation at node 1 is as follows.

The above equation states that the output flow from node 1 (x₁₂+x₁₃) should be equal to the supply of node 1 (20).

The balance equation in node 2 states that the input flow to node 2 (x₁₂ ) is equal to the output flow from node 2 (x₂₃+x₂₄+x₂₅ ).

The minimum cost flow model in the network has a special structure that is used to provide the solution order. Flow variables x_ij in balance equations only get 0, +1 and -1 coefficients. In addition, they appear exactly in two balance equations: once with a coefficient of +1 corresponding to the node from which they originate and -1 corresponding to the node to which they enter. According to the above, the general form of the Minumum Cost Flow is expressed as follows.

The above model is the general model of minimum cost flow. The above model can be converted into simpler forms, which we will describe below.

Transportation problem

The transportation problem is a type of minimum cost flow problem where there are no intermediate points (such as nodes 2 and 3 in the general form). To express the mathematical form of the transportation problem, the following parameters are defined.

a_i: the amount of supply in source i (i=1,…,m)

b_j: the amount of demand in destination j (j=1,…,n)

c_ij: transportation cost of each unit from source i to destination j (i=1,…,m, j=1,…,n)

It is assumed that the total amount of supply in sources is equal to the amount of demand in destinations, that is:

If the above assumption is not valid, the above assumption can be considered with changes. We will get to that later.

If x_ij is equal to the number of units transported from source i to destination j, then the transportation problem can be formulated as follows:

Example:

The products of a large canning company are produced in three factories and transported by truck to four warehouses. Because the cost of transportation is a significant amount, therefore, the management seeks to minimize the cost of transportation. The information about the shipping cost is given in the following table:

The linear programming model of the above problem is expressed as follows.

Presenting the simplex method for the transportation problem

Since the transportation problem is a special case of the linear programming problem, it can be solved using the simplex method. But since the structure of the transportation problem is specific, the optimal solution can be obtained by a simpler method. Instead of using the simplex table to find the optimal solution, the following table can be used to store the information of the simplex table in the transportation problem.

If a variable is basic or non-basic, the information of each cell is determined as follows.

Initial step:

In this step, we get a basic feasible solution. In the transportation problem, there are different methods to produce the initial solution, which are presented below.

North west corner rule

First, select the variable x₁₁, which is considered as the basic variable. In the following, if x_ij is the basic variable, then if the supply of source i is not finished, we will choose variable x_ij+1 and otherwise we will choose variable x_i+1j as the basic variable.

For example, consider the simplex table below. According to this rule, the initial basic solution is produced as follows.

The initial basic solution is as follows.

Vogel’s Approximation Method

The previous method does not take cost into account, but methods that do not take cost into account can lead to solutions where the total cost is too high. The Vogel’s approximation method is proposed to solve this problem and it is so effective that it is sometimes used to obtain an approximate optimal solution. Vogel’s approximation method works by calculating the difference between the smallest and the previous smallest cost for each row or column that is still under review. In the row or column where the difference is the largest, it selects the variable that has not been deleted and whose unit cost is the lowest.

To clarify the issue, obtain the initial basic solution of the following simplex table using the Vogel’s approximation method.

Iteration 1

Column 4 is omitted and x₄₄ =30 is considered.

Iteration 2

Row 4 is omitted and x₄₅ =20 is considered.

Iteration 3

Row 1 is omitted and x₁₃ =50 is considered.

Iteration 4

Column 5 is omitted and x₂₅ =40 is considered.

Iteration 5

Column 3 is omitted and x₂₃ =20 is considered.

Iteration 6

This is the final table and x₃₃=0,x₃₂=20,x₃₁=30.

The initial basic solution for the transportation problem is as follows.

Stopping condition

The purpose of the stopping condition is to test the optimality of the current feasible basic solution. A feasible basic solution is optimal if and only if the relation 0 ≤c_ij-u_i-v_j holds for all non-basic variables x_ij.

To control the above conditions, the value of u_i and v_j should be calculated. If the x_ij variable is basic, then c_ij=u_i+v_j will be, and u_i and v_j can be calculated by solving the equations for the basic variables. Due to the fact that the number of variables is one more than the number of equations, to find the solution, one of the variables should be equal to the desired value and get the value of the other variables.

To illustrate this, if the basic variables are x₃₁, x₃₂, x₃₄, x₂₁, x₂₃, x₁₃, x₁₅, and x₄₅, then we have:

If we put u₃=0 (because u₃ has the most presence in the equations), the values of other variables are obtained as follows.

By having the value of the dual variables, the optimality conditions can be controlled.

Iterative step

In this step, we identify the input basic variable and the output basic variable. In the simplex method of the transportation problem, we consider the variable that has the most negative value c_ij-u_i-v_j as the input basic variable. Based on the values, the simplex table of the transportation problem is as follows.

In the above table, variable x₂₅ has the lowest c_ij-u_i-v_j value and is selected as the input variable. To find the basic output variable from the base, the following method is used.

In the above figure, the value of θ must be increased so that the cost of the arc is not negative, then we will have:

By increasing the value of θ by 10, the variable x₁₅ is removed from the basic solution, and x₁₅ is the output basic variable. In this case, the basic solution is as follows.

Before solving the examples, we will continue with the formal presentation of the simplex method for the transportation problem:

Initial step: Obtain the initial basic feasible solution using North west corner rule or Vogel’s approximation.

Stopping condition: Solve the equations c_ij=u_i+v_j for basic variables and get the value of dual variables u_i and v_j. If the relation cij-ui-vj≥0 holds for all the non-basic variables, then the current basic solution is optimal, otherwise go to the iterative step.

Iterative step:

Part 1: Consider the non-basic variable x_ij which is the most negative value of c_ij-u_i-v_j as the input basic variable.

Part 2: Determine the output basic variable.

Part 3: Determine the new basic solution.

Go to stopping condition step.

Inequality of supply and demand

Total supply is greater than total demand

When the amount of total supply is greater than the total demand, i.e.

a virtual demand point with a demand amount equal to

should be added to the transportation table. The costs of transporting each unit of goods from this virtual point, because no goods are really transported, are considered zero.

total demand is greater than total supply

When the amount of total supply is less than the amount of total demand, i.e.

a virtual row with a capacity equal to

should be added to the transportation table. The costs of transporting each unit of goods to this virtual point, because no goods are really transported, are considered zero.

Solving non-standard transportation problem

In the transportation algorithm, the basic assumption is the equality of the total amount supply and demand. For the case where the assumption is not valid, adding a virtual point (row or column in the table) converts the problem into standard format.

There are other non-standard forms, such as the impossible cell. It is a situation where it is almost impossible to send the goods between the origin and the destination, which is caused by the lack of a road between the origin and the destination or the long distance between the two them. Another non-standard form occurs when the supply capacity at the origin has a certain range. This case means that the amount of supply is between two upper and lower limits. In this regard, demand can also have a certain range. We discuss this form as the bounded capacity in the later.

Impossible cell

Sometimes in real world issue, there is a situation where it is not possible to send goods from a specific orgine to a specific destination. Not using a route is done by assigning a cost equal to M to the cell that represents that route in the transportation problem table. M is a large number that represents the cost of transporting a unit of goods. In the transportation method, a value is not assigned to a cell that has a cost equal to M because the goal of the algorithm is to minimize the cost, and the variable related to that cell remains non-basic in the final table.

bounded capacity

Consider a transportation problem that has an origin with the capacity.

Suppose the first factory can double or triple its capacity by adding second and third shifts and can easily shut it down when necessary. By adding this new assumption, the first factory has a capacity equal to C₁, which:

The main capacity (without adding the second and third shifts) is considered as the lower limit. The upper bound of the capacity in case of adding a new line has been modified in the table below (by adding line 1-2).

The main capacity (without adding the second and third shifts) is considered as the lower bound. The upper bound of the capacity in case of adding a new line is exactly the same as the previous costs, and its supply amount is equal to the difference between the two bound (which is equal to 200 here). The addition of a new source increases supply over demand and requires a virtual node. Note that the virtual cell in row 1 is impossible and has a cost equal to M. This makes supply node 1 having a minimum capacity of 100. If this cell is not equal to M, it is possible that the flow from node 1 to the virtual node exists and the supply node 1 no longer serves demand nodes 1,2,3, and 4. Therefore, supply node 1 can produce 100 units of goods in the first shift and 200 units of goods in the next added shifts (line 1-2).

bounded demand

As before, a transportation problem can have a limited demand.

Example: Consider the previous problem again without considering the additional shifts for supply node 1. Suppose the demand for node 1 (column 1) changes between two bound of 100 and 250, that is, the value of D₁ is between 100 and 250.

The revised table with the addition of the new column 1-2 is as follows.

The demand for node 1 is equal to 100. Node 1-2 represents the surplus demand in addition to the minimum demand of node 1, which is 100. The costs of transporting to node 1-2 (column 1-2) are the same as the costs of transporting to node 1 (column 1), and the demand node 1-2 is equal to 250-100=150 (the difference between the upper bound and the lower bound). The virtual node has a capacity equal to 100, which is considered to balance supply and demand.

There should be no flow between destination node 1 and virtual node. Therefore the cost of this cell is M. Why M? If a flow is established from the virtual node to the node 1, this flow does not actually exist, and nodes 1 and 1-2 send 150 units of flow, which is more than the lower bound and the values ​​between the lower bound (100) and 150 are not covered. This setting guarantees the minimum input to node 1 being 100.

Production with different costs

Consider the following transportation problem.

Suppose that the production cost of three factories is different due to differences in the cost of manpower, equipment and raw materials. The goal is to distribute the production of factories among four warehouses in such a way that the total cost of production and transportation is minimized. If the production cost of each product unit in three factories is equal to 50, 62, and 54, respectively, the transportation and production cost will be by adding the production costs to the transportation costs of each unit. The optimal solution for this situation is shown in the figure below.

Selling with different costs

In some cases, the product of the same factory can be sold in different markets at different prices. The selling price of each product unit to the four warehouses of the previous problem is equal to 100, 105, 110, and 115 respectively. Due to the fact that we are looking to minimize the cost in the transportation problem, the selling price is considered with a negative sign, so each of the numbers inside the upper small rectangles is the difference between the selling price of each unit (negative), and the shipping cost. and production (positive).

Note: The optimal solution in this table is exactly the same as the solution presented in the initial case and production with different costs case. Adding a fixed value to the cost in the columns does not change the optimal solution.

Example:

A canning company has factories in three locations: Chicago, Cleveland, and Boston. Last week, the production of these three factories was 35, 50, and 40 units, respectively. The company wants to ship 45 units to Dallas, 20 to Atlanta, 30 to San Francisco, and another 30 to Philadelphia. The cost of production and transportation of each factory to each distribution center is shown in the table below. What is the best shipping method?

Solution:

Initial step::

1- North-west corner method

The initial basic solution by the north-west corner rule with the objective function z=1180 is as follows.

2 – Vogel’s approximation method

The application of Vogel’s approximation method to find the initial basic solution is as follows.

Iteration 1

Column 4 is omitted and x₃₄=30 is considered.

Iterations 2

Row 3 is omitted and x₃₂=10 is considered.

Iteration 3

Column 2 is o omitted and x₁₂=10 is considered.

Iteration 4

Column 1 is omitted and x₂₁=45,x₁₃=25,x₂₃=5 are considered. Therefore, the basic solution of Vogel’s approximation is as follows.

X₃₄=30,x₃₂=10,x₁₂=10,x₂₁=45,x₁₃=25,x₂₃=5

Then, the value of the objective function is equal to Z=1020.

From the comparison of the objective function value of the northwest corner rule and Vogel’s approximation, we can understand that the Vogel’s approximation leads to the basic solution with a better objective function. Therefore, the initial solution used in the algorithm is as follows.

Stopping condition: Assuming u₁=0, the value of dual variables is as follows:

In the following table, the value of c_ij-u_i-v_j for non-basic variables is calculated.

Because there is no non-basic variable that c_ij-u_i-v_j < 0, so we reached the optimal solution. It can be seen that Vogel’s approximation leads to the optimal solution.

For further practice, assume that the initial solution is given as follows:

Stopping condition: Assuming u₁=0, the value of dual variables is as follows:

In the table below, the value of c_ij-u_i-v_j is calculated for non-basic variables.

Iterative step: because c_ij-u_i-v_j < 0 for two non-basic variables, therefore the basic solution of the current solution is not optimal and we need to find an improved solution. We consider x₁₃ as the input variable. To find the output variable, it is done as follows.

Therefore, the basic variable x₁₁ is removed from the base and the non-basic variable x₁₃ is included in the base. Therefore, the current basic solution is as follows.

Stopping condition:

Assuming u₁=0, the value of the dual variables can be calculated as follows.

In the following table, the values of c_ij-u_i-v_j of non-basic variables are given.

Iterative step: The non-basic variable x₃₂ enters the base. To determine the output variable from the base, we act as follows.

With θ=10, the basic variable x₃₃ leaves the base and the non-basic variable x₃₂ enters the base. Therefore, the basic solution is as follows.

Stopping condition: Assuming u₁=0, the value of dual variables can be calculated as follows.

In the following table, the values of c_ij-u_i-v_j of non-basic variables are given.

The optimality condition is satisfied and therefore the current basic solution is optimal.

Example:

The transportation problem with the transportation cost table is assumed. Find an intial basic solution using the northwest corner rule and the Vogel’s approximation method. Compare the number of simplex iterations in each of the two initial solutions.

Solution:

A) Northwest corner rule:

The objective function value of the above table is equal to 48. The value of c_ij-u_i-v_j for non-basic variables is as follows.

The variable x₃₂ is considered as the basic input variable. To determine the basic output variable, we proceed as follows.

The variable x₂₂ should be considered as the output variable, in which case the current basic solution will be as follows.

Assuming u₁=0, other dual variables are as follows:

The value of the objective function in this iteration is equal to 42. The value of c_ij-u_i-v_j for non-basic variables is as follows.

One of c_ij-u_i-v_j is negative, so the optimality condition is not satisfied. x₁₃ variables are entered into basic variables.

With θ=0 variable x₃₃ leaves the basic solution and variable x₁₃ enters the basic solution. Therefore, the basic solution is as follows.

The value of the objective function in this iteration is equal to 42. The value of c_ij-u_i-v_j for non-basic variables is as follows.

We use the following table to control the optimality.

The x₁₄ variable should be considered as the input variable to the basic answer. The output variable from the base is obtained as follows.

By setting θ = 2, the variable x₁₂ is removed from the basic solutions and the basic solution is as follows.

The value of the objective function of the above basic solution is equal to 32. Assuming u₁=0, other dual variables are as follows:

We use the following table to control the optimality.

Considering that the non-basic arcs have a non-negative value, we reached the optimal solution. The value of the objective function is equal to 32. The number of iterations to reach the optimal solution is equal to 3.

Due to the fact that c_ij-u_i-v_j for all the non-basic arcs are positive, we reach the optimal solution. The value of the objective function is equal to 32. The number of iterations to reach the optimal solution is equal to 3.

b) The initial solution using Vogel’s approximation method is as follows.

x₂₃=2

x₃₂=3

x₁₃=0

The solution obtained from Vogel’s approximation is as follows.

The values of dual variables are as follows:

The value of c_ij-u_i-v_j for non-basic variables is as follows.

As can be seen, c_ij-u_i-v_j is non-negative for all non-basic variables and therefore we reached the optimal solution. The number of iterations to reach the optimal solution with the Vogel’s approximation method is equal to one.