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.
Le programme linéaire est le suivant : X1 pour le premier lot et X2 pour le deuxième lot
Ce qui donne pour résolution graphique :
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.
Il faut résoudre le simplexe en deux phases afin d’éliminer les variables artificielles :
Et le résultat de la première phase. On remarque que Z=0 donc il y a une solution au problème :
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 :
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).
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.
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 :
Le problème se résout en deux phases car il y a une variable artificielle. Voici le tableau de la première phase :
Et la solution de la première phase, on remarque que Z=0 donc il y a une solution au problème :
Après recalcul des coefficients de Z, la deuxième phase commence avec le tableau suivant :
Et se termine avec le tableau suivant :
Exercice 2
Résoudre le programme linéaire suivant (par Excel) :
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 :
Il faut donc résoudre le problème du grand M afin d’éliminer les variables artificielles. Le simplexe à résoudre est le suivant :
Ce qui donne pour résultat :
En éliminant les variables artificielles et en revenant au programme dual nous avons le tableau suivant :
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.
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° | 1 | 2 | 3 | 4 | 5 | 6 |
| Profit | 10 | 8 | 15 | 4 | 1 | 5 |
| Energie (en kWh) | 5 | 10 | 10 | 5 | 1 | 7 |
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.
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 :
Ce qui donne comme forme standard :
Commençons par résoudre le grand M :
Après résolution du grand M et retour sur la forme standard :
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).
