Primal, Dual and Equilibrium format of the Transportation Model

The primal transportation model [1] can be stated as:

Primal formulation
\[\begin{align}\min& \sum_{i,j} \color{darkblue}{\mathit{cost}}_{i,j}\cdot\color{darkred}x_{i,j} \\ & \sum_j \color{darkred}x_{i,j}\le \color{darkblue}{\mathit{supply}}_{i}\perp \color{darkred}u_i \le 0 && \forall i \\ & \sum_i \color{darkred}x_{i,j}\ge \color{darkblue}{\mathit{demand}}_{j}\perp \color{darkred}v_j \ge 0 && \forall j \\ & \color{darkred}x_{i,j}\ge 0\end{align} \]

Here \(\perp\) indicates "with dual ...". The duals for this model are \(\color{darkred}u_i\) and \(\color{darkred}v_j\). In the model, we have added the (optimal) signs of the duals. It may come as a surprise that the optimality of a solution can be established by just looking at the signs of the marginals (duals and reduced cost). When we print the results of this model, we can see something like:

----     56 VARIABLE x.L  shipment quantities in cases

             new-york     chicago      topeka

seattle        50.000     300.000
san-diego     275.000                 275.000


----     56 EQUATION supply.M  observe supply limit at plant i

seattle EPS


----     56 EQUATION demand.M  satisfy demand at market j

new-york 0.225,    chicago  0.153,    topeka   0.126

Notes:

• The entries x.L are the optimal levels of x, and supply.M/demand.M are the optimal duals of the supply and demand equation.
• The duals of the supply equation are EPS for Seattle and 0 for San Diego. EPS means: this entry is numerical zero, but non-basic. I.e. this model is dual-degenerate. Indeed this model has two different optimal solutions.
• The duals have the correct sign.

A dual formulation can look like:

Dual formulation
\[\begin{align}\min& \sum_{i} \color{darkblue}{\mathit{supply}}_{i}\cdot\color{darkred}u_{i}+\sum_{j} \color{darkblue}{\mathit{demand}}_{j}\cdot\color{darkred}v_{j} \\ & \color{darkred}u_{i}+\color{darkred}v_{j}\le \color{darkblue}{\mathit{cost}}_{i,j}\perp \color{darkred}x_{i,j} \ge 0 && \forall i,j \\ & \color{darkred}u_{i}\le 0,\color{darkred}v_{j}\ge 0 \end{align} \]

Note that \(\color{darkred}u_{i}\le 0\). Sometimes versions of this dual model are given that have only non-negative variables. In that case \(\color{darkred}u_{i}\) is preceded by a \(-\) sign throughout the model.

The solution is:

---     76 VARIABLE u.L  dual of supply equation

                      ( ALL       0.000 )


----     76 VARIABLE v.L  dual of demand equation

new-york 0.225,    chicago  0.153,    topeka   0.126


----     76 EQUATION dualfeas.M  

             new-york     chicago      topeka

seattle        50.000     300.000
san-diego     275.000                 275.000

Notes:

• The dual variables of this dual model correspond to the primal level of the primal model.
• The primal variables of the dual model are equal to the duals found in the solution of the primal model.  
• The dual model is not dual-degenerate (no duals or reduced cost that are EPS; you need to inspect the complete solution for this).

There is also an equilibrium or complementarity formulation. Here we form the KKT (Karush-Kuhn-Tucker) conditions [2] and solve them as an LCP (linear complementarity problem) [3,4]. 

Equilibrium formulation

\[\begin{align}& \color{darkblue}{\mathit{supply}}_{i} \ge \sum_j \color{darkred}x_{i,j} \perp \color{darkred}u_{i}\ge 0 && \forall i \\ & \sum_i \color{darkred}x_{i,j} \ge \color{darkblue}{\mathit{demand}}_{j} \perp \color{darkred}v_{j}\ge 0 && \forall j \\ & \color{darkblue}{\mathit{cost}}_{i,j} + \color{darkred}u_{i} \ge \color{darkred}v_{j} \perp \color{darkred}x_{i,j}\ge 0 && \forall i,j\end{align} \]

Note:

• This is a square system of (linear) equations plus complementarity conditions.
• There is no objective.
• Both the original primal variables \(\color{darkred}x_{i,j}\) and dual variables \(\color{darkred}u_i\) and \(\color{darkred}v_j\) are present as explicit variables in the model. This is different from the previous models where duals were in the solution but not explicitly in the model.
• We flipped the sign of \(\color{darkred}u_i\): all prices are positive. So the first constraint is rearranged.
• The first two constraints are market clearing equations. Basically: supply=demand. The last equation is a zero-profit condition: there is no arbitrage.

The solution for this model looks like:

----     95 VARIABLE x.L  shipment quantities in cases

             new-york     chicago      topeka

seattle        50.000     300.000
san-diego     275.000                 275.000


----     95 VARIABLE u2.L  dual of supply equation (sign flipped)

                      ( ALL       0.000 )


----     95 VARIABLE v.L  dual of demand equation

new-york 0.225,    chicago  0.153,    topeka   0.126

Note that all quantities are variables here.

Modelers with an O.R. background are familiar with primal and dual formulations, while economists are used to primal and equilibrium formulations.

References

1. trnsport.gms : A Transportation Problem, https://www.gams.com/latest/gamslib_ml/libhtml/gamslib_trnsport.html
2. Karush–Kuhn–Tucker conditions, https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions
3. transmcp.gms : Transportation Model as Equilibrium Problem, https://www.gams.com/latest/gamslib_ml/libhtml/gamslib_transmcp.html
4. Solving linear complementarity problems without an LCP solver, https://yetanothermathprogrammingconsultant.blogspot.com/2021/05/solving-linear-complementarity-problems.html

Appendix: GAMS model

*---------------------------------------------------------- * Data from trnsport.gms *---------------------------------------------------------- Set    i 'canning plants' / seattle,  san-diego /    j 'markets'        / new-york, chicago, topeka /; Parameter    a(i)    'capacity of plant i in cases'            / seattle    350              san-diego  600 /    b(j)    'demand at market j in cases'            / new-york   325              chicago    300              topeka     275 /    esub(j) 'price elasticity of demand (at prices equal to unity)'            / new-york   1.5              chicago    1.2              topeka     2.0 /; Table d(i,j) 'distance in thousands of miles'               new-york  chicago  topeka    seattle         2.5      1.7     1.8    san-diego       2.5      1.8     1.4; Scalar f 'freight in dollars per case per thousand miles' / 90 /; Parameter c(i,j) 'transport cost in thousands of dollars per case'; c(i,j) = f*d(i,j)/1000; *---------------------------------------------------------- * Primal formulation *---------------------------------------------------------- Variable    x(i,j) 'shipment quantities in cases'    z      'total transportation costs in thousands of dollars'; Positive Variable x; Equation    cost      'define objective function'    supply(i) 'observe supply limit at plant i'    demand(j) 'satisfy demand at market j'; cost..      z =e= sum((i,j), c(i,j)*x(i,j)); supply(i).. sum(j, x(i,j)) =l= a(i); demand(j).. sum(i, x(i,j)) =g= b(j); Model transport / all /; solve transport using lp minimizing z; display x.l,supply.m,demand.m; *---------------------------------------------------------- * Dual formulation *---------------------------------------------------------- negative variable u(i) 'dual of supply equation'; positive variable v(j) 'dual of demand equation'; equations    dualobj    dualfeas(i,j) ; dualobj.. z =e= sum(i,a(i)*u(i)) + sum(j,b(j)*v(j)); dualfeas(i,j).. u(i)+v(j) =l= c(i,j); model dual /dualobj,dualfeas/; solve dual using lp maximizing z; display u.l,v.l,dualfeas.m; *---------------------------------------------------------- * Equilibrium formulation *---------------------------------------------------------- positive variable u2(i) 'dual of supply equation (sign flipped)'; equations    supply2(i) 'flipped sign'    zeroprofit(i,j) ; supply2(i).. a(i) =g= sum(j, x(i,j)); zeroprofit(i,j).. c(i,j)+u2(i) =g= v(j); model equilibrium /supply2.u2, demand.v, zeroprofit.x/; solve equilibrium using mcp; display x.l,u2.l,v.l;