In this section, we will discuss several special types of linear programs. These are the transportation problems, the assignment problems, and the transshipment problems.

The standard scenario where a transportation problem arises is that of sending units of a product across a network of highways that connect a given set of cities. Each city is considered either as a "source," in that units are to be shipped out from there, or as a "sink," in that units are demanded there. Each source has a given supply, each sink has a given demand, and each highway that connects a source-sink pair has a given transportation cost per unit of shipment. This can be visualized in the form of a network, as depicted in Figure TP-1 below.

Given such a network, the problem of interest is to determine an optimal transportation scheme that minimizes the total cost of shipments, subject to supply and demand constraints.

Problems with the above structure arise in many applications. For example, the sources could represent warehouses and the sinks could represent retail outlets. Another example is for the sources to represent units produced by a production facility at different time periods and for the sinks to represent demands over time. Thus, the sources and the sinks do not have to correspond to physical locations.

The ability to model a wide range of problems is one important reason for singling out this particular class of problems for a separate discussion. Another reason is that these problems have a very special structure, one that will allow us to develop a streamlined version of the Simplex algorithm for their solution. This revised version of the Simplex algorithm will offer significantly improved solution times.

The assignment problem is a special case of the transportation problem where the supply from every source and the demand at every sink are equal to 1. Such a situation arises naturally in the setting of assigning workers to jobs, or of assigning workers to a time schedule. Interestingly, the assignment problem is also often referred to as the marriage problem, because it can be applied to the assignment of males to females; in such a scenario, the wish, of course, should be to maximize the overall happiness.

The improved efficiency in the Simplex algorithm is quite welcome, because many practical applications of the transportation and the assignment problems involve a very large number of constraints.

The transshipment problem is an extension of the framework of the transportation problems. The extension is in allowing the presence of a set of transshipment points that can serve as intermediate stops for shipments, possibly with a net gain or loss in units. We will show that any given transshipment problem can be converted into an equivalent transportation problem. Hence, our procedure for solving the latter problems can be applied to the solution of transshipment problems as well.

We will begin with a formal description of the linear-programming formulation of the transportation problem. This will be given at the next link.

The Transportation Problem: LP Formulations

As mentioned above, the solution method for transportation problems is a streamlined version of the Simplex algorithm. As such, the solution method also has two phases. In the first phase, the aim is to construct an initial basic feasible solution; and in the second phase, to iterate to an optimal solution. The details are given at the next two links.

Constructing an Initial Basic Feasible Solution: Two Methods

Progressing toward an Optimal Solution: Two Methods

At the next link, we will provide a summary and review of both phases of the solution method by solving a new example.

The Streamlined Simplex Method: An Example

The streamlined Simplex method has been implemented in the IOR Routines. In addition, transportation problems can of course also be solved using Excel's Solver. An example based on the network view given in Figure TP-1 above is provided here: The Transportation Problem - Spreadsheet Formulation and Solution.

Finally, at the next two links, we provide short descriptions of the assignment problem and the transshipment problem.

The Assignment Problem: An Example

The Transshipment Problem: An Example

Assignment No. 6

Chapter 8: 8.1-2, 8.1-3, and 8.1-9.

You should solve these problem using the streamlined Simplex algorithm (i.e., not using LINDO). To obtain an initial basic feasible solution, you can use either the least-cost method or the Vogel's approximation method.

Also, you can use the Interactive OR Routines to facilitate computations.