Question: A transportation problem involves I origins and J destinations. In its simplest formulation, the problem consists in transporting a homogeneous commodity from the origins to the destinations at the total minimum cost. Origins are equivalently called "warehouses" and destinations "markets." Markets place an order (demand) for the commodity and warehouses supply it. The information deals with knowledge of the routes connecting warehouses to markets, with the available supply and the requested demand, and with the unit cost of transportation on each route, cij. Hence, the primal of a transportation problem assumes the following structure:
where TCT stands for "total cost of transportation," Si for "supply" of the commodity available at the ith warehouse, Di for "demand" of the commodity at the retail markets, and Cij for the unit cost of transportation from the ith warehouse to the jth market. The transported quantities, xij must be nonnegative. Write down the dual of the transportation problem and provide a meaningful economic interpretation.