Exercise $6($dual of transportation problem$).$ Quantities a$1$

am of a certain prod

bn at

uct are to be shipped from each of m locations and received in amounts b$1$

each of n destinations. Associated with the shipping of a unit of product from origin

i to destination j is a shipping cost cij. It is desired to determine the amounts xij to

be shipped between each origin$-$destination pair i $=1$

m$,$ j $=1$ nsoas to

satisfy the shipping requirements and minimize the total cost of transportation.

$($a$)$ Formulate this as a linear program in mn variables $($x$11$

xmn$)$ subject to

m$+$nequality constraints, with the nonnegativity conditions xij $0.$

$($b$)$ Taking the linear program you wrote in $($a$)$ as the primal program, state the

corresponding dual program.