Methode simplexe cas particuliers et utilisation des solveur

Télécharger PDF

Programmation Linéaire et Optimisation : Méthode du Simplexe

Ce cours présente des cas pratiques de programmation linéaire, abordant la méthode du simplexe, les valorisations marginales, ainsi que des cas particuliers tels que les solutions non bornées, la dégénérescence duale et le cyclage.

Exercice 1 : Valorisations marginales

Un boulanger fabrique de la brioche (X1) et du pain viennois (X2). Il dispose de trois ingrédients limités : de la farine A (80 unités), du beurre B (24 unités) et du sucre C (36 unités). La production est linéaire et suit les règles suivantes :

Consommation de farine : 5x1 + 4x2 ≤ 80
Consommation de beurre : x1 + 2x2 ≤ 24
Consommation de sucre : 3x1 + 2x2 ≤ 36

Le prix de vente est de 40 pour la brioche et 50 pour le pain viennois. L'objectif est de maximiser le chiffre d'affaires (CA) : Max Z = 40x1 + 50x2.

Résolution par la méthode du simplexe :

Après itérations du tableau du simplexe, nous obtenons la solution optimale suivante :

Production optimale : x1 = 6 brioches et x2 = 9 pains viennois.
Chiffre d'affaires maximum : 690 unités monétaires.
Variables d'écart : s1 = 14 (il reste 14 unités de farine). Les stocks de beurre et de sucre sont totalement épuisés (s2 = 0, s3 = 0).

Analyse des constituants limitants :

Les constituants limitants sont le beurre et le sucre, car leurs stocks sont entièrement consommés à l'optimum. Leurs valorisations marginales (prix fictifs ou coûts d'opportunité) sont :

Beurre (B) : 17,5
Sucre (C) : 7,5

Cela signifie qu'une unité supplémentaire de beurre permettrait d'augmenter le chiffre d'affaires de 17,5, tandis qu'une unité supplémentaire de sucre l'augmenterait de 7,5. La farine n'étant pas totalement utilisée, sa valorisation marginale est nulle.

Exercice 2 : Solutions non bornées

Considérons le problème de maximisation suivant :

Maximiser z = x1 + 2x2 sous les contraintes :

–2x1 + x2 ≤ 2
–x1 + 2x2 ≤ 5
x1 – 4x2 ≤ 4
x1, x2 ≥ 0

Analyse de la résolution :

Lors de l'application de l'algorithme du simplexe, on constate qu'une variable candidate à l'entrée en base possède des coefficients tous négatifs ou nuls dans sa colonne. Cela indique que la zone de recherche est ouverte dans cette direction : la fonction objectif peut augmenter indéfiniment sans jamais violer les contraintes. On conclut que le problème possède une solution optimale non bornée supérieurement.

Exercice 3 : Dégénérescence duale

Maximiser z = 14x1 + 10x3 sous les contraintes :

x1 – x2 + x3 ≤ 3
2x1 + x2 + 4x3 ≤ 8
5x1 – x2 + x3 ≤ 5
x1, x2, x3 ≥ 0

Analyse des solutions :

À l'optimum, on remarque qu'une variable hors base (x2) possède un profit marginal nul. Cela signifie qu'il existe une infinité de solutions optimales (toutes situées sur un segment ou une face du domaine admissible). En faisant entrer x2 dans la base, on obtient une seconde solution de base optimale :

Solution 1 : x1 = 2/3, x3 = 5/3, z = 26
Solution 2 : x1 = 13/7, x2 = 30/7, z = 26

Ce phénomène est appelé dégénérescence duale.

Exercice 4 : Le problème de cyclage

Le cyclage est un phénomène rare où l'algorithme du simplexe tourne en boucle sans jamais atteindre l'optimum. Cela se produit généralement dans des problèmes présentant une forte dégénérescence (plusieurs variables de base sont nulles simultanément).

Dans l'exemple traité, après six itérations du simplexe, le septième tableau s'avère identique au premier tableau initial. L'algorithme répète alors indéfiniment la même séquence de bases sans progresser vers la valeur optimale. Pour éviter cela, on utilise des règles de priorité spécifiques, comme la règle de Bland, qui force le choix des variables pour garantir la convergence.

FAQ sur la Programmation Linéaire

Qu'est-ce qu'une valorisation marginale ?
Il s'agit du gain supplémentaire généré par l'augmentation d'une unité d'une ressource limitée. Elle permet de savoir combien un décideur devrait être prêt à payer pour obtenir davantage de cette ressource.

Pourquoi une solution est-elle dite "non bornée" ?
Une solution est non bornée lorsque les contraintes ne limitent pas la croissance de la fonction objectif dans une certaine direction. Cela signifie souvent que le modèle mathématique a oublié une contrainte réelle.

Comment détecter un cyclage dans le simplexe ?
On détecte un cyclage lorsque l'algorithme repasse par une base (une combinaison de variables) déjà visitée précédemment sans que la valeur de la fonction objectif n'ait été améliorée.