# The dual of transporting problem

So basically I'm trying to figure out what does a certain variable in dual of transporting problem mean.

Transporting problem in matrix form:

(We are searching for a min cost of transferring goods from node to node across the connections)

\begin{array}{ll} \text{min:} & \ c^Tx \\ \text{} & \ Ax = b \\ & \ x >= 0 \\ \end{array}

\begin{array}{ll} \text{$b_i$ … demand in node i}\\ \text{$c_j$ … cost of transferring one unit of good across the connection j}\\ \text{$x_j$ … number of goods, that we actually transfer across the connection j}\\ & \ \\ \end{array}

Dual:

(We are searching for max amount that the transporter earns by buying all of the goods and then reselling them in nodes)

\begin{array}{ll} \text{max:} & \ b^Ty \\ \text{} & \ A^Ty = c \\ & \ y >= 0 \\ \end{array}

\begin{array}{ll} \text{$b_i$ … ???}\\ \text{$c_j$ … ???}\\ \text{$y_j$ … ???}\\ & \ \\ \end{array}

Please help.

## 1 Answer

If I understand correctly, your question is trying to interpret the dual of your original problem which involves minimizing the cost of goods. You want to minimize cost, while trying to meet all your demand constraints. Then logically, the dual would be maximizing the amount of goods sent out (the demand met?), subject to cost constraints.

• I woude like to understand what do variables $b_i$, $c_j$ and $y_j$ mean – Matthew Apr 19 '15 at 21:54