**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 VARIABLEx.Lshipment quantities in casesnew-york chicago topeka seattle 50.000 300.000 san-diego 275.000 275.000 ---- 56 EQUATIONsupply.Mobserve supply limit at plant iseattle EPS ---- 56 EQUATIONdemand.Msatisfy demand at market jnew-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.

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.

--- 76 VARIABLEu.Ldual of supply equation( ALL 0.000 ) ---- 76 VARIABLEv.Ldual of demand equationnew-york 0.225, chicago 0.153, topeka 0.126 ---- 76 EQUATIONdualfeas.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).

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.

---- 95 VARIABLEx.Lshipment quantities in casesnew-york chicago topeka seattle 50.000 300.000 san-diego 275.000 275.000 ---- 95 VARIABLEu2.Ldual of supply equation (sign flipped)( ALL 0.000 ) ---- 95 VARIABLEv.Ldual of demand equationnew-york 0.225, chicago 0.153, topeka 0.126

#### References

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

#### Appendix: GAMS model

Seti 'canning
plants' / seattle,
san-diego /j 'markets' / new-york, chicago, topeka /;Parametera(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*----------------------------------------------------------Variablex(i,j) 'shipment quantities in cases'z 'total
transportation costs in thousands of dollars';Positive Variable x;Equationcost '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';equationsdualobj 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)';equationssupply2(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; |

## No comments:

## Post a Comment