Chapter 1 Linear Programming 1.1 Transportation of Commodities
We consider a market consisting of a certain number of providers and demanders of a commodity and a network of routes between the providers and the demanders along which the commodity can be shipped from the providers to the demanders. In particular, we assume that the transportation network is given by a set A of arcs, where (i, j) ∈ A means that there exists a route connecting the provider i and the demander j. We denote by cij the unit shipment cost on the arc (i, j), by si the available supply at the provider i , and by dj the demand at the demander j. The variables are the quantities xij of the commodity that is shipped over the arc (i, j) ∈ A and the problem is to minimize the transportation costs (1.1) minimize
(i,j)∈A

cij xij

over all x = (xij ) ≥ 0

under the natural constraints: • the supply si at i should exceed the sum of the demands at all j such that (i, j) ∈ A, i.e. (1.2) j:(i,j)∈A xij ≤ si

for all i ,

• the demand dj at j must be satisfied in the sense that is less or equal the sum of the supplies at all i such that (i, j) ∈ A, i.e. (1.3) i:(i,j)∈A xij ≥ dj

for all j .

The problem (1.1)-(1.3) is a Linear Program (LP) whose solution by the simplex method and primal-dual interior-point methods will be considered in sections 1.2 and 1.3 below.

1.1.1 Dantzig’s original transportation model
As an example we consider G.B. Dantzig’s original transportation model: We assume two providers i = 1 and i = 2 of tin cans located at Seattle and San Diego and three demanders j = 1, j = 2, and j = 3 located at New York, Chicago, and Topeka, respectively: Sets i j canning plants: markets: Seattle , San Diego New York , Chicago , Topeka
1

2

Ronald H.W. Hoppe

The following table contains the distances dij in thousands of miles between the providers and the demand centers Seattle San Diego New York