Discussion :

[Amiral56]

Bonjour à tous,

Cela fait plusieurs heures que je me creuse le cerveau pour un problème d'optimisation type recherche opérationnelle.
Je ne vois toujours pas comment aborder le sujet ...

On se situe dans le domaine de l'agro-alimentaire plus précisément dans le domaine de la préparation de viande hachée.
On a un stock qui contient plusieurs bacs, chaque bac est défini par son poids Pi (disons en moyenne 20 kg) et son taux de gras Gi € [0,1] ( notez que dans un bac il y a de la viande et qui dit viande dit muscle + gras).
On souhaite un moment donné préparer une recette de poids total Pr en Kg avec un taux de gras de Gr %.
La problématique c'est comment choisir parmi les N bacs disponibles dans le stock, la série idéale de bacs qui va me permettre de préparer ma recette en ayant à la fois le bon poids et le bon taux de gras avec une certaine tolérance.

Rien de mieux qu'un exemple pour mieux éclairer la chose !
Voici le contenu de mon stock :

Contenu Stock Poids Bac %Gras Bac
BAC_1 10 Kg 7 %
BAC_2 14 Kg 9 %
BAC_3 10 Kg 8 %
BAC_4 16 Kg 8 %
BAC_5 16 Kg 5 %
BAC_6 19 Kg 6 %
BAC_7 10 Kg 6 %
BAC_8 19 Kg 8 %

Ensuite je souhaiterais préparer une recette de 50 Kg avec un taux de gras de 7 % et une tolérance de 5 Kg pour le poids et 1% pour la taux de gras.
(Ca veut dire qu'une recette de 45 Kg avec 6 % de gras est acceptable tout comme la recette de 55 Kg à 8 % de gras).

J'espère que j'ai bien posé mon problème. Je continue de mon côté à me creuser les méninges ...

Si vous avez la moindre idée je suis preneur ou besoin d'infos je suis à votre disposition.

Merci à vous tous !

[Prof]

Bonjour.

Je présume que, lorsqu'on choisit un bac, on prend le bac en entier.

Dans ce cas, il y a 2^N cas possibles, où N est le nombre de bacs.

Tant que N est petit, disons inférieur à 24, on peut utiliser la force brute et passer en revue tous les cas possibles.
Si N est plus grand que 24, il faudra soit être patient, soit utiliser une autre méthode ...

Pour étudier tous les cas, on peut procéder de la manière suivante :

pour un entier m compris entre 0 et 2^N -1 :
- étudier les chiffres de la décomposition de m en base 2
- si le chiffre d'indice i vaut 1, prendre le bac i+1 ( i varie de 0 à N-1 )
- calculer ainsi le poids p et le taux t correspond à cet entier m
- comparer p à Pr et t à Tr, en tenant compte des tolérances
- si p et t conviennent, on a une solution au problème

On peut alors afficher cette solution, en donnant p et t, ainsi que la liste des bacs correspondant à m.
On peut également, s'il y a plusieurs solutions, chercher celle donc le poids p est le plus proche de Pr.

Remarque : le cas m = 0 n'a pas besoin d'être étudié puisqu'il correspond à p = 0.

[tbc92]

Pour compléter le message de Prof, le mot clé pour ton problème , c'est 'parcours d'arbre binaire'.
Les 2 autres informations essentielles pour ton problème, c'est :
- temps de traitement : Est-ce que tu as des contraintes pour avoir une réponse en 1 seconde, 5 secondes...
- Nombre de bacs : Dans ton exemple, tu veux en gros choisir 3 ou 4 bacs parmi 8.
Dans la vraie vie, c'est pareil, ou c'est choisir par exemple 30 bacs parmi 200 ?

[picodev]

Bonjour,
si j'étais le PO je chercherais du côté du problème du sac à dos, version multidimensionnelle. Où en résolution exacte (programmation dynamique) ou avec un heuristique appropriée … enfin c'est une idée comme ça.

[Amiral56]

Je présume que, lorsqu'on choisit un bac, on prend le bac en entier.
Dans ce cas, il y a 2^N cas possibles, où N est le nombre de bacs
Tant que N est petit, disons inférieur à 24, on peut utiliser la force brute et passer en revue tous les cas possibles.
Si N est plus grand que 24, il faudra soit être patient, soit utiliser une autre méthode ...

Bonjour Prof,
Je tiens à te remercier pour ton aide.
Pour répondre à ta question. Une fois qu'un bac est choisi, on le consomme entièrement.
Par contre je n'ai pas compris pourquoi on a 2^N cas possibles. Moi je voyais plutôt ça comme une sortie de combinaison, on pioche P bacs parmi les N bacs, C(N,P) ?
En réalité on prépare différentes recettes, donc pour chaque recette on va avoir un N différent. L'idée de se dire qu'avec N inférieur à une valeur maxi on utilise la force brute !

Pour compléter le message de Prof, le mot clé pour ton problème , c'est 'parcours d'arbre binaire'.
Les 2 autres informations essentielles pour ton problème, c'est :
- temps de traitement : Est-ce que tu as des contraintes pour avoir une réponse en 1 seconde, 5 secondes...
- Nombre de bacs : Dans ton exemple, tu veux en gros choisir 3 ou 4 bacs parmi 8.
Dans la vraie vie, c'est pareil, ou c'est choisir par exemple 30 bacs parmi 200 ?

Bonjour tbc92,

Je tiens à te remercier pour ton aide.
En réalité tout dépend de la recette qu'on prépare, mais généralement on doit choisir 30 parmi 200 !
On peut accepter un temps de calcul de l'ordre de 5 sec par exemple.
Comme disait une autre personne, c'est un problème similaire au problème du sac à dos sauf que là on a deux paramètres à gérer le poids et le taux de gras !
Je vais me renseigner sur le "parcours d'arbre binaire"

Merci

Bonjour,
si j'étais le PO je chercherais du côté du problème du sac à dos, version multidimensionnelle. Où en résolution exacte (programmation dynamique) ou avec un heuristique appropriée … enfin c'est une idée comme ça.

Bonjour picodev,

Merci pour ton aide.
Effectivement le problème est similaire à un problème de sac à dos mais avec deux paramètres , le poids et le taux de gras !
Quelle heuristique sera la mieux appropriée pour ce genre de problèmes ?

Merci

[François DORIN]

Bonjour,

Voici comment je procéderai pour aborder le problème :

1. Déterminer une fourchette du nombre de bacs à utiliser (connaissant le poids de chacun de tes bacs, tu peux rapidement faire une estimation en divisant le poids recherché par le poids du plus lourd et le poids du plus léger) ;
2. Admettons que la fourchette soit de l'ordre de 25 à 40 ;
3. Je choisi (méthode restant à définir) un certain pourcentage de bac. Par exemple, 80% de la borne min (soit ici 20 bacs) ;
4. Ces 20 bacs forment donc une base travail (il est possible de calculer à ce niveau là le poids et le taux de gras de l'ensemble) ;
5. Je complète ensuite mon ensemble de bac en piochant dans les bacs restant, via la méthode de mon choix (parcours d'arbre, heuristique, etc...) jusqu'à obtenir un résultat correspondant aux tolérances

Alors, d'accord, cela ne répond pas directement à la question (puisqu'il y a toujours le choix de l'algorithme à faire), mais tu réduis la taille du problème, et augmente donc la possibilité d'explorer un ensemble de solutions. Bien évidemment, ce n'est qu'un exemple et tu pourras jouer sur certains paramètres (comme le nombre de bacs choisi au à l'étape 3).

Et pour finaliser l'algorithme, je verrais bien une exploration d'arbre, via une méthode de séparation et d'évaluation. En plus, il doit être possible d'utiliser une heuristique pour choisir les prochains éléments. Par exemple, si ton ensemble de bac à un niveau de gras inférieur à celui qui est demandé, tu peux favoriser (en explorant en premier) les solutions utilisant des bacs "riches en gras". Tu peux aussi jouer sur le poids restant à rajouter pour obtenir une idée du nombre de bacs à rajouter, et donc favoriser les bacs autour du poids moyens.

Comme tu recherches une solution avec tolérance, je pense que tu peux ainsi obtenir des résultats très rapidement, sans forcément te casser la tête sur un algo hyper compliqué.

[Prof]

Bonjour

Par contre je n'ai pas compris pourquoi on a 2^N cas possibles.
Moi je voyais plutôt ça comme une sorte de combinaison, on pioche P bacs parmi les N bacs, C(N,P) ?

Ce serait effectivement une combinaison si l'entier P était connu à l'avance.

Or, dans l'énoncé tel qu'il a été donné au début, il n'est pas précisé qu'il faut d'utiliser un nombre fixé de bacs.

Pour le problème donné au départ, il y a donc 2 possibilités pour chaque bac : il est pris ou non.
Ce qui fait 2^N cas possibles en tout.

Mais on peut modifier l'énoncé en imposant qu'il faut prendre P bacs.
Le nombre de cas possibles est alors le nombre de combinaisons C(N,P).

L'idée de se dire qu'avec N inférieur à une valeur maxi on utilise la force brute !

Le terme " force brute " que j'ai utilisé signifie que l'on passe en revue toutes les possibilités.

C'est une méthode qui assure que, si le problème a une solution, on la trouvera.

Mais passer en revue tous les cas possibles n'est envisageable que si le nombre des cas possibles n'est pas trop élevé.
Pour N = 24, il y a 16 777 216 cas possibles et on peut les examiner tous.
Mais pour N = 200, il y a environ 10^60 cas possibles et il est impossible de les examiner tous.

Ainsi, si N est grand, il faut utiliser une autre méthode que " la force brute ".

[tbc92]

La méthode proposée par Dorinf me paraît la bonne : on prend n bacs au hasard .
Puis on utilise la force brute pour compléter la sélection.

Les cas qui vont poser problème c'est quand ton stock contient des bacs qui font 6% , 7% , 8% de MG, et qu'on te demande d'arriver à un taux de MG de 8%.
Si tu commences par prendre n bacs complètement au hasard, et que tu tombes sur des bacs avec 6% ou 7% de MG, tu risques de ne plus pouvoir atteindre le taux mini de MG demandé. Dans la première phase, il faut donc essayer d'avoir un taux de MG proche de la cible.

L'autre objectif que tu peux te fixer, c'est d'essayer d'utiliser de préférence les gros bacs. En effet, si tu utilises beaucoup de petits bacs, il te restera en stock les gros bacs, et donc moins de marge de manoeuvre pour la prochaine recette à préparer.

[Prof]

La méthode proposée par Dorinf me paraît la bonne : on prend n bacs au hasard .
Puis on utilise la force brute pour compléter la sélection.

Lorsque le nombre de bacs est trop grand pour utiliser " la force brute ", je suggère une autre méthode que le hasard pour sélectionner un sous-ensemble de bacs.

Explication sur un exemple :
si la taux souhaité Tr vaut 7 % et que la tolérance est de 1 %, se limiter aux bacs dont le taux est compris entre 6 et 8 %.
Ainsi, si on utilise uniquement ces bacs là, le taux final sera automatiquement compris entre 6 et 8 %.

L'avantage est, non seulement de réduire le nombre de bacs à prendre en compte, mais surtout de faire disparaître la contrainte sur les taux.
On est ainsi ramenè à un problème plus simple : obtenir un poids compris entre ( par exemple ) 45 et 55 kg à l'aide de bacs de divers poids.

On utilise alors ce que préconise tbc92 : prendre en premier les bacs les plus lourds, et compléter avec des bacs plus légers.

[François DORIN]

La méthode proposée par Dorinf me paraît la bonne : on prend n bacs au hasard .

Attention, je n'ai jamais dit au hasard. J'ai dis que la méthode de sélection restait à définir

si la taux souhaité Tr vaut 7 % et que la tolérance est de 1 %, se limiter aux bacs dont le taux est compris entre 6 et 8 %.
Ainsi, si on utilise uniquement ces bacs là, le taux final sera automatiquement compris entre 6 et 8 %.

Très bonne idée ! En restreignant ainsi les bacs dans lesquels il est possible de piocher, cela gère automatiquement un des paramètres (le taux de gras). Le problème se réduit finalement au problème du sac à dos "classique".

En combinant tout ce qui a été dit, il doit être possible de sortir un algo relativement performant et simple à mettre en oeuvre pour répondre à la problématique initiale.

[Amiral56]

Salut à vous tous,

J'ai un peu cherché sur le net parce qu’apparemment le problème est un peu similaire à un problème de sac à dos bidimensionnel. Mais je ne voulais pas trop me compliquer la vie ! J'ai fini par suivre le raisonnement de Dorinf.
J'ai commencé par définir une solution initiale S0(p0,g0) ( p correspond au poids et g correspond au taux de gras).
Quand le poids de la solution est inférieur au poids de la cible, je pioche un bac au hasard jusqu'à atteindre le poids cible.
Ensuite à chaque itération je calcule le taux de gras de ma solution.
Si le taux de gras de ma solution est supérieur à la cible (ie solution très grasse) je supprime le bac le plus gras de ma sélection et je le remplace par le bac le moins gras et ainsi de suite jusqu'à atteindre le nb maximal d'itérations et vice versa quand le taux de gras de ma solution est inférieur à la cible.

C'est un algorithme assez simple qui a donné des résultats très satisfaisants.
Voici quelques exemples :

Poids Cible % Gras Cible Poids obtenu % Gras obtenu Erreur Poids Erreur % Gras
Test 1 200 Kg 5 % 203 Kg 5.25 % 1.5 % 0.25 %
Test 2 400 Kg 28 % 404 Kg 28.10 % 1 % 0.10 %
Test 3 300 Kg 12 % 292 Kg 11.75 % 2.6 % 0.25 %
Test 4 250 Kg 15 % 253 Kg 14.6 % 1.2 % 0.4 %

Merci à vous tous !

[MABROUKI]

bonjour

Comme dit par Dorinf ,algo de separation et evaluarion :

L'idée de base c'est d'avoir un tableau B de 8 elements Struct(Poid,TauxGras) et de
trier le tableau par Poids croissant suivi de TauxGras croissant ....
Avoir un second un tableau MEMB de 8 elements Struct(Poid,TauxGras) pour garder une liste des bacs trouves ...


Ensuite une boucle TantQue :

MEMB -> vide
TolerancePoid = 5
ToleranceGras = 1
Cap = 50 =>capacité recette
Taux= 7 =>taux recette
I=1 =>bac de Poids et TauxGras Mini
Pi = B(I).Poids
Ti = B(i).Taux
Faire
i->i+1
Pi = B(i).Poids

Ti = B(i).TauxGras

MEMB(i)=B(i)

Cap ->Cap-Pi
Tant Que (Cap- Pi) < TolerancePoids et Taux-Ti <ToleranceGras

ceci devrait répondre au souci...

[Amiral56]

Bonjour MABROUKI,

Merci pour ton aide ! C'est un peu le même raisonnement que j'avais suivi et les résultats m'avaient l'air très satisfaisants !

Voici l'algorithme utilisé :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
-- MESURES ET TESTS
	local nbIteration : integer := 1000 ; 
	local Tolerance_Gras : real := 1 -- +/-1% ; local Tolerance_Poids : real := 10 ; -- +/- 10 Kg
 
	while nbIteration > 0 loop
		local mesurements : real[2] := ref(Algo1).Mesure_Solution(Liste_Bacs) ; 
                -- Poids total de la solution S_i ;  -- Taux gras global de la solution S_i
		local Pds_Solution : real := mesurements[1] ; local TauxGras_Solution : real := mesurements[2] ; 
 
		if abs(TauxGras_Solution - TauxGrasCible_Recette) > Tolerance_Gras OR abs(Pds_Solution - PoidsCible_Recette) > Tolerance_Poids then 
			-- SI LE POIDS DE LA SOLUTION N EST PAS BON ON AJOUTE OU ON SUPPRIME UN BAC 
			-- SINON SI LE POIDS EST BON ON INTERCHANGE DES BACS, SI LA SOLUTION EST TRES GRASSE ON REMPLACE LE BAC LE PLUS GRAS DE LA SOLUTION
                        -- PAR LE BAC LE MOINS GRAS DE LA LISTE DES BACS ELIGIBLES ETC ....
			if TauxGras_Solution > TauxGrasCible_Recette then
				if (Pds_Solution > PoidsCible_Recette + Tolerance_Poids) then
					-- SOLUTION TRES GRASSE 
					-- SUPPRESSION DU BAC LE PLUS GRAS 
					Solution.sort(Solution.GetColumnNo("TauxGras_BAC") , "down"); 
					Solution.copyRangeto({0,1}..{*,1},Liste_Bacs,0,Liste_Bacs.indexydim + 1) ;
					Solution.cutrow(1) ;
				elseif (Pds_Solution < PoidsCible_Recette - Tolerance_Poids) then
					-- AJOUT DU BAC LE MOINS GRAS
					Liste_Bacs.sort(Solution.GetColumnNo("TauxGras_BAC") , "up"); 
					Liste_Bacs.copyRangeto({0,1}..{*,1},Solution,0,Solution.indexydim + 1) ;
					Liste_Bacs.CutRow(1) ; 
				elseif abs(Pds_Solution - PoidsCible_Recette) < Tolerance_Poids then 
					-- SOLUTION TRES GRASSE 
					-- SUPPRESSION DU BAC LE PLUS GRAS 
					Solution.sort(Solution.GetColumnNo("TauxGras_BAC") , "down"); 
					Solution.copyRangeto({0,1}..{*,1},Liste_Bacs,0,Liste_Bacs.indexydim + 1) ;
					Solution.cutrow(1) ;
					-- AJOUT DU BAC LE MOINS GRAS
					Liste_Bacs.sort(Solution.GetColumnNo("TauxGras_BAC") , "up"); 
					Liste_Bacs.copyRangeto({0,1}..{*,1},Solution,0,Solution.indexydim + 1) ;
					Liste_Bacs.CutRow(1) ;
				end;
 
 
			else
				-- SOLUTION PEU GRASSE 
				-- SUPPRESSION DU BAC LE - GRAS
				if (Pds_Solution > PoidsCible_Recette + Tolerance_Poids) then
					Solution.sort(Solution.GetColumnNo("TauxGras_BAC") , "up"); 
					Solution.copyRangeto({0,1}..{*,1},Liste_Bacs,0,Liste_Bacs.indexydim + 1) ;
					Solution.cutrow(1) ; 
				elseif (Pds_Solution <= PoidsCible_Recette - Tolerance_Poids) then
					-- AJOUT DU BAC LE + GRAS
					Liste_Bacs.sort(Solution.GetColumnNo("TauxGras_BAC") , "down"); 
					Liste_Bacs.copyRangeto({0,1}..{*,1},Solution,0,Solution.indexydim + 1) ;
					Liste_Bacs.CutRow(1) ; 
				elseif abs(Pds_Solution - PoidsCible_Recette) < Tolerance_Poids then 
					-- SOLUTION TRES GRASSE 
					-- SUPPRESSION DU BAC LE PLUS GRAS 
					Solution.sort(Solution.GetColumnNo("TauxGras_BAC") , "down"); 
					Solution.copyRangeto({0,1}..{*,1},Liste_Bacs,0,Liste_Bacs.indexydim + 1) ;
					Solution.cutrow(1) ;
					-- AJOUT DU BAC LE MOINS GRAS
					Liste_Bacs.sort(Solution.GetColumnNo("TauxGras_BAC") , "up"); 
					Liste_Bacs.copyRangeto({0,1}..{*,1},Solution,0,Solution.indexydim + 1) ;
					Liste_Bacs.CutRow(1) ;
					end;
			end;
		end;
		-- MAJ DU NB D ITERATIONS
		nbIteration := nbIteration - 1 ; 
	end;

Merci