LP : cas particuliers (exercices – solutions)

Cas particuliers

Ce TD propose des exercices corrigés sur des cas particuliers (dégénérescence, grand M, simplexe en deux phases).

Tutoriel

Un brooker a besoin, pour sa clientèle, de 108 MWh d’électricité pour la ville 1 et de 96 MWh d’électricité pour la ville 2. Cependant, les lois de Kirchhoff ne permettent pas à un distributeur de cibler une ville unique pour le transit énergétique. Deux distributeurs desservent ces villes : le Distributeur A peut envoyer 12 MWh à la ville 1 et 8MWh à la ville 2 par lot acheté; le Distributeur B peut envoyer 9 MWh à la ville 1 et 12 MWh à la ville 2 par lot acheté. Les lots ont tous le même prix. Combien de lots doit acheter le brooker pour combler la demande énergétique des deux villes ? Résoudre par méthode graphique et par le simplexe.

Correction

Le programme linéaire est le suivant : X1 pour le premier lot et X2 pour le deuxième lot

cas particuliers programmation linéaire forme primale exercices corrigés

Ce qui donne pour résolution graphique :

programmation linéaire forme primale exercices corrigés

Le gradient est (-1, -1) car c’est un minimum (min f(x) = – max -f(x)). Dans le domaine de définition en vert, le point C est le seul extremum étant un optimum global. La résolution du système précédent sous forme d’égalité donne pour coordonnées (6, 4) avec Z = 10.

Pour la résolution du simplexe il faut avant tout se ramener à la forme standard.

programmation linéaire simplexe en deux phases dégénéré méthode du grand M

Il faut résoudre le simplexe en deux phases afin d’éliminer les variables artificielles :

programmation linéaire simplexe en deux phases dégénéré méthode du grand M

Et le résultat de la première phase. On remarque que Z=0 donc il y a une solution au problème :

programmation linéaire simplexe en deux phases dégénéré méthode du grand M

Pour la deuxième phase on recalcule la ligne Z après avoir retirer les colonnes des variables artificielles. Pour cela on reprend les bons coefficients de la fonction objectif (-1, -1, 0, 0) :

-(0) + (-1 * 6) + (-1 * 4) = -10 pour la colonne b (P0)
-(-1) + (-1 * 1) + (-1 * 0) = 0 pour la colonne P1
-(-1) + (-1 * 0) + (-1 * 1) = 0 pour la colonne P2
-(0) + (-1 * -1 / 6) + (-1 * 1 / 9) = 1 / 18 pour la colonne P3
-(0) + (-1 * 1 / 8) + (-1 * -1 / 6) = 1 / 24 pour la colonne P4

Ce qui donne le simplexe suivant :

programmation linéaire simplexe en deux phases dégénéré méthode du grand M

Tous les coefficients hors colonne b sont positifs donc le simplexe possède déjà la solution optimale qui est Z = 10 avec le vecteur (6, 4, 0, 0).

S’entraîner

Exercice 1

Un revendeur d’électricité a promis à sa clientèle qu’au moins 25% de son électricité serait d’origine renouvelable. Il a calculé que pour l’année qui arrive il aura un marché d’au maximum 18 TWh. Il a aussi présélectionné trois fournisseurs à qui il va acheter son électricité en gros. Voici les quantités (en TWh), le taux d’électricité renouvelable et la marge dégagée (en milliers d’euros/TWh) que peuvent lui fournir ces trois producteurs. Chez quels producteurs et en quelle quantité ce revendeur doit-il acheter son électricité pour avoir le meilleur bénéfice possible ? Résoudre le problème linéaire avec la méthode du grand M à l’aide d’Excel.

programmation linéaire simplexe en deux phases dégénéré méthode du grand M

Correction

Après mise sous forme standard, le problème est le suivant, il y a plus de contraintes que de variables on peut donc résoudre le primal :

programmation linéaire simplexe en deux phases dégénéré méthode du grand M

Le problème se résout en deux phases car il y a une variable artificielle. Voici le tableau de la première phase :

programmation linéaire simplexe en deux phases dégénéré méthode du grand M

Et la solution de la première phase, on remarque que Z=0 donc il y a une solution au problème :

programmation linéaire simplexe en deux phases dégénéré méthode du grand M

Après recalcul des coefficients de Z, la deuxième phase commence avec le tableau suivant :

programmation linéaire simplexe en deux phases dégénéré méthode du grand M

Et se termine avec le tableau suivant :

programmation linéaire simplexe en deux phases dégénéré méthode du grand M

Exercice 2

Résoudre le programme linéaire suivant (par Excel) :

programmation linéaire simplexe en deux phases dégénéré méthode du grand M

Correction

On remarque avant tout qu’il y a plus de variables que de contraintes, il faut donc résoudre le programme linéaire en passant par le simplexe et les écarts complémentaires. Le dual sous forme canonique puis standard est le suivant :

programmation linéaire simplexe en deux phases dégénéré méthode du grand M

Il faut donc résoudre le problème du grand M afin d’éliminer les variables artificielles. Le simplexe à résoudre est le suivant :

programmation linéaire simplexe en deux phases dégénéré méthode du grand M

Ce qui donne pour résultat :

programmation linéaire simplexe en deux phases dégénéré méthode du grand M

En éliminant les variables artificielles et en revenant au programme dual nous avons le tableau suivant :

programmation linéaire simplexe en deux phases dégénéré méthode du grand M

La solution optimale a pour vecteur (3/7, 2/7) avec Z=65/7. Passons par les écarts complémentaires pour trouver une solution au primal.

Les deux variables sont non nulles, donc les contraintes du primal sont saturées. La contrainte 2 et 3 du dual sont non saturées, donc la deuxième et troisième variable du primal sont nulles. Il faut donc résoudre le problème suivant :

  • X1 + 5 X4 = 15
  • 2 X1 – 4 X4 = 10

Le vecteur solution du primal est (55/7, 0, 0, 10/7) et Z=65/7. Il y a dualité forte donc il s’agit d’une solution optimale du primal.

Valider ses compétences

Exercice 3

Lorsque un éco-quartier produit plus d’énergie qu’il n’en consomme, alors il vend le surplus énergétique au voisinage et au réseau. L’éco-quartier cherche donc à maximiser ses gains en fonction des offres du marché local. Les offres du marché sont les suivantes :

Offre n°123456
Profit10815415
Energie (en kWh)51010517

Le problème se formule de la façon suivante : l’éco-quartier cherche à gagner le maximum de profit pour une vente d’énergie de 25 kWh. L’éco-quartier doit vendre la totalité du surplus énergétique.

Correction

Pour résoudre ce problème, considérons que chaque offre est représentée par une variable (en pourcentage d’acceptation de l’offre) qui sera comprise entre 0 et 1.

Le problème se formule comme suit :

programmation linéaire simplexe en deux phases dégénéré méthode du grand M

Ce qui donne comme forme standard :

programmation linéaire simplexe en deux phases dégénéré méthode du grand M

Commençons par résoudre le grand M :

programmation linéaire simplexe en deux phases dégénéré méthode du grand M

Après résolution du grand M et retour sur la forme standard :

programmation linéaire simplexe en deux phases dégénéré méthode du grand M

On remarque que la valeur Z pour la variable 1, 2, 3, 4, 5 sont à zéro donc il y a une infinité de solution. La solution obtenue ici est Z=166/5 avec le vecteur (1, 9/10, 1, 0, 1, 0).

Partager
fr_FRFR
%d blogueurs aiment cette page :