The Transportation Problem Model

By -

The Transportation Problem Model

To describe the general model for the transportation problem, we need to use terms that are considerably less specific than those for the components of the prototype example. In particular, the general transportation problem is concerned (literally or figuratively) with distributing any commodity from any group of supply centers, called sources, to any group of receiving centers, called destinations, in such a way as to minimize the total distribu- tion cost. The correspondence in terminology between the prototype example and the gen- eral problem is summarized in Table 9.4.

As indicated by the fourth and fifth rows of the table, each source has a certain supply of units to distribute to the destinations, and each destination has a certain demand for units to be received from the sources. The model for a transportation problem makes the following assumption about these supplies and demands:

The requirements assumption: Each source has a fixed supply of units, where this entire supply must be distributed to the destinations. (We let si denote the number of units being supplied by source i, for i = 1, 2, . . . , m.) Similarly, each destination has a fixed demand for units, where this entire demand must be re- ceived from the sources. (We let dj denote the number of units being received by destination j, for j = 1, 2, . . . , n.)

This assumption holds for the P & T Co. problem since each cannery (source) has a fixed output and each warehouse (destination) has a fixed allocation.

Introduction to Operations Research-0106

This assumption that there is no leeway in the amounts to be sent or received means that there needs to be a balance between the total supply from all sources and the total demand at all destinations.

The feasible solutions property: A transportation problem will have feasible solutions if and only if

Introduction to Operations Research-0107Fortunately, these sums are equal for the P & T Co. since Table 9.2 indicates that the sup- plies (outputs) sum to 300 truckloads and so do the demands (allocations).

In some real problems, the supplies actually represent maximum amounts (rather than fixed amounts) to be distributed. Similarly, in other cases, the demands represent maxi- mum amounts (rather than fixed amounts) to be received. Such problems do not quite fit the model for a transportation problem because they violate the requirements assumption. However, it is possible to reformulate the problem so that they then fit this model by in- troducing a dummy destination or a dummy source to take up the slack between the ac- tual amounts and maximum amounts being distributed. We will illustrate how this is done with two examples at the end of this section.

The last row of Table 9.4 refers to a cost per unit distributed. This reference to a unit cost implies the following basic assumption for any transportation problem:

The cost assumption: The cost of distributing units from any particular source to any particular destination is directly proportional to the number of units distrib- uted. Therefore, this cost is just the unit cost of distribution times the number of units distributed. (We let cij denote this unit cost for source i and destination j.)

This assumption holds for the P & T Co. problem since the cost of shipping peas from any cannery to any warehouse is directly proportional to the number of truckloads being shipped.

The only data needed for a transportation problem model are the supplies, demands, and unit costs. These are the parameters of the model. All these parameters can be sum- marized conveniently in a single parameter table as shown in Table 9.5.

The model: Any problem (whether involving transportation or not) fits the model for a transportation problem if it can be described completely in terms of a parameter table like Table 9.5 and it satisfies both the requirements assump- tion and the cost assumption. The objective is to minimize the total cost of distrib- uting the units. All the parameters of the model are included in this parameter table.

Introduction to Operations Research-0108

Therefore, formulating a problem as a transportation problem only requires filling out a parameter table in the format of Table 9.5. (The parameter table for the P & T Co. problem is shown in Table 9.2.) Alternatively, the same information can be provided by using the network representation of the problem shown in Fig. 9.3 (as was done in Fig. 9.2 for the P & T Co. problem). Some problems that have nothing to do with trans- portation also can be formulated as a transportation problem in either of these two ways. The Solved Examples section of the book’s website includes another example of such a problem.

Since a transportation problem can be formulated simply by either filling out a para- meter table or drawing its network representation, it is not necessary to write out a for- mal mathematical model for the problem. However, we will go ahead and show you this model once for the general transportation problem just to emphasize that it is indeed a special type of linear programming problem.

Letting Z be the total distribution cost and xij (i = 1, 2, . . . , m; j = 1, 2, . . . , n) be the number of units to be distributed from source i to destination j, the linear programming formulation of this problem is

Introduction to Operations Research-0109

Note that the resulting table of constraint coefficients has the special structure shown in Table 9.6. Any linear programming problem that fits this special formulation is of the trans- portation problem type, regardless of its physical context. In fact, there have been numerous applications unrelated to transportation that have been fitted to this special structure, as we shall illustrate in the next example later in this section. (The assignment problem described in Sec. 9.3 is an additional example.) This is one of the reasons why the transportation problem is considered such an important special type of linear programming problem.

For many applications, the supply and demand quantities in the model (the si and dj) have integer values, and implementation will require that the distribution quantities (the xij) also have integer values. Fortunately, because of the special structure shown in Table 9.6, all such problems have the following property:

Integer solutions property: For transportation problems where every si and dj have an integer value, all the basic variables (allocations) in every basic feasible (BF) solution (including an optimal one) also have integer values.

The solution procedure described in Sec. 9.2 deals only with BF solutions, so it automatically will obtain an integer optimal solution for this case. (You will be able to see why this solution procedure actually gives a proof of the integer solutions property after you learn the procedure; Prob. 9.2-20 guides you through the reasoning involved.) Therefore, it is unnecessary to add a constraint to the model that the xij must have integer values.

As with other linear programming problems, the usual software options (Excel with either the standard Solver or ASPE, LINGO/LINDO, MPL/Solvers) are available to you for setting up and solving transportation problems (and assignment problems), as demonstrated in the files for this chapter in your OR Courseware. However, because the Excel approach now is somewhat different from what you have seen previously, we next describe this approach.

Comments

Post a Comment

Popular posts from this blog

DUALITY THEORY:THE ESSENCE OF DUALITY THEORY

By -
Image
THE ESSENCE OF DUALITY THEORY Given our standard form for the primal problem at the left (perhaps after conversion from another form), its dual problem has the form shown to the right. Thus, with the primal problem in maximizatio n form, the dual problem is in minimization form instead. Furthermore, the dual problem uses exactly the same pa r amete r s as the primal problem, but in different locations, as summarized below. 1. The coefficients in the objective function of the primal problem are the right-hand sides of the functional constraints in the dual problem. 2. The right-hand sides of the functional constraints in the primal problem are the coef- ficients in the objective function of the dual problem. 3. The coefficients of a variable in the functional constraints of the primal problem are the coefficients in a functional constraint of the dual problem. To highlight the comparison, now look at these same two problems in matrix notation (as introduced at the beginn...
Read more

NETWORK OPTIMIZATION MODELS:THE MINIMUM SPANNING TREE PROBLEM

By -
Image
THE MINIMUM SPANNING TREE PROBLEM The minimum spanning tree problem bears some similarities to the main version of the shortest-path problem presented in the preceding section. In both cases, an undi r ecte d and connected network is being considered, where the given information includes some mea- sure of the positive length (distance, cost, time, etc.) associated with each link. Both problems also involve choosing a set of links that have the shortest total length among all sets of links that satisfy a certain property. For the shortest-path problem, this property is that the chosen links must provide a path between the origin and the destination. For the minimum spanning tree problem, the required property is that the chosen links must provide a path between ea c h pair of nodes. The minimum spanning tree problem can be summarized as follows: 1. You are given the nodes of a network but not the links. Instead, you are given the po- tential links and the positive length for each ...
Read more

INTEGER PROGRAMMING:THE BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS

By -
TH E BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS Integer programming has been an especially exciting area of OR since the mid-1980s be- cause of the dramatic progress being made in its solution methodology. Background To place this progress into perspective, consider the historical background. One big break- through had come in the 1960s and early 1970s with the development and refinement of the branch-and-bound approach. But then the state of the art seemed to hit a plateau. Rel- atively small problems (well under 100 variables) could be solved very efficiently, but even a modest increase in problem size might cause an explosion in computation time be- yond feasible limits. Little progress was being made in overcoming this exponential growth in computation time as the problem size was increased. Many important problems arising in practice could not be solved. Then came the next breakthrough in the mid-1980s, with the introduction of the b r an c h- and-cu t approach to sol...
Read more