Td5 programmation linéaire et optimisation -Programmation li

Télécharger PDF

TD 5 : Programmation linéaire, optimisation et dualité

Ce document traite des concepts fondamentaux de la dualité en programmation linéaire à travers une série d'exercices pratiques et de corrigés détaillés.

Exercice 1 : Formulation du problème dual

L'objectif ici est de transformer les problèmes primaux suivants en leurs formes duales respectives.

Cas a) : Problème de maximisation
Primal : Max Z = 2x1 + 4x2 + 3x3
Contraintes :
3x1 + 4x2 + 2x3 ≤ 60
2x1 + x2 + 2x3 ≤ 40
x1 + 3x2 + 2x3 ≤ 80
x1, x2, x3 ≥ 0

Cas b) : Problème de minimisation
Primal : Min Z = 20x1 + 24x2
Contraintes :
x1 + x2 ≥ 30
x1 + 2x2 ≥ 40
x1, x2 ≥ 0

Cas c) : Problème mixte
Primal : Max Z = 10x1 + 6x2
Contraintes :
x1 + 4x2 ≤ 40
3x1 + 2x2 = 60
2x1 + x2 ≥ 25
x1, x2 ≥ 0

Exercice 2 : Corrigé des duaux et analyse des algorithmes

Solutions duales :

a) Min w = 60y1 + 40y2 + 80y3
Sous : 3y1 + 2y2 + y3 ≥ 2 ; 4y1 + y2 + 3y3 ≥ 4 ; 2y1 + 2y2 + 2y3 ≥ 3 ; y1, y2, y3 ≥ 0

b) Max w = 30y1 + 40y2
Sous : y1 + y2 ≤ 20 ; y1 + 2y2 ≤ 24 ; y1, y2 ≥ 0

c) Min w = 40y1 + 60y2 - 25y3
Sous : y1 + 3y2 - 2y3 ≥ 10 ; 4y1 + 2y2 - y3 ≥ 6 ; y1 ≥ 0, y3 ≥ 0, y2 est une variable quelconque (sans restriction de signe car la contrainte associée est une égalité).

Analyse des méthodes de résolution

i) Algorithme dual du simplexe : Cet algorithme permet de passer d'une solution de base du primal à une autre satisfaisant les conditions d'optimalité (vecteur de coût relatif non négatif). L'algorithme se termine lorsque la solution de base devient réalisable pour le primal.

ii) Algorithme primal-dual : Cet algorithme permet de passer d'une solution réalisable pour le problème dual à une autre, tout en s'assurant que la solution satisfait le théorème des écarts complémentaires. L'algorithme s'arrête lorsque la solution primale est enfin réalisable.

Exercice 3 : Application complète du simplexe et déduction du dual

Soit le primal : Max Z = 40x1 + 50x2
Sous : 5x1 + 4x2 ≤ 80 ; x1 + 2x2 ≤ 24 ; 3x1 + 2x2 ≤ 36 ; x1, x2 ≥ 0

1. Dual (PL*) : Min w = 80y1 + 24y2 + 36y3 avec les contraintes 5y1 + y2 + 3y3 ≥ 40 et 4y1 + 2y2 + 2y3 ≥ 50.

2. Résolution du primal : La solution optimale par le simplexe donne x1 = 6 et x2 = 9, avec des variables d'écart s1 = 14, s2 = 0, s3 = 0. La valeur optimale est Z = 690.

3. Solution du dual : À l'optimum, les fonctions objectifs Z et W sont égales. En utilisant les relations de complémentarité : - Puisque x1 et x2 sont non nuls, les contraintes duales sont saturées (égalités). - Puisque s1 > 0, alors y1 = 0. On obtient ainsi y2 = 17,5 et y3 = 7,5, avec W = 690.

Exercice 4 : Optimisation de production (Cas des biscuits)

Un fabricant produit deux variétés de biscuits (Noix de coco x1 et Chocolat x2) avec des ressources limitées en farine, chocolat et noix de coco.

Résultats clés :

Plan de fabrication optimal : Produire x1 = 4 et x2 = 4 pour un profit Z = 44.
Analyse de sensibilité : Le plan reste optimal si le prix de vente du biscuit au chocolat (C2) varie dans l'intervalle [0, 6].
Gestion des stocks : Il reste 2 unités de chocolat inutilisées à l'optimum. La quantité minimale nécessaire pour ne pas compromettre le plan actuel est de 20 unités.
Dualité : Le prix d'ombre (valeur marginale) de la farine est de 5 et celui de la noix de coco est de 1/3, tandis que celui du chocolat est nul car la ressource est en surplus.

Foire aux questions (FAQ)

Qu'est-ce que le théorème des écarts complémentaires ?
C'est un principe stipulant qu'à l'optimum, le produit d'une variable primale par sa contrainte duale associée (ou inversement) est nul. Cela permet de déduire la solution d'un problème à partir de l'autre.

Quelle est l'utilité économique du problème dual ?
Les variables duales représentent les "prix d'ombre". Ils indiquent l'augmentation de la valeur de la fonction objectif pour chaque unité supplémentaire d'une ressource limitée.

Quand utilise-t-on l'algorithme dual du simplexe ?
On l'utilise principalement lorsqu'une solution de base est optimale mais non réalisable (par exemple, après l'ajout d'une nouvelle contrainte ou une modification des ressources).