Discussion :

[Jean R.]

Bonjour
Je suis programmeur php et mon patron me demande sur notre application de logistique d'optimiser le nombre de colis.
Il s'agit à partir d'un tableau associatif Ref->Qté de faire le maximum de colis, chaque colis contenant exactement 15 articles mais avec un maximum de 3 références.

J'ai écrit un algo en php qui fonctionne, mais il part des valeurs maximales en reclassant chaque fois le tableau en ordre décroissant des quantités et ce n'est pas la bonne approche: sur le jeu de test, il fait 7 cartons alors qu'il y a moyen d'en tirer au moins 8.

Ma fonction :

Code php :

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
 
function build_carton($tableau) {
        $arr_result = array();//tableau résultat
 
        do{
			//tri en ordre décroissant des quantités le tableau en gardant les clés 
			arsort($tableau);
 
			$cpt = 0; $tot3prem = 0;
			foreach ($tableau as $key => $val) {//on fait la somme des 3 premiers
				$cpt++;
				$tot3prem += $val;
				if($cpt == 3) break;
			}
                        echo 'total 3 prem '.$tot3prem.'<br />';
			if ($tot3prem >= 15) {//il y en a assez pour faire un carton
				$tot_carton = 0;
				$arr_carton = array();
				echo 'Nouveau carton : <br />';
				foreach ($tableau as $key => &$value){
					$qte = $value;
					$qte_utile = 15 - $tot_carton;
					if($qte > $qte_utile) $qte = $qte_utile;
					$tableau[$key] = $value - $qte;
					$tot_carton += $
					echo  $key . ' Quantité : '.$qte.' Reste : ' . $tableau[$key] .br();
					$arr_carton[$key] = $qte;
					if($tot_carton == 15){
                                            break 1;
                                        }
				}
				$arr_result[] = $arr_carton;
			}else{
				echo "pas assez d'articles pour faire un carton";
			}
        }while ($tot3prem >= 15);
        return $arr_result;
    }

Voilà le jeu de test que j'utilise :

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
 
3607868152642;5
3607868152635;6
3607868152628;6
3607868298845;6
3607868298821;6
3607868298838;6
3607868152246;4
3607868152239;4
3607868152222;4
3607868152215;4
3607868152284;4
3607868152277;4
3607868152260;4
3607868152253;4
3607868152130;4
3607868152147;5
3607868152154;4
3607868152161;3
3607868298814;4
3607868152611;4
3607867486274;1
3607867832286;1
3607867230266;1
3607867591442;1
3607867416684;1
3607867352203;1
3607867891337;3
3607867892228;2
3607867892242;3
3607867892181;3
3607867893034;5
3607867893027;5
3607867893010;3
3607867911189;2
3607867911172;3
3607867911165;2
3607867895731;2
3607867891344;1
3607867914302;4
3607867912261;3
3607867892235;3
3607867914296;2
3607867896660;2
3607867921942;4
3607867911196;1
3607867895724;2
3607867895717;1
3607867920310;2
3607867896615;2
3607867896639;2
3607867896646;1
3607867920303;2
3607867896622;3
3607867896585;3
3607867896578;3
3607867920297;2
3607867896561;2
3607867896592;2
3607867896691;2
3607867891320;1
3607867896684;3
3607867896677;2
3607867909483;3
3607867909490;2
3607867909476;3
3607867909469;2
3607867909568;2
3607867909575;3
3607867909582;3
3607867909599;2
3607867914326;2
3607867912216;4
3607867912209;4
3607867914258;3
3607867920327;1
3607867914265;4
3607867912193;3
3607867914272;2
3607867912223;2
3607867892129;3
3607867892174;2
3607867892136;3
3607868084790;5
3607868084783;6
3607868084806;2
3607867892112;1
3607867912247;2
3607867912254;3
3607867914241;2
3607867912278;1
3607867931484;6
3607867931378;3
3607867931538;3
3607867931514;4
3607867894543;1
3607867894437;2
3607867894420;3
3607867894512;2
3607867894536;2
3607867894529;3
3607867894444;1
3607867894413;1
3607867914319;5
3607867340095;4
3607867340088;4
3607867912308;2
3607867912322;1
3607867912315;3
3607867912292;1
3607867385362;2
3607867536719;9
3607867536726;8
3607867545988;5
3607867390861;1
3607867390793;6
3607867921959;2
3607867475254;7
3607867475230;5
3607867475223;5

Pas forcément très représentatif car il n'a aucune valeur >= 15 alors que cela peut se présenter.
J'ai pensé utiliser l'algorithme du simplexe mais je ne pense pas qu'il soit applicable avec une série en entrée. Enfin je ne vois pas comment l'appliquer dans ce cas là.
Votre avis svp: on peut optimiser ça ou c'est du np-complet ? Me rappelle furieusement le problème du sac à dos ça.

[dourouc05]

Pas forcément très représentatif car il n'a aucune valeur >= 15 alors que cela peut se présenter.
J'ai pensé utiliser l'algorithme du simplexe mais je ne pense pas qu'il soit applicable avec une série en entrée. Enfin je ne vois pas comment l'appliquer dans ce cas là.
Votre avis svp: on peut optimiser ça ou c'est du np-complet ? Me rappelle furieusement le problème du sac à dos ça.

Peu importe la classe de complexité, il est probablement possible de résoudre des instances assez grandes (en nombre de colis) en des temps raisonnables . Une solution sous la forme de programme en nombres entiers me paraît effectivement adaptée au cas pour t'assurer d'avoir une solution optimale.

Maintenant, ne t'amuse pas à implémenter un simplexe toi-même avec tout ce qu'il faut à côté, ça ne sera très probablement pas assez efficace. lp_solve dispose d'un API PHP (http://lpsolve.sourceforge.net/5.5/PHP.htm) ; sinon, tu peux générer un modèle AMPL (juste la partie données) depuis PHP, appeler un exécutable (AMPL, GLPK) ou plusieurs (GLPK pour un fichier LP, puis un solveur) et récupérer le résultat.

Intuitivement, cependant, l'énoncé me paraît étrange… Maximiser le nombre de colis ? Serait-ce pour minimiser le poids des marchandises dans chacun pour éviter la casse au chargement ou déchargement ? Ça pourrait être plus intéressant de modéliser le poids d'un produit, dans ce cas : mettre une borne pour le poids dans un colis et minimiser le nombre de colis.

[Flodelarab]

Bonjour,

j'ai aussi tiqué sur la maximisation du nombre de colis. Si c'était le cas, tu ferais un colis par produit et on passe à autre chose.

Si il s'agit réellement de faire 8 paquets, peut-être que d'explorer toutes les possibilités est envisageable.

Enfin, le code est en php. Si c'est pour un site web, le serveur php ne va pas aimer l'exploration de toutes les possibilités.

[anapurna]

salut

tiens moi j'aurais instinctivement fait l'inverse j'aurais pris la valeur et complété avec les valeur maximale

donc dans ton exemple je commencerais par 1 que je complète avec 9 => 10 reste 5 que je récupère sur une autre reference
la seconde je prend encore 1 que je complète avec 8 puis avec 6
la troisième boucle le mini seras 2 car avec le 1 je ne peut pas faire un carton complet
donc 2 avec 7 et 6
au quatrième tour on retrouvera le 3 avec le 6 et le 6
...
ainsi de suite au final tu fini par les 5 et tu trouve effectivement 8 cartons


PS :

je viens de verifier le nombre de combinaison possible n'est pas terriblement important
je suppose donc quand terme d'optimisation on peut accelere les chose

voici les combinaison possible

1 9 5
1 8 6
1 7 7
2 9 4
2 8 5
2 7 6
3 9 3
3 8 4
3 7 5
3 6 6
4 7 4
4 6 5
5 5 5

sachant que tes données peuvent se réduire à un tableau réduit de ce genre

val Nb Qte
1 20 20
2 33 66
3 26 78
4 20 80
5 9 45
6 8 48
7 1 7
8 1 8
9 1 9
119 361

[Flodelarab]

voici les combinaison possible

Euh... il en manque quelques unes:

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
0,1,14
0,2,13
0,3,12
0,4,11
0,5,10
0,6,9
0,7,8
0,8,7
0,9,6
0,10,5
0,11,4
0,12,3
0,13,2
0,14,1
0,15,0
1,2,12
1,3,11
1,4,10
1,5,9
1,6,8
1,7,7
1,8,6
1,9,5
1,10,4
1,11,3
1,12,2
1,13,1
1,14,0
2,3,10
2,4,9
2,5,8
2,6,7
2,7,6
2,8,5
2,9,4
2,10,3
2,11,2
2,12,1
2,13,0
3,4,8
3,5,7
3,6,6
3,7,5
3,8,4
3,9,3
3,10,2
3,11,1
3,12,0
4,5,6
4,6,5
4,7,4
4,8,3
4,9,2
4,10,1
4,11,0
5,6,4
5,7,3
5,8,2
5,9,1
5,10,0
6,7,2
6,8,1
6,9,0
7,8,0

[anapurna]

salut

non pas avec les qte fourni
sachant que la référence a zéro n'est pas possible

voici pour les qte de 15 maxi

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
 
1 13 1
1 12 2
1 11 3
1 10 4
1 9 5
1 8 6
1 7 7
2 11 2
2 10 3
2 9 4
2 8 5
2 7 6
3 9 3
3 8 4
3 7 5
3 6 6
4 7 4
4 6 5
5 5 5

allez parce que je suis de bon humeur je te fournis l'algo pour trouver les combinaisons

Code php :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
$soluce = array();
$max = 15;
$totVal = 15; 
for ($i=1;$i<=$max;$i++)
{  for ($j=$max;$j>=$i;$j--)
	{ for ($k=$j;$k>=$i;$k--)
      {  if  (($i+$j+$k )== $totVal )
		  {$soluce[] = array($i,$j,$k);
	       Echo  $i.' '.$j.' '.$k.'<BR>';
		   }
  	  }
    }
}

voila n'ayant pas de valeur au dessus de 9 j'ai pas pris la peine de mettre les combinaison correspondante
lors du parcours de recherche des éléments lorsque indice égale a la Qte atteindra 0 ... il faudras enlevé de ce tableau
toutes les ligne où cette indice est présent

reprenons l'exemple sachant que l'on a 9 elements maxi dans son exemple
au premier tour le nombre de soluce possible est donc =>

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
1 9 5
1 8 6
1 7 7
2 9 4
2 8 5
2 7 6
3 9 3
3 8 4
3 7 5
3 6 6
4 7 4
4 6 5
5 5 5

on epuisse le stock de 9
on enleve donc des soluce possible la ou se trouve le 9

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
1 8 6
1 7 7
2 8 5
2 7 6
3 8 4
3 7 5
3 6 6
4 7 4
4 6 5
5 5 5

au deuxième tour c'est le 8

Code :

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

1
2
3
4
5
6
7
8
 
1 7 7
2 7 6
3 7 5
3 6 6
4 7 4
4 6 5
5 5 5

et ainsi de suite

[anapurna]

Euh... il en manque quelques unes:

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
 
 
0,5,10
0,10,5
5,10,0
 
0,4,11
0,11,4
4,11,0
 
0,3,12
0,12,3
3,12,0
 
0,2,13
2,13,0
0,13,2
 
0,1,14
0,14,1
1,14,0
 
6,9,0
0,6,9
0,9,6
...

il y a quelque redondance dans tes combinaisons
la position des éléments n'a aucune importance