a,.. Exercise 6 (dual of transportation problem). Quantities a, ..., am of a certain prod- uct...

Transcribed Image Text:

a,.. Exercise 6 (dual of transportation problem). Quantities a, ..., am of a certain prod- uct are to be shipped from each of m locations and received in amounts b,..., b at 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 xi; to be shipped between each origin-destination pair i = 1,..., m, j 1,..., m, j=1,...,n so as to satisfy the shipping requirements and minimize the total cost of transportation. (a) Formulate this as a linear program in mn variables (x11,...,xmn) subject to mn equality 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. a,.. Exercise 6 (dual of transportation problem). Quantities a, ..., am of a certain prod- uct are to be shipped from each of m locations and received in amounts b,..., b at 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 xi; to be shipped between each origin-destination pair i = 1,..., m, j 1,..., m, j=1,...,n so as to satisfy the shipping requirements and minimize the total cost of transportation. (a) Formulate this as a linear program in mn variables (x11,...,xmn) subject to mn equality 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.