Solutions de contournement alternatives

Parfois, lorsqu’un modèle d’optimisation est formulé, le modèle fournit de nombreuses solutions alternatives alternatives, ce qui signifie que pour la même valeur de la fonction objectif, le modèle produit plusieurs valeurs des variables non fondamentales ou de décision.

Des solutions alternatives alternatives surviennent principalement du fait qu’une partie du polyèdre est parallèle à la fonction objectif. Dans de tels cas, tous les points le long du segment segment qui est parallèle à la fonction obj seront des transformations affines et donneront la même valeur de la fonction obj.

Dans une situation pratique, les implications seraient que lorsque l’on essaie de résoudre un problème, par exemple, en essayant de calculer le profit maximum compte tenu de l’effort de fabrication de 10 produits différents et de la contrainte totale sur la main-d’œuvre disponible dans l’usine. En supposant que le problème a 10 variables de décision et deux contraintes. En raison de la dégénérescence expliquée ci-dessus, il peut fournir une solution optimale avec un profit maximum de 10 000 $ pour plusieurs combinaisons du mix de produits à fabriquer en usine.

Dans de tels cas, il est très difficile de déterminer quel mix de production choisir comme critère optimal, car il existe en fait plusieurs valeurs. La partie parallèle aux bords du polyèdre ou de l’hyperplan reliant deux plans d’un polyèdre à n dimensions peut être facilement perturbée en modifiant légèrement les contraintes.

Les contraintes dans le modèle de programmation linéaire forment les limites du polyèdre ou de l’hyperplan du polyèdre. Mais le simple fait de changer la contrainte, disons de 4*X + 5 * Y < 5 à 4*X + 5 * Y < 5.1 entraînerait une légère modification de la région réalisable, mais cesserait de produire des solutions alternatives alternatives.

Dans le même contexte, nous pouvons également discuter de ce qui constitue un ensemble réalisable convexe et pourquoi les problèmes de programmation linéaire nécessitent que l’ensemble de contraintes soit convexe. La solution optimale d’une formulation de programmation linéaire est trouvée en parcourant l’ensemble des contraintes d’un sommet à l’autre. Alors pourquoi une solution optimale ne tombe-t-elle pas quelque part sur une arête reliant deux sommets, mais uniquement sur le sommet ?. En effet, l’ensemble des possibles peut être considéré comme une frontière imposée par des contraintes. Les contraintes d’un modèle de programmation linéaire se traduiraient par un polyèdre/polytope. Lorsqu’elle est convexe, cela signifie que tout point reliant les deux sommets n’est pas à l’intérieur, et donc la solution extrémale de la fonction objectif se trouvera nécessairement sur le sommet.

Retour en haut