The primal assignment problem that I have is:
$\begin{align} & \max \sum\limits_{i=i}^N\sum\limits_{j=1}^N c_{ij}x_{ij} \\ &\text{subject to} \\ &\sum_{i=1}^N x_{ij} = 1,~~j=1,\dots,N \\ &\sum_{j=1}^N x_{ij} = 1, ~~i=1,\dots,N \\ &x_{i,j} ~\in \{ 0,1 \} \end{align} $
and I would like to obtain its dual, which should be
$$ \min_{p_j} \bigg\{ \sum_{i=1}^N p_j + \sum_{i=1}^N \max \{ a_{ij} - p_j \} \bigg\} $$
Can you give me any hints on how to approach this derivation? I have tried with Lagrange multipliers but I have not been able to reach this expression.
I don't know why you want to transform a standard LP problem, as the dual of the AP is, into a min-max problem.
Anyway the transformation should be as follows.
Let $\alpha_j, \ j=1,\ldots, N$ be the dual multipliers associated to the first set of constraints and $\beta_i, \ i=1,\ldots ,N$ those associated to the second set of constraints. Then, the ordinary dual is $$ \begin{align*} \min_{\alpha , \beta}\ &\sum_{j=1}^N \alpha_j + \sum_{i=1}^N \beta_i\\ & \alpha_j + \beta_i \geq c_{ij} \ \ \ \forall i,j=1,\ldots, N \end{align*} $$
Observe now that $$\beta_i \geq c_{ij}-\alpha_j\ \ \forall i,j=1,\ldots, N \Longrightarrow \ \ \beta_i=\max_{1\leq j\leq N}\{c_{ij}-\alpha_j\}\ \ \forall i =1,\ldots,N$$
Hence we get
$$ \begin{align*} \min_{\alpha}\ \sum_{j=1}^N \alpha_j + \sum_{i=1}^N \max_{1\leq j\leq N}\{c_{ij}-\alpha_j\} \end{align*} $$