Pb de programation linéaire: chaine de restaurants

[invite2b0d5b90]

Bonjour,

Dans les finaux de la première tranche nous avions eu un exercice à résoudre qui ne ressemblait pas à ce qu'on avait l'habitude de traiter, personnellement je trouvais que la modélisation du problème est la chose la plus facile; pourtant cet exemple m'a contredit...
Bref,voici le problème:
Une ville dispose des quartiers
Une chaine de restaurants souhaite minimiser le nombre de restaurants à ouvrir dans cette ville, de façon à ce que chaque quartier possède un restaurant ou dispose d'un restaurant dans le quartier adjacent.
Soit:

1 si on ouvre un restaurant dans le quartier
0 sinon
Determiner le problème linéaire à résoudre our déterminer combien de restaurant il faut ouvrir et dans quels quartiers.

----------------------------------------
Ma résolution:



sous:





















Biensur avec les

A vos corrections
Merci d'avance
-----

[invite2b0d5b90]

Ps: Danq la pièce jointe ce trouve le dessin explicatif, je ne sais pas s'il faut impérativement s'y appuiyer, mais en ce qui me concerne je m'y suis référer pour écrire les contraintes.

[invite69d38f86]

les contraintes ne sont pas <= 1 mais >= 1 (au moins un restaurant dans le voisinage).
on résout d'abord avec les 10 équations égales à 1 (on calcule la somme)
puis 9 égales à 1 et une égale 2 en permutant
puis 8 égales à 1 et deux égales à 2 etc

pour un graphe quelconque l'optimal n'est pas forcément le résultat avec 1 restau maximum dans le voisinage
de chaque quartier.

[invite2b0d5b90]

Je vois plutôt que puisqu'il s'agit d'une minimisation les contraintes vont être <= plutôt que >= puisqu'on cherche à minimiser le nombre de restaurants à instaurer...
Pour le reste de ta proposition de résolution je n'ai pas vraiment compris :s Des explications supplémentaires pourront m'éclaircir la modélisation que tu propose.

[A voir en vidéo sur Futura]

[invite69d38f86]

Ce qu'il faut minimiser c'est N = n1 + n2 + ... + n10
tout en vérifiant 10 conditions qui demandent que por chaque quartier il y ait au moins un restaurant
dans le quartier ou dans les quartiers adjacents.
par exemple pour le quartier 1 adjacents aux quartiers 2 et 3, tu dois avoir n1 + n2 + n3 > 0 (ou >= 1)
de meme pour les autres quartiers.
Ca te donne 12 inequations + N à minimaliser
Tu peux transformer ces 10 inéquations en des ensembles de 10 equations
par exemple:
n1 + n2 + n3 = 1
...
n2 + n3 + n4 + n8 + n9 + n10 = 1
tu commence avec N <= 10
tu cherches s'il y a uns solution avec des n_i non négatifs
ensuite tu recommences avec
n1 + n2 + n3 = 2
...
n2 + n3 + n4 + n8 + n9 + n10 = 1
(la premiere equation équation avec 2 et les autres avec 1)
si tu as une solution avec un meilleur N tu le gardes
et tu continues
Je ne suis pas sur que ce soit l' algorithme le plus rapide

[invite69d38f86]

On ecrit également
0 < n1 + n2 + n3 <= 3
...
0 < n2 + n3 + n4 + n8 + n9 + n10 <= 6

[invite2b0d5b90]

Ce n'ai pas joli à voir,mais je pense que tn analyse du problème est juste, à part ça je pense que les contraintes doivent être au sens d'égalité...
Il devrait y avoir une façon plus concise de procéder vu le temps qu'on nous a accordé Je pense que j'irai demander au prof pour en avoir le coeur net.

[invite69d38f86]

je serai intéressé par la réponse propre.

[invite69d38f86]

Cet exercice a t il été corrigé?

[invite2b0d5b90]

Je me suis procuré l'e-mail du professeur dimanche et je lui ai écrit hier soir, je pense qu'on devrait attendre un peu de temps encore

[invite501e8040]

Je vois plutôt que puisqu'il s'agit d'une minimisation les contraintes vont être <= plutôt que >= puisqu'on cherche à minimiser le nombre de restaurants à instaurer...

attention ! faute grâve !
Les contraintes sont juste des contraintes, et pas forcément avec des > et <. Par exemple on peut avoir comme contrainte de devoir travailler avec des Naturels plutôt que des Réels. Je peux aussi imposer d'avoir un resto en 6 ou encore de ne pas en avoir en 3.
La minimisation se trouve dans le min devant la sommation, c'est tout.
D'ailleurs dans l'énoncé il est dit que Vj est soit 0 soit 1, or c'est déjà une contrainte qui n'est pas présente dans la solution proposée. (Et en passant le plus difficile dans ce genre de problèmes c'est de trouver les variables adéquates ! et si on a du mal à trouver les bonnes contraintes il faut peut être y voir une erreur dans le choix des variables)

Le problème décrit ici est celui du dominating set : http://en.wikipedia.org/wiki/Dominating_set
qui est équivalent au plus connu set cover problem : http://en.wikipedia.org/wiki/Hitting_set

donc la résolution était presque bonne, il faut juste remplacer les <= par des >= et dire que Vj vaut soit 0 soit 1