Les solutions d'un programme linéaire
Bonsoir à tous, je sais pas si c'est là ou je peux poser ma question mais je pense ça poserai pas de problème c'est pas trop loin des mathématiques, de toute façon ma question est la suivante:
Dans le domaine de programmation linéaire: Est-ce-que la solution d'un programme linéaire donné P est unique, je sais qu'on peut déjà avoir plusieurs solutions réalisables mais est-ce-que lorsqu'on trouve une solution optimale est-elle unique?
Merci pour vos réponses.
Pas nécessairement, mais le plus souvent c'est le cas.
En gros, un problème d'optimisation linéaire, ça revient à trouver le(s) point ou un polyèdre convexe (l'ensemble des points admissibles) est "tangent" avec un hyperplan (le graphe de la fonction à optimiser).
Et, pour résumer, la solution optimale est unique si l'hyperplan n'est pas parallèle à l'une des faces : si l'hyperplan est parallèle, alors c'est toute la face qui est optimale.
Par exemple, optimisersous les contraintes
La solution optimale n'est dans ce cas pas unique (prendre y = 1-x pour x entre 0 et 1 )
Le coup du "parallèle" se voit bien avec un dessin
Merci beaucoup, C'était très explicatif. Cordialement!
Bonsoir tous le monde,
J'arrive pas a savoir quand un problème ne posède pas de solution optimale, en faite que voulons dire par ceci? Est-ce que le nombre de solutions réalisables optimisant la fonction objectif est infini? Ou c'est que le problème n'est même pas borné? Et comment peut-onsavoir que cette solution optimale n'existe pas a l'aide de la méthode du Simplexe?
Prière de m'expliquer tout cela...Merci beaucoup.
Cordialement!
Bonjour,
Tout d'abord je tiens à préciser que j'ai très bien compris l'explication fournie plus haut, qui est d'ailleurs excellente. Cependant, je fais face à un cas où le problème est le suivant:
min 23x1 + 31x2 + 35x3 + 30x4
s.t. :
2x1 + 3x2 + 5x3 + 4x4 >= 740
x1 + x2 + x3 + x4 <= 180
x1 + x2 >= 45
xi>=0
Dans ce cas, on se rend bien compte qu'aucune pente des contraintes est identique à la pente de l'objectif. De plus, dans cet exercice que j'ai trouvé, on ne demande pas non plus d'appliquer le simplexe, et on ne sait donc pas si le cout réduit d'une des variables hors base de ce programme est nulle, ce qui impliquerait la multiplicité des solutions.
Toutefois, après que l'énoncé nous ait demandé d'écrire le programme dual (D), de prouver que la solution y*=(7,0,9) est optimale pour (D), et d'en déduire une solution optimale x* pour (P) on nous demande si x* est l'unique solution optimale de (P).
D'où ma question, étant donné qu'on est bien dans le cas où aucune pente des contraintes est identique à celle de l'objectif, et que l'on ne nous a pas demandé d'appliquer le simplexe, COMMENT savoir si x* est l'unique solution optimale de (P)?
Je crois par ailleurs que le TEC ne permet pas de conclure sur l'unicité prétendue d'une solution.
Merci d'avance.
