Linear programming transportation problems

Example 2.—A well-known special case of the linear programming problem is the transportation problem requiring an assignment of shipments of materials from sources to destinations according to total availability and total demand, that minimizes the tot l shipping cost. If we denote the sources by St (i = 1, , m) and the destinations by... 

The target of minimum utility cost in HENs can be formulated as a linear programming LP transshipment model which corresponds to a well known model in operations research (e.g., network problems). The transshipment model is used to determine the optimum network for transporting a commodity (e.g., a product) from sources (e.g., plants) to intermediate nodes (e.g., warehouses) and subsequently to destinations (e.g., markets). 

For some time now, optimization techniques have been used to solve for least-cost shipping configurations. The classic transportation problem was to solve for the best combination of routes that fulfilled aU the demeuids, subject to all the availability and, naturally, at the least cost. With a considerable number of possible routes, the problem was too complex to solve by heuid, and therefore linear programming and network algorithms provide quicker solutions to the problem. 

Linear programming models are widely used to solve a number of military, economic, industrial, and social problems. The oil companies have been and still are one of the foremost users of very large LP models in petroleum refining, distribution, and transportation. The number of LP applications has grown so much in the last 20 years that it would be impossible to survey aU the different applications. Instead, the reader is referred to two excellent textbooks, Gass (1970) and SaUdn and Saha (1975) which are devoted solely to LP applications in such diverse areas as defense, industry, commercial-retail, agriculture, education, and the environment. Many of the applications also contain a discussion of the experiences in using the LP models in practice. 

In the network model, the nodes represent source sites, demand sites, or other (intermediate) nodes that are neither source nor demand sites. The net supply at node i is denoted as (for source sites is positive, for demand sites bj is negative, and for all other nodes bj is zero). To simplify our discussion, it is assumed that the total amount produced at the source sites is exactly equ to the total amount required at the demand sites. An arc connecting two nodes represents a transportation Unk. Associated with each arc (/, j) is an upper bound (arc capacity) Ujj limiting the total amount of goods that can flow on it. (In more complex models, there may also be a specific lower bound ij on the total flow on the arc. However, to simplify the discussion in this chapter, it is assumed that all lower bounds are zero.) An uncapacitated arc is one that has no upper bound on the amount of flow it can carry. There is a unit transportation flow cost Cy. The minimum cost flow problem can be represented as the following linear program ... 

In this subclass of problems there are only source and demand sites (no intermediate nodes are included), and shipments can only be made directly between source and demand sites. The source node i has a supply of s, and demand node j has demand of dj (or a net supply of —dj). The transportation problem can be formulated as the foUowing linear programming model ... 

This transportation model can also be formulated as the foUowing linear programming problem ... 

The computations of the method are rooted in dual linear programming formulation and row operations similar to ones used in Simplex algorithm to solve linear programming problems. We can apply transportation algorithm using the initial solution firom Vogel approximation method. As mentioned in Taha s book [3] multipliers , and y, are associated with row i and column j of transportation table. 

The coefficient matrix of the transportation problem is unimodular. This feature guarantees integer solution for a linear programming problem. 

There are a number of optimization solutions available that use a combination of linear programming and mixed integer programming algorithmsto optimize inventory, transportation costs, and total landed cost. There are solutions tailored to solve specific problems. ... 

A typical production-transportation problem can be described as follows. There are m production plants and n customers. A single product is produced at the plants and shipped from the plants to the customers. Each plant ihas a capacity limit Si, and the production cost is a concave function /(xi, X2, Xm) of the amounts produced at these plants x, X2,Xm- The transportation costs from the plants to the customers are linear the unit transportation cost from plant i to customer j is Cij. The problem involves a single time period only, and the demand of each customer j is known as dj which must be satisfied. The problem seeks a production and distribution plan that minimizes total production and transportation cost. The problem can be formulated as the following mathematical program ... 

Sabri and Beamon (2000) consider a four-stage (suppliers, plants, DCs, and customer zones) problem with both strategic (plant and DC locations) and tactical decisions. Demands for products are deterministic and have to be satisfied. There are fixed costs associated with DCs and transportation links between DCs and customer zones. Production cost is assumed to be linear. Two objectives are considered (a) Total cost, (b) Volume flexibility (difference between plant capacity and its utilization, and difference between DC capacity and its utilization). The strategic sub-model of the problem is formulated as a multi-objective MIR Two operational sub-models (suppliers, production) are formulated and solved as a non-linear programming problem. An overall iterative procedure is proposed which combines the strategic sub-model with the operational sub-models. 

Linear programming formtdation To formulate the transportation problem as a linear program, we define as the quantity shipped from warehouse i to market j. Since i can assume values from 1,2,..., m and j from 1,2,..., n, the number of decision variables is given by the product of m and n. The complete formulation is given in the following ... 

---