Calcul de combinaison

Version imprimable

08/01/2015, 10h24
kohoji

Calcul de combinaison
Bonjour à tous,

Tout d'abord merci à tout ceux qui pourront m'aider et me conseiller.

J'ai un fichier dont voici le contenue :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 fee day 130 9 150 12 190 20 190 23 230 27 290 33 330 31 70 9 330 30 110 9 90 6 310 34 330 34 190 22 230 25 170 13
Je dois concevoir un programme me permettant de trouver la plus grande somme de charge
pour un total de 100 jours maximum.

Y-a t-il un algorithme sur lequel je peux me baser ?
08/01/2015, 11h31
dourouc05

:salut:

À ma connaissance, pas d'algorithme prévu pour ça ; par contre, ça semble être un bon cas d'utilisation de la programmation dynamique : déterminer la plus grande somme pour au plus n jours en utilisant les m premières entrées de ta liste ; écrire une équation pour m+1 et n+1 en fonction des résultats déjà calculés.
08/01/2015, 12h10
kohoji

Ok, je regarde ça de plus prêt et j'essaye de faire un petit quelque chose avec que
je posterai ici même.

Merci.

EDIT : Je pense que ça s'en rapproche http://fr.wikipedia.org/wiki/Probl%C...sac_%C3%A0_dos
08/01/2015, 12h26
anapurna

salut

alors sans trop réfléchir j'aurais dis que dans un premier temps
je ferais le ratio fee / day
dans un deuxième temps je ferais le trie sur ce ratio et enfin
j'essaierais d'obtenir mes 100 jours en prenant de préférence le ratio le plus élevé

voilà ci cela peut te mettre sur la voie
08/01/2015, 12h39
kohoji

ça marche !

Je prend note est je travaille dessus.

Merci
08/01/2015, 14h47
kolodz

Cela ressemble de très près au problème du sac à dos :
http://fr.wikipedia.org/wiki/Probl%C...sac_%C3%A0_dos

L'idée de ce problème est :
Pour un sac à dos limité en poids, comment optimiser les objets choisit pour prendre le plus de valeur possible.
Sachant que chaque objet à un poids et une valeur.

Si on transpose ton problème :
day = poids
fee = valeur

On a exactement le même problème :
- Comment avoir le plus de "fee" ou X "day" de capacité ?

C'est un problème NP complet. Donc pas d'algorithmes super rapide et optimal. Mais, il existe déjà des algorithmes "simpliste" qui propose des solutions "approchantes".

Cordialement,
Patrick Kolodziejczyk.

Alors voilà, après quelque recherche sur ce fameux sac j'ai pue faire quelque chose de potable.

Bon il manque encore la lecture direct du fichier mais sinon j'ai un bon résultat à savoir fee = 1170 pour 99/100 day
J'ai fait le programme en Ruby

Code:

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
Items = Struct.new(:day, :fee)
Settings = Struct.new(:rows, :max_day)
 
def zeros(rows, cols)
  Array.new(rows) do |row|
    Array.new(cols, 0)
  end
end
 
def op_main(settings)
  num_rows = settings.rows.size
  rows = settings.rows
  max_day = settings.max_day
 
  day_matrix = zeros(num_rows, max_day+1)
 
  num_rows.times do |i|
    (max_day + 1).times do |j|
      if(rows[i].day > j)
        day_matrix[i][j] = day_matrix[i-1][j]
      else
        day_matrix[i][j] = [day_matrix[i-1][j], rows[i].fee + day_matrix[i-1][j-rows[i].day]].max
      end
    end
  end
 
  day_matrix
end
 
if $0 == __FILE__
 
    rows = [
      Items.new(9   , 130) , Items.new(12  , 150)  , 
      Items.new(20 , 190) , Items.new(23  , 190) , 
      Items.new(27  , 230)  , Items.new(33  , 290)  , 
      Items.new(31  , 330)  , Items.new(9  , 70)  , 
      Items.new(30  , 330)  , Items.new(9  , 110)  , 
      Items.new(6  , 90)  , Items.new(34  , 310)  , 
      Items.new(34  , 330)  , Items.new(22  , 190)  , 
      Items.new(25  , 230)  , Items.new(13  , 170)  
    ]
 
  settings = Settings.new(rows, 100)
 
  day_matrix = op_main settings
  puts 'fee: ' + day_matrix.last.last.to_s
end

08/01/2015, 16h00
kolodz

J'avoue que je ne suis pas capable de décoder l’algorithme utilisé à partir du code Rubis.
J'ai l'impression que c'est l'algorithme glouton que tu utilise. Ce n'est pas celui qui offre le meilleur résultat, mais il est déjà relativement efficace.

As-tu besoin d'un algorithme qui teste l'ensemble de combinatoire possible ou celle-ci te suffit ?

Cordialement,
Patrick Kolodziejczyk.
08/01/2015, 16h08
kohoji

Je prend toute solution possible, cela me permettra d'optimiser mon programme.

Si tu as des conseils je suis preneurs ;)

hello,

avec un peu de retard, un peu overkill mais ca s'y prete bien, tu peux utiliser la plne, idem l'algo du simplexe
soit x_i qui vaut 0 ou 1 selon qu'on choisit la ligne, a_i tes fees associés, et b_i le nombre de jours

ta fonction objective est

Code:

1
2
3
f(x_i) = a_i.x_i
s.c
somme(b_i.x_i) < 100

avec octave et glpk par exemple

Code:

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
 
arr = [
  [130 9],
  [150 12],
  [190 20],
  [190 23],
  [230 27],
  [290 33],
  [330 31],
  [70  9],
  [330 30],
  [110 9],
  [90  6],
  [310 34],
  [330 34],
  [190 22],
  [230 25],
  [170 13]
];
fees = arr(:,1);
days = arr(:,2);
n = length(fees);
c = fees';
A = days';
b = 100;
lb = zeros(n,1)';
ub = ones(n,1)';
ctype = "U"
vartype = repmat ("I", 1, n)
s = -1;
 
[x, fmax] = glpk (c, A, b, lb, ub, ctype, vartype, s)

result

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
x =
 
   1
   1
   1
   0
   0
   0
   0
   0
   1
   1
   1
   0
   0
   0
   0
   1
 
fmax =  1170

12/01/2015, 11h50
dourouc05

Citation:

Envoyé par galerien69

avec un peu de retard, un peu overkill mais ca s'y prete bien, tu peux utiliser la plne, idem l'algo du simplexe

« plne » pour programmation linéaire non entière ?

Le simplexe ne suffira pas dans ce cas : les solutions données ne sont pas forcément entières. Si la matrice des contraintes est totalement unimodulaire (déterminant qui vaut $Formule mathématique$ ), alors la solution sera forcément entière (les coefficients des variables dans les contraintes sont +1, 0 ou -1), mais ça n'est pas le cas ici (coefficients $Formule mathématique$ dans les contraintes, alors que le nombre de jours du problème posé n'est jamais unitaire).

Autre justification, plus théorique encore : si le simplexe était suffisant, il serait équivalent d'utiliser une méthode du point intérieur (polynomiale), de récupérer une base de variables au besoin (http://www.caam.rice.edu/caam/trs/91/TR91-32.pdf semble donner un algorithme polynomial) ; par conséquent, il serait possible de résoudre le problème du sac à dos en un temps polynomial, ce qui contredit ce qui a été dit plus haut (« problème NP complet »).

Donc il faut englober le simplexe dans un algorithme par séparation et évaluation. En prenant un code commercial (type CPLEX, Gurobi), ça pourrait être très efficace (pour des problèmes de taille suffisamment grande), mais aussi très cher (sauf licences académiques). Avec un GLPK ou LP_solve ou CBC, les temps de calcul pourraient ne pas trop exploser, mais sans certitude (http://scip.zib.de/).

(Je n'avais pas proposé cette solution justement parce qu'elle me semblait excessive au niveau formalisme. Par contre, elle assure de donner la solution optimale, sans nécessiter beaucoup de code, généralement avec de bonnes performances.)

(e) C'est là que je me rends compte que c'est encore un beau pavé :aie:. Dans le bout de code que tu as mis, tu précises bien "I" comme type de variable : GLPK utilisera un certain nombre de tableaux du simplexe pour la résolution…

(e2) Pour être bien clair : je partais dans l'idée que tu proposais d'implémenter le simplexe pour résoudre ce problème, pas d'utiliser des outils déjà prêts.
11/02/2015, 21h59
Invité

j'avais raté ta réponse.. du coup encore plus de retard..

J'ai pas regardé le lien lié à ton analogie, mais je pense qu'elle est fausse.
Tu peux très bien résoudre (théoriquement ou pour de petits n) le voyageur du commerce avec un simplexe..

toute facon faut pas se fouler, on voit bien si ca prend une tete polynomiale ou exponentielle (factorielle qui traine), mais bon, ca mange pas de pain d'essayer
11/02/2015, 22h25
dourouc05

Citation:

Envoyé par galerien69

Tu peux très bien résoudre (théoriquement ou pour de petits n) le voyageur du commerce avec un simplexe..

À condition d'utiliser une formulation exponentielle dans la taille des données ;). Construire la matrice des contraintes prend donc un temps exponentiel (s'il existait une transformation polynomiale aussi simple vers un problème de P, ça se saurait :aie:). M'enfin bon, c'est plus de l'ordre du pinaillage qu'autre chose. De toute façon, l'important est de résoudre le problème, pas de se tordre le cerveau :mrgreen:.