Operations Research/Transportation and Assignment Problem

The Transportation and Assignment problems deal with assigning sources and jobs to destinations and machines. We will discuss the transportation problem first.

Suppose a company has m factories where it manufactures its product and n outlets from where the product is sold. Transporting the product from a factory to an outlet costs some money which depends on several factors and varies for each choice of factory and outlet. The total amount of the product a particular factory makes is fixed and so is the total amount a particular outlet can store. The problem is to decide how much of the product should be supplied from each factory to each outlet so that the total cost is minimum.

Let us consider an example.

Suppose an auto company has three plants in cities A, B and C and two major distribution centers in D and E. The capacities of the three plants during the next quarter are 1000, 1500 and 1200 cars. The quarterly demands of the two distribution centers are 2300 and 1400 cars. The transportation costs (which depend on the mileage, transport company etc) between the plants and the distribution centers is as follows:

Which plant should supply how many cars to which outlet so that the total cost is minimum?

The problem can be formulated as a LP model:

Let ${\displaystyle x_{ij}}$ be the number of cars to be shipped from source i to destination j. Then our objective is to minimize the total cost which is ${\displaystyle 80x_{11}+215x_{12}+100x_{21}+108x_{22}+102x_{31}+68x_{32}}$. The constraints are the ones imposed by the number of cars to be transported from each plant and the number each center can absorb.

The whole model is:

Minimize z = ${\displaystyle 80x_{11}+215x_{12}+100x_{21}+108x_{22}+102x_{31}+68x_{32}}$

subject to,

${\displaystyle x_{11}+x_{12}=1000}$;

${\displaystyle x_{21}+x_{22}=1500}$;

${\displaystyle x_{31}+x_{32}=1200}$;

${\displaystyle x_{11}+x_{21}+x_{31}=2300}$;

${\displaystyle x_{12}+x_{22}+x_{32}=1400}$;

${\displaystyle x_{ij}\geq 0}$ and integer, i = 1,2,3, j = 1,2.

The problem can now be solved using the simplex method. A convenient procedure is discussed in the next section.