The Transportation Problem
There is a linear programming problem called the transportation problem that utilizes a simplified version of the simplex technique known as the transportation method. This method is commonly used to solve problems involving multiple sources and destinations for products, hence its name. It is particularly applicable in situations where products need to be transported from various sources to several destinations.
Although the formation can be used for various purposes, including representation of general assignment, scheduling, transportation, and distribution problems. Such problems typically have two common objectives:
- minimize the cost of shipping munits to n destinations or
- maximize the profit of shipping m units to n destinations. Let us assume there are m sources supplying n destinations. Source capacities, destinations requirements and costs of material shipping from each source to each destination are given constantly.
The transportation problem can be defined by the linear programming mathematical model and is typically presented in a transportation tableau. There are three main steps involved in solving transportation problems, which we will now explore using a straightforward example. Let’s assume a company with four factories that supply four warehouses and the management wants to find the most cost-effective shipping schedule for their weekly chest output.
The transportation tableau displays the unit shipping costs in small boxes within the cells. Upon initialization, all cells are empty. It is crucial to ensure that the total supply availabilities match the total demand requirements at this stage.
In cases of excess supply or demand, a dummy warehouse or factory needs to be added to make the transportation method effective. To do this, an extra row is inserted for an additional factory or an extra column is inserted for an ad warehouse. The amount of supply or demand needed for the “dummy” is equivalent to the difference between the totals of the row and column. In this particular situation, the following is applicable:
Total factory supply is 51.
Total warehouse requirements is 52.
To accommodate the difference, an additional factory needs to be added. The supply by the dummy factory would be the difference between the total supply and total requirements, which in this case is 1 (52 – 51 = 1). The cost values for this dummy factory would be set to zero so that there are no transportation costs incurred when units are sent there. This adjustment is similar to the simplex procedure of inserting a slack variable in a constraint inequality to convert it to an equation. Like in the simplex procedure, the cost of the dummy factory would be zero in the objective function.
Initial Feasible Solution
The process of allocating numbers to cells in order to meet supply and demand constraints is called the initial allocation process. This section discusses various methods for this task, such as the Northwest-Corner method, Least-Cost method, and Vogel’s approximation method (VAM). Table 7.3 displays a northwest-corner assignment where cells A-E, A-F, B-F, and so on were sequentially assigned. The total cost is calculated as 10*10 + 30*4 + 15*10 + 30*1 + 20*12 + 20*2 + 45*12 + 0*1 = 1220 ($).
The allocation algorithm used in this method does not consider costs. Table 7.4 displays the order of assignments, starting with Cell Dummy-E, then C-E, B-H, A-H, and so forth. The total cost is calculated by multiplying the quantities in each cell by their respective costs and summing them up: 30*3 + 25*6 + 15*5 +10*10 + 10*9 + 20*6. It is worth noting that this initial solution is very close to the optimal solution achieved by improving the starting solution using the northwest-comer method. The total cost for the optimal solution can be calculated as follows: 15*14 + 15*10 + 10*10 + 20*4 + 20*1 +40 *5+35 *7+0 *1 =1005 ($).
Develop Optimal Solution
The development of an optimal solution in a transportation problem requires the evaluation of each unused cell to determine if shifting into it is advantageous from a total-cost perspective. If it is beneficial, the shift is made, and this process is repeated. Once all cells have been evaluated and necessary shifts have been made, the problem is considered solved. TheStepping stone method is one approach to conducting this evaluation.
The early descriptions of the method included the term “stepping stone”, where unused cells were called “water” and used cells were called “stones”. This analogy compared the method to walking on a path of half-submerged stones. If the evaluation of any empty cell yields the same cost as the existing allocation, there is an alternate optimal solution (see Stepping Stone Method – alternate solutions). It is assumed that all other cells are optimally assigned. In these cases, management has flexibility and can consider nontransportation cost factors when determining the final shipping schedule.
Transportation problems may exhibit degeneracy, which occurs when the number of filled cells is less than the sum of the number of rows and columns minus one (m + n – 1). Degeneracy can occur during the initial allocation when the first entry in a row or column satisfies both the row and column requirements, or during the application of the Steppingstone method when the added and subtracted values are equal. To evaluate the achieved solution, some adjustments in the matrix are necessary due to degeneracy.
The adjustment involves inserting a value into an empty cell to create a closed path for evaluating other empty cells. This value is negligible in terms of cost but is necessary for procedural purposes. Typically represented by the Greek letter epsilon (–), the value functions like a real number but can be initially placed in any empty cell, regardless of row and column requirements.
Table 7.8 presents a degenerate transportation problem with an initial allocation in the Northwest Corner. The assignment of a value to the matrix is crucial as it enables the evaluation of multiple cells. Once the value of a has been assigned, it stays in the solution until it is subtracted or until a final solution is achieved. Although there is flexibility in deciding where to place a, it is efficient to position it in a way that allows for the evaluation of as many cells as possible without necessitating any shifting.
Transportation Problem with a Maximization as a Criterion A fictive corporation
A is contracted to provide motors for all tractors manufactured by Corporation B. Corporation B has four production locations in Central Europe: Prague, Warsaw, Budapest, and Vienna. The following quantities of tractors are planned to be produced at each location:
Prague: 9,000; Warsaw: 12,000; Budapest: 9,000.
Corporation A has three plants with different production capacities for motors.
Hamburg 8,000
Munich 7,000
Leipzig 10,000
Dresden 5,000
Due to varying production and transportation costs, the profit earned on each motor depends on the production and shipping locations. The transportation table in Table 7.9 provides estimates of the euro profit per motor unit. By applying the Stepping Stone method (modified for maximization), it is evident that no other transportation schedule can increase the profit. Therefore, the Highest – Profit initial allocation is also an optimal solution for this transportation problem.
The Transshipment Problem
The transshipment problem is a variation of the transportation problem. Unlike the transportation problem, the transshipment problem allows for shipping both into and out of the same node. In the transportation problem, shipments can only be made from supply points to demand points. In the transshipment problem, shipments can be made between supply points or between demand points. The distinction between supply points and demand points becomes blurred in the transshipment problem due to the ability to ship in both directions at a node.
By classifying nodes based on their net stock position, you can improve the clarity of designations. Nodes can be classified as excess (+), shortage (-), or 0. Transshipping can be a cost-effective option in certain cases, where units can be shipped to one city at a low cost and then transferred to other cities. This may be more economical than direct shipment. Let’s take the balanced transportation problem as an example. Picture 7.1 illustrates the net stock positions of three warehouses and four customers. Assuming transshipment is possible through Pilsen to both Innsbruck and Linz.
The shipping cost from Pilsen to Innsbruck is 300 euro, making it more cost-effective to ship from Warsaw to Innsbruck through Pilsen. The direct shipping cost is 950 euro, while the transshipping cost is 600 + 300 = 900 euro. Since the transportation cost from Pilsen to Innsbruck is also 300 euro, the transshipping cost per unit from Prague through Pilsen to Innsbruck amounts to 400 euro. Therefore, choosing transshipping from Prague through Pilsen is a cheaper option than directly shipping from Prague to Innsbruck.
There are two potential transformations to a transportation model. In the initial transformation, transform every excess node into a supply point and every shortage node into a demand point. Afterward, identify the most cost-effective shipping method, taking into account all transshipment options, from surplus nodes to shortage nodes.
Let’s perform the first conversion for the Picture 7.1 example. Because the transportation table includes Prague, Warsaw, and Vienna with excesses, they are considered the supply points. Additionally, because Krakow, Pilsen, Innsbruck, and Linz have shortages, they are considered the demand points. The cheapest cost from Warsaw to Innsbruck is 900 euro, with transshipment through Pilsen. Similarly, the cheapest cost from Prague to Innsbruck is 400 euro, also with transshipment through Pilsen.
The most affordable option to transport goods from supply points to demand points is through direct shipment. Table 7.11 displays the transportation table that achieves a balance for this transshipment problem. In a basic transportation network, it is simple to identify the cheapest routes from nodes with excess supply to nodes with a shortage. You can list all possible routes and choose the least expensive one. However, in a complex network with numerous nodes and arcs, listing all potential routes becomes challenging.
Table 7.11 “The Transshipment Problem After Conversion to a Transportation Model” explains that the second conversion of a transshipment problem to a transportation model does not involve finding all of the cheapest routes from excess nodes table to shortage nodes. Instead, it requires an increased number of supply and demand nodes compared to the first conversion. This is because the points where shipping can occur, both from and to, appear twice in the converted transportation problem – once as a supply point and again as a demand point.
The Assignment Problem
The assignment problem is a transportation problem that can be used for assigning tasks to people or jobs to machines. It can also be used for awarding contracts to bidders. In this specific problem, there are n tasks allocated to n people. Each person is responsible for one task, and each task is performed by only one person. Each person and task is represented by a node, with individuals numbered from 1 to n and tasks numbered from 1 to n.
The assignment problem can be expressed through both a verbal model and a mathematical model using linear programming. For instance, let’s consider the scenario where there are five groups of computer users that need training for five different software programs. The cost of training is influenced by the skill levels of the users and the specific assignments given. In a balanced assignment problem, where there are an equal number of people and tasks, all relationships are treated as equal and each person is assigned a task.
For an unbalanced assignment problem with more people than tasks, some people don’t have to do a task and the first class of constraints is of the type.
In general, the simplex method does not guarantee that the optimal values of the decision variables are integers. Fortunately, for the assignment model, all of the corner point solutions have integer values for all of the variables. Therefore, when the simplex method determines the optimal corner point, all of the variable values are integers and the constraints require that the integers be either 1 or 0 (Boolean).
7.8.1 Conversion to a Balanced Transportation Table
It’s not surprising that the variable values for corner point solutions to the assignment model are integers because the assignment model is a special case of the transportation problem, which also has integer variable values for every corner point. In the assignment model, there are n supply and demand points, with each supply point corresponding to a person and each demand point corresponding to a task. Additionally, each supply amount is 1 and each demand amount is 1, representing one of each person and one of each task.
The computer users assignment problem involves minimizing the total cost of training. Since there are 5 users and 5 software types, the transportation problem is balanced. The standard methods for finding the initial solution (Northwest-Corner method, Least-Cost method, or Vogel’s approximation method) can be used, along with the Stepping-Stone method, to develop an optimal solution.
Considering the transportation problem in terms of shipping goods between cities can be useful, but what really matters is the underlying mathematical structure. The assignment problem shares the same mathematical structure as the transportation problem, despite not being directly related to shipping quantities. It is worth noting that every feasible solution to the assignment problem will always have a high degree of degeneracy, with the number of nonzero variables always being n. In conclusion, the assignment problem and the transportation problem are linked by their shared mathematical structure.
The transportation problem is a specific type of linear programming problem. It is highly unlikely that a linear programming problem would be solved manually, given the availability of computers and numerous LP software programs. In fact, there are even programs that help in constructing the LP or TP model, with GAMS being the most well-known. GAMS, short for General Algebraic Modeling System, is a high-level language that simplifies the representation of complex problems.
