Discussion :

[Trap D]

pcaboche >> Il me semble que ce que tu as écrit ne respecte pas les contraintes du problème:

40 / 50 / 10 / 00 / 00 / -> 100
00 / 00 / 60 / 00 / 60 / -> 120
00 / 00 / 00 / 90 / 30 / -> 120

40 50 70 90 90
en ajoutant 1 dans une case qui vaut 0 le programme doit changer les cases non nulles sans changer les sommes des lignes et les sommes des colonnes

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
:- use_module(library('clp/bounds')).
 
resoud(Vars) :-
 
  Vars =
   [A1, A2, A3, A4, A5,
    B1, B2, B3, B4, B5,
    C1, C2, C3, C4, C5],
 
  Vars in 1..120,
 
  A1 + A2 + A3 + A4 + A5 #= 100,
  B1 + B2 + B3 + B4 + B5 #= 120,
  C1 + C2 + C3 + C4 + C5 #= 120,
 
  A1 + B1 + C1 #= 40,
  A2 + B2 + C2 #= 50,
  A3 + B3 + C3 #= 70,
  A4 + B4 + C4 #= 90,
  A5 + B5 + C5 #= 90,
 
  label(Vars),
 
  write([A1, A2, A3, A4, A5]), nl,
  write([B1, B2, B3, B4, B5]), nl,
  write([C1, C2, C3, C4, C5]), nl.

[Trap D]

En cherchant un peu, je propose celà, sachant que c'est bien incomplet, dans une situation réelle, il faut pouvoir affecter à la bonne variable la valeur 1, (ici c'est W) :

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
:- use_module(library('clp/bounds')).
 
resoud(Vars) :-
 
  Vars =
   [A1, A2, A3, 
    B3, B5,
    C4, C5],
 
  Vars in 1..120,
 
  A1 + A2 + A3 +  X +  Y #= 100,
   Z +  T + B3 +  U + B5 #= 120,
   V +  W +  L + C4 + C5 #= 120,
 
  A1 +  Z +  V #= 40,
  A2 +  T +  W #= 50,
  A3 + B3 +  L #= 70,
   X +  U + C4 #= 90,
   Y + B5 + C5 #= 90,
 
  X = 0, Y = 0, 
  Z = 0, T = 0, U = 0, 
  V = 0, W = 1, L = 0,
 
  label(Vars),
 
  write([A1, A2, A3,  X,  Y]), nl,
  write([ Z,  T, B3,  U, B5]), nl,
  write([ V,  W,  L, C4, C5]), nl.

[pcaboche]

pcaboche >> Il me semble que ce que tu as écrit ne respecte pas les contraintes du problème

En effet, mais en ajoutant 1 quelque part, il faut retirer 1 dans la ligne et la colonne.

A mon avis, il manque des contraintes (on n'a pas tout l'énoncé du problème)

De plus le problème doit être résolu en C...

[andjeo]

pcaboche >> Il me semble que ce que tu as écrit ne respecte pas les contraintes du problème

En effet, mais en ajoutant 1 quelque part, il faut retirer 1 dans la ligne et la colonne.

A mon avis, il manque des contraintes (on n'a pas tout l'énoncé du problème)

De plus le problème doit être résolu en C...

exactement!

[pcaboche]

D'accord, mais:

le problème c'est qu'il faut que j'utilise ce que j'ai appris cette année et je n'ai appris que les bases du C.

Le problème, c'est qu'on ne sait pas ce que tu as appris cette année!

A part ça, j'ai l'impression qu'il manque quelque chose dans ton énoncé. Au moins un exemple complet de résolution.

[Matthieu Brucher]

Oui, je trouve aussi qu'il manque quelqque chose car, OK, on modifie la matrice selon des contraintes. Mais on en fait quoi ? C'est quoi le but ? Minimiser le carré des éléments de la matrice ? L'âge du capitaine ?

[FrancisSourd]

Au risque de paraître lourdingue, ce n'est qu'un chemin augmentant dans un graphe biparti...

[andjeo]

D'accord, mais:

le problème c'est qu'il faut que j'utilise ce que j'ai appris cette année et je n'ai appris que les bases du C.

Le problème, c'est qu'on ne sait pas ce que tu as appris cette année!

A part ça, j'ai l'impression qu'il manque quelque chose dans ton énoncé. Au moins un exemple complet de résolution.

Les bases cad les boucles if, for, while...
l'exemple complet de résolution, il se trouve à la première page

[andjeo]

Oui, je trouve aussi qu'il manque quelqque chose car, OK, on modifie la matrice selon des contraintes. Mais on en fait quoi ? C'est quoi le but ? Minimiser le carré des éléments de la matrice ? L'âge du capitaine ?

le but est d'identifier les cases auxquelles on ajoute ou retranche un qui par la suite seront multiplier par 1 ou -1 les cases correspondantes d'un autre tableau.

d'après cet exemple:
40 / 49 / 11 / 00 / 00 /
00 / 00 / 59 / 00 / 61 /
00 / 01 / 00 / 90 / 29 /

d'après cet exemple on a donc changé les cases suivantes:
1/2 ->-1
1/3->+1
2/3->-1
2/5->+1
3/2->+1
3/5->-1

ensuite j'ai un autre tableau du style

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

grace aux resultats precedent je peux calculer cela:
DELTA= -1*5+1*7-1*5+1*6+1*3-1*2=4

[Matthieu Brucher]

Rien compris.
Ton but, à part ajouter des 1 et des -1 - c'est simple, on ajoute que des 1/-1 sur une ligne et -1/1 sur une autre avec les colonnes adéquates -, on ne sait pas le but de faire ça. C'est joli, mais ton objectif, c'estq ue la matrice fasse quoi ? Maximiser le delta ? C'est quoi la formule, d'ailleurs ?

[FrancisSourd]

[quote="andjeo"]

Oui, je trouve aussi qu'il manque
grace aux resultats precedent je peux calculer cela:
DELTA= -1*5+1*7-1*5+1*6+1*3-1*2=4

Tu peux être plus explicite sur le but de ton projet?
Franchement, cela ressemble vraiment à l'algorithme hongrois et au calcul d'affectation optimale (et donc aux flots dont je te parle depuis le début).

J'ai réfléchi à nouveau à ton problème et ce n'est pas possible qu'on te pose ce problème si tu n'es pas censé avoir un minimum de connaissances en graphe ou en algorithmique

[andjeo]

[quote="FrancisSourd"]

Oui, je trouve aussi qu'il manque
grace aux resultats precedent je peux calculer cela:
DELTA= -1*5+1*7-1*5+1*6+1*3-1*2=4

Tu peux être plus explicite sur le but de ton projet?
Franchement, cela ressemble vraiment à l'algorithme hongrois et au calcul d'affectation optimale (et donc aux flots dont je te parle depuis le début).

J'ai réfléchi à nouveau à ton problème et ce n'est pas possible qu'on te pose ce problème si tu n'es pas censé avoir un minimum de connaissances en graphe ou en algorithmique

Je ne sais pas si tu connais mais je veux programmer en C la méthode du stepping-stone.
Les cours d'algorithme que j'ai eu sont les bases cad apprendre les boucles et a faire un tableau donc vraiment les bases et pour le C que j'ai appris ca se resume aux boucles if for et while.

[andjeo]

Rien compris.
Ton but, à part ajouter des 1 et des -1 - c'est simple, on ajoute que des 1/-1 sur une ligne et -1/1 sur une autre avec les colonnes adéquates -, on ne sait pas le but de faire ça. C'est joli, mais ton objectif, c'estq ue la matrice fasse quoi ? Maximiser le delta ? C'est quoi la formule, d'ailleurs ?

ok lol dsl
je vais essayer de mieux expliquer
voilà le sujet:
je dois programmer la méthode du stepping-stone, c'est une méthode permettant d'établir un plan de tranport afin que le coût soit minimale.
dans l'exemple que j'ai donné en premiere page, on sait qu'on a 3 fournisseurs dont la capacité respective est 100,120,120 et 5 clients dont les besoins respectifs sont 40,50,70,90,90.
grâce à la méthode du stepping stone on obtient un premier plan de transport initiale qui est le tableau suivant:

40/50/10/00/00
00/00/60/60/00
00/00/00/30/90

En faisant la somme de chaque ligne on trouve bien les 100,120,120 (capacités des fournisseurs) et en faisant la somme de chaque colonne on retrouve bien les 40,50,70,90,90 (besoins des clients)

Ensuite la méthode consiste à ajouter 1 unité dans une case nulle et de calculer le delta comme je l'ai expliquer avant. Si le delta est negatif cela signifie que en substituant la plus petite des valeurs où l'on à retrancher 1 et qu'on l'ajoute à la case qui était nulle(case où l'on a ajouté 1 unité) , on a un bénéfice.

Pour le moment mon programme réussi a établir ce premier plan de tranport et à calculer le plus petit delta négatif et à subsitituer la quantité.

Le problème est que désormais le plan à changer et ce que j'ai programmer n'arrive qu'à calculer tous les delta d'un plan de transport initiale.

[FrancisSourd]

Je ne sais pas si tu connais mais je veux programmer en C la méthode du stepping-stone.
Les cours d'algorithme que j'ai eu sont les bases cad apprendre les boucles et a faire un tableau donc vraiment les bases et pour le C que j'ai appris ca se resume aux boucles if for et while.

C'est effectivement une généralisation de l'algorithme hongrois. Les gens qui ont découvert ces algorithmes sont des mathématiciens aguerris (qui connaissaient les graphes!)

Je ne pense pas qu'on te demande de réinventer cet algorithme et tu dois avoir l'algorithme écrit quelque part, non? Cette phase d'amélioration de la solution ne se réinvente pas facilement...

Encore une fois, cela s'interprète en théorie des graphes. On peut écrire l'algo sans introduire formellement les graphes mais cela ne s'invente pas non plus...

[pcaboche]

Franchement, cela ressemble vraiment à l'algorithme hongrois et au calcul d'affectation optimale

Tu as des liens là-dessus? Parce que j'ai étudié les graphes mais je ne me souviens pas de ces algorithmes (ou du moins le nom ne me dit rien).

[andjeo]

Je ne sais pas si tu connais mais je veux programmer en C la méthode du stepping-stone.
Les cours d'algorithme que j'ai eu sont les bases cad apprendre les boucles et a faire un tableau donc vraiment les bases et pour le C que j'ai appris ca se resume aux boucles if for et while.

C'est effectivement une généralisation de l'algorithme hongrois. Les gens qui ont découvert ces algorithmes sont des mathématiciens aguerris (qui connaissaient les graphes!)

Je ne pense pas qu'on te demande de réinventer cet algorithme et tu dois avoir l'algorithme écrit quelque part, non? Cette phase d'amélioration de la solution ne se réinvente pas facilement...

Encore une fois, cela s'interprète en théorie des graphes. On peut écrire l'algo sans introduire formellement les graphes mais cela ne s'invente pas non plus...

La seule chose que je connaisse est la méthode du stepping-stone sur papier, on ne m'a jamais donner d'algorithme.
Je ne peux pas utiliser ta théorie des graphes car je ne la connais pas.
Le sujet que l'on m'a donné est de se mettre à la place d'une société de transport et de créer un système flexible aux niveaux des capacités, des besoins et des prix, de proposer une solution initiale et de proposer des démarches d'améliorations. C'est tout ce qu'on m'a donné.
Moi ce que j'ai réussi à faire est de faire un programme flexible donnant une solution initiale et proposant qu'une seule démarche d'améliorations ce que j'ai expliqué dans un message d'avant et tout ça je l'ai inventer seul et sans algorithme.

[FrancisSourd]

Franchement, cela ressemble vraiment à l'algorithme hongrois et au calcul d'affectation optimale

Tu as des liens là-dessus? Parce que j'ai étudié les graphes mais je ne me souviens pas de ces algorithmes (ou du moins le nom ne me dit rien).

C'est vrai qu'en France, on ne parle pas beaucoup de cet algorithme qui n'a plus qu'un intérêt historique puisqu'il peut être vu comme un cas particulier des flots à coûts minimal. Du coup, je ne connais pas de lien en Français vraiment détaillé.

Le wikipedia US est bien fait:
http://en.wikipedia.org/wiki/Hungarian_algorithm

[FrancisSourd]

La seule chose que je connaisse est la méthode du stepping-stone sur papier, on ne m'a jamais donner d'algorithme.

Je ne vois pas bien la différence entre "méthode sur papier" et "algorithme". Est-ce que cela veut dire dans ton cas qu'absolument rien n'est dit sur la manière de trouver les cases à augmenter et à diminuer?

[andjeo]

La seule chose que je connaisse est la méthode du stepping-stone sur papier, on ne m'a jamais donner d'algorithme.

Je ne vois pas bien la différence entre "méthode sur papier" et "algorithme". Est-ce que cela veut dire dans ton cas qu'absolument rien n'est dit sur la manière de trouver les cases à augmenter et à diminuer?

Je vais te citer mon cours concernant ce passage:
Pour savoir si cette solution constitue l’optimum, on va considérer une par une chacune des cases n’ayant pas reçues d’affectation (0) et calculer la différence de prix de transport (ou coût marginal) qui résulterait de l’affectation d’une unité dans cette case.
Si l’on affecte par exemple une unité dans la case (A, 4), il faut alors en retirer une de la case (A, 3), en ajouter une dans la case (B, 3) et finalement en retirer une dans la case (B, 4).
Cet échange d’une unité fait varier le coût total d’une quantité :
δ (A, 4) = 6-2+3-5=2 (bilan positif)
Si le bilan financier est positif, cela veut dire que cette opération créerait une dépense supplémentaire et n’est donc pas intéressante.

Si le bilan financier est négatif, cela veut dire que cette opération créerait une économie et est donc intéressante.

De la même manière, il faut évaluer de tels échanges pour les autres cases.

On retient l’opération qui apporte le plus d’économie c’est-à-dire celle dont le bilan négatif est le plus important.
C’est cette opération qui sera effectivement appliquée en déplaçant le plus grand nombre d’unités possibles.
Ce nombre correspond à la plus petite quantité présente dans l’une des cases de la substitution (où l’on a retirée une unité en test).

On réitère cette opération jusqu’à l’obtention d’une solution optimale. Cette solution est atteinte lorsque tous les δ (i, j) sont positifs.

[Trap D]

Je n'ai pas compris le calcul de δ (A, 4)

Pour savoir si cette solution constitue l’optimum, on va considérer une par une chacune des cases n’ayant pas reçues d’affectation (0) et calculer la différence de prix de transport (ou coût marginal) qui résulterait de l’affectation d’une unité dans cette case.
Si l’on affecte par exemple une unité dans la case (A, 4), il faut alors en retirer une de la case (A, 3), en ajouter une dans la case (B, 3) et finalement en retirer une dans la case (B, 4).
Cet échange d’une unité fait varier le coût total d’une quantité :
δ (A, 4) = 6-2+3-5=2 (bilan positif)
Si le bilan financier est positif, cela veut dire que cette opération créerait une dépense supplémentaire et n’est donc pas intéressante.