Optimisation linéaire td3 énoncés -Programmation linaire - R
Télécharger PDFOptimisation Linéaire: Introduction et Méthodes de Résolution
Ce document aborde l'optimisation linéaire, en se concentrant sur la modélisation et la résolution de problèmes. Il introduit la méthode géométrique, les tableaux du simplexe et la méthode des pénalités pour trouver des solutions optimales.
Problème 1 : Gestion d'Investissements
Un investisseur doit choisir entre deux types d'actifs : Ilog et BNP-Paribas. L'action Ilog rapporte une espérance de gain de 80 Euros, et l'action BNP-Paribas 60 Euros. L'investisseur peut acheter un total de 100 actions au maximum et ne compte pas dépenser plus de 800 Euros. L'action Ilog coûte 5 Euros et l'action BNP-Paribas 10 Euros. De plus, une commission de 2 Euros par action Ilog et 1 Euro par action BNP-Paribas est prélevée par la banque, et l'investisseur ne souhaite pas dépasser 150 Euros de commissions.
L'objectif est de déterminer combien d'actions de chaque type l'investisseur doit acheter pour maximiser ses revenus futurs. Ce problème sera modélisé et résolu par la méthode géométrique et la méthode des tableaux du simplexe.
Modélisation du Problème d'Optimisation Linéaire
Variables de décision :
x1: Nombre d'actions Ilogx2: Nombre d'actions BNP-Paribas
Fonction objectif :
Maximiser Z = 80x1 + 60x2 (Gain total)
Contraintes :
x1 + x2 ≤ 100(Nombre total d'actions)5x1 + 10x2 ≤ 800(Coût total d'achat)2x1 + x2 ≤ 150(Commissions bancaires)x1 ≥ 0, x2 ≥ 0(Non-négativité des actions)
Forme Standard pour la Méthode du Simplexe
Pour appliquer la méthode du simplexe, nous transformons le problème de maximisation en un problème de minimisation de l'opposé de la fonction objectif, et les inégalités en égalités en introduisant des variables d'écart.
- Minimiser
W = -Z = -80x1 - 60x2
Contraintes transformées :
x1 + x2 + x3 = 100(x3est la variable d'écart pour la contrainte du nombre d'actions)5x1 + 10x2 + x4 = 800(x4est la variable d'écart pour la contrainte du coût)2x1 + x2 + x5 = 150(x5est la variable d'écart pour la contrainte des commissions)x1, x2, x3, x4, x5 ≥ 0
Tableau Initial du Simplexe
| Base | cB | x1 | x2 | x3 | x4 | x5 | RHS |
|---|---|---|---|---|---|---|---|
| x3 | 0 | 1 | 1 | 1 | 0 | 0 | 100 |
| x4 | 0 | 5 | 10 | 0 | 1 | 0 | 800 |
| x5 | 0 | 2 | 1 | 0 | 0 | 1 | 150 |
| Zj | 0 | 0 | 0 | 0 | 0 | 0 | |
| cj-Zj | -80 | -60 | 0 | 0 | 0 |
Itérations du Simplexe
L'algorithme du simplexe est appliqué en effectuant des changements de base successifs. La variable entrante est choisie en fonction du coefficient cj-Zj le plus négatif (pour la minimisation de W), et la variable sortante est déterminée par le ratio minimum (RHS / coefficient de la variable entrante).
- Première itération :
- Variable entrante :
x1(car-80est le plus négatif). - Calcul des ratios :
100/1 = 100(pour x3),800/5 = 160(pour x4),150/2 = 75(pour x5). - Variable sortante :
x5(ratio minimum de 75). - La nouvelle base devient
(x3, x4, x1). - Deuxième itération :
- Après avoir mis à jour le tableau, une nouvelle variable entrante est sélectionnée (probablement
x2si son coefficientcj-Zjest négatif). - Le calcul des ratios est effectué pour déterminer la variable sortante (selon les calculs du document,
x3quitte la base). - La nouvelle base devient
(x2, x4, x1).
Solution Optimale
Après les itérations nécessaires, le tableau final du simplexe indique la solution optimale lorsque tous les coefficients de la ligne cj-Zj sont non-négatifs.
- Nombre d'actions Ilog (
x1) = 50 - Nombre d'actions BNP-Paribas (
x2) = 50
Avec cette combinaison, les variables d'écart sont :
x3 = 100 - x1 - x2 = 100 - 50 - 50 = 0x4 = 800 - 5x1 - 10x2 = 800 - 5(50) - 10(50) = 800 - 250 - 500 = 50x5 = 150 - 2x1 - x2 = 150 - 2(50) - 50 = 150 - 100 - 50 = 0
Le revenu futur maximisé est Z = 80(50) + 60(50) = 4000 + 3000 = 7000 Euros.
Problèmes avec la Méthode des Pénalités
Pour les problèmes suivants, l'algorithme du simplexe standard ne peut pas être appliqué dès le début car il n'y a pas de base réalisable triviale (par exemple, des contraintes d'égalité ou des contraintes de type "supérieur ou égal" qui nécessitent l'introduction de variables artificielles). La méthode des pénalités (ou Grande M) est utilisée pour établir un premier tableau du simplexe avec une base réalisable.
i) Problème (P.0.1)
Fonction objectif :
Minimiser W = x1 - 2x2 + 2x3
Contraintes :
x1 + x2 - x3 = 3(1)-x1 + 3x2 = -4(2)x1, x2, x3 ≥ 0
Application de la Méthode des Pénalités
Pour obtenir une base réalisable, nous introduisons des variables artificielles pour les contraintes d'égalité. La contrainte (2) est d'abord multipliée par -1 pour avoir un membre de droite positif.
1. Contrainte (1) : x1 + x2 - x3 = 3. Ajout d'une variable artificielle a1.
x1 + x2 - x3 + a1 = 3
2. Contrainte (2) : -x1 + 3x2 = -4 devient x1 - 3x2 = 4. Ajout d'une variable artificielle a2.
x1 - 3x2 + a2 = 4
Fonction objectif modifiée avec pénalités :
Minimiser W' = x1 - 2x2 + 2x3 + M(a1 + a2) où M est une très grande valeur positive.
En substituant a1 = 3 - x1 - x2 + x3 et a2 = 4 - x1 + 3x2 dans W' :
W' = x1 - 2x2 + 2x3 + M(3 - x1 - x2 + x3 + 4 - x1 + 3x2)
W' = x1 - 2x2 + 2x3 + M(7 - 2x1 + 2x2 + x3)
W' = (1 - 2M)x1 + (2M - 2)x2 + (M + 2)x3 + 7M
Premier Tableau du Simplexe avec Base Réalisable
| Base | cB | x1 | x2 | x3 | a1 | a2 | RHS |
|---|---|---|---|---|---|---|---|
| a1 | M | 1 | 1 | -1 | 1 | 0 | 3 |
| a2 | M | 1 | -3 | 0 | 0 | 1 | 4 |
| Zj | 2M | -2M | -M | M | M | 7M | |
| cj-Zj | 1-2M | 2M-2 | M+2 | 0 | 0 |
La base initiale est (a1, a2), qui est réalisable pour le problème artificiel.
ii) Problème (P.0.2)
Fonction objectif :
Minimiser Z = x1 - 2x2
Contraintes :
x1 + x2 + x3 = 3(1)-x1 + 3x2 ≤ -4(2)xi ≥ 0pouri=1, 2, 3
Application de la Méthode des Pénalités
La contrainte (1) est déjà sous forme standard avec la variable d'écart x3. La contrainte (2) doit être ajustée.
1. Contrainte (1) : x1 + x2 + x3 = 3 (x3 est une variable d'écart, donc elle peut faire partie de la base).
2. Contrainte (2) : -x1 + 3x2 ≤ -4. Multiplions par -1 pour avoir un membre de droite positif et changer le sens de l'inégalité :
x1 - 3x2 ≥ 4
Pour cette inégalité de type "supérieur ou égal", nous introduisons une variable excédentaire x4 et une variable artificielle a1 :
x1 - 3x2 - x4 + a1 = 4
Fonction objectif modifiée avec pénalités :
Minimiser W' = x1 - 2x2 + M(a1)
En substituant a1 = 4 - x1 + 3x2 + x4 dans W' :
W' = x1 - 2x2 + M(4 - x1 + 3x2 + x4)
W' = x1 - 2x2 + 4M - Mx1 + 3Mx2 + Mx4
W' = (1 - M)x1 + (3M - 2)x2 + Mx4 + 4M
Premier Tableau du Simplexe avec Base Réalisable
| Base | cB | x1 | x2 | x3 | x4 | a1 | RHS |
|---|---|---|---|---|---|---|---|
| x3 | 0 | 1 | 1 | 1 | 0 | 0 | 3 |
| a1 | M | 1 | -3 | 0 | -1 | 1 | 4 |
| Zj | M | -3M | 0 | -M | M | 4M | |
| cj-Zj | 1-M | 3M-2 | 0 | M | 0 |
La base initiale est (x3, a1), qui est réalisable pour le problème artificiel.
Foire aux Questions (FAQ)
Qu'est-ce que la méthode du simplexe ?
La méthode du simplexe est un algorithme itératif populaire pour résoudre les problèmes d'optimisation linéaire. Elle fonctionne en se déplaçant d'un sommet à l'autre d'une région faisable polyédrique, en cherchant à améliorer la valeur de la fonction objectif à chaque étape, jusqu'à atteindre la solution optimale.
Pourquoi utilise-t-on des variables artificielles et la méthode des pénalités ?
Les variables artificielles sont introduites pour aider à trouver une base réalisable initiale lorsque le problème d'optimisation linéaire contient des contraintes d'égalité ou des contraintes de type "supérieur ou égal". La méthode des pénalités (ou méthode du Grand M) attribue un coût très élevé (M) à ces variables artificielles dans la fonction objectif, garantissant qu'elles seront nulles dans la solution optimale du problème original, si une telle solution existe.
Quelle est la différence entre une variable d'écart et une variable excédentaire ?
Une variable d'écart (slack variable) est ajoutée aux contraintes de type "inférieur ou égal" (≤) pour les transformer en égalités. Elle représente la quantité non utilisée de la ressource. Une variable excédentaire (surplus variable) est soustraite des contraintes de type "supérieur ou égal" (≥) pour les transformer en égalités. Elle représente la quantité par laquelle le côté gauche de la contrainte dépasse le côté droit.