LP : Dual et écart complémentaire (exercices)

Tutoriel

Prenons le programme linéaire suivant :

Résoudre le programme linéaire.

Correction

Il y a quatre variables de base pour deux contraintes, il est possible que le problème ne soit pas borné et ne possède pas de solution. Puisqu’il y a deux contraintes, le dual aura deux variables, il est facile de trouver une solution graphique à ce nouveau programme linéaire.

Le dual est le suivant :

Et voici sa représentation graphique, avec un minimum en (1,1) et pour fonction objectif 15.

Regardons les écarts complémentaires pour trouver une solution du primal.

  • Les deux variables sont non-nulles, donc les deux contraintes du primal sont saturés (la contraintes devient égalité).
  • Dans le dual, les contraintes 1 et 3 sont non saturés pour la solution (1,1), cela signifie que la première variable et la troisième variable du primal sont nulles.

Nous avons donc les deux équations suivantes à résoudre :

  • x2 + 2x4 = 8
  • 2x2 + x4 = 7

Ce qui donne pour solution (0, 2, 0, 3) et pour fonction objectif 15. Les solutions du primal et dual sont égales, il y a dualité forte, il s’agit donc d’une solution optimale.

S’entraîner

Exercice 1

Résoudre le programme linéaire suivant à l’aide du dual (résolution graphique et écarts complémentaires) :

Exercice 2

Prenons le programme linéaire suivant :

Calculer la solution optimale par résolution graphique ou par le simplexe. La fonction objectif a pour nouveau coefficient (3, 5), vérifier que la solution trouvée précédemment est toujours optimal à l’aide du dual et des écarts complémentaires.

Exercice 3

Considérons le programme linéaire suivant :

Tester l’optimalité de la solution (250, 500, 1500) à l’aide du dual et des écarts complémentaires.

La modélisation mathématique s’avère fausse, et après vérification le vecteur b des contraintes est (950, 550, 1575, 6900). A l’aide du dual, vérifier si la solution est admissible et s’il s’agit de la solution optimale, sinon calculer la nouvelle solution.

De même avec le vecteur (1000, 500, 1500, 9750).

Valider ses compétences

Exercice 4

Une entreprise fabrique 3 produits à partir de 3 ressources. Le processus de fabrication de certains produits peut créer certaines ressources (c’est le cas par exemple de la fabrication de certains produits pétroliers). Le premier produit utilise 3 unités de la ressource 1, 1 unité de la ressource 2 et 1 unité de la ressource 3. Le deuxième produit utilise 1 unité des ressources 1 et 3 et produit 1 unité de la ressource 2. Enfin le troisième produit utilise 1 unité de la ressource 1, 2 unités de la ressource 2 et produit 1 unité de la ressource 3. Le premier produit rapporte 4, le troisième rapporte 2, tandis que le deuxième coûte 2 par unité produite. On dispose au départ de 180, 30 et 60 unités des ressources 1, 2 et 3 respectivement.

Ecrire le programme linéaire, le résoudre par le simplexe puis vérifier son optimalité à l’aide du dual et des écarts complémentaires.

Lors de l’injection d’une quantité d’électricité dans le réseau, cette énergie se diffuse à travers les lignes offrant le moins de résistance. Il est possible de connaître les lignes qui seront empruntées par ce flux énergétique à l’aide d’un programme linéaire.

Pour cela il faut définir le réseau et le flux énergétique :

  • le flux part d’une source unique et se diffuse par le chemin avec le moins de résistance vers le consommateur
  • les lignes sont à sens unique, le flux énergétique peut se déplacer que dans le sens du courant transitant déjà sur la ligne

Un réseau est représenté sous la forme d’un graphe comme suivant : les nœuds sont des sous-stations et les arcs représentant les lignes, le nœud 1 est l’origine de la source énergétique, le nœud 7 est la destination du flux énergétique.

Les variables sont les suivantes :

  • pour chaque ligne, une variable comprise entre 0 et 1 donne le pourcentage d’utilisation de la ligne.

La fonction objectif est la suivante :

  • on cherche à minimiser le cout total, c’est à dire la somme des pourcentages d’utilisation des lignes multiplié par le cout de la ligne.

Les contraintes sont les suivantes :

  • pour le nœud d’origine, la somme des variables des arcs sortants moins la somme des variables des arcs entrants est égale à 1
  • pour le nœud d’arrivé, la somme des variables des arcs entrants moins la somme des variables des arcs sortants est égale à 1
  • pour les autres nœuds, la somme des variables des arcs sortants moins la somme des variables des arcs entrants est égale à 0.

Représenter le programme linéaire du graphe précédent, calculer le programme dual et le résoudre via Excel. En déduire le résultat du programme Primal, notons qu’un système d’équation peut se résoudre sur Excel par la commande {=PRODUITMAT(INVERSEMAT(Système); Vecteur cible)} où les coefficients sont donnés sous la forme matricielle.

Ecrire le programme linéaire, le résoudre par le simplexe puis vérifier son optimalité à l’aide du dual et des écarts complémentaires.

Exercice 5

Un îlot énergétique (réseau local coupé du réseau global) possède deux sources énergétiques et trois villages consommateurs. La centrale 1 produit 550 MWh et la centrale 2 produit 350 MWh. Le village 1 demande 400 MWh, le village 2 demande 300 MWh et le village 3 demande 200 MWh. Pour chaque MWh transitant sur une ligne du réseau, le coût en euros est suivant le graphe ci-après :

  1. Exprimer le problème de minimisation du coût de transit de l’énergie des producteurs vers le consommateur, expliquer la fonction objectif et les contraintes
  2. Exprimer le problème de maximisation du profit de transit de l’énergie (point de vue du gestionnaire du réseau).
  3. Résoudre un des problèmes et trouver une solution de l’autre à l’aide des écarts complémentaires.