Optimisation moyenne de plusieurs critères

Bonjour,

Je travaille actuellement sur un problème d'optimisation dont je peine à faire la modélisation. Le problème est le suivant.

J'ai des viandes de différentes natures, stockées dans des bacs $B_i$. Pour chaque bac, je peux mesurer la masse exacte de viande contenu ainsi que le taux de matière grasse. Je dispose également d'un ensemble de recettes $R_i$ définissant un taux de matière grasse idéal ainsi que des contraintes sur les pourcentages minimal et maximal de chaque type de viande. Ces deux éléments sont liés par des commandes $C_i$ : telle masse de telle recette, sachant que la masse est normalisée (100, 200 ou 400kg).

Le problème est le suivant : comment, avec un ensemble de bacs et de commandes, optimiser ces dernières, c'est-à-dire obtenir des commandes identiques (même masse idéale et même recette) les plus homogènes possibles au niveau de la masse et du taux de matière grasse ?

Là où je bloque, c'est qu'on cherche à tout optimiser en même temps, pour obtenir une moyenne acceptable. Le but n'est pas d'avoir des commandes parfaites et d'autres moins bonnes, mais d'avoir des commandes homogènes, quitte à ce qu'elles soient toutes de qualité moyenne.

Auriez-vous des pistes de réflexion ?

Merci.

Loin d'etre expert, je vais quand meme essayer de t'aider, sait on jamais (j'ai aucune vision d'ensemble de la discipline) !

En gros t'as une liste d'objet (viande) $x_1$ … $x_{n}$ à mettre en correspondance avec d'autre objet (recette) $y_1$ …^$y_n$ et tu cherche à minimiser $\sum_{i=1}^{n} {(y_i-x_i)}^2$ ?

En programmation dynamique ça doit etre faisable, mais avec une complexité spaciale assez sale : Normalement si c'est optimal pour n objets alors les n-1 premiers x sont forcement en relation optimales avec n-1 premiers y.

Pour $x_1$ … $x_{n-1}$ on connait l'ecart lorsque mis en correspondance avec n-1 objets de (y). On minimise l'ecart en prenant la combinaison min de $x_1$ …$x_{n-1}$ en relation avec y\ $y_i$ + $x_n$ en relation avec $y_i$.

Le defaut de cette methode c'est qu'il faut calculer pour chaque i de [1,n] $\begin{pmatrix}n \\ i \end{pmatrix}$ configurations …

Apres, ça peut toujours etre une piste

Je pense que le plus important est d'essayer de déterminer la fonction que tu souhaites optimiser et les contraintes associées. Pour moi tu souhaites minimiser la différence entre l'ensemble des commandes et l'ensemble de ce que tu aura fourni, sous contraintes de recettes et de la disponibilité de la viande dans les bacs.

Cela donne une fonction objectif et deux contraintes, ce qui devrait se résoudre avec un simplexe ou un lagrangien si on est dans un cadre linéaire.

J'ai pas entièrement compris ton modèle, mais tu peux regarder du côté des problèmes d'affectation (et le fameux algorithme hongrois). Mais aussi l'optimisation combinatoire en général. Les livres de Michel Sakarovitch sont de bonnes références sur le sujet.

Tes bacs sont-ils indivisibles ? Si tu ne peux pas prendre seulement une partie du contenu, alors le problème est clairement un problème d'affectation (quel bac pour quelle commande ?). Le problème sera alors de trouver une partition des bacs qui va bien.

Si tu peux choisir la quantité extraite de chaque bac, alors c'est de l'optimisation plus classique. Le but sera de chercher pour chaque recette les quantités à piocher dans chaque bac (ce sont tes paramètres !).

Pour ce qui est de la fonction à minimiser, c'est plus complexe. Comme tu veux optimiser deux critères à la fois, il faudrait faire de l'optimisation multiobjectifs et choisir une solution parmi l'ensemble des solutions acceptables (celles qui sont optimales pour un des deux critères, l'autre étant fixé). Ces critères correspondent à la somme des écarts à la moyenne sur les commandes (une fois pour le gras, une fois pour la masse).

Si tu veux avoir un seul objectif, tu peux peux pondérer les critères par exemple, ou considérer les objectifs comme les composantes d'un vecteur.

Il y a un point que tu n'abordes pas, c'est l'aspect chronologie :

Si tu as par exemple 4360kg de viande, tu as 3 scénarios :

-1- : tu dois tout utiliser, et donc tu vas devoir être tolérant sur le poids, et avoir des lots, soit un peu plus lourds que le poids cible, soit un peu moins lourd

-2- : tu dois utiliser environ 4300kg, et les 60 kg restants seront reportés au lendemain

-3- : tu dois utiliser 4000kg, ou 4100kg, et le surplus sera reporté au lendemain.

Selon que tu es dans le scénario 1, 2 ou 3, les solutions peuvent être très différentes.

Merci pour vos réponses.

Normalement si c'est optimal pour n objets alors les n-1 premiers x sont forcement en relation optimales avec n-1 premiers y.

C'est intéressant ça. Je n'avais pas pensé à la modélisation récursive. Je vais y jeter un oeil.

Je pense que le plus important est d'essayer de déterminer la fonction que tu souhaites optimiser et les contraintes associées.

Oui.

Tes bacs sont-ils indivisibles ? Si tu ne peux pas prendre seulement une partie du contenu, alors le problème est clairement un problème d'affectation (quel bac pour quelle commande ?). Le problème sera alors de trouver une partition des bacs qui va bien.

C'est effectivement ce problème.

Si tu veux avoir un seul objectif, tu peux peux pondérer les critères par exemple, ou considérer les objectifs comme les composantes d'un vecteur.

Intéressant ! Je vais regarder ça.

Il y a un point que tu n'abordes pas, c'est l'aspect chronologie :

La viande est stockée dans un frigo donc n'a pas à être utilisée systématiquement. Je ne l'ai pas précisé dans le premier message, mais une contrainte supplémentaire est de prioriser les bacs les plus vieux.

Je suis parti sur la modélisation suivante. Pour chaque commande $C_i$ et chaque bac $B_j$, on note $x_{i,j}$ l'entier valant $0$ ou $1$ selon si le bac sert à confectionner la commande ou non. On obtient alors un système linéaire.

Seulement, avec 20 commandes et 1000 bacs, le système comporte 20 000 variables. Autant dire que ça fait beaucoup pour un simplexe.

Du coup, je ne vois pas tellement comment modéliser ça. Ca ressemble à un problème de classification de machine learning, mais sans phase d'apprentissage.

Auriez-vous des pistes ?

Merci !

Ton problème est un problème d'OLNE. En gros pour résoudre, on fait du branch and bound et on calcule un minorant (en minimisation) en relâchant les contraintes d'intégrité et en résolvant avec une technique de programmation linéaire (par ex le simplexe).

Note que le simplexe est davantage sensible au nombre de contraintes, donc peut-être que ça se tente dans ton cas. Quant aux méthodes off-the-shelf, je crois que CPLEX fait ça.

Le problème est que j'ignore comment appliquer le branch and bound, puisque je ne vois pas l'influence qu'a l'ajout d'une caisse particulière sur la fonction d'erreur.