Problème d'assignation sous contrainte

Actuellement, je ferais comme cela.

J'impose qu'un agnet ne peut détenir qu'un seul objet : $\displaystyle
\sum_j x_{ij} = 1.$
Je crée un noeud $s$ connecté à tous les objets $j$ avec un bénéfice nul, $\beta_{js}= 0$.
Un objet est soit détenu par un agent $i$ soit par le nœud $s$ : $\displaystyle
\sum_i x_{ij} +x_{js} = 1.$
Je transforme l'inégalité des contraintes $k$ en : $\displaystyle
\sum_{j\in\mathcal{J}_k}\sum_i x_{ij} + x_k =P_k, $ avec $0\le x_k \le P_k$.
La dernière contrainte doit relier les objets non assignés aux agents avec les contraintes :
\begin{equation}
\sum_j x_{js} = \sum_k x_k + \sum_k(|\mathcal{J}_k| -P_k) -N

\end{equation} Le nombre des objets non assignés aux agents est nécessairement le fait des contraintes non remplies, $x_k > 0$, où du fait que si toutes les contraintes étaient remplies, il resterait le surplus d'objets interdits par la contrainte $k$, $\mathcal{J}_k -P_k$, moins le nombre d'agents, $N$, puisqu'on impose qu'ils doivent tous recevoir un objet.

Le lagrangien s'écrit comme suit :
\begin{equation}
\begin{split}
\mathcal{L} = &\sum_{ij} -\beta_{ij} x_{ij} + \sum_i \pi_i \biggl(\sum_j x_{ij} - 1\biggr)+ \sum_j p_j \biggl(\sum_i x_{ij} +x_{js} - 1\biggr)\\
&- \sum_k\lambda_k\biggl(\sum_{j\in\mathcal{J}_k}\sum_i x_{ij} + x_k - P_k \biggr)
- \lambda \biggl(\sum_j x_{js} - \sum_k x_k - \sum_k(|\mathcal{J}_k| -P_k) +N \biggr)
\end{split}
\end{equation}
soit en réarrangeant les termes :
\begin{equation}
\begin{split}
\mathcal{L} = &\sum_{ij}\biggl(\pi_i + p_j - \lambda_{k_j} -\beta_{ij}\biggr)x_{ij} + \sum_k (\lambda - \lambda_k) x_k+ \sum_j(p_j - \lambda)x_{js}\\
&-\sum_i \pi_i - \sum_j p_j + \sum_k (\lambda_k - \lambda)P_k + \lambda (M- N),
\end{split}
\end{equation} où $M$ est le nombre total d'objets : $\displaystyle
M = \sum_k |\mathcal{J}_k|.$
Il faut commencer par minimiser le lagrangien sur toutes les variables $x_{ij}$, $x_{js}$ et $x_k$ :
- pour $x_{ij}$ il faut $\pi_i + p_j - \lambda_{k_j} -\beta_{ij}\ge 0$ et il y a égalité si $x_{ij}=1$
- pour $x_{js}$ il faut $p_j \ge \lambda$ et il y a égalité si l'objet n'est pas assigné, $x_{js} = 1$
- pour $x_k$ :
- si $\lambda > \lambda_k$ alors le minimum est obtenu pour $x_k = 0$, la contrainte est complètement remplie,
- si $\lambda < \lambda_k$ alors le minimum est obtenu pour $x_k = P_k$, la contrainte est complètement libre,
- enfin si $\lambda = \lambda_k$ on peut choisir $x_k$ comme on veut entre $1$ et $P_k -1$.
Au final, il faut minimiser :
\begin{equation}
\sum_i \pi_i + \sum_j p_j - \sum_k \min(\lambda_k - \lambda, 0)P_k - \lambda (M- N)
\end{equation} avec les contraintes :
\begin{equation}
\pi_i + p_j \ge \lambda_{k_j} +\beta_{ij}~,~~ p_j\ge \lambda.

\end{equation} Je me demande si c'est correct, c'est-à-dire si cette formulation retranscrit bien les contraintes. Je me demande aussi comment résoudre le dual ?